ГЛАВА 7. Математические модели исследования алгоритмов маршрутизации

7.1 Основные понятия и определения

Проблемы маршрутизации присутствуют в сетях любого типа -как в сетях коммутации пакетов и сообщений (Х.25, Frame Relay), так и в цифровых сетях коммутации каналов (Digital Leased Lines), реализованных на основе стандартов PDH/SDH/SONET. Конечно, конкретная реализация алгоритма маршрутизации существенно зависит от специфических особенностей сети (например, даже в пределах класса сетей пакетной коммутации алгоритмы маршрутизации значительно отличаются при использовании метода дейтаграмм или метода виртуальных соединений), но в целом для различных сетей используется достаточно похожий математический аппарат -алгоритмы кратчайшего пути (Shortest Path) и потоковые алгоритмы (Multicommodity Flow). Специфика сети проявляется в составе учитываемых входных параметров и ограничений на выбираемый маршрут, а также в требованиях на его качество. Достаточно подробное рассмотрение вопросов маршрутизации в «традиционных» вычислительных сетях проведено, например, в [6] (применительно к сетям передачи данных), в [300] (применительно к оптоволоконным сетям связи SDH/SONET) и т.д. Имеются фундаментальные работы и по динамической маршрутизации (см., например, [130]).

Классификация алгоритмов маршрутизации для сетей пакетной коммутации приведена также в [72,88,89,105,120]; для сетей ATM в разделе 7.5 настоящей главы.

Под алгоритмом маршрутизации понимается правило, в соответствии с которым в каждом узле сети передачи данных осуществляется выбор линии связи для передачи блока данных (сообщения или пакета). Согласно [89], под фиксированной (неразветвленной, однопутевой) маршрутизацией будем понимать такую процедуру выбора маршрутов, при которой для передачи данных от узла-источника узлу-адресату используется единственный маршрут. Если в процедуре выбора маршрутов разрешается использовать более одного пути, то она называется альтернативной разветвленной, многопутевой).

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

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

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

- натурное моделирование;

- имитационное моделирование;

- математические оптимизационные модели.

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

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

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

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