2.4. ПРОЦЕДУРЫ ВЫБОРА МАРШРУТОВ

Общие сведения

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

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

Избирательные процедуры выбора маршрутов

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

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

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

Основными достоинствами СП являются относительно слабая зависимость значений внешних параметров сети от надежности ее элементов и достаточность для маршрутизации и поиска абонентов только локальной сетевой информации. Недостатки СП — возможность больших издержек сообщений и значительная интенсивность внутренних потоков.

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

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

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

2. Детерминированная процедура (ДП) предусматривает для передачи между каждой парой узлов единственный маршрут. Если этот маршрут находится в неисправном или занятом состоянии, сообщение ожидает его восстановления или освобождения.

К достоинствам детерминированной процедуры можно отнести следующие:

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

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

Основной недостаток детерминированной процедуры — сильное влияние ненадежности сети на ее вероятностно-временные характеристики.

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

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

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

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

Таким образом, ПП по своим свойствам занимает промежуточное положение между СП и ДП и сглаживает достоинства и недостатки каждой из этих процедур.

Следует отметить, что реализация поисковой, процедуры выбора маршрутов в сетях ПД наиболее сложна, так как требует дополнительных операций по опробованию маршрутов и задействует значительные объемы памяти для хранения информации об этих маршрутах.

Несмотря на сложность реализации, ПП является наиболее перспективной процедурой для сетей ПД.

Процедуры повышенной надежности доставки

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

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

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

Второй вариант, получивший название алгоритма «волна» [21], не требует информации о состоянии сети и обеспечивает потенциально достижимую в сети надежность доставки.

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

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

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

Процедуры передачи циркулярных сообщений

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

К специальным циркулярным процедурам относится [46] передача:

по минимальному связывающему дереву;

по дереву кратчайших маршрутов;

ПО дереву обратных кратчайших маршрутов.

Процедура передачи по минимальному связывающему дереву базируется на алгоритм вычисления минимального дерева взвешенного графа сети. Наиболее распространенная на практике реализация такого алгоритма (алгоритма Прима) приводится в разд. 4.3.

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

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

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

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

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

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

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

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

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

Интенсивность внутренних потоков определяется выражением

где — средняя длина маршрута в сети; — интенсивность внешнего потока циркулярных сообщений.

Процедура алгоритма «волна» хотя и не зависима от одноадресной, но достаточно проста в реализации и не требует никакого информационного обеспечения. Кроме того, она характеризуется наилучшими вероятностно-временными и надежностными характеристиками. Ограниченность ее применения вариантами, когда циркулярные сообщения являются особо важными и появляются сравнительно редко, объясняется значительным увеличением внутренних потоков. Так, по полученным в [54] оценкам среднее число шагов, за которое сходится алгоритм, равно

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

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

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

Интенсивность внутреннего потока линейно зависит от числа узлов в сети:

По среднему времени задержки данная процедура уступает процедуре алгоритма «волна», но превосходит последовательную избирательную процедуру.

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

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