Особенности алгоритма поиска с использованием масок

Поиск записей в таблицах маршрутизации

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

Алгоритм просмотра таблиц без использования масок

1. Сначала выполняется первая фаза просмотра таблицы, в которой при последовательном просмотре ее строк ищется специфический маршрут к узлу назначения, т.е. полное совпадение IP- адреса получателя (номера сети и номера узла) с полем сети назначения. Если совпадение произошло и нужная строка найдена, из нее извлекается адрес следующего маршрутизатора и идентификатор выходного порта маршрутизатора. На этом просмотр таблицы заканчивается.

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

3. Если строка с искомым номером сети не найдена, то выбирается строка с записью о маршруте по умолчанию. А, если такая запись отсутствует, то пакет отбрасывается.

Следует отметить, что последовательность фаз алгоритма строго определена и не зависит от последовательности записей в таблице.

Рассмотрим алгоритм поиска маршрута в таблице маршрутизации, которая содержит маски подсетей. Из поступившего IP-пакета извлекается IP- адрес получателя, и IP-протокол приступает к просмотру таблицы маршрутизации.

1. Сначала, как и в случае маршрутизации без масок, в таблице ищется специфический маршрут к узлу назначения (полное совпадение номера сети и номера узла). Для этого из каждой записи таблицы с маской 255.255.255.255 извлекается адрес назначения и сравнивается с адресом получателя. Если совпадение произошло, то адрес следующего маршрутизатора и номер выходного порта маршрутизатора берется из этой строки

2. Если специфический маршрут не найден, ищется неспецифический маршрут к сети назначения (совпадение только номера сети назначения). Из строк таблицы последовательно берутся маски и умножаются (операция конъюнкции - логическое «И») на адрес назначения, а полученный результат сравнивается с полем сети назначения в данной строке. Если происходит совпадение, IP-протокол отмечает данную строку.

3. Если просмотрены все записи таблицы, включая запись по умолчанию, маршрутизатор анализирует отмеченные строки.

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

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

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

Наложение маски (в данном случае одинаковой) на искомый адрес дает:

11111111.11111111.11000000.00000000 & 10000001.0101100.01001110.11001000=

10000001.0101100.01000000.00000000 =129.44.64.0

Сравнение даст частичное совпадение со всеми строками, кроме 4-й (последняя строка с маской 255.255.255.255 в этой фазе участия не принимает). Выбирается строка с наибольшим количеством совпавших бит – наиболее специфический маршрут.

В результате пакет отправится на порт 129.44.64.7, к которому непосредственно подключена сеть 129.44.64.0.

Таблица 7.1. Пример таблицы маршрутизации с масками подсетей