Методы и алгоритмы адаптивной маршрутизации в корпоративных вычислительных сетях тема диссертации и автореферата по ВАК РФ 05.13.13, кандидат технических наук Перепелкин, Дмитрий Александрович

• Перепелкин, Дмитрий Александрович
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Перепелкин, Дмитрий Александрович

Введение.

Глава 1. Основные принципы маршрутизации в корпоративных вычислительных сетях.

1.1. Цели и задачи маршрутизации.

1.2. Методы маршрутизации.

1.3. Классификация методов маршрутизации.

1.4. Алгоритмы поиска кратчайших путей.

1.5. Протоколы адаптивной маршрутизации.

1.6. Алгоритмы адаптивной маршрутизации.

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

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

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

Проблемами совершенствования методов и алгоритмов маршрутизации в вычислительных сетях занимались такие ученые, как Д. Бертсекас, Д. Гарсиа-Диас, П. Гупта, А.Б. Гольдштейн, Б.С. Гольдштейн, Д. Кантор, О.Я. Кравец,

Д.В. Куракин, И.П. Норенков, А. Филипс, С. Флойд, Р. Форд, Д. Фулкерсон и другие. Задачу нахождения кратчайших путей в транспортной системе рассматривали в своих трудах ученые Л. Беллман, Г. Габов, С. Гудман, Е. Дейкстра, В.А. Евстигнеев, В.Н. Касьянов, Р. Сэджвик, Р. Тарьян, С. Флойд, Р. Форд, Д. Фулкерсон. Подробное описание методов поиска кратчайших путей можно найти в работах Т. Кормена, Ч. Лейзерсона и Р. Ривеста.

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

На основании всего сказанного можно сделать вывод об актуальности выбранной темы диссертационной работы.

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

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

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

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

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

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

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

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

7) разработать методики применения алгоритмов поиска оптимальных маршрутов с учетом частичных изменений структуры сети на основе информации о возможных парных переходах для протоколов 08РР и ЮМ*.

Методы исследования. Разработка и исследование проводились на основе теории графов, теории алгоритмов, теории матриц, а также компьютерного моделирования.

Научная новизна диссертационной работы заключается в том, что впервые разработаны методы и алгоритмы адаптивной маршрутизации при условии частичного изменения структуры корпоративной вычислительной сети, которые позволяют получить меньшую трудоемкость [0(1V), где N - число узлов в сети] построения таблиц маршрутизации по сравнению с известными алгоритмами.

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

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

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

1) создание и визуальное редактирование графовых моделей корпоративных вычислительных сетей;

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

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

4) оценка трудоемкости разработанных алгоритмов.

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

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

• XII всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании», НИТ-2007. 19 — 21 апреля 2007 г., г. Рязань;

• всероссийской научно-технической конференции «Информационные и телекоммуникационные технологии. Подготовка специалистов для инфоком-муникационной среды» 21-23 апреля 2009 г., г. Рязань.

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

Внедрение результатов работы. Результаты работы внедрены в телекоммуникационной компании «Энлинк Трэйд», г. Рязань, где используются в составе комплекса диагностики и управления состоянием сети «НА1)Т2», а также внедрены в учебный процесс ГОУВПО "Рязанский государственный радиотехнический университет".

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы, приложения, изложенных на 148 с. Список использованной литературы содержит 105 наименований. Текст диссертации содержит 19 таблиц и 30 рисунков.

Заключение диссертации по теме «Телекоммуникационные системы и компьютерные сети», Перепелкин, Дмитрий Александрович

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

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

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

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

121

Заключение

В диссертационной работе были получены следующие результаты:

• проанализированы цели и задачи маршрутизации данных в вычислительных сетях с пакетной обработкой информации. Проведен анализ существующих протоколов адаптивной маршрутизации, в результате чего выявлены достоинства, недостатки и область применения протоколов. Выполнен анализ известных алгоритмов поиска кратчайших путей в графе, применяемых в современных маршрутизаторах. Показано, что трудоемкость современных алгоритмов определения оптимальных маршрутов не менее 0(№), где N - число маршрутизаторов в сети. На основании проведенного анализа сформулированы задачи разработки методов и алгоритмов определения оптимальных маршрутов с трудоемкостью 0(М);

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

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

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

• на основе доказанных теорем и выводов разработаны метод и алгоритм адаптивной маршрутизации с учетом частичных изменений структуры сети в графе сокращенной размерности. Проведены доказательство правильности и расчет трудоемкости предлагаемого алгоритма. Верхняя и нижняя оценки трудоемкости соответственно равны £2(Ы+М) и 0{Ы), где N — число узлов в сети, а М— число связей между ними;

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

• на основе доказанных теорем и выводов разработан метод и алгоритм парных перестановок маршрутов с учетом частичных изменений структуры сети. Проведено доказательство правильности разработанного алгоритма и показано, что его трудоемкость оценивается величиной 0(И), где N - число узлов в сети;

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

Список литературы диссертационного исследования кандидат технических наук Перепелкин, Дмитрий Александрович, 2009 год

1. Адаптивный протокол иерархической маршрутизации // Экспресс — информация. Сер. ПИ. 1990. № 23. с. 9-12.

2. Архангельский А. Я. Приемы программирования в Delphi. М.: БИНОМ. 2003. 784 с.

3. Архангельский А .Я. Delphi 5. Справочное пособие. М.: ЗАО «Издательство БИНОМ». 2001. 768 с.

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

5. Буч Г., Якобсон А. и др. Унифицированный процесс разработки программного обеспечения для профессионалов / Якобсон А., Буч Г., Рамбо Дж. М.: СПб.: Киев: Минск: Питер. 2003. 496 с.

6. В.Г. Олифер, H.A. Олифер. Компьютерные сети. Принципы, технологии, протоколы. СПб.: Питер. 2001. 672 с.

7. Вирт Н. Алгоритмы и структуры данных / Пер. с англ. Подшивалова Д.Б. -2-е изд., испр. Спб.: Невский Диалект. 2001. 351 с.

8. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. Москва. Техносфера. 2003. 512 с.

9. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб: Питер. 2003. 368 с.

10. Ю.Грайнер В. Пополнение среди магистральных маршрутизаторов // Журнал сетевых решений / LAN. 2003. № 8. с. 51-54.

11. П.Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов-М.: Мир. 1981.368 с.

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

13. Иванов Б.Н. Дискретная математика. Алгоритмы и программы / Техн. ун-т. М.: Лаборатория базовых знаний. 2001. 288 с.

14. Казаков В.А. Введение в теорию марковских процессов и некоторые радиотехнические задачи. М.: Сов. Радио. 1973. 231 с.

15. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: Обработка, визуализация и применение. Спб.: БХВ-Петербург. 2003. 1104 с.

16. Кемени Дж. и др. Счетные цепи Маркова / Пер. с англ. A.M. Зубкова, Б.А. Севастьянова. М.: Наука. 1987. 413 с.

17. Кемени Дж., Снелл Дж., Лори Дж. Конечные цепи Маркова / Пер. с англ. С.А. Молчанова и др.; под ред. A.A. Юшкевича. М.: Наука. 1970. 271 с.

18. Кениг Д., Штойян Д. Методы теории массового обслуживания / Пер. с нем. В. Ф. Матвеева, Р. Ш Нагапетяна; под ред. Г.П. Климова. М.: Радио и связь. 1981. 127 с.

19. Клейнрок Л. Вычислительные системы с очередями. М.: Мир. 1979. 600 с.

20. Клейнрок Л. Теория массового обслуживания / Пер. с англ. И.И. Грушко; под ред. В.И. Неймана. М.: Машиностроение. 1979. 432 с.

21. Кнут Д.Э. Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ. М.: Издательский дом «Вильяме». 2001. 720 с.

22. Кнут Д.Э. Искусство программирования, том 3. Сортировка и поиск / Пер. с англ. под общ. ред. Казаченко Ю.В. 2-е изд., испр. и доп. М.: Издательский дом «Вильяме». 2000. 822 с.

23. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Центр непрер.матем. образования. 2000. 960 с.

24. Королев Д.Г. Разработка механизмов определения маршрутов между произвольными точками // Новые информационные технологии. 2001. с. 80-95.

25. Коршунов Ю.М. Математические основы кибернетики: Учеб. пособие для вузов. 3-е изд., перераб. и доп. М.: Энергоатомиздат. 1987. 496 с.

26. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР. М.: Энергоатомиздат. 1987. 400 с.

27. Коваленко И.Н. Случайные процессы: Справочник / И.Н. Коваленко, Н.Ю. Кузнецов, В.М. Шуренков. Киев: Наук, думка. 1983. 366 с.

28. Крейнес А. От Москвы до самых до окраин: маршрутами PNNI // Сети. Глобальные сети и телекоммуникации. 1998. №1. с.16-19.

29. Кравец О.Я., A.B. Пономарев, И.С. Подерский. Повышение эффективности маршрутизации в переходных режимах функционирования вычислительных сетей // Системы управления и информационные технологии. 2003. № 1-2. с.73-77.

30. Кульгин М. В. Технологии корпоративных сетей: Энциклопедия. СПб.: Питер. 2000. 699 с.

31. Кульгин М.В. Коммутация и маршрутизация 1РЛРХ трафика, АйТи. М.: КомпьютерПресс. 1998. 320с.

32. Куракин Д.В. Маршрутизаторы для глобальных телекоммуникационных сетей и реализуемые в них алгоритмы // Информационные технологии. 1996. №2.

33. Куракин Д.В. Маршрутизация в сетях телекоммуникаций, построенных на базе международных стандартов взаимосвязи открытых систем // Автоматизация и современные технологии. 1996. №3. с. 35-43.

34. Куроуз Д., Росс К. Компьютерные сети. Многоуровневая архитектура Интернета: Пер с англ. 2-е изд. М.: СПб.: Питер. 2004. 765 с.

35. Кэнту М. Delphi 5 для профессионалов. СПб.: Питер. 2001. 644 с.

36. Льюис К. RIP: не пора ли на заслуженный отдых? // Сети и системы связи. 1997. №1. с.56-59.

37. Льюис К. Альтернативы протоколу RIP в больших сетях // Сети и системы связи. 1997. №5. с. 58-64.

38. Майника Э. Алгоритмы оптимизации на сетях и графах: Пер. с англ. М.: Мир. 1981. 323 с.

39. Марков A.A., Нагорный Н.М. Теория алгоритмов. М.: Наука. Гл. ред. физико — математ. лит. 1984. 432 с.

40. Матчо Д., Фолкнер Д.Р. Delphi / Под ред. Тимофеева В. М.: БИНОМ. 1996. 464 с.

41. Миллер Б.М., Панков А.Р. Теория случайных процессов в примерах и задачах/ Под ред. Кибзуна А.И. М.: Физматлит. 2002. 320 с.

42. Миллер М. Новый IP: на что он способен? // Сети. №1. с. 24-29.

43. Мину М. Математическое программирование. Теория и алгоритмы: Пер. с фр. И предисловие А.И. Штерна. М.: Наука. Гл. ред. физ-мат. лит. 1990. 488 с.

44. Новиков А.Б. Маршрутизация трафика в IP-сетях с применением генетических алгоритмов // Системы управления и информационные технологии. 2003. №1-2. с. 78-81

45. Норенков И.П., Трудоношин В.А. Телекоммуникационные технологии и сети / Московский государственный технический университет. Москва. 1998. 232с.

46. Нанс Б. Компьютерные сети. М.: БИНОМ. 1995. 400с.

47. Олифер В.Г., Олифер H.A. Новые технологии и оборудование IP-сетей. СПб.: БХВ-Санкт-Петербург. 2001. 512 с.

48. Ope О. Теория графов. 2-е изд. М.: Наука. Главная редакция физико-математической литературы. 1980. 336 с.

49. Перепелкин Д.А., Перепелкин А.И. Разработка алгоритмов адаптивной маршрутизации в корпоративных вычислительных сетях // Вестник Рязанской государственной радиотехнической академии. 2006. № 19. С. 114 116.

50. Перепелкин Д.А. Алгоритмы маршрутизации в локальных сетях // Информационные технологии в образовании: межвуз. сб. науч. тр. РГРТУ.2006. С. 79-81.

51. Перепелкин Д.А., Перепелкин А.И. Разработка алгоритмов адаптивной маршрутизации в корпоративных вычислительных сетях // Информатика и прикладная математика: межвуз. сб. науч. тр. РГУ имени С.А. Есенина. 2008. С. 100- 105.

52. Перепелкин Д.А., Перепелкин А.И. Алгоритмы маршрутизации в корпоративных вычислительных сетях // Информатика и прикладная математика: межвуз. сб. науч. тр. РГУ имени С.А. Есенина. 2008. С. 106 108.

53. Перепелкин Д.А., Перепелкин А.И. Программный комплекс для оценки процессов маршрутизации в корпоративных вычислительных сетях // Информатика и прикладная математика: межвуз. сб. науч. тр. РГУ имени С.А. Есенина, 2008. С. 109 111.

54. Перепелкин Д.А., Перепелкин А.И. Разработка алгоритма динамической маршрутизации на базе протокола OSPF в корпоративных вычислительных сетях // Вестник Рязанского государственного радиотехнического университета. 2009. № 2 (выпуск 28). С. 68 72.

55. Перепелкин Д.А., Кравчук H.B. Применение алгоритмов адаптивной маршрутизации в протоколе IGRP // 13-я Международная телекоммуникационная конференция студентов и молодых ученых «Молодежь и наука». Москва. МИФИ. 2009. http://www.mephi.ru/molod.

56. Поповский В.В., Лемешко A.B., Мельникова Л.И., Андрушко Д.В. Обзор и сравнительный анализ основных моделей и алгоритмов многопутевой маршрутизации в мультисервисных телекоммуникационных сетях // Прикладная радиоэлектроника. 2005. Т.4. № 4. С. 372 382.

57. Пятибратов А.П. и др. Вычислительные системы, сети и телекоммуникации: Учебник. (2-е изд.). ФИС. 1998.

58. Пачеко К., Тейксейра С. Delphi 5. Руководство разработчика: Пер. с англ. Т.1: Основные методы и технологии. М.: Вильяме. 2000. 831 с.

59. Потемкин В.Г. Matlab 6: среда проектирования инженерных приложений. М.: Диалог-МИФИ. 2003. 448 с.

60. Рихтер Дж. Windows для профессионалов: создание эффективных Win32-приложений с учетом специфики 64-разрядной версии Windows / Пер с англ. 4-е изд. СПб: Питер. М.: Издательско-торговый дом «Русская редакция». 2001. 752 с.

61. Саати Т. Элементы теории массового обслуживания и ее приложения / Пер. с англ. Е.Г. Коваленко; под ред. И.Н. Коваленко с предисл. Акад. Б.В. Гнеденко. 2-е изд. М.: Сов. Радио. 1971. 520 с.

62. Саймон P.Windows 2000 API. Энциклопедия программиста: Пер. с англ. / Ричард Саймон. К.: СПб.: ООО «ДиаСофтЮП». 2002. 1088 с.

63. Свами М., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ. М.: Мир. 1984. 455 с.

64. Седжвик Р. Фундаментальные алгоритмы на С. Анализ, структуры данных, сортировка, поиск, алгоритмы на графах: Пер. с англ. СПб.: ООО «ДиалогСофтЮП». 2003. 1136 с.

65. Столлингс В. Современные компьютерные сети. 2-е изд. СПб.: Питер. 2003. 783 с.

66. Танненбаум Э. Компьютерные сети. Спб.: Питер. 2002. 848 с.

67. Трауб Д., Вожняковский X. Общая теория оптимальных алгоритмов / Перевод с англ. А.Г. Сухарева; под ред. Н.С. Бахвалова. М.: Мир. 1983. 382 с.

68. Уваров Д.В. Определение условий возникновения и принципов обработки парных переходов ребер в графе в задаче поиска кратчайших путей // Межвузовский сборник научных статей «Новые информационные технологии». Рязань. 2004. с. 55-60.

69. Уваров Д.В., Перепелкин А.И. Динамический алгоритм маршрутизации в вычислительной сети // Вестник Рязанской государственной радиотехнической академии. Выпуск 12. Рязань. 2003. с. 77-80.

70. Уваров Д.В., Перепелкин А.И. Определение условий использования линии связи при решении задачи маршрутизации в вычислительной сети // Известия Белорусской инженерной академии. 2004. с. 131—134.

71. Уваров Д.В., Перепелкин А.И., Корячко В .П. Построение дерева кратчайших путей в графе на основе данных о парных переходах // Системы управления и информационные технологии. 2004. №4(16). с. 93-96.

72. Успенский В.А., Семенов A.JI. Теория алгоритмов: основные открытия и приложения. М.: Наука. 1987. 288 с.

73. Фардал Р. Как повысить производительность IP-магистрали // Сети. 1998. №5. с. 24-25.

74. Фаронов В.В. Delphi. Программирование на языке высокого уровня: Учебник. М.: СПб.: Питер. 2003. 640 с.

75. Феллер В. Введение в теорию вероятностей и ее приложения. В 2-х т. Т. 1. Перевод с англ. под ред. Ю.В. Прохорова. М.: Мир. 1984. 528 с.

76. Феллер В. Введение в теорию вероятностей и ее приложения. В 2-х т. Т. 2. Перевод с англ. под ред. Ю.В. Прохорова. М.: Мир. 1984. 738 с.

77. Филипс Д. Гарсиа-Диас А. Методы анализа сетей: пер. с англ. М.: Мир. 1984. 496 с.

78. Френк Г., Фриш И. Сети, связи и потоки / Пер. с англ. под ред. Д.А. Поспелова. М.: Связь. 1978. 448 с.

79. Эдди С.Э. XML: Справочник. СПб.: Питер. 1999. 477 с.

80. Brodnik A., Carlsson S., Degemark М., Pink S., «Small Forwarding Tables for Fast Routing Lookups». Proceedings of ACM SIGCOMM '97 (Cannes, France, Oct, 1997). pp. 3-15. http://www.acm.org/sigs/-sigcomm/sigcomm97/papers/pl92.html.

81. Christiansen M., Jeffay K., Ott D., Smith F. D., «Tuning Red for Web Traffic», IEEE / ACM Transactions on Networking. Vol. 9. No. 3 (June 2001). pp. 249-264. http://www.cs.unc.edu/~ieffav/papers/IEEE-ToN-01 .pdf.

82. Cisco Systems Inc. Catalyst 8500 ampus Switch Router Architecture».http://www.cisco.com/univercd/cc/td/doc/pcat/ca8500c.htm.

83. Cisco Systems Inc. «Next Generation ClearChannel Architecture for Catalyst 1900/2820 Ethernet Switches»,http://www.cisco.com/warp/public/cc/pd/si/casi/cal900/tech/nwgenwp.htm.

84. Cisco Systems.«Cisco 12000 Series Gigabit Switch Router~s», http://www.cisco.com/univercd/cc/td/doc/pcat/12000.htm.

85. Floyd S. «References on RED (Random Early Detection) Queue Management», http://www.icir.org/floyd/red.html.

86. Gupta P., Lin S., McKeown N., «Routing lookups in hardware at memory access speeds», Proc. IEEE Infocom 1998 (San Francisco, CA, April 1998), pp. 1241-1248, http://tinytera.stanford.edu/~nickm/papers/ Infocom981ookup.pdf.

87. Gupta P., McKeown N., «Algorithms for Packet Classification», IEEE Network Magazine.Vol. 15. o. 2 (Mar. / Apr. 2001).pp. 24-32, http://klamath.stanford.edu/~pankai-/paps/ieeenetwork tut Ol.pdf.

88. Labrador M., Banerjee S., «Packet Dropping Policies for ATM and IP Networks». IEEE Communications Surveys. Vol. 2. No. 3 (Third Quarter 1999). pp. 2-14. http://www.comsoc.org/livepubs/surveys/public/ 3q99issue/banerjee.html.

89. Leland W., Taqqu M., Willinger W., Wilson D. On the Self-Similar Nature of Ethernet Traffic. Proceedings (Extended Veresion). IEEE/ACM Transactions on Networking. February 1994.

90. RFC-1745. BGP4/IDRP for IP ~ OSPF Interaction. K. Varadhan, S. Hares, Y. Rekhter. December 1994.

91. RFC—1058. Routing Information Protocol. C.L. Hedrick. 1988.

92. RFC—1142. OSIIS-IS Intra-domain Routing Protocol. D. Oran. 1990.

93. RFC—1163. A Border Gateway Protocol (BGP). K. Logheed, Y. Rekhter. 1990.

94. RFC—1247. OSPF Version 2. J. Moy. 1991.

95. RFC—1267. A Border Gateway Protocol 3 (BGP-3). K. Logheed, Y. Rekhter. 1991.

96. RFC—904. Exterior Gateway Protocol Formal Specification. D.L. Mills. 1984.

97. Srinivasan V. and Varghese G. «Fast Address Lookup Using Controlled Prefix Expansion». ACM Transactions Computer Sys. Vol. 17. No. 1 (Feb 1999). pp. 1-40. http://www-cse.-ucsd.edU/-users/varghese/PAPERS/cpeTOCS.ps.Z.

98. Waldvogel M. et al. «Scalable High Speed IP Routing Lookup». Proceedings of ACM SIGCOMM '97 (Cannes, France, Sept. 1997). http://www.acm.org/sigs/-sigcomm/-sigcomm97/-papers/pl 82.html.

99. Williamson C. A Model for Self-Similar Ethernet LAN Traffic: Design, Implementation, and Performance Implications, ftp://ftp.cs.usask.ca/ pub/discus/paper.95-7.ps.Z.

100. Williamson C. Generating Synthetic Traffic Streams for ATM Network Simulations, http://www.cs.usask.ca/faculty/carev/papers/guidelines.ps.

101. Williamson C. Statistical Multiplexing of Self-Similar Network Traffic. http://www.cs.usask.ca/faculty/-carey/papers/statmuxing.ps.

102. Xiaojun H. The Self-Similar Traffic Modeling in the Internet. http://www.ee.ust.hk/~heixj/publication/comp660fi/comp660f.html.1. ЪЪ