алгоритм Лулео

Методика хранения и поиска таблиц маршрутизации в Интернете

Алгоритм компьютерной науки Лулео , разработанный Дегермарком и др. (1997), представляет собой метод эффективного хранения и поиска таблиц маршрутизации в Интернете . Он назван в честь Технологического университета Лулео , родного института/университета авторов метода. Название алгоритма не появляется в оригинальной статье, описывающей его, но было использовано в сообщении Крейга Партриджа в Internet Engineering Task Force, описывающем эту статью до ее публикации. ^[1]

Ключевая задача, которую необходимо выполнить при маршрутизации в Интернете, — сопоставить заданный адрес IPv4 (рассматриваемый как последовательность из 32 бит) с самым длинным префиксом адреса, для которого доступна информация о маршрутизации. Эту проблему сопоставления префиксов можно решить с помощью trie , но структуры trie используют значительный объем пространства ( узел для каждого бита каждого адреса), и для их поиска требуется пройти по последовательности узлов с длиной, пропорциональной количеству бит в адресе. Алгоритм Лулео сокращает этот процесс, сохраняя только узлы на трех уровнях структуры trie, а не сохраняя все trie.

Перед построением Luleå trie записи таблицы маршрутизации должны быть предварительно обработаны. Любой больший префикс, который перекрывает меньший префикс, должен быть многократно разделен на меньшие префиксы, и только разделенные префиксы, которые не перекрывают меньший префикс, сохраняются. Также требуется, чтобы дерево префиксов было полным. Если нет записей таблицы маршрутизации для всего адресного пространства, оно должно быть дополнено путем добавления фиктивных записей, которые несут только информацию о том, что для этого диапазона нет маршрута. Это позволяет упростить поиск в Luleå trie (Sundström 2007).

Главное преимущество алгоритма Лулео для задачи маршрутизации заключается в том, что он использует очень мало памяти, в среднем 4–5 байт на запись для больших таблиц маршрутизации. Этот небольшой объем памяти часто позволяет всей структуре данных поместиться в кэш процессора маршрутизации, ускоряя операции. Однако у него есть недостаток, заключающийся в том, что его нельзя легко модифицировать: небольшие изменения в таблице маршрутизации могут потребовать реконструкции большей части или всей структуры данных. Современный домашний компьютер (ПК) имеет достаточно оборудования/памяти для выполнения алгоритма.

Первый уровень

Первый уровень структуры данных состоит из

• Битовый вектор, состоящий из 2 ¹⁶ = 65 536 бит, с одной записью для каждого 16-битного префикса адреса IPv4 . Бит в этой таблице устанавливается в единицу, если есть информация о маршрутизации, связанная с этим префиксом или с более длинной последовательностью, начинающейся с этого префикса, или если данный префикс является первым, связанным с информацией о маршрутизации на некотором более высоком уровне trie; в противном случае он устанавливается в ноль.
• Массив 16-битных слов для каждого ненулевого бита в битовом векторе. Каждый элемент данных либо предоставляет индекс, указывающий на объект структуры данных второго уровня для соответствующего префикса, либо предоставляет информацию о маршрутизации для этого префикса напрямую.
• Массив «базовых индексов», по одному для каждой последовательной подпоследовательности из 64 бит в битовом векторе, указывающий на первый элемент данных, связанный с ненулевым битом в этой подпоследовательности.
• Массив "кодовых слов", по одному для каждой последовательной подпоследовательности из 16 бит в битовом векторе. Каждое кодовое слово имеет длину 16 бит и состоит из 10-битного "значения" и 6-битного "смещения". Сумма смещения и связанного базового индекса дает указатель на первый элемент данных, связанный с ненулевым битом в данной 16-битной подпоследовательности. 10-битное значение дает индекс в "maptable", из которого можно найти точное положение соответствующего элемента данных.
• Таблица сопоставления. Поскольку дерево префиксов должно быть полным, в битовом векторе может существовать только ограниченное количество возможных значений 16-битной битовой маски, 678. Строки таблицы сопоставления соответствуют этим 678 16-битным комбинациям, а столбцы — количеству установленных битов в битовой маске в битовом местоположении, соответствующем столбцу, минус 1. Таким образом, столбец 6 для битовой маски 1010101010101010 будет иметь значение 2. Таблица сопоставления является постоянной для любого содержимого таблицы маршрутизации.

Чтобы найти данные для заданного адреса x на первом уровне структуры данных, алгоритм Лулео вычисляет три значения:

1. базовый индекс в позиции в массиве базовых индексов, индексированный первыми 10 битами x
2. смещение в позиции в массиве кодовых слов, индексированное первыми 12 битами x
3. значение в maptable[ y ][ z ], где y — индекс maptable из массива кодовых слов, а z — биты 13–16 x

Сумма этих трех значений дает индекс, который следует использовать для x в массиве элементов.

Второй и третий уровни

Второй и третий уровни структуры данных структурированы аналогично друг другу; на каждом из этих уровней алгоритм Лулео должен выполнять сопоставление префиксов на 8-битных величинах (биты 17–24 и 25–32 адреса соответственно). Структура данных структурирована в «куски», каждый из которых позволяет выполнять эту задачу сопоставления префиксов на некоторой подпоследовательности адресного пространства; элементы данных из структуры данных первого уровня указывают на эти куски.

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

Примечания

1. «Вторая поездка в Европу для членов IETF... Архивировано 19 августа 2012 г. на Wayback Machine », Крейг Партридж в IETF, 1 мая 1997 г.

Ссылки

• Дегермарк, Микаэль; Бродник, Андрей; Карлссон, Сванте; Пинк, Стивен (1997), «Малые таблицы пересылки для быстрого поиска маршрутов», Труды конференции ACM SIGCOMM '97 по приложениям, технологиям, архитектурам и протоколам для компьютерной связи, Технический университет Лулео, стр. 3–14, doi : 10.1145/263105.263133 , ISBN 0-89791-905-X, S2CID  17232414.

• US 6266706, Дегермарк, Микаэль; Бродник, Андрей и Карлссон, Сванте и др., «Система быстрого поиска маршрутизации, использующая полное дерево префиксов, битовый вектор и указатели в таблице маршрутизации для определения того, куда направлять IP-дейтаграммы», выпущен в 2001  г.

• Medhi, Deepankar; Ramasamy, Karthikeyan (2007), Сетевая маршрутизация: алгоритмы, протоколы и архитектуры , Elsevier, стр. 510–513, ISBN 978-0-12-088588-6.

• Сундстрём, Микаэль (2007), Эффективные по времени и пространству алгоритмы для классификации и пересылки пакетов (кандидатская диссертация), Технологический университет Лулео.