Алгоритм Лулео - Luleå algorithm

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

  1. ^ "вторая поездка в Европу для IETFers ... ", Крейг Партридж на конференции IETF, 1 мая 1997 г.

Рекомендации

  • Дегермарк, Микаэль; Бродник, Андрей; Карлссон, Сванте; Пинк, Стивен (1997), «Небольшие таблицы пересылки для быстрого поиска маршрутизации», Материалы конференции ACM SIGCOMM '97 по приложениям, технологиям, архитектурам и протоколам для компьютерной связи, стр. 3–14, Дои:10.1145/263105.263133, S2CID  17232414.
  • США 6266706, Дегермарк, Микаэль; Андрей Бродник и Сванте Карлссон и др., «Система быстрого поиска маршрутизации с использованием полного дерева префиксов, битового вектора и указателей в таблице маршрутизации для определения, куда направлять дейтаграммы IP», выпущенный в 2001 г. .
  • Медхи, Дипанкар; Рамасами, Картикеян (2007), Сетевая маршрутизация: алгоритмы, протоколы и архитектуры, Elsevier, стр. 510–513, ISBN  978-0-12-088588-6.
  • Сундстрём, Микаэль (2007), "Эффективные по времени и пространству алгоритмы для классификации и пересылки пакетов", Докторская диссертация, ISSN  1402-1544.