7.4 Примеры анализа алгоритмов маршрутизации в сетях передачи данных

Предложенные выше математические модели были использованы для анализа двух ведомственных сетей передачи данных, являющихся основой систем продажи и бронирования железнодорожных и авиационных билетов - «Экспресс» и «Сирена».

7.4.1 Анализ различных вариантов алгоритмов маршрутизации для СПД «Экспресс»

Сеть передачи данных «Экспресс» состоит из 30 узлов коммутации и 76 линий связи.

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

Таблица 7.1. Перечень мест размещения узлов коммутации СПД

«Экспресс»

Сообщения, поступающие в СПД «Экспресс», подразделяются на два класса: диалоговые сообщения и архивные сообщения, причем диалоговые сообщения имеют относительный приоритет (приоритет без прерывания обслуживания) по отношению к архивным. Средняя длина диалоговых сообщений составляет 167 байтов, средняя длина архивных сообщений - 1524 байта. В результате измерений на реальной сети были определены матрицы входных потоков для каждого класса.

Первоначально в СПД «Экспресс» использовался алгоритм с однопутевой стратегией маршрутизации. В процессе развития системы «Экспресс» требования к надежности и пропускной способности сети передачи данных резко повысились, что было связано как со значительным увеличением узлов и ребер сети (от 3-х узловой сети в 1988 г. до сети из 30 узлов в настоящее время), так и с внедрением новых технологий организации продажи билетов и управления пассажирскими перевозками. Одним из недостатков используемого алгоритма являлось отсутствие расщепления трафика между несколькими маршрутами и, как следствие, неравномерность распределения трафика между линиями связи.

Таблица 7.2. Топологическая структура и характеристики каналов связи СПД «Экспресс»

(см. скан)

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

Одним из вариантов такого алгоритма является алгоритм К -путевой (K = 2) маршрутизации, в котором устанавливаются два направления передачи к одному и тому же узлу, используемые попеременно.

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

- однопутевой;

- К - путевой (K = 2);

- альтернативной.

Модель альтернативной маршрутизации использовалась для поиска оптимального решения, позволяющего определить «идеальные» характеристики СПД.

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

Во-первых, были проведены расчеты на реальных исходных данных.

Результаты расчетов содержат следующую информацию:

1) среднее время реакции диалоговых сообщений по сети:

- для альтернативной маршрутизации - 8.45 сек;

- для 2-х путевой маршрутизации - 8.49 сек;

- для фиксированной (однопутевой) маршрутизации - 8.50 сек;

2) максимальное время реакции среди всех пар узлов коммутации:

- для альтернативной маршрутизации - 39.73 сек;

- для 2-х путевой маршрутизации - 41.88 сек;

- для фиксированной (однопутевой) маршрутизации - 42.59 сек;

3) средняя загрузка в линиях связи:

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

- для 2-х путевой маршрутизации - 0.12;

- для фиксированной (однопутевой) маршрутизации - 0.12;

4) максимальная загрузка в линиях связи:

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

- для 2-х путевой маршрутизации - 0.51;

- для фиксированной (однопутевой) маршрутизации - 0.54.

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

Для более полного исследования были проведены численные эксперименты, при которых элементы матриц входных потоков одновременно умножались на одну и ту же величину - нагрузку на сеть (начальное значение этой величины принимается равным 1). В результате экспериментов были построены функциональные зависимости средней задержки сообщений по сети от величины нагрузки. Графики данных зависимостей приведены на рис. 4.1. Результаты экспериментов показывают, что перегрузка сети наступает при увеличении нагрузки на сеть:

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

- для 2-х путевой маршрутизации - в 2.6 раза;

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

Таким образом, 2-х путевая маршрутизация допускает значительно большую нагрузку на сеть, чем фиксированная (однопутевая), и в тоже время, характеристики СПД для 2-х путевой маршрутизации очень близки к случаю альтернативной маршрутизации (фактически, при увеличении нагрузки до 2.5 раз), то есть 2-х путевая маршрутизация достаточно близка к идеальной (оптимальной) маршрутизации.

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