Управление перераспределением потоков в магистральных сетях передачи данных тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Максимович, Вадим Васильевич

• Максимович, Вадим Васильевич
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Максимович, Вадим Васильевич

ВВЕДЕНИЕ.

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

1.1. Классификация алгоритмов и средств управления маршрутизацией потоков данных (обзор).

1.2. Многопротокольная коммутация меток.

1.3. Методы перераспределения потоков данных с помощью технологии MPLS-TE.

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

2.1. Постановка задачи о равномерной загрузке каналов связи.

2.2. Обзор методов решения задач удовлетворения ограничений с конечными областями значения переменных.

2.3. Программирование в ограничениях как метод решения задачи о равномерной загрузке каналов связи СПД.

2.4. Булевы модели генерации туннельных маршрутов.

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

3.1. Описание системы управления.

3.2. Структура и функциональные возможности программного обеспечения сервера маршрутизации.

3.3. Балансировка загрузки каналов связи для магистральной СПД ВСЖД.

Введение диссертации (часть автореферата) на тему «Управление перераспределением потоков в магистральных сетях передачи данных»

Актуальность темы. Сети передачи данных (СПД), использующие протокол Internet Protocol (IP), широко распространены по всему миру. В последнее время в сетях передачи данных, использующих протокол IP, внедряются услуги, как характерные для традиционных сетей с коммутацией каналов, такие как телефония, так и новые услуги, такие как видеотелефония, телевидение по запросу, виртуальные частные сети. При этом пользователи требуют от сетей передачи данных на основе протокола IP, такого же качества предоставляемых услуг и надежности сети, к которому они привыкли в традиционных сетях TDM(Time-Division Multiplexing, Мультиплексирование с разделением времени) и PSTN(Public Switched Telephone Network, Публичная коммутируемая телефонная сеть). При этом остро стоит вопрос об эффективности использовании ресурсов СПД, надежности и быстрого восстановления работы сети после сбоя. Не смотря на резкое увеличение скоростей на магистральных каналах связи, пропускная способность локальных сетей растет еще быстрее. В октябре 2006 года подразделением IEEE SA(IEEE Standard Association) организации IEEE(Institute of Electrical and Electronics Engineers) принят стандарт Ethernet с пропускной способностью 10 Гигабит/сек(100Вазе-Т) по медной паре на расстоянии 100 и более метров. Раньше для таких величин пропускной способности использовали дорогое оптоволокно, и внедрение медной пары вместо оптоволокна резко удешевит внедрение и сопровождение локальных сетей с такими скоростями передачи данных, что сделает внедрение локальных сетей с такой пропускной способностью массовой, и повлечет за собой широкое внедрение широкополосных сервисов и резкое возрастание объемов данных передаваемых через глобальные сети между локальными сетями. Причина неэффективного использования ресурсов глобальных (магистральных) сетей передачи данных заключается в существующих алгоритмах протоколов маршрутизации. Из-за недостатков традиционных протоколов маршрутизации потоки данных направляются только по маршруту с минимальной метрикой, игнорируя другие маршруты. Разумеется, если маршруты для передачи данных будут выбираться с учетом доступных ресурсов сети, это положительно скажется на качестве обслуживания и позволит при неизменных ресурсах сети повысить качество обслуживания или увеличить количество услуг, для которых необходимо гарантированное качество сервиса.

Один из способов решения вышеприведенных проблем заключается во внедрении в СПД, использующих протокол IP, методов перераспределения потоков данных. Задача методов перераспределения заключается в достижении наиболее эффективного использования ресурсов СПД при обеспечении требуемого качества предоставляемых сервисов, быстрого восстановления после сбоев. Как правило, работа методов перераспределения требует использования протоколов маршрутизации с учетом ограничений (Constraint-Based Routing Protocol), иначе называемых протоколы маршрутизации с учетом уровня качества (QoS-Based Routing Protocol).

В глобальных СПД базовые средства перераспределения потоков данных в настоящее время реализованы в рамках технологии MPLS-TE (Multiprotocol Switching Label Traffic Engineering). При использовании технологии MPLS-TE маршрутизаторы сами могут самостоятельно рассчитывать пути, но без учета всей информации о состоянии СПД, особенно о загруженности каналов связи. В этих условиях предпочтительным является использование внешней управляющей программы, обеспечивающей сбор статистики об интенсивности входных потоков и принятие (на основе этой информации) необходимых управляющих решений по перераспределению потоков данных с учетом пропускных способностей каналов связи.

Тематика диссертационного исследования находится в русле приоритетных направлений развития науки в Российской Федерации

Информационно-телекоммуникационные системы", утвержденных Президентом Российской Федерации 21 мая 2006 г. (№ Пр-843).

Объект исследования. Глобальные СПД с технологией перераспределения потоков данных MPLS-TE.

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

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

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

2. Формализовать задачу перераспределения потоков данных с целью равномерной загрузки каналов связи в виде специализированной задачи удовлетворения ограничений(в том числе и булевых).

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

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

5. Оценить эффективность разработанных методов и средств на примере производственной задачи перераспределения потоков данных и балансировки загруженности каналов связи для магистральной СПД Восточно-Сибирской железной дороги (ВСЖД).

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

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

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

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

Практическая значимость полученных результатов. Применение разработанных в диссертации методов и программных средств позволяет повысить эффективность использования ресурсов магистральных СПД с технологией MPLS-TE.

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

Реализация. Исследования по теме диссертации выполнялись в рамках плановых тем кафедры "Управление техническими системами" Иркутского государственного университета путей сообщения. Результаты исследования используются информационно-вычислительном центре ВСЖД филиала ОАО "РЖД" для совершенствования алгоритмов управления магистральной СПД, а также в Иркутском государственном университете путей сообщения при выполнении дипломных работ по кафедре "Управление техническими системами".

Апробация. Основные результаты работы докладывались и обсуждались на следующих конференциях:

• II Всероссийская конференция "Инфокоммуникационные и вычислительные технологии и системы" (Иркутск, 2006).

• VI Международная научно-практическая конференция "Моделирование. Теория, методы и средства." (Новочеркасск, 2006).

• 44-ая Всероссийская научно-практическая конференция "Современные технологии-железнодорожному транспорту и промышленности" (Хабаровск, 2006).

• конференция "Ляпуновские чтения & Презентации информационных технологий" (Иркутск, 2006).

• V Сибирская научная школа-семинар с международным участием "Компьютерная безопасность и криптография" - SIBECRYPTO'06 (Шушенское, 2006).

Публикации. По теме диссертации опубликовано 6 работ в виде статей в журналах, трудах международных и российских конференций и сборнике научных трудов ИрГУПС, в том числе одна статья в издании, рекомендованном ВАК для опубликования научных положений диссертационных работ. В работах, опубликованных в соавторстве, автору принадлежат научные и практические результаты, заявленные в диссертации. При этом булевы модели и средства генерации туннельных маршрутов разработаны совместно с Г.А. Опариным, А.П. Новопашиным, В.Г. Богдановой и являются неделимыми.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы из 91 наименования. Общий объем диссертации - 98 страницах машинописного текста, полный объем диссертационной работы 131 страница. Работа включает 30 рисунков, 2 таблицы и 8 приложений.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Максимович, Вадим Васильевич

ЗАКЛЮЧЕНИЕ

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

Основные научные и практические результаты, которые выносятся на защиту:

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

2. Методическое, алгоритмическое и программное обеспечение решения задачи балансировки загрузки каналов связи, основанное на применении технологии программирования в ограничениях.

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

4. Решение прикладной задачи о перераспределении потоков данных в магистральной СПД ВСЖД.

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

Список литературы диссертационного исследования кандидат технических наук Максимович, Вадим Васильевич, 2007 год

1. http://standards.ieee.org/2. http://www.ieee.org/

2. Олифер В.Г., Олифер Н.А. Компьютерные сети. 3-е изд.-СПб.: Питер2006.-958 с.

3. Davie В., Rekhter Y. MPLS Technology and Applications Los Altos.: CA.—2000.-287 c.

4. V. Sharma, et. al., "Framework for MPLS based Recovery", Internet draftdraft-ietf-mpls-recovery-frmwrk-04.txt>-July, 2001.-31 p.

5. M. Kodialam, T.V. Lakshman, Dynamic Routing of Bandwith Guaranteed

6. Tunnels with Restoration. Proc Of Infocom - March, 2000.-10 p.

7. Вишневский В. M. Теоретические основы проектирования компьютерныхсетей. М.: ЗАО "Техносфера".- 2003 512 с.

8. Gafni М., Bertsekas D. Asymptotic Optimality of Shortest Path Routing

9. Algorithms // IEEE Trans. Of Information Theory 1987 - N 1 - 83- 90 p.

10. Дикер Пилдуш Г. Сети ATM корпорации Cisco С.П.: Вильяме - 2004—880 с.

11. ATM Forum. Private Network-Network Interface Specification. Version10.- AF-PNNI-0055.000- March, 1996.-385 p.

12. ATM Forum. PNNI Augmented Routing. Version 1.0.-AF-RA-0104.0001. January, 1999 -65 p.

13. ATM Forum. Private Network-Network Interface Specification. Ver. 2.O.1.ving List.- LTD-CS-RA-PNNI-02.03.- July, 1996.

14. Reilly J., Abate M. Scheduled Connections: Managing Temporal Constrainson Broadband Network Resources // Proceedings of IS& N'98. May, 1998— Lecture Notes in Computer Science. Springer.-425 p.90

15. Вивек Олвейн. Структура и реализация современной технологии MPLS .- С.П.: Вильяме.- 2004.- 470 с.

16. Awduche D. MPLS and Traffic Engineering in IP Network, IEEE Communications, Vol. 37, Dec. 1999.-7 p.

17. Шринивас Вегешна. Качество обслуживания в сетях IP С.П.: Издательский дом "Вильяме",- 2003 - 368 с.

18. D. Awduche, A. Chiu, A. Elwalid, I. Widjaja, X. Xiao. Overview and Principles of Internet Traffic Engineering. Request for Comments: 3272-2002.-71 p.

19. D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, J. McManus. Requirements for Traffic Engineering Over MPLS. Request for Comments: 2702.-1999-29 p.

20. E. Crawley, R. Nair, B. Rajagopalan, H. Sandick. A Framework for QoS-based Routing in the Internet. Request for Comments: 2386 1998 - 37 p.

21. J. Moy. OSPF Version 2. Request for Comments: 2328.-1998.- 244 p.

22. J. Moy. OSPF Standardization Report. Request for Comments: 2329.-1998-9 p.

23. Томас M. Томас II., Структура и реализация сетей на основе протокола

24. OSPF. 2-ое изд.- С.П.: Вильямс.-2004.- 816 с.91

25. Пакет К., Тир Д. Создание масштабируемых сетей Cisco С.П.: Издательский дом "Вильяме".- 2002 - 792 с.

26. I. Widjaja, I. Saniee, A. Elwalid, and D. Mitra. Online Traffic Engineering with Design-based Routing, ITC Specialist Workshop, Wurzburg-2002-10 p.26. www.opnet.com27. www.wandl.com

27. P. Aukia, M. Kodialam, P. V. Koppol, Т. V. Lakshman, H. Sarin, B. Suter. RATES: A Server for MPLS Traffic Engineering. IEEE Network, vol. 14, no. 2- Mar./Apr. 2000.-10 p.

28. J. Boyle, R. Cohen, D. Durham, S. Herzog, R. Rajan, and A. Sastry. "The COPS (common open policy service) protocol," Internet Draft, Internet Engineering Task Force Feb. 1999.-38 p.

29. M. Kodialam and Т. V. Lakshman, "Minimum interference routing withapplications to MPLS traffic engineering," in Proceedings of the Conference on Computer Communications (IEEE Infocom).- Mar. 2000.-10 p.

30. G.B. Figueiredo, N.L.S. da Fonseca, J.A.S. Monteiro. A Minimum1.terference Routing Algorithm. Technical Report 1С—03-014—2003 —12 p.

31. B.W.X. Su, C.P. Chen, "A new bandwidth guaranteed routing algorithm for

32. MPLS traffic engineering", Proceeding of IEEE International Conference on Communications April, 2002.-10 p.

33. S. Suri, M. Waldvogel, P. Warkhede. Profile-based routing: A newframework for MPLS traffic engineering. Washington University Computer Science Technical Report WUCS-00-21.- July, 2001.-11 p.

34. A.Elwalid, C. Jin, S. Low, I. Widjaja. MATE: MPLS adaptive trafficengineering. Proc. of IEEE INFOCOM'2001.- 2001.-10 p.

35. Eric Osborne, Ajay Simha. Traffic Engineering with MPLS Cisco Press2002.- 608 p.

36. Попков В.К. Математические модели связности 4.2 Гиперграфы игиперсети.- Новосибирск: Изд. ИВМиМГ СО РАН 2001.- 180 с.

37. Опарин Г.А., Богданова В.Г., Новопашин А.П., Максимович В.В.

38. Опарин Г.А., Богданова В.Г., Новопашин А.П., Максимович В.В.

39. Фиксированная маршрутизация в магистральных сетях передачи данных: булевы модели генерации множества туннельных маршрутов и узла-источника в узел-адресат. //Вестник ТГУ. Приложение -2006-№17. С. 170-175.

40. Лорьер Ж.-Л. Системы искусственного интеллекта: Пер. с франц.-М.:1. Мир.- 1991.-586 с.

41. Яхно Т.М. Программирование в ограничениях: обзоры и классификацияподходов и методов. Системная информатика: Сб. научн. тр-Новосибирск: Наука, 1995-Вып. 4: Методы теоретического и системного программирования С. 160 - 192.

42. Dechter R., Pearl J. Tree Clustering for Constraint Network // Arificial1.telligence.- 1989.- Vol.38.-P. 353-366.

43. Freuder E. Synthesizing Constraint Expressions // Comm. of the ACM, 19781. V.21.-№ 11.-P. 958-966.

44. Dechter R., Pearl J. Network-based heuristics for constraint-satisfactionproblems //Artifical Intelligence.-1998.-V.34.-№1.-P. 1-38.

45. Bitner J.R., Reingold E.M. Blacktrack programming techniques // Commun.

46. ACM.-l 975.-V. 18.-P.651-656.

47. Montanari U. Networks of constraints: Fundamental properties andapplications to picture processing // Information Science, 1974- V.7.-№66-P.95-132.

48. Mackworth A.K. Consistency in networks of relations // Artifical1.telligence.- 1977.-V.8.-№1.-P.99-118.

49. Freuder E. A sufficient condition of backtrack-free search // J.ACM 19821. V.29.-№1 -P.24-32.

50. Mohr R., Henderson T. Arc-consistency and path-consistency revisited //

51. Artificial Intelligence.- 1986.-№28.-P.325-330.

52. Deville Y., Van Hentenryc P. An Efficient Arc Consistency Algorithm for a

53. Class of CSP Problems // Proc. IJCAI.-1991.-P.325-330.

54. Bessiere C. Arc-consistency and arc-consistency again // Artifical1.telligence.- 1994,- №65.-P. 179-190.

55. Bessiere C., Freuder E.C., Regin J.-C. Using inference to reduce arcconsistency computation // Proc. 14th IJCAI.-1996.-V.1.-P.592-598.

56. Haralick R.M., Elliot G.L. Increasing tree search efficiency for constraintsatisfaction problem // Artificial Intelligence.-l980.-№14.-P.263-313.

57. McGregor J.J. Relational consistency algorithms and their applications topicture processing // Infotrom. Sci.-1979.-V.19.-P.229-250.

58. Tsang E. Foundations of Constraint Satisfaction // Academic Press.-1993.-201. P

59. Zsofia Ruttkay. Constraint Satisfaction a Survey / CWI Quarterly .-19981. V. 1 .-№2-3 -P. 123-161.

60. Decther R., Rossi F. Constraint Satisfaction. Survey ECS.-March.-2000.-151. P

61. Dechter R., Pearl J. Network-based heuristics for constraint-satisfaction problems // Artifical Intelligence.-1998.-V.34.-№l.-P.l-38.

62. Dechter R. Enhancement schemes for constraint processing: backjumping,learning, and cutest decomposition // Artificial Intelligence -1990 -V.41-№3-P.273-312.

63. Roberto J. Bayardo, Daniel P. Miranker. An optimal backtrack algorithm fortree-structured constraint satisfaction problems // Artificial Intelligence .-1994.-№71 -P. 159-181.

64. Van Hentenryck P. Constraint Satisfaction in Logic Programming // Logic

65. Progr. Series, MIT Press-Cambridge, MA.-1989.

66. Kondrak G., Van Beek P. A theoretical evalution of selected backtrackingalgorithms // Artifical Intelligence.- 1997.-V.98.-№(l-2)-P.365-387.

67. Gasching J. A general backtracking algorithm that eliminates most redundanttests I I Proceedings IJCAI-77.-Cambridge,MA.-1977.-P.457.

68. Haralick R.M., Elliot G.L. Increasing tree search efficiency for constraintsatisfaction problem // Artificial Intelligence.-V.14- 1980-P.263-313.

69. MCGregor J.J. Relational consistency algorithms and their applications topicture processing // Infortorm. Sci.-№19.-1979.-P.229-250.

70. Горшков С.П. Применение теория NP-полных задач для оценкисложности решения систем булевых уравнений // Обозрение прикладной и промышленной математики.Серия дискретной математики.- Т.2.-Вып.З.-1995.- С. 325-398.

71. Prosser P. Hybrid algorithms for the constraints satisfaction problem //

72. Comput. Intell.-l 990.-P. 17-24.

73. Опарин Г.А., Богданова В.Г. Технология булева моделирования дискретных задач в инструментальном комплексе РЕБУС. Моделирование. Теория, методы и средства. Материалы V Межд. Научн.-практ. конф-Новочеркасск: ЮРГТУ-2005-Ч. 1-С. 18-22.

74. Опарин Г.А., Новопашин А.П. Булево моделирование планирования действий в распределенных вычислительных системах. Известия РАН. Теория и системы управления - 2004 - N.S.- С.105-108.

75. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1973- 386 с.

76. Опарин Г.А., Максимович В.В. Управление маршрутизацией вмагистральных сетях передачи данных с использованием технологии MPLS. Информационные системы контроля и управления в промышленности и на транспорте. Моделирование систем управления:

77. Сб. науч. трудов / Под ред. С.Н. Васильева, Ю.Ф. Мухопада- Иркутск: Изд-во ИрГУПС, 2006.- Вып. 14.- С. 22-29.75. http://netacad.kiev.ua/flowc.76. www.netams.com.

78. MySQL Administrator's Guide.- Sams Publishing 2004 - 400 p.

79. MySQL Certification Study Guide Sams Publishing.- 2004 - 648 p.

80. X.M. Дейтел, П.Дж. Дейтел, T.P. Нието, Д.К. МакФай., Какпрограммировать на Perl М.:ЗАО "Издательство БИНОМ".- 2002 г-1088 с.80. http://search.cpan.org/~ehood/Proc-Daemon-0.03/Daemon.pm.81. http://www.freepascal.org.82. http://www.freepascal.ru.

81. М. Бен-ари. Языки программирования. Практический сравнительныйанализ. М.: Издательство "Мир",- 2000 г.- 336 с.84. http://search.cpan.org/~irogers/Net-Telnet-3.03/lib/Net/Telnet.pm.85. http://search.cpan.org/~ioshua/Net-Telnet-Cisco-l.10/Cisco.pm

82. Cisco Systems. Руководство по технологиям объединенных сетей, 3-еиздание С.П.: Издательский дом "Вильямс".-.2002.- 1040 с.

83. В. Боллапрагада, К. Мэрфи, Р. Уайт. Структура операционной системы

84. Cisco IOS С.П.: Издательский дом "Вильяме" .- 2002 - 200 с.88. http://www.cisco.com.89. www.openview.hp.com.90. http://www.splintered.net/sw/flow-tools/.91. http://www.mindrot.org/softflowd.html.