Галкин В.А., Григорьев Ю.А. - Телекоммуникации и сети (1053870), страница 93
Текст из файла (страница 93)
Dijkstra). АлгоритмSPF, основьшаясь на базе данных состояния связей, вьшисляет кратчайшиепути между заданной вершиной S-графа и всеми остальными вершинами. Результатом работы алгоритма является таблица, где для каждой вершиныV-графа указан список ребер, соединяющих заданную вершину S с вершинойV по кратчайшему пути.Введем следующие обозначения:Е - множество обработанных вершин, т. е.
вершин, кратчайший путь к которым от заданной вершины S уже найден;R — множество оставшихся вершин графа (т. е. множество вершин графа завычетом множества Е);О — упорядоченный список путей.Шаг 1. Инициализировать E={S}, К={все вершины графа, кроме S}.
Поместить в О все односегментные (длиной в одно ребро) пути, начинающиеся из S,отсортировав их в порядке возрастания метрик.Шаг 2. Если О пуст или первый путь в О имеет бесконечную метрику, тоотметить все вершины в R как недостижимые и закончить работу алгоритма.От392ДоR2СетьМетрика5.5. Протоколы III уровня стека TCP/IPШаг 3. Рассмотрим Р - кратчайший путь в списке О. Удалить Р из О.Пусть V - последний узел в Р. Если V е Е, перейти на шаг 2; иначе Р являетсякратчайшим путем из S в V (будем записывать как V:P); перенести V из R в Е.Шаг 4. Построить набор новых путей, подлежащих рассмотрению, путемдобавления к пути Р всех односегментных путей, начинающихся из V.
Метрика каждого нового пути равна сумме метрики Р и метрики соответствующегоодносегментного отрезка, начинающегося из V. Добавить новые пути в упорядочешп>1Й список О, поместив их на места в соответствии со значениями метрик. Перейти к шагу 2.Все вычисления вычисляются локально по известной базе данных, а потому значительно быстрее по сравнению с дисташщонно-векторными протоколами, при этом результаты получаются на основе полной, а не частичной информащш о графе системы сетей.Предположим, что к маршрутизатору /?4 подключена сеть N1 компьютеров(хостов) i/j - Я^. Следуя разобранной вьппе модели, каждый хост должен бытьтакже вершиной графа OSPF-системы, хотя сам и не строит базу данных и непроизводит вычисления маршрутов.
Тем не менее, информащм о связях маршрутизатора R4 с каждым из хостов сети N1 ио метриках этих связей должнабыть внесена в базу данных, чтобы все остальные маршрутизаторы системымогли построить маршруты от себя до этих хостов. Очевидно, что такая процедура неэффективна. Вместо информации о связях с каждым хостом в базуданных вносится информация о связи с сетью, т. е.
сама IP-сеть становитсявершиной графа системы, соединенной с маршрутизатором R4 некоторой связью Р (рис. 5.45).В данном случае сеть, точнее ее адрес, используется как обобщающийидентификатор группы хостов^ находящихся в одной IP-сети, к которой маршрутизатор R4 непосредственно подключен. Вершина Л^1 назьшается тупиковой сетью (stub network); все узлы сети, обозначаемые этой вершиной, являются хостами, у которых установлен маршрут по умолчанию, направленный намаршрутизатор R4.Рис. 5.45. Дополнею1е IP-сети в OSPF-систему3935. Сетевые протоколыПротокол OSPF проводит разграничение хостов и маршрутизаторов. Если к IP-сети Л^1 подРR4 N11ключен еще и один из интерфейсов маршрутизатора R2, то связь между R2 и R4 будетРис. 5.46. Запись в базе данных установлена отдельно, как если бы они былидля тупиковой сетисоединены двухточечной линией связи (приэтом у маршрутизатора R2 также будет связь с тупиковой сетью N1),При подключении тупиковой сети N1 в базе данных состояния связей появится запись (рис.
5.46).Связей, направленных из вершины N1, в базе данньпс нет и не будет, потомучто вершина Л^1 не является марпфутизатором. Построение маршрутов до вершины N1 (т. е. фактически сразу до всех хостов сети N1) будет осуществленокаждым маршрутизатором обычным способом по алгоритму SPF.Поддержка множественных маршрутов. Если между двумя узлами сетисуществует несколько маршрутов с одинаковыми или близкими по значениюметриками, протокол OSPF позволяет направлять части трафика по этим маршрутам в пропорщш, соответствующей значениям метрик. Например, если естьдва альтернативных маршрута с метриками 1 и 2, то две трети трафика будетнаправлено по первому из них, а оставшаяся треть - по второму. Положительный эффект такого механизма заключается в уменьшении средней задержкипрохождения дейтаграмм между отправителем и получателем, а также в уменьшении колебаний значения средней задержки.Менее очевидное преимущество поддержки множественных маршрутовсостоит в следующем.
Если при использовании только одного из возможныхмаршрутов этот маршрут внезапно выходит из строя, весь трафик будет разомперемаршрутизирован на альтернативный маршрут, при этом во время процесса массового переключения больших объемов трафика с одного маршрута надругой весьма велика вероятность образования затора на новом маршруте.Если же до аварии использовалось разделение трафика по нескольким маршрутам, отказ одного из них вызовет перемаршрутизащпо лишь части трафика,что существенно сгладит нежелательные эффекты.Рассмотрим следующий пример (рис.
5.47). Узел RI отправляет данные вузел /гЗ, используя поддержку множественных маршрутов, по маршрутам С (2/3 трафика) и АВ (1/3 трафика). Однако узел R2 тожеподдерживает механизм множественных путей, и когда к нему пребывают дейтаграммы,адресованные в R3 (в том числе, и отправленные из /?1), он применяет к ним ту же логику, т. е. 2/3 из них отправляет в R3 по маршруту 5 , а одну треть - по маршруту АС,Следовательно, 1/9 дейтаграмм, отправленньгсузлом RI в узел /?3, возвращаются опять в узелРис.
5.47. Частичное защпсливание /?1, который 1/3 из них опять отправляет в R3дейтаграммпо маршруту С, а 2/3 - по маршруту АВ через^ От394ДоСетьМетрика5.5. Протоколы III уровня стека TCP/IPузел J?2 И Т. Д. В итоге сформировался «частичный цикл» при посьшке дейтаграмм из i?l в i?3, который, помимо частичного зацикливания дейтаграмм, ведет к быстрой перегрузке линии ^.Избежать зацикливание дейтаграмм позволяет следующее правило:если узел X отправляет данные в узел Y, он может пересылать их черезузел Q только в том случае, если Q блилсе к Y, чем к X,В приведенном примере, следуя этому правилу, R\ не может посылать данные в КЪ через /f2, поскольку Kl не ближе к ЛЗ, чем /?1.
Однако такая посьшкавозможна, если связи между узлами имеют соответствующие метрики, нарис.5.47 эти значения приведены в скобках.Для реализации построения дополнительных альтернативных маршрутов сучетом вьппеприведенного правила в алгоритме ^PF необходимо внести изменения в шаг 3 и добавить шаг 3 а. Ниже приведена новая версия алгоритмаSPF, в которой изменение и дополнение показаны курсивом.Алгоритм SPF с поддержкой мноэюественных маршрутов.Шаг 1.
Инициализировать E={S}, К={все вершины графа, кроме S}. Поместить в О все односегментные (длиной в одно ребро) пути, начинающиеся извершины S, отсортировав их в порядке возрастания метрик.Шаг 2. Если О пуст или первый путь в О имеет бесконечную метрику, тоотметить все вершины в R как недостижимые и закончить работу алгоритма.Шаг 3. Рассмотрим Р - кратчайший путь в списке О. Удалить Р из О.Пусть V - последний узел в Р.
Если V принадлежит Е, перейти на шаг За;иначе Р является кратчайшим путем из S в V; перенести V из R в Е. Перейтина шаг 4,Шаг За. Рассмотрим W, узел, предшествующий V в пути Р. Если расстояние от S до W меньше расстояния от S до V, то обозначим Р как приемлемыйальтернативный путь к V. В любом случае перейти на шаг 2.Шаг 4. Построить набор новых путей, подлежащих рассмотрению, путемдобавления к пути Р всех односегментньпс путей, начинающихся из узла V.Метрика каждого нового пути равна сумме метрики Р и метрики соответствующего односегмешного отрезка, начинающегося из V. Добавить новые пути вупорядоченный список О, поместив их на места в соответствии со значениямиметрик.
Перейти на шаг 2.Накладывающиеся маршруты. Пусть в графе OSPF-системы некий маршрутизатор имеет связи с вершинами N и М, которые представляют сети хостов, подключенные к различным интерфейсам марпфутизатора. Это означает,что в таблице маршрутов этого маршрутизатора, будет две записи: для сети Nи для сети М.Предположим теперь, что адрес и маска сети М таковы, что она являетсяподсетью сети N. Например, IP-адрес сети N равен 172.16.0.0, а маска сети 255.255.0.0; для сети М -172.16.5.0 и 255.255.255.0 соответственно.3955.
Сетевые протоколыВ ЭТОМ случае дейтаграммы, следующие по адресу, находящемуся в обеихсетях, будут отправлены в сеть с более длинной маской. Например, адрес172.16.5.1 находится как в сети N, так и в сети М, но маска сети М длиннее,следовательно, дейтаграмма, следующая по этому адресу, будет отправлена всеть М.Внешние маршруты.
Для достижения сетей, не входящих в OSPF-систему (в автономную систему), используют пограничные маршрутизаторы автономной системы (ASBR - Autonomous System Border Router), имеющиесвязи, уходящие за пределы системы.ASBR вносят в базу данных состояния связей данные о сетях за пределамисистемы, достижимых через тот или иной маршрутизатор ASBR. Такие сети, атакже ведущие к ним маршруты назьшаются внешними (external).В простейшем случае, если в системе есть только OWXRASBR^ ОН объявляетчерез себя маршрут по умолчанию (default route) и все дейтаграммы, адресованные в сети, не входящие в базу данных системы, отправляются через этотмарпфутизатор. Если в системе несколько ASBR, то, возможно, внутренниммаршрутизаторам системы придется выбирать, через какой именно пограничный маршрутизатор нужно отправлять дейтаграммы в ту или иную внешнююсеть.
Это делается на основе спещ1альных записей, вносимых ASBR в базуданных системы. Такие записи содержат адрес и маску внешней сети и метрику расстояния до нее, которая может быть сравнимой с метриками, используемыми в OSPF-системе. Если возможно, адреса нескольких внешних сетейагрегируются в общий адрес с более короткой маской.Все или некоторые внешние маршруты могут быть сконфигурированы администратором (в том числе единственный маршрут по умолчанию) либо ASBRможет получать информащпо о внешних маршрутах от протоколов внешнеймарпфутизации.Построение базы данных состояния связей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
