8. Cхема ip-маршрутизации. Упрощенная таблица маршрутизации. Маршрутизация без и с использованием масок. Алгоритмы динамической маршрутизации. Методы выбора оптимального пути

Рассм. мех-м IР-маршр-ции на примере составной сети, представ­ленной на рис. 18.2. В этой сети 20 маршр-ов (изображенных в виде про­нумерованных квадрантных блоков) объединяют 18 сетей в общую сеть; N1, N2,..., N18 — это № сетей. На каждом маршр-ре и кон. узлах А и В установлены протоколы IР.

Маршр-ры имеют по неск.интерфейсов (портов), к которым присо­единяются сети. Каждый интерфейс маршр-ра можно рассматривать как отд.узел сети: он имеет сетевой адрес и лок.адрес в той подсети, которая к нему подключена. Напр, маршр-р под № 1 имеет 3 интерфейса, к которым подключены сети N1, N2, N3. На рисунке сетевые адреса этих портов обозначены IР₁₁, IР₁₂ и . IР₁₃ Интерфейс IР₁₁ является узлом сети N1, и следовательно в поле номера сети порта IР₁₁ сод-ся номер N1. Аналогич­но интерфейс IР₁₂ — узел в сети N2, а порт IР₁₃ — узел в сети N3. Т.о., маршр-р можно рассматривать как сов-ть неск.узлов, каж­дый из которых входит в свою сеть. Как единое устройство маршр-р не имеет ни отд-го сетевого, ни лок. адреса.

В сложных составных сетях почти всегда сущ-ют неск. альтернативных маршрутов для передачи пакетов между двумя конечными узлами. Так, пакет, отправленный из узла А в узел В, может пройти через маршр-ры 17, 12, 5, 4 и 1 или маршр-ры 17, 13, 7, 6 и 3. Нетрудно найти еще неск.мар­шрутов м/у узлами А и В. Задачу выбора маршрута из нескольких возможных решают маршр-ры, а также кон.узлы. Маршрут выбирается на основании имеющейся у этих устройств информации о текущей конфигурации сети, а также на основании критерия выбора маршрута. В кач-ве критерия часто выступает задержка прохождения маршрута отдельным пакетом, средняя пропускная способность мар­шрута для послед-ти пакетов или наиболее простой критерий, учиты­вающий только кол-во пройденных в маршруте промежуточных маршр-ов (ретрансляционных участков, или хопов). Полученная в рез-те анализа инфа о маршрутах дальнейшего следования пакетов помещается в таблицу маршрутизации.

Упрощенная таблица маршрутизации

Используя условные обозначения для сетевых адресов маршр-ов и номе­ров сетей в том виде, как они приведены на рис. 18.2, посмотрим, как могла бы выглядеть таблица маршрутизации, например, в маршрутизаторе 4 (табл. 18.1).

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

[8.1]

Перед тем как передать пакет след. маршр-ру, текущий маршр-р должен определить, на какой из нескольких собственных портов (IР₄₁ или IР₄₂) он должен поместить данный пакет. Для этого служит третий столбец таб­лицы маршрутизации, содержащий сетевые адреса выходных интерфейсов.

Некот. реализации сетевых протоколов допускают наличие в табл. мар­шрутизации сразу нескольких строк, соответствующих одному и тому же адресу назначения. В этом случае при выборе маршрута принимается во внимание стол­бец «расстояние до сети назначения». При этом расстояние измеряется в любой метрике, используемой в соответствии с заданным в сетевом пакете критерием. Расстояние может измеряться временем прохождения пакета по линиям связи, различными характеристиками надежности линий связи на данном маршруте, пропускной способностью или другой величиной, отражающей качество данного маршрута по отношению к заданному критерию. В табл. 18.1 расстояние м/у сетями измеряется хопами. Расстояние для сетей, непосредственно подключен­ных к портам маршр-ра, здесь принимается =0, однако в некоторых реализациях отсчет расстояний начинается с 1. Когда пакет поступает на маршр-р, модуль IР извлекает из поступившего заголовка кадра № сети назначения и послед-но сравнивает его с № сетей из каждой строки таблицы. Строка с совпавшим № сети ука­зывает ближайший маршр-р, на кот.следует направить пакет. Напр, если на какой-либо порт маршр-ра 4 поступает пакет, адресованный в сеть N6, то из табл маршр-ции следует, что адрес след.маршр-ра — IР₂₁, т.е. очередным этапом движения данного пакета будет дви­жение к порту 1 маршр-ра 2.

Чаще всего в кач-ве адреса назначения в таблице указывается не весь IР-адрес, а только номер сети назначения. Т.о, для всех пакетов, направляе­мых в одну и ту же сеть, протокол IР будет предлагать 1 и тот же маршрут (мы пока не принимаем во внимание возможные изменения в состоянии сети — отказы маршрутизаторов или обрывы кабелей). Однако в некоторых случаях возникает необходимость для одного из узлов сети определить специфический маршрут, отличающийся от маршрута, заданного для всех остальных узлов сети. Для этого в таблицу маршрутизации помещают для данного узла отдельную стро­ку, содержащую его полный IР-адрес и соотв-щую маршрутную инф-ю. Такого рода запись имеется в табл. 18.1 для узла В. Пусть, напр, ад­министратор маршр-ра 4, руководствуясь соображениями безопасности, ре­шил, что пакеты, следующие в узел В (полный адрес IР_В), должны идти через маршрутизатор 2 (интерфейс IР₂₁), а не маршрутизатор 1 (интерфейс IР₁₂), че­рез который передаются пакеты всем остальным узлам сети N3. Если в табли­це имеются записи о маршрутах как к сети в целом, так и к ее отд-му узлу, то при поступлении пакета, адресованного данному узлу, маршр-р отдаст предпочтение специфическому маршруту.

Поскольку пакет может быть адресован в любую сеть составной сети, может по­казаться, что каждая таблица маршр-ции должна иметь записи обо всех се­тях, входящих в составную сеть. Но при таком подходе в случае крупной сети объем таблиц марш-ции может оказаться очень большим, что повлияет на время ее просмотра, потребует много места для хранения и т. п. Поэтому на прак­тике широко известен прием уменьшения кол-ва записей в таблице мар­шр-ции, основанный на введении маршрута по умолчанию (defaulte route). В этом приеме используются особенности топологии сети. Рассмотрим, напри­мер, маршр-ры, находящиеся на периферии составной сети. В их таб­лицах дост-но записать номера только тех сетей, которые непосредственно подсоединены к данному маршр-ру или расположены поблизости, на ту­пиковых маршрутах. Обо всех же остальных сетях можно сделать в таблице единств. запись, указывающую на маршр-р, через который пролега­ет путь ко всем этим сетям. Такой маршр-р называется маршр-ом по умолчанию (defaulte route). В нашем примере маршр-р 4

[8.2]

указывает специфические маршруты только для пакетов, следующих в сети N1-N6. Для всех остальных пакетов, адресованных в сети N7-N18, маршрутизатор предлага­ет продолжить путь через один и тот же порт IР₅₁, маршрутизатора

Марш-ция с исп-ем масок

Алгоритм маршр-ции усложняется, когда в с-му адресации узлов вно­сятся доп.эл-ты — маски. В чем же причины отказа от хорошо себя зарекомендовавшего в течение многих лет метода адресации, основанного на классах? Основная из них — потребность в структуризации сетей в условиях дефицита нераспределенных номеров сетей.

Часто админы сетей испытывают неудобства, поскольку кол-ва централизованно выделенных им номеров сетей недостаточно для того, чтобы структурировать сеть надлежащим образом, напр, развести все слабо взаи­модействующие компы по разным сетям, В такой ситуации возможны 2 пути. Первый из них связан с получением от какого-либо центрального органа доп.номеров сетей. Второй способ, употребляющийся чаще, связан с исп-ем технологии масок, которая позволяет разделить 1 сеть на несколько сетей.

Просмотр таблиц маршрутизации с учетом масок

Алгоритм просмотра таблиц маршр-ции, содержащих маски, имеет много общего с описанным выше алгоритмом просмотра таблиц, не содержащих маски. Однако в нем имеются и существенные изменения.

1.Поиск следующего маршр-ра для вновь поступившего IР-пакета про­токол начинает с того, что извлекает из пакета адрес назначения (обозначим его IРd). Затем протокол IР приступает процедуре просмотра таблицы мар­шрутизации, также состоящей из 2х фаз, как и процедура просмотра табли­цы, в которой столбец маски отсутствует.

2. Первая фаза состоит в поиске специфического маршрута для адреса IРd .С этой целью из каждой записи таблицы, в которой маска имеет значение 255.255.255.255, извлекается адрес назначения и сравнивается с адресом из пакета IРd. Если в какой-либо строке совпадение произошло, то адрес сле­дующего маршр-ра для данного пакета берется из данной строки.

3. Вторая фаза выполняется только в том случае, если во время первой фазы не произошло совпадения адресов. Она состоит в поиске неспецифического мар­шрута, общего для группы узлов, к которой относится и пакет с адресом IРd .Для этого IР заново просматривает таблицу маршр-ции, причем с каж­дой записью производятся следующие действия:

a. маска (обозначим ее М), содержащаяся в данной записи, «накладывается» на IР-адрес узла назначения IР_D, извлеченный из пакета: IРd АND М;

b. полученное в рез-те число сравнивается со зн-ем, кот. поме­щено в поле адреса назначения той же записи таблицы маршрутизации;

c. если происходит совпадение, протокол IР соответствующим образом от­мечает эту строку;

d. если просмотрены не все строки, то IР-протокол аналогичным образом про­сматривает след.строку, если все (включая строку о маршруте по умолчанию), то просмотр записей заканчивается и происходит переход к след.шагу.

4. После просмотра всей таблицы маршр-р вып-ет 1 их 3 дей­ствий:

1) если не произошло ни 1 совпадения и маршрут по умолчанию отсут­ствует, то пакет отбрасывается;

2) если произошло 1 совпадение, то пакет отправляется по маршруту, указанному в строке с совпавшим адресом;

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

Протокол IP является дейтаграммным, т.о не дает никаких гарантий надежной доставки сообщений.

Важной особ-ю протокола IР, отличающей его от др. сетевых протоколов, напр от сетевого протокола IРХ, является его способность выполнять динамическую фрагментацию пакетов при передаче их м/у сетями с различными, максимально допустимыми значениями длины поля данных кадров (МТU).

Max длина IР-пакета составляет 65 535 байт. Заголовок обычно имеет длину 20 байт и сод-ит инфу о сетевых адресах отправителя и получателя, пар-ры фрагмента­ции, время жизни пакета, контр.сумму и некоторые другие параметры.

[8.3]

Вид таблицы IР-маршр-ции зависит от конкретной реализации маршр-ра. Несмот­ря на значит. внешние различия выводимых на экран таблиц, все они включают 2обя­зательных поля, без которых невозможно выполнять маршрутизацию, — это поля адресов на­значения и следующего маршрутизатора.

Записи в таблицу маршр-ции могут поступать из разных источников. Во-1, в рез-те конфигурирования ПО стека ТСР/IР заносит в табл. записи о непосредственно подключенных сетях и маршр-ах по умолчанию, а также записи об особых адресах. Во-2, админ вручную заносит записи о специфических мар­шрутах и о маршруте по умолчанию. В-3, протоколы маршр-ции автоматически за­носят в табл.динамические записи об имеющихся маршрутах.

Эффект.ср-ом структуризации IР-сетей явл. маски. Маски позволяют разделить 1 сеть на неск подсетей или объединить неск.сетей в одну более крупную сеть.

Значительная роль в будущем IР-сетей отводится технологии бесклассовой междоменной маршрутизации. которая решает 2 осн.задачи. 1-ая состоит в более эконом­ном расходование адресного пространства, 2-ая — в уменьшении числа записей в таблицах (1 запись может представлять мн-во сетей, объединенных общим префиксом).

В начале 90-х годов стек протоколов ТСР/IР столкнулся с серьезными проблемами, которые нельзя было решить без изменения формата IР-пакета и логики обработки полей заголовка IР- пакетов. В рез-те сообщество Интернета решило создать нов.версию протокола IР (IРv6), выбрав в кач-ве осн.целей модернизации создание масштабируемой схемы ад­ресации; повышение пропускной способности сети за счет сокращения работ, выполняемых маршр-ми;предоставление гарантий кач-ва трансп.услуг;обесп-е защиты данных, перед-ых по сети.

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

Ниже приведен алгоритм просмотра таблицы маршр-ции протоколом IР, установленным на маршрутизаторе. При его описании мы будем использовать табл. 18.1 и рис. 18.2.

Пусть на один из интерфейсов маршр-ра поступает пакет. Протокол IР извлекает из пакета IР-адрес назначения (предположим, адрес назначения IР_В).

Выполняется первая фаза просмотра таблицы — поиск конкретного маршру­та к узлу. IР-адрес (целиком) последовательно строка за строкой сравнивает­ся с содержимым поля адреса назначения таблицы маршр-ции. Если произошло совпадение (как в табл. 18.1), то из соответствующей строки из­влекаются адрес следующего маршр-ра (IР₂₁) и идентификатор выход­ного интерфейса (IР₄₁) На этом просмотр таблицы заканчивается.

Предположим теперь, что в таблице нет строки с адресом назначения IРв, а зна­чит, совпадения не произошло. В таком случае протокол IР переходит ко второй фазе просмотра - поиску маршрута к сети назначения. Из IР-адреса выделяется номер сети (в нашем примере из адреса IР_В выделяется номер сети N3), и таблица снова просматривается на предмет совпадения номера сети в какой-либо строке с номером сети из пакета. При совпадении (а в нашем при­мере оно произошло) из соответствующей строки таблицы извлекаются адрес следующего маршрутизатора (IР₁₂) и идентификатор выходного интерфейса (IР₄₁). Просмотр таблицы на этом завершается.

Наконец, предположим, что адрес назначения в пакете был таков, что совпа­дения не произошло ни в первой, ни во второй фазах просмотра. В таком случае протокол IР либо выбирает маршрут по умолчанию (и пакет направляется по адресу IР₅₁), либо, если маршрут по умолчанию отсутствует, отбрасывает па­кет. Просмотр таблицы на этом заканчивается.

Алгоритмы динамической маршрутизации

Самыми распространенными являются алгоритмы адаптивной (или динамической) маршрутизации. Эти алгоритмы обеспечивают автоматическое обновление таблиц маршрутизации после изменения конфигурации сети. Протоколы, построенные на основе адаптивных алгоритмов, позволяют всем маршрутизаторам собирать информацию о топологии связей в сети, оперативно отрабатывая все изменения конфигурации связей. В таблицах маршрутизации при адаптивной маршрутизации обычно имеется информация об интервале времени, в течение которого данный маршрут будет оставаться действительным. Это время называют временем жизни маршрута (Time To Live, TTL).

[8.4]

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

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

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

-дистанционно-векторные алгоритмы (Distance Vector Algorithms, DVA);

- алгоритмы состояния связей (Link State Algorithms, LSA).

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

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

Наиболее распространенным протоколом, основанным на дистанционно-векторном алгоритме, является протокол RIP, который распространен в двух версиях - RIP IP, работающий с протоколом IP, и RIP IPX, работающий с протоколом IPX.

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

Чтобы понять, в каком состоянии находятся линии связи, подключенные к его портам, маршрутизатор периодически обменивается короткими пакетами HELLO со своими ближайшими соседями. Этот служебный трафик также засоряет сеть, но не в такой степени как, например, RIP-пакеты, так как пакеты HELLO имеют намного меньший объем.

Протоколами, основанными на алгоритме состояния связей, являются протоколы IS-IS (Intermediate System to Intermediate System) стека OSI, OSPF (Open Shortest Path First) стека TCP/IP и недавно реализованный протокол NLSP стека Novell.