Содержание к диссертации
Введение
Глава 1. Принципы маршрутизации в телекоммуникационных сетях 10
1.1. Цели и задачи маршрутизации 12
1.2. Методы маршрутизации 14
1.3. Классификация методов маршрутизации 17
1.4. Протоколы маршрутизации 28
1.5. Устройство маршрутизатора 38
1.6. Поиск в ширину 47
Основные результаты и выводы 53
Глава 2. Математическое моделирование процессов маршрутизации в корпоративных вычислительных сетях 55
2.1. Основные понятия и определения 55
2.2. Управление потоком передачи информации 58
2.3. Постановка задачи поиска оптимальных потоков 73
2.4. Решение задачи поиска оптимальных потоков в вычислительной сети 82
2.5. Рассмотрение задачи маршрутизации в условиях самоподобного трафика 87
Основные результаты и выводы 93
Глава 3. Разработка алгоритмов поиска кратчайших путей 95
3.1. Задача поиска путей 95
3.2. Алгоритм уменьшения размерности задачи поиска кратчайшего пути 103
3.3. Алгоритм парных переходов 122
Основные результаты и выводы 144
Глава 4. Практическая реализация и исследование разработанных алгоритмов 146
4.1. Разработка программного обеспечения 146
4.2. Исследование алгоритмов поиска кратчайших путей на графе 166
Основные результаты и выводы 176
Заключение 177
Библиографический список 181
Приложение 193
- Классификация методов маршрутизации
- Управление потоком передачи информации
- Алгоритм уменьшения размерности задачи поиска кратчайшего пути
- Исследование алгоритмов поиска кратчайших путей на графе
Введение к работе
Актуальность работы. В настоящее время происходит бурный рост корпоративных вычислительных сетей. Необходимость обеспечения качественного обслуживания современного трафика, передаваемого через IP-сети, предъявляет высокие требования к эффективности передачи пакетов данных от отправителя к получателю. Предлагаются различные методы ускорения маршрутизации, поддержки требуемого качества обслуживания, передачи голосового и видео трафика, повышения уровня безопасности сети и т.д.
Загрузка и пропускная способность линий связи вычислительной сети динамически меняется. Традиционно применяемый в корпоративных вычислительных сетях метод статической маршрутизации оказывается в этих условиях неэффективен. Применение современных адаптивных протоколов маршрутизации в ряде случаев наталкивается на проблему быстродействия при решении задачи поиска кратчайших путей. Изменение характеристик линий связи приводит к полному перерасчету оптимальных маршрутов. Эти изменения связаны с увеличением размера сети, включением в нее все новых узлов и подсетей. Изменяются и требования к параметрам обслуживания передаваемого потока информации. Как показали исследования, в ряде случаев удается уменьшить трудоемкость расчета оптимальных маршрутов путем использования дополнительной информации и изменения алгоритма поиска кратчайших путей в графе. Под ускоренной маршрутизацией понимается метод поиска оптимальных маршрутов для передачи пакетов данных от узла-отправителя к узлу-получателю через составную вычислительную сеть в условиях динамически меняющихся значений задержек передачи по линиям связи, позволяющий сократить трудоемкость этой операции за счет использования априорно вычисленной информации и частичного изменения дерева кратчайших путей.
Маршрутизация является неотъемлемой частью составных вычислительных сетей. Осуществление процессов маршрутизации является одной из наиболее важных проблем, возникающих при определении направлений и непосредственной передаче информационных потоков в области современных вычислительных сетей. Особую важность имеет эффективная маршрутизация сообщений в условиях отказов отдельных элементов сети, всплесков трафика и локальных перегрузок.
Имеет место прямая зависимость производительности составной сети от производительности элементов, обрабатывающих межсетевой трафик - маршрутизаторов. Многие как отечественные, так и зарубежные сети не используют алгоритмов маршрутизации, адаптивных к перегрузкам каналов. В значительной мере это объясняется тем, что большинство вычислительных сетей использует при выборе маршрута передачи критерий минимума стоимости передачи, а стоимость каналов связи в распределенных системах не зависит от нагрузки. В то же время, выбор маршрута, учитывающий перегрузки в сети, улучшает характеристики сети.
Загрузка и реальная пропускная способность линий связи вычислительной сети динамически меняется, что, в свою очередь, может приводить к относительно частой рассылке служебной информации изменения маршрутов. В настоящее время достигнуто значительное увеличение скоростей передачи данных, что способно нивелировать эту нагрузку.
В свою очередь, получение маршрутизатором новой маршрутной информации приводит к перерасчету кратчайших маршрутов между различными подсетями. Для первоначального расчета кратчайших путей и для перерасчета после изменения значения метрики одного канала связи применяются одни и те же алгоритмы поиска кратчайших путей из одной вершины. Данные алгоритмы, в общем случае, имеют полиномиальную сложность, поскольку предназначены для поиска путей в условиях отсутствия априорной информации о кратчайших маршрутах, существовавших
до изменения. При частом обновлении маршрутной информации задача уменьшения трудоемкости расчета кратчайших путей является важной.
Исходя из всего выше сказанного, можно сделать вывод об актуальности выбранной темы диссертационной работы.
Цель диссертационной работы состоит в разработке способов повышения эффективности функционирования составных вычислительных сетей, увеличения производительности маршрутизаторов путем разработки новых методов и алгоритмов поиска оптимальных маршрутов в составных вычислительных сетях в условиях изменяющейся загрузки и реальной пропускной способности линий связи.
Для достижения поставленной цели необходимо решить следующие задачи:
Выполнить анализ целей и задач маршрутизации в вычислительных сетях с пакетной обработкой информации. Провести исследование существующих адаптивных алгоритмов, протоколов маршрутизации, применяемых в составных вычислительных сетях для того, чтобы выявить достоинства, недостатки и область их применения; провести исследование современных маршрутизаторов.
Разработать графоаналитическую модель процесса передачи пакетов данных в виде задачи управления телекоммуникационным трафиком. Рассмотреть детерминированное и случайное управления. Построить математическую модель маршрутизации с использованием теории систем и сетей массового обслуживания. Сформулировать и решить оптимизационную задачу нахождения среднего времени передачи пакета для фиксированной и альтернативной процедур выбора маршрута.
Разработать математическую модель процесса маршрутизации на основе предположения о самоподобии трафика данных в вычислительных сетях. Обосновать корректность применения данной модели.
Разработать алгоритм поиска оптимальных маршрутов при изменении значения метрики линии связи, учитывающий факт ее использования в дереве кратчайших путей.
Разработать алгоритм поиска оптимальных маршрутов на основе дополнительной априорной информации о структуре дерева кратчайших путей.
Привести доказательство правильности и оценку трудоемкости разработанных алгоритмов, и определение области и условий их применения.
Научная новизна. В рамках диссертационной работы были получены следующие результаты:
Построена математическая модель управления трафиком в вычислительной сети на основе стратегий маршрутизации;
Разработана математическая модель адаптивной однопутевой и многопутевой маршрутизации с использованием теории систем и сетей массового обслуживания;
Построена математическая модель адаптивной маршрутизации на основе предположения о самоподобии трафика данных в вычислительных сетях;
Разработан алгоритм уменьшения размерности задачи поиска кратчайших путей в графе;
Разработан алгоритм поиска оптимальных маршрутов с использованием информации о парных переходах;
Проведено доказательство правильности и оценка трудоемкости разработанных алгоритмов.
Практическая ценность работы. Разработанные в диссертационной работе алгоритмы поиска кратчайших путей предназначены для применения в маршрутизаторах дейтаграмных вычислительных сетей.
Алгоритм уменьшения размерности задачи нахождения оптимальных маршрутов позволяет сократить трудоемкость решения задачи поиска
8 кратчайших путей в графе в условиях изменений значений метрик линий связи. Алгоритм парных переходов предназначен для поиска кратчайших путей в графе в условиях изменений значений метрик линий связи, который целесообразно применять в сравнительно больших корпоративных вычислительных сетях с относительно редкими изменениями значения метрик каналов связи при необходимости получения актуального дерева кратчайших путей за время, линейно зависящее от количества вершин графа.
В рамках диссертации разработан программный комплекс «Имитационное моделирование изменения дерева кратчайших путей», который построен на базе библиотеки классов, реализующих известные и вновь разработанные алгоритмы поиска кратчайших путей. Данный программный комплекс предназначен для выполнения следующих функций:
создание и визуальное редактирование графовых моделей вычислительных сетей;
поиск кратчайших путей на графе с использованием алгоритмов Дейкстры и Беллмана-^Форда;
обработка изменения веса ребра графа с использованием алгоритма уменьшения размерности задачи и алгоритма парных переходов;
проведение экспериментов по изменению весов ребер графа с построением дерева кратчайших путей;
оценка трудоемкости (количества действий) алгоритма.
Достоверность полученных в диссертационной работе результатов
подтверждается:
использованием выводов теории управляемых процессов;
применением выводов теории систем и сетей массового обслуживания, теории вероятностей и статистики;
использованием результатов теории самоподобных стохастических процессов;
применением положений теории графов;
использованием выводов теории алгоритмов;
имитационным моделированием и сравнением полученных результатов с рассчитанными параметрами.
Апробация работы. Основные результаты диссертационной работы докладывались на следующих конференциях:
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 наименований.
Классификация методов маршрутизации
В зависимости от применяемого алгоритма маршрутизации и способа рассылки топологической информации о сети известные методы маршрутизации можно разделить на следующие группы: статическая маршрутизация, квазистатическая маршрутизация, локальная адаптивная маршрутизация, централизованная адаптивная маршрутизация, гибридная адаптивная маршрутизация, распределенная адаптивная маршрутизация, простая маршрутизация. Подобную классификацию проводил Д.В. Куракин в [46]. В данной работе классификация была расширена за счет анализа дополнительных методов маршрутизации.
Статическая маршрутизация. При статической маршрутизации вся известная системе маршрутная информация загружается в базу маршрутной информации системным диспетчером [47, 66]. При этом вводятся не все возможные пути, а только те, которые будут реально использоваться. По существу статическая маршрутизация выполняет функцию принятия решений в автономном режиме и использует протоколы системного управления для связи и заполнения маршрутных таблиц в каждой системе.
При использовании статической маршрутизации появляется возможность выполнять крайне сложные автономные алгоритмы маршрутизации, поскольку при ретрансляции протокольных блоков сетевого уровня нет необходимости вычислять маршрут в реальном времени. Недостатком статической маршрутизации является неспособность логически "связывать" поставщиков сетевых услуг, поскольку сами сетевые логические объекты не собирают и не распространяют никакой информации. Более того, статическая маршрутизация неспособна реагировать на изменения конфигурации, топологии, структуры трафика или качества услуг адаптивным образом, поскольку все пути заранее вычислены.
Квази статическая маршрутизация. Квазистатическая маршрутизация подобна статической маршрутизации, в которой пути вычисляются автономно и загружаются в базу маршрутной информации через административное управление системы [47, 66]. Но, вместо запоминания единственного маршрута для каждого показателя, квазистатическая маршрутизация позволяет запомнить альтернативные пути. Это уменьшает влияние неисправностей, позволяя функции продвижения выбирать резервный путь, если наилучший путь недоступен. Квазистатическая маршрутизация имеет сходные со статической маршрутизацией преимущества и недостатки. Она может, однако, приспосабливаться в определенной мере к топологическим изменениям ценой увеличения количества хранимой информации о резервных путях. Квазистатическая маршрутизация не может приспосабливаться к изменениям конфигурации, структуры трафика или качества услуг.
Адаптивная маршрутизация. Существует несколько модификаций адаптивной маршрутизации, различающихся тем, какая именно информация используется при выборе маршрута. Получили распространение такие модификации, как локальная, распределенная, централизованная, гибридная адаптивная маршрутизация [66].
Локальная адаптивная маршрутизация основана на использовании информации, имеющейся в данном узле и включающей: таблицу маршрутов, которая определяет все направления передачи пакетов из этого узла; данные о состоянии выходных линий связи (работают или не работают); длину очереди пакетов, ожидающих передачи. Данный метод выделил А.П. Пятибратов в [66]. Информация о состоянии других узлов связи не используется, Таблица маршрутизации определяет кратчайшие пути, обеспечивающие доставку пакета адресату за минимальное время. Преимущество такого метода состоит в том, что принятие решения о выборе маршрута производится с использованием самых последних данных о состоянии узла. Недостаток метода заключается в его «близорукости», поскольку выбор маршрута осуществляется без учета глобального состояния всей сети. Следовательно, всегда есть опасность передачи пакета по перегруженному маршруту.
Централизованная адаптивная маршрутизация. При централизованной маршрутизации логические объекты сетевого уровня сообщают aинформацию о своем локальном окружении (обеспечиваемых пунктами доступа услугах сетевого уровня, существующих пунктов подключения подсети, маршрутных показателях для каждого исходящего пути и т.д.) центральному в своем регионе маршрутизации средству [47 66]. Центральное средство накапливает эту информацию и периодически (или при наступлении некоторых событий) вычисляет маршруты. Затем оно передает эту информацию каждой системе в своем регионе, которые используют ее для продвижения протокольных блоков данных сетевого уровня. В сущно сти, полная база маршрутной информации существует только в центральном средстве, где выполняется функция "принятие решений". Образующиеся в результате базы информации продвижения передаются затем каждому логическому объекту сетевого уровня для их использования функцией продвижения. Работу процедуры централизованной маршрутизации можно моделировать как справочную службу, где функция сбора информации аналогична операции модификации в справочной службе, а функция
Управление потоком передачи информации
При оценке сетей с коммутацией пакетов рассматриваются следующие количественные характеристики сети [27, 34]: задержка, скорость передачи, стоимость, надежность. Первые две характеристики тесно связаны друг с другом; они обычно применяются в качестве критериев к различным видам трафика. В частности, диалоговый трафик должен быстро доставляться и обычно он имеет малую протяженность (в этом случае скорость передачи не очень существенна). При передаче же длинных файлов не очень важна начальная задержка при приеме первых нескольких бит через сеть; в этом случае имеет значение, сколько бит в секунду можно передавать через сеть.
Процедура выбора маршрутов сообщений представляет собой правила выбора (согласно некоторому, возможно, рандомизированному алгоритму) следующего узла, в которое сообщение придет на своем пути по сети. Подробное описание алгоритма определяет процедуру выбора маршрута. В этот алгоритм входят такие параметры, как место возникновения и место назначения сообщения, приоритет сообщений, возможность использования определенных каналов, перегрузка или отказ узлов и каналов. Определим фиксированную процедуру выбора маршрутов как такую, при которой путь сообщения по сети однозначно устанавливается лишь по его местам возникновения и назначения. Если в процедуре разрешается использование более чем одного пути, то она называется процедурой выбора маршрутов, допускающей альтернативы. На основе параметров, которые указаны выше, при допускающей альтернативы процедуре выбор путей среди действующих линий может осуществляться либо детерминировано, либо случайно. Первая процедура называется детерминированной процедурой выбора маршрутов, допускающей альтернативы, а вторая — случайной процедурой выбора маршрутов, допускающей альтернативы (или случайной процедурой выбора маршрутов). Если алгоритм выбора маршрутов основан на решениях относительно некоторых параметров текущего трафика и выхода из строя узлов или каналов, то соответствующую процедуру называют динамической, или адаптивной процедурой выбора маршрутов.
Процедура выбора маршрутов должна обрабатывать весь трафик в сети, но она не оказывает прямого влияния на управление тем, какой интенсивности трафик может поступать в сеть. Задача регулирования входного трафика возлагается на процедуру управления потоками, которая выполняет одну из наиболее важных функций в сетях. В основном данная процедура предсказывает и предотвращает перегрузки путем регулирования входного трафика, идущего от подсети ресурсов и пользователей в подсеть связи,
В сети связи с коммутацией сообщений и пакетов, в которых пакеты сообщения после ввода в сеть, в конце концов, попадают в сферу «внимания» канала связи. Естественно, что, если канал занят в момент, когда сообщение требует обслуживание, оно должно встать в очередь и ожидать. Отметим, что обслуживание, которое предлагается прибором, состоит в использовании канала для передачи. Время обслуживания (передачи) для данного сообщения равняется его длине (например, в битах), деленной на пропускную способность канала (в битах за секунду). После того как сообщение использует данный канал, оно будет принято следующим узлом, и канал освобождается для использования другими сообщениями. После приема сообщения в узле процедура выбора маршрутов приписывает его некоторому выходному каналу, идущему от этого узла по пути в место назначения. Опять, если этот новый канал занят, сообщение должно ждать в очереди получения обслуживания от канала и т. д. Наконец, сообщение будет принято местом назначения. Общее время, проведенное сообщением в сети, называется задержкой сообщения (или задержкой сети). На надежность сети, ее задержку, процедуру выбора маршрутов и т. п. существенное влияние оказывает топологическая конфигурация сети связи. При проектировании сети передачи данных и в процессе ее развития очень важной является задача выбора алгоритмов маршрутизации. Для этой цели могут быть использованы различные средства: измерения и статистический анализ параметров реальной сети; натурное моделирование; имитационное моделирование; математическое моделирование.
Алгоритм уменьшения размерности задачи поиска кратчайшего пути
Анализ на основе теории очередей широко применяется при проектировании сетей и очень полезен при планировании ресурсов и предсказании производительности. В течение десятилетий анализ очередей основывался на предположении о соответствии типа трафика распределению Пуассона [34]. Однако во многих реальных случаях результаты, полученные на основе анализа очередей, существенно отличаются от фактически наблюдаемой производительности. Исследователи из Бостонского университета и лаборатории Bellcore опубликовали следующие результаты. В некоторых случаях трафик описывается не распределением Пуассона, а является по своей природе самоподобным, или фрактальным. При таком трафике производительность сети не подчиняется формулам анализа очередей, а имеют место большие задержки и снижение пропускной способности. С момента публикации эти результаты были многократно подтверждены на трафиках самых разных типов. Концепция самоподобия тесно связана с получившим большую известность понятием фракталов и теорией хаоса [73, 118].
Наиболее замечательной особенностью самоподобного трафика в контексте производительности сетей является устойчивость кластеризации. В пуассоновском трафике кластеризация наблюдается в краткосрочном масштабе, но сглаживается в долгосрочном. Очередь может образоваться в краткосрочной перспективе, но за долгий период времени буферы очистятся. Однако, если сами кластеры кластеризуются, тогда могут образовываться очереди большей длины, чем можно ожидать от пуассоновско-го потока. В результате оказывается, что традиционный анализ очередей, в основе которого лежит предположение о пуассоновском потоке, не может точно предсказывать производительность системы. Трафик данных лучше всего рассматривать как стохастический процесс, поэтому можно говорить лишь о статистическом самоподобии.
Общее определение самоподобного стохастического процесса основано на прямом масштабировании непрерывной переменной времени [118]. Стохастический процесс x(t) является статистически самоподобным с параметром Н (0,5 Н 1), если для любого вещественного значения а О процесс aHx(at) обладает теми же статистическими характеристиками, что и сам процесс x(t). Это утверждение можно выразить тремя следующими параметрами:
Параметр Н, называемый параметром Херста, или параметром самоподобия, представляет собой меру устойчивости статистического явления, или меру длительности долгосрочной зависимости стохастического процесса. Значение Я = 0,5 указывает на отсутствие долгосрочной зависимости. Чем ближе значение Які, тем выше степень устойчивости долгосрочной зависимости. Предположим, что наблюдаемая временная последовательность взята из самоподобного стохастического процесса с параметром Н и что выбрана конкретная форма процесса. В этом случае параметр Н можно оценить, если найти такое значение Я, которое минимизирует следующее выражение: Другой концепцией, связанной с самоподобием, являются медленно затухающие распределения. По существу, самоподобный стохастический процесс можно определить при помощи таких распределений. Одно из достоинств подхода медленно затухающих распределений заключается в том, что он позволяет получить управляемые модели. Медленно затухающие распределения могут использоваться для Ф представления плотностей вероятности, описывающих процессы передачи данных, такие как интервалы между поступлениями пакетов и числа паке тов в сообщении. В целом, случайная переменная с медленно затухающим распределением обладает бесконечной дисперсией и, возможно, бесконеч ным средним значением. Случайная переменная с медленно затухающим распределением может принимать очень большие значения с вероятно стью, которой нельзя пренебречь. Как правило, если производится выборка такой случайной переменной, будет получено множество относительно малых значений, хотя некоторые значения будут относительно велики. Самым простым медленно затухающим распределением является распре м деление Парето с параметрами киа(к,а 0)и следующими функциями плотности, распределения вероятностей и среднего значения: Параметр к определяет минимальное значение, которое может принимать случайная переменная. Параметр а определяет среднее значение и дисперсию случайной переменной. Если а 2, тогда распределение обладает бесконечной дисперсией, а если а 1, тогда распределение обладает бесконечным средним значением и дисперсией. Медленно затухающее распределение определенных сетевых переменных (например, размеров файлов и длительности соединений) является основной причиной долгосрочной зависимости и самоподобия сетевого трафика. С 1993 г. множество исследований, о которых сообщается в литературе [73, 104, 115-118], показало, что тип трафика данных в широком спектре сетевых ситуаций реального мира хорошо моделируется самоподобными процессами. В. Лиланд, М. Таку, В. Вилинджер и Д. Вилсон опубликовали в 1994 году статью [104], в которой утверждали, что анализ очередей с использованием предположения о пуассоновском потоке не представляет собой адекватную модель сетевого трафика. Опираясь на большое количество исходных данных и тщательный статистический анализ, они показали, что требуется новый метод моделирования и анализа, учитывающий свойства самоподобия трафика передаваемых данных.
Исследователи из Bellcore промоделировали Ethernet-трафик с помощью распределений с бесконечной дисперсией, в частности, используя распределение Парето с параметром а. Лежащим в интервале от 1 до 2. Как уже упоминалось, когда параметр а находится в этом диапазоне, случайная переменная обладает конечным средним значением и бесконечной дисперсией. Суперпозиция нескольких источников, подчиняющихся распределению Парето, позволяет получить самоподобный трафик с параметром Херста Н - (3 - а)/2. Для 1 а 2 получим 0,5 Н 1, что представляет собой диапазон самоподобия. Для Ethernet-трафика было обнаружено, что параметр а индивидуальных источников равен 1,2, что соответствует самоподобному трафику с Н — 0,9 [104, 115].
Исследование алгоритмов поиска кратчайших путей на графе
В результате работы над диссертационной работой были получены следующие теоретические и экспериментальные результаты:
Проведен анализ целей и задач маршрутизации данных в вычислительных сетях с пакетной обработкой информации. Исследование существующих адаптивных алгоритмов, протоколов маршрутизации, применяемых в составных вычислительных сетях. Выявлены достоинства, недостатки и область применения методов маршрутизации, проведено исследование современных маршрутизаторов.
Выявлены количественные характеристики, применяемые при оценке сетей с коммутацией пакетов. Проведено исследование процедур выбора маршрутов. Даны определения фиксированной процедуры, а также детерминированной и случайной процедур выбора маршрутов, допускающей альтернативы.
Среди всех стратегий маршрутизации выделены следующие 4 по влиянию на производительность вычислительной сети: 1. Выбор единственного кратчайшего пути по критерию минимизации оценки пути. 2. Использование одного или нескольких маршрутов с одинаковыми оценками, которые являются минимальными для заданной сети. 3. Распределение пакетов по всем возможным маршрутам между заданной парой узлов с вероятностью, обратно пропорциональной длине выбранного маршрута. 4. Распределение пакетов данных по к кратчайшим маршрутам с вероятностью, обратно пропорциональной длине этого маршрута. Построена фафоаналитическая модель процесса маршрутизации в вычислительной сети как модель управления передачей телекомму 178 никационного трафика. Рассмотрены детерминированное и случайное управления. Построена модель управляемого марковского процесса передачи данных.
Приведена постановка задачи маршрутизации в вычислительной сети с использованием математического аппарата теории массового обслуживания. Сформулирована оптимизационная задача нахождения среднего времени передачи пакета для фиксированной и альтернативной процедур выбора маршрута. Предложено использовать для решения поставленной задачи метод отклонения потока или метод, состоящий в решении двойственной задачи методом лагранжевого ослабления некоторого количества ограничений исходной задачи. Построена математическая модель маршрутизации на основе предположения о самоподобии сетевого трафика. Приведено обоснование данного предположения для трафика составной вычислительной сети. Модель построена для фиксированной и альтернативной процедур выбора маршрута.
Проведен анализ процедуры обработки изменения значения метрики линии связи вычислительной сети. Выдвинуто предположение о возможности разработки алгоритма обработки изменения меньшей трудоемкости по сравнению с известными применяемыми алгоритмами. Основой подобного алгоритма будет являться использование априорно известной информации о конфигурации кратчайших путей до рассматриваемого изменения.
Рассмотрена задача обработки изменения метрики линии связи. Проведено разбиение исходного множества вершин графовой модели вычислительной сети на множество вершин с неизменными оценками длин и конфигурацией кратчайшего пути Vr и множество вершин, для которых кратчайший путь может измениться. Сформулированы и доказаны теоремы, определяющие способ формирования данных множеств. Показано, что операция поиска кратчайших путей для вершин множества Vx не требуется. Выводы теорем позволяют разработать алгоритм уменьшения размерности задачи поиска кратчайших путей в графе после изменения веса ребра.
Разработан алгоритм уменьшения размерности задачи поиска кратчайших путей в графе после изменения веса ребра. Проведено доказательство правильности и расчет трудоемкости предлагаемого алгоритма. Верхняя и нижняя оценки трудоемкости соответственно равны П(ММ) и 0(1). Введено понятие парного перехода и точки вхождения ребра в дерево кратчайших путей. Сформулированы и доказаны теоремы, определяющие условия срабатывания парных переходов ребер графа. Операция обработки изменения веса ребра графа представлена как процедура выполнения парных переходов ребер графа.На основе выводов сформулированных теорем разработан алгоритм расчета и выбора парных переходов. Проведено доказательство правильности и расчет трудоемкости предлагаемого алгоритма. Верхняя и нижняя оценки трудоемкости соответственно равны Q(N) и @(N). Разработан программный комплекс для оценки эффективности выполнения функций маршрутизации в вычислительных корпоративных сетях. Предлагаемые в работе алгоритмы были реализованы на языке Object Pascal. При проектировании программного комплекса применялся модульный принцип построения. При разработке программного обеспечения использовался объектно-ориентированный подход к проектированию программных систем с использованием техники паттернов, что позволило добиться максимально возможной степени повторного использования проектных решений.
