Введение к работе
Актуальность темы. Рациональное использование ресурсов телекоммуникационных сетей -одна из актуальных задач в связи с постоянным ростом нагрузки на каналы сетей передачи данных. Сети передачи данных являются сложными системами и к анализу такого рода систем надо подходить с системных позиций. В связи с этим необходим системный анализ различных параметров сети, а также выработка новых подходов для прокладки путей. Для использования всех возможностей сетей передачи данных нужна оценка и планирование загрузки каналов передачи данных.
Имитация работы сети - один из распространенных способов оценки возможностей сети передачи данных. Однако подходы к задаче имитации работы сетей могут различаться коренным образом. Многие исследователи берут на вооружение теорию массового обслуживания. При таком подходе можно оценить вероятности загрузки каналов и сети в целом, но нельзя выявить особенности работы алгоритмов прокладки путей (маршрутов).
В диссертации идет речь о подходе к заполнению телекоммуникационных сетей, который основан на применении новых характеристик при выборе каналов связи и использовании аппарата теории потоков. В этом контексте обосновано применение имитационного моделирования, когда прокладываются все маршруты, и в каждый момент времени можно абсолютно точно определить состояние любого канала в сети. Данный подход позволяет отследить различия в организации каналов при использовании нескольких алгоритмов заполнения сети. Использование данного подхода может осуществляться в рамках принятия решения по модификации существующих телекоммуникационных сетей и проектировании новых.
' Далее в тексте термин телекоммуникационные сети равнозначен термину сети передачи данных.
Постановка задачи
Под сетью передачи данных будет подразумевать граф G, каждой дуге которого поставлено в соответствие действительное число, которое мы будем называть пропускной способностью. Вершины графа G делятся на два типа: полюса и промежуточные узлы (или просто узлы). Полюса - это те вершины графа G, между которыми прокладываются пути.
Очевидно, что прокладывание любого нового пути изменяет пропускную способность исходного графа, в свою очередь, прокладка еще одного пути меняет полученный при предыдущей итерации граф. Таким образом, исходный граф динамически меняется до состояния, когда его связность может нарушиться. Описанную выше процедуру прокладки (назначения) путей в динамически меняющемся графе будем называть процедурой заполнения сети или просто заполнением сети. Факт возникновения необходимости очередной прокладки пути будем называть заявкой. Процедуру прокладки пути будем назвать удовлетворением заявки. В случае невозможности проложить путь будем говорить об отказе в обслуживании заявки.
Суть работы заключается в том, чтобы разработать инструментарий, позволяющий наилучшим образом реализовать удовлетворение заявок по критерию наибольшего увеличения общего числа удовлетворенных заявок.
Цель работы и задачи исследования.
Целями диссертации являются:
Разработка методов и программного инструментария максимизирующих общий проведенный поток в сетях передачи данных.
Для достижения поставленных целей в диссертационной работе решены следующие задачи:
Разработка методики анализа сетей передачи данных, выявляющую прямую зависимость загрузки сетей от стратегии маршрутизации.
Разработка эвристических алгоритмов, увеличивающих общую
пропускную способность телекоммуникационных сетей в рамках
задачи о многопродуктовой сетевой модели.
Разработка программного инструментария, реализующего
предложенный подход по заполнению сетей передачи данных, и
позволяющего провести оценку и сравнительный анализ результатов
работы различных алгоритмов последовательного заполнения.
Методы исследования. В диссертационной работе используются методы
математического моделирования, методы теории потоков, теории графов,
теории вероятностей и математической статистики, а также стандарты и
протоколы маршрутизации в 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 наименований), одно приложение.
