9.5 Методы маршрутизации в сетях электросвязи

Основные определения. Маршрут (Route) - список элементов сети связи (УК, линий связи, каналов связи), начинающийся с узла-источника и заканчивающийся узлом-получателем (УП).

Пример 9.2.

Маршруты между УК № 1 и УК № 4 на сети, изображенной на рис. 9,16, будут иметь следующую запись: = {УК № 1, УК № 2, УК № 4}; = {УК № 1, УК № 3, УК № 2, УК № 4}. В данном примере УК № 1 является исходящим, УК № 4 - входящим, а УК № 2, 3 - транзитными.

Маршрутизация (Routing) - процедура, определяющая оптималь­ный по заданным параметрам маршрут на сети связи между узлами коммутации.

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

(9.3)

(9.4)

где S - количество УК в сети; H_j - количество исходящих линий связи (ЛС)из j-го УК.

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

Первый элемент вектор-строки (9.4) указывает номер исходящей ЛС из j-го УК к

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

Второй элемент (9.4) указывает номер следующей исходящей ЛС из j-го УК к другому смежному УК, которая менее предпочтительна для организации иско­мого маршрута. И так до Н_j-го элемента вектор-строки (9.4).

В данном случае: - исходящая ЛС первого выбора, - ис­ходящая ЛС второго выбора и - исходящая ЛС Н_j -го выбора.

Пример 9.3. Построим таблицу маршрутизации для УК № 2 (рис. 9.16). Соответствующие строки матрицы М⁽²⁾ будут иметь сле­дующий вид:

При поиске маршрута от УК № 2 к УК № 1 необходимо обратиться к вектор-строке . Исходящая ЛС к УК № 1 является более предпочтительной, так как она ведет непосредственно к иско­мому УК, следовательно, является исходящей ЛС первого выбора. Соответственно, исходящие ЛС к УК № 4 и 3 являются исходящими ЛС второго и третьего выбора.

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

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

Пример 9.4. Зададим ПРИ на сети, изображенной на рис. 9.16:

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

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

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

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

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

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

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

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

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

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

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

зации искомого маршрута между заданной парой узлов.

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

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

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

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

нализации.

Маршрутизация и модель ВОС. В модели ВОС функции маршрутизации возложены на третий - сетевой уровень (Network layer). Дан­ный уровень удобно представить в виде подуровней (рис. 9.17). На третьем, верхнем подуровне производится формирование ПРИ и принятие решения о его коррекции.

Рис. 9.17. Подуровни сетевого уровня модели ВОС

Первоначально ПРИ формируется администрацией при проектировании или модификации сети связи. Частота коррекции ПРИ зависит от многих факторов:

• использование статических или динамических методов маршру­тизации;

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

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

• возможности администрации влиять на процесс управления сетью связи;

• наличие постоянных (не коммутируемых) соединений между поль­зователями сети связи.

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

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

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

Методы формирования плана распределения информации на сети связи (таблиц маршрутизации). Метод рельефов. Суть данно­го метода состоит в следующем. Пусть i- произвольный УК сети свя­зи, i-рельефом называется процедура присвоения значения числовой функции каждой ЛС. i-рельеф строится следующим образом. Из i-го УК по всем исходящим ЛС передается число 1. Все УК, в которые по­ступило число 1, передают по всем исходящим ЛС, кроме тех ЛС, по которым поступила 1, число 2. Далее УК, на которые поступило число 2, передают по ЛС, кроме тех, по которым поступила 2, число 3 и т.д., до тех пор, пока все ЛС не будут пронумерованы. Говорят, что ЛС имеет n высоту, если она обозначена числом n в i-рельефе.

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

Пример 9.5. Построим рельеф на сети относительно УК А (рис. 9.18). УК А по исходящим ЛС АВ, AC, AD передает число 1 и присваивает им это значение. Узлы В, С и D передают по ЛС BG, ВО, CL, CK, CD и DК в узлы G, / и К число 2. В свою очередь, узлы G, /, H и К передают по ЛС GL, G/, IL, IM, /Н, НК и КО число 3. Перечисленным ЛС присваивается число 3. УК L, М, Н, О, в свою очередь, передают по ЛС LM, MN, НМ, НО и ON число 4 и им присваивается число 4. Та­ким образом, на сети строится А-рельеф (рис. 9.19).

Чтобы найти кратчайший маршрут от произвольного УК к узлу А достаточно в каждом УК выбирать исходящую ЛС с меньшим весом. Например, кратчайший маршрут от УК N до УК А будет следующий: или ,

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

Игровой метод [15, 16] формирует ПРИ по накопленной ранее статистике установления соединения между заданной парой УК. Перед началом функционирования на сети устанавливается начальный ПРИ в виде набора таблиц маршрутизации (9.3). Каждому значению присваивается некоторый весовой коэффициент . Причем, нормируется

В результате формируется матрица весовых коэффициентов

(9.5)

где (9.6)

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

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

Пример 9.6. Покажем формирование ПРИ игровым методом для сети, изображенной на рис. 9.16. Будем считать, что начальный ПРИ задан в виде таблиц маршрутизации примера 9.4. Весовые коэффициенты (9.5) для узлов сети имеют следующий вид:

Допустим, что необходимо определить маршрут между УИ №2 и УП №1. При условии, что количество транзитных УК не должно превышать одного. В УИ №2 из таблицы весовых коэффициентов P⁽²⁾ выбираем вектор строку Исходящей ЛС первого выбора является ЛС к УК №1. Предположим, что данная ЛС в настоящий момент времени недоступна. Так как , то исходящей ЛС второго выбора является ЛС к УК №4. Допустим, что исходящая ЛС из УК №2 к УК№4 в данный момент времени доступна. Следовательно, данная ЛС участвует в организации искомого маршрута. В УК №4 в соответствии с выбираем исходящую ЛС к УК №1. Допустим, она доступна. Следовательно, маршрут между УИ и УП μ_2,1 = {2,4,1} организован. ЛС, участвующие в данной процедуре, поощряются. Соответствующие весовые коэффициенты увеличиваются (предположим, что на 0.2), а вектора нормируются. В результате получаем новые числовые значения:

Если ситуация поиска маршрута между заданной парой УК повторится, то вектора изменятся и примут следующий вид: Анализируя ситуацию с вектором , видно, что исходящая ЛС к УК №4 из УК №2 при поиске маршрута к УК №1 приняла значение первого выбора, так как ее весовой коэффициент стал максимальным из всех возможных в данном векторе.

Матрицы весовых коэффициентов УК №2 и 4 примут следующий вид:

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

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

Логический метод [17] состоит в процедуре, выполняемой в каждом транзитном УК, начиная от УИ, позволяющей определить исходящую ЛС, максимально близкой к геометрическому направлению на УП.

Сеть связи вкладывается в прямоугольную систему координат. Ка­ждому узлу сети присваивается собственный адрес (X, Y) (рис. 9.20).

Рис. 9.20. Поиск маршрута логическим методом

В каждом транзитном УК (Х_i, У_i), начиная с УИ (X_R, Y_L), производится анализ адреса УП сопоставлением его с собственным. В результате вычисляется геометрическое направление из данного узла на УП. За­тем определяется та ЛС, которая имеет наибольшее совпадение с ранее рассчитанным геометрическим направлением на УП. Если ближайшая по направлению исходящая ЛС не доступна, то подбира­ется очередная по предпочтительности исходящая ЛС.

Пример 9.7.

На рис. 9.21 представлена сеть связи, в которой УИ и УП, соответ­ственно, имеют координаты {1, 2} и {10, 2}. Из УИ определяем геомет­рическое направление на УП (указано пунктиром). С данным направ­лением совпадает исходящая ЛС к узлу с координатами {4, 2}. В УК {4, 2} выбираем исходящую ЛС к УК с координатами {7, 3}, так как она имеет наименьший угол отклонения от геометрического направления на УП. В УК {7, 3} подобным образом выбираем ЛС к УК {8, 2}. В УК {8, 2} выбираем Л С к УК {10, 2}.

Рис. 9.21. Пример формирования ПРИ логическим методом

Таким образом: μ({1, 2}; {10, 2}) = ({1,2}, {4, 2}, {7, 3}, {8, 2}, {10, 2}). Достоинством данного метода является простота и отсутствие необ­ходимости передачи служебной информации по сети. В то же время логический метод не является динамическим и не решает задачу гло­бальной оптимизации ПРИ.

Логически-игровой метод [17] формирования ПРИ является обобщением логического и игрового методов. По аналогии с логиче­ским методом сеть связи вкладывается в прямоугольную систему координат, в соответствии с которой каждому узлу сети присваива­ется собственный адрес (X, У). В каждом УК j имеется матрица которая имеет следующий вид:

и содержит S⁰ строк. Учитывая, что возможно увеличение числа УК на сети, то S⁰ выбирают таким, чтобы S⁰ > S. Количество столбцов мат­рицы P^0(j) для УК под номером j равно: (Н_j + 3), где H_j - число исхо­дящих ЛС из у-го узла; три столбца отводится для номеров УП, пред­ставленных в общепризнанной нумерации и прямоугольной системе координат (X, У).

На момент ввода узла в эксплуатацию матрица содержит только информацию о смежных номерах УК с данными выраженных в прямо­угольной системе координат: (X_Qj, Y_Qj), ..., (X_vj, Y_vj).....(X_Hj, Y_Hj). По мере функционирования сети связи матрица Р^0(j) заполняется и кор­ректируется.

Определение исходящих ЛС осуществляется логическим методом, а заполнение и корректировка матрицы P^0(j) осуществляется игровым методом.

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

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

Градиентный состоит в том, что в каждом транзитном УК, начиная с УИ, в процессе выбора исходящей Л С участвуют не все ЛС, а лишь часть (наиболее предпочтительные). Если в одном из УК исходящие ЛС, участвующие в выборе, не доступны, то данной заявке на форми­рование маршрута дается отказ.

В результате градиентного выбора маршрут будет формироваться вдоль геометрического направления с УИ на УП (рис. 9.22).

Выбор ЛС, при котором искомый маршрут формируется и в проти­воположную сторону от УП, будем называть диффузным.

Таким образом, диффузный выбор исходящих ЛС допускает воз­можность выбора любой доступной исходящей ЛС (рис. 9.22).

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

Рис. 9.22. Градиентный и диффузный выбор исходящих ЛС

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

Возможен и комбинированный способ выбора исходящих ЛС, который содержит как вероятностную, так детерминированную компоненты.

Учитывая перечисленные градации, можно указать множество ва­риантов последовательных алгоритмов выбора исходящих ЛС в УК (например, «Диффузный, вероятностный» или «Градиентно-диффуз­ный, детерминированный»),

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

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

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

Локально-волновой метод маршрутизации [17] является обоб­щением волнового метода маршрутизации и логического способа по­лучения ПРИ на сети связи. Локально-волновой метод маршрутиза­ции в зависимости от организации выбора исходящей ЛС может быть отнесен к параллельным и параллельно-последовательным методам. В то же время, способ выбора зоны, в которой осуществляется поиск маршрута, в локально-волновом методе может быть вероятностным, детерминированным и комбинированным.

Рис. 9.23. Поиск маршрута локально-волновым методом

Локально-волновой метод маршрутизации состоит в том, что для на­хождения оптимального маршрута в сети между парой узлов из УИ орга­низуется волновой поиск, но не во всех направлениях, а лишь в сторону УП. Волна поиска при этом распространяется в некоторой зоне (рис. 9.23). Ширина и форма зоны в зависимости от приоритета абонента может устанавливаться в заданных пределах. На рис. 9.23 показан ло­кально-волновой поиск на сети от УИ к УП в некоторый момент времени, соответствующий примерно половине пути между парой узлов. Из ри­сунка видно, что поисковая волна - это подвижная узкая зона, все узлы в пределах которой охвачены процессом волнового поиска. По мере продвижения к УП волна оставляет за собой ЛС, исходящие из УИ. Чем выше приоритет абонента, тем больше возможностей он имеет для установления соединения. Таким образом, при данном методе в каждом узле определяются исходящие ЛС из данного узла к смежным узлам, наиболее близко совпадающие с геометрическим направлени­ем на искомый узел. Выбранные исходящие ЛС располагаются в ряд по степени предпочтительности.

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

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

Рис. 9.24. Классификация методов маршрута

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