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

Я нашел прохладную статью об этом предмете под названием Самый Длинный Префикс, Соответствующий использующий Фильтры Цветка.

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

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

У Вас есть некоторая запасная память?

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

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;

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