Содержание к диссертации
Введение
Глава 1. Принципы построения сетей с использованием технологии MPLS и задачи их оптимизации
1.1 .Определение основных целей и задач исследования. Общие понятия. 12
1.2.Преимущества MPLS 17
1.3. Проблемы распределения трафика и безопасности в сетях MPLS 21
1 4. .Формирование трафика 27
1.5.Управление трафиком 32
1.6. Обеспечение QoS (качество услуг) 39
1.7.0бзор методов оптимизации трафика в IP/MPLS сетях 42
1.8.Выводы 47
Глава 2. Разработка метода распределения многопродуктовых потоков 49
2.1 .Модель для оптимизации 5 О
2.2.Цели оптимизации 53
2.3.Методы оптимизации 55
2.4. Принцип максимального потока (минимального разреза) 56
2.5.Линейное программирование 60
2.6.Эвристический метод определения оптимального дизайна 62
2.7.Сравнение алгоритмов поиска оптимального дизайна 71
2.8.Выводы 74
Глава 3. Оптимизация сетей IP/MPLS с дифференциальным обслуживанием 75
3.1 Формулировка задачи оптимизации 77
3.2 Эвристический алгоритм оптимизации 85
3.3 Метод повторной оптимизации 90 ЗАЧисленный пример 90 3.5.Выводы 98 CLASS Глава 4. Программы для оптимизации распределения потоков трафика в сетях IP/MPLS 99 CLASS
4.1. Описание среды разработки программы 99
4.2. Назначение программы для определения оптимального дизайна LSP 103
4.3. Описание программного модуля для определения оптимального дизайна 104 4.4 Испытания сети IP\MPLS
4.5.Выводы 115
Основные результаты работы 116
Библиографический список литературы
- Проблемы распределения трафика и безопасности в сетях MPLS
- Обеспечение QoS (качество услуг)
- Принцип максимального потока (минимального разреза)
- Назначение программы для определения оптимального дизайна
Введение к работе
Как отмечалось в [57] основным принципом работы протоколов маршрутизации в сетях с коммутацией пакетов, вот уже долгое время является выбор маршрута на основе топологии сети без учета информации о текущей загрузке. Для каждой пары «адрес источника - адрес назначения» такие протоколы выбирают единственный маршрут, не принимая во внимание информационные потоки, протекающие через сеть. В результате все потоки между парами конечных узлов идут по кратчайшему маршруту (в соответствии с некоторой метрикой). Выбранный маршрут может быть более рациональным, например, если в расчет принимается номинальная пропускная способность канала связи или вносимые ими задержки, либо менее рациональным, если учитывается только количество промежуточных маршрутизаторов между исходным и конечным узлами.
Такой подход приводит к тому, что даже если кратчайший путь перегружен, пакеты все равно посылаются по этому пути. Налицо явная ущербность методов распределения ресурсов сети - одни ресурсы работают с перегрузкой, а другие не используют вовсе. Традиционные методы борьбы с перегрузками эту проблему решить не могут, нужны качественно иные механизмы.
С этой целью на сетях связи осуществляется внедрение новых сетевых технологий, таких как, многопротокольная коммутацией по меткам (Multiprotocol Label Switching, MPLS), которая обеспечивает гарантированную среднюю пропускную способность в соответствии с принципами инжиниринга трафика [2-9,12-24,57]. Наряду с этим, необходимо предусмотреть чтобы, сети были спроектированы с учетом необходимых методов оптимизации, которые позволят провайдерам максимально эффективно использовать имеющуюся инфраструктуру.
Поэтому, для более эффективного использования сетевых ресурсов важными являются задачи оптимизации выбора алгоритмов маршрутизации, чтобы обеспечить производительность сети и сбалансировать нагрузку в случае изменения трафика, без необходимости изменения структуры сети и повышения емкости каналов.
Таким образом, необходимость диссертационной работы вызвана разработкой алгоритмов оптимизации сети с MPLS, для перераспределения трафика между LSP и устранения перегрузки работы в сети.
Обзор работ. Задачи, оптимизации при условии, что берется более или менее реальная сеть и оптимизация осуществляется по нескольким параметрам, относятся к классу сложных задач. Их решение с учетом ограничений требует большого объема вычислительных ресурсов и времени на реализацию. Поскольку выбор путей осуществляется в процессе работы сети, поэтому время вычислений оптимальных путей является основополагающим фактором. Вопросом оптимального распределения трафика посвящено множество работ, и задача чаще всего формулируется следующим образом - требуется найти путь, обеспечивающий минимальную стоимость при наличии определенных ограничений. Решению такого рода задач посвящены работы как российских ученых [27-28,40,43,45,48,58-61], так же и зарубежных [1,22,26,29-36,39,41,46,52-56,62-95]. Учитывая актуальность вышеизложенной проблемы, диссертационная работа посвящена исследованиям в этой области и разработке новых более эффективных методов и алгоритмов оптимизации.
Обзор методов оптимизации. Технология MPLS постоянно совершенствуется в направлении адаптации к условиям передачи трафика в сетях, обеспечивая поддержку QoS. В решении этих задач неоценимый вклад внесли такие исследователи как Вишневский В.М., Awduche D.O., Malcolm J.,Agogbua J.,ODell M., McManus J., M.S.Garey, D.S.Johnson, G.Cornuejols, M.L.Fisher, B.Fortz. R.Widyono,H др.
Так Хемди A. Таха рассматривает фундаментальные основы для понимания математического моделирования методов исследования операций в теории массового обслуживания. Вишневский В.М. рассмотрел алгоритмы выбора оптимальных потоков и определения оптимальных маршрутов в сетях передачи данных по критерию средней задержки. R.Widyono, предложил метод, маршрутизации, который позволяет определять оптимальный путь с самой низкой возможной стоимостью без влияния на задержки. Авторы R.Hassin, D.H.Lorenz, F.Orda, Danny Raz,Yuva Shavitt дали полностью полиномиальную схему аппроксимации по времени для проблемы пути с Минимальной Стоимостью и Ограниченной Задержкой. Kenji Ishida, Kitsutaro Amano предложили распределенный алгоритм, в котором узлы всегда выбирают наименьший по стоимости путь, пока не будут выполнены требования по задержке. Далее Shigang Cheng и Klara Nahrstedt, предлагают алгоритм для поиска пути, который удовлетворяет двум требованиям в полиномиальном времени, а Liang Guo и Ibrahim Matta, соответствующий путь, находят основанный на единственной стоимости нескольких метрик с разными коэффициентами веса.
Несмотря на значительную актуальность данной темы и продолжительный период ее изучения, до сих пор остается ряд нерешенных задач.
Анализ работ позволяет сделать вывод, что исследования в данной области требуют дальнейшего развития и, учитывая актуальность вышеизложенной проблемы, диссертационная работа посвящена разработке новых более эффективных алгоритмов оптимизации, на основе эвристик, которые дают приближенное решение поставленных задач.
Формулировка задачи и цель работы. Целью диссертационной работы является разработка алгоритмов оптимизации сети с многопротокольной коммутацией по меткам (Multiprotocol Label Switching, MPLS), обеспечивающих повышение производительности за счет более эффективного распределения ресурсов пропускной способности магистральных каналов связи между набором заданных путей с коммутацией по меткам (Label Switched Path, LSP), перераспределения нагрузки между LSP в условиях изменения трафика в сети. В рамках выше изложенного решаются следующие задачи:
1. Разработка алгоритмов оптимизации процессов, обеспечивающих повышение производительности сетей и адаптацию к трафику без необходимости изменения структуры сети и повышения пропускной способности каналов.
2. Разработка, на основе использования метода неопределенных множителей Лагранжа, алгоритма оптимизации модифицированной функции затрат, которая включает ограничения пропускной способности для каждого класса обслуживания (при предоставлении дифференцированных услуг), а также коэффициенты отказоустойчивости трактов, которые используются для уточнения значений пропускной способности резервных LSP.
3. Разработка программ для автоматизации расчетов по оптимизации распределения потоков трафика.
Методы исследования. В работе для решения задач эффективного использования ресурсов пропускной способности магистральных каналов связи используются методы математического программирования, теория управления трафиком, методы поиска условного экстремума с использованием метода неопределенных множителей Лагранжа и градиентного спуска.
Достоверность результатов подтверждается корректностью постановки задач, применением строгих математических моделей, непротиворечивостью результатов и выводов, моделированием, а также сравнением полученных результатов с известными.
Объект исследования. Объектом исследования являются сети с многопротокольной коммутацией по меткам и их оптимизация.
Научная новизна. В процессе исследования получены следующие результаты:
1. Разработан эвристический алгоритм определения оптимального дизайна LSP в сетях MPLS, позволяющий на каждом итерационном шаге алгоритма распределять многопродуктовый поток. Предлагаемый алгоритм позволяет при значительно меньших затратах времени, чем при линейном программировании, получить приемлемое решение.
2. На основе использования метода неопределенных множителей Лагранжа разработан алгоритм оптимизации поиска LSP. В состав модифицированной функции затрат, используемой для поиска LSP, включены ограничения пропускной способности на каждый класс обслуживания и также коэффициенты отказоустойчивости трактов, которые используются для уточнения значений пропускной способности каждого тракта, с учётом появления неисправностей в LSP.
3. Созданы программы определения оптимального дизайна LSP методами линейного программирования и предлагаемого эвристического, выбора кратчайшего пути с использованием алгоритма Дейкстра, программы расчета коэффициентов отказоустойчивости трактов.
Практическая ценность работы и внедрение результатов исследования. Практическая ценность работы заключается в создании алгоритмов оптимизации маршрутов, обеспечивающих повышение производительности сети, без необходимости изменения структуры сети и повышения пропускной способности каналов, обеспечении оптимального резервирования пропускной способности с учётом коэффициентов отказоустойчивости трактов, а также обеспечении заданного уровня QoS с учётом дифференцированного обслуживания (DiffServ).
Результаты диссертационной работы использованы при постановке курсов лекций по дисциплинам «Системы документальной электросвязи », «Передача дискретных сообщений», «Протоколы компьютерных сетей и сетевые операционные системы» в ГОУ ВПО «СибГУТИ».
Разработанные алгоритмы оптимизации использованы при составлении проекта модернизации мультисервисной сети связи ОАО «Уралсвязьинформ» для оптимизации потоков при изменяющейся нагрузке.
Материалы диссертационной работы вошли: в учебное пособие «Телекоммуникационные системы и сети», том 3. Мультисервисные сети (гл.4. Многопротокольная коммутация по меткам.), в учебное пособие «Технологии глобальных компьютерных сетей»; монографию «Телекоммуникационные сети с многопротокольной коммутацией по меткам. Построение и оптимизация».
Апробация работы. Основные положения работы докладывались на следующих конференциях и семинарах:
1. Научно-практической конференции «Электронная Россия-стратегия развития г. Екатеринбурга и Уральского региона» в рамках выставки URALNET -сетевые технологии и решения, Екатеринбург, Уралэкспоцентр,2003г.
2. Международной научно-практической конференции «Связь-ПРОМ 2004» 1-й Евроазиатский международный форум «Связь-ПРОМЭКСПО 2004», Екатеринбург,2004г.
3. Научно-практической конференции «Электронная Россия - стратегия развития реальной инфраструктуры инфокоммуникаций», Екатеринбург, Уралэкспоцентр, 2004г.
4. Международной научно-практической конференции «Связь-ПРОМ 2005» 2-й Евроазиатский международный форум «Связь-ПРОМЭКСПО 2005», Екатеринбург,2005г.
5. Международной научно-практической конференции «Связь-ПРОМ 2006» 3-й Евроазиатский международный форум «Связь-ПРОМЭКСПО 2006», Екатеринбург,2006г.
6. Международной практической конференции «Современные научные достижения-2006».Белгород.2006г. http://www.rusnauka.com/SND/Tecnic.htm;
7. Российской научно-технической конференции «Информатика и проблемы телекоммуникаций», Новосибирск,2005г.
Основные положения, выносимые на защиту: 1.Эвристический алгоритм определения оптимального дизайна LSP в сетях MPLS;
2.Методика расчета коэффициентов отказоустойчивости трактов, которые используются для уточнения значений пропускной способности резервных LSP; 3.Алгоритм оптимизации маршрутов с учетом ограничений по классам обслуживания потоков трафика, в основу которого положен метод неопределенных множителей Лагранжа;
4.Программы позволяющие, автоматизировать процесс определения оптимального дизайна LSP, выбора кратчайшего пути, программы расчета коэффициентов отказоустойчивости связи.
Публикации. Основные результаты работы были отражены в 16 печатных работах в том числе в монографии и двух учебных пособиях.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы и приложений. Содержит 124 страницы основного текста, 6 таблиц, 27 рисунков, включает в себя 5 приложений на 89 листах. Список литературы составляет 96 наименований.
Краткое содержание работы. В первой главе рассмотрены особенности и способы управления трафиком в сетях с Многопротокольной коммутацией по меткам (Multiprotocol Label Switching, MPLS) и представлены пути совершенствования технологии MPLS, дан обзор методов оптимизации IP/MPLS сетей, сформулированы задачи оптимизации сетей IP/MPLS. Во второй главе рассмотрены существующие подходы к решению задачи определения оптимального дизайна LSP, а также предложен эвристический метод пропорционального распределения потоков, который позволяет получить квазиоптимальный дизайн LSP. Из существующих методов решения задачи оптимизации рассмотрены метод минимального разреза и метод линейного программирования. В третьей главе рассмотрены вопросы выбора оптимальных путей (LSP) с дифференциальным обслуживанием трафика при наличии нескольких ограничений. Решение поставленной задачи предлагается осуществить путем использования метода неопределенных множителей Лагранжа. Задача разбита на две части. В первой решается вопрос, связанный с необходимостью перенаправления потоков при выходе из строя ранее выбранного пути. Это приводит к увеличению нагрузки на резервные пути и, следовательно, к необходимости увеличения пропускной способности «резервных» путей на величину определенную так называемым коэффициентом отказоустойчивости. Во второй части, с учетом результатов полученных в первой, решается задача выбора квазиоптимальных путей.
В четвертой главе представлены программы определения оптимальных путей, позволяющих осуществлять перераспределение потоков трафика в условиях его изменения. Достоинством этих программ является, то что, их можно использовать в автоматическом режиме и нет необходимости вручную выполнять огромное количество вычислений, которые лежат в основе большинства алгоритмов исследования операций. В заключении сформулированы основные результаты, полученные в работе.
Приложение 1 содержит листинг программ для определения оптимального дизайна LSP с использованием симплекс-метода и эвристического метода. Приложение 2 содержит листинг программы реализации алгоритма Dijkstra на языке программирования Pascal. Приложение 3 содержит листинг программы для реализации поиска коэффициентов отказоустойчивости связи с отбрасыванием первого ребра по пути следования пакета. Приложение 4-листинг программы для реализации поиска коэффициентов отказоустойчивости связи с отбрасыванием по очереди всех ребер, входящих в путь предлагаемой топологии сети. Приложение 5- листинг программы для поиска коэффициентов отказоустойчивости связи при случайном выборе узла связи, который «выходит из строя» у(е,).
Проблемы распределения трафика и безопасности в сетях MPLS
Несмотря на то, что технология MPLS достигла значительного прогресса и обеспечивает широкий диапазон функциональных возможностей и приложений, ее реализация связана с большими сложностями. Производители, разрабатывающие технологию MPLS, а также организации, в настоящее время развертывающие MPLS сети, должны также учитывать состояние постоянного развития этой технологии и, ее влияние на производительность, и расширяемость сети [21].
Как было сказано выше, MPLS не является самостоятельной - она накладывается на технологии 2-го уровня, такие как Ethernet или ATM, и должна работать совместно с другими протоколами плоскости управления, такими как протоколы маршрутизации IP. Сложность развертывания MPLS возрастает из-за этого взаимодействия. В некоторых случаях в заданный сетевой сценарий может быть вовлечено четыре или более протоколов, требующих тщательной координации и подтверждения работоспособности сквозной системы. Интеграция традиционных услуг и развертывание новых, таких как VPN, требует туннелирования, которое, в свою очередь, расширяет требования настройки для данной сети [21]. Поэтому, возможность взаимодействия оборудования MPLS в разнородных сетях остается проблемой. Хотя достижения в технологии интегральных схем значительно улучшили характеристики современных маршрутизаторов, сложность MPLS в реальных сетевых приложениях вызывает проблемы с рабочими показателями и расширяемостью сети. Проблемы обычно возникают не в базовой сети MPLS, где данные просто переключаются с использованием меток, а на краю сети, где MPLS должна интегрироваться с не-MPLS сетями, и где инициируются услуги. Из-за объединения сетей загрузка трафика возрастает, и сети должны справляться с дополнительными задачами обработки трафика в реальном времени и трафика с приоритетом. Вот почему основной задачей при построении сетей на основе технологии MPLS остается оптимизация трафика.
Рассматривая более детально архитектуру протокола MPLS необходимо отметить, что в основном некоторые проблемы связаны с обеспечением безопасности при создании сети, а именно с несанкционированным доступом, несовершенной конфигурацией самой сети, атаками внутри сети, подмене меток и т.д.
Архитектура данного протокола обеспечивает защищенность на втором уровне с использованием обычных протоколов типа ATM или Frame Relay.
Базовый принцип защиты основывается на сокрытие структуры ядра MPLS сети. Из соображений безопасности операторы и заказчики обычно не хотят открывать сетевую топологию внешним сторонам. Это значительно снижает вероятность атак на сетевую инфраструктуру. Зная IP-адресацию, потенциальный злоумышленник в состоянии организовать атаку типа отказ в обслуживании направленную против сетей заказчика, или ядра MPLS сети. В общем, атаки на данный протокол (и сети, построенные на базе данного протокола) можно разделить на два типа: - атаки типа отказ в обслуживании (denial-of-service, DoS), - атаки, направленные на взлом самой сети (для получения информации). Учитывая выше сказанное на практике должны быть предприняты многочисленные дополнительные меры безопасности, в основном по фильтрации пакетов.
Для защиты от атак второго вида, существует два базовых типа защиты: усиление защищенности самих протоколов, обеспечивать "невидимость" самой сети как таковой (использование межсетевых экранов и пакетных фильтров).
Для защиты от DoS атак наиболее устойчивый способ защиты - обеспечение "невидимости" самой сети извне (использование межсетевых экранов или трансляции сетевых адресов (NetWork Address Translation,NAT) т.е. маршрутизаторы скрывают детали домашней сети). MPLS распространяет наружу только необходимую информацию, это относится и к VPN клиентам. Адресация ядра MPLS сети может быть выполнена с использованием как частных (RFC 1918), так и публичных адресов. Так как в основном выходной интерфейс VPN сети - потенциально может быть Интернет -здесь работает протокол BGP, то наружу остальную внутреннюю информацию показывать не обязательно. Однако, если между пользовательским маршрутизатором (customer edge, СЕ) и граничным маршрутизатором провайдера (provider edge, РЕ) ядра MPLS сети используется протокол маршрутизации, то может еще и передаваться информация о маршрутах, тогда единственной требуемой информацией является адрес РЕ маршрутизатора. Если требуется этого избежать, то между РЕ и СЕ можно сконфигурировать статическую маршрутизацию. В этом случае ядро MPLS сети может быть полностью скрыто. В случае VPN услуги с одновременным разделяемым доступом в Интернет оператор, обычно, объявляет адресную информацию клиентов, желающих использовать Интернет вышестоящим или одноранговым провайдером. Сокрытие подобной информации может быть организовано с использованием NAT функциональности (трансляции адресов). Оператор в этом случае объявляет только адреса своего пограничного РЕ- маршрутизатора.
В случае использования "чистой" сети на базе MPLS-VPN сервиса, где нет подключения к Интернету, защищенность такая же как и у протоколов ATM/FR. При подключении к сети Интернет, провайдер обязан "открыть" хотя бы один адрес РЕ - маршрутизатора, что может повлечь за собой атаку.
Обеспечение QoS (качество услуг)
Сетевой трафик состоит из множества потоков, сгенерированных приложениями конечных станций. Эти приложения отличаются друг от друга различными требованиями к обслуживанию и к рабочим характеристикам сети. По сути, требование к обслуживанию каждого потока целиком и полностью определяется требованиями сгенерировавшего этот поток приложения. Следовательно, для того чтобы выяснить структуру существующих в сети запросов на качество обслуживания, необходимо определить типы сетевых приложений.
Способность сети обеспечивать различные уровни обслуживания, запрашиваемые теми или иными сетевыми приложениями, наряду с проведением контроля за характеристиками производительности — полосой пропускания, задержкой/дрожанием и потерей пакетов — может быть классифицирована по трем перечисленным ниже категориям.
-Негарантированная доставка данных (best-effort service). Обеспечение связности узлов сети без гарантии времени и самого факта доставки пакета в точку назначения. Следует отметить, что отбрасывание пакета может произойти только в случае переполнения буфера входной или выходной очереди маршрутизатора.
На самом деле негарантированная доставка пакетов не является частью QoS вследствие отсутствия гарантии качества обслуживания и гарантии обеспечения доставки пакетов. Следует отметить, что негарантированная доставка пакетов является на сегодняшний день единственной услугой, поддерживаемой в Internet. -Дифференцированное обслуживание (differentiated service). предполагает разделение трафика на классы на основе требований к качеству обслуживания. Каждый класс трафика дифференцируется и обрабатывается сетью в соответствии с заданными для этого класса механизмами QoS. Подобная схема обеспечения качества обслуживания (QoS) довольно часто называется схемой CoS (Class of Service). Следует отметить, что дифференцированное обслуживание само по себе не предполагает обеспечения гарантий предоставляемых услуг. В соответствии с данной схемой трафик распределяется по классам, каждый из которых имеет свой собственный приоритет. По этой причине дифференцированное обслуживание довольно часто называют мягким QoS (soft QoS).
Дифференцированное обслуживание удобно применять в сетях с интенсивным трафиком приложений. В этом случае важно обеспечить отделение административного трафика сети от всего остального трафика и назначить ему приоритет, позволяющий в любой момент времени быть уверенным в связности узлов сети.
-Гарантированное обслуживание (guaranteed service). Гарантированное обслуживание предполагает резервирование сетевых ресурсов с целью удовлетворения специфических требований к обслуживанию со стороны потоков трафика.
В соответствии с гарантированным обслуживанием выполняется предварительное резервирование сетевых ресурсов по всей траектории движения трафика.
Гарантированное обслуживание довольно часто называют еще жестким QoS (hard QoS) в связи с предъявлением строгих требований к ресурсам сети.
Таким образом, качество услуг (Quality of Service, QoS) - концепция, обеспечивающая выделение сетевых ресурсов, необходимых для работы приложения. QoS - суммарный эффект характеристик обслуживания, определяющий степень удовлетворения пользователя обслуживанием (рекомендация G.106).
Обеспечение требуемого качества услуги достигается следующими методами: -поддержкой определенной полосы пропускания; -сокращением вероятности потери кадров; -исключением или управляемостью сетевых перегрузок; -возможностью конфигурирования сетевого трафика; -установкой количественных характеристик трафика по пути через сеть.
Рекомендации IEFT определяют два вида уровней услуг: -интегрированные услуги (Integration Services, IntServ); -дифференцированные услуги (Differentiated Services, DiffServ).
Интегрированные услуги расширяют модель IP - сети, поддерживая представление гарантируемой полосы пропускания определенным потокам.
Модель с предоставлением IntServ была разработана для того, чтобы оптимизировать сеть при использовании ее ресурсов новыми приложениями, например, мультимедийными в реальном времени, которые требуют QoS.
Модель Internet с предоставлением интегрированных услуг была определена рабочей группой IETF. В эту модель включены способ передачи с «максимальным усилием» и новый вид обслуживания трафика в реальном времени, который обеспечивает резервирование полосы пропускания в Internet.
Механизмы предоставления дифференцированных услуг размещают различные сервисные уровни между различными группами пользователей сети Internet. Это означает, что общий трафик разбивают на группы и предоставляют этим группам различные параметры QoS. DiffServ предлагает передачу трафика с предсказуемыми параметрами (задержкой, пропускной способностью, потерями пакетов и т.д.).
Различие между предоставлением интегрированных услуг и дифференцированных услуг в том, что при предоставлении DiffServ обеспечивается масштабируемое сервисное разделение без необходимости выделения потоков и проведения сигнализации при каждом переходе. Поэтому нет необходимости проводить уникальное резервирование параметров QoS для каждого потока. При работе с DiffServ трафик Internet разбивают на различные классы с различными требованиями к QoS [6].
Принцип максимального потока (минимального разреза)
Принцип максимального потока (минимального разреза) можно использовать для нахождения минимального разреза в сети. Сумма пропускных способностей линий-рёбер на определенном разрезе ограничивает максимально допустимую величину передаваемого потока Ts =ЛШХТ = (AmsatIJ). Принцип работы алгоритма по нахождению "узкого места" основан на определении минимального разреза. Многопродуктовый поток в сети максимален только тогда, когда: -пропускные способности подмножества рёбер (т.е. разреза) полностью исчерпаны отдельными потоками между источниками и потребителями многопродуктового потока; -после удаления полностью загруженных линий-рёбер (разреза) из графа (сети) остаточный граф больше не является связанным.
Минимальный разрез ограничивает максимально возможное значение потока при прочих равных постоянных условиях: топология, пропускная способность, требования на распределение потоков. В одной отдельно взятой сети может существовать несколько таких разрезов.
Разрез s = (Vg,Vz) делит условно все узлы сети на подмножество вершин-истоков VQ С V и комплементарное ему подмножество вершин-стоков VZ=V- VQ, так что каждая вершина принадлежит одному из подмножеств: либо подмножеству вершин-истоков, либо подмножеству вершин-стоков. При этом разрез состоит из множества рёбер E(VQ,VZ), начинающихся (оканчивающихся) в подмножестве VQ, либо оканчивающихся (начинающихся) в подмножестве Vz и определяется, как: E(VQ,Vz) = {eeE:h(e)eVz&t(e)eVQ} Можно определить сумму всех требований на распределение потока, которые обязательно должны занять ("застолбить") пропускную способность на разрезе:
Пропускная способность разреза определяется суммой пропускных способностей рёбер, принадлежащих ему: eeE{VQ,Vz)
Одна из возможностей для нахождения минимального разреза состоит в том, чтобы поочередно исследовать все 2N возможных разбиений множества вершин на два комплиментарных множества (вершин-истоков и вершин-стоков), причем для каждого разбиения и соответствующего разреза определяется отношение Rs суммы всех требований Ts к доступной пропускной способности Cs: _ Ts _ кеУд ПеУг 5 С, с(е) eeE(Vg,Vz)
Заданные в трафик-матрице потоки могут быть переданы через сеть, только если выполняется условие RS=TS/CS 1 или Ть Cs для всех возможных разрезов.
В противном случае сеть может пропустить только часть требований T = (tv), которая определяется коэффициентом А для трафик-матрицы Ts=AxT = (Axt0) из соотношения: , 1 Q Атах = = mm — . max maxRs vs т
Алгоритм по вычислению "узкого места" показывает, на сколько может быть увеличен трафик, пока пропускная способность линий-рёбер "узкого места" не будет исчерпана максимальным многопродуктовым потоком. В качестве результатов метод дает информацию о том, где и при каком значении трафика, передаваемого по сети, ресурсы сети будут перегружены. Эти данные могут быть успешно использованы для планирования топологии сетей, в особенности для оценки влияния изменений структуры сети на "узкие места" и для проверки определенного дизайна LSP, например, на всевозможные варианты "отказов" линий.
При использовании принципа "узкого места" необходимо учитывать, что максимально возможное в действительности значение коэффициента Я тах не всегда может достигнуть порогового значения А , найденного с помощью принципа максимального потока (минимального разреза), таким образом, в общем случае справедливо неравенство: Я аш Лпах = mill Cs/Ts . VS
Если, например, для всех требований на распределение недостаточно имеющейся пропускной способности внутри соответствующего подмножества вершин-истоков или вершин-стоков потока, то необходимо будет занимать часть пропускной способности разреза. Вследствие этого не всегда достигается верхняя граница, вычисляемая данным алгоритмом.
Рассмотрим пример графа, приведенного на рис.2.1. с матрицей пропускных способностей сАВ = сВА = свс = ссв = сАС = сСА = 1 и матрицей требований на распределение потоков tAB =tBC=tCA=\.
Вычисление согласно принципу максимального потока (минимального разреза) приведено в таблице 2.1. Как можно видеть, граф имеет шесть минимальных разрезов с коэффициентом Ятах =2.
Для 2" возможных разбиений узлов-вершин находятся сумма требований на распределение потока Ts и суммарная пропускная способность рёбер Сь, соединяющих вершины истоки с вершинами стоками. Все разбиения исследуются последовательно друг за другом, так что одно разбиение от следующего отличается в среднем только сменой двух вершин между подмножеством вершин-истоков VQ И подмножеством вершин-стоков Vz.
Назначение программы для определения оптимального дизайна
Программа разработана для оптимизации распределения трафика. Она позволяет выполнить линейное программирование с использованием симплекс-метода и рассчитать пропускную способность и стоимостные коэффициенты нагрузки на каждый LSP с использованием эвристического метода. Программа позволяет детально исследовать данные методы и практически проработать. Достоинством этой программы является, то что, ее можно использовать в автоматическом режиме и нет необходимости вручную выполнять огромное количество вычислений, которые лежат в основе большинства алгоритмов исследования операций.
Программа является самодостаточной системой, в том смысле, что все инструкции и пояснения необходимые для работы с этой программой, заключены в названиях пунктов меню, командных кнопок, опций и других элементов управления.
Программой предусмотрено (см.приложение 1.): - определение структуры сети: с использованием матрицы каналов по пропускной способности, коэффициенты стоимости; - матрицы весов; - трафик матрицы определяющей нагрузку на ребра сети; - матрицы потоков, для определения типа потока с учетом пропускной способности и стоимости а также с учетом Quality of Service. Генерация структуры сети и трафик матрицы осуществляется случайным образом.
Перед тем, как приступить к описанию программного модуля, необходимо отметить некоторые особенности программирования в Delphi. В Delphi 7.О., как уже упоминалось, используется язык программирования Паскаль. Паскаль является процедурным языком программирования. Это значит, что для решения какой-то части задачи используется отдельный блок программы, который вызывается по мере необходимости. Замечательное его свойство заключается в том, что его можно вызывать многократно и передавать ему разные входные данные. Такой блок называется процедурой.
В Delphi также введено понятие модуля. Модуль - это набор функционально объединенных процедур и функций. Различают модули программные и модули формы. Модули формы - отвечают за работу одного из окон приложения. Программный модуль предназначен только для обработки каких-либо задач.
Разработанная программа состоит из двух алгоритмов:
1.Алгоритм симплекс-метод находит оптимальное решение, рассматривая ограниченное количество допустимых базисных решений. Решение симплекс -метода лежит через описание кратчайших точек, пространственных решений.
Для этого, сначала необходимо преобразовать неравенство ограничений в равенство путем введения дополнительных переменных.
Основное свойство симплекс-методов состоит в том, что задачи линейного программирования осуществляется итерационно. На каждой итерации алгоритм переходит к новой угловой точке, которая потенциально может улучшить значение целевой функции. Этот процесс перехода от одной угловой точки к следующей заканчивается, когда дальнейшее улучшение значений целевой функции невозможно.
Процесс реализации симплекс-метода включает большое количество однотипных, громоздких и утомительных вычислений. Это делает компьютер незаменимым инструментом для решения задач линейного программирования, поскольку вычислительный алгоритм симплекс-метода позволяет сравнительно легко автоматизировать вычисления.
2. Эвристический метод, обеспечивает быстрое изменение дизайна LSP и выбор оптимального дизайна LSP.
Предлагаемый программой алгоритм рассматривает не каждое отдельно взятое требование в отдельности на распределение потоков, а все одновременно, определяемые в трафик-матрице. Выбор кратчайшего пути, осуществляется с использованием алгоритма Дейкстра. Выбор оптимального пути определяется на основе пропускной способности и весовых коэффициентов, а нагрузка определена в трафик - матрице, на каждые ребра сети.
Таким образом, программа составлена из четырех матриц (рис. 4.3.): -Матрицы пропускной способности (Bandwidth matrix); -матрицы весов (Cast matrix); -трафик -матрицы (Traffic matrix); -матрицы определения оптимального дизайна LSP (Optimal LSP Design).
Кроме того, интерфейсом предусмотрены, опции для управления режимами алгоритмов. Результаты исследований можно сохранить в памяти или на твердой копии, для этого в меню Файл предусмотрены соответствующие опции.
