Общая характеристика маршрутизации

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

1. Обеспечить минимальную возможную задержку и максимальную пропускную способность.

2. Обеспечить прохождение пакета сквозь сеть за минимальную стоимость.

3. Обеспечить каждый пакет максимальной возможной защитой и надежностью.

Приведем некоторые виды классификации методов маршрутизации.

Классификация по способу управления сетью

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

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

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

Сводка основных свойств методов приведена в табл. 3.5.

Таблица 3.5

Свойства методов маршрутизации

Классификация по способу принятия решений узлом

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

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

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

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

Свойства детерминированных и вероятностных методов также сведены в табл. 3.5.

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

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

o фиксированный, или статический, каталог. Изменяется единственный раз при генерации системы. Сохраняется неизменным для всех сеансов;

o каталог, ориентированный на сеансы. Изменяется для каждого сеанса каждого отдельного пользователя. Сохраняется неизменным для отдельного сеанса;

o адаптивный, или динамический, каталог. Изменяется в течение каждого пользовательского сеанса.

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

Рассмотрим, как работают и где применяются некоторые методы маршрутизации.