Структура данных поиска IPv6

Question

Патриция - это общеизвестная рекомендуемая структура данных для хранения назначений / назначений IPv4 и выполнения поиска.

Это также верно для адресов IPv6?Просто более глубокий / высокий три для размещения дополнительных 96 бит?Три по-прежнему патриция, или другая радикальная три?

Answer 1

Вы все еще можете использовать попытки Патрисии с большей глубиной, но проблема в том, что производительность падает линейно с глубиной дерева.Разработка специализированных структур данных для поиска IPv6 является активной областью.Среди последних публикаций:

• Динамическая двоичная схема хеширования для поиска IPv6 (PDF)
• Поиск IPv6 с использованием распределенных и сбалансированных по цвету фильтров Блума для 100 Гбит / сЛинейные карты базового маршрутизатора (PDF)
• FlashTrie: основанный на хэш-памяти префиксный трип для поиска по IP-адресу свыше 100 Гбит / с (PDF)

Iне знаю ни одной доступной (с открытым исходным кодом) реализации этих структур данных.