Содержание к диссертации
Введение
Глава1. Технологии транспорта ІР-трафика 12
1.1 Введение. Общие положения 12
1.2 Варианты технологий транспорта IP-трафика 12
1.2.1 Общее описание 12
1.2.2 Таблица параметров сравнения технологий 13
1.2.2.1 Технология передачи пакетов IP через ATM (IP over ATM) 15
1.2.2.2 Технология передачи пакетов по каналам CLIH(POS) 21
1.2.2.3 Протокол MAPOS 23
1.2.2.4 Технология передачи кадров Ethernet по каналам СЦИ (Ethernet over SDH 24
1.3 Устойчивое пакетное кольцо (технология RPR) 25
1.3.1 Услуги, качество обслуживания и управление ресурсами в сетях RPR 26
1.3.1.1 Виды услуг 26
1.3.1.2 Управление потоком от источника (Steer) 27
1.3.1.3 Перенаправление трафика в другое кольцо (Wrap) 28
1.3.2 Классы качества обслуживания 29
1.3.3 Механизмы управления доступом к ресурсу 31
1.3.3.1 Механизм пространственного использования ресурсов 31
1.3.3.2 Алгоритм справедливого доступа 32
Выводы к главе 1 39
Глава 2. Аналитическая модель коммутатора RPR 40
2.1 Введение и постановка задачи 40
2.2 Приоритетная модель коммутатора RPR 41
2.2.1 Аналитическая модель коммутатора RPR 41
2.2.2 Входной поток и дисциплина осблуживания 47
2.2.3 Имитационная модель коммутатора RPR 48
2.2.4 Анализ результатов моделирования 49
2.3. Модель механизма управления входным накопителем коммутатора RPR 51
2.3.1 Общая характеристика механизмов управления буферами 51
2.3.2 Особенности взаимодействия сетей RPR 52
2.3.3 Механизм ограничения входного буфера коммутатора RPR 55
2.3.4 Определение параметра N управления буфером 60
Выводы к главе 2 62
Глава 3. Аналитическая модель сети RPR 63
3.1 Введение и постановка задачи 63
3.2 Применение основной теоремы для сетей массового обслуживания к анализу сетей
RPR 64
3.2.1 Теорема о мультипликативном виде выражения для вероятности стационарного состояния сети 64
3.2.2 Применение теоремы ВСМР для анализа сети RPR 67
3.3 Анализ влияния длины кадра на эффективную скорость передачи 72
Выводы к главе 3 77
Глава 4. Исследование алгоритмов назначения и распределения длин волн в сетях RPR со спектральным мультиплексированием 78
4.1 Введение и постановка задачи 78
4.2 Особенности сетей со спектральным мультиплексированием каналов 80
4.2.1 Общие сведения о сетях, использующих спектральное мультиплексирование 80
4.2.2 Иерархический подход к проектированию сетей со спектральным мультиплексированием 81
4.3 Задача формирования логической топологии в линейных сетях 82
4.3.1 Проектирование сетей, не использующих спектральное мультиплексирование (одна длина волны) 82
4.3.1.1 Базовый алгоритм проектирования логической топологии 83
4.3.1.2 Алгоритм проектирования логической топологии для различных размеров логических колец 87
4.3.2 Проектирование сетей на базе спектрального мультиплексирования 91
4.3.2.1 Проектирование сети RPR на базе двоичного алгоритма 91
4.3.2.2 Проектирование сети RPR на базе алгоритма частичного параметра 95
4.3.2.3 Уточненный алгоритм частичного параметра 98
4.4 Проектирование логической топологии в кольцевых сетях 103
4.4.1 Проектирование сетей, не использующих спектральное мультиплексирование (одна длина волны) 104
4.4.2 Проектирование сетей на базе спектрального мультиплексирования... 105
4.4.2.1 Базовый алгоритм проектирования логической топологии 106
4.4.2.2 Проектирование сети RPR на базе двоичного алгоритма 106
4.4.2.3 Проектирование сети RPR на базе алгоритма частичного параметра ... 109
4.4.2.4 Уточненный алгоритм частичного параметра 111
Выводы к главе 4 119
Заключение 120
Список литературы 121
Приложение 1.. Акты внедрения 125
- Технология передачи пакетов IP через ATM (IP over ATM)
- Теорема о мультипликативном виде выражения для вероятности стационарного состояния сети
- Алгоритм проектирования логической топологии для различных размеров логических колец
- Проектирование сети RPR на базе алгоритма частичного параметра
Введение к работе
Актуальность работы. Волоконно-оптические кольца уже давно являются обязательной частью структуры территориально распределенных сетей (WAN -Worldwide Area Network) и, особенно, больших городских сетей (сетей MAN — Metropolitan Area Networks, известных также как сети Metro). Эффективность кольцевых структур сегодня является общепризнанной, однако, основное применение колец в крупных городских сетях состоит в использовании колец для организации магистральных сегментов телефонных сетей общего пользования (ОП) — сетей, построенных на базе технологии коммутации каналов.
В основе разделения ресурсов на физическом уровне в современных кольцевых сетях лежит технология SDH - технология синхронного временного разделения каналов (TDM - Time Division Multiplexing), которая может быть эффективной только в условиях гладкого трафика и становится ограничивающим фактором при необходимости масштабирования как ресурсов, так и услуг.
В последние несколько лет в связи с конвергенцией телефонных сетей общего пользования и сетей Интернет возникла концепция построения сетей следующего поколения (сетей NGN), в которой предполагается применять на сетевом и транспортном уровне IP-ориентированные протоколы. Если эта идея будет реализована (а сегодня пока нет причин сомневаться в этом), это будет означать смену парадигмы -уход от сетей ОП на базе коммутации каналов к сетям ОП на базе коммутации пакетов. Однако при использовании популярных сегодня кольцевых топологий, протоколы которых выбирались с учетом специфики сетей с коммутацией каналов, могут возникнуть проблемы, связанные с трудностями оптимизации и масштабирования кольцевых структур для пакетных сетей NGN.
Построение сетей NGN является проблемой хотя и близкого, но будущего. Другая, более насущная проблема - как совместить две широко используемых технологии - SDH и Ethernet. Практически, за последние 20 лет технология Ethernet превратилась в стандарт de facto при передаче данных в локальных сетях, а с появлением технологий семейства Gigabit Ethernet - и в сетях класса Metro. Широкое применение сетей Ethernet в сетях LAN и MAN определяется, в первую очередь, их высокими экономическими показателями в пересчете на стоимость передачи одного мегабита. Трафик Ethernet переносится сегодня непосредственно через высоконадежную транспортную среду SDH, которая, как было отмечено выше, оптимизирована для транспортировки голосового трафика и не способна обеспечить эффективные решения для существенно пачечного трафика в силу своей статической природы и негибких принципов управления пропускной способностью.
С развитием сетей на базе IP требования к ресурсам, необходимым для доставки новых услуг, непрерывно растут. Продвижение на рынок услуг, жестко связанных с величиной необходимой полосы пропускания, заставляет сервис-провайдеров отказываться от классических моделей обслуживания, базировавшихся только на величине ресурса, и развивать модели, определяемые видом трафика (речь, данные, видео). Такой подход приводит к необходимости создания новых технологий доступа к разделяемой среде. Эти технологии должны учитывать особенности структуры трафика, обладать свойствами отказоустойчивости, обеспечивать возможность динамического управления транспортными ресурсами и быть экономически эффективными.
В конце 2000 г. в институте ШЕЕ была создана рабочая группа 802.17, которая начала разработку спецификации транспортной технологии для кольцевых структур в пакетных сетях. Эта технология получила название технологии устойчивых пакетных колец (Resilient Packet Ring, RPR). Основной целью разработки новой технологии было создание возможностей развертывания отказоустойчивых пакетно-ориентированных сетей класса Metro, которые могут обеспечить экономически эффективную транспортировку пачечного трафика, в первую очередь трафика Ethernet, через кольцевые топологии на базе SDH.
Следует отметить, что все научные исследования, выполненные специально созданным комитетом RPR (RPR Alliance), сводятся лишь к имитационному анализу на основе специализированных пакетов прикладных программ, таких как Opnet Modeler системного решения компании Cisco - технологии DPT, при полном отсутствии аналитических исследований технологии RPR. Среди работ в этом направлении отметим имитационные исследования сотрудников компании Cisco и членов рабочей группы по стандартизации технологии RPR: L. Byoung-Joon, G. Peng и J. Lemon. Однако все компании-производители, члены комитета RPR, признают, что эффективное построение сетей класса Metro возможно только при детальном исследовании технологии RPR, поэтому аналитические исследования в этом направлении являются актуальными. В числе авторов, получивших важные результаты в решении задач анализа вероятностно-временных характеристик (ВВХ) отметим отечественных и зарубежных исследователей Г.П. Захарова, В.М. Вишневского, Г.Г. Яновского, N. Uzun и др.
Цель и задачи исследования. Целью диссертационной работы является создание методов оценки характеристик региональных сетей RPR и их элементов и разработка к построению эффективных сетей RPR. Поставленная цель обусловила необходимость решения следующих основных задач: разработка аналитической модели коммутатора RPR; разработка аналитической модели сети RPR; разработка механизма ограничения входного буфера при взаимодействии нескольких сетей RPR; анализ методов управления канальными ресурсами в сетях RPR со спектральным
Технология передачи пакетов IP через ATM (IP over ATM)
Будем понимать под масштабируемым протоколом тот, который корректно функционирует в условиях роста сети и трафика в ней, т.е. когда число узлов, пользователей, потоков трафика возрастает.
CLIP (Classical IP Over ATM): Этот протокол был разработан инженерной группой IETF (Internet Engineering Task Force); он дает возможность маршрутизировать IP-пакеты через сеть ATM - либо магистральную, либо рабочей группы. Classical IP over ATM позволяет преобразовывать IP-адреса сетевого уровня в адреса ATM и передавать IP-пакеты по сети ATM.
Classical IP Over ATM имеет ряд недостатков. Поскольку серверу ATMARP (серверу разрешения адресов ATM - ATM Address Resolution Server) доступна только одна IP-подсеть, IP-хосты могут напрямую взаимодействовать только с 1Р-хостами, расположенными в той же подсети. Чтобы посылать пакеты IP-хосту, находящемуся в другой виртуальной подсети, передающий IP-хост должен направлять их через маршрутизатор. Передающий ІР-хост использует для соединения с маршрутизатором один виртуальный канал, а маршрутизатор применяет для соединения с 1Р-хостом, являющимся адресатом, другой виртуальный канал. В этой цепи маршрутизаторы создают "узкое место", поскольку, как правило, работают медленнее коммутаторов. Кроме того, Classical IP Over ATM может маршрутизировать только IP-пакеты; при необходимости маршрутизировать пакеты других протоколов, например IPX, этот стандарт использовать нельзя. Он не решает проблем задержек и перегрузки сети, поскольку не может использовать преимущества поддержки качества сервиса (QoS) сетей ATM. И кроме того, Classical IP Over ATM не поддерживает многоадресную рассылку (рассылку информации определенной группе хостов) и не масштабируем.
Тем не менее технология CLIP имеет и некоторые достоинства. Во-первых, она позволяет передавать IP-пакеты по сети ATM. Во-вторых, поскольку конечные станции являются частью одной виртуальной подсети, даже если находятся в физически независимых локальных сетях, Classical IP Over ATM обеспечивает большую свободу при конфигурировании сети. Сетевые администраторы могут предоставлять пользователям, находящимся на значительных расстояниях от сети, возможность обращаться к ее ресурсам через высокоскоростную магистраль ATM.
LANE (LAN Emulation): Разработанный ATM Forum стандарт LANE определяет способ соединения локальных сетей по высокоскоростной ATM-магистрали. LANE также дает возможность подключать непосредственно к сети ATM рабочие станции, использующие традиционные протоколы, для создания высокоскоростных сетей рабочих групп. С помощью LANE конечная станция из одной ЛВС может связываться через сеть ATM с конечной станцией из другой ЛВС или с конечной станцией, подключенной непосредственно к сети ATM. Таким образом, имеется возможность использования в одной и той же сети как подключенных, так и не подключенных к сети ATM устройств.
LANE эмулирует подуровень управления доступом к среде передачи (Media Access Control - MAC) модели OSI, давая возможность любому протоколу сетевого уровня, который работает с моделью OSI (в том числе IPX, IP, NetBIOS и DECnet), передавать пакеты по сети ATM без их модификации. Благодаря этому пользователи могут выполнять свои приложения в сети ATM точно так же, как они это делают в локальной сети Ethernet или Token Ring, т.е. сеть ATM "прозрачна" для пользователей локальной сети. LANE имеет ряд ограничений. Как и в случае с IP-хостами в подсетях, образованных с помощью Classical IP Over ATM, для взаимодействия двух конечных станций, находящихся в разных эмулированных ЛВС, требуется маршрутизатор. Передающая конечная станция должна установить виртуальный канал с маршрутизатором, который, в свою очередь, устанавливает виртуальный канал с конечной станцией адресата. И поскольку маршрутизаторы обычно медленнее коммутаторов, они могут создавать "узкие места" в сети.
LANE является технологией соединения мостового типа, что накладывает определенные ограничения на масштабируемость эмулированных ЛВС. LNNI (Интефейс сеть-сеть LANE - Networko-Network Interface) помогает решить эту проблему, позволяя реализовать в пределах одной сети несколько служб LANE, однако тоже не свободен от ограничений, которые не дают возможности иметь более 2 тыс. конечных станций в эмулированной ЛВС. Практически, чем больше конечных станций, тем хуже работает сеть. Большее количество конечных станций означает большее число широковещательных передач и виртуальных каналов, что может вызвать сложности, поскольку сеть ATM одновременно поддерживает ограниченное число таких каналов.
Кроме того, LANE - это технология канального уровня OSI, которая "прозрачна" для более высоких уровней модели OSI. Вследствие этого LANE не может использовать преимущества качества сервиса (QoS) сетей ATM. Стандарт LANE 1.0 поддерживает только неопределенную скорость передачи (UBR). LANE 2.0 дает возможность сетевому администратору задавать категории качества сервиса в соответствии с типом трафика, который будет передаваться по эмулированной ЛВС -CBR (постоянную скорость передачи), VBR (переменную скорость передачи), UBR или ABR (доступную скорость передачи). Однако стандарт LANE 2.0 требует, чтобы все виртуальные каналы в эмулированной ЛВС использовали заданный тип трафика.
LANE имеет несколько важных достоинств. Так, возможности маршрутизировать все протоколы сетевого уровня OSI и выполнять приложения ЛВС в магистральной сети ATM без их модификации делают LANE мощным, но в то же время простым способом интеграции высокоскоростной ATM-магистрали с ЛВС. Кроме того, позволяя конечным станциям передавать ячейки без установления виртуальных каналов, LANE лучше поддерживает трафик сети без установления соединения. LANE также поддерживает трафик широковещательных и многоадресных рассылок. И наконец, способность LANE группировать конечные станции эмулированной ЛВС на основе их МАС-адресов обеспечивает необходимую гибкость в конфигурировании сети.
Протокол LANE также немасштабируем. По причине того, что протокол разрешения адресов, используемый для преобразования IP-адресов в АТМ-адреса (ATMARP — ATM Address Resolution Protocol) ограничен одной подсетью. Текущие исследования сфокусированы на определении протоколов сервер-сервер для распределенных ATMARP механизмов.
МРОА (Multi Protocol Over ATM): Разработка стандарта МРОА велась ATM Forum. МРОА дает возможность маршрутизировать протоколы типа IP, IPX и NetBIOS из традиционных ЛВС по коммутируемой ATM-магистрали. Подобно Classical IP Over ATM и LANE, МРОА обеспечивает мостовое соединение канального уровня OSI по виртуальной подсети. Фактически, МРОА использует технологию LANE для обеспечения соединения мостового типа, однако (в отличие от Classical IP Over ATM и LANE) может осуществлять маршрутизацию между виртуальными подсетями без использования традиционных маршрутизаторов.
Теорема о мультипликативном виде выражения для вероятности стационарного состояния сети
На рис. 14 приводятся графики зависимости производительности 7/от нагрузки Я/. Обе эти величины нормированы относительно производительности канала {Л в кадрах за единицу времени. Максимальная емкость накопителя принимается равной N = 8 кадров. Средняя длина пути кадра выбрана равной п =2 участка при вероятности того, что в любом узле имеются транзитные кадры, равной Рт = У 0»5. Кривые показаны при значениях управляющего параметра N, изменяющегося в пределах от 1 до 6 входящих кадров. Отметим, что спад кривой производительности, ведущий к тупиковой ситуации, с уменьшением Nj уменьшается. И при N/=2 кривая спрямляется, спад производительности устраняется, и производительность достигает максимального значения около 33% теоретической пропускной спососбности канала. При еще более жестком управлении, допускающим в любой момент времени наличие Nj=l входящего кадра, перегрузка также устраняется, но производительность снижается. В [47] показано, что в подобной схеме перегрузки устраняются, если где п = \/рт - среднее число участков в маршруте. Это совпадает с результатом на рис. 13. При этом зависимость на рис. 14 позволяет выбирать параметр управления в зависимости от средней длины пути кадра в сети с целью недопущения возникновения тупиковой ситуации и максимизации производительности. Выводы 1. Разработана аналитическая модель коммутатора для сетей RPR, основанная на теории приоритетных СМО. Получены оценки среднего времени ожидания в коммутаторе RPR для транзитного трафика и трафика, генерируемого коммутатором. Проведено сравнение результатов аналитического и имитационного моделирования и показано, что представленная аналитическая модель позволяет получить достаточно точные данные, особенно при низких и средних нагрузках. При нагрузках р, близких к единице, различия результатов имитационной и аналитической моделей могут иметь порядок 20%. 2. Исследована модель взаимодействия сетей RPR. Показана необходимость введения в коммутатор механизма ограничения входного накопителя для борьбы с перегрузками. Предложен механизм управления входным буфером, основанный на выборе оптимального числа мест ожидания, совместно используемого транзитными и исходящими кадрами. 3. В предложенном механизме ограничения входного буфера установлено количество мест в буфере, при котором исключается явление перегрузки и производительность коммутатора достигает максимального значения. Глава 3. Аналитическая модель сети RPR 3.1 Введение и постановка задачи Предметом изучения сетей массового обслуживания являются методы количественного анализа очередей при взаимодействии множества центров обслуживания и потоков сообщений. Сеть массового обслуживания представляет собой совокупность конечного числа М центров обслуживания, в которой циркулируют сообщения, переходящие в соответствии с маршрутной матрицей из одного центра в другой. Под цетром обслуживания понимают систему массового обслуживания, состоящую из А одинаковых приборов (1 Л )и буфера объемом С (1 С ). Если в момент поступления сообщения все обслуживающие приборы центра заняты, то сообщение занимает очередь в буфере, где ожидает начала обслуживания. Очереди являются неизбежным следствием стохастического характера поступления и обслуживания сообщений в центре. Переход сообщения из одного центра после окончания обслуживания в нем в другой осуществляется в соответствии с заданным маршрутом, под которым понимается последовательность посещаемых сообщением центров сети. Маршрут сообщения по сети массового обслуживания задается матрицей маршрутов Р, вид которой зависит от того, является ли сеть массового обслуживания открытой или замкнутой. В открытую сеть МО сообщения поступают из внешнего источника и могут покидать сеть после завершения осблуживания. Если принять внешний источник за новый центр сети и обозначить индексом 0, то маршрут в открытой сети задается стохастической неразложимой матрицей Р = PJ , где PQ , И PJO " соответственно вероятность поступления в у -ый центр сообщения из источника и вероятность покидания сообщением сети после окончания обслуживания в /-ом центре (у = \,М). Очевидно, что выполняется равенство Х/=о У= 0" == 0»l» -»-W)» где PQQ=0 (предположение PQQ Ф 0 не представляет практического интереса). Входящий из источника в сеть поток сообщений определяется совместным распределением случайных величин д= д " д-1 гл-е я -моменты поступления сообщений (R \,t0= 0,0 tx t2 ...). Основные подходы к исследованию сетей массового обслуживания базируются либо на прямом методе отыскния выражений для вероятностей состояний сети с использованием техники составления уравнений локального баланса, как это изучено в [25] , либо на методе составления рекуррентных уравнений для средних значений [28, 59]. Перечисленные методы позволяют находить точное решение для мультипликативных или, как их часто называют, локально-сбалансированых сетей, где выражения для вероятностей состояний имеют мультипликативную форму. Уравнения глобального баланса для нахождения стационарного распределения Р{п) вероятностей состояния сети записываются в общем виде следующим образом: п для любого состояния п,п , где Я(п) - интенсивность ухода сети из состояния п; Я(п ,п) - интенсивность ухода сети из состояния п в состояние п. Получение стационарного распределения непосредственно из системы уравнений представляет сложную задачу, поэтому обычно используется подход, связанный с составлением уравнений локального баланса. Существо составления уравнений локального баланса состоит в приравнивании интенсивности входа сети в состояние, при котором сообщений начинает обслуживаться с определенного этапа, к интенсивности выхода сети из этого состояния, при котором сообщение заканчивает этот этап обслуживания. С каждым сообщением связывается этап обслуживания. При таком подходе каждое уравнение системы можно представить в виде уравнений локального баланса, выполнение которых является достаточным условием выполнения уравнений глобального баланса. Применение основной теоремы для сетей массового обслуживания к анализу сетей RPR 3.2.1 Теорема о мультипликативном виде выражения для стационарного состояния сети Рассмотрим сеть МО, включающую М центров с дисциплиной обслуживания в порядке поступления и Lоткрытыми подцепями. Обозначим через n[i?,r], n(u?r] ), пІЇ/?/-] ), п(ГЛгр.пШ r Y)j состояния сети такие, что переходы из состояния в состояние при поступлении или окончании обслуживания сообщения г-го класса в центре R осуществляются следующим образом:
Алгоритм проектирования логической топологии для различных размеров логических колец
Как было отмечено во введении, к недостаткам технологии RPR следует отнести возможность использования только одной физической топологии для построения сети — топологии кольца. Решить эту проблему можно путем применения спектрального разделения каналов (WDM - Wave Division Multiplexing) в сети RPR, так как WDM позволяет организовать любую логическую топологию на кольцевой физической топологии. Однако при переходе от однозначной физической топологии двунаправленного кольца к многообразным логическим топологиям, построенным на базе длин волн, может возрастать путь передачи протокольных блоков, измеряемый в количестве переприемных участков. Одним из параметров логической топологии, влияющим на межконцевую среднесетевую задержку, является расстояние между максимально удаленными узлами. В случае кольца это расстояние является диаметром. Поэтому минимизация среднесетевой задержки непосредственно связана с задачей минимизации диаметра логической топологии D
В качестве основной задачи поставим задачу минимизацию кадровой задержки. В [22] показано, что основной вклад в общую задержку на сетях, использующих WDM, вносит задержка на электронную обработку. Задержка электронной обработки является достаточно существенной на высоких скоростях передачи, и в этой главе мы предположим, что задержка электронной обработки является основным фактором, вносящим вклад в общую задержку.
Для однородного трафика между узлами ("allo-all" — передача трафика "каждый-с-каждым") это уменьшение задержки соответствует минимизации числа переприемов на самом коротком пути между двумя самыми отдаленными узлами в логической топологии (диаметр логической топологии). В данной главе получены также нижние границы для диаметра логической топологии и предложим практические алгоритмы проектирования логической топологии.
Физическую топологию сети определим направленным графом G = (К, Е), где набор вершин V = {l,2,..., Nj соответствует оптическим маршрутизаторам длин волн, и набор ребер Е соответствует одиночным волоконно-оптическим соединениям точка точка в сети. Физическое расстояние (число переприемов в физической топологии) между вершинами і и у, обозначенное как P(i,j) является количеством ребер по наиболее короткому пути от / к j в G. Каждый маршрутизатор длин волн соединен с пакетным маршрутизатором, который обрабатывает пакеты в электрическом виде по прибытию на узел. Предположим, что каждое волокно может нести F длин волн, Лі,Л2,-..,Лр, и, следовательно, косвенно ограничим количество терминирующего оптического оборудования. Преобразование длин волн (т.е. возможность конверсии длины волны в световом пути на промежуточных узлах) предполагается не возможным. Логическая топология G = {у, Е ) является направленным графом содержащим набор вершин соответствующих пакетным маршрутизаторам. Направленное ребро (дуга) (w,v) принадлежит Е если установлен световой путь из и к v. Логическое расстояние между двумя вершинами и и v, обозначенное как f/(w,v), определено как число ребер в Е на самом коротком пути от и к v в G . R\u,v\ описывает наиболее короткий логический путь от и к v, который выбран для маршрутизации пакетов от и к v при этом диаметр логической топологии D = maxMV d{u,v) является расстоянием (числом переприемов) между наиболее удаленными узлами в G .
Мы предполагаем, что трафик существует между всеми парами пакетных маршрутизаторов и что задержка, вызванная обработкой пакетов одинакова на всех маршрутизаторах. Как уже было сказано выше, нашей задачей является минимизация задержки. Так как трафик существует между каждой парой узлов, по нашим допущениям, пакетная задержка будет минимальна при минимальном же логическом расстоянии между конечными узлами. Таким образом, дан направленный граф G, соответствующий двунаправленному кольцу или линии с F длинами волн на соединение, наша задача формулируется следующим образом - необходимо спроектировать логическую топологию так, чтобы ее диаметр ( ) был минимален. Минимизация диаметра соответствует минимизации пакетной задержки. 4.2 Особенности сетей со спектральным мультиплексированием
В результате современного прогресса в сфере производства оптических волокон и систем спектрального уплотнения для использования в магистральных и городских линиях и сетях связи стала доступной значительная полоса пропускания.
Маршрутизация по длинам волн, реализуемая узлами, используется для маршрутизации световых сигналов в соответствии с длинами волн несущих и источниками.
Сети с WDM маршрутизацией длин волн состоят из световых путей, которые могут быть представлены как транспортные соединения. Световые пути - это полностью оптические коммутируемые соединения, которые сформированы выбором одной длины волны на каждом соединении от источника до приемника. Если маршрутизирующие узлы не имеют возможности изменения длины волны, то длины волн на каждом маршруте светового пути должны быть одни и те же.
Если же необходимые технические ресурсы способны организовать столько световых путей, сколько необходимо, то весь трафик может быть перенесен через световые пути от источника до приемника с оптоэлектронным преобразованием, возложенным на периферию оптического ядра. Обычно, однако, трафик, который передается в городских и магистральных сетях является "многопереходовым", т.е. трафик между двумя конечными узлами переносится через множество световых путей и электронно обрабатывается (маршрутизируется или коммутируется) на промежуточных узлах. Инфраструктура оптической сети, а именно маршрутизаторы длин волн и волокна, объединяющие их, представляют собой физическую топологию сети. Логическая же топология (ЛТ) является набором световых путей, которые устанавливаются поверх физической топологии между маршрутизаторами/коммутаторами, обрабатывающими трафик в электрической форме. Следовательно, каждый световой путь является логическим соединением. В этом контексте мы можем сказать, что пользовательский трафик передается от источника к пункту назначения через логическую топологию. Взаимосвязь двух топологий проиллюстрирована рис. 20.
Проектирование сети RPR на базе алгоритма частичного параметра
Доказательство: рассмотрим произвольную пару узлов и,v. Как и ранее, определим уровень узла и как самый высокий индекс длины волны, терминируемой на и. Предположим, что уровень узла и, т.е. д(и)=і, и д{у) = j. Определим частичный параметр k, k=\N . Отметим, что начиная от и мы можем достичь узла на уровне / + 1 используя последовательность максимум из — 1 переходов на световых путях в У} и как максимум к-\ переходов на световых путях в Xt. Следовательно, используя как максимум (2k-2)(F-i) переходов мы можем достичь любого узла на уровне F, стартуя от узла и. Подобным образом, используя тот факт, что от любого узла на уровне F, мы можем достичь любой другой узел уровня F используя последовательность как максимум 2к—Ъ световых путей (как максимум к — 1 световых путей в Yp чтобы достичь узел из которого начинается световой путь вХр, как максимум к — 1 световых путей в Yp к узлу назначения). Следовательно, мы имеем d(i,j) (2k-2X2F-/-j)+(3k-3). В наихудшем случае, / = J = 1, мы имеем D (4F - \)\N 2F \- 1J. Из теоремы 8,11 и 7 мы имеем следующее. Теорема 12. Для двунаправленной кольцевой топологии, оптимальный диаметр асимптотически того же порядка как N \ т.е. D = Q\N 2F J для любого произвольного F 1. Доказательство данной теоремы дано в [22]. На рис. 44, 45 приведены зависимости диаметра логической топологии как функции количества узлов при фиксированном числе используемых длин волн (F=2, F=4, F=6, F=8). Для облегчения интерпретации, отдельно простроены зависимости для числа узлов от 0 до 16 и от 0 до 256. Далее рассмотрим использование трех основных методов распределения длин волн и покажем границы их применимости. В данной главе мы рассмотрели проблему проектирования логических топологий в двунаправленных кольцевых и линейных топологиях. Поставленная задача формулировалась как минимизация средней задержки, вызванную электронной обработкой для наихудшего случая течения трафика. Для однородного трафика, это эквивалент минимизации диаметра логической топологии. Был представлен анализ нижних границ для различных значений числа длин волн на соединениях F. Теперь рассмотрим вопрос применимости полученных результатов. Из графических зависимостей (рис. 46-49) можно сделать вывод о применимости различных подходов к назначению длин волн на сетях RPR, использующих спектральное уплотнение каналов. Отдельно были рассмотрены физические топологии двунаправленной линии и двунаправленного кольца, кроме того для облегчения интерпретации результатов раздельно также рассмотрены сети для двух видов топологий с числом узлов от 0 до 16 и от 0 до 256. Далее выполним сравнение представленных в данной главе алгоритмов назначения и распределения длин волн и попытаемся определить границы приминимости алгоритмов, дающие минимизацию диаметра логической топологии. На рис. 46-49 приняты следующие обозначения: С помощью программы 3D Grapher возможно точное нахождение точек (количество узлов; количество длин волн) при которых необходимо выполнить переход от одного алгоритма проектирования ЛТ к другому для того, чтобы при каждом конкретном наборе (количество узлов; количество длин волн) используемый алгоритм назначения и распределения длин волн давал минимальный диаметр. 1. Предложен подход к проектированию колец сетей RPR, имеющих различные логические топологии, образованные путем применения спектрального мультиплексирования (технология DWDM). Задача минимизации среднесетевой задержки решена путем выбора соответствующего диаметра логической топологии RPR, получаемого при применении двоичного алгоритма, алгоритма частичного параметра или уточненного алгоритма частичного параметра. Аналогичная задача решена для физической топологии шины, образуемой в сети RPR в результате срабатывания механизма защиты. 2. Полученные оценки сверху диаметров логических топологий при применении различных алгоритмов распределения и назначения длин волн позволяют определить границы применимости каждого алгоритма в рамках которых применение алгоритма гарантирует минимизацию диаметра логической топологии и следовательно минимизацию среднесетевой задержки. Это позволяет выбрать соответствующий алгоритм распределения и назначения длин волн. В процессе проведенных в диссертационной работе исследований получены следующие основные результаты: 1. Разработана аналитическая модель коммутатора для сетей RPR, основанная на теории приоритетных СМО. Получены оценки среднего времени ожидания в коммутаторе RPR для транзитного трафика и трафика, генерируемого коммутатором. Проведено сравнение результатов аналитического и имитационного моделирования и показано, что представленная аналитическая модель позволяет получить достаточно точные данные, особенно при низких и средних нагрузках. При нагрузках р, близких к единице, различия результатов имитационной и аналитической моделей могут иметь порядок 20%. 2. Исследована модель взаимодействия сетей RPR. Показана необходимость введения в коммутатор механизма ограничения входного накопителя для борьбы с перегрузками. Предложен механизм управления входным буфером, основанный на выборе оптимального числа мест ожидания, и установлено количество мест в буфере, при котором производительность узла достигает максимального значения. 3. На основе теории открытых сетей массового обслуживания разработана аналитическая модель сети RPR. Получена оценка межконцевой среднесетевой задержки в сети RPR. Эта оценка базируется на теореме о мультипликативной форме выражения для вероятности стационарного состояния сети (Теорема ВСМР). 4. На основе разработанной модели сети массового обслуживания решена задача определения оптимальной длины кадра по критерию максимизации эффективной скорости передачи для случаев наличия и отсутствия ошибок в тракте передачи. 5. Предложен подход к проектированию колец сетей RPR, имеющих различные логические топологии, образованные путем спектрального разделения каналов (технология DWDM). Решена задача минимизации среднесетевой задержки путем выбора соответствующего диаметра логического кольца RPR. Аналогичная задача решена для физической топологии шины RPR. 6. Полученные результаты диаметров логических топологий при применении различных алгоритмов позволяют определить границы применимости каждого алгоритма и выбрать соответствующий алгоритм распределения и назначения длин волн.
