Разработка и исследование модели алгоритма динамической маршрутизации для сетей GMPLS
Диссертация
Успех MPLS дал толчок для создания универсальной технологии коммутации с использованием меток. Новая технология получила название Generalized MPLS (GMPLS — обобщенный MPLS). Она расширяет и унифицирует функции (маршрутизации и сигнализации) MPLS для любых транспортных технологий канального и физического уровней. В частности, появление технологии плотного волнового мультиплексирования (Dense… Читать ещё >
Содержание
- Основные обозначения и сокращения
- Глава 1. Анализ существующих методов и алгоритмов распределения информационных потоков
- 1. 1. Промышленные протоколы маршрутизации-. ! ' ' '
- 1. 111 Дистанционно-векторный протокол RIP
- 1. 1. 2. Протокол состояния связей OSPF
- 1. 1. 3. Протокол EIGRP
- 1. 2. Графовые алгоритмы поиска оптимальных маршрутов
- 1. 2. 1. Алгоритм Дейкстры
- 1. 2. 2. Алгоритм Флойда
- 1. 2. 3. Поиск К-кратчайших путей (метод Дж. Иена)
- 1. 2. 4. Задача о максимальном потоке в сети
- 1. 2. 5. Задача нахождения потока наименьшей стоимости
- 1. 3. Расчет маршрутов методами математического программирования
- 1. 3. 1. Формулирование сетевых задач в терминах связей и путей
- 1. 3. 2. Формулирование сетевых задач в терминах узлов и связей
- 1. 3. 3. Решение некоторых сетевых оптимизационных задач методом математического программирования
- 1. 4. Методы реализации многопутевой маршрутизации. Технология MPLS
- 1. 4. 1. Протокол распространения меток LDP
- 1. 4. 2. Задача выбора оптимальных маршрутов
- 1. 4. 3. Технология Traffic Engineering
- 1. 4. 4. Механизмы MPLS, реализующие Traffic Engineering
- 1. 5. Полнооптические сети с коммутацией каналов. Технология GMPLS
- 1. 5. 1. Сеть оптической коммутации блоков (OB S)
- 1. 5. 2. Технология DWDM
- 1. 5. 3. Архитектурные решения коммутационного устройства узла сети
- 1. 5. 4. Алгоритмы установления канала связи
- 1. 5. 5. Существующие методы распределения потоков в сети OBS
- 1. 6. Постановка задачи поиска оптимальных маршрутов в полнооптических сетях с канальной коммутацией
- 1. 7. Выводы по главе 1
- 2. 1. Формулирование оптимизационной-задачи
- 2. 2. Решение оптимизационной задачи градиентным методом
- 2. 3. Решение оптимизационной задачи симплекс-методом
- 2. 4. Алгоритм поиска маршрутов из найденного вектора распределения сетевого трафика
- 2. 5. Разработка алгоритма конроля девиации сетевого потока
- 2. 6. Выводы по главе 2
- 3. 1. Объекты сети оптической коммутации блоков
- 3. 2. Протокол установления маршрутных туннелей CR-LDP
- 3. 3. Алгоритм расчета текущей нагрузки вдоль MP-BGP-сессии
- 3. 4. Повышение отказоустойчивости сети. Алгоритм расчета запасных маршрутов
- 3. 5. Функциональная схема разработанной модели алгоритма динамической> многопутевой маршрутизации
- 3. 6. Оптимизация распределения нагрузки городской сети IP-MPLS Вологодского филиала ОАО «Северо-Западный Телеком»
- 3. 6. 1. Постановка задачи оптимального распределения трафика
- 3. 6. 2. Модификация алгоритма расчета оптимальных маршрутов для сетей с пакетной коммутацией
- 3. 7. Выводы по главе 3
- 4. 1. Разработка модели сети оптической коммутации блоков
- 4. 1. 1. Модуль протокола установления канала связи
- 4. 1. 2. Модуль оптической DWDM-линии
- 4. 1. 3. Модуль фотонного коммутатора, коммутационный алгоритм
- 4. 1. 4. Модуль имитации агента — источника блоков данных
- 4. 1. 5. Сбор статистики и формирование результатов моделирования
- 4. 2. Имитационное моделирование сети оптической коммутации блоков
- 4. 3. Оптимальное распределение трафика в сети IP-MPLS Вологодского филиала ОАО «Северо-Западный Телеком»
- 4. 4. Выводы по главе 4
Список литературы
- Все уже описано. К счастью, не обо всем еще подумано.1. С. Лец
- Голышко А. В., Лескова Н. А. Фотонный транспорт: концепция. // Вестник связи. -№ 12, 2000.
- Иванов П. Оптика в новой ипостаси. // Сети. № 23, 2003.
- Голышко А.В., Лескова Н. А. Оптическая коммутация блоков. // Вестник связи.-№ 8,2001.
- Олифер В., Олифер Н. Искусство оптимизации трафика // Журнал сетевых решений LAN-№ 12, 2001.
- Qiao С., Yoo М. Choices, Features and Issues in Optical Burst Switching // Optical Networking Magazine. Vol.1, No.2, April 2000. — pp. 36−44.
- Qiao C., Yoo M. Optical Burst Switching (OBS): A new paradigm for an Optical Internet. // Journal of High Speed Networks. vol. 8, no. 1., 1999 — pp. 69−84.
- Lisong Xu, Perros H.G., Rouskas G. Techniques for Optical Packet Switching and Optical Burst Switching. // IEEE Communications Magazine. Volume: 39 Issue: 1, Jan. 2001.-Pages: 136−142.
- Павлов И. П. Системы DWDM: особенности и применение. // Сети и системы связи. № 4, 2003.
- Yoo М., Qiao С., Dixit S. QoS Performance of Optical Burst Switching in IP-Over-WDM Networks. // IEEE journal on selected areas in communications. -vol. 18, no. 10.-October 2000.
- Технология волнового мультиплексирования (DWDM) Электронный ресурс. / Корпорация ЮНИ, 2004 Режим доступа: http://www.uni.ru/article/art2536 dwdm. shtml
- Detti A., Listanti М. Application of Tell & Go and Tell & Wait Reservation Strategies in a Optical Burst Switching Network: a Performance Comparison. // Proceedings of IEEE International Conference on Telecommunication (ICT).
- Vol.2, June 2000. pp. 540−548.
- Qiao С., Yoo M. A Novel Switching Paradigm for Buffer-less WDM Networks. // Proceedings of Optical Fiber Communication Conference (OFC). Paper ThM6, Feb. 1999.-pp. 177−179.
- Davie В., Doolan P., Rekhter Y. Switching in IP Networks. Morgan Kaufmann, 1998.
- Awduche D. et al. Multi-Protocol Lambda Switching: Combining MPLS Traffic Engineering Control With Optical Cross-connect. / Internet draft, draft-awduche-mpls-te-optical-01 .txt. Nov. 1999.
- Awduche D. MPLS and Traffic Engineering in IP Networks. // IEEE Commun. Mag., Dec. 1999.
- Papadimitriou Georgios I., Papazoglou Chrisoula, Pomportsis Andreas S. Optical Switching: Switch Fabrics, Techniques, and Architectures // 384 JLT. -Vol. 21, N0.2. Feb 2003.
- Turner J. Terabit Burst Switching. // Journal of High Speed Networks. 1999.
- Ramamirtham J., Turner J. Design of Wavelength Converting Switches for Optical Burst Switching. // WUCS-01−21. Aug 7, 2001.
- Dragone C. An NxN optical multiplexor using a planar arrangement of two star couplers. // IEEE Photonic Technology Letters. vol. 6, Sept. 1991. — pp. 812 815.
- Haselton E. A PCM frame switching concept leading to burst switching network architecture. // IEEE Comm. Magazine. vol. 21, June 1983. — pp. 13−19.
- Amstutz S. Burst switching an introduction. // IEEE Communications Magazine. — vol. 21, Nov. 1983. — pp. 36−42.
- Qiao C. Labeled Optical Burst Switching for IP-over-WDM integration. // IEEE Communications Magazine. Vol.38, No 9, September 2000. — pp. 104−114.
- Ramaswami R., Sivarajan K. N. Optical Networks: A Practical Perspective. -San Francisco: Morgan Kaufmann, 1998.
- Masetti F., et al. Fiber Delay Lines Optical Buffer for ATM Photonic Switching
- Applications. // in Proc. INFOCOM'93. San Francisco, 1993. — pp. 935−942
- Karasan E., Ayanoglu E. Effects of Wavelength Routing and Selection Algorithms on Wavelength Conversion Gain in WDM Optical Networks. // IEEE/ACM Trans. Networking. № 6, 1998.
- Kovacevic, Acampora A. On Wavelength Translation in All-optical Networks. // in Proc. INFOCOM'95. Boston, 1995. — pp. 413−422
- Subramaniam S., Barry R. Wavelength Assignment in Fixed Routing WDM Networks. // in Proc. ICC'97. Montreal, 1997. — pp. 406−415.
- Blumenthal D. J., et al. Photonic Packet Switches: Architecture and Experimental Implementations. // in Proc. of the IEEE, 82. 1994. — pp. 16 501 667.
- Park Jae-Hyun, et al. The Deflection Self-Routing Banyan Network: A Large-Scale ATM Switch Using the Adaptive Self-Routing and its Performance Analyses. // IEEE/ACM Trans. Networking, 7. 1999. — pp. 588−604.
- Varvarigos E. A., et al. A Virtual Circuit Deflection Protocol. // IEEE/ACM Trans. Networking, 7. 1999. — pp. 335−349.
- Dutta R. and Rouskas G. N. A survey of virtual topology design algorithms for wavelength routed optical networks. // Optical Networks. № 1(1). — January 2000.-pp. 73−89.
- Baresi M., Bregni S., Pattavina A., Vegetti G. Deflection Routing in Full-Optical IP Switching Networks. // in Proc. of the IEEE ICC 2003.
- Chen Y., Wu H., Hu D., Qiao C. Performance Analysis of Optical Burst Switched Node with Deflection Routing. // in Proc. of the IEEE ICC 2003.
- Dueser M., Bayvel P. Analysis of a Dynamically Wavelength-Routed Optical Burst Switched Network Architecture. // Journal of Lightwave Technology. -vol. 20. April 2002. — pp. 574−585.
- Липский В. Комбинаторика для программистов: Пер. с польск М.: Мир, 1988.-213с. ил.
- Goldberg А. V. Combinatorial Optimization Lecture Notes for CS363/OR349.
- Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974 -519с.
- Форд JI. Р., Фалкерсон Д. Р. Потоки в сетях. М.: Мир, 1966.
- Диниц Е. А. Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой // Докл. АН СССР. 1970. — Т. 194, N 4. — С. 754−757
- Карзапов А. В. Нахождение максимального потока в сети методом предпотоков // Докл. АН СССР. 1974. — Т. 215, N 1. — С. 49−52.
- Goldberg А. V., Tarjan R. Е. A New Approach to the Maximum Flow Problem. // J. Assoc. Comput. Mach. № 35. 1988. — pp. 921−940
- Goldberg A. V., Rao S. Length functions for flow computations. // Technical report #97−055: NEC Research Institute. 1997.
- Черкасский Б.В. Алгоритм построения максимального потока в сети с трудоемкостью 0(|V|"W|E|) действий // Математические методы решений экономических задач. Сб. 7. М.: ВНИИСИ, 1977. — С. 117−126.
- Элиас П., Фанстейн А., Шеннон К. О максимальном потоке через сеть. // Работы по теории информации и кибернетике. М.: Изд-во иностр. лит., 1963.-с. 729−734.
- Dijkstra Е. W. A note on two problems in connection with graphs. // Numerische Mathematik, 1. 1959. — p. 269.
- Bennington G. E., An efficient minimal cost flow algorithm, Report № 75, Department of Industrical Engineering, North Carolina State University at Raleigh. 1972.
- Bray J. A., Wizgall C., Algorithm 336 NETFLOW, Comm. of ACM, 11, 1961. -p. 631.
- Busacker R. G., Gowen P. J., A procedure for determining a family of minimal-cost network flow patterns, Operations Research Office, Technical paper 15. -1961
- Ford L. R., Fulkerson D.R., Flows in networks, Princeton University Press, Princeton. 1962.
- Klein M., A primal method for minimal cost flows with applications to the assignment and transportation problems, Man. Sci., 14, 1967. p. 205.
- Johnson E. L. On shortest paths and sorting. // Proc. of Annual Conf. of ACM. -Boston, 1972-p. 510.
- Ahuja R. K., Magnanti T. L., Orlin J. B. Network Flows: Theory, Algorithms, and Applications. // Prentice Hall, Englewood Cliffs, N.J. 1993.
- Лившиц Б. С., Пшеничников А. П., Харкевич А. Д. Теория телетрафика. -Учебник для вузов. 2-е изд., перераб. и доп. М.: Связь, 1979. — 224 е., ил.
- Астафьев Н. Н. Линейные неравенства и выпуклость. М.: Наука, 1982. -153с.
- Ашманов С. А., Тимохов А. В. Теория оптимизации в задачах и упражнениях. М.: Наука, 1991. — 448 с.
- Baldine I., Cassada М., Bragg A., Karmous-Edwards G., Stevenson D. Just-in-time optical burst switching implementation in the ATDnet all-optical networking testbed. // In Proceedings of Globecom 2003, volume 5. San Francisco, USA. — December 2003.
- Демьянов В. Ф., Васильев Л. В. Недифференцируемая оптимизация. М.: Наука, 1981.-383 с.
- Еремин И. И., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976. — 192 с.
- Bannister J., Borgonovo F., Fratta L., and Gerla M. A performance model of deflection routing in multibuffer networks with nonuniform traffic. // IEEE/ACM Transactions on Networking, 3(5):509−520. October 1995.
- Bellman R. On the approximation of curves by line segments using dynamic programming. // Communications of the ACM, 4(6):284. June 1961.
- Chen Y., Qiao C., Yu X. Optical burst switching: A new area in optical networking research. // IEEE Network, 18(3): 16−23. May/June 2004.
- Андронов A. M., Копытов E. А., Гринглаз Л. Я. Теория вероятностей и математическая статистика. Учебник для вузов. СПб.: Питер, 2004.461с.: ил.
- Антонов А. В. Системный анализ. Учеб. для вузов М.: Высш. шк., 2004. -454 е.: ил.
- Моисеев Н. Н. Математические задачи системного анализа. — М.: Наука. 1981.-488 с.
- Таха Хэмди А. Введение в исследование операций, 6-е издание. -Издательский дом «Вильяме». 2001. — 912 с.
- Канторович J1.B. Функциональный анализ-и прикладная математика. // Успехи мат. наук.— 1948.—Т. 3, № 6.—С. 89−185.
- Данциг Дж. Б. Линейное программирование, его применение и обобщения. М.: Прогресс. — 1966. — 600 с.
- Уолрэнд Дж. Телекоммуникационные и компьютерные сети. Вводный курс. М.: Постмаркет, 2001. — 480 с.
- Ершов М. А., Кузнецов Н. А. Теоретические основы построения сети с интеграцией служб. М.: ИППИ РАН, 1995.
- Лагутин В. С., Степанов С. И. Телетрафик мультисервисных сетей связи. -М.: Радио и связь, 2000. 320 с.
- Гмурман В. Е. Теория вероятностей и математическая статистика. Учеб. пособие для вузов. 8-е изд., стер. — М.: Высш. шк., 2002. — 479 с.
- Вентцель Е. С., Овчаров Л. А. Теория случайных процессов и ее инженерные приложения. Учеб. пособие для втузов. 2-е изд., стер. — М.: Высш. шк., 2002. — 383с.
- Трифонов А. Г. Постановка задачи оптимизации и численные методы ее решения. Электронный ресурс. Режим доступа: http://www.nsu.ru/matlab/MatLab RU/optimiz/book 1 /index.asp.htm
- Аоки M. Ведение в методы оптимизации. М.: Наука. 1977. 344с.
- Бояринов А. И., Кафаров В. В. Методы оптимизации в химической технологии. М.: Химия. — 1975. — 576с.
- Голыитейн Е. Г., Юдин Д. Б. Задачи линейного программированиятранспортного типа. М.: Наука, 1969. — 382с.
- Фурунжиев Р. И., Бабушкин Ф. М., Варавко В. В. Применение математических методов и ЭВМ: Практикум. Мн.: Выш.шк. — 1988. — 191с.
- Кирьянов Д. В. Самоучитель MathCad 2001. СПб.: БХВ-Петербург. -2002. — 544с.
- Хинчин А. Я. Три жемчужины теории чисел. М.: Наука. — 1979.
- Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир. -1978.-432 е., ил.
- Pioro М., Medhi D. Routing, Flow, and Capacity Design in Commu-nication and Computer Networks. Morgan Kaufmann. — 2004.
- Yen J.Y. Finding the K-shortest, loopless paths in a network. // Man. Sci., 17. -1971.-p. 712.
- Беллман P., Дрейфус С. Прикладные задачи динамического программирования. М., 1965. -460с., ил.
- Кельтон В., Jloy А. Имитационное моделирование. Классика CS. 3-е изд. -СПб.: Питер- Киев: Издательская группа BHV. 2004. — 847 е.: ил.
- Березко М. П., Вишневский В. М., Левнер Е. В., Федотов Е. В. Математические модели исследования алгоритмов маршрутизации в сетях передачи данных. // Информационные процессы, Том 1. № 2, 2001. — стр. 103−125.
- Клейнрок Л. Коммуникационные сети. М.: Наука, 1975.
- Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979.
- Шварц М. Сети ЭВМ. Анализ и проектирование. М.: Радио и связь, 1981.
- Бертсекас Д., Галлагер Р. Сети передачи данных. М.: Мир, 1989.
- Дэвис Д., Барбер Д., Прайс У., Соломонидес С. Вычислительные сети и сетевые протоколы. М.: Мир. — 1981.
- Мизин И. А., Богатырев В. А., Кулешов А. П. Сети коммутации пакетов. -М.: Радио и связь. 1986.
- Jackson J. R. Networks of Waiting Lines. // Operations Research, № 5. 1957.pp. 518−521.
- Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. М.: Наука. — 1987.
- Fratta L., Gerla М., Kleinrock L. The Flow Deviation Method: An Approach to Store-and-Forward Communication Network Design. // Networks, vol. 3, № 2. -1973.-pp. 97−133.
- Jackson J.R. Networks of Waiting Lines. // Operations Research, № 5.- 1957 -pp. 518−521.
- Cantor D. G, Gerla M. Optimal Routing in a Packet-Switched Computer Network. IEEE Trans. // Computers, vol. C-23, № 10. 1974. — pp. 1062−1068.
- Schwartz M., Cheung C.K. The Gradient Projection Algorithm for Multiple Routing in Message-Switched Networks. // IEEE Trans. Commun., vol. COM-24, № 4. 1976. — pp. 449−456.
- Gerla M., Kleinrock L. On the Topological Design of Distributed Computer Networks. // IEEE Trans. Commun., vol. COM-25, № 1. 1977. — pp. 48−53.
- Frank M., Wolfe P. An Algorithm for Quadratic Programming. // Naval Research Logistic Quarterly, № 3. 1956. — pp. 95−110.
- Floyd R. W. Algorithm 97: Shortest Path. Comm. // ACM, № 3. 1962 — p. 345.
- Murchland J. D. A965), A new method for finding all elementary paths in a complete directed graph, London School of Economics, Report LSE-TNT-22.
- Федотов E. В. Определение оптимальных маршрутов в сети пакетной коммутации. // В сборнике: Сетевая обработка информации. М.: МДНТП, 1990.-стр. 95−98.
- Gavish В., Hantler S. L. An Algorithm for Optimal Route Selection in SNA Networks. // IEEE Trans. Commun., vol. COM-31, № 10. 1983. — pp. 11 541 161.
- Courtois P. J., Semal P. An Algorithm for the Optimization of Nonbifurcated Flows in Computer Communication Networks. // Performance Evaluation, vol. 1. 1981.-pp. 139−152.
- Вишневский В. М., Федотов Е. В. Анализ методов маршрутизации при проектировании сетей пакетной коммутации. // 3rd I.S. «Teletraffic Theory and Computing Modeling». София. — 1990.
- Мину M. Математическое программирование. Теория и алгоритмы. М.: Наука, — 1990.
- Поляк Б. Т. Введение в оптимизацию. М.: Наука. — 1983.
- Held М., Wolfe P., Growder Н.Р. Validation of Subgradient Optimization. // Mathematical programming, № 6. 1974. — pp. 62−88.
- Dijkstra E. W. A Note on Two Problems in Conection with Graphs. // Numer. Math., № 1.- 1959. pp. 269−271.
- Land A.H., and Doig A.G. An autmatic method of solving discrete programming problems. // Econometrica, v28. 1960. — pp 497−520.
- Little J.D.C., Murty K.G., Sweeney D.W., and Karel C. An algorithm for the traveling salesman problem. // Operations Research, vl 1. 1963. — pp. 972−989.
- Корбут А.А., Финкелыптейн Ю. Ю. Дискретное программирование. M. Наука. Гл. ред. физ.-мат. лит. 1969.
- Зайченко Ю. П. Задачи проектирования структуры распределенных вычислительных сетей. // Автоматика, № 3. 1981. — С. 35−44.
- Жожикашвили В. А., Вишневский В. М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь. — 1988.
- Нижарадзе Т. 3. Алгоритм оптимальной маршрутизации в сетях оптической коммутации блоков // Информационные технологии моделирования и управления № 6(24). Воронеж: науч.-техн. журнал, 2005 — С. 872−877.
- Нижарадзе Т. 3., Суконщиков А. А. Метод оптимального распределения трафика в сетях оптической коммутации блоков // Информационно-вычислительные технологии и их приложения. Пенза: РИО ПГСХА, 2005. -С. 152−155.
- Нижарадзе Т. 3. Моделирование сетей оптической коммутации блоков с использованием пакета Network Simulator 2. // Кибернетика и высокие технологии XXI века: Материалы VII межд. науч.-техн. конф.т.2. -Воронеж, 2006. — С. 773-781.
- Нижарадзе Т. 3. Алгоритм многопутевой маршрутизации в сетях оптической коммутации блоков. // Системы управления и информационные технологии № 2.1(24) Воронеж: науч.-техн. журнал, 2006-С. 167−170.
- Сетевой симулятор ns-2 Электронный ресурс. Электрон, докум. и прогр. — Режим доступа: http://www-mash.CS.Berkeley.EDU/ns.
- Официальный сайт проекта VINT Электронный ресурс. .- Режим доступа: http://www.isi.edu/nsnam/vint/index.html
- Вопросы развертывания MPLS-TE Электронный ресурс. .- Режим доступа: http://www.cisco.com/en/US/tech/tk436/tk428/technologies white рарег9 186а00800a4472. shtml#wp39803