Проблема счета до бесконечности

Установление маршрутов, соответствующих кратчайшим путям, в сети называется конвергенцией ( convergence ). Алгоритм маршрутизации по вектору расстояний — простой метод, позволяющий маршрутизаторам совместно вычислять кратчайшие пути. Однако на практике он обладает серьезным недостатком: хотя правильный ответ в конце концов и находится, процесс его поиска может занять довольно много времени. В частности, такой алгоритм быстро реагирует на хорошие новости и очень лениво — на плохие. Рассмотрим маршрутизатор, для которого расстояние до маршрутизатораXдостаточно велико. Если при очередном обмене векторами его соседA сообщит ему, что от него до маршрутизатораX совсем недалеко, наш маршрутизатор просто переключится для передач маршрутизаторуX на линию, проходящую через этого соседа. Таким образом, хорошая новость распространилась всего за один обмен информацией.

Чтобы увидеть, как быстро распространяются хорошие известия, рассмотрим линейную сеть из пяти узлов, показанную на рис. 5.8, в которой мерой расстояния служит количество транзитных участков. Предположим, что вначале маршрутизаторA выключен, и все остальные маршрутизаторы об этом знают. То есть они считают, что расстояние доA равно бесконечности.

 

402 Глава 5. Сетевой уровень

Рис. 5.8. Проблема счета до бесконечности

Когда в сети появляется A, остальные маршрутизаторы узнают об этом с помощью обмена векторами. Для простоты будем предполагать, чтогде-тов сети имеется гигантский гонг, в который периодически ударяют, чтобы инициировать одновременный обмен векторами. После первого обменаB узнает, что у его соседа слева нулевая задержка при связи сA, аB помечает в своей таблице маршрутов, чтоA находится слева на расстоянии одного транзитного участка. Все остальные маршрутизаторы в этот момент еще полагают, чтоA выключен. Значения задержек дляA в таблицах на этот момент показаны во второй строке на рис. 5.8, а. При следующем обмене информациейC узнает, что уB есть путь кA длиной 1, поэтому он обновляет свою таблицу, указывая длину пути доA, равную 2, ноD иE об этом еще не знают. Таким образом, хорошие вести распространяются со скоростью один транзитный участок за один обмен векторами. Если самый длинный путь в сети состоит изN транзитных участков, то черезN обменов все маршрутизаторы подсети будут знать о включенных маршрутизаторах и заработавших линиях.

Теперь рассмотрим ситуацию на рис. 5.8, б, в которой все связи и маршрутизаторы изначально находятся во включенном состоянии. МаршрутизаторыB, C, D иE находятся на расстоянии 1, 2, 3 и 4 транзитных участков отA соответственно. Внезапно либоA отключается, либо происходит обрыв линии междуA иB (что с точки зренияB одно и то же).

При первом обмене пакетами B не слышит ответа отA. К счастью, C говорит: «Не волнуйся. У меня есть путь кA длиной 2».B вряд ли догадывается, что путь отC кAпроходит черезB.B может только предполагать, что уC около 10 выходных связей с независимыми путями кA, кратчайшая из которых имеет длину 2. Поэтому теперьBдумает, что может связаться сA черезC по пути длиной 3. При этом первом обмене маршрутизаторыD иE не обновляют свою информацию обA.

При втором обмене векторами C замечает, что у всех его соседей есть путь кAдлиной 3. Он выбирает один из них случайным образом и устанавливает свое расстояние доA равным 4, как показано в третьей строке на рис. 5.8, б. Результаты последующих обменов векторами также показаны на этом рисунке.

Теперь должно быть понятно, почему плохие новости медленно распространяются — ни один маршрутизатор не может установить значение расстояния, более чем на

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

Неудивительно, что эта проблема называется счетом до бесконечности ( count-to-infinity ). Было сделано много попыток решить ее, например можно запретить маршрутизатору сообщать о своих кратчайших путях соседям, от которых они получили эту информацию, с помощью правила расколотого горизонта с «отравляющим» ответом внесенного в RFC 1058. Однако на практике все эти эвристические правила с красивыми названиями оказались абсолютно бесполезными. Суть проблемы заключается в том, что когдаХ сообщаетY о том, что у него естькакой-топуть, уY нет никакой возможности узнать, входит ли он сам в этот путь.

Маршрутизация с учетом состояния линий

Маршрутизация на основе векторов расстояний использовалась в сети ARPANET вплоть до 1979 года, когда ее сменил алгоритм маршрутизации с учетом состояния линий. Отказаться от прежнего алгоритма пришлось в первую очередь потому, что при изменении топологии сети алгоритм слишком долго приходил к устойчивому состоянию (вследствие проблемы счета до бесконечности). В результате он был заменен на совершенно новый алгоритм, ныне называемый маршрутизацией с учетом состояния линий ( link state routing ). Сейчас в крупных сетях и сети Интернет используются его варианты — алгоритмы маршрутизацииIS-ISи OSPF.

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

1)обнаруживать своих соседей и узнавать их сетевые адреса;

2)задавать метрику расстояния или стоимости связи с каждым из своих соседей;

3)создавать пакет, содержащий всю собранную информацию;

4)посылать этот пакет всем маршрутизаторам и принять все пакеты, отправленные другими маршрутизаторами;

5)вычислять кратчайший путь ко всем маршрутизаторам.

Врезультате каждому маршрутизатору высылается полная топология. После этого для обнаружения кратчайшего пути ко всем остальным маршрутизаторам каждый маршрутизатор может использовать алгоритм Дейкстры. Ниже мы рассмотрим каждый из этих пяти этапов более подробно.

Знакомство с соседями

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

 

404 Глава 5. Сетевой уровень

что три маршрутизатора являются соседями маршрутизатора F, то не должно возникать разночтений по поводу того, один и тот же маршрутизаторF имеется в виду или нет.

Когда два или более маршрутизаторов соединены с помощью широковещательной связи (например, коммутатора, кольцевой сети или классической сети Ethernet), си- туация несколько усложняется. На рис. 5.9, аизображена широковещательная ЛВС, к которой напрямую подключены три маршрутизатора: A, C иF. Каждый из них, как показано на рисунке, соединен также с одним или несколькими дополнительными маршрутизаторами.

Рис. 5.9. Широковещательная ЛВС: а — девять маршрутизаторов и широковещательная локальная сеть; б — графовая модель той же системы

Широковещательная ЛВС обеспечивает связь между каждой парой подключенных маршрутизаторов. Однако моделирование такой сети в виде системы связей «точкаточка» существенно увеличивает размер топологии и приводит к нерациональной передаче сообщений. Более подходящий способ моделирования локальной сети состоит в том, что ЛВС рассматривается в виде узла графа, как и маршрутизаторы. Это показано на рис. 5.9, б. На рисунке сеть изображена в виде искусственного узлаN, с которым соединены маршрутизаторыA, C иF. Для исполнения ролиN в протоколе маршрутизации выбирается один из маршрутизаторов сети, который называется отмеченным маршрутизатором ( designated router ). Возможность передачи пакетов отA кC по локальной сети отражается здесь наличием путиANC.

Задание стоимости связи

Алгоритм маршрутизации с учетом состояния линии требует, чтобы каждая связь обладала метрикой расстояния или стоимости, необходимой для вычисления кратчайшего пути. Стоимость пути до соседних маршрутизаторов может быть задана автоматически или определена оператором сети. Чаще всего стоимость обратно пропорциональна пропускной способности связи. Так, сеть Ethernet со скоростью 1 Гбит/с

может иметь стоимость 1, а Ethernet со скоростью 100 Мбит/с — стоимость 10. Бла-

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

5.2. Алгоритмы маршрутизации 405

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

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: