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

• Автор: Уваров, Дмитрий Владиславович
• Шифр специальности: 05.13.13
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Рязань
• Количество страниц: 196 с. : ил.

Содержание
Введение

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

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

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

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

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

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

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

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

Глава 2. Математическое моделирование процессов маршрутизации в корпоративных вычислительных сетях
2.1. Основные понятия и определения.
2.2. Управление потоком передачи информации.
2.3. Постановка задачи поиска оптимальных потоков.
2.4. Решение задачи поиска оптимальных потоков в вычислительной сети
2.5. Рассмотрение задачи маршрутизации в условиях
самоподобного трафика
Основные результаты и выводы.
Глава 3. Разработка алгоритмов поиска кратчайших путей
3.1. Задача поиска путей.
3.2. Алгоритм уменьшения размерности задачи поиска кратчайшего пути
3.3. Алгоритм парных переходов.
Основные результаты и выводы.
Глава 4. Практическая реализация и исследование разработанных алгоритмов.
4.1. Разработка программного обеспечения
4.2. Исследование алгоритмов поиска кратчайших путей на
Основные результаты и выводы.
Заключение.
Библиографический список.
Приложение.
Введение
Актуальность


Это ускоряет прохождение пакета по сети, разгружает маршрутизаторы, но при этом большая нагрузка ложится на конечные узлы. Эта схема в вычислительных сетях применяется сегодня гораздо реже, чем схема распределенной одношаговой маршрутизации. Однако в новой версии протокола 1Р наряду с классической одношаговой маршрутизацией будет разрешена и маршрутизация от источника. Определение пути передачи данных происходит программно. Соответствующие программные средства носят название протоколов маршрутизации. Логика их работы основана на алгоритмах маршрутизации. Алгоритм выбора пути передачи пакета данных является частью программного обеспечения сетевого уровня, ответственной за выбор выходной линии, по которой следует отправить пришедший пакет. Если подсеть использует дейтаграммную службу, выбор маршрута для каждого пакета должен производиться заново, так как оптимальный маршрут мог измениться. После этого все информационные пакеты следуют по выбранному маршруту. Последний случай иногда называют сеансовой маршрутизацией, так как маршрут остается в силе на протяжении всего сеанса пользователя. Однако в обоих случаях алгоритм выбора маршрута должен обладать определенными свойствами: правильностью, простотой, надежностью, устойчивостью, справедливостью и оптимальностью. Правильность и простота вряд ли требуют комментариев, но потребность в надежности не столь очевидна с первого взгляда. За период работы большой сети постоянно происходят различные отказы аппаратуры и изменения топологии. Алгоритм маршрутизации должен уметь справляться с такими изменениями без необходимости прекращения всех задач на всех оконечных системах и перезагрузки сети при каждой поломке маршрутизатора. Алгоритм выбора маршрута должен обладать устойчивостью. Существуют алгоритмы, никогда не приходящие в состояние равновесия, независимо от того, как долго они работают. Такие цели, как справедливость и оптимальность, могут показаться очевидными, однако они часто оказываются взаимоисключающими. Для каждого класса процедур указывается ее способность реагировать на различные динамические изменения в глобальной сети, например, изменения топологии из-за появления или пропадания путей к системам и подсетям; изменения в конфигурации, добавления новых систем (подсетей) или их удаление; модификации в сгруктуре трафика сети; изменение доступного качества услуг на некоторых подсетях или некоторых используемых путях. В зависимости от применяемого алгоритма маршрутизации и способа рассылки топологической информации о сети известные методы маршрутизации можно разделить на следующие группы: статическая маршрутизация, квазистатическая маршрутизация, локальная адаптивная маршрутизация, централизованная адаптивная маршрутизация, гибридная адаптивная маршрутизация, распределенная адаптивная маршрутизация, простая маршрутизация. Подобную классификацию проводил Д. В. Куракин в []. В данной работе классификация была расширена за счет анализа дополнительных методов маршрутизации. Статическая маршрутизация. При статической маршрутизации вся известная системе маршрутная информация загружается в базу маршрутной информации системным диспетчером [, ]. При этом вводятся не все возможные пути, а только те, которые будут реально использоваться. По существу статическая маршрутизация выполняет функцию принятия решений в автономном режиме и использует протоколы системного управления для связи и заполнения маршрутных таблиц в каждой системе. При использовании статической маршрутизации появляется возможность выполнять крайне сложные автономные алгоритмы маршрутизации, поскольку при ретрансляции протокольных блоков сетевого уровня нет необходимости вычислять маршрут в реальном времени. Недостатком статической маршрутизации является неспособность логически "связывать" поставщиков сетевых услуг, поскольку сами сетевые логические объекты не собирают и не распространяют никакой информации. Более того, статическая маршрутизация неспособна реагировать на изменения конфигурации, топологии, структуры трафика или качества услуг адаптивным образом, поскольку все пути заранее вычислены. Квазистатическая маршрутизация.