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

На правах рукописи

Курочкин Илья Ильич

РАЗРАБОТКА И АНАЛИЗ МЕТОДОВ ПОСЛЕДОВАТЕЛЬНОЙ ПРОКЛАДКИ ПУТЕЙ В СЕТЯХ ПЕРЕДАЧИ ДАННЫХ

Специальность 05.13.01 «Системный анализ, управление и обработка информации» (информационно-вычислительное обеспечение)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

- 3 июн 2010

Москва-2010

004603384

Работа выполнена в Учреждении Российской академии наук Институте системного анализа РАН в лаборатории Ц-1 «Моделирование и анализ телекоммуникационных систем, Центр Грид-технологий и распределенных вычислений»

Научный руководитель: доктор физико-математических наук, профессор

Афанасьев Александр Петрович

Официальные оппоненты: доктор физико-математических наук,

Карзанов Александр Викторович

кандидат технических наук, Кулагин Михаил Викторович

Ведущая организация: Учреждение Российской академии наук Институт

проблем управления им. В.А. Трапезникова РАН

Защита состоится «7» июня 2010 г. в 11 часов на заседании диссертационного совета Д 002.086.02 при Учреждении Российской академии наук Институте системного анализа Российской Академии паук, по адресу: 117312, Москва, проспект 60-летия Октября, 9.

С диссертацией можно ознакомиться в научной библиотеке Учреждения Российской академии наук Институте системного анализа Российской Академии наук (г. Москва, проспект 60-летия Октября, 9).

Отзывы на автореферат, заверенные печатью, просим направлять по адресу: 117312, Москва, проспект 60-летия Октября, 9, диссертационный совет Д 002.086.02.

Автореферат разослан «30» апреля 2010 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

Цель работы и задачи исследования.

Целями диссертации являются:

Разработка методов и программного инструментария максимизирующих общий проведенный поток в сетях передачи данных.

Для достижения поставленных целей в диссертационной работе решены следующие задачи:

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

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

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

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

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

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

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

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

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

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

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

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

Теоретическая значимость работы. Предложена новая

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

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

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

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

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

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

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

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

телекоммуникационные сети, обрабатывать информацию по текущему

заполнению сетей и осуществлять помощь по проектированию и синтезу

сетей.

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

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались па семинарах в Институте системного анализа РАН, а также на 2-й московской конференции «Декомпозиционные методы в математическом моделировании и информатике», ВЦ РАН, 2004г., г.Москва, Россия; I международной конференции «Системный анализ и информационные технологии» САИТ-2005; XV международной конференции по механике и современным прикладным программным системам (ВМСППС'2007), г.Алушта, Украина; XVI международной конференции по механике и современным прикладным программным системам (ВМСППС'2009), г.Алушта, Украина; VII международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» 2009 г., Санкт-Петербург, Россия; III международной конференции «Системный анализ и информационные технологии» САИТ-2009, Звенигород, Россия.

Публикации. Основные результаты, полученные в диссертации, опубликованы в 11 печатных работах, в том числе 5 работ в рецензируемых научных изданиях, рекомендованных ВАК, 6 публикаций в трудах научных конференций.

Личный вклад соискателя в совместных работах составляет 79 страниц в публикациях (39%) из общего объема 203 страницы (согласно изданиям) и состоит в разработке методов последовательного заполнения, разработке методики анализа и обработки результатов эксперимента, разработке и реализации алгоритмов последовательного заполнения, программной реализации алгоритмов нахождения максимального потока и алгоритмов нахождения кратчайшего пути, разработка и реализация алгоритма нахождения множества минимальных разрезов, проектировании и разработке программных

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

Структура и объем работы. Общий объем диссертации составляет 169 страниц. Диссертация включает в себя введение, четыре главы, заключение, список литературы ( 87 наименований), одно приложение.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

• Разработка алгоритмов маршрутизации, которые учитывали такие характеристики каналов передачи данных, как величины пропускной способности минимальных разрезов в сети;

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

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

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

потоками информации, максимизирующих суммарную пропускную способность сети.

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

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

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

- 1 "

разрезе максимальному потоку между этой парой полюсов; ^= ^ X ^ -среднее значение пропускных способностей минимальных разрезов между

всеми парами полюсов; общее количество М различных пар полюсов в сети равно М- N¡(N¡-1) / 2, где N - количество полюсов.

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

"ы 1 и

цг __1=Уяг

' д2 1 МЯ^

г - и,пк

~ К' 1 "

Ьт - полное количество минимальных разрезов между «1-ой парой полюсов; числа и^т = I,м,к = \,К обозначают количество различных минимальных разрезов между т-ой парой полюсов, в которые входит дуга к. Веса дуг по этой формуле получаются как положительными так и отрицательными, причем возможны циклы с отрицательными весами дуг. В этом случае задача выбора пути становится ЫР-полной, что неприемлемо на практике. Поэтому полученный алгоритм был модифицирован двумя способами. А именно, были введены аддитивно-разрезный алгоритм и субоптимальный минимально-разрезный алгоритм.

Аддитивно разрезный алгоритм (РА), его дополнительная

характеристика дуг определена следующим образом:

= К'к + 1У0 + $ £>0,

где 1Ук определяется так же, как и для оптимального алгоритма, 1¥0 -

максимальный по модулю элемент среди отрицательных величин 1Ук, взятый с

обратным знаком (т.е. положительный). Эта модификация, хотя и кажется

«безобидной», на самом деле существенно меняет критерий а именно,

8

введение постоянной для всех дуг сети положительной добавки к весам W0 + s означает замену критерия х на следующий

где bk~ пропускная способность дуги в сети G.

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

Wm =N-\ + (M-h„ +1)"; где hm - порядковый номер величины минимального разреза Rm, которые ранжированы в порядке возрастания пропускной способности. Вес всех остальных дуг, которые не входят ни в один из минимальных разрезов задается Wm= 1. Данная функция была выбрана по принципу: чем меньше пропускная способность минимального разреза, куда входит данная дуга, тем «дороже» она стоит.

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

В первом собственно дуговом алгоритме (Д) все дуги разбиваются на классы по величине пропускных способностей. Стоимости убывают по мере увеличения пропускной способности дуг, так что самые большие стоимости у дуг первого класса, самые маленькие - у дуг последнего класса. Стоимости назначаются таким образом, что если в сети существует путь, не содержащий представителя какого-либо класса, то все пути, содержащие представителя этого или меньших классов, будут иметь большие стоимости. Обозначим через IV(c) - стоимость пути с, т.е. ¡¡-'(с) = W\ ct + W2 с2 + ... + £Cq.

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

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

= N-\ + (М -кт + 1)\

где кт - порядковый номер класса дуг, которые ранжированы в порядке убывания пропускной способности, М - количество классов дуг. Данная функция была выбрана по принципу: чем меньше пропускная способность дуги, тем «дороже» она стоит.

Гибридный алгоритм. Пусть 0 - количество различных по пропускной способности минимальных разрезов между всеми парами полюсов в сети. Образуем классов дуг Вч, упорядоченных по возрастанию этих величин, которые обозначим как Ьч. Все дуги сети разнесем по классам по следующему правилу. Пусть дуга сети входит в несколько минимальных разрезов и ч -порядковый номер минимального из них по пропускной способности; тогда отнесем эту дугу к классу Вч. Если дуга не принадлежит ни к какому минимальному разрезу, то отнесем ее к классу Вч+1 и присвоим ей эффективную пропускную способность Ь,+1* = Ьч +е, £>0. Далее веса дуг рассчитываются точно так же, как в равномерном по дугам алгоритме.

В качестве эталона для сравнения введен простой алгоритм (П). В простом алгоритме веса для всех ненулевых дуг задаются как 1.

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

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

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

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

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

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

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

• Стохастическая топология;

• Топология типа «колесо» (с вариациями);

• Топология «связные кластеры».

Топология типа «дерево» умышленно не рассматривается в данной работе, так как для этой топологии не существует ни статической, ни динамической маршрутизации как таковой.

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

Рассмотрена вероятностная модель потока элементарных заявок. Пусть имеется сеть представленная графом О, состоящая из N узлов, А], А2,...,Ац и К дуг, Вь В2,...,ВК, имеющих пропускные способности Ък, к=1,2,...,К. Узлы Аь ¡=1,2,...N1, Л'/ < N будем называть также полюсами. Упорядочим каким-либо образом все пары полюсов. Общее количество М различных пар полюсов в графе в равно М = Л'/ (Л'/ — 1) / 2. Последовательность

целых неотрицательных чисел [], / = 1,2.....(,... будем называть вероятностной

моделью потока элементарных заявок, если выполнены следующие условия:

• Все числа последовательности меньше или равны М;

• Существуют частоты рт, с которыми каждое число 1 < ш < М встречается в этой последовательности.

Частота рт определяется как следующий предел:

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

и

Очевидно, что /1 Р», ='.

Вероятностный поток элементарных заявок с частотами рш для всех пар полюсов будем обозначать П( Рш)- Если все частоты одинаковы и равны 1 / М, то такой поток будем называть равномерным потоком и обозначать ПО)-Поток заявок генерировался как последовательность случайных чисел от 1 до ш, каждое с частотой рт.

Статическое заполнение. При моделировании заполнения сети время жизни заявки не учитывается и приравнивается к бесконечности, таким образом моделирование проводится в статическом режиме, в котором можно с минимальными вычислительными затратами оценить заполнение сети «на отказ».

Например, сеть кластерной топологии обладает следующими характеристиками:

• количество кластеров;

• количество вершин в каждом кластере;

• максимальное количество дуг между двумя кластерами;

• количество (часть от общего числа) пулевых дуг;

• максимальная пропускная способность дуг в сети;

• граф связности, в котором указываются пропускные способности дуг сети;

• вектор пар полюсов (пар источник-сток);

• избыточный вектор заявок на пропуск потока единичной величины (Заявка определяется как номер пары полюсов, между которыми

следует провести единичный поток);

13

• идентификационный уникальный номер сети.

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

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

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

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

В зависимости от распределения времени жизни заявок заполнение сети может протекать в нескольких режимах:

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

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

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

• Режим полного заполнения - равноценен статическому заполнению сети заявками, когда время жизни достаточно велико по сравнению с временем моделирования, полный отказ происходит в 100% случаев.

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

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

• количество связных пар полюсов,

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

• количество отказов,

• средняя длина пути,

• текущая пропускная способность дуг сети,

• мера неравномерности.

Оценка эффективности алгоритмов последовательного заполнения сети проводилась посредством следующих методов оценки:

• превышение проведенного потока (по сравнению с эталонным алгоритмом),

• величина средней длины пути,

• превышение количества отказов,

• величина суммарной пропускной способности остова сети,

• динамика меры неравномерности,

• распределение количества отказов,

• наличие и длительность стационарного режима.

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

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

Процент превышения проведенного потока. Таблица 1

Алгоритм Проведенный поток до первого отказа (1) Проведенный поток до разрыва всех пар полюсов (2)

Простой 0 0

Дуговой 8.3 -9.7

Субоптимальный дуговой 12.2 2.8

Минимально-разрезный аддитивный 4.6 -1.4

Минимально-разрезный субоптимальный 12.3 5.5

Минимально-разрезный гибридный 12.3 3.1

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

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

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

• гибридный минимально-разрезный алгоритм (РГ). Использование нового дугового субоптимального алгоритма возможно для

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

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

• аддитивный минимально-разрезный алгоритм (РА),

так как они не позволяют достичь увеличения полного потока в сети для критерия №2 (до полного отказа).

Результаты по динамическому заполнению телекоммуникационных

сетей

Один из самых интересный моментов - наблюдение различий при заполнении сети разными алгоритмами. На Рис. 1-3 показаны 3 такие сети.

Net 19

Рисунок 1. Динамика заполнения сети №19 до полного отказа.

(О а. а)

1000 1100 1200 1300 1400 1500 1600 1700 1800 Кол-во заявок

Рисунок 2. Динамика заполнения сети №37 до полного отказа. Увеличение.

—-Э|тр1е (1284/2772)

----Агс (1138/2503)

ЭиЬСй (1293/3128) АсМСШ (1284/3419) НуЬпсЮт (1293/3088) -АгсЭиЬор! (1201/3394)

МЫ 37

а <и 3

о

о

О 2000 4000 6000 8000 10000 12000 14000 16000 Кол-во заявок

Рисунок 3. Динамика заполнения сети №24 до полного отказа 18

15----------;-------- ■■•- ......-----

| -31тр1е (5780/15670)

—Агс (5801/10223)

ЭиЬСи! (5801/15266) АсМСШ (5801/10560) И— НуЬгИОЛ (5801/13739)

-АгсЗиЬор! (5801/12869)

10 - ---~ , -

№1 24

На графиках представлена динамика меры неравномерности в зависимости от количества удовлетворенных заявок при заполнении телекоммуникационной сети различными алгоритмами. Можно видеть, что длительность стационарного режима может различаться в разы для разных алгоритмов. Например, в сети № 37 для простого алгоритма нет стационарного режима, а для гибридного и дугового субоптималыюго стационарный режим составляет существенную часть процесса заполнения. Для сети № 24 пять алгоритмов последовательного заполнения имеют временный «стационарный режим» при значениях 7300-9000, тогда как простой алгоритм этого режима не имеет, хотя по критерию полного отказа этот алгоритм оказался лучшим.

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

Процент превышения проведенного потока. Таблица 2

Алгоритм Проведенный поток до первого отказа (1) Проведенный поток до разрыва всех пар полюсов (2)

Простой 0 0

Дуговой 2.1 -8.5

Субоптимальный дуговой 2.9 2.1

Минимально-разрезный аддитивный 2.3 -6.1

Минимально-разрезный субоптимальный 3.0 2.0

Минимально-разрезный гибридный 3.0 1.8

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

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

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

• аддитивный минимально-разрезный алгоритм (РА),

так как они не позволяют достичь увеличения полного потока в сети при заполнениии до полного отказа.

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

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

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

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

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Афанасьев А.П., Гринберг Я.Р., Курочкин И.И.. Алгоритм, реализующий критерий уменьшения неравномерности при заполнении сети многопродуктовым потоком. Тезисы докладов 2-й московской конференции Декомпозиционные методы в математическом моделировании и информатике./ М.: ВЦ РАН, 2004. стр.12-14

[2] Афанасьев А.Г1., Гринберг Я.Р., Курочкин И.И.. Принципы, методы, алгоритмы и протоколы маршрутизации в сетях связи. Обзор. В кн.: Сетевые и алгоритмические задачи распределенных вычислений. Труды ИСА РАН. -М.: изд-во УРСС, 2004. стр. 5-104.

[3] Афанасьев А.П., Гринберг Я.Р., Курочкин И.И.. Равномерное заполнение телекоммуникационной сети каналами связи. В кн. Прикладные проблемы управления макросистемами, Труды ИСА РАН, том 8, изд-во УРСС, 2004. стр. 118-123.

[4] Афанасьев А.П., Гринберг Я.Р., Курочкин И.И.. «Равномерные» алгоритмы последовательного заполнения потоковой сети потоками продуктов. В кн. Проблемы вычислений в распределенной среде: Сборник трудов ИСА РАН. М.: ООО «КомКнига», 2005,224 с.

[5] Афанасьев А.П., Гринберг Я.Р., Курочкин И.И.. Сравнительный анализ двух последовательных алгоритмов заполнения сети потоками продуктов. В кн. Труды конференции САИТ-2005, т.2, стр. 136-140.

[6] Гринберг Я.Р., Курочкин И.И.. Анализ результатов численного эксперимента по последовательному заполнению сетей со стохастической топологией// Проблемы вычислений в распределенной среде: распределенные приложения, коммуникационные системы, математические модели и оптимизация: Сборник трудов ИСА РАН / Под ред. А.П. Афанасьева - Т.25 - М.: КомКнига, 2006, с.99-128.

[7] Гринберг Я.Р., Курочкии И.И.; Математическое моделирование проследователыюго заполнения телекоммуникационных сетей с топологией «колесо» потоками связи. Материалы XV Международной конференции по механике и современным прикладным программным системам (ВМСППС'2007), 25-31 мая 2007, г.Алушта, Украина. - Москва, 2007г.

[8] Гринберг Я.Р., Курочкин И.И. Математическое моделирование последовательного заполнения телекоммуникационных сетей с топологией «колесо» потоками связи. / Труды ИСА РАН "Проблемы вычислений в распределенной среде" / Под ред. А.П. Афанасьева. Т.32 - М.¡Издательство ЛКИ, 2008, с.82-108.

[9] Гринберг Я.Р., Курочкин И.И. «Математическое моделирование последовательного заполнения телекоммуникационных сетей с кластерной топологией.» Т.2: Сборник трудов VII международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» 28-30 апреля 2009, Санкт-Петербург, Россия. Изд-во Политехнического университета, 2009. с.52-53.

[10] Гринберг Я.Р., Курочкин И.И. «Методы оценки математического моделирования по динамическому последовательному заполнению телекоммуникационных сетей потоками связи.» Материалы XVI Международной конференции по механике и современным прикладным программным системам (ВМСППС'2009), 25-31 мая 2009, г.Алушта, Украина. - М.: МАИ-ПРИНТ, 2009г. с.231-233.

[11] Гринберг Я.Р., Курочкин И.И. «Первичные результаты численных экспериментов по динамическому заполнению телекоммуникационных сетей». III международная конференция «Системный анализ и информационные технологии» САИТ-2009, 14-18 сентября 2009, г.Звенигород, Россия. - М.: ПолиПринтСервис, 2009. с. 10

Подписано в печать:

29.04.2010

Заказ № 3677 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

ВВ БДЕНИЕ.

ГЛАВА 1.£

ТЕЛЕКОММУНИКАЦИОННЫЕ СЕТИ.£ локальные и глобальные сети.

ТРЕБОВАНИЯ К СЕТЯМ.

ВЫНУЖДЕННЫЕ УЛУЧШЕНИЯ.

МАРШРУТИЗАЦИЯ.

ПРИНЦИПЫ IP-МАРШРУТИЗАЦИИ.

ОСНОВНЫЕ ПРОТОКОЛЫ МАРШРУТИЗАЦИИ.

ОБ ОСНОВНЫХ ПРИНЦИПАХ ПРОТОКОЛОВ СОСТОЯНИЯ КАНАЛА.

ПРОБЛЕМЫ СОВРЕМЕННЫХ ПРОТОКОЛОВ МАРШРУТИЗАЦИИ.

СЕТИ SDH/SONET.

ОСОБЕННОСТИ ТЕХНОЛОГИИ SDH/SONET.

ВЫВОДЫ.

ГЛАВА 2.

ПОСТАНОВКА ЗАДАЧИ. РАЗЛИЧНЫЕ ВАРИАНТЫ АЛГОРИТМОВ РЕШЕНИЯ.

АЛГОРИТМЫ ПОСЛЕДОВАТЕЛЬНОГО ЗАПОЛНЕНИЯ.

ПРОСТОЙ АЛГОРИТМ.

СУБОПТИМАЛЬНЫЙ МИНИМАЛЬНО-РАЗРЕЗНЫЙ АЛГОРИТМ.

РАВНОМЕРНЫЙ ПО МИНИМАЛЬНЫМРАЗРЕЗАМ АЛГОРИТМ.

РАВНОМЕРНЫЙ ПО ДУГАМ АЛГОРИТМ.

СУБОПТИМАЛЬНЫЙ ДУГОВОЙ АЛГОРИТМ.

ОПТИМАЛЬНЫЙ АЛГОРИТМ.

АДДИТИВНЫЙ МИНИМАЛЬНО-РАЗРЕЗНЫЙ АЛГОРИТМ.

ГИБРИДНЫЙ МИНИМАЛЬНО-РАЗРЕЗНЫЙ АЛГОРИТМ.

ГРУППИРОВКА АЛГОРИТМОВ ПОСЛЕДОВАТЕЛЬНОГО ЗАПОЛНЕНИЯ.

ВЕРОЯТНОСТНАЯ МОДЕЛЬ ПОТОКА ЭЛЕМЕНТАРНЫХ ТРЕБОВАНИЙ.

АЛГОРИТМЫ ПОИСКА НА ГРАФЕ.

ПОИСК В ШИРИНУ.

ПОИСК В ГЛУБИНУ.

АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ.

РЕЛАКСАЦИЯ.

АЛГОРИТМ ДЕЙКСГРЫ.

АЛГОРИТМ БЕЛЛМАНА-ФОРДА.

АЛГОРИТМЫ НАХОЖДЕНИЯ МАКСИМАЛЬНОГО ПОТОКА.

МЕТОД ФОРДА-ФАЛКЕРСОНА.

АЛГОРИТМ ФОРДА-ФАЛКЕРСОНА.

АЛГОРИТМ ЭДМОНДСА-КАРПА.

ОЦЕНКИ СЛОЖНОСТИ АЛГОРИТМОВ НАХОЖДЕНИЯ МАКСИМАЛЬНОГО ПОТОКА

ВЫВОДЫ.

ГЛАВ A3.

МОДЕЛЬ СЕТИ.

ГЕНЕРАЦИЯ СЕТЕЙ С ЗАДАННЫМИ ПАРАМЕТРАМИ.

Приближенные схемы вычислений.

СТРУКТУРА ХРАНЕНИЯ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ.

ВЫВОДЫ.

ГЛАВА 4.

СТАТИЧЕСКОЕ ЗАПОЛНЕНИЕ ТЕЛЕКОММУНИКАЦИОННЫХ СЕТЕЙ.

СТАТИЧЕСКОЕ ЗАПОЛНЕНИЕ СЕТЕЙ СТОХАСТИЧЕСКОЙ ТОПОЛОГИИ.

ХАРАКТЕРИСТИКА ВЫБРАННЫХ СЕТЕЙ СТОХАСТИЧЕСКОЙ ТОПОЛОГИИ.

РЕЗУЛЬТАТЫ МОДЕЛИРОВАНИЯ. ДИНАМИКА ЗАПОЛНЕНИЯ СЕТЕЙ.

РЕЗУЛЬТАТЫ ЗАПОЛНЕНИЯ СЕТЕЙ.

ВЫВОДЫ.

СТАТИЧЕСКОЕ ЗАПОЛНЕНИЕ СЕТЕЙ С ТОПОЛОГИЕЙ КОЛЕСО.

М ОДЕ ЛИР ОВ АНИ Е.

РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТА. простое колесо (1). результаты.

КОЛЕСО С ХОРДАМИ (2). РЕЗУЛЬТАТЫ.

ДВОЙНОЕ КОЛЕСО (3). РЕЗУЛЬТАТЫ.

ДВОЙНОЕ КОЛЕСО С ХОРДАМИ (4). РЕЗУЛЬТАТЫ.

ПЕРИФЕРИЧЕСКОЕ ДВОЙНОЕ КОЛЕСО (5). РЕЗУЛЬТАТЫ.

СИЛЬНОСВЯЗНОЕ ДВОЙНОЕ КОЛЕСО (6). РЕЗУЛЬТАТЫ.

СТАТИЧЕСКОЕ ЗАПОЛНЕНИЕ СЕТЕЙ С ТОПОЛОГИЕЙ СВЯЗНЫЕ КЛАСТЕРЫ.

РЕЗУЛЬТАТЫ МОДЕЛИРОВАНИЯ.

ПЕРВОЕ МНОЖЕСТВО СЕТЕЙ.11 б

ВТОРОЕ МНОЖЕСТВО СЕТЕЙ.

ДИНАМИЧЕСКОЕ ЗАПОЛНЕНИЕ ТЕЛЕКОММУНИКАЦИОННЫХ СЕТЕЙ.

ДИНАМИЧЕСКОЕ ЗАПОЛНЕНИЕ СЕТЕЙ СТОХАСТИЧЕСКОЙ ТОПОЛОГИИ.

РЕЗУЛЬТАТЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ.

ВЫВОДЫ.

Работа посвящена проблемам маршрутизации в телекоммуникационных сетях. Эта проблема рассматривается с двух сторон. Во-первых, в общем контексте сетевых моделей и протоколов передачи данных разных уровней, причем рассматриваются обе эталонные модели - семиуровневая модель 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 алгоритма (простой)

1. Абросимов Л.И., Лукьянчиков А.В. Анализ вероятностно-временных характеристик ЛВС.

2. Басакер Р., Саати Т. Конечные графы и сети. Пер.с англ. М. Наука, 1974. 368 с.

3. Блэк Ю., Сети ЭВМ: протоколы стандарты, интерфейсы.; перев. с англ. М.: Мир, 1990.

4. Борисов М. Новые стандарты высокоскоростных сетей // Открытые системы. 1994. вып.З. С. 20-31.

5. Вишневский В., Гузаков Н., Лаконцев Д. Система "Рапира" базис для отечественных широкополосных беспроводных сетей. - ЭЛЕКТРОНИКА: НТБ,2005, № 1, с.30-34.

6. Вишневский В., Лаконцев Д., Сафонов А., Шпилев С. Mesh-cera: в ожидании стандарта IEEE 802.1 Is. ЭЛЕКТРОНИКА.: НТБ, 2008, №3, с.98-106.

7. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. -М. Техносфера, 2003.

8. Волкова В. Н., Воронков В. А., Денисов А. А. Теория систем и методы системного анализа в управлении и связи / М.: Радио и связь, 1983. 248 с.

9. Герасимов А.И. Аналитические методы исследования и оптимизации вычислительных систем и сетей на основе сетевых моделей массового обслуживания. Москва: Радио и связь, 2001.

10. Труды Института Системного Анализа Российской Академии Наук (ИСА РАН). -Москва: КомКнига, 2006, 224с.

11. Дженнингс Ф., Практическая передача данных: Модемы, сети и протоколы.; перев. с англ. М.: Мир, 1989.

12. Ефимова М.Р., Петрова Е.В., Румянцев В.Н. Общая теория статистики. Учебник. Второе издание, исправленное и дополненное. — Москва: Инфра-М, 2006.

13. Келли-Бутл С. Введение в UNIX / Пер. с англ. М.: Лори, 1995.

14. Корпоративные информационные сети./ Под ред. М.Б.Купермана. Информсвязь, вып. 3, 1997.

15. Крылов В.В., Самохвалова С.С. Теория телетрафика и ее приложения. Санкт-Петербург: БХВ-Петербург, 2005.

16. Кульгин М.В. Коммутация и маршрутизация IP/IPX трафика. М.: КомпьютерПресс, 1998. 320 с.

17. Липский В. Комбинаторика для программистов: Пер. с польск М.: Мир, 1988. -213с. ил.

18. Локальные вычислительные сети: Справочник / Под ред. С.В.Назарова. М.: Финансы и статистика, 1994.

19. Мизин И.А., Богатырев В.А., Кулешов А.П. Сети коммутации пакетов. М.:Радио и связь, 1986.-408 с.

20. Нанс Б. Компьютерные сети / Пер с англ. М.: Бином, 1995.

21. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. СПб: Питер, 2000. 672 с.

22. Остерлох Х„ Маршрутизация в IP-сетях. Принципы, протоколы, настройка. -СПб.: ООО «ДиаСофтЮП», 2002. 512 с.

23. Петраков А.В. Введение в электронную почту. М.: Финансы и статистика, 1993.

24. Протоколы информационно-вычислительных сетей / Под ред. И.А. Мизина, А.П. Кулешова. М: Радио и связь, 1990.

25. Савельев А. Современные протоколы маршрутизации. LAN/ЖУРНАЛ СЕТЕВЫХ РЕШЕНИЙ #12/98, 2000 (www.citforum.ru)

26. Семенов А. Б., Волоконная оптика в локальных и корпоративных сетях связи., АйТи. М.: Компьютер-пресс, 1998.

27. Семёнов Ю.А. (ГНЦ ИТЭФ). Бесклассовая интердоменная маршрутизация (CIDR), book.itep.ru

28. Семенов Ю.А. Протоколы и ресурсы Internet. М.: Радио и связь, 1996.

29. Слепов Н. Н., Синхронные цифровые сети SDH. Н. Н. Слепов. Эко-Трендз, 1998.

30. Спортак Марк А. и др.Высокопроизводительные сети. Энциклопедия пользователя.; перев. с англ. Киев, ДиаСофт, 1998.

31. Таненбаум Э. Компьютерные сети Изд. 3-е. Пер. с англ. — СПб. Питер, 2007. 992 с.

32. ТахаХ. Введение в исследование операций: В 2 кн.: Пер. с англ. М.: Мир, 1985.

33. Тернер Д. Вероятность, статистика и исследование операций: Пер. с англ. М.: Статистика, 1976. 431 с.

34. Томас X. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION ТО ALGORITHMS. — 2-е изд. — М.: «Вильяме», 2006. — С. 1296. — ISBN 0-07013151-1

35. Уилсон Р. Введение в теорию графов: Пер. с англ. М.: Мир, 1977. 207 с.

36. Фейт С. TCP/IP: Архитектура, протоколы, реализация (включая IP версии 6 и IP Securing) 2-е изд. - М.: Лорри, 2000.

37. Филимонов А.Ю. Сети ЭВМ и терекоммуникации. (курс лекций)

38. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей: Пер. с англ. М.: Мир, 1984. 496 с.

39. Форд Л. Р., Фалкерсон Д. Р. Потоки в сетях. М.: Мир, 1966.

40. Фролов А.В., Фролов Г.В. Глобальные сети компьютеров. М.: Диалог-МИФИ, 1996.

41. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1973.

42. Челлис Дж., Перкинс Ч., Стриб М., Основы построения сетей. Учебное руководство для специалистов MCSE.; перевод с англ. Лори, 1997.

43. Шапорев С. Д. Дискретная математика. Курс лекций и практических занятий. Изд.: БХВ-Петербург, ISBN: 5941577036, 2005.

44. Шатт С. Мир компьютерных сетей / Пер. с англ. Киев: BHV, 1996.

45. Шеннон Р. Имитационное моделирование систем искусство и наука: Пер. с англ. М.: Мир, 1978.418 с.

46. Шмалько А.В. Цифровые сети связи: основы планирования и построения. — М.: Эко-Трендз, 2001.

47. Шпилев С. А. Проактивная маршрутизация в IEEE 802.1 Is mesh-сетях. — Третья всероссийская молодежная научная конференция по проблемам управления (ВМКПУ-2008), 2008.

48. Эндрюс Дж., Математическое моделирование: Пер. с англ. / Под ред. Дж. Эндрюса и Р. Мак-Лоуна. М.: Мир, 1979. 278 с.54. www.citforum.ru. Материалы по маршрутизации в IP-сетях и описанию Ethernet.

49. Cheriyan J., Mehlhorn К. An Analysis of the Highest-Level Selection Rule in the Preflow-Push Max-Flow Algorithm.

50. Comer Duglas E., Internetworking with TCP/IP: Principles, Protocols, and Architecture, Prentice Hall, 1995.

51. Cormen Т.Н., Leiserson C.E., Rivest R.L. Introduction to algorithms. 1990.

52. Edmunds. K., Karp R.M. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM, 1972, 19, s. 248-264.

53. Fong С. O, Rao M. R. Accelerated labeling algorithms for the maximal flow problem with applications to transportation and assignment problems Working Paper No. 7222, Graduate School of Management, U. of Rochester, Rochester, N Y , 1972.

54. Galil Z., Naamad A. Network flow and generalized path compression. 1979.

55. Goldberg A. V. Combinatorial Optimization Lecture Notes for CS363/OR349.

56. Goldberg A. V., Rao S. Length functions for flow computations. Technical report #97055, NEC Research Institute, 1997.

57. Goldberg A. V., Tarjan R. E. A New Approach to the Maximum Flow Problem. J. Assoc. Comput. Mach., 35:921-940, 1988.

58. Halsall F. Data Communications, Computer Networks and Open Systems. Addison-Wesley Publ., 1992.

59. Halsall Fred, Data Communications, Computer Networks and Open Systems, Adisson-Wesley, 1996.

60. Hein M., Kemmler W. Bay Networks. Gigabit Ethernet Guide. FOSSIL Verlag GmbH, 1998.

61. Hunt Craig, TCP/IP Network Administration, 2/e, O'Reilly & Associates, 1998.

62. Johnson E L. Networks and basic solutions. Oper. Res. 14 (1966), 619-623.

63. Kurt Mehlhorn, Christian Uhrig. The minimum cut algorithm of Stoer and Wagner 1995.

64. Lin P. M., Leon B. J. Improving the efficiency of labeling algorithms for maximum flow In networks Proc IEEE Int Syrup on Circuits and Systems, 1974, pp 162-166.

65. Mechthild Stoer, Frank Wagner. A Simple Min-Cut Algorithm 1997.

66. Sleator D. D., Tarjan R. E. A Data Structure for Dynamic Trees. J. Comput. System Sci.,26:362-391, 1983.

67. Srinivasan V., Thompson G.L. Accelerated algorithms for labeling and relabeling trees, with applications to distribution problems. J. ACM 19, 4 (Oct. 1972), 712-726.

68. Stallings William, Data and Computer Communications, 5/e,, Prentice Hall, 1997.

69. Stallings William, ISDN and Broadband ISDN with Frame Relay and ATM, 3/e, Prentice Hall, 1995.

70. Wilf B. S. Algorithms and Complexity. Internet edition, summer 1994. http://www/cis.upenn.edu/wilf.

71. IEEE P802.1 ls/D1.08. Amendment: Mesh Networking. IEEE, January 2008.

72. Perkins C., Belding-Royer E., Das S. Ad hoc On-Demand Distance Vector (AODV) Routing. IETF RFC 3561, July 2003.

73. IEEE P802.1 ls/D1.00. Amendment: Mesh Networking. IEEE, November 2006.

74. IEEE P802.1 Is/ D1.06. Amendment: Mesh Networking. IEEE, July 2007.

75. Clausen Т., Jacquet P. Optimized Link State Routing Protocol (OLSR). IETF RFC 3626, October 2003.

76. Qayyum, Laouiti A., Viennot L. Multipoint relaying technique for flooding broad-cast messages in mobile wireless networks. HICSS: Hawai Int. Conference on System Sciences, January 2002.

77. IEEE P802.11s/D1.07. Amendment: Mesh Networking. IEEE, September 2007.

78. Reconsidering RA-OLSR IEEE P802.1 l-07.2547r2, September 2007.

79. Mesh Meeting Agenda September 2007. IEEE P802.1 l-07.2290rl 1, September 2007.

80. Vishnevsky V.M., Gorodov P.V., Shpilev S.A. Performance analisys of RA-OLSR in IEEE 802.1 Is mesh networks. International Workshop. Proc. Of Distributed Computer and Communication Networks (DCCN-2007), 2007, Vol. 1.

81. Schriber T.J. Simulation using GPSS. John Wiley & Sons, 1974.