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

Размещено на http://www.allbest.ru/

Введение

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

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

1) Отыскание оптимального пути соединяющего все точки графа (задача построения минимального остовного дерева);

2) Отыскание оптимального пути соединяющего две заданные точки графа (задача поиска кратчайших путей).

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

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

1. Постановка задачи сетевого взаимодействия

1.1 Понятие сети связи

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

Основой сети связи является ее структура - пункты и линии (каналы) связи. Сеть с N пунктами характеризуется прежде всего их расположением - географией сети, что определяется либо перечнем координат всех пунктов а₁, ..., а_n, либо расстояниями между ними: кратчайшими (по прямой) lijкр или по линиям сети lij. Расстояния могут быть записаны в виде матриц Lкр = || lijкр || или L= || lij ||.

Все пункты сети по своей роли в доставке информации можно разделить на два основных класса:

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

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

2. Узлы связи УС, осуществляющие распределение информации на сети: а) коммутационные узлы КУ, обеспечивающие коммутацию каналов КК, сообщений КС или пакетов КП между сходящимися в узле каналами или линиями от оконечных пунктов и других узлов; б) сетевые (некоммутационные) узлы, в которых осуществляется кроссировка (долговременная коммутация) сходящихся в узле линий для организации пучков прямых каналов. В общем случае узлы всегда выполняют несколько функций, т. е. в коммутационном узле часть каналов может быть скроссирована и имеются каналы, которые не могут быть использованы для транзита. Всякий узел содержит каналообразующую аппаратуру и системы, обеспечивающие распределение сообщений: кросс, системы коммутации каналов, сообщений или пакетов, -- а также устройства управления УУ и может содержать ЭВМ или другие устройства для хранения и обработки информации.

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

1.2 Показатели эффективности сетей связи

Одной из важнейших характеристик сети связи является степень использования каналов и другого оборудования, которая зависит как от построения сети и ее исправной работы, так и от загрузки каналов передаваемыми сообщениями. В настоящее время существует несколько подходов к оценке полезного использования канала, под которым понимают время: t1 ? в течение которого канал предоставлен пользователю (занят абонентом или сдан в аренду) независимо от того, загружен он или нет; t2 ? то же, но оплачиваемое пользователем; t3 ? в течение которого канал «активен», т. е. по нему передаются сообщения; t4 ? в течение которого передается полезная для пользователя информация (исключаются адресная и служебная информация, избыточная информация для повышения верности, переспросы и т. п.). При этом t4<t3<t2?t1<tи, где tи ? время исправного состояния канала. Под коэффициентом использования канала чаще всего понимают отношение:

где Т ? полное время эксплуатации канала. Иногда степень использования канала определяют отношением объема переданного сообщения (общего, оплачиваемого, соответствующего полезной информации и т, п.) к пропускной способности канала.

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

где cij ? номинальная пропускная способность ребра (линии, пучка каналов) в бит/с или Эрл при заданном качестве;

lij ? длина ребра в километрах.

Если пропускная способность ребра определена его емкостью , то мощность сети в канало-км равна общей длине каналов:

.

Реальная мощность сети

,

где? коэффициент использования каналов ребра.

Производительность сети:

где ? объем переданных за время Т сообщений (в битах или часо-занятиях) между пунктами as и at;

lst ? длина кратчайшего пути между этими пунктами (в километрах). Отношение П/D показывает, насколько хорошо используется мощность сети ? ее каналы.

Качество обслуживания кроме таких показателей, как качество передачи (наличие искажений, разборчивость, четкость), потери вызовов и различные задержки в установлении соединения и при доставке может быть охарактеризовано коэффициентом полезного использования времени пользователей (абонентов):

где ? эффективное время (при телефонном разговоре ), затрачиваемое пользователями на передачу и прием полезной информации;

? коэффициент, учитывающий потери времени на паузы, повышение верности, переспросы и т. п.;

Т1 и Т2 ? полное время, затрачиваемое передающим и принимающим пользователями;

Т3 ? время, затрачиваемое третьим человеком принимающим участие в установлении связи (например, ответетившим и вызвавшим адресата).

1.3 Понятия о структуре сети, путях и сечениях

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

Для изучения структурных свойств сетей их удобнее всего представить в виде графа без петель (рисунок 1.1) G={A, В}, где А = {а1, ..., aN} ? совокупность пунктов (узлов) сети (вершин графа) и B={bij} ? множество ребер, соединяющих узлы ai и aj, соответствующих всем линиям или каналам связи между этими узлами. Поскольку каналы могут быть одностороннего (по направлению передачи информации или установления соединения) и двустороннего действия, то и соответствующие им ребра будут направленными (ориентированными) или ненаправленными (неориентированными).

Граф может быть записан матрицей смежности (связности) порядка N, по главной диагонали которой поставлены черточки (знак неопределенности), которые в конкретных случаях могут заменяться 0 или 1, а вхождения аij принимают значения 1, если есть ребро, связывающее узел ai с узлом aj, и 0, если ребра нету. Если в сети нет направленных ребер, то матрица будет симметричной по отношению к главной диагонали. Для сети на рисунке 1.1 матрица смежности имеет вид:



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

Пункты (узлы), соединенные ребром, будем называть смежными. Число ребер, инцидентных данному пункту (входящих или исходящих), назовем рангом r(ai) этого узла. Узел ранга 1 является тупиковым ? оконечным, ? и через него не могут проходить никакие пути.

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

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



Рисунок 1.1 ? Пример сети изображенной в виде графа

Рангом пути будем называть число ребер, образующих этот путь. Минимальный ранг пути 1, максимальный N-1, когда путь проходит через все узлы.

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

Все пути от as к at образуют множество mst, а совокупность (объединение) двух множеств, соответствующих противоположным направлениям, ? множество Mst всех путей между as и at: . Для ненаправленных сетей .

В реальной сети, как правило, для связи между заданными узлами as и at используются не все возможные пути, а только пути, выделенные по какому-либо показателю или обладающие некоторыми заданными свойствами.

Связной называется сеть, любые узлы которой связаны хотя бы одним путем. Сеть называется h-связной, если любые два узла связаны независимыми путями, число которых не менее h. Понятие связности чаще относится не ко всей сети, а к заданным узлам as и at (hst ? связность).

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

В общем случае в сети с N узлами может быть сечений. Каждое сечение может быть записано множеством (перечнем) входящих в него ребер:

Рангом сечения будем называть число входящих в него ребер.

Из теории графов известно, что в ненаправленной сети необходимым и достаточным условием связности сети является то, что ранг всех сечений этой сети должен быть не менее h:

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

Рассмотрим некоторые типовые структуры сетей связи и их основные характеристики (число ребер, связность и т. п.) при N узлах и ненаправленных ребрах.

1. Полносвязная сеть (рисунок 1.2 а) ? «каждый с каждым». В такой сети число ребер равно N(N-1)/2. Связность h=N-1.

2. Древовидная сеть (рисунок 1.2 б) ? «дерево». В такой сети между любыми двумя узлами может быть только один путь, т. е. сеть односвязная (h=1). Число ребер в такой сети равно N-1. Частными случаями древовидной сети являются: а) узловая сеть (рисунок 1.2 в) с иерархическим построением и соподчинением узлов; б) звездообразная сеть рисунок 1.2 г) с одним узлом и в) линейная сеть (рисунок 1.2 д).

3. Петлевая (шлейфовая, кольцевая) сеть (рисунок 1.2 е). В ней число ребер равно N, и между каждыми двумя узлами имеется два пути (h = 2).

4. Сетка ? сетеобразная сеть (рисунок 1.2 ж-и), в которой каждый узел смежен только с небольшим числом других узлов, обычно ближайших по расстоянию или имеющих большое тяготение. Различают два вида сеток ? плоскую (планарную), которая может быть нарисована на плоскости без пересечения ребер (рисунок 1.2 ж) и неплоскую (непланарную), которую нельзя изобразить без пересечения ребер (рисунок 1.2 з). Среди сетеобразных структур можно выделить радиально-петлевую (паутинообразную), сеть, которая при одной петле (рисунок 1.2 и) имеет 2(N--1) ребер и h=3.

Рисунок 1.2

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

2.1 Постановка задачи

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

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

2.2 Определение маршрута

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

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

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

Таблица 2.1

Сеть назначения	Послать пакет
27	Узлу A
57	Узлу B
17	Узлу C
24	Узлу A
52	Узлу A
16	Узлу B
26	Узлу A
…	…

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

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

2.3 Алгоритмы маршрутизации

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

2.4 Цели разработки алгоритмов маршрутизации

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

1. Оптимальность

2. Простота и низкие непроизводительные затраты

3. Живучесть и стабильность

4. Быстрая сходимость

5. Гибкость

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

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

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

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

Быстрая сходимость: Алгоритмы маршрутизации должны быстро сходиться. Сходимость - это процесс соглашения между всеми маршрутизаторами по оптимальным маршрутам. Когда какое-нибудь событие в сети приводит к тому, что маршруты или отвергаются, или становятся доступными, маршрутизаторы рассылают сообщения об обновлении маршрутизации. Сообщения об обновлении маршрутизации пронизывают сети, стимулируя пересчет оптимальных маршрутов и, в конечном итоге, вынуждая все маршрутизаторы придти к соглашению по этим маршрутам. Алгоритмы маршрутизации, которые сходятся медленно, могут привести к образованию петель маршрутизации или выходам из строя сети.

На рисунке 2.3 изображена петля маршрутизации. В данном случае, в момент времени t1 к маршрутизатору 1 прибывает пакет. Маршрутизатор 1 уже был обновлен и поэтому он знает, что оптимальный маршрут к пункту назначения требует, чтобы следующей остановкой был маршрутизатор 2. Поэтому маршрутизатор 1 пересылает пакет в маршрутизатор 2. маршрутизатор 2 еще не был обновлен, поэтому он полагает, что следующей оптимальной пересылкой должен быть маршрутизатор 1.

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

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



Рисунок 2.3

2.4 Типы алгоритмов

Алгоритмы маршрутизации могут быть классифицированы по типам. Например, алгоритмы могут быть:

1. Статическими или динамическими

2. Одномаршрутными или многомаршрутными

3. Одноуровневыми или иерархическими

4. С интеллектом в главной вычислительной машине или в маршрутизаторе

5. Внутридоменными и междометными

6. Алгоритмами состояния канала или вектора расстояний

1) Статические алгоритмы маршрутизации вообще вряд ли являются алгоритмами. Распределение статических таблиц маршрутизации устанавливется администратором сети до начала маршрутизации. Оно не меняется, если только администратор сети не изменит его. Алгоритмы, использующие статические маршруты, просты для разработки и хорошо работают в окружениях, где трафик сети относительно предсказуем, а схема сети относительно проста.

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

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

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

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

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

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

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

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

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

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

6) Алгоритмы состояния канала (известные также как алгоритмы "первоочередности наикратчайшего маршрута") направляют потоки маршрутной информации во все узлы объединенной сети. Однако каждый маршрутизатор посылает только ту часть маршрутной таблицы, которая описывает состояние его собственных каналов. Алгоритмы вектора расстояния (известные также как алгоритмы Бэлмана-Форда) требуют от каждого маршрутизатора посылки всей или части своей маршрутной таблицы, но только своим соседям. Алгоритмы состояния каналов фактически направляют небольшие корректировки по всем направлениям, в то время как алгоритмы вектора расстояний отсылают более крупные корректировки только в соседние маршрутизаторы.

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

2.5 Показатели алгоритмов (метрики)

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

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

1. Длина маршрута

2. Надежность

3. Задержка

4. Ширина полосы пропускания

5. Нагрузка

6. Стоимость связи

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

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

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

4) Полоса пропускания относится к имеющейся мощности трафика какого-либо канала. При прочих равных показателях, канал Ethernet 10 Mbps предпочтителен любой арендованной линии с полосой пропускания 64 Кбайт/сек. Хотя полоса пропускания является оценкой максимально достижимой пропускной способности канала, маршруты, проходящие через каналы с большей полосой пропускания, не обязательно будут лучше маршрутов, проходящих через менее быстродействующие каналы. Например, если более быстродействующий канал почти все время занят, то фактическое время, необходимое для отправки пакета в пункт назначения, для этого быстродействующего канала может оказаться больше.

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

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

2.6 Таблицы маршрутизации

Решение о пересылке данных по определенному маршруту принимается на основании сведений о том, какие адреса сетей (или идентификаторы (коды) сетей) доступны в объединенной сети. Эти сведения содержатся в базе данных, называемой таблицей маршрутизации. Таблица маршрутизации представляет собой набор записей, называемых маршрутами, которые содержат информацию о расположении сетей с данными идентификаторами в объединенной сети. Таблицы маршрутизации могут существовать не только на маршрутизаторах. Узлы, не являющиеся маршрутизаторами, могут также вести свои таблицы маршрутизации для определения оптимальных маршрутов.

2.6.1 Типы записей в таблице маршрутизации

Каждая запись в таблице маршрутизации считается маршрутом и может иметь один из следующих типов.

1) Маршрут к сети

Маршрут к сети ведет к сети, входящей в объединенную сеть и имеющей указанный код (идентификатор).

2) Маршрут к узлу

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

3) Маршрут по умолчанию

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

2.6.2 Структура таблицы маршрутизации

Каждая запись таблицы маршрутизации состоит из следующих информационных полей.

1) Код сети

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

2) Адрес пересылки

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

3) Интерфейс

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

4) Метрика

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

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

3. Проблема оптимальных потоков в сетях

3.1 Основные понятия теории графов

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

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

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

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

Свойство 3.1.1 Граф, состоящий из V вершин, содержит не более V(V - 1) / 2 рёбер.

Доказательство. Всего существует V² возможных пар вершин, но в это число входят V петель, при этом связи между различными вершинами учитываются дважды, следовательно, максимальное число ребер равно (V² - V) / 2 = V(V - 1) / 2.

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

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

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

Планарный граф ? граф, который можно построить на плоскости без пересечения ребер.

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

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

Термин циклический путь используется для обозначения пути, у которого первая и последняя вершина одна и та же (и который в других отношениях не обязательно является простым); термин контур употребляется для обозначения циклического пути, который включает каждую вершину. Эквивалентное определение рассматривает путь как последовательность ребер, которая соединяет соседние вершины. Например, простой путь, показанный на рисунке 3.1 содержит последовательности 3-4-6-0-2 и 9-11-12, а циклами графа являются последовательности 0-6-4-3-5-0 и 5-4-3-5. Длина пути и цикла представляет собой количество образующих их ребер.

Рисунок 3.1

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

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

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

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

Например, граф, изображенный на рисунке 3.1, имеет три связных компоненты и охватывается лесом 7-8 9-10 9-11 9-12 0-1 0-2 0-5 5-3 5-4 4-6 (существует множество других остовных лесов). На рисунке 3.2 эти и некоторые другие свойства отображены на большем из графов.

Граф G с V вершинами есть дерево тогда и только тогда, когда он удовлетворяет одному из четырех условий:

- G содержит V - 1 ребро и ни одного цикла.

- G содержит V - 1 ребро и представляет собой связный граф.

- Каждую пару вершин в G соединяет в точности один простой путь.

- G представляет собой связный граф, в то же время при удалении любого из ребер он перестает быть связным.

Графы, у которых присутствуют все ребра, называются полными графами. Дополнение графа G определяется методом построения, взяв для начала полный граф, имеющий то же число вершин, что и исходный граф G, и удалив из него все ребра графа G. Объединением двух графов является граф, порожденный объединением множеств ребер этих графов. Объединение графа и его дополнения образует полный граф. Все графы, имеющие V вершин, суть подграфы полного графа с V вершинами. Общее число различных графов с V вершинами равно 2^V(V-1)/2 (число различных способов выбора подмножеств из V(V-1)/2 возможных ребер). Полный подграф называется кликой.

Положим насыщенность графа равной среднему значению степеней его вершин, т.е. 2•E/V. Насыщенный граф есть граф, средняя степень вершин которого пропорциональна V; разреженный граф есть граф, дополнение которого является насыщенным. Другими словами, мы считаем граф насыщенным, если число его ребер Е пропорционально V², и разреженным в противном случае.

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

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

Ребра в орграфах называются ориентированными ребрами, хотя в общем случае это различие понятно из контекста. Первая вершина ориентированного ребра называется началом; вторая вершина называется концом. На диаграммах ориентированные ребра изображаются в виде стрелок, направленных из начала в конец. Когда используется обозначение w-v по отношению к орграфу, это делается с целью показать, что ребро, которое исходит из w и заходит в v, отличается от ребра v-w, которое исходит из v и заходит в w. Направленный цикл в орграфе ? это цикл, в котором пары смежных вершин появляются в порядке, устанавливаемом ребрами графа.

Граф DAG (ориентированный ациклический граф) есть орграф, который не содержит направленных циклов. DAG-граф (ациклический орграф) и дерево (ациклический неориентированный граф) ? это отнюдь не тождественные понятия.

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

Рисунок 3.2 - Основные понятия теории графов: а) понятие цикла и клики; б) понятие остовного дерева; в) понятие дерева и пути;

3.2 Постановка задачи

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

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

Естественно, в таких ситуациях возникают вопросы, касающиеся различных аспектов минимизации стоимости. Ниже рассмотрены алгоритмы решения двух задач такого рода: 1) определение пути с наименьшей стоимостью, соединяющего все точки, и 2) отыскание пути наименьшей стоимости, соединяющего две заданных точки. Первый тип алгоритма используется в коммутаторах при работе алгоритма покрывающего дерева (STA) , находит минимальное остовное дерево; это дерево является основной темой раздела 3.3. Второй тип алгоритма, применяемый в протоколах маршрутизации (например, OSPF), определяет кратчайшие пути, и они обсуждаются в разделе 3.5.

3.3 Минимальное остовное дерево

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

Определение 3.3.1 Минимальное остовное дерево (МОД) взвешенного графа есть остовное дерево, вес которого (сумма весов его ребер) не превосходит вес любого другого остовного дерева.

Если все веса положительны, достаточно определить дерево МОД как множество ребер с минимальным общим весом, ибо такое множество и должно образовать остовное дерево.

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