Поддержка множественных маршрутов
Если между двумя узлами сети существует несколько маршрутов с одинаковыми или близкими по значению метриками, протокол OSPF позволяет направлять части трафика по этим маршрутам в пропорции, соответствующей значениям метрик. Например, если существует два альтернативных маршрута с метриками 1 и 2, то две трети трафика будет направлено по первому из них, а оставшаяся треть- по второму.
Положительный эффект такого механизма заключается в уменьшении средней задержки прохождения дейтаграмм между отправителем и получателем, а также в уменьшении колебаний значения средней задержки.
Менее очевидное преимущество поддержки множественных маршрутов состоит в следующем. Если при использовании только одного из возможных маршрутов этот маршрут внезапно выходит из строя, весь трафик будет разом перемаршрутизирован на альтернативный маршрут, при этом во время процесса массового переключения больших объемов трафика с одного маршрута на другой весьма велика вероятность образования затора на новом маршруте. Если же до аварии использовалось разделение трафика по нескольким маршрутам, отказ одного из них вызовет перемаршрутизацию лишь части трафика, что существенно сгладит нежелательные эффекты.
Рассмотрим теперь следующий пример.
Рис. 5.1.5. Пример особой ситуации при поддержке множественных маршрутов
Узел ?
отправляет данные в ?
, используя поддержку множественных маршрутов, по маршрутам С (2/3 трафика) и АВ (1/3 трафика). Однако узел ?
тоже поддерживает механизм множественных путей, и когда к нему пребывают дейтаграммы, адресованные в ?
(в том числе, и отправленные из ?
), он применяет к ним ту же логику, то есть 2/3 из них отправляются в ?
по маршруту В, а одна треть - по маршруту АС. Следовательно, 1/9 дейтаграмм, отправленных узлом ?
в узел ?
, возвращаются опять в узел ?
, и тот 1/3 из них опять отправляет в ?
по маршруту С, а 2/3 - по маршруту АВ через узел ?
и так далее. В итоге сформировался "частичный цикл" при посылке дейтаграмм из ?
в ?
, который, помимо частичного зацикливания дейтаграмм, ведет к быстрой перегрузке линии А.
Избежать этого явления позволяет следующее правило.
Если узел Х отправляет данные в узел Y, он может пересылать их через узел Q только в том случае, если Q ближе к Y, чем Х.
В разобранном выше примере, следуя этому правилу, ?
не может посылать данные в ?
через ?
, поскольку ?
не ближе к ?
, чем ?
. Однако такая посылка возможна, если связи между узлами имеют метрики, например, как изображено на следующем рисунке.
Рис. 5.1.6. Пример корректной ситуации при поддержке множественных маршрутов
Для реализации построения дополнительных альтернативных маршрутов с учетом вышеприведенного правила в алгоритме SPF требуется внести изменения в шаг 3 и добавить шаг 3А. Ниже приводится новая версия алгоритма SPF, в которой изменение и дополнение показаны курсивом.
Алгоритм SPF с поддержкой множественных маршрутов
1. Инициализировать E={S}, R={все вершины графа, кроме S}. Поместить в О все односегментные (длиной в одно ребро) пути, начинающиеся из S, отсортировав их в порядке возрастания метрик.
2. Если О пуст или первый путь в О имеет бесконечную метрику, то отметить все вершины в R как недостижимые и закончить работу алгоритма.
3. Рассмотрим P - кратчайший путь в списке О. Удалить P из О. Пусть V - последний узел в P.
Если V принадлежит E, перейти на шаг 3А;
иначе P является кратчайшим путем из S в V; перенести V из R в E. Перейти на шаг 4.
3А. Рассмотрим W, узел, предшествующий V в пути Р. Если расстояние от S до W меньше расстояния от S до V, обозначить Р как приемлемый альтернативный путь к V. В любом случае перейти на шаг 2.
4. Построить набор новых путей, подлежащих рассмотрению, путем добавления к пути P всех односегментных путей, начинающихся из V. Метрика каждого нового пути равна сумме метрики P и метрики соответствующего односегментного отрезка, начинающегося из V. Добавить новые пути в упорядоченный список О, поместив их на места в соответствии со значениями метрик. Перейти на шаг 2.
