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

На правах рукописи

Уваров Дмитрий Владиславович

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

Специальность 05.13.13. Телекоммуникационные системы

и компькнерные сети

АВТОРЕФЕРАТ диссертации на соискание ученой сгеиепи кандидата технических наук

Рязань - 2004

Работа выполнена на кафедре систем автоматизированного проектирования вычислительных средств ГОУВПО Рязанская государственная радиотехническая академия.

Научный руководитель: кандидат технических наук, доцент Перелелкин Александр Иванович.

Официальные оппоненты:

доктор технических наук, профессор Витязев Владимир Викторович; кандидат технических наук, доцент Шувнков Владимир Иванович.

Ведущая организация:

Государственный научно-исследовательский институт информационных технологий и телекоммуникаций (ГНИИ ИТТ) «Информика», г. Москва.

Защита состоится 11 марта 2005 г. в 12 часов на заседании диссертационного совета Д 212.211.02 в ГОУВПО Рязанская государственная радиотехническая академия по адресу. 390005, г. Рязань, ул. Гагарина, 59/1.

С диссертацией можно ознакомиться в библиотеке ГОУВПО РГРТА. Автореферат разослан « ^ » января 2005 г.

Отзывы на автореферат в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 390005, г. Рязань, ул. Гагарина, 59/1, Рязанская государственная радиотехническая академия.

Ученый секретарь диссертационного совета

Ъ8оЗЗ>

06? 2 А^

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Г

ловиях отказов отдельных элементов сети, всплесков трафика и локальных перегрузок.

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

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

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

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

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

.-.»♦.»«л ♦•'•>' '

а-с* г*н» {'«*!>•* i

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

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

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

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

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

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

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

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

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

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

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

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

5. Разработан алгоритм поиска оптимальных маршрутов с использованием информации о парных переходах.

6. Приведены доказательство правильности и оценка трудоемкости разработанных алгоритмов.

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

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

• 8-я всероссийская конференция «Нейрокомпьютеры и их применение НКП-2002» с международным участием, 21-22 марта 2002 г., г. Москва.

• Всероссийская научная конференция "Проектирование научных и инженерных приложений в среде МАТЬАВ", 28-29 мая 2002 г., г. Москва.

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

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

Публикации. По теме диссертационной работы опубликовано 13 работ. «Пакет программ имитационного моделирования изменения дерева кратчайших путей в графе» зарегистрирован в Российском агентстве по патентам и товарным знакам (свидетельство № 2004611620).

Внедрение результатов работы. Результаты работы внедрены и используются в составе «Информационной системы управления предприятием М-3», для организации информационного обмена между подразделениями ООО «Клиент-серверные технологии» (г. Москва) и клиентами, а также в учебном процессе ГОУВПО Рязанская государственная радиотехническая академия.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав и заключения. Содержит 196

страниц, 14 таблиц, 33 рисунка. Список литературы состоит из 118 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Приведено описание известных протоколов маршрутизации в вычислительных сетях, таких как IGP, IGRP, E1GRP, BGP, EGP, RIP, NLSP, OSPF, IS-IS и др. Показаны особенности построения современных маршрутизаторов, решаемые задачи и подходы к реализации отдельных функциональных блоков, таких как входные и выходные порты, очереди, коммутационные блоки.

Проведен анализ существующих алгоритмов поиска кратчайших путей из заданной вершины в графе, в частности алгоритмов поиска в ширину. Рассмотрены алгоритмы Дейкстры, Беллмана-Форда, Габова. Для всех алгоритмов приведены краткое описание, особенности реализации и оценки трудоемкости выполнения.

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

потока и для самоподобного трафика.

При рассмотрении задачи управления передачей трафика данных в общем случае имеем конечные множества точек Х„„ Х„, I, ,Х„ и конечные множества дуг А„, /, ,.,А„ (дуги множества |

А, ведут из X, / в X,). Точки множества Х„ называются финальными. Из каждой не финальной точки выходит, по крайней мере, одна дуга. Последовательность дуг образует путь, если начало каждой из них (кроме первой) совпадает с концом предыдущей дуги и последняя дуга оканчивается в Х„. На множестве всех дуг задана функция Сумма значений этой функции по всем дугам пути называется мет- '

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

где х - начало дуги а, у - ее конец. Определим оценку / пути / формулой

/(1)=г(х1П)+д(ат ,)+г(хт ,)+.. +д(ап)+г(хп), где г— функция на точках.

Допустим, что г равно 0 на не финальных точках. Тогда оценкой пути / будет сумма:

Предположим, что выбор дуги в точке х определяет не состояние^, а лишь распределение вероятностей для этого состояния. Каждому а из А, сопоставлено распределение вероятностей р(а\х) на А,. Переход из хеХ,./ в А, определяется выбором. При этом мы выбираем а не из всего А„ а из его подмножества А(х), зависящего от состояния х. На множестве всех управлений задана текущая плата д(а), на множестве финальных состояний - финальная плата г(х).

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

д(а) = у(х)-у(у),

п

/(/)= £<7(д,) + Г(*и).

1=т+1

п

/=1Н +1

пути

/ = х,„ат ,хт х,еХ,, т<1<п; а,еА(х,_,)су1„ т<1<п.

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

Составим математическую модель передачи данных на сетевом уровне. Вычислительная сеть состоит из N узлов V¡,, ..., \т соединенных между собой каналами связи. Для такой сети существует (Ы-!)^ возможных пар узлов источник-адресат. Для сетевого уровня модели взаимодействия открытых систем справедливы следующие предположения:

1. Все каналы связи являются абсолютно надежными.

2. Каждый канал является дуплексным с пропускной способностью, равной С, бит в секунду; если канал связи отсутствует, то С,=0.

3. Все N узлов, соответствующие центрам коммутации пакетов, предполагаются абсолютно надежными.

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

5. Память буферов в узлах принимается бесконечной.

6. Длины всех сообщений независимы и распределены по показательному закону со средним значением ////бит.

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

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

Исходные данные для задачи:

1. Топологическая структура сети передачи данных, представленная в виде графа С=(У,Е), где V - множество вершин, Е- множество ребер.

2. Матрица входных потоков -

3. Пропускные способности каналов связи - ||С,||.

4. Средняя длина пакетов - 1//л.

5. Семейство матриц маршрутов (11' к).

В задаче требуется найти значения селекторов пути с1!к такие, что средняя задержка передачи пакета данных через сеть:

ЦА'11 д

шш

г

1

при выполнении ограничении

4-<с„

И

для альтернативной маршрутизации:

м

0<(Цк<1, ]£<//•* = \,],к=1,2.....N. М>1;

/=1

для фиксированной маршрутизации:

ё!-ке{0.1},],к-1.2,...Л Л/-/,

где

N N М /=I *=I /=1

ГЛ* = 1,1

М N

если 1-й канал входит в / - й

маршрут между узлами уу в противном случае,

М N

Л/, о.

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

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

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

разом:

/

1-Я Л

И д

шт Т = тт V —— 1 +

{»с,

н

\

где Н - параметр Херста.

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

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

Представим вычислительную сеть в виде неориентированного, взвешенного связного графа 0=(У,Е,№), где V - множество вершин, Е- множество ребер, Ж- множество весов ребер. Элементы множества Е будем обозначать через е,(/ при условии, что это ребро инцидентно вершинам V/ и V;. Пусть я;,, есть путь из V, в г„ у„у, еУ с длиной при условии, что такой путь существует. Полагаем

длину пути равной сумме весов ребер, его образующих. Для А,ВсУ(А,В) задача отыскания кратчайшего пути заключается в определении самого короткого пути из V, в V, для каждой вершины \>,еВ и у^еА. Задача считается хорошо определенной, если выполняются следующие предположения:

1. Для каждой вершины у,еА и V, еВ существует путь из V,

в v,.

2. Никакой путь из у, в v, не содержит контур отрицательной длины.

Обозначим и>(/ значение веса ребра, которое будет равно значению метрики линии связи между узлами вычислительной сети, обозначенными вершинами у, и V,; пм?п - новое значение веса, полученное в результате изменения значения метрики линии связи. Вершина VJ располагается ниже по иерархии дерева кратчайших путей относительно V,.

Будем называть V/,—путем совокупность подмножества

У*п> аУ вершин, через которые проходит кратчайший путь до вершины ух из исходной вершины V,, и подмножества е!п> сЕ ребер, составляющих этот путь.

Назовем К4-деревом Тк совокупность подмножества У/П! сУ, состоящего из всех вершин, кратчайшие пути до которых из исходной вершины содержат вершину V* и подмножества Е/Ук>сЕ ребер, составляющих эти пути после ук при движении от вершины V,.

Множество ребер дерева Ет -множество ребер дерева Г, для графа й. Для заданного графа С, согласно свойству дерева, мощность множества £/ будет равняться мощности множества V минус единица ||£7'||=||И||-/.

Множество ребер замены для дерева Ея - множество ребер графа С, не вошедших в дерево Г,.

Теорема 1. Если пм>ч>м>ц и ечеЕ/, то изменению могут подвергнуться кратчайшие пути и оценки их длин для вершин К,™.

Теорема 2. Если т/ы<м>ц и е^еЕ/, то без изменения останутся кратчайшие пути для вершин множества VеУ/^ и У а для вершин множества V (У° неизменными останутся и оценки длин кратчайших путей.

Теорема 3. Если и еие Е/, то исходное дерево крат-

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

Теорема 4. Если гмч<и>у и еч0 Ето без изменения останутся кратчайшие пути и оценки их длин для вершин множества V

Использование доказанных выше теорем позволило разработать алгоритм, уменьшающий размерность задачи поиска кратчайших путей в условиях, когда пропускная способность линий связи динамически меняется. Верхняя оценка трудоемкости алгоритма равна /ЭД|К||||£|[Л нижняя оценка - 0(1). Верхняя оценка предлагаемого алгоритма равна соответствующей оценке алгоритма Беллмана-Форда. Нижняя оценка не зависит от размерности задачи.

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

При соответствующих условиях некоторое ребро еч еЕК, инцидентное вершинам V, и V,, может перейти во множество ребер дерева £/, заменив собой некоторое ребро екреЕг. При этом инцидентность ребра ек,Р вершине V, или V, является обязательным условием. В

свою очередь, ребро еч перейдет во множество £«.

Будем называть такие переходы парными переходами и обозначать еч- екр.

Маршрутная степень вершины - число неповто-

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

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

становится ребром замены и переходит во множество Ея

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

Отношение парного перехода г, - отношение соответствия элемента еч множества Е/ элементу екр множества Ек такое, что при увеличении веса ребра еу так, что и'у> м,,], имеет место парный переход еи-екр.

Теорема 6. Для любого ребра ек.реЕц, находящегося в отношении парного перехода с некоторым ребром еч еЕу с заданной точкой вхождения в дерево и>,/ существует такое значение веса что при ук.р< \vicj ребро екр становится веткой дерева Тч и переходит во множество Е-1

Теорема 7. Для элементов парного отношения г, ечеЕч и екреЕК при известной точке вхождения в дерево и-,/ и ч!кр справедливо, что м>к,р-

Следствие I. Если для элементов парного отношения г„ ечеЕ1 и екр еЕК, соответствующих весов м>ч и мкр при известной точке вхождения в дерево м>кр изменился вес ребра еч до значения и'¡, то м^кр =

Следствие 2. Если для элементов парного отношения г„ ечеЕт и екр еЕц, соответствующих весов м?^ и м>к р при известной точке вхождения в дерево изменился вес ребра екр на значения м>2, то м'ц'+^гщ.р).

Теорема 8. Ребра еч еЕ, и екреЕК, находящиеся в одном отношении инцидентны одной и той же вершине v, при условии, что v, является листом дерева кратчайших путей.

Множество ребер замены Ея для дерева - это такое подмножество множества ЕК, элементы-ребра которого участвуют, по крайней мере, в одном отношении парного перехода.

Множество непарных ребер ЕР - это такое подмножество

множества Еп, элементы-ребра которого не участвуют ни в одном отношении из множества /?.

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

Величину ч>кр будем называть точкой вхождения во множество замены для ребра

Теорема 10. Для любого ребра еыеЕц, инцидентного некоторым вершинам у, и vp маршрутные степени которых больше двух, при заданной конфигурации графа, неизменных весах других ребер существуют такое ребро е^р еЕр и такое значение его веса у*>к,р, что при ¡г-Ыкр ребро екр становится ребром замены и переходит во множество Еь

При рассмотрении изменения веса ребра следует выделить 9 случаев в зависимости от принадлежности к интервалам до, и после изменения:

2, .,<>»>,,/; №у'<лн'у<и'/,/

4. т»,.,<\»ц

5. н',./<ям'у<н',1/

6. н',,/<и'у<и'(,/;

8. и^и-у,- ъ>ц<т>ц<\»ц

9. и'(1/>\у//; т^у>и>Л/

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

и В этом случае изменение дерева не требуется и

необходимо просто пересчитать значения в структуре вхождения в дерево. Этому варианту соответствуют случаи 5, 6, 8, 9. В остальных случаях изменения дерева кратчайших путей вероятны.

Использование сформулированных выше теорем позволило разработать алгоритм, вычисляющий оптимальные маршруты до вершин графа без полного повторного построения дерева кратчайших путей. Проведены доказательство правильности и расчет трудоемкости предлагаемого алгоритма. Верхняя и нижняя оценки трудоемкости алгоритма расчета начальной информации соответственно равны ПО/У/^^^/У//) и 0(7/К//?/о^//(//// Верхняя и нижняя оценки трудоемкости алгоритма нахождения кратчайших путей соответст-

венно равны Q(//V//) и ©(//V.'//) К достоинствам предложенного алгоритма относится линейная сложность расчета кратчайших путей в графе из заданной вершины.

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

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

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

В таблице приведены обобщенные статистические характеристики для средней размерности задачи. Здесь СКО обозначено среднеквадратическое отклонение.

Статистические характеристики средней размерности задачи

Минимальное значение Максималь- Математи-

Граф ное значе- ческое ожи- СКО

ние дание

№10 3,347 4,81 4,234 0,2711

||V||=10, полный 3,48 4,87 4,135 0,2764

№100 39,19 57,47 47,18 3,846

||V||=100, полный 38,24 62,11 48,4 4,52

l|V||=500 173,1 306,5 248,4 25,71

||V||=500, полный 188,3 346,7 245,2 27,21

Были проведены эксперименты для графов, состоящих их 10, 100 и 500 вершин. Исследование алгоритма уменьшения размерности задачи поиска кратчайших путей показало, что математическое ожидание размерности задачи не превышает половины объема исходной задачи, максимальное значение не превышает исходной размерности задачи. На основе этого можно сделать вывод, что предложенный алгоритм уменьшения размерности задачи поиска кратчайших путей является эффективным при поиске оптимальных маршрутов в условиях изменения весов ребер графа.

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

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

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

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

1. Построена графоаналитическая модель управления передачей телекоммуникационного трафика в корпоративной вычислительной сети. Рассмотрены детерминированное и случайное управления. Построена модель управляемого марковского процесса передачи данных.

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

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

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

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

6. Разработан пакет программ для исследования предложенных алгоритмов. Проведено исследование корректности и трудоемкости алгоритмов.

Публикации по теме диссертации

1. Елкин Д.В. Применение нейронных сетей для решения задачи маршрутизации в вычислительных сетях с пакетной обработкой данных // Труды 8-й всероссийской конференции «Нейрокомпьютеры и их применение НКП-2002» с международным участием. М.: ИПУ РАН. 2002. С. 216-218.: ил.

2. Елкин Д.В., Перепелкин А.И. Аспекты моделирования процессов маршрутизации в вычислительных сетях // Межвуз. сб. научн. трудов «Математическое и программное обеспечение вычислительных систем»: Рязань, 2002. С. 71-73.

3. Уваров Д.В. Алгоритм нахождения парных переходов // Тезисы докладов 9-й всероссийской научно-технической конференции студентов, молодых ученых и специалистов Новые информационные технологии в научных исследованиях и в образовании НИТ-2004: Рязань: Рязанская государственная радиотехническая академия, 2004. С.72-73.

4. Уваров Д.В. Алгоритм обработки изменения веса ребра графа на основе информации о парных переходах // Тезисы докладов 9-й всероссийской научно-технической конференции студентов, молодых ученых и специалистов Новые информационные технологии в научных исследованиях и в образовании НИТ-2004: Рязань: Рязанская государственная радиотехническая академия, 2004. С.74-75.

5. Уваров Д.В. Нахождение кратчайших путей в графе после увеличения веса ребра, входящего в кратчайший путь // Тезисы докладов 8-й всероссийской научно-технической конференции студентов, молодых ученых и специалистов Новые информационные технологии в научных исследованиях и в образовании НИТ-2003: Рязань: Рязанская государственная радиотехническая академия, 2003. С.77-78.

6. Уваров Д.В. Определение условий возникновения и принципов обработки парных переходов ребер в графе в задаче поиска крат-

чайших путей // Межвуз. сб. научн. трудов Новые информационные технологии: Рязань, 2004. С. 55-60.

7. Уваров Д.В. Постановка задачи выбора маршрутов передачи данных в вычислительной сети // Межвуз. сб. научн. тр. Новые информационные технологии: Рязань, 2002. С. 30-32.

8. Уваров Д. В. Построение дерева кратчайших путей в графе после уменьшения веса ребра, не участвующего в формировании кратчайших путей // Тезисы докладов 8-й всероссийской научно-технической конференции студентов, молодых ученых и специалистов Новые информационные технологии в научных исследованиях и в образовании НИТ-2003: Рязань: Рязанская государственная радиотехническая академия, 2003. С.79-80.

9. Уваров Д.В. Применение релаксационных нейронных сетей для решения задач поиска кратчайших путей в графе // Тезисы докладов Всероссийской научной конференции "Проектирование научных и инженерных приложений в среде МАТЬАВ" (28-29 мая 2002 г.). М.: ИПУ РАН, 2002. 207 е.: ил.

10. Уваров Д.В. Сокращение размерности задачи поиска кратчайших путей в условиях изменения пропускной способности линий связи // Межвуз. сб. научн. трудов Новые информационные технологии: Рязань, 2004. С. 52-54.

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

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

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

14. Свидетельство об официальной регистрации программы для ЭВМ № 2004611620. Пакет программ имитационного моделирования изменения дерева кратчайших путей в графе/ Уваров Д.В., Перепелкин А.И. Зарегистрировано в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам 05.06.2004.

Уваров Дмитрий Владиславович

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 30.12.2004. Формат бумаги 60x84 1/16. Бумага офсетная. Печать трафаретная. Усл. неч. л. 1,0. Уч.-изд. л. 1,0. Тираж 100 экз.

Рязанская государственная радиотехническая академия 390005, г. Рязань, ул. Гагарина, 59/1. Редакционно-издательский центр РГРТА.

ü-1695

РНБ Русский фонд

2005-4 38093

Введение.

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

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

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

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

1.4. Протоколы маршрутизации.

1.5. Устройство маршрутизатора.

1.6. Поиск в ширину.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Проведено доказательство правильности и оценка трудоемкости разработанных алгоритмов.

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

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

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

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

• поиск кратчайших путей на графе с использованием алгоритмов Дейкстры и Беллмана-Форда;

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

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

• оценка трудоемкости (количества действий) алгоритма.

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

• использованием выводов теории управляемых процессов;

• применением выводов теории систем и сетей массового обслуживания, теории вероятностей и статистики;

• использованием результатов теории самоподобных стохастических процессов;

• применением положений теории графов;

• использованием выводов теории алгоритмов;

• имитационным моделированием и сравнением полученных результатов с рассчитанными параметрами.

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

• 8-я Всероссийская конференция «Нейрокомпьютеры и их применения» НКП-2002 с международным участием 21-22 марта 2002 г., г. Москва.

• Всероссийская научная конференция "Проектирование научных и инженерных приложений в среде MATLAB" 28-29 мая 2002 г., г. Москва.

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

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

Публикации. По теме диссертационной работы опубликовано 13 работ.

Пакет программ имитационного моделирования изменения дерева кратчайших путей» зарегистрирован в Российском агентстве по патентам и товарным знакам (свидетельство № 2004611620).

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав и заключения. Содержит 196 страниц, 14 таблиц, 33 рисунка. Список литературы состоит из 118 наименований.

Результаты работы были внедрены на предприятии ООО «Клиент серверные технологии - М-3» в составе «Информационной системы управления предприятием М-3», а также для организации информационного обмена между подразделениями предприятия и клиентами. Применение методики уменьшения размерности задачи и методов обработки изменения значения метрики связи обеспечило повышение оперативности и надежности передачи информации до получателей.

Заключение

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

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

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

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

1. Выбор единственного кратчайшего пути по критерию минимизации оценки пути.

2. Использование одного или нескольких маршрутов с одинаковыми оценками, которые являются минимальными для заданной сети.

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

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

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

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

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

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

Введено понятие парного перехода и точки вхождения ребра в дерево кратчайших путей. Сформулированы и доказаны теоремы, определяющие условия срабатывания парных переходов ребер графа. Операция обработки изменения веса ребра графа представлена как процедура выполнения парных переходов ребер графа. На основе выводов сформулированных теорем разработан алгоритм расчета и выбора парных переходов. Проведено доказательство правильности и расчет трудоемкости предлагаемого алгоритма. Верхняя и нижняя оценки трудоемкости соответственно равны Q(N) и 0(N). Разработан программный комплекс для оценки эффективности выполнения функций маршрутизации в вычислительных корпоративных сетях. Предлагаемые в работе алгоритмы были реализованы на языке Object Pascal. При проектировании программного комплекса применялся модульный принцип построения. При разработке программного обеспечения использовался объектно-ориентированный подход к проектированию программных систем с использованием техники паттернов, что позволило добиться максимально возможной степени повторного использования проектных решений. Было проведено исследование работы предлагаемых алгоритмов. При этом основное внимание уделялось оценке корректности работы алгоритмов и размерности решаемой задачи. Для каждого эксперимента было найдено математическое ожидание и среднее квадрати-ческое отклонение для размерности задачи.

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

2. Альянах И.Н. Моделирование вычислительных систем. Д.: Машиностроение. Ленингр. отд-ние, 1988. - 233 с.

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

4. Ахо А. и др. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман: пер с англ. М.: Мир, 1979. - 356 с.

5. Баженова И.Ю. Delphi 5. Самоучитель программиста. М.: КУДИЦ-ОБРАЗ, 2000. - 335 с.

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

7. Бобровский С.И. Delphi 5. Начальный курс. М.: ДЕСС, 1999. -271 с.

8. Буч Г. и др. Язык UML. Руководство пользователя: Пер. с англ./ Буч Г., Рамбо Д., Джекобсон А. М.: ДМК, 2000. - 429 с.

9. Буч Г. Объектно-ориентированный анализ и проектирование с примерами на С++/Пер. с англ. под ред. Романовского И. А., Андреева Ф. Г.- 2-е изд. М.: БИНОМ, 2001. -558 с.

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

11. В.Г. Олифер, Н.А. Олифер. Компьютерные сети. Принципы, техно-(iф логии, протоколы. СПб.: Питер, 2001. - 672 е.: ил.

12. Ванг Ж. Маршрутизация обретает интеллектуальность. // Журнал сетевых решений/ LAN. 2002. - № 6. - с. 73-77

13. Вентцель Е.С. Теория вероятностей: Учебник для вузов. 8-е изд., стереотип. - М.: Высшая школа, 2002. - 576 с.

14. Вентцель Е.С., Овчаров J1.A. Прикладные задачи теории вероятностей. М.: Радио и связь, 1983. - 416 с.

15. Ф 16. Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и ее инженерные приложения: Учеб. Пособие для втузов. 2-е изд., стереотип. - М.: Высшая школа., 2000, 383 с.

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

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

18. СПб: Питер, 2003. -368 е.: ил.

19. Гнеденко Б.В. Курс теории вероятностей: Учеб. 7-е изд., испр. -М.: Эдиториал УРСС, 2001.-318 с.

20. Гофман В. К., Хомоненко А. В. Delphi 5. СПб.: М.: Минск: Питер, 2001.-560 с.

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

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

23. Дарахвелидзе П.Г. и др. Программирование в Delphi 5/ Дарахвелид-зе П.Г., Марков Е.П., Котенок О. Е. СПб.: БХВ-Санкт-Петербург, 2000. - 774 с.

24. Дынкин Е. Б., Юшкевич А.А. Управляемые марковские процессы и (ф их приложения. М.: Наука, 1975. - 33 8 с.

25. Елкин Д.В., Перепелкин А.И. Аспекты моделирования процессов маршрутизации в вычислительных сетях // Межвуз. сб. научн. трудов «Математическое и программное обеспечение вычислительных систем». Рязань, 2002. С. 71-73.

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

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

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

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

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

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

32. Кениг Д., Штойян Д. Методы теории массового обслуживания / Пер.

33. Ф с нем. В. Ф. Матвеева, Р. Ш Нагапетяна; под ред. Г.П. Климова. М.:

34. Радио и связь, 1981. 127 с.

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

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

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

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

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

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

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

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

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

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

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

46. Кульгин М.В. Коммутация и маршрутизация IP/IPX трафика, АйТи. -М.: КомпьютерПресс. 1998. 320с.

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

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

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

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

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

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

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

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

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

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