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

Работа посвящена проблемам маршрутизации в телекоммуникационных сетях. Эта проблема рассматривается с двух сторон. Во-первых, в общем контексте сетевых моделей и протоколов передачи данных разных уровней, причем рассматриваются обе эталонные модели — семиуровневая модель OSI/ISO и четырехуровневая модель DOD. Во-вторых, с точки зрения теории потоков в сетях и оптимальных процедур нахождения путей в потоковых сетях.

Описаны основные протоколы IP-маршрутизации, а также приведено строение глобальных и локальных сетей, освещены некоторые вопросы мониторинга и анализа локальных сетей. Сделана попытка систематизировать и обобщить знания связанные с маршрутизацией в телекоммуникационных сетях (не ограничиваясь IP-сетями). [4, 16, 26, 33, 64, 65].

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

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

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

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

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

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

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

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

Выводы.

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

При создании программного инструментария были использованы современные средства разработки, такие как математический пакет Matlab, среда разработки MS Visual Studio, СУБД MS SQL Server.

Научная новизна диссертационной работы складывается из следующих результатов:

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

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

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

• На основе численных экспериментов проведено исследование по сравнительному анализу алгоритмов последовательного заполнения.

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

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

• Управление потоками в распределенных системах хранения и передачи данных;

• Задача минимизации заторов и пробок в дорожной сети города;

• Задача планирования развития дорожной сети города;

• Маршрутизация и проектирование в IP-сетях для автономной системы или ее сегментов при использовании MPLS и туннелирования;

• Маршрутизация в SDH/SONET-сетях;

• Канальная маршрутизация с централизованным управлением.

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

Результаты данной работы были использованы при проектировании телекоммуникационных сетей РАН.

Обобщить результаты и выводы можно следующими пунктами:

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

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

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

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

Численный эксперимент в статическом режиме сетей позволил выявить два лучших алгоритма:

• субоптимальный минимально-разрезный алгоритм (PC);

• гибридный минимально-разрезный алгоритм (РГ).

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

• равномерный по дугам алгоритм (Д);

• аддитивный минимально-разрезный алгоритм (РА), так как они не позволяют достичь увеличения полного потока в сети при заполнении до полного отказа.

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

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

• Наличие и протяженность стационарного режима является важной характеристикой сетей при динамическом заполнениисущественно здесь также и то, что свойство стационарности проявляется в сетях, которые в начальный период времени были «пустыми" — это свойство было качественно выявлено на основе экспериментальных данных;

• Для некоторых сетей выбор того или иного алгоритма заполнения оказывается очень существенным — 50% - 70% превышения проведенного потока по сравнению с простым алгоритмом.

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

Заключение

.

На рисунках 5.1. и 5.2. представлены графики относительного превышения потока по разным алгоритмам по сравнению с простым алгоритмом по критерию завершения № 1.

По результатам заполнения сетей до первого отказа (критерий завершения № 1) можно сделать следующие выводы:

• Для значительного количества сетей наблюдается превышение потока, проведенного с помощью минимально-разрезных алгоритмов (группа 2) по сравнению с простым алгоритмом. Это превышение в основном имеет место для сетей с начальными значениями МНМР меньше 0.25.

• Для сетей с 'большими значениями МНМР разные алгоритмы заполнения почти во всех случаях дают одинаковый результат,.

• Существуют сети, для которых превышение потока составляет 50%.

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

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

2.500.

— 40% bN.

2.000.

1.500.

1.000.

0.500 2 та В I, а 1 л г л.

I X X X.

О с X.

— г 5 т.

0.000.

Рисунок 5.1, Процент превышения потока для критерия 1-ого отказа.

— 40%.

2.000 e> а. п (С а. s 2 X л.

1.000.

0.000.

Рисунок.5.2. Процент превышения потока для критерия 1-ого отказа. Сортировка по убыванию процента превышения.

На рисунке 5.3. показаны графики превышения потока в процентах до полного отказа (критерий завершения № 2) для всех алгоритмов заполнения сетей. Значения отсортированы по убыванию процента превышения для гибридного алгоритма.

Рисунок 5.3. Процент превышения потока для критерия полного отказа.

Arc. Criteria 2.

Subopt. Criteria 2.

Рисунок 5.4. Гистограммы процента превышения по каждому алгоритму. Критерий № 2 до полного отказа.

Hybrid. Criteria 2.

Addopt. Criteria 2.

По этим результатам можно сделать следующие выводы.

• Алгоритмы второй группы (минимально-разрезные) создавались для увеличения потока по критерию завершения № 1, но, тем не менее, эксперимент показал, что и по критерию завершения № 2 они дают преимущество над простым алгоритмом.

• Существуют сети, для которых превышение потока составляет почти 20%.

• Наилучшие результаты, по представленным графикам, демонстрирует субоптимальный (РС) алгоритм.

• Дуговой алгоритм (группа 1) в подавляющем большинстве случаев не дает превышения потока по сравнению с простым алгоритмом.

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

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

Нижняя кривая представляет отношение полного количества проведенных заявок к общему количеству заявок. Поскольку внешний поток заявок равномерно распределен между всеми парами полюсов, то чем более неравномерна начальная сеть, тем большее количество заявок не будет удовлетворено, что и демонстрирует в среднем нижняя кривая. criteria 1/goodOrders g ood О rd ers/a IЮ rde rs steady Value at 1-st step.

0 20 40 60 80 100 120 140.

Рисунок 5.5. Заполнение 131 сетей с помощью 1 алгоритма (простой).