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

Question

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

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

Answer 1

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

Answer 2

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

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

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

Answer 3

У вас есть запасная память?

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

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;

Answer 4

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