Методы и модели адаптивной маршрутизации в сетях ЭВМ: На примере сети ЭВМ "Экспресс-2" тема диссертации и автореферата по ВАК РФ 05.13.13, кандидат технических наук Березка, Михаил Павлович

• Березка, Михаил Павлович
• кандидат технических наук
• 2001

Оглавление диссертации кандидат технических наук Березка, Михаил Павлович

ВВЕДЕНИЕ.

ГЛАВА 1. МЕТОДЫ МАРШРУТИЗАЦИИ В СЕТЯХ ЭВМ.

1.1. Распределенная обработка данных в сетях ЭВМ.

1.2. Стратегии маршрутизации в сетях передами данных.

1.3. Краткая характеристика системы "Экспресс-2".

1.4. Развитие СПД "Экспресс-2" и методы маршрутизации.

1.5. Постановка задачи исследования.

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

2.1. Основные понятия и определения.

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

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

ГЛАВА 3. МОДЕРНИЗАЦИЯ АЛГОРИТМОВ МАРШРУТИЗАЦИИ СООБЩЕНИЙ В СПД "ЭКСПРЕСС-2".

3.1. Разработка алгоритма адаптивной маршрутизации с учетом текущей загрузки для АСУ "Экспресс-2".

3.2. Исследование методов маршрутизации в сети передачи данных системы "Экспресс - 2".

3.3. Результаты анализа методов маршрутизации СЦЦ "Экспресс-2".

ГЛАВА 4. ВОПРОСЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ АЛГОРИТМОВ МАРШРУТИЗАЦИИ В СПД "ЭКСПРЕСС-2".

4.1. Методика распространения информации о состоянии сети.

4.2. Протокол адаптивной маршрутизации с учетом текущей загрузки ребер.

4.3. Программная реализация алгоритма адаптивной маршрутизации.

4.4. Методика сбора статистических данных о функционировании СПД "ЭКСПРЕСС-2".

4.5. Анализ результатов измерений работы реальной СПД "Экспресс-2" при использовании различных алгоритмов маршрутизации.

Введение диссертации (часть автореферата) на тему «Методы и модели адаптивной маршрутизации в сетях ЭВМ: На примере сети ЭВМ "Экспресс-2"»

Актуальность проблемы. Тема диссертации актуальна в связи с важным значением задачи эффективного использования пропускных способностей каналов связи в сетях передачи данных (в частности в СПД «Экспресс-2») с обеспечением установленного качества обслуживания. Особую важность имеет эффективная маршрутизация сообщений в условиях отказов отдельных элементов сети, всплесков трафика и локальных перегрузок. Несмотря на бурное развитие телекоммуникационных технологий, многие крупные сети передачи данных производственного назначения до сих пор вынуждены использовать низкоскоростные и ненадежные каналы связи. В тоже время многие как отечественные, так и зарубежные сети не используют алгоритмов маршрутизации, адаптивных к перегрузкам каналов. В значительной мере это объясняется тем, что большинство зарубежных сетей использует при выборе маршрута передачи критерий минимума стоимости передачи, а стоимость каналов связи в коммерческих системах не зависит от нагрузки. В тоже время существует класс отечественных и зарубежных сетей, для которых выбор маршрута, использующий в качестве метрики величину шлейфовой задержки и учитывающий перегрузки в сети, улучшает характеристики сети. Поэтому разработка адаптивного алгоритма маршрутизации, учитывающего текущую загрузку, перегрузки в сети и обеспечивающего эффективное расщепление трафика по нескольким направлениям, является актуальной задачей.

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

В соответствии с поставленной целью задачами диссертации являются:

- разработка и исследование адаптивного алгоритма маршрутизации, эффективно функционирующего в низкоскоростной ненадежной технической среде;

- разработка методов математического моделирования алгоритмов адаптивной маршрутизации в СПД;

- оценка целесообразности использования алгоритмов адаптивной маршрутизации в СПД «Экспресс-2» на основе разработанных методов математического моделирования.

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

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

Новыми научными результатами являются:

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

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

- эффективный метод определения нижней оценки задачи выбора оптимальных маршрутов для фиксированной (однопутевой) маршрутизации;

- сравнительный анализ и выбор алгоритмов маршрутизации применительно к сети ЭВМ «Экспресс-2».

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

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

Реализация результатов работы. Методы и алгоритмы, предложенные в диссертации, внедрены во всех 29-ти региональных центрах системы «Экспресс-2». Работы по модернизации алгоритмов маршрутизации сообщений проводились в 1999-2000 годах в рамках договоров ВНИИАС МПС на сопровождение эксплуатации системы «Экспресс-2» с МПС РФ, железнодорожными администрациями Украины, Белоруссии, Казахстана, Молдовы, Латвии и Узбекистана. 6

Внедрение указанных алгоритмов позволило улучшить функционирование сети в условиях всплесков нагрузки, при отказе каналов связи и в условиях перегрузки в периоды максимального трафика, а также позволило обеспечить в рамках сети «Экспресс-2» сбор информации в Москву и Минск обо всех проездных и перевозочных документах, оформленных, возвращенных и погашенных в любом региональном центре России и СНГ, если эти документы имеют отношение к перевозкам по России/Белоруссии или в вагонах Российских/Белорусских железных дорог, для формирования аналитической базы данных по пассажирским перевозкам. Акты о внедрении приведены в приложении 1. Апробация работы. Результаты диссертации докладывались на:

• V совещании по распределенным системам и сетям, С08-92. Светлогорск, 1992. «Организация сети передачи данных в АСУ "Экспресс-2"»

• Международной конференции по проблемам управления. Москва, ИЛУ, 1999. «Адаптивная маршрутизация сообщений в сети передачи данных».

• На научных семинарах ИППИ РАН и ВНИИАС МПС.

Публикации. Основные результаты диссертации опубликованы в 10 печатных работах. Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и приложений. Диссертация содержит 130 страниц включающих 6 рисунков, 22 таблицы, приложения содержат 20 страниц. Список литературы имеет 48 наименований.

Заключение диссертации по теме «Телекоммуникационные системы и компьютерные сети», Березка, Михаил Павлович

ЗАКЛЮЧЕНИЕ

1. Предложен метод адаптивной распределенной к-путевой маршрутизации сообщений в сети передаче данных, основанный на анализе шлейфовой задержки;

2. Проведен анализ методов математического моделирования, применимых к маршрутизации в СПД «Экспресс-2»;

3. Проведено математическое моделирование предложенного метода маршрутизации, а также методов однопутевой и к-путевой маршрутизации без учета текущей загрузки на примере сети ЭВМ «Экспресс-2»;

4. Разработан алгоритм определения шлейфовой задержки в сети;

5. Разработан алгоритм обмена информацией о состоянии сети и поддержании идентичности модели сети в узлах сети;

6. Разработан алгоритм для практической реализации метода адаптивной п-путевой маршрутизации с учетом текущей загрузки ребер;

7. Разработана система измерений для анализа эффективности функционирования СПД и апробации новых алгоритмов;

8. Проведен натурный эксперимент на реальной сети ЭВМ «Экспресс-2», который подтвердил высокую степень соответствия полученных теоретических результатов и натурного эксперимента;

Список литературы диссертационного исследования кандидат технических наук Березка, Михаил Павлович, 2001 год

1. Клейнрок JI. Коммуникационные сети: Пер. с англ. М.: Наука, 1975. - 256 с.

2. Клейнрок Л. Вычислительные системы с очередями: Пер. с англ. М.: Мир, 1979. - 600 с.

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

4. Д. Бертсекас, Р. Галлагер. Сети передачи данных: Пер. с англ. М.: Мир, 1989. - 544 с.

5. Дэвис Д., Барбер Д., Прайс У., Соломонидес С. Вычислительные сети и сетевые протоколы: Пер. с англ. М.: Мир, 1981. - 563 с.

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

7. Jackson J. R. Networks of waiting lines //Operations Research.-1957.-N5.-p. 518-521.

8. Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. М.: Наука, 1987.-336 с.

9. Fratta L., Gerla М., Kleinrock L. The flow deviation method: An approach to store-and-forward communication network design //Networks.-1973.-vol.3, N2.-p. 97-133.

10. Cantor D. G, Gerla M. Optimal routing in a packet-switched computer network// IEEE Trans, on Computers.-1974.-vol. C-23, N10.-p. 1062-1068.

11. M. Schwartz, Cheung С. K. The gradient projection algorithm for multiple routing in message-switched networks/ЯЕЕЕ Trans, on Commun.-1976.-vol. COM-24, N4.-p. 449-456.

12. Gerla M., Kleinrock L. On the topological design of distributed computer networks// ШЕЕ Trans, on Commun.-1977.-vol. COM-25, Nl.-p. 48-53.

13. Frank M., Wolfe P. An algorithm for quadratic programming //Naval Research Logistic Quarterly.-^, N3.-p. 95-110.

14. Floyd R. W. Algorithm 97: Shortest path //Comm. ACM.-1962.-N3.-p. 345.

15. Федотов E. В. Определение оптимальных маршрутов в сети пакетной коммутации// Сетевая обработка информации/ МДНТП. М., 1990. - с.95-98.

16. Gavish В., Hantler S. L. An algorithm for optimal route selection in SNA networks// IEEE Trans, on Commun.-1983.-vol. COM-31, N10.-p. 1154-1161.

17. Courtois P. J., Semal P. An algorithm for the optimization of nonbifurcated flows in computer communication networks //Performance Evaluation.-1981.-vol.1.-p.139-152.

18. Вишневский В.М., Федотов Е. В. Анализ методов маршрутизации при проектировании сетей пакетной коммутации//3-гс11.S. "Teletraffic Theory and Computing Modeling". София, 1990.

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

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

21. Held М., Wolfe P., Growder Н. P. Validation of subgradient optimization //Mathematical programming.-1974.-N6.- p. 62-88.

22. Dijkstra E. W. A note on two problems in connexion with graphs//Numer. Math.-1959,l.-p. 269-271.

23. Зайченко Ю. П. Задачи проектирования структуры распределенных вычислительных сетей// Журнал «Автоматика». № 3, 1981. с.35-44.

24. Жожикашвили В. А., Вишневский В. М. Сети массового обслуживания.Теория и применение к сетям ЭВМ,- М.: Радио и связь, 1988,- 192 с.

25. Э.МАИНИКА Алгортимы оптимизации на сетях и графах

26. Прытов A.A. Алгоритмы маршрутизации сети "Сирена-2". 5-я Всесоюзная школа-семинар по РАСМО Рига, 1988 с.222

27. Прытов A.A. Адаптивная маршрутизация сети "Сирена-2". 3-е Всесоюзное совещание по распределенным автоматизированным системам массового обслуживания. Москва, 1990

28. Б.Марчук, И.Родин, М.Березка, А.Комиссаров "На пути к "Экспрессу-3". Журнал «Железнодорожный транспорт/Connect! Мир связи» (совместный выпуск), № 9, 1999г, с.64-67.

29. Березка М.П., Богданов В.М., Овчинников Б.С. "Взаимодействие терминалов и информационных систем в АСУ "Экспресс" при переходе от системы "Экспресс-2" к системе "Экспресс-3". Журнал «Автоматика, связь, информатика», № 4, 2000г. с.22-24.1.SN 0005-2329

30. Березка М.П. "Маршрутизация сообщений в сети передачи данных АСУ "Экспресс-2". Журнал «Автоматика, связь, информатика», №10, 2000г с.40-43. ISSN 0005-2329

31. Марчук Б.Е. От продажи билетов к управлению пассажирскими перевозками. Журнал «Автоматика, связь, информатика», № 9, 1999г с.4-7. ISSN 0005-2329

32. Марчук Б.Е. Межгосударственная система управления пассажирскими перевозками АСУ «Экспресс-3». В сб: «Опыт разработки, эксплуатации и перспективы развития «Экспресс». Научно-практическая конференция» М.,ВНИИЖТ,1997 с.34-43.

33. Лисицын А.Л., Марчук Б.Е. Автоматизация управления пассажирскими перевозками. В сб: «Опыт разработки, эксплуатации и перспективы развития «Экспресс». Научно-практическая конференция» М.,ВНИИЖТ,1997 с.8-12.

34. Березка М.П., Рыжик Б.З. Организация сети передачи данных в АСУ "Экспресс-2". Тезисы докладов V совещания по распределенным системам и сетям, CDS-92. Светлогорск, 1992 РЦ ГПНТБ России с.7-9.

35. Березка М.П., Борткевич А.И. Автоматизированная система коммутации сообщений NETWORK. В сб. "Проблемы информатизации на ж.д. транспорте" М,Транспорт,1992 с.76-83. ISBN 5-277-01656-2

36. Березка М.П., Родин И.В., Рыжик Б.З. Некоторые проблемы разнородных и интегрированных сетей на базе АСУ "Экспресс-2". В сб. "Компьютерные технологии управления на ж.д. транспорте" М, НИИЖА, 1995 с. 132-140. УДК 656.211.5.072

37. Кульгин М.В. Коммутация и маршрутизация IP/IPX трафика. М, КомпьютерПресс, 1998, 216 с. ISBN 5-89959-057-2

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

39. Богуславский Л.Б. Управление потоками данных в сетях ЭВМ. М, Энергоиздат, 1984, 168 с.

40. Васильев Г.П., Горский В.Е., Шяудкулис В.И., Саух Н.М. Программное обеспечение неоднородных распределенных систем: анализ и реализация. М, Финансы и статистика, 1986, 158 с.

41. Мартин Дж. Вычислительные сети и распределенная обработка. Перев с англ. Вып 2. М, Финансы и статистика, 1985, 256 с.

42. Лазарев В.Г., Лазарев Ю.В. Динамическое управление потоками в сетях связи. М, Радио и связь, 1983, 216 с.

43. Шварц М. Сети связи: Протоколы, моделирование и анализ. В 2-х частях. Часть1. Перев с англ. М, Наука, Гл.ред.физ-мат.лит, 1992, 336 с.

44. Бутрименко A.B. Разработка и эксплуатация сетей ЭВМ. М, Финансы и статистика, 1981, 256 с.

45. Березка М.П., Родин И.В., Рыжик Б.З. Развитие математического и программного обеспечения АСУ «Экспресс-2». Журнал «Автоматика, телемеханика и связь на железнодорожном транспорте» № 2, 1994, с.76-73 ISSN 0005-2329

46. Березка М.П., Вишневский В.М., Федотов Е.В. «Модернизация алгоритмов маршрутизации в сети ЭВМ «Экспресс-2». Журнал «Ведомственные корпоративные сети и системы130

47. BKCC. Connect)». № l, 2001

48. Березка М.П., Левнер Е.В., Вишневский В.М., Федотов Е.В. «Математические модели ал горитмов адаптивной маршрутизации». Электронный журнал ИППИ РАН. № 1, 2001

49. Березка М.П. Адаптивная маршрутизация сообщений в сетях передачи данных. Международная конференция по проблемам управления. Тезисы докладов, т.З, с. 176-178 ИЛУ, 1999 ISBN 5-93394-004-6

50. Лазарев В.Г. Интеллектуальные цифровые сети. М, Финансы и статистика, 1996 223 с.131