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