Книги по разным темам УДК 621.391 Лемешко А.В., Евсеева О.Ю., Дробот О.А.

Lemeshko A.V., Evseeva O.Yu., Drobot O.A.

Методика выбора независимых путей с определением их количества при решении задач многопутевой маршрутизации The Method of Paths Independents Choice with Definition of their Quantity at the Solving of Multipath Routing Problem Аннотация В статье предлагается методика

Abstract

In the article the method of a choice of выбора количества путей при решении задач мно- paths quantity at the solving of problem of multipath гопутевой маршрутизации. На основе геометри- routing is offered. Mathematical expression for calcuческого представления структуры телекоммуни- lation of quantity independent paths is offered for the кационной сети введено линейное пространство solving of problems multipath routing. The formula is путей, базис которого определяет количество не- received on the basis of geometrical representation of зависимых путей между заданной парой сетевых structure of a network with introduction of linear path узлов. space.

Введение Многопутевая маршрутизация была и остается в Switching) при решении задач многопутевой марсовременных и перспективных мультисервисных шрутизации используются множество протоколов - телекоммуникационных сетях (ТКС) эффективным RIP (Routing Internet Protocol), IGRP (Interior Gateсредством повышения производительности сети и way Routing Protocol), EIGRP (Extended IGRP), IS-IS отказоустойчивости маршрутных решений (Fast (Intermediate System - to - Intermediate System), Reroute) [1], обеспечения скоростных и вероятност- OSPF (Open Shortest Path First) и PNNI (Private Netно-временных показателей качества обслуживания work - to - Network Interface), в которые заложены (Quality of Service, QoS) [2], а также сбалансирован- эвристические процедуры балансировки нагрузки по ной загрузки буферных и канальных сетевых ресур- путям как с равной, так и с различной стоимостью сов (Load-Balancing Routing, Traffic Engineering) [3]. (метрикой). Например, протоколы RIP и OSPF выКлючевой проблемой, с которой приходится полняют автоматическую балансировку нагрузки сталкиваться исследователям и производителям се- одновременно по шести маршрутам с равной стоитевого оборудования при проектировании и внедре- мостью, а в протоколах IGRP и EIGRP количество нии аппаратно-программных средств многопутевой используемых путей с различной метрикой опредемаршрутизации, является определение необходимо- ляется административно с помощью команды vaго количества путей, поддерживаемых тем или иным riance [4]. Тенденция к административному, т.е. теомаршрутизирующими протоколом. ретически необоснованному выбору числа путей В настоящее время в современных транспортных сохраняется и во вновь предлагаемых моделях мнотехнологиях - IP (Internet Protocol), ATM (Asynchro- гопутевой маршрутизации [5, 6].

ny Transfer Mode) и MPLS (MultiProtocol Label Геометризация структуры ТКС В дальнейшем будем основываться на том, что секающимися. Но, как показывает практика, подобпуть - это упорядоченное множество последова- ный подход не реализует в должной мере преимущетельно соединенных между собой сетевых узлов и ства многопутевых решений маршрутных задач, т.к.

трактов передачи (ТП). Для удобства в данной рабо- не всегда трафик использует полностью канальные те путь будет записываться как последовательность ресурсы трактов передачи вдоль рассчитываемого образующих его трактов передачи. пути. В этой связи, как правило, необходимо испольВ свою очередь, множество рассчитываемых пу- зовать одновременно множество путей с реберным и тей между заданной парой узлов сети должно удов- (или) узловым пересечением (рис.1 б). При этом, летворять ряду требований, касающихся их незави- пути ТП1-ТП4 и ТП2-ТП3-ТП4 соотносятся друг симости. Под независимостью путей в некоторых относительно друга как пути с реберным пересечеслучаях понимается их узловая и реберная непересе- нием (ТП4 является общим для обоих путей), а пути каемость (рис.1 а), т.е. в предельном случае пути не ТП1-ТП6-ТП7 и ТП2-ТП3-ТП4 - как пути с узловым должны полностью совпадать друг с другом. Пути, пресечением, т.к. для этих путей узел 2 является обобразованные последовательностью трактов щим.

(рис.1 а) ТП1-ТП2; ТП4-ТП5; ТП3, являются непереУзел Узел Узел 1 Узел ТП ТП ТП ТП ТП ТП ТП Узел ТП ТП 4 ТП Узел ТП ТП Узел Узел Узел а) б) Рис.1. Примеры структур сетей с непересекающимися (а) и пересекающимися (б) типами путей С целью решения поставленной задачи, касаю- нию и будет определять общее количество незавищейся определения необходимого количества путей симых путей в сети между узлами ui и u.

j в ходе реализации многопутевой маршрутизации, С целью определения размерности введенного произведем геометризацию структуры ТКС с введепространства ( n(i, j) ) для математического описания нием ряда пространств, в том числе пространства path путей и соответствующих ему систем координат.

Как известно [7, 8], при описании структуры ТКС того или иного пути (, k 1, n(i, j) ) произвольно k path одномерной сетью (одномерным симплексом) на введем ориентацию трактов передачи ( vl,l 1, n ) с структуре ТКС, состоящей из соединенных между использованием следующей алгебры путей: тракт собой n ветвей ( v, j 1, n ) и m узлов ( ui,i 1, m ), j передачи входит в выражение для определения пути могут быть введены линейные дискретные просо знаком л+, если ориентация тракта совпадает с странства трактов передачи размерности n, разреориентацией пути, и со знаком л- в противном слузающих множеств (узловых пар) размерности m чае. Например, для структуры ТКС (рис.2 а) множеи контуров сети ( ) размерности n m. Напомство путей между узлами u1 и u4 можно предстаним, что выбор базисных контуров производиться на вить в виде следующей системы уравнений хордах произвольно определенного остова сети, т.е.

каждая хорда остова должна входить лишь в один v1 v2;

базисный контур [7].

v4 v5;

Параллельно с этими пространствами введем (1) v1 v3 v5;

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

v4 v3 v2.

Размерность этого пространства n(i, j) по определеpath uuvvvvuvvvuuа) б) Рис.2. Примеры анализируемых структур ТКС ) не определяет базис путевого пространства (эти пути Ранг (rank) матрицы путей ( A(1,4h) в этом случае pat являются зависимыми), т.к. соответствующая матравен трем, т.е.

рица путей будет иметь ранг равный трем:

1 1 0 0 1 0 0 0 0 1 0 0 0 1 1 0 1 0 1 0 rank 3, (2) rank 3, 1 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 и определяет число независимых путей в сети при n(1,5) 4, т.е. остается неохваченным один баpath ( n(1,4) ) между парой узлов u1 и u4.

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

u1 и u5, т.е. путей, не содержащих контуров (пе- Базис путевого пространства для данного примера определяет следующее множество путей между тель), можно представить в виде следующей систеузлами u1 и u5 (рис.2 а) мы уравнений v1 v6 v7 ;

v1 v6 v7 ;

v1 v4;

v2 v5;

(6) v1 v3 v5;

v2 v3 v6 v7 ;

(3) v2 v5;

v1 v4;

v2 v3 v4;

т.к. соответствующая матрица путей имеет ранг равv2 v3 v6 v7.

ный четырем:

) Ранг матрицы путей A(1,4h в этом случае равен 4:

1 0 0 0 0 1 pat 0 1 0 0 1 0 1 0 0 0 0 1 rank 4.

0 1 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 rank 4. (4) 0 1 0 0 1 0 Если при выборе множества независимых путей 0 1 1 1 0 0 0 определенный ТП входит в тот или иной базисный путь со знаком минус, то это означает, что пере0 1 1 0 0 1 дача пакетов в этом тракте будет происходить в обТаким образом, количество независимых путей в ратном направлении по отношению к изначальной сети между заданной парой узлов (размерность про- произвольно выбранной ориентации этого ТП.

странства путей) равно рангу соответствующей мат- Таким образом, при реализации многопутевой рицы путей: стратегии маршрутизации для сети (рис.1 б) при передаче пакетов от первого узла к пятому нет необхо, димости устанавливать более четырех путей. С техn(i, j) rank A(iaj). (5) path p th нологической точки зрения поддержка избыточных путей нецелесообразна, т.к. это всегда связано с неТо есть, на всем множестве путей существует опобходимостью дополнительных расходов времени и ределенное количество путей, определяющих базис сетевых (буферных и канальных) ресурсов. Испольпутевого пространства. При этом выбор базисных зование выражения (5) позволяет определить верхпутей, в общем случае, может производиться мноний предел количества рассчитываемых путей при жеством способов. Поэтому, при выборе базисных организации многопутевой маршрутизации.

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

Например, множество путей между узлами u1 и мо при формировании матрицы путей A(i, j) запиpath u5 (рис.2 б) сывать все возможные пути между заданной парой узлов в сети. Для сетей большой размерности это v1 v6 v7 ;

достаточно трудоемкая операция. В этой связи ниже v1 v3 v5;

предлагается вывод аналитического выражения для v2 v5;

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

v2 v3 v6 v7 ;

Порядок выбора независимых путей и вывод аналитического выражения для определения их количества в сети произвольной структуры Индуктивно можно доказать, что количество не- Введение же ветви между узлами u4 и u5, а зависимых путей ( n(i, j) ) между парой узлов ui и также u6 и u7 увеличит количество независимых path контуров до трех, а базисных путей до четырех, u на один больше, чем число независимых контуj придав некоторую свободу их выбору. Для трехконров [8, 9], т.е.

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

n(i, j) n m 2. (7) path,,,, (8) 1 2 3 Например, для древовидной сети (рис.3 а) рагде v1 v3 v8 v6 ; v1 v2 v4 v9.

3 зомкнутый путь между узлами u1 и u7 можно При этом любой другой путь между узлами u1 и представить следующим образом:

u7 в сети можно представить в виде линейной комv1 v2 v5 v6.

бинации перечисленных базисных путей. Например, Действительно, оставляя количество узлов сети путь постоянным, введение каждой последующей ветви, v7 v8 v5 v4 vспособствующей образованию контура в сети, приводит к возникновению дополнительного пути.

в базисе (8) можно представить в виде Для одноконтурной сети (рис.3 б) двумя базис2.

ными путями из узла u1 в u7 являются пути и 5 1 2 3, где 2 Анализ выражения (7) показывает, что количество независимых путей в сети инвариантно относиv7 v3 v2 v5 v6.

тельно рассматриваемой пары узлов, т.е. индексы ( i, j ) в этом выражении можно опустить.

uuuuvvvuvuu2 vu2 vvvvu1 v1 u4 vu1 vuu5 uvа) б) uuvvvu2 vuvu1 vuvv7 v8 uв) Рис.3. Примеры одномерных сетей с различным числом контуров Таким образом, размерность пространства путей путей. Например, для сети (рис.2 а) остов состоит из на единицу больше (7) чем размерность пространст- ветвей v1,v3,v5, а для структуры (рис. 2 б) остов ва контуров [7, 8]. В этой связи для непосредственопределяется множеством v2,v3,v4,v7. При этом ного определения множества независимых путей для структуры сети (рис.2 б) в качестве хорд выстумежду заданной парой узлов воспользуемся методипает множество v1,v5,v6, а первые три базисных кой определения базисных контуров. В соответствии с предлагаемым подходом, основанным на ранее пути задаются множеством,, (6). Недос1 2 произведенной геометризации структуры ТКС, в тающий базисный путь выбирается между заданной качестве базисных выбирается определенное множепарой узлов таким образом, чтобы он не совпадал с ство путей мощности n m 2, в котором n m ранее определенными базисными путями. Для путей обязательно проходят по хордам предвариструктуры сети (рис.2 б) в качестве такого пути мотельно выбранного остова сети, причем каждая хоржет выступать путь (6).

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

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

ов сети предложенным выше способом, чтобы ранг.

итература 1. Pan P. et al. Fast Reroute Techniques in RSVP-TE // Internet Draft / draft-pan-rsvp-fastreroute-00.txt. 2002.

2. Lee G. M. A survey of multipath routing for traffic engineering // Proc. of LNCS 3391. - Springer-Verlag, 2005. - Vol. 4. - P. 635-661.

3. Поповский В.В., Лемешко А.В., Мельникова Л.И., Андрушко Д.В. Обзор и сравнительный анализ основных моделей и алгоритмов многопутевой маршрутизации в мультисервисных телекоммуникационных сетях // Прикладная радиоэлектроника. - 2005. - Том.4. - Вып. № 4. - С. 372-382.

4. Руденко И. Маршрутизаторы CISCO для IP-сетей. - М.: КУДИС-ОБРАЗ, 2003. - 656 с.

5. Вишневский В.М. Теоретические основы проектирования компьютерных систем. - М.: Техносфера, 2003. - 512 с.

6. Jia Y., Nikoladis I. Gburzynski P. Multiple path QoS routing // Proc. Int. Conf. Communications (ICC 2001). - Helsinki, 2001. - P.

2583-2587.

7. Сешу С., Рид М.Б. Линейные графы и электрические цепи. - М.: Высш. школа, 1971. - 448 с.

8. Крон Г. Тензорный анализ сетей. - М.: Сов. радио, 1978. - 719 с.

9. Лемешко А.В. Тензорные модели решения задачи поиска кратчайшего пути // Прикладная радиоэлектроника. - 2003. - Том.2, № 1. - С. 52-59.

   Книги по разным темам