Поиск записей в таблицах маршрутизации
Как уже отмечалось ранее, поиск нужной строки в таблице маршратизации выполняется значительно медленнее, чем в таблице коммутации. И связано это не только с большим количеством записей в таблице, но и с самим алгоритмом, который является многопроходным.
Алгоритм просмотра таблиц без использования масок
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. Пример таблицы маршрутизации с масками подсетей
Сети назначения | Маска | Адрес следующего маршрутизатора | Номер собственного выходного порта | Расстояние до сети назначения (число промежуточных узлов) |
129.44.0.0. | 255.255.192.0 | 129.44.0.1 | 129.44.0.1 | Подключена |
129.44.64.0. | 255.255.192.0 | 129.44.64.7 | 129.44.64.7 | Подключена |
129.44.128.0. | 255.255.192.0 | 129.44.128.5 | 129.44.128.5 | Подключена |
131.54.191.0 | 255.255.192.0 | 129.44.192.2 | 129.44.192.1 | |
129.44.192.0 | 255.255.192.0 | 129.44.192.1 | 129.44.192.1 | Подключена |
0.0.0.0. | 0.0.0.0 | 129.44.192.2 | 129.44.192.1 | - |
129.44.128.15 | 255.255.255.255 | 129.44.64.8 | 129.44.64.7 | Подключена |