Маршрутизация

 

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

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

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

• измерение и оценивание параметров сети;

• принятие решения о рассылке служебной информации;

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

• реализация принятых маршрутных решений.

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

Теоретической основой маршрутизации является решение задачи поиска мар­шрутов между вершинами во взвешенном графе. В этом случае моделью сети связи является ориентированный граф G(V, E), в котором узлы представлены вершинами К а множество каналов (линий) связи — ветвями (дугами, ребрами) Е. Каждой ветви присваивается вес (положительное число, не зависящее от вре­мени), равный стоимости пропуска трафика по данной линии связи. В общем случае допускается, что граф является полным, тогда если между произвольны­ми узлами нет прямой линии связи, то этой ветви присваивается бесконечная стоимость. В этих терминах проблема маршрутизации формулируется как поиск пути с минимальным весом между каждой парой узлов, при этом вес маршрута вычисляется как сумма весов каждой линии связи, входящей в маршрут.

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

Алгоритмы маршрутизации должны:

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

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

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

• быть масштабируемыми, т.е. нормально функционировать при произволь­ном числе узлов в сети;

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

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