Одной из задач, требующих решения в сетях связи, является управление информационными потоками. К этому классу задач относится маршрутизация. Маршрутизация означает доставку информации от источника к адресату через сеть связи (этот же термин используется и при объединении сетей с использованием мостов и шлюзов). К настоящему моменту проведено большое число исследований и экспериментов по проблеме маршрутизации в вычислительных сетях. Ранние исследования были направлены на изучение проблемы в низкоскоростных узкополосных сетях связи, в частности ARPANET, для случаев линий связи с низкой надежностью, ограничениями на производительность и объем памяти аппаратно-программных средств.
В отличие от наземных сетей связи топология IICCC и характеристики информационных потоков изменяются чаще, а величина этих изменений в течение даже нескольких десятков секунд может быть очень существенной. Практически каждый СР орбитальной группировки функционирует в нестационарном режиме в течение витка вокруг Земли, так как зоны его радиовидимости постоянно изменяются, а распределение пользователей НССС по земной поверхности существенно неравномерное. Поэтому решение задачи управления информационными потоками и сетью связи в WCCC является более сложным, чем в наземных сетях, и будет постоянно актуальным для данного класса сетей. Рассмотрим основные элементы маршрутизации сообщений в сетях связи.
Маршрутизация включает в себя две основные компоненты: определение оптимальных маршрутов между источником и адресатом и передача информации по выбранному маршруту. Алгоритмы маршрутизации содержат, как правило, следующие процедуры:
• измерение и оценивание параметров сети;
• принятие решения о рассылке служебной информации;
• расчет таблиц маршрутизации, представляющих собой матрицы, в строках которых, в зависимости от используемого алгоритма, может находиться адрес узла-назначения, длина пути, номер ближайшего узла и т.п.;
• реализация принятых маршрутных решений.
Определение маршрута может базироваться на различных показателях (или метриках), в качестве которых чаще всего выступают длина маршрута (в числе участков переприема), длина очереди, задержка доставки информации, пропускная способность, надежность и др. или их комбинации. Программные реализации алгоритмов маршрутизации рассчитывают показатели маршрута для определения оптимальных, в выбранной метрике, маршрутов от источника к пункту назначения.
Теоретической основой маршрутизации является решение задачи поиска маршрутов между вершинами во взвешенном графе. В этом случае моделью сети связи является ориентированный граф G(V, E), в котором узлы представлены вершинами К а множество каналов (линий) связи — ветвями (дугами, ребрами) Е. Каждой ветви присваивается вес (положительное число, не зависящее от времени), равный стоимости пропуска трафика по данной линии связи. В общем случае допускается, что граф является полным, тогда если между произвольными узлами нет прямой линии связи, то этой ветви присваивается бесконечная стоимость. В этих терминах проблема маршрутизации формулируется как поиск пути с минимальным весом между каждой парой узлов, при этом вес маршрута вычисляется как сумма весов каждой линии связи, входящей в маршрут.
Желательно, чтобы алгоритмы маршрутизации были как можно более простыми. В этом случае для их реализации требуются минимальные затраты программного обеспечения и производительности маршрутизаторов.
Алгоритмы маршрутизации должны:
• обладать живучестью, под которой понимается обеспечение выполнения основных функций в случае отказов аппаратуры, перегрузок маршрутов (или каналов связи) и возникновения некорректных действий;
• быстро сходиться, т.е. при изменении ситуации в сети значение контролируемого параметра должно вести себя устойчиво вблизи некоторого равновесного значения, близкого или равного оптимальному. Алгоритмы маршрутизации, которые сходятся медленно, могут привести к образованию петель (циклов) или к выходу из строя сети;
• обладать устойчивостью (быть робастными) и гибкостью, быстро и точно адаптироваться к изменениям в сети, например, к изменениям полосы пропускания каналов связи сети;
• быть масштабируемыми, т.е. нормально функционировать при произвольном числе узлов в сети;
• быть справедливыми, т.е. для передачи пакетов одного и того же класса сервиса должны выделяться и одинаковые сетевые ресурсы;
• быть стабильными и функционировать без нежелательных колебательных процессов. Незначительные изменения в сети должны приводить к незначительным изменениям в маршрутизации.