Лекции 2010-го года (1130544), страница 60
Текст из файла (страница 60)
Хотя, например, в том случае,когда наикратчайший маршрут перегружен, очевидно, лучше воспользоваться пусть болеедлинным, но менее загруженным маршрутом. Здесь мы рассмотрим статический алгоритммаршрутизации на основе потока, который учитывает как топологию, так и загрузкутранспортной подсети.В некоторых сетях трафик между каждой парой узлов известен заранее и относительностабилен. Например, в случае взаимодействия сети торгующих организаций со складом.Время подачи отчетов, размер и форма отчетов известны заранее.
В этих условиях, знаяпропускную способность каналов, можно с помощью теории массового обслуживаниявычислить среднюю задержку пакета в канале. Тогда нетрудно построить алгоритм,вычисляющий путь с минимальной задержкой пакета между двумя узлами.Для реализации этой идеи нам нужно о каждой транспортной среде заранее знатьследующее:••••топологиюматрицу трафика Fijматрицу пропускных способностей каналов Cijалгоритм маршрутизацииРисунок 5-8. (а) Топология ТС с пропускной способностью в Кбит/сек.; (b) Матрица страфиком в пакетах/сек. и маршрутомНа рисунке 5-8 показан пример: (а) – топология транспортной среды с пропускнойспособностью каналов в Кбит/сек., (б) – матрица, где для каждой пары узлов (i, j) указансредний размер трафика в пакетах в секунду и маршрут для этого трафика.
В таблице 5-9показан итоговый трафик для некоторых пар соседних вершин. Предполагается здесь, что13трафик на каждой линии симметричен, т.е. трафик Х к Y идентичен трафику от Y к Х. Вэтой таблице также показаны среднее число пакетов в секунду (μCi), при средней длинепакета 1/μ=800 бит. В последнем столбце указана средняя величина задержки,вычисленная по формулеИмея эти данные, нетрудно построить алгоритм вычисления наикратчайшего пути с точкизрения весов на дугах графа. Если трафик изменится по какой-либо причине, тодостаточно перевычислить таблицу, не меняя алгоритма.Таблица 5-9.
Итоговый трафик для некоторых пар вершинiЛинияλ1 (пак./сек.)С1(кбит/сек.)μС1(пак./сек.)T1(мсек.)Величина задержки1AB142025910,1712BC122025770,1463CD61012.51540,0734AE112025710,1345EF135062.5200,1596FD81012.52220,0987BF102025670,1228EC82025590,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.Алгоритм маршрутизации по вектору расстояния устроен следующим образом: у каждогомаршрутизатора в транспортной подсети есть таблица расстояний до каждогомаршрутизатора, принадлежащего подсети. Периодически маршрутизатор обмениваетсятакой информацией со своими соседями и обновляет информацию в своей таблице.Каждый элемент таблицы состоит из двух полей: первое - номер канала, по которому надоотправлять пакеты, чтобы достичь нужного места, второе - величина задержки до местаназначения. Величина задержки может быть измерена в разных единицах: числепереходов, миллисекундах, длине очереди на канале и т.д.
Фактически в протоколеиспользовалась версия алгоритма, где эту задержку определяли не на основе пропускнойспособности канала, а на основе длины очереди к каналу.Каждые Т секунд маршрутизатор шлет своим соседям свой вектор задержек до всехмаршрутизаторов в подсети.
В свою очередь, он получает такие же вектора от своихсоседей. Кроме этого, он постоянно замеряет задержки до своих соседей. Поэтому, имеявектора расстояний от соседей и зная расстояние до них, маршрутизатор всегда можетвычислить кратчайший маршрут до определенного места в транспортной среде.14Рассмотрим пример на рисунке 5-10. На рисунке 5-10 (а) показана подсеть. На рисунке 510 (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. Проблема счетчика до бесконечности15Теперь рассмотрим обратную ситуацию на рисунке 5-11(b).
Здесь изначально всемаршрутизаторы и каналы были работоспособны. Пусть в какой-то момент времени каналмежду А и В оказался разрушен. В перестает видеть А, но С говорит В: «Не беспокойся, уменя есть маршрут до А». При этом В не подозревает, что маршрут от С до А идет черезнего же. Маршрутизаторы D и Е своих таблиц не меняют. Их расстояния до А на единицубольше, чем у С.
На втором обмене С увидит, что оба его соседа достигают А за 3единицы. С выбирает одного некоторым случайным образом, увеличив значение 3 наединицу. Плохая весть будет распространяться медленно, пока счетчики задержек непримут значения бесконечности для данной сети. Только после этого станет ясно, что Ане достижим ни через С, ни через D, ни через Е. Сколько времени на это потребуется,зависит от конкретного значения бесконечности в данной подсети.5.2.5.2.
Разделение направлений (Split Horizon Hack)Одним из решений этой проблемы является следующий прием. Алгоритм работает так,как было описано, но при передаче вектора по линии, по которой направляются пакетыдля маршрутизатора Х, т.е. по которой достижим маршрутизатор Х, расстояние до Хуказывается как бесконечность.
Если теперь рассмотреть то, как будет работать подсетьна рисунке 5-11(b), то там проблем возникать не будет. Действительно, когда А «упадет»,при первом же обмене В это обнаружит, но С также будет слать В вектор, согласнокоторому А не достижимо (∞). На следующем обмене С увидит, что А недостижим изобоих его соседей, и также отметит его как недостижимый узел.Однако и в алгоритме разделения направлений есть «дыры».
Рассмотрим подсеть нарисунке 5-12. Если линия между С и D будет разрушена, то С сообщит об этом А и В.Однако А знает, что у В есть маршрут до D, а В знает, что такой маршрут есть и у А. Иопять мы «сваливаемся» в проблему бесконечного счетчика.Рисунок 5-12. Случай, при котором разделение направлений не помогает165.2.6. Маршрутизация по состоянию каналаАлгоритм маршрутизации по вектору расстояний использовался в сети ARPANET до 1979года, после чего он был заменен. Тому было две основных причины. Первая - пропускнаяспособность канала никак не учитывалась, поскольку основной мерой задержки быладлина очереди. Пока основная масса каналов имела пропускную способность 56 Кбит/сек.,это было не страшно.
Однако, когда появились каналы на 230 Кбит/сек. и 1,5 Мбит/сек.,это стало недостатком. Вторая проблема – медленная сходимость алгоритма приизменениях. По этим причинам был создан новый алгоритм маршрутизации по состояниюканала.Основная идея построения этого алгоритма проста и состоит из пяти основных шагов:1.Определить своих соседей и их сетевые адреса.2.Измерить задержку или оценить затраты на передачу до каждого соседа.3.Сформировать пакет, где указаны все данные, полученные на шаге 2.4.Послать этот пакет всем другим маршрутизаторам.5.Вычислить наикратчайший маршрут до каждого маршрутизатора.Топология и все задержки оцениваются экспериментально и сообщаются всем узлам.После этого можно использовать, например, алгоритм Дейкстры для вычислениянаикратчайшего маршрута. Теперь рассмотрим подробнее эти пять шагов.5.2.6.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
