7.2 Принцип оптимальности
Прежде чем перейти к рассмотрению отдельных алгоритмов, возможно, следует привести некое общее соображение об оптимальных маршрутах, вне зависимости от топологии или трафика, известное как принцип оптимальности. В соответствии с этим принципом, если маршрутизатор В располагается на оптимальном маршруте от маршрутизатора А к маршрутизатору С, тогда оптимальный маршрут от маршрутизатора В к маршрутизатору С совпадает с частью первого маршрута. Чтобы убедиться в этом, назовем часть маршрута от маршрутизатора А к маршрутизатору В r1, а остальную часть маршрута – r2. Если бы существовал лучший маршрут от В к С, чем r2, то его можно было объединить с r1, чтобы улучшить маршрут от маршрутизатора А к маршрутизатору С, что противоречит первоначальному утверждению о том, что маршрут r1r2 является оптимальным.
На рисунке 64 изображена сеть. Прямым следствием принципа оптимальности является возможность рассматривать множество оптимальных маршрутов от всех источников к данным приемникам в виде дерева, в корне которого располагается приемник. Такое дерево называется входным деревом. Такое дерево изображено на рисунке 65. Расстояния измеряются количеством транзитных участков. Причем, входное дерево не обязательно является уникальным. У одной сети может существовать несколько входных деревьев с одинаковыми длинами путей. Цель всех алгоритмов выбора маршрутов заключается в вычислении и использовании входных деревьев для всех маршрутизаторов.
Поскольку входное дерево действительно является деревом, оно не содержит петель, поэтому каждый пакет будет доставлен за конечное и ограниченное число пересылок. На практике все это не так просто. Линии связи и маршрутизаторы могут выходить из строя и снова появляться в сети во время выполнения операции, поэтому у разных маршрутизаторов могут оказаться различные представления о текущей топологии сети. Принцип оптимальности и входное дерево составляет точку отсчета, относительно которой можно измерять эффективность различных алгоритмов выбора маршрутов.
Рисунок 64 - Данная подсеть
7.3 Выбор кратчайшего пути
Первым рассмотрим алгоритм выбора маршрута с метода, широко применяемого в различных формах благодаря его простоте и понятности. Идея заключается в построении графа подсети, в котором каждый узел будет соответствовать маршрутизатору, а каждая дуга – линии связи (часто называют связью). При выборе маршрута между двумя маршрутизаторами алгоритм просто находит кротчайший путь между ними на графе. Один из способов измерения длины пути состоит в подсчете количества транзитных участков. В таком случае пути АВС и АВЕ на рисунке 64 имеют одинаковую длину . Можно измерять
Рисунок 65 - Входное дерево для маршрутизатора В
расстояние в километрах. В таком случае окажется, что путь АВС значительно длиннее пути АВЕ.
Однако помимо учета количества транзитных участков и физической длины линий, возможен учет и других параметров. Например, каждой дуге графа можно поставить в соответствие среднюю длину очереди и время задержки пересылки, определяемые каждый час с помощью передачи специально тестового пакета. В таком графе кратчайший путь определяется как самый быстрый путь, а не путь с самой короткой длиной кабеля или путь, состоящий из минимального числа отдельных отрезков кабеля.
В наиболее общем случае параметры дуг графа являются функциями расстояния, пропускной способности, средней загруженности, стоимости связи средней длины очереди, измеренной величины задержки и других факторов. Изменяя весовую функцию, алгоритм может вычислять кратчайший путь с учетом любого количество критериев в различных комбинациях.
Рассмотрим алгоритм вычисления кратчайшего пути от А к D, изображенный на рисунке 66, где стрелка указывает на рабочий узел.
Каждый узел помечается (в скобках) расстоянием до него от узла отправителя по лучшему известному пути. Вначале пути неизвестны, поэтому все узлы помечаются символом бесконечности. По мере работы алгоритма и нахождения путей отметки узлов изменяются, отражая лучшие пути.
Отметка может быть постоянной или экспериментальной. Вначале все отметки являются ориентированными. Когда выясняется, что отметка соответствует кратчайшему возможному пути, она становится постоянной и в дальнейшем не изменяется.
Рассмотрим взвешенный ненаправленный граф, где весовые коэффициенты соответствуют, например, расстояниям. Мы хотим найти кратчайший путь от А к D. Для начала мы заштрихованным кружком помечаем узел А как постоянный.
Рисунок 66 Взвешенный ненаправленный граф
Затем мы исследуем все соседние узлы с ним, указывая около них расстояние до узла А. Если отыскивается более короткий путь к какому–либо узлу, то вместе с указанием расстояния в отметке меняется и узел, через который прошел более короткий путь. Т.е., позднее можно восстановить весь путь. Рассмотрев все соседние с А узлы, мы помечаем ближайший узел как постоянный, как изображено на рисунке 67, этот узел становится рабочим узлом.
Далее мы повторяем ту же процедуру с узлом В, исследуя все его соседние узлы (рисунки 68,69,70,71). Если сумма расстояния от узла В и значения отметки в узле В (расстояния от А до В) оказывается меньше, чем отметка у исследуемого узла (уже найденное другим путем расстояние от А), это значит, что найден более короткий путь, поэтому пометка узла изменяется.
Рисунок 67 - Вычисление кратчайшего пути от узла А.
Рисунок 68 - Вычисление кратчайшего пути для узла Е
Рисунок 69 - Выбор кратчайшего пути от узла Е
Рисунок 70 - Выбор кратчайшего пути. Стрелка указывает рабочий узел
Рисунок 71 - Выбор кратчайшего пути. Стрелка указывает рабочий узел.