Разработка системы автоматизированного расчёта оптимальных потоков в сетях передачи данных

Возможно существование сразу нескольких МОД, это обозначение не отражает достаточно четко тот факт, что мы минимизируем вес, а не само дерево. Наиболее подходящее прилагательное для описания свойства такого дерева есть минимальное (т.е., дерево, имеющее минимальный вес). Если ребра различны, минимальным ребром является самое короткое ребро, такое ребро будет единственным; но если существует несколько ребер минимального веса, любое из них может быть минимальным.

В данном подразделе будут рассматриваться исключительно неориентированные графы. Задача поиска на орграфе ориентированного остового дерева с минимальным весом не принадлежит к этому классу, к тому же она намного труднее.

Для решения задачи МОД были разработаны несколько классических алгоритмов. Классические методы предлагают общий подход, в то же время современные алгоритмы и структуры данных позволяют получать компактные и эффективные программные реализации этих алгоритмов. В самом деле, такие реализации представляют собой убедительные примеры эффективности тщательного проектирования АТД (абстрактный тип данных) и правил выбора фундаментальных структур данных АТД и реализаций алгоритмов при решении алгоритмических задач, сложность которых неуклонно растет.

Рисунок 3.3 - Пример минимального остовного дерева

Основные подходы к решению задачи нахождения МОД были получены задолго до разработки современных структур данных и современных технологий изучения рабочих характеристик алгоритмов, еще в те времена, когда определение дерева МОД, конкретного графа, содержавшего, скажем, тысячи ребер, представляло собой невыполнимую задачу. Некоторые новые алгоритмы определения MST отличаются от старых, главным образом, способами использования и реализации современных алгоритмов и структур данных для базовых задач, которые (в совокупности с мощью современных компьютеров) дают возможность вычислять деревья МОД, состоящие из миллионов и даже миллиардов ребер.

Одно из определяющих свойств дерева заключается в том, что добавление ребра в дерево порождает уникальный цикл. Это свойство является определяющим для доказательства двух фундаментальных свойств деревьев МОД. Все алгоритмы, с которыми приходится работать, основаны на одном или обоих этих свойствах.

Первое из этих свойств, которое называется свойство сечения, относится к идентификации ребер, которые должны входить в дерево МОД заданного графа. Несколько основных терминов из теории графов, определение которых даны ниже, позволяют получить нижеследующую компактную формулировку этого свойства.

Определение 3.3.2 Сечение графа есть разделение множества всех вершин графа на два непересекающихся множества. Пересекающее ребро есть ребро, которое соединяет вершину одного множества с вершиной другого множества.

Иногда сечение графа описывается путем описания некоторого множества вершин графа, подразумевая при этом, что сечение содержит само это множество и его дополнение. Обычно используются сечения, в которых оба указанных выше множества не пусты - в противном случае, например, пересекающие ребра отсутствуют.

Свойство 3.3.1 (Свойство сечения). При любом сечении графа каждое минимальное пересекающее ребро принадлежит некоторому дереву МОД графа, и каждое дерево МОД содержит минимальное пересекающее ребро.

Доказательство. Проведем доказательство от противного. Предположим, что е ? минимальное пересекающее ребро, которое не содержится ни в одном МОД, и пусть Т есть некоторое дерево МОД, которое не содержит минимального пересекающего ребра е. В любом случае Т есть МОД, которое не содержит минимального пресекающего ребра е. Теперь рассмотрим граф, полученный после добавления ребра е в Т. В этом графе имеется цикл, который содержит ребро е, и этот цикл должен, по меньшей мере, содержать еще одно пересекающее ребро, скажем, f, которое имеет вес, равный или больший веса е (поскольку е имеет минимальный вес. Можно получить остовное дерево равного или меньшего веса, если удалить f и добавить е, что противоречит условию минимальности Т или предположению, что е не содержится в Т.

Если все веса ребер графа различны, он обладает единственным деревом МОД; свойство сечения свидетельствует о том, что кратчайшее пересекающее дерево для каждого сечения должно быть внутри дерева MST. Если имеют место равные веса ребер, можно получить несколько минимальных пересекающих ребер. По меньшей мере, одно из них входит в состав любого заданного дерева МОД, в то время как другие могут в нем быть, а могут и не быть.

На рисунке 3.4 представлены несколько примеров рассмотренного свойства сечения. В рассматриваемом случае отсутствует требование того, что минимальное ребро должно быть единственным ребром МОД, которое соединяет два эти множества; в самом деле, для обычных сечений существует несколько ребер, соединяющих вершину одного множества с вершиной другого. Мы используем свойство сечения в качестве основы для алгоритмов поиска деревьев МОД, оно может также служить условием оптимальности, которое характерно для деревьев МОД. В частности, из выполнения условия оптимальности следует, что каждое ребро дерева МОД есть минимальное ребро, пересекающее сечение, определенное вершинами двух поддеревьев, соединенных этим ребром.

Второе свойство, которое называется свойством цикличности, применяется с целью выявления ребер, которые не должны входить в дерево МОД графа. Другими словами, если мы игнорируем эти ребра, то, тем не менее, не теряем возможности отыскать дерево МОД.

Свойство 3.3.2. (Свойство цикличности). Пусть задан граф G, рассмотрим граф G', который получается в результате добавления к графу G ребра е. Добавление ребра е в дерево МОД графа G и удаление максимального ребра из полученного в результате этой операции цикла дает дерево МОД графа G'.

Доказательство. Если ребро е длиннее всех других ребер цикла, то, в соответствие со свойством 3.3.1, оно не должно содержаться в дереве МОД графа G': удаление е из любого такого дерева МОД разделит последнее на две части, а е не будет самым коротким ребром, соединяющим вершины каддой из полученных двух частей, поскольку это должно делать какое-то другое ребро цикла. И наоборот, пусть t есть максимальное ребро цикла, построенного в результате добавления ребра e в дерево МОД графа G. Удаление ребра t приводит к разбиению исходного дерева МОД на две части, а ребра графа G, соединяющие эти две части, не короче t; следовательно, е является минимальным ребром G', которое соединяет вершины этих двух частей. Подграфы индуцированные этими двумя подмножествами вершин, идентичны G и G', таким образом, дерево МОД для G' состоит из ребра е и из деревьев МОД этих двух подмножеств.

Рисунок 3.4

Свойство цикличности служит также основой условия оптимальности, которое характерно для деревьев МОД: из него следует, что каждое ребро любого графа, содержащегося в заданном МОД, есть максимальное ребро цикла, который оно образует с ребрами МОД.

Свойства сечения и цикличности образуют основу для классических алгоритмов, которые будут исследоваться применительно к задаче определения дерева МОД. Ребра рассматриваются по одному за раз, используя сечения с целью проверки их пригодности для пользования в качестве ребер дерева МОД, или свойство цикличности с целью определения возможности их отбрасывания по причине ненадобности. Эти алгоритмы различаются по их способности эффективно идентифицировать сечения и циклы.

Первый подход к поиску дерева МОД, который будет рассмотрен во всех подробностях, заключается в постепенном построении МОД, добавляя одно ребро за раз: построение начинается с произвольной вершины, которую рассматриваем как дерево МОД, состоящее из одной вершины, затем добавляем к нему V ? 1 вершин, при этом каждый раз выбираем минимальное ребро, которое соединяет вершину, уже включенную в дерево МОД, с вершиной, которая еще не содержится в МОД. Этот метод известен как алгоритм Прима.

Еще один подход к вычислению дерева МОД предусматривает многократное применение свойства цикличности: ребра добавляются по одному за раз в мнимое дерево МОД, с удалением максимального ребра из цикла, если таковой был. Этому методу уделяется меньше внимание, чем другим алгоритмам, в силу трудностей, связанных с поддержкой структуры данных, которые обеспечивают реализацию операции "удалить самое длинное ребро цикла".

Второй подход отыскания дерева МОД, предусматривает обработку ребер в порядке возрастания их длины (первым обрабатывается наиболее короткое) с добавлением в МОД каждого ребра, которое не образует цикла с ребрами, включенными в МОД ранее; при этом процесс останавливается после того, как будут добавлены V ? 1 ребер. Этот метод известен как алгоритм Крускала.

Третий подход к построению дерева МОД, известен как алгоритм Борувки. На первом шаге в дерево МОД добавляются ребра, которые соединяют каждую вершину с её ближайшим соседом. Если веса ребер различны, этот шаг порождает лес из поддеревьев дерева МОД. Затем мы добавляем в дерево МОД ребра, которые соединяют каждую вершину с её ближайшим соседом, и повторяем этот процесс до тех пор, пока у нас не останется только одно единственное дерево.

3.4 Алгоритм Прима построения минимального остовного дерева

С точки зрения реализации алгоритм Прима, по-видимому, является простейшим из всех алгоритмов построения дерева МОД, ему отдают предпочтение в случае насыщенных графов. Сечение графа состоит из древесных вершин (те, которые выбраны для представления дерева МОД) и недревесных вершин (те, которые не попадают в дерево МОД). Начинаем с того, что помещаем произвольную вершину в дерево МОД, затем помещаем в МОД минимальное пересекающее ребро (которое превращает недревесную вершину дерева МОД в древесную) и повторяем подобную операцию V ? 1 раз, пока все вершины не окажутся в дереве.

Реализация алгоритма Прима "в лоб" следует непосредственно из этого описания. Чтобы найти очередное ребро для включения его в дерево МОД, нужно исследовать все ребра, которые выходят из древесной вершины в недревесную вершину, затем выбрать из них самое короткое и поместить его в дерево МОД. Применение простых структур данных, позволяющих устранить повторные вычисления, приводят к упрощению алгоритма и повышению его быстродействия.

На рисунке 3.5 приведен пример нахождения МОД при помощи алгоритма Прима. Первое действие при вычислении дерева МОД по алгоритму Прима предусматривает включение в это дерево вершины 0. Затем нужно найти все ребра, которые соединяют 0 с другими вершинами (еще не включенные в это дерево), и выбрать из них самое короткое (слева вверху на рисунке 3.5) Ребра, соединяющие древесные вершины с недревесными, изображены сером цветом, их список приводится под каждым чертежом графа. Чтобы не усложнять чертеж, ребра, образующие бахрому, перечислены в порядке возрастания их длины, так что самое короткое ребро в этом списке следует первым. В различных реализациях алгоритма Прима используются различные структуры данных для поддержания этого списка и определения минимального ребра. Второе действие заключается в переносе самого короткого ребра 0-2 (вместе с вершиной, в которую оно нас приводит) из бахромы в дерево (вторая диаграмма сверху слева рисунка 3.5).

Рисунок 3.5 - Алгоритм Прима построения минимального остовного дерева

В-третьих, ребро 0-7 переносится из бахромы в дерево и заменяется ребро 0-1 на 7-1, а ребро 0-6 на 7-6 в бахроме (поскольку с включением вершины 7 в дерево 1 и 6 становятся ближе к дереву), и включается ребро 7-4 в бахрому (поскольку добавление вершины 7 в дерево превращает 7-4 в ребро, которое соединяет древесную вершину с недревесной) (третья диаграмма сверху слева рисунка 3.5). Далее, ребро 7-1 переносится в дерево (диаграмма слева внизу рисунка 3.5). В завершение вычислений ребра 7-6, 7-4, 4-3 и 3-5 исключаются из очереди и обновляется бахрома после каждой вставки с тем, чтобы зафиксировать обнаруженные более короткие или новые пути (диаграммы справа сверху вниз рисунка 3.5). Ориентированный чертеж возрастающего дерева МОД показан справа от каждого чертежа графа. Ориентация побочный продукт изучаемого алгоритма: в общем случае само дерево рассматривается как множество ребер, неупорядоченное и неориентированное.

3.5 Кратчайшие пути

Каждому пути во взвешенном орграфе можно поставить в соответствие вес пути, т.е. сумму весов ребер, составляющих этот путь. Эта важная характеристика сразу же приводит к задачам типа "найти путь между двумя заданными вершинами, имеющий минимальный вес". Эта задача и большое количество аналогичных ей известны под общим названием задач о кратчайших путях. Задачи о кратчайших путях не только интуитивно вытекают из многих проблемно-ориентированных приложений, но и вводят нас в мощную и широкую область, в которой изучают эффективные алгоритмы решения задач в общем виде, которые применимы к широкому кругу конкретных приложений.

Для краткости взвешенные орграфы называются сетями. На рисунке 3.6 показан пример сети.

Определение 3.5.1 Кратчайшим путем между двумя вершинами s и t в сети называется такой направленный простой путь из s в t, что никакой другой путь не имеет более низкого веса.

Существует несколько типов задач нахождения кратчайших путей:

1) Кратчайший путь из источника в сток. Для заданной начальной вершины s и конечной вершины t найти кратчайший путь в графе из s в t. Начальная вершина называется источник, а конечная - сток.

2) Кратчайшие пути из одного источника. Для заданной начальной вершины s найти кратчайшие пути из s во все остальные вершины графа.

3) Кратчайшие пути между всеми парами вершин. Найти кратчайшие пути, соединяющие каждую пару вершин в графе. Для краткости при ссылке на это множество из V² путей иногда используют термин все кратчайшие пути.

В общем случае может быть несколько кратчайших путей, соединяющих любую заданную пару вершин, и достаточно найти один из них. Когда говорят "найти кратчайший путь", имеют в виду "вычислить длину кратчайшего пути и способ прохода заданного пути за время, пропорциональное его длине".

В сетях с V вершинами решение задачи с одним источником задается V ? 1 путем, а для решения задачи кратчайших путей для всех пар вершин потребуется определить V(V? 1) путей.

Примером использования алгоритма нахождения кратчайших путей может служить составление маршрутов авиалиний. Карты маршрутов и расписания для авиалиний или других транспортных систем представляют собой сети, для которых различные задачи о кратчайших путях имеют первостепенное значение. Например, может потребоваться минимизировать время, которое займет перелет между двумя городами, или стоимость путешествия. Стоимости, или расходы, в таких сетях могут быть функциями времени или каких-либо других ресурсов, более сложных, чем расстояния. Например, перелеты между двумя городами обычно занимают больше времени в одном направлении, нежели в другом, по причине преобладающих ветров. Авиапассажиры также знают, что стоимость перелета не обязательно является простой функцией расстояния между городами - ситуации, когда использование окольного маршрута (или путешествие с пересадками) дешевле прямого перелета, встречаются довольно часто. Такие усложненные модели могут быть обработаны базовыми алгоритмами поиска кратчайших путей, при условии, что все положительны.

Рисунок 3.6 - Пример сети

В сетях передачи данных алгоритмы нахождения кратчайших используются в маршрутизаторах для определения оптимального пути, по которому следует передавать пакеты.

Алгоритмы поиска кратчайших путей базируются на простой операции, известной как ослабление, или релаксация, и которая появляется в алгоритмах в различных модификациях. В начале выполнения алгоритма поиска кратчайших путей известны только ребра сети и их веса. По мере продолжения мы собираем сведения о кратчайших путях, которые соединяют различные пары вершин. Наши алгоритмы пошагово обновляют эти сведения и делают новые предположения о кратчайших путях, основываясь на информации, полученной к текущему моменту. На каждом шаге мы проверяем, можно ли найти путь, более короткий, чем некоторый известный путь. Термин ослабление (релаксация) обычно используется для описания этого шага, т.к. он ослабляет ограничения на кратчайший путь. Мы можем представить себе резиновую ленту, плотно натянутую на пути, соединяющем две вершины, а успешная операция ослабления разрешает нам ослабить натяжение этой резиновой ленты вдоль более короткого пути.

Наши алгоритмы основываются на многократном применении одного из двух типов операций ослабления:

- Проверка, дает ли данное ребро новый кратчайший путь к вершине своего назначения;

- Проверка, дает ли прохождение через данную вершину новый кратчайший путь, соединяющий две других заданных вершины.

Первый тип будем называть ослаблением ребра, а второй - ослаблением пути. Ослабление ребра есть частный случай ослабления пути; тем не менее, оба этих типа рассматривают как отдельные операции, поскольку используют их порознь (первый ? в алгоритмах для одного источника, второй ? в алгоритмах для всех пар вершин). В обоих случаях главное требование, которое предъявляют к структурам данных, используемых для представления текущего состояния знаний о кратчайших путях сети, состоит в том, чтобы иметь возможность легко обновлять их для отображения изменений, вызванных операцией ослабления.

Определение 3.5.2 Пусть задана сеть и некоторая вершина s, тогда деревом кратчайших путей (ДКП) для s называется подсеть, содержащая s и все вершины, достижимые из s, и образующая ориентированное дерево с корнем в s, такое, что каждый путь в дереве является кратчайшим путем в сети.

Деревья ДКП не обязательно уникальны, и обычно ограничиваются вычислением какого-либо одного ДКП для данного графа и начальной вершины.

На рисунке 3.7 приведен пример ДКП, кратчайшие пути из 0 в другие узлы этой сети - это 0-1, 0-5-4-2, 0-5-4-3, 0-5-4, и 0-5.

Второй тип нахождения кратчайшего пути называется ослабление пути, которое является основой некоторых алгоритмов поиска кратчайших путей для всех пар вершин: дает ли прохождение через данную вершину более короткий путь, соединяющий две другие заданные вершины? Например, предположим, что имеются три вершины s, х и t, и нужно знать, что лучше: пройти из s в х, а затем из х в t, или сразу пройти из s в t, не заходя в х. Для прямолинейных соединений в эвклидовом пространстве из неравенства треугольника следует, что маршрут через х не может быть более коротким, чем прямой маршрут из s в t, но для путей на сети это вполне возможно. Чтобы определить, как именно обстоят дела, нам нужно знать длины путей из s в х, из х в t и из s в t (но не включающих х). Затем необходимо просто проверить, меньше ли сумма первых двух, чем третий; и если это так, соответствующим образом обновить наши данные.

Рисунок 3.7 - Деревья кратчайших путей

Свойство 3.5.1 Если вершина х лежит на кратчайшем пути из s в t, то этот путь складывается из кратчайшего пути из s в х, за которым следует кратчайший путь из x в t.

Доказательство. От противного. Иначе можно было бы воспользоваться любым более коротким путем из s в х или из х в t и составить более короткий путь из s в t.

Из свойства 3.5.1 следует, что кратчайший путь из s в t содержит кратчайшие пути из s в каждую другую вершину вдоль пути в t. Большинство алгоритмов поиска кратчайших путей также вычисляют кратчайшие пути из s в каждую вершину, которая находится ближе к s, чем к t (независимо от того, лежит ли вершина на пути из s в t), хотя это и не обязательно. Решение задачи о кратчайших путях из источника в сток с помощью такого алгоритма, когда t является наиболее удаленной от s вершиной, эквивалентно решению задачи о кратчайших путях из одного источника для s.

3.6 Алгоритм Дейкстры нахождения кратчайших путей

В разделе 3.3 был рассмотрен алгоритм Прима для нахождения минимального остовного дерева взвешенного неориентированного графа: его строили, добавляя на каждом шаге одно ребро, всегда выбирая следующее кратчайшее ребро, которое соединяет вершину из МОД с вершиной, еще не входящей в МОД. Для вычисления дерева ДКП можно воспользоваться почти такой же схемой. Начинаем с помещения в ДКП источника, затем строим ДКП, добавляя на каждом шаге одно ребро, всегда выбирая такое следующее ребро, которое дает кратчайший путь из источника в вершину, не включенную в ДКП. Другими словами, добавляем вершины к ДКП в порядке их расстояния (на дереве ДКП) от стартовой вершины. Этот метод известен как алгоритм Дейкстры.

Свойство 3.6.1 Алгоритм Дейкстры решает задачу нахождения кратчайших путей для одного источника на сетях, имеющих неотрицательные веса.

Доказательство. Для заданной вершины-источника s необходимо установить, что пути в дереве из корня s в каждую вершину х в дереве, вычисленном по алгоритму Дейкстры, соответствуют кратчайшим путям в графе из s в х. Это доказывается по индукции: исходя из предположения, что только что вычисленное поддерево обладает этим свойством, нам нужно просто показать, что добавление новой вершины х приводит к добавлению кратчайшего пути в эту вершину. Однако все другие пути, ведущие в х, должны начинаться путем в дереве и завершаться ребром, исходящим из вершины, не лежащей на дереве. По построению все такие пути являются более длинными, чем рассматриваемый путь из s в x.

На рисунке 3.8 показана последовательность построения для типовой сети (рисунок 3.6) при помощи алгоритма Дейкстры остовного дерева кратчайших путей с корнем в вершине 0. Толстыми черными линиями на схемах сетей показаны ребра дерева, а толстыми серыми - ребра бахромы. Представления в виде ориентированного дерева, в процессе его роста показаны в центре, а список ребер бахромы приведен справа.

На первом шаге добавляем вершину 0 к дереву, а ребра, выходящие из него, 0-1 и 0-5, - к бахроме (рисунок 3.8 вверху). На втором шаге перемещаем самое короткое из этих рёбер, 0-5, из бахромы в дерево и проверяем ребра, отходящие от него: ребро 5-4 добавляется к бахроме, а ребро 5-1 удаляется, поскольку оно не является частью пути из 0 в 1 более короткого, чем известный путь 0-1 (рисунок 3.8 второй сверху).

Рисунок 3.8 - Алгоритм Дейкстры нахождения кратчайших путей

Приоритет ребра 5-4 в бахроме определяется длиной пути из 0, который оно представляет, 0-5-4. На третьем шаге перемещаем 0-1 из бахромы в дерево, добавляем, к бахроме 1-2 и удаляем из нее 1-4 (рисунок 3.8 третий сверху). На четвёртом шаге перемещаем 5-4 из бахромы в дерево, добавляем 4-3 к бахроме, и заменяем 1-2 в 4-2, поскольку путь 0-5-4-2 короче, чем 1-2 (рисунок 3.8 четвертый сверху). В бахроме содержится не более одного ребра, ведущего к каждой вершине, выбирая из них то, которое лежит на кратчайшем пути из 0. Вычисления завершаются перемещением 4-2 и затем 4-3 из бахромы в дерево (рисунок 3.8 внизу).

маршрутизация алгоритм граф программа

4. Протокол маршрутизации OSPF

4.1 Протокол OSPF

Для демонстрации работы алгоритма Дейкстры для поиска кратчайших путей в дипломной работе рассмотрим протокол маршрутизации (Open Shortest Path First). Он представляет собой протокол состояния связей, использующий алгоритм Дейкстры для построения таблицы маршрутизации. OSPF применяется для внутренней маршрутизации в системах сетей любой сложности. Ниже будут рассмотрены основные особенности данного протокола.

4.2 Построение маршрутов

Рассмотрим построение маршрутов на примере системы, изображенной на рисунке 4.1. Для простоты будем рассматривать OSPF-систему, состоящую только из маршрутизаторов, соединенных линиями связи типа "точка-точка".

Обозначения на рисунке: 1,2,3,4 - маршрутизаторы; A,B,C,D - линии связи (или просто связи), цифры означают метрику каждой связи.

4.3 Метрики

Метрика представляет собой оценку качества связи в данной сети (на данном физическом канале); чем меньше метрика, тем лучше качество соединения. Метрика маршрута равна сумме метрик всех связей, входящих в маршрут. В простейшем случае (как это имеет место в протоколе RIP) метрика каждой сети равна единице, а метрика маршрута тогда просто является его длиной в хопах.

Поскольку при работе алгоритма поиска кратчайших путей ситуации, приводящие к счету до бесконечности, отсутствуют, значения метрик могут варьироваться в широком диапазоне. Кроме того, протокол OSPF позволяет определить для любой сети различные значения метрик в зависимости от типа сервиса. Для каждого типа сервиса будет вычисляться свой маршрут, и дейтаграммы, затребовавшие наиболее скоростной канал, могут быть отправлены по одному маршруту, а затребовавшие наименее дорогостоящий канал - по другому.

Рисунок 4.1 - Пример OSPF системы

Метрика сети, оценивающая пропускную способность, определяется как количество секунд, требуемое для передачи 100 Мбит через физическую среду данной сети. Например, метрика сети на базе 10Base-T Ethernet равна 10, а метрика выделенной линии 56 кбит/с равна 1785. Метрика канала со скоростью передачи данных 100 Мбит/с и выше равна единице.

Порядок расчета метрик, оценивающих надежность, задержку и стоимость, не определен. Администратор, желающий поддерживать маршрутизацию по этим типам сервисов, должен сам назначить разумные и согласованные метрики по этим параметрам.

Если не требуется маршрутизация с учетом типа сервиса (или маршрутизатор ее не поддерживает), используется метрика по умолчанию, равная метрике по пропускной способности.

В нашем примере мы будем использовать метрики, указанные на рисунке 4.1, без учета типов сервиса. Следует заметить, что маршрутизация по типам сервиса крайне редка, более того, она исключена из последних версий стандарта OSPF.

4.4 База данных состояния связей

Для работы алгоритма Дейкстры на каждом маршрутизаторе строится база данных состояния связей, представляющая собой полное описание графа OSPF-системы. При этом вершинами графа являются маршрутизаторы, а ребрами - соединяющие их связи. Базы данных на всех маршрутизаторах идентичны.

За создание баз данных и поддержку их взаимной синхронизации при изменениях в структуре системы сетей отвечают другие алгоритмы, содержащиеся в протоколе OSPF. Эти алгоритмы рассмотрены ниже, а сейчас будем считать, что базы данных на всех маршрутизаторах каким-то образом построены, синхронизированы и правильно описывают граф системы в данный момент времени.

База данных состояния связей представляет из себя таблицу, где для каждой пары смежных вершин графа (маршрутизаторов) указано ребро (связь), их соединяющее, и метрика этого ребра. Граф считается ориентированным, то есть ребро, соединяющее вершину 1 с вершиной 2, и ребро, соединяющее вершину 2 с вершиной 1, могут быть различны или это может быть одно и то же ребро, но с разными метриками.

База данных состояния связей в нашем примере (для рисунка 4.1) выглядит следующим образом:

Таблица 4.1

Направление передачи	Сеть	Метрика
1 2	A	2
1 3	C	3
1 4	B	1
2 1	A	2
3 1	C	3
3 4	D	1
4 1	B	1
4 3	D	1

4.5 Разграничение хостов и маршрутизаторов

Выше была рассмотрена сеть, состоящая только из маршрутизаторов, соединенных двухточечными линиями связи. В этой системе отсутствовали хосты.

Предположим, что к маршрутизатору 4 подключена сеть N1 из некоторого количества хостов H1-Hk (рисунок 4.2).

Рисунок 4.2 - OSPF-система с маршрутизаторами и хостами

Следуя разобранной выше модели, каждый хост должен быть также вершиной графа OSPF-системы, хотя сам и не строит базу данных и не производит вычисления маршрутов. Тем не менее, информация о связях маршрутизатора 4 с каждым из хостов сети N1 и о метриках этих связей должна быть внесена в базу данных, чтобы все остальные маршрутизаторы системы могли построить маршруты от себя до этих хостов.

Очевидно, что такая процедура неэффективна. Вместо информации о связях с каждым хостом в базу данных вносится информация о связи с сетью, то есть сама IP-сеть становится вершиной графа системы, соединенной с маршрутизатором 4 с помощью некоторой связи P (рисунок 4.3).

Рисунок 4.3 - OSPF-система с маршрутизаторами и тупиковой сетью

Подчеркнем, что в данном случае сеть, точнее ее адрес, используется как обобщающий идентификатор группы хостов, находящихся в одной IP-сети, к которой маршрутизатор 4 непосредственно подключен. Вершина N1 называется тупиковой сетью; все узлы сети, обозначаемые этой вершиной, являются хостами, у которых установлен маршрут по умолчанию, направленный на маршрутизатор 4.

Протокол OSPF производит разграничение хостов и маршрутизаторов. Если к IP-сети N1 подключен еще и один из интерфейсов маршрутизатора 2, то связь между 2 и 4 будет установлена отдельно, как если бы они были соединены двухточечной линией связи (при этом у маршрутизатора 2 также будет связь с тупиковой сетью N1).

При подключении тупиковой сети N1 в базе данных состояния связей появится запись:

Таблица 4.2

От до	Связь	Метрика
4N1	P	1

Связей, направленных из вершины N1, в базе данных не будет, потому что вершина N1 не является маршрутизатором. Построение маршрутов до вершины N1 (то есть фактически сразу до всех хоcтов сети N1) будет произведено каждым маршрутизатором обычным способом по алгоритму Дейкстры.

4.6 Поддержка множественных маршрутов

Если между двумя узлами сети существует несколько маршрутов с одинаковыми или близкими по значению метриками, протокол OSPF позволяет направлять части трафика по этим маршрутам в пропорции, соответствующей значениям метрик. Например, если существует два альтернативных маршрута с метриками 1 и 2, то две трети трафика будет направлено по первому из них, а оставшаяся треть - по второму.

Положительный эффект такого механизма заключается в уменьшении средней задержки прохождения дейтаграмм между отправителем и получателем, а также в уменьшении колебаний значения средней задержки.

Менее очевидное преимущество поддержки множественных маршрутов состоит в следующем. Если при использовании только одного из возможных маршрутов этот маршрут внезапно выходит из строя, весь трафик будет разом перемаршрутизирован на альтернативный маршрут, при этом во время процесса массового переключения больших объемов трафика с одного маршрута на другой весьма велика вероятность образования затора на новом маршруте. Если же до аварии использовалось разделение трафика по нескольким маршрутам, отказ одного из них вызовет перемаршрутизацию лишь части трафика, что существенно сгладит нежелательные эффекты.

4.7 Накладывающиеся маршруты

Пусть в графе OSPF-системы некий маршрутизатор имеет связи с вершинами N и М, которые представляют сети хостов, подключенные к различным интерфейсам маршрутизатора. Это означает, что в таблице маршрутов этого маршрутизатора, будет две записи: одна для сети N, другая для сети M.

Предположим теперь, что адрес и маска сети М таковы, что она является подсетью сети N. Например, N=172.16.0.0 netmask 255.255.0.0; M=172.16.5.0 netmask 255.255.255.0.

В этом случае дейтаграммы, следующие по адресу, находящемуся в обеих сетях, будут отправлены в сеть с более длинной маской. Например, адрес 172.16.5.1 находится как в сети N, так и в сети М, но маска сети M длиннее, следовательно, дейтаграмма, следующая по этому адресу, будет отправлена в сеть М.

4.8 Внешние маршруты

Для достижения сетей, не входящих в OSPF-систему (в автономную систему), используются пограничные маршрутизаторы автономной системы (autonomous system border router, ASBR), имеющие связи, уходящие за пределы системы.

ASBR вносят в базу данных состояния связей данные о сетях за пределами системы, достижимых через тот или иной ASBR. Такие сети, а также ведущие к ним маршруты называются внешними (external).

В простейшем случае, если в системе имеется только один ASBR, он объявляет через себя маршрут по умолчанию (default route) и все дейтаграммы, адресованные в сети, не входящие в базу данных системы, отправляются через этот маршрутизатор.

Если в системе имеется несколько ASBR, то, возможно, внутренним маршрутизаторам системы придется выбирать, через какой именно пограничный маршрутизатор нужно отправлять дейтаграммы в ту или иную внешнюю сеть. Это делается на основе специальных записей, вносимых ASBR в базу данных системы. Эти записи содержат адрес и маску внешней сети и метрику расстояния до нее, которая может быть, а может и не быть сравнимой с метриками, используемыми в OSPF-системе возможно, адреса нескольких внешних сетей агрегируются в общий адрес с более короткой маской.

Рисунок 4.4 - Состояние каналов и компоненты протокола OSPF

ASBR может получать информацию о внешних маршрутах от протоколов внешней маршрутизации, а также все или некоторые внешние маршруты могут быть сконфигурированы администратором (в том числе единственный маршрут по умолчанию).

4.9 Построение базы данных состояния связей

4.9.1 Протокол Hello

После инициализации модуля OSPF (например, после подачи питания на маршрутизатор) через все интерфейсы, включенные в OSPF-систему, начинают рассылаться Hello-сообщения. Задача Hello-протокола - обнаружение соседей и установление с ними отношений смежности.

Соседями называются OSPF-маршрутизаторы, подключенные к одной сети (к одной линии связи) и обменивающиеся Hello-сообщениями.

Смежными называются соседние OSPF маршрутизаторы, которые приняли решение обмениваться друг с другом информацией, необходимой для синхронизации базы данных состояния связей и построения маршрутов. Не все соседи становятся смежными.

Другая задача протокола Hello - выбор выделенного маршрутизатора в сети с множественным доступом, к которой подключено несколько маршрутизаторов.

Hello-пакеты продолжают периодически рассылаться и после того, как соседи были обнаружены. Таким образом маршрутизатор контролирует состояние своих связей с соседями и может своевременно обнаружить изменение этого состояние (например, обрыв связи или отключение одного из соседей). Обрыв связи может быть также обнаружен и с помощью протокола канального уровня, который просигнализирует о недоступности канала.

В сетях с возможностью широковещательной рассылки (broadcast networks) Hello-пакеты рассылаются по мультикастинговому адресу 224.0.0.5 ("Всем ОSPF-маршрутизаторам"). В других сетях все возможные адреса соседей должны быть введены администратором.

4.9.2 Протокол обмена

После установления отношений смежности для каждой пары смежных маршрутизаторов происходит синхронизация их баз данных. Эта же операция происходит при восстановлении ранее разорванного соединения, поскольку в образовавшихся после аварии двух изолированных подсистемах базы данных развивались независимо друг от друга. Синхронизация баз данных происходит с помощью протокола обмена (Exchange protocol).

Сначала маршрутизаторы обмениваются только описаниями своих баз данных (Database Description), содержащими идентификаторы записей и номера их версий, это позволяет избежать пересылки всего содержимого базы данных, если требуется синхронизировать только несколько записей.

Во время этого обмена каждый маршрутизатор формирует список записей, содержимое которых он должен запросить (то есть эти записи в его базе данных устарели либо отсутствуют), и соответственно отправляет пакеты запросов о состоянии связей (Link State Request). В ответ он получает содержимое последних версий нужных ему записей в пакетах типа "Обновление состояния связей (Link State Update)".

После синхронизации баз данных производится построение маршрутов используя алгоритм поиска кратчайших путей.

4.9.3. Протокол затопления

Каждый маршрутизатор отвечает за те и только те записи в базе данных состояния связей, которые описывают связи, исходящие от данного маршрутизатора. Это значит, что при образовании новой связи, изменении в состоянии связи или ее исчезновении (обрыве), маршрутизатор, ответственный за эту связь, должен соответственно изменить свою копию базы данных и немедленно известить все остальные маршрутизаторы OSPF-системы о произошедших изменениях, чтобы они также внесли исправления в свои копии базы данных.

Подпротокол OSPF, выполняющий эту задачу, называется протоколом затопления (Flooding protocol). При работе этого протокола пересылаются сообщения типа "Обновление состояния связей (Link State Update)", получение которых подтверждается сообщениями типа "Link State Acknowledgment".

Каждая запись о состоянии связей имеет свой номер (номер версии), который также хранится в базе данных. Каждая новая версия записи имеет больший номер. При рассылке сообщений об обновлении записи в базе данных номер записи также включается в сообщение для предотвращения попадания в базу данных устаревших версий.

Маршрутизатор, ответственный за запись об изменившейся связи, рассылает сообщение "Обновление состояния связи" по всем интерфейсам. Однако новые версии состояния одной и той же связи должны появляться не чаще, чем оговорено определенной константой.

Далее на всех маршрутизаторах OSPF-системы действует следующий алгоритм.

1) Получить сообщение. Найти соответствующую запись в базе данных.

2) Если запись не найдена, добавить ее в базу данных, передать сообщение по всем интерфейсам.

3) Если номер записи в базе данных меньше номера пришедшего сообщения, заменить запись в базе данных, передать сообщение по всем интерфейсам.

4) Если номер записи в базе данных больше номера пришедшего сообщения и эта запись не была недавно разослана, разослать содержимое записи из базы данных через тот интерфейс, откуда пришло сообщение. Понятие "недавно" определяется значением константы.

5) В случае равных номеров сообщение игнорировать.

Протокол OSPF устанавливает также такую характеристику записи в базе данных, как возраст. Возраст равен нулю при создании записи. При затоплении OSPF-системы сообщениями с данной записью каждый маршрутизатор, который ретранслирует сообщение, увеличивает возраст записи на определенную величину. Кроме этого, возраст увеличивается на единицу каждую секунду. Из-за разницы во времени пересылки, в количестве промежуточных маршрутизаторов и по другим причинам возраст одной и той же записи в базах данных на разных маршрутизаторах может несколько различаться, это нормальное явление.

При достижении возрастом максимального значения (60 минут), соответствующая запись расценивается маршрутизатором как просроченная и непригодная для вычисления маршрутов. Такая запись должна быть удалена из базы данных.

Поскольку базы данных на всех маршрутизаторах системы должны быть идентичны, просроченная запись должна быть удалена из всех копий базы данных на всех маршрутизаторах. Это делается с использованием протокола затопления: маршрутизатор затапливает систему сообщением с просроченной записью. Соответственно, в описанный выше алгоритм обработки сообщения вносятся дополнения, связанные с получением просроченного сообщения и удалением соответствующей записи из базы данных.

Чтобы записи в базе данных не устаревали, маршрутизаторы, ответственные за них, должны через каждые 30 минут затапливать систему сообщениями об обновлении записей, даже если состояние связей не изменилось. Содержимое записей в этих сообщениях неизменно, но номер версии больше, а возраст равен нулю.

Вышеописанные протоколы обеспечивают актуальность информации, содержащейся в базе данных состояния связей, оперативное реагирование на изменения в топологии системы сетей и синхронизацию копий базы данных на всех маршрутизаторах системы.

Для обеспечения надежности передачи данных реализован механизм подтверждения приема сообщений, также для всех сообщений вычисляется контрольная сумма.

В протоколе OSPF может быть применена аутентификация сообщений, например, защита их с помощью пароля.

Рисунок 4.5 - Анализ пакета LSU

4.10 Сети множественного доступа

4.10.1 Проблемы возникающие в сетях множественного доступа

Протокол OSPF особым образом выделяет сети множественного доступа, то есть сети, где каждый узел может непосредственно связаться с каждым. Такие сети могут также поддерживать широковещательную передачу и мультикастинг (broadcast networks, например, Ethernet, FDDI) или не поддерживать таковой (non-broadcast multi-access networks, NBMA, например, Х.25, Frame Relay, ATM).

Рассмотрим сначала случай широковещательной сети, к которой подключено несколько маршрутизаторов. Следуя модели работы протоколов состояния связей, связь каждой пары маршрутизаторов должна рассматриваться как связь типа "точка-точка", что значит: каждый маршрутизатор должен установить смежность с каждым, то есть всего N(N-1)/2 отношений смежности, по которым происходит обмен всеми типами сообщений, описанных выше. Каждый маршрутизатор будет вносить в базу данных N-1 записей о связях с другими маршрутизаторами плюс одна связь с вершиной типа "тупиковая сеть" (то есть с хостами, которые тоже могут находиться в этой IP-сети), всего в базе данных будет N2 записей, касающихся рассматриваемой сети.

4.10.2 Уменьшение числа отношений смежности

Очевидно, такое буквальное следование идеологии не является рациональным. Протокол OSPF сводит ситуацию только к N отношениям смежности, выбирая среди всех маршрутизаторов данной широковещательной сети один выделенный маршрутизатор (designated router, DR), с которым все остальные маршрутизаторы устанавливают отношения смежности.

Это значит, что каждый "невыделенный" маршрутизатор поддерживает синхронизацию базы данных состояния связей не со всеми соседями, а только с выделенным маршрутизатором. При этом протокол затопления в подобной сети работает следующим образом: "обычный" маршрутизатор сообщает об изменении состояния своих связей выделенному маршрутизатору, а тот затапливает сеть этим сообщением и его получают все остальные маршрутизаторы сети. Естественно, что по своим внешним интерфейсам, ведущим к прочим маршрутизаторам системы, не находящимся в данной сети множественного доступа, каждый маршрутизатор отправляет сообщения без участия выделенного маршрутизатора.

4.10.3 Уменьшение размера базы данных

Протокол OSPF позволяет также редуцировать размер базы данных состояния связей. Для этого в граф системы вводится виртуальная вершина "транзитная сеть", представляющая собой сеть множественного доступа как таковую. Каждый маршрутизатор, в том числе и выделенный, при таком подходе имеет не набор двухточечных связей со всеми остальными маршрутизаторами своей сети, а одну связь с вершиной "транзитная сеть". Таким образом, в базу данных вносится всего 2•N, а не N² записей: N записей о связях, идущих от маршрутизаторов к вершине "транзитная сеть", и столько же связей, идущих в обратном направлении.

За поддержку в базе данных записей о связях, идущих от маршрутизаторов, отвечают, как и положено, сами маршрутизаторы. Эти связи имеют метрику, равную метрике сети (например, 10 в случае 10Base-T Ethernet).

За поддержку связей, идущих от транзитной сети к маршрутизаторам, отвечает выделенный маршрутизатор. Такие связи имеют нулевую метрику, это связано с тем, что при такой модели маршрут между двумя маршрутизаторами А и В в сети T проходит через вершину "транзитная сеть Т", то есть его метрика равна сумме метрик связей АТ и ТВ. Очевидно, что метрика этого маршрута должна быть равна метрике сети, но метрика связи АТ уже равна метрике сети, следовательно, метрика связи ВТ должна быть нулевой.

4.10.4 Выборы выделенного маршрутизатора

Выборы выделенного маршрутизатора проводятся с помощью протокола Hello. Кроме выделенного маршрутизатора выбирается также и запасной выделенный маршрутизатор (backup designated router, BDR), остальные маршрутизаторы сети устанавливают отношения смежности как с DR, так и с BDR (следовательно, в предыдущем пункте при описании отношений смежности не хватает BDR). Все сообщения для DR и BDR посылаются по мультикастинговому адресу 224.0.0.6 "Всем выделенным OSPF-маршрутизаторам".

Запасной выделенный маршрутизатор получает эти сообщения, но не предпринимает никаких действий, связанных со своей выделенной функцией. Однако если выделенный маршрутизатор отключается (этот факт детектируется с помощью протокола Hello), то запасной немедленно становится выделенным, не тратя времени на установление отношений смежности с остальными маршрутизаторами, так как эти отношения уже установлены. При этом с помощью протокола Hello выбирается новый запасной выделенный маршрутизатор. Если бывший выделенный маршрутизатор подключится снова, статус выделенного маршрутизатора ему не возвращается.

4.10.5 NBMA и point-to-multipoint сети

В случае, когда несколько OSPF-маршрутизаторов подключены к сети множественного доступа, не поддерживающей широковещательную передачу (NBMA-сеть), они следуют той же процедуре, что и в случае широковещательной сети, поскольку каждый маршрутизатор также может непосредственно связаться с каждым, и, следовательно, существует та же проблема "N²" по числу отношений смежности и числу записей в базе данных состояния связей. В случае NBMA-сетей проблема даже усугубляется тем, что поддержка постоянных соединений между любыми двумя маршрутизаторами для обмена маршрутной информацией (отношения смежности) может потребовать значительных технических и финансовых затрат.

Отличие NBMA от широковещательных сетей состоит в том, что адреса всех соседей должны быть предварительно сконфигурированы на каждом маршрутизаторе, потому что возможности передавать мультикастинговые сообщения нет.

Если маршрутизатор, подключенный к нешироковещательной сети, может непосредственно связаться с несколькими, но не со всеми маршрутизаторами этой сети (неполный множественный доступ), такое соединение конфигурируется как point-to-multipoint и не рассматривается протоколом OSPF как сеть множественного доступа со всеми вышеописанными последствиями. Маршрутизатор, подключенный к соединению типа point-to-multipoint, устанавливает двухточечные связи с каждым своим соседом по соединению.

Могут быть также причины, по которым администратор пожелает сконфигурировать сеть с полным множественным доступом как point-to-multipoint.

4.11 Межзональное взаимодействие с помощью протокола OSPF

4.11.1 Работа протокола OSPF в многозонной среде

Ранее была рассмотрена работа протокола OSPF в пределах одной зоны. Теперь рассмотрим, что произойдет, если эта зона распадается, допустим, на 400 сетей. Для понимания принципов работы протокола OSPF в многозонной среде необходимо рассмотреть следующие проблемы.

- Периодические перерасчеты по алгоритму Дейкстры. При наличии большого количества сегментов возникновение изменений в сети неизбежно. ЦПУ маршрутизаторов будут в основном затребованы для перерасчета таблиц маршрутизации, так как в этом случае они будут получать все обновления из зон.

- Большой размер таблицы маршрутизации. Маршрутизатор должен хранить не менее одной записи для каждой сети. В предыдущем примере, по крайней мере, 400 сетей. Полагая, что как минимум в 25% из этих 400 сетей будут существовать альтернативные пути, это увеличит размер таблиц маршрутизации еще на десять записей.

В свете этих проблем и был создан протокол OSPF. Он был разработан для того чтобы иметь возможность разделения больших зон на маленькие, более управляемые зоны, которые по-прежнему будут обмениваться между собой маршрутизирующей информацией.

Способность протокола OSPF к разделению больших сетей на множество малых называется также иерархической маршрутизацией. На рисунке 4.6 показано, как иерархическая маршрутизация позволяет разделить большую сеть (автономную систему) на множество малых сетей, которые называются зонами. При такой технологии марщру. тизация будет иметь место также и между зонами (это называется межзонной маршрутизацией), но многие из внутренних операций маршрутизации, такие как перерасчет базы данных, останутся внутри зоны. Возьмем для примера рисунок 4.6. Здесь при возникновении проблем с каналами в зоне 1 маршрутизаторы в других зонах не будут производить перерасчет в соответствии с алгоритмом SPF, так как они полностью изолированы от проблем, возникающих в зоне 1.

Иерархическая топология протокола OSPF имеет следующие преимущества:

-Уменьшение частоты перерасчетов в соответствии с алгоритмом Дейкстры. Поскольку детальная информация о путях в отдельных зонах хранится в каждой зоне отдельно, необходимость в рассылке информации о состоянии каналов отпадает. Таким образом, при изменениях в топологии далеко не всем маршрутизаторам требуется запускать перерасчет SPF. Это потребуется делать только тем маршрутизаторам, которые принадлежат отдельной сети, где имело место изменение;

- Уменьшение размера таблиц маршрутизации. При работе в многозонной среде детализированные записи о межзонных сетях хранятся внутри самих зон. Вместо того чтобы посылать объявление обо всех маршрутах за пределы зоны, все они суммируются в один или более суммарных адресов. Объявление о суммарных путях уменьшает трафик LSA-пакетов, рассылаемых между зонами в такой сети.

Иерархическая маршрутизация позволяет повысить эффективность маршрутизации, контролировать тип информации о маршрутизации, их поступление и рассылку. Протокол OSPF позволяет варьировать типы обновления маршрутизации. Это достигается присвоением всем зонам и всем маршрутизаторам определенных характеристик. Характеристики зоны и маршрутизатора управляют процессом обработки информации о маршрутизации, включая и то, какие типы LSU-пакетов маршрутизатор может создавать, принимать и рассылать.

Рисунок 4.6 - Иерархическая маршрутизация протокола OSPF

4.11.2 Типы маршрутизаторов

На рисунке 4.7 отображен процесс управления прохождением трафика из одной зоны в другую зону различными типами маршрутизаторов под управлением протокола OSPF. Маршрутизаторы характеризуются следующими типами:

- Внутренний маршрутизатор - это маршрутизатор, интерфейсы которого находятся в одной и той же зоне. Внутренние маршрутизаторы внутри одной зоны имеют аналогичные базы данных каналов;

- Магистральный маршрутизатор - это маршрутизатор, установленный в магистральной зоне. По крайней мере один его интерфейс подключен к зоне 0. Эти маршрутизаторы обрабатывают маршрутизирующую информацию протокола OSPF с помощью тех же процедур и алгоритмов, что и внутренние маршрутизаторы. Зона 0 является транзитной между другими зонами;

- Пограничный маршрутизатор (ABR) - это маршрутизатор, интерфейсы которого подключены к внешним зонам. Эти маршрутизаторы ведут базы данных состояния каналов со всеми зонами, к которым они подключены, и маршрутизируют входящий и исходящий трафики. Для зоны марщру. тизаторы ABR являются выходными точками, а это значит, что маршрутизируемая информация, направляющаяся в другие зоны, может достичь их только через пограничные маршрутизаторы. Маршрутизаторы ABR могут суммировать информацию из своих БД состояния каналов из зон, подключенных к ним, и передавать ее в свою магистральную зону. Затем магистральные маршрутизаторы ABR пересылают информацию во все подключенные к ним зоны. Зона может иметь один или более маршрутизаторов ABR;