Каков наилучший способ реализации поиска longest-prefix для ipv6?

Question

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

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

Answer 1

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

Answer 2

Я считаю, что наиболее эффективным способом вычисления самого длинного общего префикса в целом является suffix tree или suffix array (продолжительность выполнения линейна по длине префикса после предварительной обработки).

Answer 3

У вас есть резервная копия?

Сделать структуру, как это:

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

Теперь вы можете сделать Lookups так:

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

Answer 4

Я нашел cool paper на эту тему называется Longest Prefix Matching using Bloom Filters.

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

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