Полный курс лекций 2009-го года (1130357), страница 60
Текст из файла (страница 60)
В таблице 5-9 показан итоговый трафик для некоторыхпар соседних вершин. Предполагается здесь, что трафик на каждой линии симметричен, т.е. трафик Х к Yидентичен трафику от Y к Х. В этой таблице также показаны среднее число пакетов в секунду (mC i), присредней длине пакета 1/ m = 800 бит. В последнем столбце указана средняя величина задержки,вычисленная по формулеИмея эти данные, нетрудно построить алгоритм вычисления наикратчайшего пути с точки зрениявесов на дугах графа. Если трафик изменится по какой-либо причине, то достаточно перевычислитьтаблицу, не меняя алгоритма.Таблица 5-9. Итоговый трафик для некоторых пар вершинil1 (пак./сек.)ЛинияС1(кбит/сек.)mС1(пак./сек.)T 1(мсек.)Величина задержки1 AB142025910,1712 BC122025770,1463 CD61012.51540,0734 AE112025710,1345 EF135062.5200,1596 FD81012.52220,0987 BF102025670,1228 EC82025590,0985.2.5.
Маршрутизация по вектору расстоянияВсе современные транспортные подсети используют динамическую маршрутизацию, а нестатическую. Один из наиболее популярных алгоритмов - маршрутизация по вектору расстояния. Этоталгоритм построен на идеях алгоритмов нахождения кратчайшего пути Беллмана-Форда и алгоритмаФорда-Фолкерсона, определяющего максимальный поток в графе. Он изначально использовался в сетиARPA и используется по сей день в протоколе RIP (Routing IP).
Оба эти алгоритма можно посмотреть в T.H.Cormen, C.E. Leiserson, R.L. Rivest Introduction to Algorithms. MIT Press, 1990. Он используется в сетяхNovell, AppleTalk, маршрутизаторах Cisco.Алгоритм маршрутизации по вектору расстояния устроен следующим образом: у каждогомаршрутизатора в транспортной подсети есть таблица расстояний до каждого маршрутизатора,принадлежащего подсети. Периодически маршрутизатор обменивается такой информацией со своимисоседями и обновляет информацию в своей таблице.
Каждый элемент таблицы состоит из двух полей:первое - номер канала, по которому надо отправлять пакеты, чтобы достичь нужного места, второе величина задержки до места назначения. Величина задержки может быть измерена в разных единицах:числе переходов, миллисекундах, длине очереди на канале и т.д. Фактически в протоколе использоваласьверсия алгоритма, где эту задержку определяли не на основе пропускной способности канала, а на основедлины очереди к каналу.Каждые Т секунд маршрутизатор шлет своим соседям свой вектор задержек до всех маршрутизаторовв подсети. В свою очередь, он получает такие же вектора от своих соседей. Кроме этого, он постояннозамеряет задержки до своих соседей.
Поэтому, имея вектора расстояний от соседей и зная расстояние доних, маршрутизатор всегда может вычислить кратчайший маршрут до определенного места в транспортнойсреде.Рассмотрим пример на рисунке 5-10. На рисунке 5-10 (а) показана подсеть. На рисунке 5-10 (b)показаны вектора, которые маршрутизатор J получил от своих соседей, и его замеры задержек до них.Там же показана итоговая таблица маршрутизации, которую J вычислит на основании этой информации.Рисунок 5-10.
Маршрутизация по вектору расстоянияРассмотрим, как маршрутизатор J с помощью этой таблицы вычислит маршрут до G. J знает, что онможет достичь А за 8 мсек., А объявляет, что от него до G 18 мсек. Таким образом, J может достичь G за 26мсек. через A. Аналогично можно подсчитать, что достичь G через I, H и K можно за 41 (31+10), 18 (6+12)и 37 (31+6) мсек. соответственно. Наилучшее значение – 18, поэтому это и есть наилучший маршрут.5.2.5.1. Проблема счетчика до бесконечностиАлгоритм маршрутизации по вектору расстояния теоретически работает хорошо, но у него есть одиннедостаток: он очень медленно реагирует на разрушения каналов в транспортной среде. Информация опоявлении хорошего маршрута в подсети распространяется более или менее быстро, а вот данные опотере, разрушении какого-то маршрута распространяются не столь быстро.Рассмотрим пример на рисунке 5-11 (а).
В нем показана линейная транспортная среда. Пустьизначально маршрутизатор А не работал. Поэтому у всех маршрутизаторов в подсети расстояние до негобыло равно ¥. Пусть в какой-то момент времени А был включен. По истечении определенного временимаршрутизаторы начнут обмениваться векторами, и В узнает об А. Еще через один обмен векторами об Аузнает С, и т.д. Таким образом, информация о новом маршруте будет распространяться линейно шаг зашагом, за каждый обмен векторами. Если самый длинный маршрут в подсети имеет длину N, топотребуется N обменов векторами, пока информация о новом маршруте дойдет до самого удаленного узлав подсети.Рисунок 5-11.
Проблема счетчика до бесконечностиТеперь рассмотрим обратную ситуацию на рисунке 5-11(b). Здесь изначально все маршрутизаторыи каналы были работоспособны. Пусть в какой-то момент времени канал между А и В оказался разрушен. Вперестает видеть А, но С говорит В: «Не беспокойся, у меня есть маршрут до А». При этом В неподозревает, что маршрут от С до А идет через него же.
Маршрутизаторы D и Е своих таблиц не меняют.Их расстояния до А на единицу больше, чем у С. На втором обмене С увидит, что оба его соседа достигаютА за 3 единицы. С выбирает одного некоторым случайным образом, увеличив значение 3 на единицу.Плохая весть будет распространяться медленно, пока счетчики задержек не примут значениябесконечности для данной сети.
Только после этого станет ясно, что А не достижим ни через С, ни через D,ни через Е. Сколько времени на это потребуется, зависит от конкретного значения бесконечности в даннойподсети.5.2.5.2. Разделение направлений (Split Horizon Hack)Одним из решений этой проблемы является следующий прием. Алгоритм работает так, как былоописано, но при передаче вектора по линии, по которой направляются пакеты для маршрутизатора Х, т.е.по которой достижим маршрутизатор Х, расстояние до Х указывается как бесконечность. Если теперьрассмотреть то, как будет работать подсеть на рисунке 5-11(b), то там проблем возникать не будет.Действительно, когда А «упадет», при первом же обмене В это обнаружит, но С также будет слать Ввектор, согласно которому А не достижимо (¥).
На следующем обмене С увидит, что А недостижим изобоих его соседей, и также отметит его как недостижимый узел.Однако и в алгоритме разделения направлений есть «дыры». Рассмотрим подсеть на рисунке 5-12.Если линия между С и D будет разрушена, то С сообщит об этом А и В. Однако А знает, что у В естьмаршрут до D, а В знает, что такой маршрут есть и у А.
И опять мы «сваливаемся» в проблемубесконечного счетчика.Рисунок 5-12. Случай, при котором разделение направлений не помогает5.2.6. Маршрутизация по состоянию каналаАлгоритм маршрутизации по вектору расстояний использовался в сети ARPANET до 1979 года, послечего он был заменен. Тому было две основных причины.
Первая - пропускная способность канала никак неучитывалась, поскольку основной мерой задержки была длина очереди. Пока основная масса каналовимела пропускную способность 56 Кбит/сек., это было не страшно. Однако, когда появились каналы на230 Кбит/сек. и 1,5 Мбит/сек., это стало недостатком. Вторая проблема – медленная сходимость алгоритмапри изменениях. По этим причинам был создан новый алгоритм маршрутизации по состоянию канала.Основная идея построения этого алгоритма проста и состоит из пяти основных шагов:1.Определить своих соседей и их сетевые адреса.2.Измерить задержку или оценить затраты на передачу до каждого соседа.3.Сформировать пакет, где указаны все данные, полученные на шаге 2.4.Послать этот пакет всем другим маршрутизаторам.5.Вычислить наикратчайший маршрут до каждого маршрутизатора.Топология и все задержки оцениваются экспериментально и сообщаются всем узлам. После этогоможно использовать, например, алгоритм Дейкстры для вычисления наикратчайшего маршрута.
Теперьрассмотрим подробнее эти пять шагов.5.2.6.1. Определение соседейПри загрузке маршрутизатор прежде всего определяет, кто его соседи. Для этого он рассылает повсем своим линиям точка-точка специальный пакет HELLO. В ответ все маршрутизаторы отвечают,указывая свое уникальное имя. Имя маршрутизатора должно быть уникальным в сети, чтобы избежатьнеоднозначностей. Если же два и более маршрутизатора соединены одним каналом, как на рисунке 5-13(а), то этот канал в графе связей представляют отдельным, искусственным узлом (рисунок 5-13 (b)).Рисунок 5-13. Определение соседей5.2.6.2.
Оценка затратОценка затрат до каждого соседа происходит с помощью другого специального пакета EСHO. Этопакет рассылается всем соседям, при этом замеряется задержка от момента отправки этого пакета домомента его возвращения. Все, кто получает такой пакет, обязаны отвечать незамедлительно. Такиезамеры делают несколько раз и вычисляют среднее значение. Таким образом, длина очереди к каналу неучитывается.Здесь есть одна тонкость: учитывать загрузку в канале или нет? Если учитывать, то задержку надозамерять от момента поступления пакета в очередь к каналу. Если не учитывать, то от момента, когдапакет достиг головы очереди. Есть доводы, как в пользу учета нагрузки, так и против такого учета.Учитывая нагрузку, мы можем выбирать между двумя и более каналами с одинаковой пропускнойспособностью, получая лучшую производительность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
