Место транспортных технологий IP и MPLS в мультисервисных сетях

СОДЕРЖАНИЕ СОДЕРЖАНИЕ ПЕРЕЧЕНЬ УСЛОВНЫХ СОКРАЩЕНИЙ ВВЕДЕНИЕ

1. Место транспортных технологий IP и MPLS в мультисервисных сетях

1.1 Характеристики транспортных технологий мультисервисных ТКС

1.1.1 Особенности транспортного уровня NGN на основе IP-протокола и АТМ технологии

1.1.2 Особенности технологии MPLS

1.2 Анализ сетевых ресурсов транспортных технологий мультисервисных ТКС

2. Математические модели балансировки информационных ресурсов в технологиях IP и MPLS

2.1 Особенности однопутевой и многопутевой маршрутизации

2.2 Анализ существующих математических моделей маршрутизации и балансировки информационных ресурсов в ТКС

2.2.1 Модели на основе вероятностно-временных графов

2.2.2 Оптимизационные модели управления сетевыми ресурсами

2.2.3 Потоковые модели многопутевой маршрутизации

3. Исследование моделей балансировки информационных ресурсов

3.1 Численное моделирование предложенных моделей балансировки информационных ресурсов ПЕРЕЧЕНЬ ССЫЛОК

ПЕРЕЧЕНЬ УСЛОВНЫХ СОКРАЩЕНИЙ

ATM (Asynchronous Transfer Mode) — режим асинхронной передачи

AS (Autonomous System) — автономная система

IGRP (Interior Gateway Routing Protocol) — протокол маршрутизации внутреннего шлюза

IP (Internet Protocol) — протокол сети Internet

ITU (International Telecommunication Union) — Международный союз электросвязи

MPATH (Multipath Routing Algorithm) — алгоритм многопутевой маршрутизации

MPLS (MultiProtocol Label Switching) — многопротокольная коммутация меток

NGN (Next Generation Network) — сеть следующего поколения

OSI (ЭМВОС) — эталонная модель взаимодействия открытых систем

OSPF (Open Shortest Path First) — протокол маршрутизации по кратчайшему пути

QoS (Quality of Service) — качество обслуживания

RIP (Routing Internet Protocol) — протокол маршрутизации сети Internet

TE (Traffic Engineering) — инжиниринг трафика АУ — агент управления КС — канал связи ПС — пропускная способность ТКС — телекоммуникационная система

ВВЕДЕНИЕ

Процес развития перспективных мультисервисных телекоммуникационных систем (ТКС), являющихся базой для создания и использования сетей следующего поколения (Next Generation Network, NGN), существенно зависит от развития их средств управления. К основным таким средствам относят механизмы управления трафиком, который представляет собой информационный ресурс, а также средства распределения пропускной способности каналов связи, являющейся канальным ресурсом ТКС.

Эффективным средством удовлетворения противоречивых требований по обеспечению гарантированного качества обслуживания и сбалансированной загрузки ресурсов ТКС выступает многопутевая маршрутизация, в ходе которой пакеты одного трафика могут передаваться одновременно вдоль нескольких путей, обеспечивая сбалансированную загрузку ТКС и способствуя повышению, прежде всего, скоростных и связанных с ним вероятностно-временных показателей качества обслуживания. К средствам многопутевой маршрутизации выдвигаются две группы требований. Требования первой группы являются традиционными для любых алгоритмов маршрутизации и предполагают их низкую вычислительную сложность, быструю сходимость и минимальные объемы создаваемого служебного трафика. Вторая группа требований обусловлена необходимостью обеспечения гарантированного качества обслуживания и сбалансированной загрузки ТКС на основе реализации принципов концепций управления трафиком — Traffic Engineering QoS-based (constraint based) Routing и Load-Balancing Routing. В связи с тем, что в большинстве своем приведенные требования по своей природе являются противоречивыми, в настоящее время предложен целый ряд подходов к формализации и решению задач многопутевой маршрутизации, основанных на использовании различных математических моделей и алгоритмов решения возникающих в том или ином виде оптимизационных задач.

1. МЕСТО ТРАНСПОРТНЫХ ТЕХНОЛОГИЙ IP И MPLS В МУЛЬТИСЕРВИСНЫХ СЕТЯХ Современному периоду развития телекоммуникационных сетей (ТКС) соответствует все возрастающее увеличение спроса на инфокоммуникационные услуги — услуги связи, предполагающие автоматизированную обработку, хранение или предоставление по запросу информации с использованием средств вычислительной техники, как на входящем, так и на исходящем конце соединения.

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

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

1.1 Характеристики транспортных технологий мультисервисных ТКС Согласно рекомендации МСЭ Y.2001 «Сеть следующего поколения» NGN — это пакетная ТКС, которая способна предоставлять службы/услуги электросвязи и возможность использовать одну либо несколько широкополосных транспортных технологий, обеспечивающих качество обслуживания, и в которой функции, относящиеся к службам, независимы от нижележащих технологий, реализующих транспортировку. NGN позволяет организовать свободный доступ для пользователей, по их выбору, к сетям и к конкурирующим поставщикам служб и/или к службам/услугам. Такая сеть поддерживает обобщенную подвижность, которая будет давать возможность постоянного и повсеместного обеспечения служб для пользователей [2], а также реализует принцип глобальной доступности услуги — 4Any — Any Service — Anywhere — Anyway — Anytime — или любая услуга в любом месте любым способом в любое время. Этим обстоятельством NGN определяет себя как мультисервисная сеть. При этом она имеет существенные возможности для развития и привлечения новых абонентов за счет расширения перечня предоставляемых услуг.

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

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

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

Рисунок 1.1 — Уровневая архитектура NGN

Рисунок 1.2 — Функциональная схема NGN

Сети NGN, будучи результатом слияния обычных телефонных сетей и сети Интернет, объединяют в себе их лучшие черты:

— адаптируемость для передачи трафика любого вида, что можно сравнить с адаптируемостью сети Интернет в противоположность отсутствию гибкости передачи данных в ТфОП;

— гарантированное качество голосовой связи и критически важных приложений передачи данных, что отвечает надежности ТфОП в противоположность негарантированному качеству связи в сети Интернет;

— низкая стоимость передачи в расчете на единицу объема информации приближается к стоимости передачи данных в сети Интернет, а не ТфОП.

Одним из открытых вопросов при создании мультисервисной NGN сети является соглашение об использовании определенной базовой транспортной технологии с коммутацией пакетов. В качестве технологической базы для построения транспортного уровня мультисервисной сети выделяются технологии и протоколы IP (Internet Protocol), ATM (Asynchrony Transfer Mode), MPLS (MultiProtocol Label Switching) [3, 4], однако предложения по использованию каждой из них или их совокупности имеет лишь рекомендательный характер и не определены строго.

1.1.1 Особенности транспортного уровня NGN на основе IP-протокола и АТМ технологии Протокол IP (RFC 791) используется для негарантированной доставки данных, разделяемых на так называемые пакеты от одного узла сети к другому. Это означает, что на уровне этого протокола (третий уровень сетевой модели OSI) не даётся гарантий надёжной доставки пакета до адресата. В частности, пакеты могут прийти не в том порядке, в котором были отправлены, продублироваться (две копии одного пакета), оказаться повреждёнными (обычно повреждённые пакеты уничтожаются) или не прибыть вовсе. Гарантии безошибочной доставки пакетов дают протоколы более высокого (транспортного уровня) сетевой модели OSI — например, TCP — которые IP используют в качестве транспорта.

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

Однако в последнее время широкую известность приобрела стратегия обслуживания IP-пакетов Differential Services (DiffServ) [4], которая основана на вариациях поля качества обслуживания TOS. Основная идея DiffServ заключается в том, что пользовательские пакеты маркируются на уровне протокола IP как относящиеся к определенному классу обслуживания. Все процедуры фильтрации и маркировки пакетов реализуются на границе между сетями клиента и провайдера, в то время как центральная часть сети провайдера должна дифференцированно обслуживать лишь сравнительно небольшое число классов трафика.

Такая модель является довольно простой. Попадающие в сеть пакеты классифицируются и при необходимости подвергаются на границе сети процессу так называемого кондиционирования. Там же осуществляется маркировка пакетов с учетом их принадлежности к одному из поддерживаемых в сети классов обслуживания, именуемых агрегаторами поведения (Behavior Aggrege, BA). Маркер, идентифицирующий агрегатор поведения, представляет собой кодовое слово (DS CodePoint, DSCP), которое помещается в заголовок каждого IP-пакета. Приоритет и тип обслуживания пакетов в сети DS определяются типом локального поведения (Per-Hop Behavior, PHB). Набор значений кодовых слов DSCP отображается на некоторый набор типов локального поведения. PHB локален в том смысле, что он задает метод локального обслуживания пакета (с тем или иным значением DSCP) маршрутизатором, в котором находится пакет, а точнее — способ обслуживания пакета при его отправке в канал, подключенный к выходному для данного пакета интерфейсу маршрутизатора.

В документе МСЭ Y.2001 приведена рекомендация к использованию в качестве ядра NGN IP-сети. Большим преимуществом IP протокола является распространенность, как самой технологии, так и сетевой техники, работающей на ее принципе, в глобальных и локальных компьютерных сетях и сетях цифровой телефонии. Это обстоятельство делает переход к NGN более «гибким» и незаметным для провайдеров услуг и пользователей сети.

Недостатки протокола IP нивелируются посредством применения в качестве ядра NGN технологии асинхронного режима доставки — АТМ. При использовании ATM все коммутационное оборудование становится однородным, решающим для всех видов информации одну задачу — быстрой коммутации фиксированных пакетов (ячеек), и асинхронного временного разделения ресурсов, при котором множество виртуальных соединений с различными скоростями асинхронно мультиплексируются в едином физическом канале [5, 6].

Сеть ATM, способная транспортировать единым методом все виды информации, позволяет обеспечить:

— высокую гибкость и адаптацию сети к изменению уровня требований пользователей к объему, скорости, качеству доставки информации и к появлению требований на предоставление новых услуг, требующих наличия у сети интеллекта;

— повышение эффективности использования сетевых ресурсов за счет статистического мультиплексирования множества источников с пачечным графиком;

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

Однако серьезными недостатками использования АТМ как базовой транспортной технологии NGN являются:

— более высокая, по сравнению с IP, стоимость оборудования и сложность адаптации его к уже существующим сетевым решениям;

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

1.1.2 Особенности технологии MPLS

В основе MPLS лежит принцип обмена меток. Любой передаваемый пакет ассоциируется с тем или иным классом сетевого уровня (Forwarding Equivalence Class, FEC), каждый из которых идентифицируется определенной меткой. Значение метки уникально лишь для участка пути между соседними узлами сети MPLS, которые называются также маршрутизаторами, коммутирующими по меткам (Label Switching Router, LSR). Метка передается в составе любого пакета, причем способ ее привязки к пакету зависит от используемой технологии канального уровня.

Маршрутизатор LSR получает топологическую информацию о сети, участвуя в работе алгоритма маршрутизации — OSPF, BGP, IS-IS. Затем он начинает взаимодействовать с соседними маршрутизаторами, распределяя метки, которые в дальнейшем будут применяться для коммутации. Обмен метками может производиться с помощью как специального протокола распределения меток (Label Distribution Protocol, LDP), так и модифицированных версий других протоколов сигнализации в сети (например, незначительно видоизмененных протоколов маршрутизации, резервирования ресурсов RSVP и др.).

Распределение меток между LSR приводит к установлению внутри домена MPLS путей с коммутацией по меткам (Label Switching Path, LSP). Каждый маршрутизатор LSR содержит таблицу, которая ставит в соответствие паре «входной интерфейс, входная метка» тройку «префикс адреса получателя, выходной интерфейс, выходная метка». Получая пакет, LSR по номеру интерфейса, на который пришел пакет, и по значению привязанной к пакету метки определяет для него выходной интерфейс. Старое значение метки заменяется новым, содержавшимся в поле «выходная метка» таблицы, и пакет отправляется к следующему устройству на пути LSP.

Вся операция требует лишь одноразовой идентификации значений полей в одной строке таблицы. Это занимает гораздо меньше времени, чем сравнение IP-адреса отправителя с наиболее длинным адресным префиксом в таблице маршрутизации, которое используется при традиционной маршрутизации.

Сеть MPLS делится на две функционально различные области — ядро и граничную область (рис. 1.3). Ядро образуют устройства, минимальным требованием к которым является поддержка MPLS и участие в процессе маршрутизации трафика для того протокола, который коммутируется с помощью MPLS. Маршрутизаторы ядра занимаются только коммутацией. Все функции классификации пакетов по различным FEC, а также реализацию таких дополнительных сервисов, как фильтрация, явная маршрутизация, выравнивание нагрузки и управление трафиком, берут на себя граничные LSR. В результате интенсивные вычисления приходятся на граничную область, а высокопроизводительная коммутация выполняется в ядре, что позволяет оптимизировать конфигурацию устройств MPLS в зависимости от их местоположения в сети.

Рисунок 1.3 — Структура MPLS сети Таким образом, главная особенность MPLS — отделение процесса коммутации пакета от анализа IP-адресов в его заголовке, что открывает ряд привлекательных возможностей. Очевидным следствием описанного подхода является тот факт, что очередной сегмент LSP может не совпадать с очередным сегментом маршрута, который был бы выбран при традиционной маршрутизации.

Поскольку на установление соответствия пакетов определенным классам FEC могут влиять не только IP-адреса, но и другие параметры, нетрудно реализовать, например, назначение различных LSP пакетам, относящимся к различным потокам RSVP или имеющим разные приоритеты обслуживания. Конечно, подобный сценарий удается осуществить и в обычных маршрутизируемых сетях, но решение на базе MPLS оказывается проще и к тому же гораздо лучше масштабируется.

Каждый из классов FEC обрабатывается отдельно от остальных — не только потому, что для него строится свой путь LSP, но и в смысле доступа к общим ресурсам (полосе пропускания канала и буферному пространству). В результате технология MPLS позволяет очень эффективно поддерживать требуемое качество обслуживания, не нарушая предоставленных пользователю гарантий. Применение в LSR таких механизмов управления буферизацией и очередями, как WRED, WFQ или CBWFQ, дает возможность оператору сети MPLS контролировать распределение ресурсов и изолировать трафик отдельных пользователей.

Использование явно задаваемого маршрута в сети MPLS свободно от недостатков стандартной IP-маршрутизации от источника, поскольку вся информация о маршруте содержится в метке и пакету не требуется нести адреса промежуточных узлов, что улучшает управление распределением нагрузки в сети.

Таким образом, можно сделать вывод, что наиболее перспективным в качестве транспортного ядра мультисервисных ТКС является использование стека IP/MPLS, в совокупности с сигнализационными протоколами маршрутизации и заказа необходимых сетевых ресурсов.

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

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

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

Рисунок 1.4 — Сетевые ресурсы мультисервисных ТКС Для каждого вида сетевого ресурса разработано и апробировано множество средств и методов его управления, кроме этого, предложены определенные показатели обеспечения качества обслуживания QoS для оптимизации данного ресурса.

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

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

2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ БАЛАНСИРОВКИ ИНФОРМАЦИОННЫХ РЕСУРСОВ В ТЕХНОЛОГИЯХ IP И MPLS

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

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

Наиболее известным и популярным дистанционно-векторным протоколом маршрутизации является протокол RIP (Routing Information Protocol) [4], в рамках которого определение лучшего маршрута происходит на основе простой метрики — количестве переприемов (хопов). Такой подход определяет основной недостаток использования протокола RIP в крупномасштабных ТКС — ограниченность числа сетевых переприемов до 15 устройств. Кроме этого, обновление маршрутных таблиц происходит периодически и не зависит от их актуальности и полноты, что приводит к нерациональному повышению объемов передаваемой служебной информации, способной полностью загрузить некоторые низкоскоростные каналы.

Также, исходя из своей единичной метрики, протокол RIP не обеспечивает достаточную гибкость определения наилучшего маршрута следования пакетов, особенно в случае составных ТКС, содержащих каналы с различной ПС, а также балансировку нагрузки по путям с одинаковой и неравной стоимостью. Эти обстоятельства привели к широкому использованию протокола IGRP (Interior Gateway Routing Protocol), представленного корпорацией Cisco, который поддерживает 255 сетевых переприемов, что обеспечивает его корректную работу в крупномасштабных ТКС.

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

(2.1)

где — ПС;

— задержка передачи;

— загрузка тракта передачи;

— надежность.

Стоит отметить, что показатели композитной метрики учитываются в виде коэффициентов, которые можно административно изменять. В отличие от RIP протокол IGRP предусматривает широкий диапазон значений для своих показателей (надежность и нагрузка — до 255, ширина полосы пропускания — до 10 Гбит/с, задержка — значение до 24-го порядка), что позволяет производить удовлетворительную регулировку общего показателя объединенной сети с большим диапазоном изменения характеристик производительности.

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

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

Наиболее распространенный протокол такого типа — OSPF (Open Shortest Path First), который обеспечивает отправку объявлений о состоянии канала (LSA, Link-State Advertisement) во все маршрутизаторы, которые находятся в пределах одной и той же иерархической области (автономной системы). В данные объявления включается информация о подключенных интерфейсах, об использованных показателях метрики и о других переменных. По мере накопления маршрутизаторами OSPF информации о состоянии канала, они используют алгоритм SPF (алгоритм Дийкстры) для расчета кратчайшего пути к каждому узлу.

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

Протоколы состояния канала характерны также для технологии АТМ (RFC 2386) и в первую очередь направлены на поддержку гарантированного качества обслуживания в пределах постоянных и коммутируемых соединений. Наиболее распространенным протоколом маршрутизации в АТМ является PNNI (Private Network to Network Interface), определенный спецификацией ATM Forum af-pnni-055.000. Данный протокол определяет правила передачи служебных уведомлений для распределенного построения топологической карты сети, на основании которой происходит выбор наилучшего маршрута передачи ячеек между узлом-отправителем и узлом-получателем. По выбранному пути производится установка постоянного либо коммутируемого виртуального соединения с поддержкой заданного уровня качества обслуживания, что определяется использованием QoS-совместимой композитной метрики, которая состоит из следующих показателей:

1. Доступная скорость передачи (AvCR, Available Cell Rate);

2. Максимальная задержка тракта передачи (MaxCD, Maximum Transfer Rate);

3. Максимальная скорость передачи тракта (MaxCR, Maximum Cell Rate);

4. Административный стоимостный коэффициент (AW, Administrative Weight);

5. Процент потери АТМ-ячеек (CLR, Cell Loss Ratio);

6. Разброс задержек тракта и его окружения (CDV, Cell Relay Variation).

Протокол PNNI осуществляет выбор наилучшего пути узлом-отправителем и полностью поддерживает QoS-совместимую архитектуру АТМ, поэтому для маршрутизации в данной технологии не нужно использовать дополнительные программные либо аппаратные средства.

Описанные протоколы базируются на графокомбинаторных алгоритмах однопутевой маршрутизации, таких как алгоритмы Дийкстры, Беллмана-Форда и т. п., которые имеют похожий формализм.

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

(2.2)

где — «вес» кратчайшегопути от вершины к вершине ;

— «вес» дуги между вершинами и .

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

Многопутевая маршрутизация (МПМ), в отличие от однопутевой, поддерживает методы балансировки поступающей нагрузки, что выражается в передаче одного информационного потока вдоль различных путей одинаковой или разной стоимости. Данное обстоятельство обеспечивает сбалансированную загрузку сетевых ресурсов и приводит к повышению эффективной ПС трактов ТКС, улучшению скоростных и вероятностно-временных показателей сети. Алгоритмы многопутевой маршрутизации адаптированы под известные протоколы с поддержкой балансировки: IGRP, OSPF. Наиболее известные из них:

1. ECMP (Equal CostMultipath). Алгоритм расчета путей равной стоимости. Может использоваться в расширениях протокола OSPF, оптимизированного под многопутевые решения.

2. MPA (Multiple PathAlgorithm). Алгоритм нахождения мультипутей. Может использоваться в расширениях протокола OSPF, оптимизированного под многопутевые решения.

3. DSPA (Discount Shortest Path Algorithm). Алгоритм отказа от кратчайшего пути. Используется для минимизации задержки пакетов. Учитывает количество и независимость (не пересекаемость) путей в сети.

4. CRA (Capacity RemovalAlgorithm). Используется для максимизации производительности сети. Учитывает изменение состояния трактов для вычисления путей, максимиирующих поток между узлами.

5. DASM (Diffusing Algorithmfor ShortestMultipath). Обобщает алгоритмы Дийкстры/Шолтена, гарантирует отсутствие петель в рассчитываемых многопутевых таблицах маршрутизации и обеспечивает балансирование загрузки ресурсов сети.

6. ROAM (Routing On-Demand AcyclicMultipath). Алгоритм маршрутизации по требованию, который поддерживает многопутевой способ доставки пакетов без образования петель. Рассчитывает множество независимых путей доставки. Устранена проблема поиска в бесконечность.

7. MDVA (multipath distancevector algorithm). Обобщает распределенный алгоритм Беллмана-Форда на случай расчета множества кратчайших путей.

8. MPATH (MultipathRouting Algorithm). Обобщает дерево кратчайших путей, получаемых в рамках алгоритмов Дийкстры и Беллмана-Форда, в граф кратчайших мультипутей различной стоимости.

9. MPDA (MultipathPartial DisseminationAlgorithm), QMPDA (Quality MultiplePartial DisseminationAlgorithm). Алгоритмы с частичным распространением информации о состоянии сети. Они обеспечивают расчет множества безпетельных путей с учетом изменения состояния трактов сети, в т. ч. при выходе их из строя (QMPDA). Синхронизация информации о состоянии сети ограничена одним переприемом. QMPDA также поддерживает различные классы обслуживания трафиков.

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

(2.3)

где — множество вариантов передачи пакетов от узла к узлу ;

— множество узлов-соседейму узлу;

— кратчайшие пути от узла к узлу

— локальная величина дерева кратчайших путей от узла к узлу .

Выражение (2.3) вместе с условиями устранения петель определяет правила нахождения совокупности маршрутов с наименьшей метрикой для передачи пользовательских информационных потоков.

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

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

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

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

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

2.2 Анализ существующих математических моделей маршрутизации и балансировки информационных ресурсов в ТКС

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

(2.4)

где — параметр.

Тогда функция последовательности смен состояний моделируемой системы может быть записана в виде

(2.5)

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

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

Аппарат ВВГ определяет следующие характеристики исследуемой системы: среднее время выполнения процесса управления (), описываемого таким графом, дисперсия () и вероятность достижения определенной вершины (). Данные характеристики определяются по формулам:

транспортный мультисервисный протокол маршрутизатор

;

; (2.6)

.

Аппарат ВВГ является достаточно удобным средством моделирования процессов управления сетевыми ресурсами с учетом влияния внешней среды. Однако данный математический аппарат также имеет ряд недостатков:

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

— аппарат ВВГ не позволяет корректно описать процессы динамики изменения состояния управляемой системы, обеспечения мультисервисности и гарантированного качества обслуживания одновременно по нескольким показателям;

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

2.2.2 Оптимизационные модели управления сетевыми ресурсами В этом случае, при аналитическом описании процессов управления сетевыми ресурсами формулируется оптимизационная задача, в которой в качестве критерия качества выступают некоторые стоимостные критерии или непосредственные показатели качества обслуживания. Критерием может выступать некоторый функционал следующего вида, например [12, 13]:

. (2.7)

где — критерий качества (время задержки, сетевые ресурсы и т. д.).

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

(2.8)

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

Значение критерия определяется функционалом

(2.9)

где, , — действительные, симметрические, неотрицательные матрицы, инвариантные во времени; - значение времени, когда цель (минимум) будет достигнута.

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

Оптимальная траектория системы управления определяется во время минимизации гамильтониана вдоль этой траектории:

(2.10)

где .

При выполнении условия (2.10) значение оптимального управления находится как

(2.11)

где — конечное состояние управляющей системы.

Данный метод аналитического моделирования имеет ряд существенных недостатков:

— наличие большого количества ограничений (закон сохранения потока, условие отсутствия перегрузок сетевых узлов и трактов передачи) приводит к созданию моделей, неадекватных реальным образцам;

— полученная модель управления является детерминированной; при рассмотрении стохастических процессов аналитическая модель становится громоздкой и имеет малую описательную возможность;

— позволяет учесть лишь небольшое количество критериев управления.

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

Большинство потоковых задач могут быть сформулированы в форме задач математического (линейного, целочисленного, нелинейного) программирования [14, 15]. В ряде важных случаев удобнее решать подобные задачи сетевыми методами в терминах распределения потока на графах. Важно отметить, что при использовании потоковых моделей основное внимание уделяется изучению особенностей структуры сети, что играет главную роль в повышении эффективности вычислительных алгоритмов. В значительной степени сетевой анализ основан на теории графов. Однако сетевое моделирование по сравнению с комбинаторными методами расчета графовых моделей ТКС позволяет получить теоретические результаты и вычислительные алгоритмы, в которых более полно производится учет параметров трафиков, что важно при решении задач обеспечения QoS. В сетевых моделях каждая дуга характеризуется тремя параметрами: минимальным значением потока, который может протекать по дуге (нижняя граница); пропускной способностью, которая показывает, какой максимальный поток можно передавать по дуге (верхняя граница); стоимостью передачи единицы потока поданной дуге. При анализе решений задач МПМ нередко возникает необходимость в вычислении оптимального значения функции потока, протекающего от источника к стоку, что, как правило, связано с однопродуктовым потоком, поскольку потоки в дугах сети соответствуют потокам некоторого однородного продукта. Ключевую роль в сетевом моделировании играет теорема о максимальном потоке, предложенная Фордом и Фалкерсоном: для любой сети с одним источником и одним стоком величина максимального потока от источника к стоку равна величине минимального разреза. Алгоритмы, которые находят максимальный поток, кроме того, позволяют определить минимальный разрез. Тем самым, во-первых, для задачи максимизации потока становятся наглядно видны «узкие места», и, во-вторых, появляется возможность решать некоторые задачи об оптимальных разбиениях (разрезаниях) сетей. Выяснилось, что алгоритмы и минимаксные теоремы для различных задач близки друг к другу и фактически являются конкретизациями алгоритма увеличивающих путей и теоремы о максимальном потоке и минимальном разрезе Форда и Фалкерсона. Благодаря этому стало возможным сконцентрировать усилия на построении эффективных потоковых алгоритмов. Некоторые комбинаторные задачи, возникшие как задачи на графах и матрицах, допускают потоковую интерпретацию и могут быть решены посредством одноили многократного нахождения максимального потока в сети. Потоковый подход к комбинаторным задачам был также развит Фордом и Фалкерсоном и применен к задачам балансировки нагрузки. Для многих задач было установлено важное единообразие как в доказательствах минимаксных теорем — аналогах теоремы о максимальном потоке и минимальном разрезе, так и в методах решения — аналогах метода увеличивающихся путей Форда и Фалкерсона. Тем самым создание новых алгоритмов нахождения максимального потока в сети фактически означает появление новых алгоритмов решения комбинаторных потоковых задач. В отличие от комбинаторных алгоритмов сетевые методы более адаптированы под решение многополюсных и (или) многопродуктовых задач, что связано с одновременным расчетом множества путей в сети. Правда основным средством решения многополюсных задач является редукция к задаче о максимальном потоке в сети с одним источником и одним стоком или к нескольким таким задачам. Потоковые многополюсные задачи (задача нахождения потока максимальной суммарной мощности, задача на допустимость, задача о нахождении допустимого потока максимальной мощности) могут быть непосредственно интерпретированы под задачи МПМ.

В сетях с неориентированными дугами поток по дуге может протекать в любом направлении. В случае, когда поток однопродуктовый, неориентированную дугу можно заменить двумя противоположно направленными дугами. Для переноса рассматриваемых результатов на неориентированный случай достаточно каждую ветвь заменить двумя дугами, инцидентными тем же вершинам, идущими во взаимно противоположных направлениях и имеющими одинаковые пропускные способности. Это можно сделать благодаря тому, что потоки, протекающие по противоположным направлениям, поглощают друг друга. Однако при моделировании многопродуктовых сетей возникают определенные сложности, так как для многопродуктового потока такую замену произвести нельзя ввиду того, что потоки различных продуктов, протекающие по противоположным направлениям, не поглощают друг друга, а суммируются, и суммарная величина потока не должна превосходить пропускную способность дуги. В рамках сетевых моделей задача о максимальном многопродуктовом потоке, так же как и задача о многопродуктовом потоке минимальной стоимости, является весьма сложной. Их решения обеспечены только для ряда специфических случаев. Например, в результате решения задачи (алгоритм Гомори-Ху) определяются максимальные потоки между всеми узлами сети (многополюсный максимальный поток), но без учета влияния друг на друга. Такая же ситуация и в задаче о многополюсной цепи с максимальной пропускной способностью. Разрешимые многопродуктовые задачи в ориентированных сетях сводятся к однопродуктовым многополюсным задачам []. Существует подход, при котором для решения многопродуктовой задачи достаточно решить модельную однопродуктовую задачу, а затем разделить построенный однопродуктовый поток на составляющие. Однако подобный подход в приложении к задачам МПМ не является адекватным. Это проявляется в том случае, когда один и тот же узел является источником и стоком потоков разных продуктов. Результативные решения удалось получить лишь для случая двухпродуктовой неориентированной задачи (задача Ху). Для задачи Ху существует и может быть эффективно построен поток, максимизирующий вместе с суммарной мощностью мощность потока любого продукта.

Подход к потоковому моделированию задач МПМ и балансировки нагрузки в виде решения задач динамического и линейного, в т. ч. целочисленного, программирования предложен в работах [14, 15]. Например, пусть граф G (M, E) представляет структуру ТКС, где M — множество узлов сети, а E — множество дуг (трактов передачи) ТКС. Для каждой дуги (i, j) E характерна пропускная способность. Пусть также K — множество обслуживаемых сетью трафиков. Тогда для k K необходимо указать, и — требуемую полосу пропускания, узел-источник и узел-получатель соответственно. Для каждой связи (i, j) E и передаваемого трафика k K величина характеризует долю требуемой полосы пропускания для этого трафика от пропускной способности тракта. Пусть также величина представляет собой максимальный порог использования трактов сети. Тогда задачу маршрутизации в сети MPLS с обеспечением требований QoS можно сформулировать следующим образом:

(2.12)

(2.13)

где — доляго трафика, протекающего вм канале;

— интенсивностьго трафика на входе сети;

— ПСго канала;

— максимальный порог использования канальных ресурсов КС.

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

Потоковые модели процессов балансировки сетевых ресурсов в IP-сетях определяются соответствующими используемыми протоколами маршрутизации. Например, модель однопутевой маршрутизации RIP, построенная по принципу нахождения кратчайшего пути по количеству переприемов, базируется на распространенном аппарате систем массового обслуживания. Более сложными и адекватными являются модели многопутевой маршрутизации с балансировкой нагрузки по путям равной и неравной стоимости, большинство которых основано на методах линейного программирования. Здесь, чаще всего, в качестве решаемой задачи выступает минимизация функционала следующего вида [17]:

(2.14)

где — вектор метрик каналов;

— вектор интенсивности трафика (1/c).

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

(2.15)

где — пропускная способность канала передачи (1/с).

Размерность и способ нахождения метрики канала определяется принципом моделируемого протокола маршрутизации с соответствующими ограничениями модели [15]: для случая балансировки нагрузки по путям равной стоимости метрика равна 1, для случая неравной стоимости — определяется для каждого протокола в отдельности.

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

Распространенной является потоковая модель (модель Галлагера), в рамках которой предполагается в качестве критерия качества решения задачи маршрутизации использовать следующее выражение:

. (2.16)

На координаты вектора накладывается система ограничений, которая моделирует условия сохранения потока в каждом из сетевых узлов и в ТКС в целом:

(2.17)

где — интенсивность трафика на входе в сеть.

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

1. Распределенная процедура расчета кратчайшего множества безпетельных путей (кратчайших мультипутей), основанная на комбинаторных методах многопутевой маршрутизации, например MPDA или MPATH.

2. Процедура расчета оптимальных потоков в рамках модели Галлагера, основанная на ранее рассчитанном множестве мультипутей.

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

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