Курсовые и лабораторные работы Математика решение задач Электротехника Лабораторные работы по электронике Физика Информатика На главную
Реализация сервиса виртуальные каналы Алгоритмы маршрутизации Метод заливки Маршрутизация Иерархическая маршрутизация Широковещательная маршрутизация Многоадресная рассылка Борьба с флуктуациями

В CIDR этот простой алгоритм применить не удается. Вместо этого применяется расширение всех записей таблицы маршрутизации за счет добавления 32-битной маски. Таким образом, образуется единая таблица для всех сетей, состоящая из набора троек (IP-адрес, маска подсети, исходящая линия). Что происходит с приходящим пакетом при применении метода CIDR? Во-первых, извлекается IP-адрес назначения. Затем (концептуально) таблица маршрутизации сканируется запись за записью, адрес назначения маскируется и сравнивается со значениями записей. Может оказаться, что по значению подойдет несколько записей (с разными длинами масок подсети). В этом случае используется самая длинная маска. То есть если найдено совпадение для маски /20 и /24, то будет выбрана запись, соответствующая /24.

Был разработан сложный алгоритм для ускорения процесса поиска адреса в таблице (Ruiz-Sanchez и др., 2001). В маршрутизаторах, предполагающих коммерческое использование, применяются специальные чипы VLSI, в которые данные алгоритмы встроены аппаратно.

Чтобы лучше понять алгоритм маршрутизации, рассмотрим пример. Допустим, имеется набор из миллионов адресов, начиная с 194.24.0.0. Допустим также, что Кембриджскому университету требуется 2048 адресов, и ему выделяются адреса от 194.24.0.0 до 194.24.7.255, а также маска 255.255.248.0. Затем Оксфордский университет запрашивает 4096 адресов. Так как блок из 4096 адресов должен располагаться на границе, кратной 4096, то ему не могут быть выделены адреса начиная с 194.24.8.0. Вместо этого он получает адреса от 194.24.16.0 до 194.24.31.255 вместе с маской 255.255.240.0. Затем Эдинбургский университет просит выделить ему 1024 адреса и получает адреса от 194.24.8.0 до 194.24.11.255 и маску 255.255.252.0. Все эти присвоенные адреса и маски сведены в табл. 5.7.

Таблица 5.7. Набор присвоенных 1Р-адресов Представительный уровень Информационно-вычислительные системы и сети

Университет

Первый адрес

Последний адрес

Количество

Форма записи

Кембридж

194.24.0.0

194.24.7.255

2048

194.24.0.0/21

Эдинбург

194.24.8.0

94.24.11.255

1024

194.24.8.0/22

(Свободно)

194.24.12.0

94.24.15.255

1024

194.24.12.0/22

Оксфорд

194.24.16.0

94.24.16.255

4096

194.24.16.0/20

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

К: 11000010 00011000 00000000 00000000 11111111 11111111 11111000 00000000 Э: 11000010 00011000 00001000 00000000 11111111 11111111 11111100 00000000 0:11000010 00011000 00010000 00000000 11111111 11111111 11110000 00000000 Теперь посмотрим, что произойдет, когда пакет придет по адресу 194.24.17.4. В двоичном виде этот адрес представляет собой следующую 32-битную строку:

11000010 00011000 00010001 00000100 Сначала на него накладывается (выполняется логическое И) маска Кембриджа, в результате чего получается

11000010 00011000 00010000 00000000

Это значение не совпадает с базовым адресом Кембриджа, поэтому на оригинальный адрес накладывается маска Оксфорда, что дает в результате

11000010 00011000 00010000 00000000

Это значение совпадает с базовым адресом Оксфорда. Если далее по таблице совпадений нет, то пакет пересылается Оксфордскому маршрутизатору. Теперь посмотрим на эту троицу университетов с точки зрения маршрутизатора в Омахе, штат Небраска, у которого есть всего четыре выходных линии: на Миннеаполис, Нью-Йорк, Даллас и Денвер. Получив три новых записи, маршрутизатор понимает, что он может скомпоновать их вместе и получить одру агрегированную запись, состоящую из адреса 194.24.0.0/19 и подмаски: 11000010 00000000 00000000 00000000 11111111 11111111 11100000 00000000 В соответствии с этой записью пакеты, предназначенные для любого из трех университетов, отправляются в Нью-Йорк. Объединив три записи, маршрутизатор в Омахе уменьшил размер своей таблицы на две строки.

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

И последнее замечание по данному примеру. Та же самая агрегированная запись маршрутизатора в Омахе используется для отправки пакетов по не присвоенным адресам в Нью-Йорк. До тех пор, пока адреса остаются не присвоенными, это не имеет значения, поскольку предполагается, что они вообще не встретятся. Однако если в какой-то момент этот диапазон адресов будет присвоен какой-нибудь калифорнийской компании, для его обработки понадобится новая запись: 194.24.12.0/22.

 


Сетевой уровень Управление доступом У каждого хоста и маршрутизатора в Интернете есть IP-адрес