Книги по разным темам Pages:     | 1 | 2 | 12 Прац УНДРТ, 2004, № 4 (40) УДК 621.391 Лемешко А. В.

Lemeshko A. V.

Тензорная модель многопутевой маршрутизации агрегированных потоков с резервированием сетевых ресурсов, представленная в пространстве с кривизной Tensor Model of Multipath Routing of the Aggregated Flows with Reservation of Network Resources, Represented in Space with Curvature Аннотация Предложена математическая

Abstract

The mathematical model of multipath модель многопутевой маршрутизации агреги- routing of the aggregated flows with reservation of рованных потоков с резервированием сетевых network resources, represented by tensors of space ресурсов, представленная тензорами простран- with curvature is offered. Model of routing oriented ства с кривизной. Модель маршрутизации ори- on usage in networks with support of guaranteed ентирована на использование в сетях с под- quality of services. The probing of model has conдержкой услуг связи гарантированного качества. firmed efficiency of the decisions, received on its Исследование модели подтвердило эффектив- basis.

ность получаемых на ее основе решений.

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

дач в телекоммуникационных сетях (ТКС) претер- С целью получения многопутевых решений пели значительное изменение. Это, прежде всего, комбинаторные модели поиска кратчайшего пути, связано с мультисервисностью предоставляемых положенные в основу большинства протоколов услуг связи и необходимостью обеспечения диф- однопутевой маршрутизации, в настоящее время ференцированных гарантий качества обслуживания существенно видоизменяются [3], что также ха - QoS (Quality of Service) [1]. В современных сетях рактерно для математических моделей решения связи стало нормой, что предоставление "hard" QoS маршрутных задач, представленных сетями массвязано так или иначе с резервированием сетевых сового обслуживания [4]. Однако в рамках данных ресурсов вдоль прокладываемого пути передачи подходов расчет множества маршрутов обслужитрафика. Поэтому вновь разрабатываемые прото- вания трафика подчинено лишь самоцели - реаликолы маршрутизации функционируют согласо- зации многопутевой стратегии маршрутизации, а ванно с сигнальными протоколами резервирования вот задачи контроля качества вдоль проложенных сетевых ресурсов, например, RSVP (Resource Res- путей остаются нерешенными. По этой причине ervation Protocol) и SCR-LDP (Signalling актуальной представляется научная задача, свяConstraint-based Routed Label Distribution Protocol) занная с разработкой моделей, методов и протокосоответственно в сетях IP (Internet Protocol) и MPLS лов многопутевой маршрутизации с поддержкой (Multiprotocol Label Switching), а в АТМ-сетях услуг связи гарантированного качества.

применяется маршрутизирующий протокол PNNI Для решения поставленной задачи путем ре(Private Network-to-Network Interface), выполняю- зервирования сетевых ресурсов для каждого польщий одновременно и функции протокола сигнали- зовательского трафика в отдельности хорошо себя зации при установлении соединений [2]. С другой зарекомендовал тензорный подход [5, 6], связанный стороны превалирующее положение на рынке с применением методов тензорного анализа сетей протокольных решений занимают протоколы од- [7]. Однако низкая масштабируемость подобных нопутевой маршрутизации - PNNI, OSPF (Open решений вызвала необходимость расширения тенShortest Path First) и IS-IS (Intermediate System зорных моделей маршрутизации для агрегирован-to-Intermediate System), которые весь трафик от ных потоков, т.е. объединенных в единый поток отправителя к получателю маршрутизируют вдоль однотипных пользовательских трафиков, как праодного, обычно кратчайшего в выбранной метрике, вило, с одинаковыми требованиями к гарантиям пути. Причина этого кроется, во-первых, в относи- качества своего обслуживания. По этой причине тельной простоте организации процесса резерви- целью данной статьи является разработка тензоррования сетевых ресурсов, а во-вторых, в отсутст- ной модели многопутевой маршрутизации агрегивии приемлемых решений задач многопутевой рованных потоков с резервированием сетевых ремаршрутизации, которые остро востребованы, в сурсов и поддержкой QoS.

том числе, в рамках концепции ТЕ (Traffic EngiЛемешко А. В. Тензорная модель многопутевой маршрутизации агрегированных потоков с резервированием сетевых ресурсов, представленная в пространстве с кривизной Прац УНДРТ, 2004, № 4 (40) Тензорная модель ТКС, представленная одномерной сетью В рамках тензорного анализа сетей [7] при мо- графов.

делировании структуры ТКС одномерным сим- плициальным комплексом вводится понятие одномерной сети S = (U, V), состоящей из двух мноuжеств: конечного множества U {ui,i 1, m} нульмерных симплексов - узлов сети, и конечного vvмножества V {vj, j 1, n}, одномерных симплексов - ветвей сети. Узлы сети моделируют коммуv5 таторы, маршрутизаторы (Мр) ТКС, а ветви - u1 uvтракты передачи. Упрощенным представлением vодномерной сети является ориентированный граф, vпоэтому при анализе одномерных сетей вводимые ниже важные сетевые термины и понятия, в ряде vслучаев, имеют близкие по смыслу аналоги в теоuuрии графов.

4 Путь в сети представляет собой конечную последовательность ветвей. Путь называется контуром или замкнутым путем, если его конечные Рисунок 1 - Структурная модель ТКС, представленная одномерной сетью узлы одинаковы. Например, путь, проходящий последовательно по ветвям v1, v3 и v2 (рис. 1) является Пусть сеть S содержит n ветвей, m узлов и контуром ( ). Частным, но важным в тензорном несвязных компонент. Тогда ранг сети p(S) и циканализе сетей случаем представления разрезаюломатическое число (S) определяют в ней соотщего множества является узловая пара, которая ветственно число базисных контуров и узловых пар формально представляет собой два различных узла связной сети и определяется всецело инцидент (S) = m - ; (1) ными ко второму узлу ветвями. На рис. 1 узлы u1 и (S) = n - m +, (2) u5 определяют узловую пару под номером один ( ), но с точки зрения разрезающих множеств уз- обусловливая тождество ловая пара образована ветвями v6 и v7. Узел u1, n = (S) + (S).

относительно которого определяются узловые па- ры, называется опорным. Структура сети определяет пространство, разПродуктом в сети называется однородная ин- мерность которого соответствует числу ветвей сети формационная нагрузка - пользовательский трафик, [5, 7]. При этом системы координат (СК) образуют обслуживаемый ТКС. Полюсами называются те множества базисных контуров и узловых пар, а в узлы сети, через которые в сеть поступает или через роли координатных осей выступают сами базисные которые убывает из сети определенный продукт. Все контуры и узловые пары. Преобразование струкостальные узлы называют внутренними. Далее ос- туры сети с сохранением числа ее ветвей может новное внимание будет уделено двухполюсным од- трактоваться как изменение системы координат ее нопродуктовым сетям, т.е. сетям в которых во мно- рассмотрения. Например, для ТКС, структура кожестве узлов выделяется два полюса: один исток и торой представлена топологической моделью ододин сток, между которыми обслуживается (пере- номерной сети (рис. 1), содержащей пять узлов дается) один тип трафика - продукт сети.

(u1 u5, m = 5) и семь ветвей (v1 v7, n = 7), разВажным моментом при рассмотрении путей в мерность введенного пространства-структуры сети, контуров и узловых пар, является то, что с равна семи. Вследствие справедливости выражений любым из них тесно связано понятие "направление" (1) и (2) число несвязных подсетей ( ) равно едиили "ориентация". Причем для контура ориентация нице, количество базисных узловых пар ( ) соотустанавливается за или против хода часовой ветствует четырем, а численность базисных констрелки, а для разрезающих множеств (узловых туров ( ) равняется трем, что определяет в сумме пар) направление задается от одной образованной общее число ветвей в сети.

ими (разрезанной) подсети к другой. Например, Во введенном n-мерном пространстве произвеконтур имеет ориентацию противоположную 1 дем тензорное описание ТКС с помощью одноваконтуру, а разрез (узловая пара) совпадает с 2 лентного тензора интенсивностей трафиков с i ориентацией образующих его ветвей v6 и v7. Стоит компонентами, одновалентного тензора вреотметить, что ориентация контуров и узловых пар менных задержек передачи пакетов T с компоненможет задаваться исследователем в общем случае тами, а также тензора второй валентности Q, коj произвольно, и не связана с физикой моделируемой ординаты которого рассчитываются исходя из высистемы как в случае задания ориентированных ражения Лемешко А. В. Тензорная модель многопутевой маршрутизации агрегированных потоков с резервированием сетевых ресурсов, представленная в пространстве с кривизной Прац УНДРТ, 2004, № 4 (40) ных потоков, является компромиссом между ре qij i j, (i, j 1, n), (3) зервированием ресурсов для каждого конкретного i где - интенсивность трафика, передаваемого чепользовательского трафика и отсутствием резеррез i-й базисный путь, измеряемая в пакетах/с;

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

например, в маршрутизирующих протоколах В прямом обозначении или безиндексной заConstrained OSPF (CSPF) и IS-IS расширен переписи выражение (3) принимает вид чень используемых метрик путем включения новых типов объявлений для распространения по сети Q = T, информации о номинальной и нерезервированной где - знак тензорного умножения.

(доступной) пропускной способности каждого Для обеспечения многоаспектного (многостотракта передачи в MPLS-сетях. Такие же расшироннего) описания ТКС в рассматриваемом n-меррения коснулись и протокола RSVP, которые уже ном дискретном пространстве-структуре могут прописаны рабочей группой по инженерным пробыть приняты во внимание целый ряд систем коблемам сети IETF (Internet Engineering Task Force) в ординат. Основное требование, которое должно виде соответствующих рабочих документов (Interудовлетворяться в процессе выбора, это информаnet Draft) [2].

тивность этих систем координат, т.е. в этих СК Для дальнейшего удобства тензорной формадолжны быть искомые или известные проекции лизации уравнения поведения системы выражение различных компонент тензора Q, опираясь на ко(4) представим в следующем виде торые, можно рассчитать необходимые компоi i i i v ( ( )), (i 1, n). (5) ненты в той или иной СК. По этой причине введем в v v v v i рассмотрение две координатные системы. Первая - Уравнение (5) характеризует процессы инфорсистема координат ветвей сети, которой отвечает мационного обмена, протекающие в отдельных структура с отдельными несоединенными между элементах - ветвях сети. Исходя из постулата персобой ветвями. Вторая - система координат бавого обобщения Г. Крона [7], форма записи уравзисных контуров и узловых пар сети, отвечающая нений поведения сети в целом должна соответстреальной структуре сети. Подобный выбор СК вовать уравнению поведения отдельных элементов, обусловлен тем, что в системе координат ветвей что обуславливает замену системы скалярных сети необходимо рассчитать неизвестные величиуравнений (5) векторно-матричным уравнением ны: интенсивность трафика и величину временной вида задержки в каждом тракте передачи ТКС. В системе = LvTv, (6) v координат базисных контуров и узловых пар про1 v екции тензоров и T определяют исходные данные v для решения расчетных задач - интенсивность вн внешнего трафика и требуемую задержу переi v где и Tv i - векторы, соответстv v дачи.

трб При обслуживании агрегированного потока в основу функционального построения тензорной n v v n модели ТКС будет положено уравнение поведения венно, интенсивностей трафиков и задержек переотдельно взятого элемента системы, полученное ij путем моделирования каждой ветви сети системой дачи пакетов в ветвях сети размерности n; Lv lv массового обслуживания типа M/M/1 - однока - диагональная матрица размерности n n, элементы нальной моделью с пуассоновским потоком заявок главной диагонали которой рассчитываются сои показательным законом распределения времени гласно выражению обслуживания [4], ii i lv i v i, ( i 1,n ). (7) v v v, (i 1,n), (4) i i i v v Исходя из второго постулата Г. Крона уравнеi в котором - величина пропускной способности ние поведение ТКС (6), сохраняя неизменным свой v вид для различных координатных систем ее рас(ПС) ветви vi (1/с), выделенная для обслуживания i v смотрения, принимает тензорную форму агрегированного потока с интенсивностью, - v i задержка передачи одного пакета в этой ветви. = LT. (8) Отличительной особенностью зависимости (4) Ввиду одинаковой размерности введенных коявляется то, что в ней фигурирует не номинальная ординатных систем существуют однозначные ПС ветви vi, а именно выделенная, т.е. подлежащая правила преобразования координат любых геодальнейшему резервированию, величина пропускметрических объектов из одной системы координат ной способности.

в другую. Если эти геометрические объекты являПодобный подход, основанный на резервироются тензорами, то по определению [7] правила вании сетевых ресурсов в интересах агрегированЛемешко А. В. Тензорная модель многопутевой маршрутизации агрегированных потоков с резервированием сетевых ресурсов, представленная в пространстве с кривизной Прац УНДРТ, 2004, № 4 (40) координатного преобразования носят линейный = L T. (10) характер и формализуемы с помощью невырожСогласно обратному тензорному признаку тенденной квадратной матрицы размера n n. Матрица зор L является дважды контравариантным метриконтравариантного преобразования C определяется ческим тензором, проекции которого при смене из соотношения координатной системы преобразуются следующим = C, v образом:

где, - представленные в виде векторов разv L = AtLvA, мерности n проекции тензора во введенных выше где Lv, L - проекции тензора L в СК ветвей сети и координатных системах отдельных ветвей сети, а базисных контуров и узловых пар соответственно.

также базисных контуров и узловых пар. В свою Согласно выражению (7) координаты метрического очередь, вектор имеет составляющие ij 1 тензора ( lv ) в общем случае зависят от координат i точки пространства ( ). Это отличительный v признак пространств с кривизной, в отличие от j p ; ;, евклидовых пространств, рассмотренных в [5, 6].

Pages:     | 1 | 2 |    Книги по разным темам