tanenbaum_seti_all.pages (525408), страница 110
Текст из файла (страница 110)
Каждый узел помечается (в скобках) расстоянием до него от узла отправителя по наилучшему известному пути. Вначале пути неизвестны, поэтому все узлы помечаются символом бесконечности. По мере работы алгоритма и нахождения путей отметки узлов изменяются, показывая оптимальные пути. Отметка может быть постоянной или экспериментальной. Вначале все отметки являются ориен- Алгоритмы маршрутизации 411 тировочными. Когда выясняется, что отметка действительно соответствует кратчайшему возможному пути, она становится постоянной и в дальнейшем не изменяется. Чтобы показать, как работает этот алгоритм, рассмотрим взвешенный ненаправленный граф (рис.
5.6, а), где весовые коэффициенты соответствуют, например, расстояниям. Мы хотим найти кратчайший путь от А к )). Для начала мы черным кружком помечаем узел А как постоянный. Затем мы исследуем все соседние с ним узлы, указывая около них расстояние до узла А. Если отыскивается более короткий путь к какому-либо узлу, то вместе с указанием расстояния в отметке меняется и узел, через который прошел более короткий путь.
Таким образом, позднее можно восстановить весь путь. Рассмотрев все соседние с А узлы, мы помечаем ближайший узел как постоянный, как показано на рис. 5.6, б. Этот узел становится новым рабочим узлом. Теперь мы повторяем ту же процедуру с узлом В, исследуя все его соседние узлы. Если сумма расстояния от узла В и значения отметки в узле В (расстояния от А до В) оказывается меньше, чем отметка у исследуемого узла (уже найденное другим путем расстояние от А), это значит, что найден более короткий путь, поэтому пометка узла изменяется.
После того как все соседние с рабочим узлы исследованы и временные отметки при необходимости изменены, по всему графу ищется узел с наименьшей временной отметкой. Этот узел помечается как постоянный и становится текущим рабочим узлом. На рис. 5.6 показаны первые пять этапов работы алгоритма. Чтобы понять, как работает алгоритм, посмотрим на рис. 5.6, в. На данном этапе узел Е только что был отмечен как постоянный. Предположим, что существует более короткий путь, нежели АВЕ, например АХКИ В этом случае есть две возможности — либо узел 2 уже сделан постоянным, либо еше нет. Если да, значит, узел Е уже проверялся, когда узел 2 был сделан постоянным и, следовательно, рабочим узлом.
В этом случае путь АХУ2Е уже исследовался. Теперь рассмотрим случай, когда узел 2 все еще помечен как временный. В этом случае отметка узла 2 либо больше или равна пометки узла Е, либо меньше ее. В первом случае путь АХУ2Е не может быть короче, чем путь АВЕ. Если же отметка узла 2 меньше пометки узла Е, то тогда узел 2 должен был стать постоянным раньше узла Е, и узел Е проверялся бы с узла 2. Этот алгоритм приведен в листинге 5А. Глобальные переменные и и ЫЫ описывают граф и инициализируются раньше, чем вызывается йоггезг рагл. Единственное отличие программы от описанного выше алгоритма заключается в тоя, что вычисление кратчайшего пути в программе начинается не от узла-источника з, а от конечного узла г.
Поскольку в однонаправленном графе кратчайший путь от Г к з тот же самый, что и от з к Г, не имеет значения, с какого конца начинать. (Если только не существует несколько кратчайших путей. В таком случае, двигаясь в противоположном направлении, мы можем обнаружить другой путь.) Причина поиска пути в обратном направлении заключается в том, что каждый узел помечается предшествующим узлом, а не следующим. Когда найденный путь копируется в выходную переменную рата, он инвертируется.
С помошью реверсивного поиска убирается неправильность направления поиска, и мы получаем путь, идущий в нужную сторону. 412 Глава б. Сетевой уровень Листинг 5.1. Алгоритм Дейкстры вычисления кратчайшего пути по графу /)бет(пе МАХ ИООЕ5 1024 /* максимальное количество узлов */ /)бег(пе 1ие1и1тт 1000000000 /* число, большее длины максииальното пути */ !пт и, бтзь[МАХ ИООЕ53[МАХ ИООЕ53; /* бтзт[э][3] - зто расстояние от т до ) */ чо1б элогтезт рати(тпт з, 1пт С, 1пт рагл[]) ( звгцст агате ( /* рабочий путь */ 1пт ргебесеззог; /* предыдущий узел */ (пс 1епдсп: /* расстояние от источника до этого узла */ епцш (регшапепт.
секта(1че) 1аЬе1: /* метка состояния */ ) агате[МАХ ИООЕ53: тпт !. Х, штп; зггцст, агате [р; Гог (р - аэтате[03; р < азса1е[п]: р++) ( /* инициализировать состояние */ р->ргебесеввог - -1; р->)епд(П - 1ИЕ(И(ту, р->1аЬе1 Сепсаттче; зтасе[с].1епдсп - 0; агате[13.1аье1 - регщапепт; /* Х вЂ” начальный рабочий узел */ бо( /* Есть ли лучший путь от Х? */ тог (! 0; т < и; энч) /* у этого града п узлов */ 1г (б(зт[х][13 1- 0 аа агате[1],1аье1 — сепсат(че) ( 11 (агате[И].1епдГЬ + б1зт[Х][1] < з1ате[13.1епдгй) ( э(все[!],ргебесеззог - х, всаге[т].1епд(Ь агаве[И].1епдбб + сйзв[Х][13; ) /* Найти узел, помеченный кан предварительный с наииеньшей иеткой */ Х 0; ш1п !ИЕ1И!ТУ; тог (т - 0; 1 < и: 1<<) !т (агате[13.1абе) — Сапов((че йй зтасе[1].1епдСЬ < ш(п) ( ш!п - втаге[!3.1епдГЬ. втаге[Х],1аЬе) ° регшапепс; ) ыП11е (Х ( в); /и Копировать путь в выходной пассив */ О! Х 5! бо (раба[1++3 Х: Х - вовсе[д].ргебесеввог; ) ыл(1е (Х > О); ) Заливка Метод заливки представляет собой еще один статический алгоритм, при котором каждый приходящий пакет посылается на все исходящие линии, кроме той, по которой пришел пакет.
Очевидно, что алгоритм заливки порождает огромное количество дублированных пакетов, даже бесконечное количество в сетях с замкнутыми контурами, если не принять специальных мер. Одна из таких мер состоит в помещении в заголовок пакета счетчика преодоленных им транзитных участков, уменьшаемого при прохождении каждого маршрутизатора.
Когда значение этого счетчика падает до нуля, пакет удаляется. В идеальном случае счетчик транзит- Алгоритмы маршрутизации 413 ных участков должен вначале устанавливаться равным длине пути от отправите- ля до получателя. Если отправитель не знает расстояния до получателя, он может установить значение счетчика равным длине максимального пути (диаметру) в данной подсети, Альтернативный способ ограничения количества тиражируемых пакетов за- ключается в учете проходяших через маршрутизатор пакетов.
Это позволяет не посылать их повторно. Один из методов состоит в том, что каждый маршрутиза- тор помешает в каждый получаемый от своих хостов пакет порядковый номер. Все маршрутизаторы ведут список маршрутизаторов-источников, в котором со- храняются все порядковые номера пакетов, которые им встречались. Если пакет отданного источника с таким порядковым номером уже есть в списке, он дальше не распространяется н удаляется. Чтобы предотвратить неограниченный рост размера списка, можно снабдить все списки счетчиком я, показывающим, что все порядковые номера вплоть до я уже встречались. И когда приходит пакет, можно очень легко проверить, не яв- ляется ли он дубликатом. При положительном ответе такой пакет отвергается. Кроме того, не нужно хранить весь список до я, поскольку этот счетчик очень действенно подытоживает его. На практике чаше применяется вариант данного алгоритма под названием выборочная заливка.
В этом алгоритме маршрутизаторы посылают пакеты не по всем линиям, а только по тем, которые идут приблизительно в нужном направ- лении. Вряд ли есть смысл посылать пакет, направляющийся на запад, по линии, идущей на восток, если только топология сети не представляет собой лабиринт и маршрутизатор не знает об этом. В большинстве случаев алгоритм заливки является непрактичным, но, тем не менее, иногда он применяется. Например, в военных приложениях, где большая часть маршрутизаторов в любой момент может оказаться уничтоженной, высо- кая надежность алгоритма заливки является, наоборот, желательной. В распре- деленных базах данных иногда бывает необходимо одновременно обновить все базы данных, и в этом случае заливка также оказывается полезной.
Третье при- менение алгоритма заливки — эталонное тестирование других алгоритмов выбо- ра маршрутов, так как заливка всегда находит все возможные пути в сети, а сле- довательно, и кратчайшие. ухудшить эталонные показатели врегиени доставки могут разве что накладные расходы, вызванные огромным количеством пакетов, формируемых самим алгоритмом заливки. Маршрутизация по вектору расстояний Современные компьютерные сети обычно используют не статические, а динамические алгоритмы маршрутизации, поскольку статические просто не принимают во внимание текущую нагрузку на сеть.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
