Р.Л. Смелянский - Компьютерные сети. Том 2. Сети в ЭВМ, страница 9

Рассмотрим теперь статический алгоритм маршрутизаиии на основе потока, который учитывает как топологию транспортной среды, так и загрузку СПД. В некоторых сетях трафик между каждой парой узлов известен заранее и относительно стабилен. Например, при взаимодействии филиалов торгующей организации с головной организацией время подачи, размер и форма отчетов известны заранее. Лри этих условиях, зная про- Назначение А В С 2З Е Р А р 50 а б Рнс. 24. топология транспортной среды (а) в таблица графика (б) Зб Таблипа 2.! Итоговый график лля некоторых нар вершин пускную способность каналов, можно с помощью теории массового --.':, обслуживания вычислить среднюю задержку пакета в канале, после чего ' ';.. нетрудно построить алпэритм, вычисляющий путь пакета с минимальной :,.:.задержкой между двумя узлами. Для реализации этой идеи требуется заранее знать следующее; топологию транспортной среды; «матрицу трафика Г", ° матрицу пропускных способностей каналов С"; ° алгоритм маршрутизации.

На рис. 2.4, а приведен пример топологии транспортной среды с ' пропускной способностью каналов в килобитах в секунду, а на рис. :::.; 2.4, б — матрица гт, где для каждой пары узлов (г, у) указан средний размер графика в пакетах в секуиду и маршрут лля этого трафика. В табл. 2.1 приведен итоговый трафик для некоторых пар соседних вершин В табл. 2.1 предполагается, что трафик на каждой линии симметри- .

чен, т.е. график от Хк Уидентичен трафику от Ук Х Здесь также приве',,:. дены среднее число пакетов в секунду (оС;) при средней длине пакета 1/ 1г = 800 бит и среднее значение задержки, определяемое по формуле Т= 1 РС-).' где 2 — средняя скорость поступления кадров в секунду. Эта формула уже приводилась в подразд. 4.3.! т.

1 данного учебНика при построении модели канала с множественным доступом. Имея эти данные, нетрудно применить алгоритм вычисления наикратчайшего пути к размеченному таким образом графу. Если трафик изменится по какой-либо причине, то достаточно просто заново вычислить таблицу, не изменяя алгоритма. 37 2.2.6. Маршрутизация гуо вектору раоотояния Во всех современных транспортных средах используется динамическая маршрутизация, а не статическая. Один из наиболее популярных алгоритмов динамической маршрутизации — маршрутизация ло вектору расстояния. Этот алгоритм, построенный на идеях алгоритма Беллмана — Форда для нахождения наикратчайшего пути !231 и алгоритма Форда — Фолкерсона !451, определяюшего максимальный поток в графе, изначально использовался в сети АКРА и использует- Маршругизато Новая ожидаемая К А А В С В Е Р гг Р х х К Е Новая таблица маршру- тнзацннХ ХА ХХ ХИ ХК задержка задержка задержка задержка 8 1О !2 б Векторы, полученные от соседей Х Рис.

2.5. Пример маршрутизации по вектору расстояния: а — топология транспортной среды; б — векторы, которые маршрутизатор Х получил от своих соседей, его замеры задержек ло ннх н итоговая таблица маршрутизации, которую Х вычислит на основании атой инФормации 38 ся в настоящее время в протоколе К1Р (Копйпй!Р) [53[, а также в сетях )чоче11, Арр1еТа18 и маршрутизаторах С|асс. Алгоритм маршрутизации по вектору расстояния работает следующим образом: у каждого маршрутизатора в транспортной среде есть таблипа расстояний до всех других маршрутизаторов, приналлежащих этой транспортной среде. Периодически каждый маршрутизатор обменивается этой информацией со своими соседями и обновляет информапию в своей таблице.

Каждый элемент этой табли:;., цы включает в себя два поля; первое — номер канала, по которому следует отправлять пакеты, чтобы достичь нужного места, второе— значение задержки до места назначения, которое может измеряться ' .,в разных единицах: числе скачков, миллисекундах, длине очереди к ' ': '..каналу и т.д. Фактически в протоколе использовалась версия алгоритма, где эту задержку определяли не на основе пропускной способ.':,-,.' ности канала, а на основе длины очереди к каналу. Каждые Т секунд маршрутизатор шлет своим соседям свой вектор ".;" ., задержек до всех маршрутизаторов в транспортной среде. В свою "::;.-: очередь, он получает такие же векторы от своих соседей.

Кроме того, :.;.- он постоянно замеряет задержки до своих соседей, следовательно, имея векторы расстояний от соседей и зная расстояние до них, марш:;:::,рутизатор всегда может вычислить наикратчайший маршрут до . определенного места в транспортной среде На рис. 2.5 приведен пример маршрутизации по вектору расстояния [19) Рассмотрим, как маршрутизатор У с помощью итоговой таблицы маршрутизации вычислит маршрут до Ы Маршрутизатор У знает, что '- '-' он может достичь А за 8 мс, маршрутизатор А объявляет, что от него .-,'., '.:до О 18 мс.

Таким образом, У может достичь О за 26 мс через А. Аналогично можно подсчитать, что достичь б через 7, Н и К можно ':: .' „соответственно за 41 (31 ь 10), 18 (6 ь 12) и 37 (31 ь 6) мс. Наилучшее :;:: .полученное значение — 18, следовательно, этот маршрут и является Наилучшим по критерию скорости доставки Проблема бесконечного счетчика задержки Алгоритм маршрутизации по вектору расстояния теоретически работает хорошо, но у него есть один недостаток; он очень медлен.: но реагирует на разрушения каналов в транспортной среде, Инфор: мация о появлении хорошего маршрута в транспортной среде рас-;,' пространяется более или менее быстро, а вот данные о потере, разрушении какого-то маршрута распространяются значительно медленнее.

Рассмотрим пример транспортной среды с линейной топологией, ": показанный на рис. 2.6, а [19]. Пусть изначально маршрутизатор А . не работал, поэтому у всех маршрутизаторов расстояние до него было -" .Равно сс. Пусть в какой-то момент времени А включился. По истече- 39 А В С .0 Е с Исходное состояние с После 1-то обмена с После двух обменов с После трех обменов 4 После четырех обменов 1 с ! 2 ! 2 1 2 Е 4 Исходное состояние 4 После 1-го обмена 4 После двух обменов 4 После трех обменов 6 После четырех обменов 6 После пяти обменов 8 После шести обменов А В С 27 1 2 3 2 4 4 5 5 5 6 7 6 7 6 Рис.

2,6. Пример топологии транспортной среды с изначально нс работающим маршрутизатором А (а) и с полностью работоспособными марепрутизвторами и каналами (б) Разделение направлений (Зр!И Ног!хоп Наск) Одним из решений проблемы бесконечного счетчика задержки является следующее. Алгоритм маршрутизации по вектору расстояния 40 нии определенного времени маршрутизаторы начнут обмениваться векторами, и В узнает об А.

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

2.6, б, т.е. когда изначально все маршрутизаторы и каналы работоспособны. Пусть в какой-то момент времени канал между А и В оказался разрушен. В этом случае В перестает видеть А, но С говорит В: еУ меня есть маршрут до А». При этом В не подозревает, что маршрут от С до А идет через него же. Маршрутизаторы Р и Е своих таблиц не изменяют. Их расстояния до А на единицу больше, чем у С. При втором обмене С увидит, что оба его соседа достигают А за 3 единицы.

Некоторым случайным образом С выбирает одного соседа, увеличив значение 3 на единицу. Плохая весть будет распространяться медленно, пока счетчики задержек не примут некоторого очень большого значения, практически бесконечного для данной сети. Только после этого станет ясно, что А недостижим ни через С, ни через Р, ни через Е. Сколько времени на это потребуется зависит от конкретного значения бесконечности в данной транспортной среде. , Рис. 2.7. Пример, когда азгоритм разделения направлений не помогает: А ... Р— маршрутизаторы .-'., работает так, как было описано ранее, но при передаче вектора по ,: линии, по которой направляются пакеты для маршрутизатора Х, т.е.

:: по которой достижим маршрутизатор Х, расстояние до Хуказывает.': ся как бесконечность. Теперь у алгоритма маршрутизации по векто.:::.ру расстояния (см. рис. 2.6, б) проблемы бесконечного счетчика не '...возникнет. Действительно, когда маршрутизатор А «упадет», при :,': "'первом же обмене В это обнаружит, но С также будет посылать век.:, .тор В, согласно которому А недостижим (>з). При следующем обмене ;.;. С увидит, что А недостижим и через В, и через Р, и также отметит его как недостижимый узел Однако и в алгоритме разделения направлений есть «дыры». Рассмотрим пример, показанный на рис.

2.7. Если линия между С и Р :,;,-будет разрушена, то С сообщит об этом А и В. Однако А знает, что ..-' 'у В есть маршрут до Р, а В знает, что такой маршрут есть и у А. :.;,: ' И опять мы «сваливаемся> в проблему бесконечного счетчика. 2.2.7. Маршрутизация по состоянию канала Алгоритм маршрутизации по вектору расстояний использовался , -' в сети АКРАХЕТ до 1979 г., после чего он был заменен по двум основным причинам. Первая причина — это то, что в нем никак не учитывалась пропускная способность канала, поскольку задержка ':.'.

в основном определялась длиной очереди. Пока основная масса -;. каналов имела пропускну1о способность 56 Кбит/с, это было не .', страшно. Однако, когда появились каналы с пропускной способно:.: 'стью 256 Кбит)с и 1,5 Мбит/с, это стало недостатком. Вторая при' ', чина — это медленная сходимость алгоритма при изменениях в транспортной среде. По этим причинам был создан новый алгоритм " Маршрутизации по состоянию канала. Идею алгоритма маршрутизации по состоянию канала можно описать в виде пяти основных шагов, которые должен выполнить ." каждый маршрутизатор в транспортной среде: 41 1. Определить своих непосредственных соседей и их сетевые адреса.