Маршрутизация. Основные определения

Одной из важнейших функций УУСС является маршрутизация, которая значительно влияет на качество обслуживания (Quality of Service (QoS)) пользователей сети, эффективное использование линейных сооружений и аппаратуры передачи информации. Дадим основные определения.

Маршрут (Route) ¾ список элементов сети связи (АП, УК, ЛС, ТПС, КС), начинающийся с АП вызывающего пользователя и заканчивающийся АП вызываемого пользователя. Физически маршрут реализуется в виде соединительного тракта передачи сообщения либо скоммутированных в УК каналов связи между исходящим и входящим оконечным оборудованием пользователей.

Пример 1.2.

Маршруты между АП № 1 и АП № 5 сети, изображенной на рисунке 1.2, будут иметь следующую запись:

· m¹_1,5 = {АП № 1, УК № 1, УК № 2, УК № 4, АП № 5};

· m²_1,5 = {АП № 1, УК № 1, УК № 3, УК № 2, УК № 4, АП № 5}.

В данном примере УК № 1 является исходящим (узел - источник (УИ)), УК №5 входящим (узел - получатель (УП)), а УК № 2, 3, 4 транзитными.

С целью упрощения записи маршрута абонентские пункты в списке могут отсутствовать.

Маршрутизация (Routing) ¾ набор процедур, позволяющих определить оптимальный по заданным параметрам маршрут (например, количество транзитных УК, время задержки в элементах сети связи при передаче информации между пользователями, надежности элементов сети и др.) на сети связи между АП пользователей либо узлами коммутации.

Для реализации маршрутизации на сети в каждом транзитном УК (УК № j), начиная с УИ, формируется таблица маршрутизации, которая представляет собой матрицу (Matrix) размерностью (S - 1)×H_j

(1.1)

= (m^(j)_i1,…, m^(j)_iv,…, m^(j)_iHj); v = , (1.2)

где S ¾ количество УК в сети; H_j ¾ количество исходящих ТПС из j-го УК.

Матрица M^(j) содержит информацию о предпочтительности выбора исходящего ТПС из j-го УК при поиске маршрута к i-му узлу (УП).

Первый элемент m^(j)_i1 вектор строки (1.2) указывает номер исходящего ТПС из j-го УК к смежному УК, который предпочтительнее выбрать для организации маршрута к i-му УК (УП).

Второй элемент m^(j)_i2 вектор строки (1.2) указывает номер следующего исходящего ТПС из j-го УК к другому смежному УК, который менее предпочтительный для организации искомого маршрута к i-му УК. И так до H_j-го элемента вектор строки (1.2).

При этом говорят, что m^(j)_i1 является исходящим ТПС первого выбора,

m^(j)_i2 ¾ исходящим ТПС второго выбора и, соответственно, m^(j)_iHj ИТПС

H_j-го выбора.

Пример 1.3.

Построим таблицу маршрутизации для УК под номером 2 (Рисунок 1.3).

Соответствующие строки матрицы M⁽²⁾ будут иметь следующий вид:

= (1 ,4 ,3); = (3, 4, 1); = (4, 1, 3). Таким образом, при поиске маршрута от УК № 2 к УК № 1 необходимо обратиться к вектор - строке

= (1 ,4 , 3). При этом исходящий ТПС к смежному УК № 1 является более предпочтительным, так как он ведет непосредственно к искомому УК, следовательно, является ИТПС первого выбора. Соответственно, исходящие ТПС к смежным УК № 4 и 3 являются исходящими ТПС второго и третьего выбора.

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

Совокупность таблиц маршрутизации для всех УК сети называется планом распределения информации (ПРИ) на сети связи. Считается, что ПРИ на сети задан, если определены таблицы маршрутизации для каждого УК.

Пример 1.4.

Зададим ПРИ на сети, изображенной на Рисунке 1.3, в виде таблиц маршрутизации:

В данном примере формирование ПРИ осуществлялось по минимальному количеству транзитных УК в искомом маршруте. Возможны ситуации, когда формирования ПРИ осуществляется и по другим критериям:

· надежность элементов сети связи;

· время задержки передачи информации в элементах сети;

· скорость передачи информации и прочие.

Данные параметры являются случайными величинами и зависят от многих причин:

· вида и интенсивности трафика пользователей сети;

· условий окружающей среды при эксплуатации оборудования сети;

· технического состояния оборудования сети и других причин.

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

Если в процессе эксплуатации сетей связи происходит автоматическое переформирование ПРИ (без участия администрации сети), то такой ПРИ называют динамическим.

В противном случае формирование ПРИ будет статическим.

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

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

Пример 1.5.

Используя таблицы маршрутизации для сети, изображенной на Рисунке 1.3, определим несколько вариантов формирования маршрутов между узлами

№ 2 и № 1.

Этап № 1. Обращаемся к таблице маршрутизации УК № 2 и выбираем вектор строку под номером 1: = (1, 4, 3). В данной вектор строке ИТПС первого выбора является ТПС, соединяющий данный узел с узлом под номером 1. УК № 1 является искомым (УП). Следовательно, маршрут m¹_2,1 = {2, 1} является маршрутом первого выбора. Допустим, что в данный момент времени исходящий ТПС первого выбора является недоступным.

Этап № 2. В данном случае необходимо выбрать следующий по предпочтительности исходящий ТПС, т. е. ИТПС к УК № 4.

Этап № 3. В УК № 4 обращаемся к таблице маршрутизации и выбираем вектор строку под номером 1: = (1, 2, 3). Исходящим ТПС первого выбора является ТПС, соединяющий данный узел с узлом под номером 1. УК № 1 является искомым (УП). Следовательно, маршрут m²_2,1 = {2, 4, 1} является маршрутом второго выбора.

Обратимся к этапу № 1. В случае занятости или неисправности исходящих ТПС первого выбора и второго выбора в УК № 2 имеется возможность выбрать ИТПС к УК № 3. В данной ситуации будет определен маршрут между УК № 2 и 1 третьего выбора: m³_2,1 = {2, 3, 4, 1}.

Таким образом, используя заданный ПРИ можно организовать между узлами № 2 и № 1 следующие маршруты: m¹_2,1 = {2, 1}, m²_2,1 = {2, 4, 1} и

m³_2,1 = {2, 3, 4, 1}.

Анализ ситуаций выбора исходящих ТПС на этапе № 3 позволяет сделать важный вывод: при поиске маршрутов между заданной парой УК на сети необходимо избегать возможных зацикливаний маршрута.

Действительно, если на этапе № 3 окажется недоступным исходящий ТПС к УК № 1, то согласно информации, заложенной в вектор строке = (1, 2, 3), выбор следующих по предпочтительности исходящих ТПС к УК № 2 и 3 приведет к зацикливанию маршрута. Данная ситуация недопустима, так как это приведет к невозможности установления маршрута между заданной парой узлов и перегрузке сети.

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

Если в каждом УК одновременно выбирается два и более исходящих ТПС, то такой выбор ИТПС будем называть параллельным. В этом случае на сети формируется несколько маршрутов от УИ к УП, один из которых будет оставлен и зафиксирован. Остальные должны само распадаться.

Критерием выбора одного из множества маршрутов могут быть:

· минимальное количество транзитных УК;

· минимальное время задержки при передачи сообщения по всей длине маршрута;

· максимальная надежность элементов, участвующих в формировании маршрута.

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

Отметим, что последовательный выбор исходящих ТПС является частным случаем параллельного выбора ИТПС.

Критериями выбора количества исходящих ТПС в каждом УК могут служить:

· приоритет пользователей сети связи (определяется срочностью и ценностью предполагаемой к передачи информации);

· степень загруженности или неисправности элементов сети связи.

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

1. Формирование ПРИ на сети связи.

2. Выбор исходящего тракта передачи сообщения в каждом УК при поиске маршрута между УИ и УП.

Выводы

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

2. Структуру сети связи (соединение элементов сети между собой) можно описать матрицами: ТПС L= l_ij ; ; каналов связи K= k_ij ; ; V v_ij скоростей. При необходимости они могут быть дополнены матрицами надежности, пропускных способностей элементов сети и многими другими, которые необходимы при анализе и синтезе сетей связи.

3. Маршрутизация состоит из двух этапов: формирование ПРИ на сети связи; выбор исходящего ТПС в каждом УК при поиске маршрута между УИ и УП.

4. Если в процессе эксплуатации сетей связи происходит автоматическое переформирование ПРИ (без участия администрации сети), то такой ПРИ называют динамическим. В противном случае формирование ПРИ будет статическим.

5. При поиске маршрутов между заданной парой УК на сети необходимо избегать возможных зацикливаний маршрута.

6. Выбор исходящих ТПС (по количеству одновременно выбираемых ТПС) в каждом УК может быть последовательным, параллельным и комбинированным