Как лучше всего реализовать сопоставление самого длинного префикса для ipv6?

Question

Маршрутизатор ipv6 сохраняет несколько маршрутов в качестве первых. n биты адреса.В 2000 году исследователи обнаружили только 14 различных длин префиксов в 1500 маршрутах ipv6.Входящие пакеты направляются на разные исходящие порты на основе совпадения самого длинного префикса, поэтому, если первые 8 бит пакета x соответствуют 8-битному маршруту, а первые 48 бит того же пакета соответствуют 48-битному маршруту, тогда маршрутизатор должен выбрать 48-битный маршрут.

Мой маршрутизатор обрабатывает так много пакетов, что скорость поиска в памяти таблицы маршрутизации является ограничивающим фактором.Каков хороший алгоритм для поиска самого длинного совпадающего префикса в моей таблице маршрутизации?

Answer 1

Используйте либо попробовать или поразрядное дерево для хранения «стандартных» префиксов.Суффиксное дерево/массив — это ненужное избыточное уничтожение;они используются для поиска совпадений между инфиксы (используя тот факт, что любой инфикс является префиксом суффикса, и если вы хотите найти совпадение между несколькими строками, соедините их друг с другом), а не только между префиксами.

Answer 2

Я нашел классная бумага на эту тему позвонил Сопоставление самого длинного префикса с использованием фильтров Блума.

Абстрактный: Мы представляем первый известный нам алгоритм, использующий фильтры Блума для сопоставления самых длинных префиксов (LPM).Алгоритм выполняет параллельные запросы к фильтрам Блума, эффективной структуре данных для запросов на членство, чтобы определить принадлежность префикса адреса к наборам префиксов, отсортированных по длине префикса.Мы показываем, что использование этого алгоритма для поиска маршрутизации по Интернет-протоколу (IP) приводит к тому, что поисковая система обеспечивает лучшую производительность и масштабируемость, чем подходы на основе TCAM.

Их основная идея состоит в том, чтобы использовать фильтры Блума, хранящиеся во встроенной SRAM процессора (быстрой), для направления поиска по хеш-таблице префиксов в более медленной, но более обширной памяти.В случае IPv4 они настраивают свой алгоритм с учетом того факта, что большинство префиксов таблицы маршрутизации имеют длину 24 бита.Для IPv6 они обнаружили только 14 уникальных длин префиксов в 1550 записях BGP.

Answer 3

Я считаю, что наиболее эффективный способ вычислить самый длинный общий префикс в целом — это суффиксное дерево или массив суффиксов (время выполнения линейно зависит от длины префикса после предварительной обработки).

Answer 4

У вас есть свободная память?

Сделайте такую ​​структуру:

typedef struct node {
  struct node* table[256];
  Port_type port;
} Node;
Node* root[256];

Теперь вы можете выполнять поиск следующим образом:

Node* table = root;
for (i=0; table != NULL; i++)
{
   node = table[address_byte[i]];
   table = node->table;
}
destination = node->port;