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

Введение.

Глава 1 - Анализ основных направлений развития структур и технологий телекоммуникационных сетей.

1.1 Телекоммуникационные сети и прогресс в телекоммуникационных технологиях.

1.1.1 Анализ этапов интеграции и конвергенции сетей связи.

1.1.2 Анализ проблем развертывания конвергированных сетей связи наВСС РФ.

1.1.3 Ожидаемые результаты развертывания конвергированных сетей связи.

1.2 Взаимодействие различных телекоммуникационных технологий на перспективной широкополосной сети электросвязи.

1.2.1 Анализ модели перспективной инфокоммуникационной сети.

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

1.2.3 Анализ существующего состояния на ВСС России.

1.3 Анализ телекоммуникационных технологий, имеющих перспективу применения на ВСС России.

1.3.1 Сети стандарта Х.25.

1.3.2 Технология Frame Relay.

1.3.3 Широкополосная цифровая сеть с интеграцией служб.

1.3.4 Протокол IP.

1.3.5 Технология MPLS.

1.3.6 Плезиохронная и синхронная цифровые иерархии.

1.3.7 Технология WDM.

1.4 Классификация технологий абонентского доступа.

1.4.1 Анализ основных технологий семейства xDSL.

1.4.2 Анализ методик использования оптического кабеля в сети абонентского доступа.

1.4.3 Анализ использования в сети абонентского доступа гибридных схем HFC.

1.4.4 Концепция передачи информации с применением оборудования "Home Gateway".

1.5 Выводы.

Глава 2 - Анализ существующих алгоритмов поиска оптимальных путей в оптических телекоммуникационных сетях.

2.1 Введение.

2.2 Проблема поиска оптимального пути в оптической сети.

2.2.1 Декомпозиция телекоммуникационной сети на информационную сеть и сеть управления потоками информации.

2.2.2 Модель информационной сети.

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

2.3 Анализ точного алгоритма поиска оптимального полусветового пути.

2.3.1 Алгоритм поиска оптимального полусветового пути.

2.4 Анализ канальных планов для технологии WDM.

2.5 Совместное использование различных функциональных элементов для формирования узла полностью оптической сети.

2.6 Анализ нормативных документов, регламентирующих параметры оборудования со спектральным разделением каналов.

2.6.1 Рекомендации Международного Союза Электросвязи в области

ВОСП со спектральным разделением каналов.

2.6.2 Нормативные документы, разработанные в Российской

Федерации.

2.7 Выводы.

Глава 3 - Разработка алгоритма поиска оптимального маршрута передачи информации в оптической сети с учетом ее свойств.

3.1 Введение.

3.2 Анализ последовательности проведения расчетов в процессе выполнения алгоритма поиска оптимального пути.

3.2.1 Алгоритм преобразования структуры сети связи к расчетному графу с учетом точек ввода-вывода.

3.2.2 Выбор алгоритма поиска кратчайшего пути в графе.

3.2.2.1 Общая схема алгоритма Дейкстры.

3.2.2.1.1 Итерация 1.

3.2.2.1.2 Итерация 2.

3.2.2.1.3 Итерация номер к>2.

3.2.2.2 Общая схема алгоритма Флойда.

3.2.3 Разработка алгоритма внесения изменений в структуру расчетного графа в соответствии с установленным соединением.

3.3 Выводы.

Глава 4 - Исследование результатов практической реализации разработанного комплексного алгоритма.

4.1 Анализ трудоемкости разработанного алгоритма.

4.1.1 Анализ трудоемкости алгоритма преобразования структуры сети к расчетному графу.

4.1.2 Анализ трудоемкости алгоритма поиска кратчайшего пути в графе.

4.1.2.1 Пример нахождения кратчайшего пути в графе с количеством вершин, равном 8.

4.1.2.1.1 Постановка задачи: орграф, матрица стоимостей.

4.1.2.1.2 Итерация 1.

4.1.2.1.3 Итерация 2.

4.1.2.1.4 Итерация 3.

4.1.2.1.5 Итерация 4.

4.1.2.1.6 Итерация 5.

4.1.2.1.7 Итерация 6.

4.1.2.1.8 Итерация 7.

4.1.2.1.9 Окончательные результаты.

4.1.2.2 Анализ трудоемкости алгоритма Дейкстры в зависимости от числа вершин п.

4.1.2.2.1 Анализ формулы (1) при различных гипотезах о виде зависимости т(к)

4.1.3 Трудоемкость алгоритма внесения изменений в структуру расчетного графа в соответствии с установленным соединением.

4.2 Разработка программного обеспечения для расчетов по разработанному алгоритму.

4.3 Выводы.

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

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

Конечной целью развития проводных транспортных сетей связи на сегодняшний день является создание полностью оптических сетей - AON (All-Optical Network), которые не только удовлетворяют потребности компаний-операторов в бесперебойной работе высокоскоростных каналов передачи информации, но и позволяют операторам получать дополнительную прибыль за счет сдачи каналов в аренду. Сети AON создаются рядом крупнейших мировых фирм (Alcatel, Lucent Technologies и т.д.) с учетом принципов оптической коммутации и использованием технологии спектрального уплотнения - WDM (Wavelength Division Multiplexing).

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

Цель работы. Целью диссертационной работы является:

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

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

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

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

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

Структура и объем работы.

Диссертация состоит из введения, четырех глав и заключения.

Основные результаты проведенных исследований сводятся к следующему:

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

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

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

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

Заключение

1. Эндрю Крэй, "DWDM-мультиплексоры: забег иа короткие дистанции", Москва, Сетевой журнал №2 2000;

2. Анпилогов В.Р., Гольдберг B.C., Диденко М.Г., "Волоконно-оптические и спутниковые линии связи в современных и перспективных телекоммуникационных системах", Москва, Технологии и средства связи №1 2000;

3. Алексей Любимов, "Магистральные технологии ПД и современные сети связи", Москва, Мир Связи Connect номер 2 - 2000;

4. Крис Болдуин, "MPLS повышает производительность сетей IP", Москва, Computer World Россия № 31-1998;

5. Барсков А. Г., "Интеграция услуг: сегодня и завтра", Москва, Сети и системы связи № 6-2000;

6. Соколов Н.А., "Конвергенция телекоммуникационных сетей. Терминологический аспект", Москва, Вестник Связи № 4 2000;

7. Коллектив авторов, "Концепция построения цифровой междугородной сети связи России", Москва, Госкомсвязи, 2000 г.;

8. А.Е. Кучерявый, АЛ. Цуприков, Ф, Доленц, И.Г. Мазин, "Некоторые аспекты конвергенции сетей ТфОГОЦСИС и IP", Москва, Вестник Связи №4 2000;

9. B.C. Томский, "Новые подходы к проектированию телекоммуникационных сетей", Москва, ЭЛЕКТРОСВЯЗЬ, № 5, 2000;

10. Кучерявый А.Е., "Состояние отрасли Связь", Москва, Технологии и средства связи, Отраслевой каталог 2000, Гротек 2000;

11. А.В. Шмалько, "Планирование и построение современных цифровых корпоративных сетей связи", Москва, Вестник Связи № 4 2000;

12. Коллектив авторов, "Правила построения системы телефонной связи общего пользования", Москва, Госкомсвязи 2000 г;

13. С. Игуменов, "Технологии широкополосного доступа", Москва, Мир Связи Connect №5 - 2000;

14. А.Ю. Рокотян, "Перспективы конвергенции сетей электросвязи в России", Москва, Вестник Связи № 1-2000;

15. А. В. Голышко, Н. А. Лескова, "Телекоммуникационные сети: вечная динамика", Москва, Сети и системы связи №5-6 2000;

16. А. Полунин, "Топологии и технологии", Москва, Сети Network World № 4-2000;

17. М. Денисьева, Д.Г. Мирошников, "Средства связи для последней мили", Москва, Эко-Трэндз 1998;

18. A.I-I. Назаров, М.В. Симонов, "ATM технология высокоскоростных сетей", Москва, Эко-Трендз 1999;

19. Н.Н, Слепов, "Современные технологии цифровых оптоволоконных сетей связи", Москва, Радио и Связь 2000;

20. М. Кульгин, "Технологии корпоративных сетей", Санкт-Петербург, "Питер" 1999;

21. И. Шелухин, Н.Ф. Лукьянцев, "Цифровая обработка и передача речи". Москва, Радио и Связь 2000;

22. Н.А. Соколов, "Сети абонентского доступа. Принципы построения", Пермь, "Энтер-Профи" 1999;

23. С, А. Дмитриев, Н.Н. Слепов, "Волоконно-оптическая техника: история, достижения, перспективы", Москва, Connect 2000;

24. А.Б. Семенов, Волоконная оптика в локальных и корпоративных сетях связи", Москва, Компьютер Пресс 1998;

25. Тезисы докладов Юбилейной НТК МТУСИ, 26 февраля 1 марта 2001 года, Москва, МТУСИ 2001;26. "Толковый словарь терминов по системам, средствам и услугам связи", Москва, Радио и Связь 2000, под редакцией В.А. Докучаева;

26. ITU-T Рекомендация Y, 120, "Методология сценария глобальной информационной инфраструктуры", 1998 год;

27. ITU-T Рекомендация G.692 "Optical interfaces for multichannel systems with optical amplifiers", 10/98;29. «Технологии DWDM в современных сетях связи», Век качества №4, 2001;

28. ITU-T Рекомендация G.957, " Optical interfaces for equipments and systems relating to the synchronous digital hierarchy", 06/99;

29. Гольдштейн B.C., "Сигнализация в сетях связи", Москва, Радио и Связь, 1997 год;

30. I.Chlamtac, A.Farago, Т. Zhang, "Lightpath (wavelength) routing in large WDM networks", IEEE J Select. Areas Commun., vol. 14, pp. 909-913;

31. Weifa Liang, Xiaojun Shen, "Improved Lightpath (Wavelength) routing in large WDM networks", IEEE Transactions on communications, vol. 48, no 8, September 2000, pp. 1571-1579;

32. K.M. Chandy and J. Mishra, "Distributed computations on graphs: Shortest path algorithms", Commun. ACM, vol.25, pp.833-837, 1982;

33. S. Haldar, "An all pairs shortest path's distributed algorithm using 2n2 messages", J. Algorithms, vol.24 pp. 20-36, 1997;

34. Иванов П., "Из тени в свет перелетая", Сети. Network World, № 7 (105);

35. Брискер А.С., Гусев Ю.М., Ильин В.В., Карпешко Ю.Е., Оробинский С.П., "Спектральное уплотнение волоконно-оптических линий ГТС", Электросвязь № 1, 1990 г.;

36. Заркевич ЕА., Павлов Н.М., Скляров O.K., Устинов С.А., "Параметры системы связи со спектральным уплотнением и оптическими усилителями в документах МСЭ-Т", Электросвязь № 6, 2000 г.;

37. ОСТ 45.178-2001, "Системы передачи с оптическими усилителями и спектральным уплотнением. Стыки оптические. Классификация и основные параметры". Введен в действие 24.04.2001

38. Paul Green, "Progress in optical networking", IEEE Communication Magazine, January 2001;

39. Крейнин P.В., Цым А.Ю., "Спектральное уплотнение оптических кабелей на транспортной сети ОАО "Ростелеком", Электросвязь №8, 2000 г.;

40. ITU-T, Рекомендация G.661 "Definition and test methods for the relevant generic parameters of optical fibre amplifiers", 1996 год;

41. ITU-T, Рекомендация G.662 "Definition and test methods for the relevant generic parameters of optical fibre amplifiers", 1995 год;

42. ITU-T, Рекомендация G.663 " Application related aspects of optical fibre amplifier devices and sub-systems", 1996 год;

43. Варданян B.A., «Исследование и разработка ВОСП с уплотнением поднесущих и спектральным уплотнением», автореферат диссертации на соискание ученой степени к.т.н., СибГУТИ, Новосибирск, 1999 год;

44. Левитан Р.И., «Разработка метода и средств повышения качества функционирования ВОСП», автореферат диссертации на соискание ученой степени к.т.н., МЭИС, Москва, 1992 год;

45. Гермейер Ю.Б., «Введение в теорию исследования операций», Наука, Москва 1971 год;50. «Теория надежности и массовое обслуживание», под редакцией Гнеденко Б.В., Наука, Москва, 1969 год;51. «Основы теории информационных сетей», Морозов В.К., Долганов

46. B.Н., Дмитриев В.П., Радио и связь, Москва, 1998 год;55. «Проектирование и техническая эксплуатация систем передачи», под редакцией Гордиенко В.Н., Крухмалева В.В., Радио и связь, Москва, 1996 год;

47. Hui Zang, Jason P. Jue, Laxman Sahasrabuddhe, Ramu Ramamurthy, Biswanath Mukherjee, "Dynamic Lightpath Establishment in Wavelength-Routed WDM Networks", IEEE Communications Magazine, September 2001, pp. 100-108;

48. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман, "Структуры данных и алгоритмы", Издательский дом "Вильяме", Москва-Санкт-Петербург-Киев, 2001 г.;

49. Новиков Ф.А., "Дискретная математика для программистов", Издательский дом "Питер", Москва-Харьков-Минск 200!г.;

50. RFC 791, "Internet Protocol", Darpa Internet Programm, Protocl Specification, September 1981;

51. Докучаев В.А., Мартынов К.Б., «Обзор малых УАТС российского производства», депонировано в ЦНТИ "Информсвязь", Москва, 1999 г;

52. Докучаев В.А. Мартынов К.Б., «База данных АПОС для хранения справочной информации», депонировано в ЦНТИ "Информсвязь", Москва, 1999 г.;

53. Докучаев В. А., Мартынов К.Б., Кузнецов А.Е., «Современные электронные компоненты MITEL Semiconductor для систем связи», каталог «Телесофт», Москва, 1999 г.;

54. Мартынов К.Б., «Анализ использования микросхем корпорации MITEL Semiconductor на российском телекоммуникационном рынке», работа представлена на Всероссийский конкурс;

55. Мартынов К.Б., Кузнецов А.Е., «Перспективная технология беспроводного доступа», Data Communication, №8-9 1999 г;

56. Мартынов К.Б., «Анализ устройств коммутации на основе TDM и ATM», Научно-техническая конференция профессорско-преподавательского состава МТУ СИ, Москва 25-27 января 2000 г.;

57. Мартынов К.Б., «Анализ вопросов интеграции коммутационных устройств», Научно-техническая конференция профессорско-преподавательского состава МТУСИ, Москва 25-27 января 2000 г.;

58. Мартынов К.Б., «Анализ подхода TDM/ATM к разработке коммутаторов», 55 научная сессия РНТО РЭС им. Попова "Радиотехника, электроника и связь на рубеже тысячелетия", Москва, МТУСИ 2000 г.;

59. Мартынов К.Б., «Роль и место технологии DWDM в современных телекоммуникационных сетях», Юбилейная научно-техническая конференция профессорско-преподавательского, научного и инженерно-технического состава, Москва 26 февраля 1 марта 2001 г;

60. Мартынов К.Б., «Маршрутизация вызовов в полностью оптических сетях», 57 научная сессия РНТО РЭС им. Попова, Москва, МТУСИ, 2002 г.;

61. Мартынов К.Б., «Преимущества применения систем WDM в полностью оптических сетях», «ИнформКурьерСвязь» №9, Москва 2002 г;

62. Мартынов К.Б., «Задача оптимальной маршрутизации в полностью оптических сетях», «Электросвязь» №9, Москва, 2002 г.