Разработка и исследование алгоритмов оптимизации сетей с многопротокольной коммутацией по меткам тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат технических наук Будылдина, Надежда Вениаминовна

• Будылдина, Надежда Вениаминовна
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Будылдина, Надежда Вениаминовна

Введение

Глава 1. Принципы построения сетей с использованием технологии 12 MPLS и задачи их оптимизации

1.1 .Определение основных целей и задач исследования. Общие понятия.

1 ^.Преимущества MPLS

1.3 .Проблемы распределения трафика и безопасности в сетях MPLS

1.4.Формирование трафика

1.5.Управление трафиком

1.6. Обеспечение QoS (качество услуг) 39 1.7.0бзор методов оптимизации трафика в IP/MPLS сетях 42 1.8.Выводы

Глава 2. Разработка метода распределения многопродуктовых потоков 49 2.1 .Модель для оптимизации 5 О

2.2.Цели оптимизации

2.3.Методы оптимизации

2.4.Принцип максимального потока (минимального разреза)

2.5.Линейное программирование 60 2.6.Эвристический метод определения оптимального дизайна

2.7.Сравнение алгоритмов поиска оптимального дизайна

2.8.Выводы

Глава 3. Оптимизация сетей IP/MPLS с дифференциальным обслуживанием

3.1 Формулировка задачи оптимизации

3.2 Эвристический алгоритм оптимизации

3.3 Метод повторной оптимизации 90 3.4.Численный пример 90 3.5.Выводы

Глава 4. Программы для оптимизации распределения потоков трафика в сетях IP/MPLS

4.1. Описание среды разработки программы

4.2. Назначение программы для определения оптимального дизайна LSP

4.3. Описание программного модуля для определения оптимального дизайна 104 4.4 Испытания сети IP\MPLS 110 4.5.Выводы 115 Основные результаты работы 116 Библиографический список литературы 117 Приложения

Введение диссертации (часть автореферата) на тему «Разработка и исследование алгоритмов оптимизации сетей с многопротокольной коммутацией по меткам»

Как отмечалось в [57] основным принципом работы протоколов маршрутизации в сетях с коммутацией пакетов, вот уже долгое время является выбор маршрута на основе топологии сети без учета информации о текущей загрузке. Для каждой пары «адрес источника - адрес назначения» такие протоколы выбирают единственный маршрут, не принимая во внимание информационные потоки, протекающие через сеть. В результате все потоки между парами конечных узлов идут по кратчайшему маршруту (в соответствии с некоторой метрикой). Выбранный маршрут может быть более рациональным, например, если в расчет принимается номинальная пропускная способность канала связи или вносимые ими задержки, либо менее рациональным, если учитывается только количество промежуточных маршрутизаторов между исходным и конечным узлами.

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

С этой целью на сетях связи осуществляется внедрение новых сетевых технологий, таких как, многопротокольная коммутацией по меткам (Multiprotocol Label Switching, MPLS), которая обеспечивает гарантированную среднюю пропускную способность в соответствии с принципами инжиниринга трафика [29,12-24,57]. Наряду с этим, необходимо предусмотреть чтобы, сети были спроектированы с учетом необходимых методов оптимизации, которые позволят провайдерам максимально эффективно использовать имеющуюся инфраструктуру.

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

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

Обзор работ. Задачи, оптимизации при условии, что берется более или менее реальная сеть и оптимизация осуществляется по нескольким параметрам, относятся к классу сложных задач. Их решение с учетом ограничений требует большого объема вычислительных ресурсов и времени на реализацию. Поскольку выбор путей осуществляется в процессе работы сети, поэтому время вычислений оптимальных путей является основополагающим фактором. Вопросом оптимального распределения трафика посвящено множество работ, и задача чаще всего формулируется следующим образом - требуется найти путь, обеспечивающий минимальную стоимость при наличии определенных ограничений. Решению такого рода задач посвящены работы как российских ученых [27-28,40,43,45,48,58-61], так же и зарубежных [1,22,26,29-36,39,41,46,5256,62-95]. Учитывая актуальность вышеизложенной проблемы, диссертационная работа посвящена исследованиям в этой области и разработке новых более эффективных методов и алгоритмов оптимизации.

Обзор методов оптимизации. Технология MPLS постоянно совершенствуется в направлении адаптации к условиям передачи трафика в сетях, обеспечивая поддержку QoS. В решении этих задач неоценимый вклад внесли такие исследователи как Вишневский В.М., Awduche D.O., Malcolm J.,Agogbua J.,О Dell M., McManus J., M.S.Garey, D.SJohnson, 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», Екатеринбург^006г.

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 наименований.

Заключение диссертации по теме «Системы, сети и устройства телекоммуникаций», Будылдина, Надежда Вениаминовна

Основные результаты работы

1. Рассмотрены алгоритмы оптимизации сетей MPLS и существующие подходы к решению задачи оптимизации (определения оптимального дизайна LSP), а также предложен эвристический метод пропорционального распределения потоков, который позволяет получить квазиоптимальный дизайн LSP.

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

3.Разработаны программы, которые позволяют автоматизировать процесс оптимизации распределения потоков трафика с использованием симплекс-метода и эвристического метода. Эти программы могут быть использованы в LSR.

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

5.Созданы программы для выбора кратчайшего пути на основе алгоритма Дейкстра и для расчетов коэффициентов отказоустойчивости связи.

Список литературы диссертационного исследования кандидат технических наук Будылдина, Надежда Вениаминовна, 2006 год

1. Hakim Badis, Khaldoun А1 Agha. "A Distributed Algorithm for Multiple-Metric Link State QoS Routing Problem", Globecom 2003.

2. Шринивас Вегешна. "Качество обслуживания в сетях IP". Пер.с англ.-Москва, Санкт-Петербург, Киев, 2003.

3. Столингс В. "Современные компьютерные сети". Пер.с англ.- Москва, Санкт-Петербург, Нижний Новгород, Воронеж, Ростов-на-Дону, Екатеринбург, Самара, Киев, Харьков, Минск; Изд.-во «Питер», 2003.

4. Лукацкий А.С. "Неизвестная VPN", Компьютер Пресс. № 10.-октябрь,2001.

5. Олифер В.Г., Олифер Н.А. "Виртуальные частные сети на основе MPLS", Журнал сетевых решений LAN. № З.-март 2002.

6. Mannie Е. (ed.). "Generalized Multi-Protocol Label Switching Architecture", IETF Internet Draft, work in progress, draft-ietf-ccamp-gmplsarchitecture-07.txt, May 2003.

7. Kompella K. et al. "Routing Extensions in Support of Generalized MPLS", IETF Internet Draft, work in progress, draft-ietf-ccamp-gmpls-routing-09.txt.- October 2003.

8. Berger L. (Ed.). "Generalized Multi-Protocol Label Switching (GMPLS) Signaling Functional Specification", IETF Request for Comments, RFC 3471. -January 2003.

9. Rousseau B. and Papadimitriou D. "GMPLS. The Telecommunication holy grail or pragmatic means of raising carrier profitability? " Alcatel strategy White Paper, 2003.

10. Interfaces for the Optical Transport Network (OTN), ITU-T G.709,2003.

11. Алленов O.M. "Технология GMPLS: методы защиты и восстановления. Вестник связи. № 9.-сентябрь 2002.

12. Гольдштейн А.Б.,Гольдштейн Б.С. "Технология и протоколы MPLS", BHV, «БХВ-Санкт-Петербург»,2005.13. http://zxcv.stsland.ru/200 l05multiservice/index.htm

13. Дж.Ирвин, Д.Харль, "Передача данных в сетях: Инженерный подход". Учебное пособие. Пер.с англ.- «БХВ- Санкт-Петербург»,2003.

14. Олифер В., Олифер Н., Петрусов. Д., "ATM и MPLS: враги или союзники? ". Журнал сетевых решений LAN.№12.- декабрь 2002.

15. Марка Лассерре, "Межсоединение локальных сетей посредством MPLS", Журнал сетевых решений LAN. №1.-январь 2004.

16. Величко В.В., Субботин Е.А., Шувалов В.П., Ярославцев А.Ф., "Телекоммуникационные системы и сети т.З. Мультисервисные сети". Учебное пособие. М.: Горячая линия Телеком, 2005.

17. Сергей Орлов. "Перекресток миров". Журнал сетевых решений LAN.№5.-май 2004.

18. Будылдина Н.В, Шувалов В.П. "Телекоммуникационные сети с многопротокольной коммутацией по меткам". Построение и оптимизация. Монография. М.: УрТИСИ ГОУ ВПО СибГУТИ, 2005.

19. E.Rosen. RFC 2702. "Multiprotocl Label Switching Architecture".- September 2000.

20. SYRUS SYSTEMS-MPLS/ "Аттестационные и эксплуатационные испытания", http://www.syrus.ru/index.cgi

21. Awduche D.O., Malcolm J.,Agogbua J.,ODell M., McManus J., RFC "Requirements for Traffic Engineering over MPLS".//IFTF Draft,drifi-ietf-mpls-traffic-eng-00.txt. October 1998.

22. Соболев Д.В. "Защищенная телекоммуникационная сеть оператора связи на базе технологии IP-MPLS для построения корпоративной сети". Аналитический информационный журнал. Документальная электросвязь. №13.-август 2004.

23. Захватов М.А. "Вопросы безопасности в VPLS сетях". Аналитический информационный журнал. Документальная электросвязь.№ 13.-август 2004.

24. Нормативная рекомендация RFC 1918- частное адресное пространство.2000.

25. Alpar Juttner, Balazs Szviatovszki, Ildiko Mecs, Zsolt Rajk. "Lagrange Relaxation Based Method for the QoS Routing Problem", IEEE INFOCOM 2001.

26. Вишневский В.М., Ливнер Е.В., Федотов Е.В. "Математические модели исследования алгоритмов маршрутизации в сетях передачи данных".Информационные процессы,- Том 1, №2, 2001.

27. Поляк Б.Т. "Введение в оптимизацию".- М: Наука, 1983.

28. Kehang Wu and Douglas S. "Reeves Link Dimensioning and LSP Optimization for MPLS Networks Supporting DiffServ EF and BE traffic classes",2004.

29. Alpar Juttner, Balazs Szviatovszki,Aron Szentesi, Daniel Orincsay, Janos Harmatos "On-demand optimization of label switched paths in MPLS networks", IEEE 2000.

30. A. Feldmann and J. Rexford, "IP Network Configuration for Intradomain Traffic Engineering," IEEE Network, vol. 15, no. 5, pp. 46-57, September/ October 2001.

31. Christofides, N.: "Graph Theoriy- An Algorithmic Approach". New York: Academic Press, 1975

32. Franzke, Martin; Haftlinger, Gerhard; Schnitter, Stefan: "Performance and Applicability of MPLS-based Traffic Engineering Methods",2002.

33. Haftlinger, Gerhard; Schnitter, Stefan: "Optimized Traffic Load Distribution in MPLS Networks". In: Telecommunications Network Design and Management, Kluwer Akad. Publ, 2002.

34. Neuman, Klaus; Morlock, Martin: "Operations Research". Miinchen Wien: Carl HanserVerlag, 1993.

35. Э. Майника "Алгоритмы оптимизации на сетях и графах". М.: Наука, 1981.37. http://program.rin.ru/razdel/html/973.html "Оценка времени исполнения".38. http://algolist.manual.ru/maths/graphs/shortpath/ "Задача о кратчайших путях".

36. Haftlinger, Gerhard; Schnitter, Stefan: "Impact of Traffic Characteristics and Engineering on QoS in MPLS-based IP platforms", 2002.

37. Вишневский B.M. "Теоретические основы проектирования компьютерных сетей". М.: Техносфера,2003.

38. Мину М. "Математическое программирование. Теория и алгоритмы". Пер.с фр.-М.: Наука, 1990.

39. Fratta L., Gerla M., Kleinrock L. "The Flow Deviation Method: An Approach to Store-and-Forward Communication Networks", vol.3, 1973.

40. Тихомиров B.M. "Рассказы о максимумах и минимумах". М.: «Наука» Главная редакция физико-математической науки, 1986.44. http://www.opu.Odessa.ua/konsp/MMXTP/RAZDEL5/glava53 .htm.

41. Краснов M.JI и др. "Вариационное исчисление". Избранные главы высшей математики для инженеров и студентов Вузов. М.: «Наука», 1973.

42. Хемди А.Таха "Введение в исследование операций". Пер.с англ.-Издательский дом «Вильяме». Москва-Санкт-Петербург-Киев,2005.

43. Кристофидес Н. "Теория графов. Алгоритмический подход": Пер.с англ. -М.:, Мир, 1978.

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

45. Олифер В., Олифер Н. "Новые технологии и оборудование 1Р-сетей".-СПб.,2000.

46. Шварц М. "Сети ЭВМ. Анализ и проектирование": Пер.с англ.-М.: Радио и связь, 1981.

47. Вивек Олвейн, CCIE™. "Структура и реализация современной технологии MPLS". Пер.с англ.- Издательский дом «Вильяме». Москва-Санкт-Петербург-Киев,2004.

48. М. L. Fisher "The Lagragian Relaxation Method for Solving Integer Problems, Management Science", vol. 27, no.l, pp. 1-18, January 1981.

49. R. K. Ahulja, T. L. Magananty, and J. B. Orlin Network Flows: "Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, New Jersey", 1993.

50. B.Fortz and M.Thorup, "Internet Traffic Engineering by Optimizing /OSPF/ Weights" in Proceedings oflEEEINFOCOM'OO, Israel, 2000.

51. G. Cornuejols, M. L. Fisher, and G. L. Nemhauser, "Location of Bank Accounts to Optimize Float": An Analytic Study of Exact and Approximate Algorithms, Management Science, vol. 23, no. 8, April 1977.

52. F.Le Faucheur, "Rassian Dolls Bandwidth Constraints Model for Diff-servware MPLS Traffic Engineering", IETF Internet Draft, Work in Progress, March 2004.

53. Олифер В.Г., Олифер Н.А., "Компьютерные сети". Принципы, технологии, протоколы. -3-е издание.- Питер,2006.

54. Зайченко Ю.П. "Задачи проектирования структуры распределенных вычислительных сетей". Автоматика, 1981,№3, с.35-44.59. .Федотов Е.В. "Определение оптимальных маршрутов в сети пакетной коммутации". В сборнике. Сетевая обработка информации. М.:МДНТП,1990.

55. Зайченко Ю.П., Гонта Ю.В. "Структура и оптимизация сетей ЭВМ".-Киев: Техника, 1986.

56. Бочаров П.П. "Сеть массового обслуживания с сигналами со случайной задержкой"// Автоматика и телемеханика. №9 -сентябрь 2002.

57. M.S.Garey, D.S.Johnson, "Computers and Intractability": Guaide to the Theory of NP-Completeness'W.H.Freeman, New York, 1979.

58. R.Widyono, "The design and evaluation of routing algorithms for realtimechannels".Technical Report TR-94-024,University of California at Berkeley',June 1994.

59. L. Georgiadis, R. Guerin, V. Peris and R. Rajan, "Efficient Support of Delay and Rate Guarantees in an Internet", IBM T.J.Watson Research Center, 1999.

60. A.K. Parekh and R.G. Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks The Multiple Node Case", IEEE/ACM Transactions on Networking, 1(3): June 1993.

61. A.K. Parekh and R.G. Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks The Multiple Node Case", IEEE/ACM Transactions on Networking, 2(2):137-150, April 1994.

62. R. Szab.o, P. Barta, J. B.r.o, F. N.emeth, C-G. Perntz, "Non Rate-Proportional Weighting of Generalized Processor Sharing Schedulers" GLOBECOM'99, December 1999.

63. R. L. Cruz, "A Calculus for Network Delay", IEEE Transactions on Information Theory, vol.37, no. 1, pp.114-141, January 1991.

64. S. Rampal, R. Guerin, "Flow Grouping For Reducing reservation Requirements for Guaranteed Delay Service", July 1997

65. Stefan Savage, Andy Collins, Eric Hoffman, Thomas Anderson, 'The End-to-End Effects of Internet Path Selection"ACM SIGCOMM '99. September 3,1999.

66. Roch A. Guerin, et al., "QoS Routing mechanisms and OSPF Extensions", Internet Engineering Task Force, Internet Draft, December 1998, (Work in Progress).

67. Guerin Roch A.; Orda Ariel, "QoS routing in networks with inaccurate information: theory and algorithms" IEEE/ACM-Transactions-on-Networking. vol.7, no.3; June 1999.

68. G. Apostolopoulos, R. Gu.erin and S. Kamat, "Implementation and Performance measurements of QoS routing extensions to OSPF" in Proceedings of INFOCOM'1999, New York, March 1999.

69. S. Shenker, C. Partridge, R. Gu.erin, "Specification of guaranteed quality of service" Request For Comments (Proposed Standard) RFC2212, Internet Engineering Task Force, September 1997.

70. Zheng Wang and Jon Crowcroft, "Bandwidth-Delay based routing algorithms", IEEE GlobeCom'95, Singapore, November 1995.

71. Funda Ergun, Rakesh Sinha, Lisa Zhang, "QoS Routing with Performance-Dependent Costs" IEEE INFOCOM'2000 , March 2000.

72. Hussein F. Salama, Douglas S. Reeves and Yannis Viniotis, "A Distributed Algorithm for Delay-Constrained Unicast Routing", IEEE INFOCOM'97, Kobe, Japan, April 1997.

73. W.C.Lee, et al. "Multi-Criteria Routing subject to Resource and Performance Constraints", ATM Forum 94-0280, March 1994.

74. C. Pornavalai, G. Chakraborty and N. Shiratori, "Routing with multiple QoS requirements for supporting multimedia applications", Journal of High Speed Networks, 1998.

75. Kenji Ishida and Kitsutaro Amano, "A Delay-Constrained Least-Cost Path Routing Protocol and the Synthesis Method", IEEE 1998.

76. Shigang Cheng and Klara Nahrstedt, "On finding multi-constrained paths" ICC'98, Atlanta, Georgia, 1998.

77. Jeffrey Jaffe, "Algorithms for finding path with multiple constraints", Networks, vol. 14, pp.95-116,1984.

78. David Blokh and George Gutin, "An approximation algorithm for combinatorial optimization problems with two parameters", 1995.

79. Ravindra K. Ahuja, Tomas L. Magnanti and James B. Orlin, "Network Flows" PRENTICE HALL, Upper Saddle River, New Jersey 07458,1993.

80. H. de Neve, P. van Mieghem, "A multiple quality of service routing algorithm for PNNI", IEEE ATM'98 Workshop, pp.306-314, Fairfax, Virginia, May 1998.

81. Liang Guo and Ibrahim Matta, "Search Space Reduction in QoS Routing" Technical Report NU-CCS-98-09, October 1998.

82. Atsushi Iwata, et al. "ATMRouting Algorithms with Multiple QoS Requirements for Multimedia Internetworking", IEICE Trans. Commun., vol.E79-B, August 1996.

83. M. Held and R. Karp, "The traveling salesman problem and minimum spanning trees", Operations Research 18, pp.l 138-1162, 1970.

84. M. Held and R. Karp, "The traveling salesman problem and minimum spanning trees, Part II. ", Mathematical Programming 6,1971.

85. R. Hassin, "Approximation schemes for the restricted shortest path problem", Mathematics of Operations Research, 17(1): Feb 1992.

86. D.H. Lorenz and A. Orda, "QoS routing in networks with uncertain parameters", IEEE/ACM Transactions on Networking, 6(6), Dec 1998.

87. Danny Raz and Yuval Shavitt, "Optimal Partition of QoS requirements with Discrete Cost Functions", INFOCOM 2000 .

88. Dean H. Lorenz, Ariel Orda, Danny Raz, and Yuval Shavitt, "Efficient QoS Partition and Routing of Unicast and Multicast", IW QoS 2000, June 2000.

89. J. Boyle et al., "Applicability Statement for Traffic Engineering with MPLS", IETF, RFC 3346, August 2002.

90. Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, Alg, StdCtrls, Menus, Grids, ExtCtrls, Simplex, Spin, ComCtrls, TeEngine, Series, TeeProcs, Chart, jpeg; type

91. Private declarations} public1. Public declarations} end;const MAXCOST=32768;

92. WeightPlus=l; //------------//

93. WeightMinus= 1; // — Веса — // WeightMoves= 1; II Операций - //

94. WeightCompare=l; //------------//var frmMain: TfrmMain;

95. Net:TNet; // — Структура сети-------//

96. Traffic:TTraffic; // ~ Трафик-матрица-------//

97. Count: integer; //-- Размерность матриц —II Thread:THandle; // — ID трэда выполнения ~ //

98. TotalCount : Longword; //-----------------------//

99. CountPlus : Longword; //-----------------------//

100. CountMinus : Int64; // -- Счетчики операций ~ //

101. CountMoves : Longword; //-----------------------//

102. CountCompare : Longword; //-----------------------//

103. Count:=5; //Размер матриц по умолчанию 5x5btSetClick(frmMain); //Применение размеров1. Chartl .Visible:=false;1. Chart2.Visible:=false;

104. AssignFile(F,,simplex.opc');1. Reset(F);

105. Read(F,SimplexCompareVector); CloseFile(F);

106. AssignFile(F,'heuristic.opc'); Reset(F);

107. Read(F,HeuristicCompare Vector); CloseFile(F); end;---------------------------------//1. — Трэд симплексного алгоритма ~ // И.---------------------------------Цprocedure SimplexPart; var

108. CountResult; // ~ Записывается показания счетчиков после выполнения симплекса ~ // OperationCompareVectorf 1 . :=TotalCount;

109. SimplexCompareVectorcount.:=(SimplexCompareVector[count]+OperationCompareV ector[l]) div 2;

110. SimplexCompareVectorcount+20. :=SimplexCompareVector[count+20]+1; SimplexCompareVector[]:=(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ,0,0,0,0,0,0,0,0);

111. SimplexCompareVector0.:=0;SimplexCompareVector[l]:=0;SimplexCompare Vector [2]:=0;

112. SimplexCompareVector3.:=0;SimplexCompareVector[4]:=0;SimplexCompareVector[ 5]:=0;

113. SimplexCompareVector6.:=0;SimplexCompareVector[7]:=0;SimplexCompareVector[ 8]:=0;

114. SimplexCompareVector9.:=0;SimplexCompareVector[ [11]:=0;

115. SimplexCompareVector12.:=0;SimplexCompare Vector or[14]:=0;

116. SimplexCompareVectorl 5 or[17.:=0;

117. SimplexCompareVector 18 or[20.:=0;

118. SimplexCompareVector21 or[23.:=0;

119. SimplexCompareVector24 or[26.:=0;

120. SimplexCompareVector27 or[29.:=0;

121. SimplexCompareVector30 or[32.:=0;

122. SimplexCompareVector33 or[35.:=0;

123. SimplexCompareVector36 or[38.:=0;

124. SimplexCompareVector39 AssignFile(F,'simplex.opc'); Rewrite(F);