close

Вход

Забыли?

вход по аккаунту

?

Krylov

код для вставкиСкачать
Министерство образования и науки российской федерации
Федеральное государственное автономное
образовательное учреждение высшего образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
Ю. Д. Крылов
МЕТОДЫ МАРШРУТИЗАЦИИ И КОММУТАЦИИ
В ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ
Учебное пособие
Санкт-Петербург
2015
УДК 004.7(075.8)
ББК 32.973.202я73
К85
Рецензенты:
доктор технических наук, профессор В. В. Михайлов;
кандидат технических наук, доцент А. А. Ключарев
Утверждено
редакционно-издательским советом университета
в качестве учебного пособия
Крылов, Ю. Д.
К85 Методы маршрутизации и коммутации в вычислительных
сетях: учеб. пособие / Ю. Д. Крылов. – СПб.: ГУАП, 2015. – 55 с.
ISBN 978-5-8088-1026-6
В учебном пособии рассмотрены современные методы маршрутизации
и коммутации в глобальных и интегрированных вычислительных сетях, способные передавать высокоскоростной трафик для различных типов сервиса.
Предназначено для студентов, обучающихся по специальности «Вычислительные машины, комплексы, системы и сети» и по другим родственным специальностям.
УДК 004.7(075.8)
ББК 32.973.202я73
ISBN 978-5-8088-1026-6
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения (ГУАП), 2015
© Ю. Д. Крылов, 2015
ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ И СОКРАЩЕНИЙ
АТМ – асинхронный режим передачи
ЛВС – локальная вычислительная сеть
ГВС – глобальная вычислительная сеть
МОС – Международная организация по стандартизации
УДС – управление доступом к среде
ЦСИС – цифровая сеть интегрированного сервиса
У-ЦСИС – узкополосная цифровая сеть интегрированного сервиса
Ш-ЦСИС – широкополосная цифровая сеть интегрированного
сервиса
ТВ – телевидение
ТВВЧ – телевидение высокой четкости
МВВ – мультиплексор ввода/вывода
МСЭ – Международный союз электросвязи
УК – узел коммутации;
УУ – устройство управления
ЗУ – запоминающее устройство
3
Предисловие
В настоящее время большое значение имеют высокоскоростные
глобальные и интегрированные вычислительные сети. Появились
новые информационные технологии, позволяющие передавать разнородный трафик на высоких скоростях в реальном масштабе времени и с высоким качеством. При этом большое значение имеют
устройства маршрутизации и коммутации.
Учебное пособие состоит из четырех разделов. В разделе 1 описываются основные протоколы маршрутизации для IP-сетей. В разделе 2 приводятся принципы маршрутизации, основанные на выборе кратчайших путей по линейному расстоянию (матричный метод
и метод Флойда) и по числу транзитных участков (метод рельефов),
а также методы маршрутизации, принятые в АТМ-сетях. В разделе
3 рассматриваются методы повышения производительности вычислительных сетей за счет передачи информации по множеству маршрутов, в разделе 4 – требования к системам коммутации для передачи видеопотоков и способы построения коммутаторов.
4
1. ОСНОВНЫЕ МЕТОДЫ МАРШРУТИЗАЦИИ
1.1. Основные методы маршрутизации
в стеке протоколов TCP/IP
Под маршрутизацией понимается решение задачи поиска оптимального пути от отправителя информации к ее получателю. Устройство, которое решает эту задачу, называется маршрутизатором. В IPсетях главным параметром маршрутизации является адрес в IPпротоколе. Сеть Интернет организована как совокупность взаимосвязанных между собой автономных систем или доменов. Автономная
система включает в себя IP-сети, которые имеют единое административное управление и общую политику (стратегию) маршрутизации.
В пределах домена используются протоколы внутренней маршрутизации (Interior Gateway Protocol – IGP), а между доменами – протоколы внешней маршрутизации(Exterior Gateway Protocol – EGP).
При маршрутизации необходимо рассмотреть две проблемы:
– определение и распространение сведений о маршрутах в сети
(домене), которые связаны с реализацией политики маршрутизации и регламентируются алгоритмами «вектор-расстояние» и «состояние каналов»;
– продвижение по установленным маршрутам пакетов от отправителя к получателю, которое определяется алгоритмами поэтапной маршрутизации и маршрутизации от источника.
Алгоритм «вектор-расстояние» основан на том, что каждый объект (маршрутизатор), который принимает участие в маршрутизации, сохраняет в своей базе информацию обо всех адресах сети и
метрику – расстояние до получателя информации. Маршрутизаторы обмениваются между собой маршрутными базами. При принятии решения о маршруте передачи пакета оценивается каждый
путь к объекту и выбирается наилучший. Этот протокол реализован в протоколах маршрутизации RIP (Routing Information Protocol) и IGRP (Internet Gateway Routing Protocol).
Алгоритм состояния каналов заключается в следующем. Здесь
на первом этапе каждый объект формирует топологическую базу
и строит граф связей сети, который описывает ее топологию с учетом того, что каждая связь характеризуется своей метрикой. Объекты обмениваются базами и обновляют сведения о сетях. На втором этапе объект решает проблему определения оптимального пути
к каждой известной ему сети. Этот алгоритм реализован в протоколах OSPF (Open Shortest Path First) и EIGRP.
5
Поэтапная маршрутизация. Здесь каждый маршрутизатор
принимает независимое решение о продвижении пакета на основании адреса получателя и информации, которая находится в маршрутной базе.
Маршрутизация от источника. Маршрут формируется отправителем пакета и записывается в каждый пакет, который отправляется в сеть.
Протокол RIP
Это – протокол внутренней маршрутизации, предназначенный
для небольших доменов [1]. Данный протокол для передачи сообщений использует протокол UDP (User Datagram Protoсol). Сообщения
RIP состоят из IP-адреса сети и числа шагов (маршрутизаторов).
Максимальное число шагов – 15. В одном сообщении может быть
информация о 25 сетях. Маршрутизатор, на котором работает RIP,
получает сообщения RIP от других маршрутизаторов и строит таблицу маршрутизации, в которой прописаны пути к другим сетям.
Обмениваясь сообщениями, маршрутизаторы каждые 30 с обновляют свои таблицы маршрутизации.
Недостатки данного протокола:
– не всегда выбирается самый эффективный маршрут;
– из-за медленной сходимости могут образовываться логические
петли;
– медленно возобновляются таблицы маршрутизации после сбоя
в работе маршрутизатора;
– используются широковещательные рассылки большого количества служебной информации (таблицы маршрутизации);
– ограничен размер домена маршрутизации (15 переходов);
– не работает с адресами подсетей и не различает автономных
систем.
Протокол OSPF
Он применяется для внутренней и внешней маршрутизации [1] и
использует алгоритм состояния каналов. При этом он может обслуживать автономную систему, которая состоит из нескольких зон.
Протокол OSPF значительно эффективнее протокола RIP. Маршрутизатор с протоколом OSPF решает проблему оптимизации маршрутов, анализируя граф сети с метрикой, характеризующей качество обслуживания.
6
Основные параметры метрики – пропускная способность, задержка и надежность. Дополнительными параметрами будут загрузка канала и безопасность. Маршрутизаторы обмениваются сообщениями
только при изменении топологии сети. Протокол OSPF быстрее, чем
протокол RIP, перестраивает маршрутные таблицы.
Основные преимущества протокола OSPF:
– применение групповой передачи коротких сообщений при изменении топологии сети, что снижает загрузку сети;
– поддержка распределения информации по параллельным каналам в зависимости от их пропускной способности.
Протоколы IGRP и EIGRP
IGRP – Internet Gateway Routing Protocol– фирменный протокол, принадлежащий к классу IRG. Данный протокол чаще всего
используется маршрутизаторами фирмы Cisco System. В его основу
заложен алгоритм длины вектора. Современная реализация протокола предназначена для сетей TCP/IP. Протокол имеет значительно
лучшие характеристики по сравнению с протоколом RIP, так как он:
– надежно работает в сетях сложной топологии;
– обладает лучшей сходимостью по сравнению с RIP;
– значительно снижает объем служебной информации;
– распределяет информацию между каналами с одинаковыми
метриками.
Метрика протокола содержит следующие параметры канала:
– пропускная способность;
– задержка;
– нагрузка;
– надежность.
При этом параметры канала могут меняться в широких пределах.
Протокол EIGRP объединяет все преимущества алгоритмов «вектор-расстояние» и «состояние каналов». Протокол использует алгоритм распределенного обновления (Distributed Update Algorithm –
DUAL), который позволяет быстро возобновить работу после изменения сетевой топологии. Протокол характеризуется следующими
особенностями:
– возможностью быстро находить соседний маршрутизатор;
– использовать алгоритм DUAL;
– наличием усовершенствованного механизма инкапсюляции
сообщений в IP-пакет.
7
В первую очередь маршрутизатор определяет достижимость «соседнего» маршрутизатора, который может напрямую взаимодействовать с ним. Для этого он периодически посылает пакет Hello.
Затем алгоритм DUAL по полученной от «соседей» информации
о маршрутах определяет оптимальный маршрут передачи, который
не является частью петли маршрутизации.
Протоколы EGP и BGP
Эти протоколы являются протоколами внешней маршрутизации сети Интернет. С помощью EGP взаимодействуют выделенные
маршрутизаторы разных автономных систем, которые собирают
информацию о системе с помощью внутренних протоколов маршрутизации.
Недостатки протокола:
– не используется метрика, т. е. маршрутизация не интеллектуальна;
– возможно появление петель на маршруте;
– служебные сообщения имеют большой размер.
Протокол BGP (Border Gateway Protocol) используется для организации связи между корневыми маршрутизаторами сети Интернет. Он использует протокол TCP, что повышает надежность при
взаимодействии между автономными системами. Протокол BGP
ликвидирует недостатки протокола EGP. В качестве метрики используются скорость передачи в канале, его надежность и др.
1.2. Протокол OSPF
Протокол маршрутизации OSPF (Open Shortest Path First) представляет собой открытый протокол состояния связей. При этом он
использует алгоритм SPF поиска кратчайшего пути на графе. Данный протокол применяется для внутренней маршрутизации.
Рассмотрим алгоритм и построение маршрутов на примере
системы, представленной на рис. 1.1. Будем рассматривать OSPFсистему, состоящую только из маршрутизаторов, которые соединены линиями связи типа «точка – точка».
Состояния связей для рассматриваемого примера приведены
в табл. 1.1.
На рис. 1.1 маршрутизаторы обозначены цифрами 1, 2, 3, 4, 5.
Линии связи обозначены буквами A, B, C, D, E, K. Цифры на линиях связи обозначают метрику между маршрутизаторами. Метрика – это оценка качества связи на данном физическом канале.
8
Таблица 1.1
1
2
2
A
E
K
5
2
B
1
1
4
1
C
3
3
D
Рис. 1.1. Пример OSPF-системы
От до
Сеть
Метрика
1 2
A
2
1 3
C
3
1 4
B
1
1 5
E
2
2 1
A
2
3 1
C
3
4 1
B
1
5 1
E
2
3 4
D
1
2 5
K
1
4 3
D
1
5 2
K
2
Чем меньше метрика, тем выше качество соединения. Метрика маршрута равна сумме метрик всех связей (сетей), входящих
в маршрут. Если метрика каждой сети равна единице, метрика
маршрута является его длиной, определяемой количеством шагов
от отправителя до получателя, т.е. количеством маршрутизаторов,
через которые будут проходить пакеты. Значения метрик могут
варьироваться в широком диапазоне. Протокол позволяет назначать
для любой сети различные значения метрик в зависимости от типа
сервиса. Тип сервиса запрашивается дейтограммой в соответствии
со значением поля ToS (Typeof Service) ее заголовка. Для каждого
типа сервиса вычисляется свой маршрут. Метрика сети, оценивающая пропускную способность, определяется временем, требуемым
для передачи 100 Мбит через физическую среду данной сети. Метрика сети со скоростью передачи данных 100 Мбит/c и выше равна единице. Порядок расчета метрик, оценивающих надежность,
задержку и стоимость, не определен. Для поддержания маршрутизации по этим типам сервиса необходимо назначать метрики самостоятельно. Если не требуется маршрутизация с учетом типа сервиса или если маршрутизатор ее не поддерживает, то используется
метрика, равная метрике по пропускной способности. Маршрутизация по типам сервиса используется редко и исключена из последних версий данного стандарта.
9
Для работы алгоритма SPF на каждом маршрутизаторе необходимо создать базу данных состояния связей, представляющую собой полное описание графа OSPF-системы. Вершинами графа являются маршрутизаторы, а ребрами – соединяющие их линии связи.
При этом базы данных на всех маршрутизаторах одинаковы. База данных состояния связей представляет собой таблицу, где для
каждой пары смежных вершин (маршрутизаторов) указано ребро
(связь), их соединяющее, и метрика этого ребра. База данных для
рассматриваемого примера приведена в табл. 1.1.
Алгоритм SPF в соответствии с базой данных вычисляет кратчайшие пути между маршрутизаторами. Результатом работы алгоритма – будет таблица, где для каждой вершины графа указан список ребер, соединяющих маршрутизаторы между собой по кратчайшему пути.
10
2. МЕТОДЫ МАРШРУТИЗАЦИИ В ВЫСОКОСКОРОСТНЫХ
И ИНТЕГРИРОВАННЫХ ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ
2.1. Определение кратчайших путей
по матричному методу и методу Флойда
Распределение каналов и потоков информации на линии связи
производится с учетом длины пути. Для оценки длины пути используются различные критерии: число транзитных участков между взаимодействующими узлами коммутации (УК); протяженность
пути; качество тракта передачи; надежность передачи и т. д.
Кратчайшим путем передачи информации называется путь, для
которого критерий длины пути имеет наименьшее значение по сравнению с его значением для других возможных путей [2].
В теории потоков все методы выбора кратчайших путей основаны на утверждении о том, что если кратчайший путь mij от произвольного УКi к УКj проходит через промежуточные УК1, …,
УКk (рис. 2.1), то кратчайшие пути μ1j, …, μkj от УК1, …, УКk
к УКj соответственно являются частями кратчайшего пути μij
от УКi к УКj.
Если длина пути μ1j равна l1j, то lij = li1 + l1j. Так как μij – кратчайший путь,=
то lij min (liv + lvj ) , где N – число узлов сети. Для наv =1,N
хождения кратчайшего пути от узла i к узлу j необходимо просмотреть все возможные пути и выбрать тот, у которого наименьшая
длина .
Для этого имеется ряд методов, которые можно разделить на две
группы: методы нумерации узлов и матричные методы.
Матричный метод определения кратчайших путей позволяет
найти длину кратчайших путей между всеми узлами сети одновременно и основывается на применении операций над матрицами расстояний.
УК i
УК1
УК k
l 1j
УК j
l kj
l ij
Рис. 2.1. Понятие кратчайшего пути
11
Структуру сети связи с указанием длины ветвей можно описать в виде матрицы расстояний (длин) непосредственных связей
L1 = ||l1ij||, где элемент lij1 определяет длину дуги bij.
П р и м е р. Пусть коммуникационная сеть, имеющая в своем составе сеть связи и соединяющая узлы, имеет вид, представленный
на рис. 2.2.
Цифры на дугах соответствуют длинам дуг. При этом под длиной
дуги понимается линейное расстояние между узлами коммутации.
Это линейное расстояние является метрикой. Тогда матрица расстояний будет иметь вид
A B C D E F
A 0 30 ∞ 20 ∞ ∞
B ∞ 0 15 15 ∞ ∞
1
L = C ∞ 15 0 20 25 ∞ .
D 20 15 20 0 ∞ 25
E ∞ ∞ 25 10 0 40
F 15 ∞ ∞ 25 40 0
Элементы главной диагонали равны нулю, так как принимается,
что расстояние внутри узла отсутствует. Если между парой узлов
отсутствует дуга, то соответствующий элемент матрицы равен бесконечности (она обозначена в матрице знаком ∞). Если между узлами i и j имеется дуга bij, то элемент lji также принимается равным
бесконечности, например, l1AF = ∞, тогда же l1FA = 15.
При анализе сетей передачи данных длину ветви удобно трактовать как задержку, которую вносит ветвь при передаче информации.Матрица расстояний непосредственных связей неориентированной сети всегда симметрична относительно своей главной
B
30
диагонали. Для ориентирован15
A
ной сети (как в примере) она мо15
C
20
жет быть несимметричной.
20
Возведем матрицу L1 в квадD
15
рат L2 = L1 · L1. Тогда
25
F
25
10
40
E
li2,j =
N
∑li1,k lk1,j =
k =1
1
1
li1,N ⋅ l1N,j .
Рис. 2.2. Коммуникационная сеть = li,1 ⋅ l1,j +…+
12
(2.1)
Можно интерпретировать умножение как последовательное соединение дуг, а сложение как параллельное соединение дуг. Произведение l1ik · l1kj соответствует двутранзитному пути, т. е. пути,
проходящему через две дуги сети от узла i к узлу j через узел k
(рис. 2.3, а), а сумма, например, трех произведений l1ii · l1ij +
+ l1ij · l1jj + l1ik · l1kj – трем двутранзитным путям (рис. 2.3, б). Произведения l1ii · l1ij и l1ij · l1jj фактически соответствуют однотранзитным путям,
так как длина пути (задержка) внутри УК, т. е. l1ii и l1jj, не принимается во внимание.
Для подсчета длины каждого из таких N-транзитных путей необходимо операцию умножения заменить операцией сложения, т. е.
вместо l1ik · l1kj будем иметь l1ik + l1kj.
При наличии нескольких параллельных одно- и двутранзитных
путей (см. рис. 2.3, б) для определения длины кратчайшего пути
между узлами следует операцию сложения заменить операцией выбора из всех длин минимальной длины одно- и двутранзитного пути,
1
1
т. е. вместо выражения (2.1) будем иметь
=
lij2 min (lik
+ lkj
).
k =1,N
Таким образом элемент l2ij матрицы L2 равен длине кратчайшего
пути от УКi к УКj среди всех одно- и двутранзитных путей. При возведении матрицы L1 в r-ю степень при использовании этих операций
r −1
1
получим матрицу Lr = Lr–1 · L1, элемент которой
=
lijr min (lik
+ lkj
)
k =1,N
будет равен длине кратчайшего пути от УКi к УКj среди всех возможных одно-, двух- и т. д. до r-транзитных путей.
При наличии на сети N узлов коммутации число транзитных дуг
в пути без петель не может быть больше N – 1. Следовательно, может потребоваться вычисление матрицы Lr, у которой r ≤ N – 1. Для
конкретной сети может оказаться, что
Lr = Lr–1
(2.2)
при r < N – 1. Так как при равенстве (2.2) всегда выполняется равенство Lr+1 = Lr, вычисление матрицы более высокой степени прекращается, если в процессе вычисления матриц встретится равенство (2.2).
а)
б)
i
j
l 1ik
k
l 1kj
l 1jj
l 1ii
l 1ij
i
l 1ik
k
j
l 1kj
Рис. 2.3. Двутранзитные пути
13
Матрица Lr–1 при выполнении условия (2.2) называется дистанционной матрицей и обозначается D = Lr–1 = Lr = ||dij||. Таким образом,
элементы дистанционной матрицы равны длинам кратчайших путей между соответствующими узлами сети связи. Матрица часто
называется матрицей расстояний (длин, задержек).
Для рассматриваемого примера вычислим l2AC:
l2AС = min|(l1AA + l1AС); (l1AB + l1BС); (l1AC + l1CС);
(l1AD + l1DС); (l1AE + l1EB); (l1AF + l1FB)| = min |(0 + ∞ );
(30 + 15); (∞ + 0); (20 + 20); (∞ + ∞);(∞ + ∞)| = min (∞; 45; ∞; 40;∞;∞) = 40.
Аналогично вычислим остальные элементы матрицы L2, получим
A
B
L2 = C
D
E
F
A
0
35
40
20
30
15
B
30
0
15
15
25
40
C
40
15
0
20
25
45
D
20
15
20
0
10
25
E
∞
40
25
45
0
40
F
45
40
45 ,
25
35
0
A
B
L3 = C
D
E
F
A
0
35
40
20
30
15
B
30
0
15
15
25
40
C
40
15
0
20
25
45
D
20
15
20
0
10
25
E
65
40
25
45
0
40
F
45
40
45 .
25
35
0
A
B
L4 = C
D
E
F
A
0
35
40
20
30
15
B
30
0
15
15
25
40
C
40
15
0
20
25
45
D
20
15
20
0
10
25
E
65
40
25
45
0
40
F
45
40
45 .
25
35
0
далее
А затем
14
Здесь L4 = L3, следовательно, D = L3.
Рассмотренные методы позволяют определить длину кратчайшего пути, но не указывают те дуги, которые входят в этот путь.
Определение кратчайшего пути связано с некоторой дополнительной процедурой.
Если для определения длины кратчайшего пути применяется
способ нумерации узлов, то при выполнении дополнительной процедуры учитывается свойство веса УКk. Это свойство заключается
в том, что на пути от УКi к УКj существует УКk, для которого вы=
полняется равенство W
k lk,j + Wj .
Отсюда следует, что
W i − Wj =
li,j .
(2.3)
Поэтому, если выполняется условие (2.3), то кратчайший путь от
УКi проходит по дуге bij. Переходя к ÓÊj , находим следующую дугу, для которой выполняется условие (2.3) и которая также входит
в этот кратчайший путь. Так, шаг за шагом можно определить все
дуги, образующие кратчайший путь.
Исключив затем кратчайший путь из рассмотрения, подобным
образом определяются и другие пути от исходящего УКi к входящему УКj. Данный метод выбора кратчайших путей от одного узла до
всех остальных узлов называется методом Флойда.
При матричном методе определения кратчайшего пути дополнительно к дистанционной матрице на основе матрицы длин непосредственных связей составляется так называемая матрица длин
непосредственных связей Г, элементы главной диагонали которой
в отличие от элементов lij, равных нулю, имеют значения lij = ∞, где
значком ∞ обозначена бесконечность. Таким образом, матрица Г
легко может быть получена по матрице L1. В нашем случае матрица Г будет
A B C D E F
A ∞ 30 ∞ 20 ∞ ∞
B
∞ ∞ 15 15 ∞ ∞
г= C
∞ 15 ∞ 20 25 ∞
D 20 15 20 ∞ ∞ 40
∞ ∞ 25 15 ∞ 40
E
F 15 ∞ ∞ 25 40 ∞
П р и м е р. Замена элемента l1ii = 0 на l1ii = ∞ в матрице Г означает,
что длина дуги (задержка) в УКi принимается бесконечно большой.
15
Это дает возможность не рассматривать все пути, проходящие через
исходный узел, т. е. позволяет исключить пути bii, bjj, изображенные
на рис. 2.3, б. Полученная таким способом модернизированная матрица длин Г = ||γij|| умножается на дистанционную матрицу D с использованием тех же операций, что и ранее. При умножении матрицы Г на матрицу D образуется матрица Δ = ГD, элементы которой используются для получения дисперсионных матриц (т. е. матриц величин второго и т. д. кратчайших путей). Каждый элемент матрицы
Δ= || δij || имеет вид
=
δij min (γ i1 + d1j ); (γ i2 + d2 j ); ... (γ ik + dkj ); ... (γ iN + dNj ) .
k =1,N
(2.4)
В выражении (2.4) min означает, что минимум может браться
для кратчайшего пути (к = 1), второго по длине пути (к = 2) и т. д.
Каждый из членов (γie + dej) ¹ ∞ в выражении (2.4) определяет длину
пути от узла i к узлу j, если первым транзитным узлом после узла i
на пути к узлу j будет узел ε ∈ (1, …, N). Если узел ε не является соседним узлом с i, то (γie + dej) = ∞. Так как γii = ∞, член (γii + dij) будет
всегда бесконечным. При этом элемент (gij + djj) не обязательно равен бесконечности. Таким образом, число членов выражения (2.4),
не равных бесконечности, равно числу n соседних УК, т. е. числу
исходящих из УК ребер.
Член выражения (2.4), имеющий минимальное значение и определяющий длину кратчайшего пути от узла i к узлу j через узел ε
1
δ=
ij min ( γ i1 + d1j )...( γ iN + dNj ) ,
e
заносится в качестве элемента δ1ij в дисперсионную матрицу первого
выбора Δ1 = ||δ1ij||. Второй по значению член выражения (2.4), определяющий длину второго по протяженности пути после кратчайшего
от узла i к узлу j
δ2=
ij min ( γ i1 + d1j )...(γ iN + dNj ) ,
e
заносится в качестве элемента δ2ij в дисперсионную матрицу второго
выбора Δ2 = ||δ2ij||. При наличии n соседних узлов можно получить n
дисперсионных матриц ∆1, …, ∆n.
Для определения вершин, через которые проходит путь, необходимо наряду со значениями δ запомнить и номера соответствующих
им вершин.
16
Рассмотрим пример расчета элементов матриц D (D1, D2, …). Пусть
сеть связи имеет вид, представленный на рис. 2.2, для которой матрицы L1, D и Г приведены выше. Тогда, например, элемент δ112,
определяющий минимальный по протяженности путь от вершины A к вершине B матрицы Δ1 согласно (2.4), будет
δ112 = min [(γ11 + d12); (γ12 + d22);
(γ13 + d32); (g14 + d42); (γ15 + d52);
(γ16 + d62)] = min [(∞ +30); (30 + 0); (∞ +15);
(20 +15); (∞ + 0); (∞ + ∞)] = 30.
Так как минимальное значение в выражении находится на втором месте, что соответствует вершине B, то в минимальном пути от
вершины A к вершине B нет промежуточных вершин.
Элемент δ212 матрицы Δ2, соответствующий второму по протяженности пути от вершины A к вершине B, будет δ 212 = min[….] = 35.
Так как второе по минимуму выражение находится на четвертом
месте, что соответствует вершине D, второй по протяженности путь
от вершины A к вершине B проходит через вершину D.
Выбрав кратчайшие пути от какого-либо узла ко всем остальным, можно построить так называемое дерево кратчайших путей,
в котором из всего множества путей от узла указаны только кратчайшие от него пути ко всем остальным узлам. Например, для графа на рис. 2.2, с которым сопоставлена матрица L1 непосредственных связей, дерево кратчайших путей изображено на рис. 2.4. Оно
является поддеревом дерева путей (рис. 2.5).
Замечание. Дерево кратчайших путей и дерево путей от узла ко
всем остальным узлам для неориентированных графов (сетей) совпадает с деревом кратчайших путей и деревом путей соответственно от всех узлов к рассматриваемому узлу i. Для ориентированных
графов (сетей связи) такого совпадения может и не быть.
B
C
A
E
D
F
Рис. 2.4. Дерево кратчайших путей от вершины A
17
D
F
E
E
D
E
F
D
C
E
F
D
F
E
B
C
E
F
F
E
C
B
C
E
C
B
D
A
D
F
B
Рис. 2.5. Полное дерево путей от вершины A
2.2. Метод рельефов
Метод рельефов относится к групповым распределенным методам динамического управления. Критерием выбора пути является минимизация длины пути, выраженная числом транзитных
участков. На сети связи при применении этого метода должны выполняться операции формирования рельефа и его коррекция. Формирование рельефа осуществляется в начальный момент времени
(в момент пуска сети) и при развитии сети, т. е. при вводе в действие
новых узлов коммутации (УК). Коррекция выполняется периодически в процессе функционирования сети или в момент возникновения повреждений или перегрузок. Рассмотрим эти операции подробнее.
Формирование рельефа
В момент пуска сети формирование рельефа начинается с некоторого узла УКa, a = 1, 2, …, N, где N – число УК на сети. Говорят, что
начинается построение a-рельефа. В запоминающих устройствах
18
каждого УКi сети отводится объем памяти N · Mi, где Mi – число исходящих направлений из УКi. Туда заносится матрица рельефов Ri.
При формировании рельефа из УК – инициализатора во всех исходящих из него направлениях передается цифра 1. Эта единица на
соседних с УК-инициализатором узлах заносится в матрицу Ri по
координатам (n, m1), где n – номер УК-инициализатора; m1 – номер
ветви по которой поступила единица.
Далее процесс построения рельефа производится следующим образом. Все УК, в которые поступила цифра 1, передают по всем исходящим направлениям, за исключением того направления, по которому поступила 1, цифру 2. Эта цифра во всех УК, в которые она
поступила, заносится в матрицу Ri по координатам (n, m2), где m2 –
номер ветви, по которой поступила цифра 2. Теперь УК, на которые
поступила цифра 2, передают по исходящим направлениям цифру
3 и так далее, при этом должны соблюдаться следующие правила:
1. Если в УК поступили одинаковые цифры с двух и более направлений, то данный УК инициирует передачу цифры на единицу
большей поступившей по всем без исключения исходящим направлениям.
2. Если в УК поступает цифра с одного направления, то на данном УК происходит инициализация для передачи цифры на единицу больше той, которая поступила, по всем направлениям за исключением того направления, по которому получена данная цифра.
Передача цифры по этому направлению возможна лишь при поступлении в данный УК следующей цифры. Следовательно, цифра, передаваемая по этому направлению, должна быть на единицу больше цифры, поступающей второй по порядку.
3. Инициализация передачи цифр по всем направлениям на
каждом УК происходит один раз после поступления первой цифры
по порядку.
П р и м е р. Пусть имеется сеть, фрагмент которой изображен на
рис. 2.6.
Фрагменты матриц рельефов представлены на рис. 2.7.
Пусть в каждом УК отведена область памяти для формирования
матрицы R, фрагменты которой для строки, соответствующей УК А,
приведены на рис. 2.7 (bIJ – ветвь от УКI к УКJ). Пусть узлом-инициатором является УКА. В этом случае цифра 1 (см. рис. 2.7) будет
записана в матрицу RB и RC УКB и УКC. Далее эти УК передают по
всем исходящим направлениям, за исключением того направления,
по которому поступила цифра 1, цифру 2, которая будет занесена
в матрицы RB, RC, RD, RE, RF. Теперь УК, на которые поступила
19
1
1
УКА
1
1
2
УКB
2
2
3
4
2
УК C
2
3
3
УКE
3
3
2
3
2
УКD
3
2
2
УКF
3
3
Рис. 2.6. Фрагмент коммуникационной сети
RB
bBA
bBC
bBD
bBE
RC
bCA
bCB
bCE
УКА
1
2
4
3
УКА
1
2
3
RD
bDB
bDE
RE
bEB
bEC
bED
УКА
2
3
УКА
2
2
3
RF
bFC
УКА
2
Рис. 2.7. Фрагменты матриц рельефов
цифра 2, передают по исходящим направлениям цифру 3, соблюдая
при этом приведенные выше правила.
Так, согласно правилу 1, в УКЕ цифра 2 поступает с направлений, идущих от УКВ и УКС. В этом случае цифра 3 с УКЕ передается
по всем исходящим направлениям, включая УКВ и УКС.
Согласно правилу 2 в УКD цифра 2 поступает только по одному
направлению – от УКВ. Тогда цифра 3 с УКD должна передаваться
по всем направлениям, за исключением направления к УКВ. По этому
20
направлению будет передана цифра 4, так как следующая по порядку цифра, поступившая в УКD, – цифра 3.
В соответствии с правилом 3 при передаче цифры 3 на УКС от
УКЕ она заносится в матрицу RC по соответствующим координатам,
а инициализация передачи следующей по порядку цифры уже не
происходит, так как ранее была осуществлена передача цифры 2.
Так будет сформирован A-рельеф. Аналогично строятся рельефы для всех остальных узлов сети. Считается, что рельеф сформирован, если построены все a-рельефы (a = 1, 2, ….N).
Поиск оптимального пути
При установлении соединения от УКi к УКj поиск оптимального
пути состоит в отыскании в УКi и в каждом промежуточном УК ветви, которой соответствует минимальное число в соответствующей
строке матрицы рельефов для УКj.
П р и м е р. Пусть требуется установить соединение от УКD к УКА
(см. рис. 2.6). На УКD происходит обращение к строке матрицы рельефов RD, соответствующей УКА (рис. 2.7). Соединение устанавливается по ветви, которой соответствует минимальное число в этой
строке. Для рассматриваемого примера это ветвь bDB. На УКВ процесс поиска оптимального пути повторяется. В данном случае будет
выбрана ветвь bВА.
Если в этой ветви нет свободных каналов, то выбирается ветвь,
которой соответствует следующее по порядку число (в примере это
ветвь bВС) и т. д.
При выборе пути возможно возникновение «петель», когда соединение дважды проходит через один и тот же узел. «Петли» могут
быть двух типов – прямые и косвенные.
П р и м е р. Пусть требуется установить соединение от УКD к УК A.
На УКD выбирается ветвь bDB. Пусть теперь в ветви bBA нет ни одного свободного канала. Тогда вызов согласно матрице RB перенаправляется по ветви bBC. Если в ветви bCA тоже нет свободных каналов, то согласно матрице RC вызов должен быть направлен обратно
на УКВ. Это – первый тип «петли». При соответствующей комбинации загрузок каналов узлов, участвующих в передаче, данный вызов может блуждать по сети, например по такой петле: bDB, bBC, bCE,
bCB. Вызов дважды попадает в УКВ. Это – второй тип «петли».
Появление «петель» первого и второго типов недопустимо. Способ борьбы с ними заключается в том, что в процессе распространения по сети вызов «запоминает» номера УК, через которые он прошел, чтобы не проходить через них дважды.
21
Коррекция рельефа
Ситуация на сети непрерывно меняется: одни направления перегружаются, а нагрузка других уменьшается; могут выйти из строя
каналы связи; могут быть повреждения в отдельных направлениях
связи и УК, поэтому необходима периодическая коррекция рельефа
сети.
Рассмотрим процесс обмена служебной информацией между управляющими устройствами (УУ) соседних узлов УКi, УКk,
УКm при коррекции рельефа сети, фрагмент которой приведен на
рис. 2.8, а соответствующие матрицы рельефов – на рис. 2.9.
Пусть на УКi поступил сигнал начала передачи служебной информации о рельефах на соседние УК. Тогда его устройство управления (УУ) считает из ЗУ, в котором хранится матрица Ri, элементы первой строки и найдет минимальный из них. Предположим,
что минимальным элементом, т. е. элементом с минимальной высотой первого рельефа, будет r1k. Это означает, что кратчайший путь
R1k
Rm
Ri
R1
УКk
Ri
Rm
УК m
УК
Ri
R1k
Rm
Рис. 2.8. Фрагмент сети
Rk
Ri
Rm
УК
bi1
bik
biMi Rimin
УК
УК1
УК1
ri1
r1k
r1Mi
УК1
УКj
УКj
rj1
rjk
rjMi
УКj
УКN
УКN rN1
rNk
rNMi
УКN
УК
bki
Рис. 2.9. Матрицы рельефов
22
bmi
из УКi до УК1 проходит через узел УКk, а число транзитных участков в нем равно r1k. Согласно определению формирования рельефа УУ, прибавив единицу к этому элементу, получим элемент
r1i = min(r11, …, r1k, … r1Mi) + 1, который необходимо передать на соседние узлы. Значение r1i равно высоте первого рельефа тех ветвей,
которые связывают узлы с УКi.
Однако в рассматриваемой распределенной системе динамического управления элемент r1i не передается на соседние узлы до тех
пор, пока не будут определены другие элементы, соответствующие
другим рельефам, т. е.
r2i = min (r21, …, r2k, … r2Mi) + 1;
.............
;
i
rN = min (rN1, …, rNk, …rNMi) + 1.
i = (r i, …, r i, …, r i ).
Эти элементы образуют вектор Rmin
1
j
N
i
После того как вектор Rmin полностью вычислен управляющим
устройством УКi, передаем его в УУ всех соседних УК (см. рис. 2.9).
При этом он записывается в ЗУ этих УК в качестве столбцов матрицы рельефов. Точно такие же операции выполняют управляющие
устройства всех остальных УК.
Если в какой-либо ветви, например bi,k, отсутствуют каналы или
она повреждена, то при вычислении элементов rij (j = 1, …, N) принимаем rj,k = ∞.
2.3. Способы маршрутизации в АТМ-сетях
Маршрутизация ячейки производится коммуникационными
блоками, которые связывают ее идентификатор с местом назначения [4]. В каждом коммуникационном блоке существует таблица
маршрутизации (рис. 2.10).
Логический идентификатор имеет только местное (локальное)
значение и реализован в двух полях:
– групповой идентификатор VPI-идентификатор виртуального
пути (VP) занимает 8 бит в заголовке ячейки UNI и 12 бит в заголовке ячейки NNI. При этом каждый виртуальный путь может содержать множество виртуальных каналов, например идентификатор
элемента в группе VCI – идентификатор виртуального канала (VC)
занимает 16 бит.
Пара, образованная виртуальным путем (VP) и виртуальным каналом (VC), эквивалентна виртуальному каналу в сети коммутации
23
Узел коммутации
Данные а
Данные b
1
3 Данные a Данные b
2
4
Таблица маршрутизации для узла коммутации
Входной порт
Выходной порт
1
2
3
3
Рис. 2.10. Узел коммутации и таблица маршрутизации
Коммуникационный блок
VCIn
Коммуникационный блок
VCIm
VCIp
VCIm
Кроссовый коммутатор
VPIa
VCIn
VPIb
VPIc
VCIm
VPId
VCIp
Рис. 2.11. Маршрутизация ячеек в коммуникационных узлах
пакетов. Маршрут образуется с помощью множества виртуальных
путей и виртуальных каналов. Каждое соединение является каскадным соединением виртуальных путей и каналов. Маршрутизация ячеек в ATM-сетях представлена на рис. 2.11.
При этом используются два типа коммуникационных узлов:
– кроссовые коммутаторы для коммутации виртуальных путей,
использующие только идентификатор виртуального пути для направления пакетов данных по маршруту и управляемые средствами административного управления сети;
– коммуникационные блоки виртуальных каналов, учитывающие оба идентификатора VPI и VCI .
24
Кроссовый коммутатор VP используется для маршрутизации
всех виртуальных каналов, относящихся к одному виртуальному
пути. Кроссовые коммутаторы применяются для конфигурации
маршрута из сетей арендованных линий для создания альтернативных (резервных) маршрутов и организации взаимосвязи между узлами коммутации в режиме передачи информации без установления соединения.
Сети ATM используют два типа соединений:
– постоянные виртуальные соединения, создаваемые на основании соглашения между оператором сети и пользователем;
– коммутируемые виртуальные соединения, создаваемые по протоколу сигнализации между оборудованием пользователя и блоком
доступа к сети.
Рассмотрим более подробно коммуникационные устройства сетей. Они выполняют следующие функции:
– маршрутизация ячеек от входных портов к соответствующим
выходным портам, что создает в конечном счете маршрут;
– временное хранение ячеек;
– анализ и модификация заголовка ячеек (входные значения
VPI/VCI преобразуются в выходные VPI/VCI) и т. д.
Коммутационные устройства ATM-сетей имеют входные и выходные звенья, входные и выходные адаптеры и коммуникационную структуру, соединяющую на основании анализа заголовков и
их перевода в соответствии с таблицей соединений (рис. 2.12). Заголовок обычно обрабатывается во входных адаптерах, маршрутизация выполняется коммуникационной структурой, а временное
хранение информационных ячеек обычно производится в выходных и/или входных адаптерах. На рис. 2.12 показано, как во входном адаптере 1 заголовок с ячейки, поступающей по входному звену i1, т. е. a(i1) с помощью таблицы соединений преобразуется в заголовок b ячейки, которая затем поступает в выходной адаптер 3,
т. е. b(О3).
Обычно соединение между входным и выходным портом, определяющее маршрут через коммуникационную структуру, должно
быть предварительно известно, и информация о нем хранится в таблице соединений. Эта информация извлекается либо из маркера,
который передается заранее и устанавливает путь для передачи
информационных ячеек, относящихся к данному соединению (непрямая маршрутизация), либо извлекается из специальной метки, которая добавляется спереди к передаваемым информационным ячейкам, обеспечивая им возможность направлять самих себя
25
Таблица соединений
a(i1)
Перевод
заголовков
b(O3)
Анализ
заголовков
i1
O1
1
1
a
b
b
O3
3
iN
Входные
звенья
Мультиплексирование
и очереди
ON
N
Входные
адаптеры
Коммуникационная
структура
Выходные
звенья
Выходные
адаптеры
Рис. 2.12 Коммуникационные устройства АТМ и их функции
от соответствующего входного порта к соответствующему выходному порту (самомаршрутизация).
Так как услуги ATM-сети ориентированы на соединения, то
обычно режим маршрутизации является непрямым. Путь, соответствующий устанавливаемому соединению, должен быть в явном виде записан в каждом коммуникационном узле до начала передачи
информационных ячеек. Этот путь устанавливается маркером. На
рис. 2.13 показано, как проходящий маркер произвел коммутацию
входного звена i1 к выходному звену О3. Заголовок каждой поступающей ячейки по входному звену 1, т. е. a(i1), содержащий указатель VPI/VCI и имеющий только локальное значение, преобразуется в заголовок b, также содержащий указатель VPI/VCI, содержимое которого устанавливается на основе анализа вида информации
(данные, речь, видео), приоритетности и т.д.
На рисунке 2.14 приведен пример самомаршрутизации в коммуникационном устройстве сети ATM. Метка i содержит перечень
данного и последующего коммуникационных узлов и их выходных
портов. Так как метка i для данного коммуникационного устройства содержит указание выходного звена (O3). С помощью метки
производится коммутация i1 > O3 при ее приходе. Использованная информация удаляется из содержимого метки до прохождения
26
Таблица соединений
a(i1)
b(O3)
O3
Команда
коммутации
i1
a
b
Входное
звено Входной адаптер
b
Выходной адаптер
O3
Выходное
звено
Коммуникационная
структура
Рис. 2.13. Пример непрямой адресации
в коммуникационном устройстве АТМ
Таблица соединений
a(i1)
b
b
i1
Входное
звено
a+i
i
O3
Заголовок
для самомаршрутизации
b+i
Входной
адаптер
b+i
O3
Выходной
адаптер
Коммуникационная структура
Выходное
звено
Рис 2.14. Пример самомаршрутизации
в коммуникационном устройстве АТМ
ячейки через коммуникационное устройство. Заголовки a и b относятся здесь к информационной ячейке, проходящей через данное
коммуникационное устройство.
27
2.4. Управление в АТМ-сетях
Выбор оптимальных путей и виртуальных каналов реализуется
на основе соглашения между сетевым администратором и пользователем относительно качества сервиса (Q0S) и параметров трафика. В свою очередь параметры трафика зависят от класса сервиса
и могут задавать такие показатели, как усредненную скорость пакета (Submiddle Cell Rate – SCR), минимальную скорость пакета
(Minimum Cell Rate – MCR), пиковую скорость пакета (Peak Cell
Rate – PCR) и/или устойчивость к перегрузке (Burst Tolerance –
BT). ATM-коммутатор должен обеспечивать эти параметры на основе выбора соответствующих виртуальных путей и каналов и осуществлять буферизацию пакетов (ячеек), чтобы противодействовать
резким изменениям (взрывам) трафика. Для информации, чувствительной к задержкам, коммутатор должен обеспечить гарантированную пропускную способность и допустимый уровень задержек,
а также их колебаний.
ATM Forum разработал принципы формирования трафика перед его поступлением в сеть и принципы регулирования трафика
внутри сети ATM-коммутаторов при его прохождении. Алгоритм
управления доступа к соединению (формирование трафика) должен
гарантировать, чтобы трафик удовлетворял соглашению о качестве
сервиса.
ATM Forum определил два метода управления переполнением
трафика при его прохождении по сети: методы «открытой петли»
(Open loop) и «закрытой петли» (Closed loop).
Термин «открытая петля» означает, что все устройства сети, потребляющие ресурсы, во время передачи ячеек не имеют информации о состоянии сети, тем не менее этот метод предусматривает правило пометки ячеек на отбрасывание при переполнении сети, т. е.
помещения их для временного хранения в буферную память. Недостатком этого метода является то, что при отбрасывании ячеек, для
передачи которых уже использовались сетевые ресурсы, будет сделан запрос на повторную передачу всего передаваемого сообщения.
Это приведет к еще большему переполнению трафика.
Метод «закрытой петли» контролирует переполнение трафика при входе в сеть. Перед отправлением сообщения анализируется состояние узла назначения (получателя) на основании информации, поступающей от данного узла. Отправка очередного сообщения может быть задержана, если наблюдается переполнение
трафика.
28
При использовании ATM-сетей предполагается, что трафик любого типа можно передавать с использованием одного из четырех базовых классов сервиса, это:
– постоянная скорость передачи (Constant Bit Rate – CBR), используемая для передачи равномерного несжимаемого голосового
потока (сервис AAL1);
– переменная скорость передачи (Variable Bit Rate – VBR), используемая для передачи неравномерного возникающего, критичного
к задержкам трафика, например видео со сжатием (сервис AAL2);
– доступная скорость передачи (Available Bit Rate – ABR), используемая для неравномерного трафика, как правило, от локальных сетей (сервис AAL3/4);
– неопределенная скорость передачи (Unspecified Bit Rate –
UBR), используемая для передачи всех остальных типов трафика
(сервис AAL5).
ATM-коммутатор распределяет свои ресурсы, обеспечивая трафику перечисленные классы сервиса. Если же трафик выходит изпод контроля, то соответствующие ячейки либо отбрасываются немедленно (попадают в буфер), либо помечаются как разрешенные
для отбрасывания.
В локальных сетях ATM режимы CBR и VBR используются ограниченно, в глобальных сетях – часто. Класс VBR поддерживается
небольшим числом типов коммутаторов, CBR реализуется многими
коммутаторами. При работе в режиме CBR требуется следить только за пиковыми скоростями передачи ячеек, при использовании
VBR коммутатор устанавливает как пиковые, так и средние скорости передачи ячеек, задержки передачи и учитывает всплески
интенсивности потока.
Режим UBR достаточно прост в реализации. К трафику не предъявляются какие либо жесткие требования. Поведение трафика не
контролируется, что крайне нежелательно. Для улучшения характеристик вводится механизм управления трафиком, например ранний сброс пакетов (Early Packet Discard – EPD) и сброс остатков пакета (Partial Packet Discard – PPD). Данный тип сервиса называется
UBR+. Кроме того, используется алгоритм своевременного обнаружения перегрузок (Random Early Detection – RED).
Существуют два типа управления в ATM-сетях: превентивный
контроль и адаптивный контроль. Превентивный контроль основан
на соглашении о трафике. Источник трафика «вписывается» в рамки качества обслуживания, оговоренного заранее с помощью механизмов контроля, таких как Leaky Basket (метод «протекающего
29
ведра») и Virtual Scheduling (виртуальный список). Этот тип контроля применяется для режимов CBR и UBR, где характеристики
трафика известны, либо могут быть спрогнозированы.
Адаптивный контроль основан на использовании свободной полосы пропускания. Он реализуется для ABR и UBR, где нет жестких требований к качеству обслуживания. Адаптивный контроль
осуществляется с помощью процедуры обратной связи между источником информации и коммутатором ATM. Обратная связь может быть явной, когда для передачи информации о перегрузках
применяются специальные ячейки, как в режиме ABR, или скрытой, когда поведение источника информации изменяется в соответствии с изменением состояния сети.
Алгоритм RED в ATM-сетях использует скрытую обратную связь
для уведомления о перегрузках за счет выборочного уничтожения ячеек от источника информации. Алгоритм RED уничтожает часть поступающих в сеть ячеек. В сетях ATM применяются две модификации алгоритма: C-RED – Cell RED, работающая с каждой ячейкой, и P-RED
– Packet RED, работающая с группой ячеек, образующих пакет.
В табл. 2.1 приведены перечисленные виды контроля трафика.
Рассмотрим приведенные методы контроля переполнения более
подробно.
Правила допуска вызова в сеть связаны с учетом влияния приоритетов на качество обслуживания и требуют знания состояния
звена передачи, т. е. знания числа принятых к обслуживанию вызовов различного типа. Решение о принятии к обслуживанию следующего вызова может быть осуществлено, если вероятность потери
информационных ячеек вызовов, уже находящихся на обслуживании, будет составлять, например, 10–9–10–10.
Метод Leaky Busket (метод «протекающего ведра») получил большое распространение и основан на следующем. Каждому установТаблица 2.1
Методы контроля трафика в сетях ATM
Тип управления
Контроль
с помощью
использования
Превентивный
Классов сервиса
CBR, UBR
ABR
–
Явная
Скрытая
–
UBR+ (EPD, PPD)
RED (C-RED, P-RED)
Обратной связи
Механизмов
контроля
30
Leaky Busket
Virtual Scheduling
Адаптивный
UBR
ленному соединению ставится в соответствие счетчик, содержимое
которого увеличивается на единицу в случае поступления информационной ячейки в коммутатор и уменьшается, если в звене передачи наблюдается приемлемая скорость передачи. В счетчик вводится некоторый порог. Если содержимое счетчика достигает его
значения, то доступ ячеек в сеть прекращается и они поступают
в буферный накопитель. Этот метод относится к стратегии обслуживания уже принятого вызова. Рассмотрим алгоритм RED, который
уничтожает часть поступающих в сеть ячеек. Число уничтоженных
ячеек определяется параметром, который называется вероятностью уничтожения (pa). Этот параметр определяется длиной очереди на обслуживание в ATM-коммутаторе. Средняя длина очереди l
рассчитывается по формуле
1

l=
1 − n
 2
1

 lïðåä + lòåê n ,

2
где lпред – длина очереди на предыдущем подсчете; l òåê – текущая
длина очереди; n – весовой коэффициент (n > 1), определяемый администратором сети. Его значение выбирается следующим образом.
Если величина n имеет малое значение, то средняя длина очереди l
определяется, в основном, текущей длиной lòåê . В этом случае алгоритм оперативно реагирует на любые изменения текущей длины
очереди, и ATM-коммутатор быстро избавляется от лишних ячеек
при малейшей опасности перегрузки. Но при малых значениях n будут отбрасываться ячейки при небольших временных увеличениях
очередей, что необосновано. Если коэффициент n имеет большое
значение, то средняя длина очереди l становится в основном функцией от предыдущей длины очереди. Тогда алгоритм медленно реагирует на изменения длины очереди, что позволяет ATM-коммутатору сглаживать пиковые значения трафика без удаления ячеек. Но при этом алгоритм может оказаться настолько медленным,
что будет продолжать отбрасывать ячейки даже тогда, когда длина
очереди станет меньше минимального значения. Работа алгоритма
RED заключается в следующем. Если средняя длина очереди l
находится внутри назначенного диапазона порогов Lmin < l < Lmax,
алгоритм RED уничтожает некоторую часть ячеек. Доля уничтожаемых ячеек определяется значением Pa, которое рассчитывается
в соответствии с состоянием ресурсов коммутатора. Пересчет вероятности Pa и процесс отбрасывания ячеек будут продолжаться до
тех пор, пока l > lmin.
31
Вероятность отбрасывания пакетов рассчитывается по формуле
Pa =
При этом
Pb =
Pb
.
1 − CountPb
Pmax (1 − lmin )
lmax − lmin
L
, Lmin
где Pmax – максимальная вероятность уничтожения ячеек; Count –
количество ячеек, помещенных в очередь с момента последнего
сброса; L – длина пакета, инкапсюлированого в ATM; Lmax – максимальная длина пакета, инкапсюлированного в ATM.
Если средняя длина очереди l больше или равна максимально
допустимому значению lmax, то поступившая на вход коммутатора
ячейка будет уничтожена обязательно. При этом вероятность уничтожения пакетов Pa зависит от размера пакетов. Длинные пакеты
будут уничтожаться чаще, чем короткие.
Модификация алгоритма C-RED работает с каждой ячейкой,
а модификация P-RED – с группой ячеек. Поскольку алгоритм применяется для каждой ячейки пакета, имеется четкая картина состояния сети в данный момент, но реализация алгоритма сложна
при больших скоростях передачи.
Алгоритм P-RED работает с группой ячеек, образующих пакет.
Пересчет средней длины очереди для всех ячеек пакета осуществляется один раз в момент поступления первой ячейки. Алгоритм менее гибок, чем предыдущий, но может использоваться при высоких
скоростях передачи.
Недостатком алгоритма RED при работе в сетях ATM является
то, что он отбрасывает только часть ячеек пакета, а остальные будут уничтожены лишь в приемнике. Алгоритм PPD (Partual Packet
Discard) обеспечивает удаление неполных пакетов.
В алгоритме RED вероятность уничтожения пакета зависит от
его размера (длины), а эти длины определяются в процессе передачи через ATM-коммутатор. В AAL5 граница пакета определяется
по значению поля PTI (3 бита) в заголовке пакета, помечающего последнюю ячейку пакета. Так как определить размер поступающего
в коммутатор пакета нельзя, его считают равным размеру последнего пакета, принятого по данному виртуальному каналу.
В алгоритме EPD вероятность уничтожения пакета не зависит от
его длины. Этот алгоритм производит сброс целого пакета, а не его
отдельных ячеек. Это снижает нагрузку на ATM-коммутатор.
32
3. ПОВЫШЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ
В ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ
3.1. Множественные маршруты в протоколе OSPF
Если между двумя узлами сети существует несколько маршрутов с одинаковыми или близкими метриками, протокол OSPF позволяет направлять части трафика по этим маршрутам в пропорции, соответствующей значениям метрик. Например, если существуют два альтернативных маршрута с метриками 1 и 2 (рис. 3.1),
то две трети трафика будут направлены по первому пути, а оставшаяся часть (треть) – по второму. При этом уменьшается средняя задержка прохождения дейтограмм между отправителем и получателем, а также уменьшаются колебания значений средней задержки.
Кроме того, уменьшается время восстановления режима нормальной работы. Суть этого процесса заключается в следующем.
Если при использовании только одного из возможных маршрутов
этот маршрут внезапно выходит из строя, весь трафик будет направлен на альтернативный маршрут, но при этом при больших
объемах информации велика вероятность затора на новом маршруте. Если до аварии использовалось разделение трафика по нескольким маршрутам, то отказ одного из них вызовет изменение маршрутизации только части трафика, что уменьшает вероятность заторов
и их последствия меньше сказываются.
1
2
2
K
5
2
A
E
B
1
1
4
1
C
3
3
D
Рис. 3.1. Пример OSPF-системы с множественными маршрутами
33
2
1 B
1
1
1
A
1
1
3
C
Рис. 3.2. Пример фрагмента сети и ситуации
по поддержке множественных маршрутов
П р и м е р. Пусть имеется два маршрута между узлами 1 и 3
(рис. 3.2) с метриками, равными единице на каждой линии
связи.
Пусть узел 1 использует поддержку множественных маршрутов
и отправляет данные в узел 3. Тогда 2/3 трафика пойдeт по маршруту С, а 1/3 трафика – по маршрутам A и В. Пусть узел 2 также использует поддержку множественных маршрутов.Когда к нему прибывают дейтограммы, адресованные в узел 3, в том числе отправленные из узла 1, он применяет тот же алгоритм, т. е. 2/3 трафика
отправляются в узел 3 по маршруту B, а одна треть – по маршрутам A и C. Следовательно, 1/9 дейтограмм, отправленных узлом 1
в узел 3, возвращается опять в узел 1, а 1/3 трафика опять отправляется в узел 3 по маршруту С, а 2/3 трафика – по маршруту A и B
через узел 2 и т. д. В результате формируется «частичный цикл» при
посылке дейтограмм из узла 1 в узел 3, который ведет к частичному зацикливанию дейтограмм и перегрузке линии A. Чтобы избежать зацикливания, необходимо применять правило: если узел X
отправляет данные в узел Y, он может пересылать их через узел Q
только в том случае, если Q ближе к Y, чем X.
3.2. Метод отклонений потока
На сети пакетной коммутации применяются различные принципы построения плана распределения информации, т. е. способа выбора на узлах коммутации (УК) исходящих направлений для передачи по ним пакетов. Рассмотрим три наиболее характерных [2].
Первый способ является наиболее простым и предполагает наличие только одного кратчайшего пути передачи пакетов меж34
ду двумя корреспондирующими УК. При этом матрица маршрутов для УКi представляет собой вырожденную (единичную) или
примитивную матрицу размера N строк на ni+1 столбцов (N – число УК в сети, ni – число ветвей в узле УКi), например, такого
вида:
УК1
Mi =
УКj
УКN
0
…
1
…
0
bi1
…
…
…
…
…
bik
1
…
0
...
1
…
…
…
…
…
bini
0
…
0
…
0
В такой матрице каждый элемент равен 1 или 0, т. е. mji ∈ (0, 1),
в одной строке имеется только одна единица. Поэтому пакеты к узлу назначения УК1 с УКi будут передаваться только по ветви bik, если m1k = 1.
Этот способ прост, но не позволяет обеспечить хорошее использование сетевых ресурсов, и велика вероятность возникновения тупиковых состояний даже при локальных перегрузках сети.
Второй способ характеризуется тем, что в случае отказа принятия пакета на соседнем УКk из-за отсутствия свободной памяти, возникновения ошибки или по каким-либо другим причинам, на УКi,
откуда передается пакет на УКl, обеспечивается выбор другой ветви bir, вместо ветви bik для повторной передачи этого пакета с УКi.
Если и с УКr поступит отказ в принятии пакета, то в третий раз
осуществляется передача пакета по ветви bie (e ≠ k; e ≠ r) и т. д., пока не будут перебраны все исходящие ветви, доступные для передачи пакетов с УКi к узлу назначения УКj. После этого начинается
второй цикл выбора ветвей. В этом случае элементы mjk, матрицы
маршрутов Mi = УКj||mjk|| принимают целочисленные значения, т. е.
mjk ∈ {1, 2, …ki}, ki ≤ ni. Они определяют порядок выбора направлений при передаче пакетов с УКi к УКj.
Данный способ аналогичен методу поиска исходящих направлений в сети коммутации каналов с обходными путями (методу рельефа), заметно улучшает использование связных ресурсов, существенно уменьшает вероятность возникновения тупикового состояния в сети, время передачи пакетов по сети.
Третий способ (метод отклонений) производит рассеяние каждого из потоков пакетов по направлениям, что позволяет обеспечить
минимальную задержку в передаче пакета.
35
План распределения пакетов задается стохастической матрицей
вида
Mi = УКj || mjk ||,
где 0 ≤ mjk ≤ 1, при этом
ni
∑mj,k = 1.
k =1
При доказательстве оптимальности распределения потоков по
сети пакетной коммутации обычно допускается следующее:
– в модели сети коммутации пакетов, имеющей N узлов коммутации и Ti ветвей, отходящих от каждого узла коммутации, предполагается, что ветвь состоит из одного канала, все каналы сети надежны и УК также надежны;
– пропускная способность канала (ветви) постоянна и равна
C пакет./с;
– время (с) обработки пакетов в УК равно k;
– время распространения сигнала Pk (бита информации) по каналу bk зависит от длины канала lk, т. е. Pk = lk/V, где V – скорость распространения сигнала по каналам;
– поступающие на УKi пакеты, предназначенные для передачи
на другие УКj, образуют пуассоновский поток пакетов со средним
значением lij пакет./с;
– пакеты в сети не теряются и не возникают новые, т. е. служебные пакеты не рассматриваются. Объем потока пакетов, поступаюTi
щего в УКi (и покидающего его) в единицу времени l i = ∑l ij , а общий объем поступающего в сеть потока
=
Λ
j=1
N Ti
∑∑lij ;
=i 1j= 1
– длины всех пакетов независимы и распределены по экспоненциальному закону со средним значением 1/m бит, где m – интенсивность обслуживания пакета (емкость памяти на УК принимается
неограниченной).
Отношение li/m характеризует нагрузку ri. Ее называют коэффициентом использования, т.е. ri = li/m.
По какой-либо ветви blk может проходить весь или некоторая
часть потока пакетов lij, т.е. llikj = Qlikjlij, или rlikj = Qlikjrij, где Qlikj – коэффициент рассеяния потока lij, который определяет долю потока, приходящегося на ветвь blk при передаче потока пакетов от УКi
36
к УКj, причем 0 ≤ Qlikj ≤ 1. При этом по одной и той же ветви blk могут
проходить различные потоки в частичном или полном объеме.
Тогда общий поток, поступающий на ветвь, будет l lk =
rlk =
N
∑ llkij
или
ij=1
N
∑ rlkij .
ij=1
При этих допущениях среднее время задержки передачи пакета
по сети
N

 l lk / m
/
T=
1
Λ

(
)
(3.1)
∑  C − llk / m + llkTlk 
ñð
lk
= 1;l ≠ k  lk

или
N

 rlk
lk ′ 
(3.2)
Tñð
= (1 / Λ ) ∑ 
+
r
T
,
lk
lk


lk
= 1;l ≠ k  Clk − r

где T′lk = mТik; Clk – емкость (пропускная способность) ветви blk
(пакет./c).
Задача оптимального распределения потока пакетов по сети состоит в нахождении величин Qijlk , при которых будет минимальным среднее время задержки передачи пакета в сети Тср. Для этого
может быть использован эффективный итерационный метод – метод девиации (отклонения) потока.
П р и м е р. Пусть задана ориентированная сеть, показанная
на рис. 3.3. Пусть УК3 находится в космосе на спутнике Земли, а
остальные УК – на поверхности Земли. В сеть поступает два потока
l14 = 2 пакета/с; l32 = 1 пакет/с. Длины пакетов распределены по
экспоненте со средним значением, равным 1, т. е. m =1.
На рис. 3.3 на дугах показаны интенсивности частей потока пакетов для исходных потоков l14 и l32 (нижние индексы) на соответствующей дуге графа (верхние индексы). В квадратных скобках
указаны оптимальные значения интенсивности потока пакетов, полученные в результате расчетов.
Таким образом, матрица требований задана в виде
УК1 УК2 УК3 УК4
УК1
Ф = УК2
УК3
УК4
–
–
–
–
–
–
1
–
–
–
–
–
2
–
–
–
.
37
λ 32
УК3
λ 13 = 0,49
13
= 0,49]
[ λ 14
λ 34 = 0,66
[ λ 34
14 = 0,49]
λ 32 = 0,83
[ λ 34
32 = 0,17]
[ λ 32
32 = 0,83]
λ 42 = 0,17
[ λ 42
32 = 0,17]
УК1
λ 14
λ 12 = 1,51
[ λ 12
14 = 1,51]
УК2
УК4
λ 24 = 1,51
[ λ 24
14 = 1,51]
λ 32
λ 14
Рис. 3.3. Оптимальное распределение потоков в коммуникационной сети
Пусть задана матрица емкостей ветвей в виде матрицы пропускной способности C:
УК1 УК2 УК3 УК4
УК1
С = УК2
УК3
УК4
–
–
3
–
3
–
2
3
2,5
2,5
–
–
–
3
2
–
.
Емкости каналов между вершинами i и j (ij = 1, …, 4) Cij = Cji
(если каналы существуют в обоих направлениях): С12 = 3; C13 = 3;
C23 = 2, 5; C24 = 2; C34 = 2.
Время задержки в передаче (время обработки плюс время распространения) представим в виде матрицы T
УК1 УК2 УК3 УК4
УК1
T = УК2
УК3
УК4
38
–
–
0,5
–
0
–
0,5
0
0,5
0,5
–
–
–
0 .
0,5
–
Время распространения сигналов по каналам Tij = Tji (ij =1, …, 4)
(при условии, что каналы существуют в обоих направлениях):
T12 = 0 c; T13 = 0,5 c; T23 = 0,5 c; T24 = 0 c; T34 = 0,5 c.
Из матрицы T видно, что временем обработки на УК и временем
распространения сигналов между наземными УК мы пренебрегаем.
При использовании метода отклонения было получено оптимальное распределение потоков пакетов, представленное на рис. 3.3, где
на ветви blk в скобках указаны доли проходящих по ней потоков.
Такое распределение обеспечивает минимальное среднее время задержки передачи пакета Тср = 1,5 с.
Метод отклонения потоков позволяет получить минимальное
среднее время задержки пакета в сети, но требует достаточно большого объема вычислений, поэтому для больших сетей, особенно если требуется перераспределять потоки в изменяющихся условиях,
целесообразно применять субоптимальные методы распределения
потоков типа последовательного или параллельного методов распределения потоков некоммутируемой сети.
Рассмотрим один из них, а именно метод последовательного приближения к оптимальному. Он относится к классу итерационных
методов и состоит в выполнении последовательности итераций, состоящих из нескольких шагов на каждой итерации (рис. 3.4).
На нулевой итерации, состоящей из одного шага, производится
распределение потоков по кратчайшим путям, причем критерием
выбора кратчайшего пути является время задержки пакета на этом
пути.
Вначале находятся все пути Пe(j), по которым возможна передача каждого из потоков.
Затем для каждого из этих путей Пe(j) с учетом только первого
потока по формуле (3.1) или (3.2) вычисляется среднее время заÏe (1)
в предположении, что поток lij = 1 передается тольдержки Òñð
ко по одному пути Пe (1). Из всех возможных путей выбирается
Ïe (1)
минимально, и поток l1 направляеткратчайший, в котором Òñð
ся по этому пути.
Аналогично выбираются пути для передачи остальных потоков.
После того как все потоки распределены, по формуле (3.1) или (3.2)
подсчитывается среднее время нулевой итерации Тср0. На этом выполнение нулевой итерации заканчивается.
Замечание. Если на нулевой итерации не найдено ни одного
Ïe (1)
хотя бы для одного потока, это означает,
кратчайшего пути с Òñð
что реального плана распределения потоков только по кратчайшим
путям без их рассеяния не существует, поэтому в данном случае
39
происходит условное распределение потока по одному из «пересыÏe (1)
= ∞. На последующей итеращенных» путей, для которого Òñð
ции предполагается рассеяние потоков.
Рассмотрим пример, приведенный выше. Выполним нулевую
итерацию. Для этого построим дерево путей для имеющихся двух
потоков l14 (рис. 3.4, а) и l32 (рис. 3.4, б). Видно, что для потока l14
имеется четыре пути: П124(1, 4); П1234(1, 4); П134(1, 4) и П1324(1, 4),
а для потока l32 – три пути П32(3, 2); П342(3, 2) и П312(3, 2).
Найдем кратчайший из них по критерию минимальной задержки. По формуле (3.1) вычислим время задержки для каждого из путей, предполагая, что по сети передается только один из потоков
124
Ï1234
и только по одному пути. При этом получим Ò(Ï
1, 4) = 2; Ò(1, 4) = ∞;
134
Ò(Ï
1, 4) = ∞;
1324
Ò(Ï
1, 4) = ∞;
32
Ò(Ï
1, 4) = 1,5;
342
Ò(Ï
1, 4) = 2;
312
Ò(Ï
1, 4) = 2.
Таким образом, кратчайшим путем для потока l1, 4 является путь
24
П124, а для потока l3, 2 – путь П32. Следовательно, Q12
Q14
=
Q32
1,
14 =
32 =
а остальные коэффициенты рассеяния равны 0 (рис. 3.4, в, г).
По формуле (3.1) определим Т0ср = 167.
Первая итерация.
Шаг 1. Производится рассеяние потока l14 на исходящем УК1.
34
Пусть шаг рассеяния D = 0,1. Тогда Q12
0,9; Q13
0,1; Q14
=
1.
14 =
14 =
Остальные коэффициенты рассеяния не изменяются, т. е.
24
Q14
=
Q32
1 (рис. 3.4, г, д). С учетом этих коэффициентов получим:
32 =
24
34
l12
1,8; l14
=
1,8; l13
0,2; l14
=
0,2; l32
1. По форму14 =
14 =
32 =
ле (3.1) определим среднее время задержки шага 1 первой итерации
1
1
Òñð
1 = 1,63. Так как Òñð 1 < Òñð 0 , данное рассеяние принимается.
Шаг 2. Рассеиваем поток l14 на транзитном УК2, принимая
24
Q14
23
34
=
0,9; Q14
=
0,1; Q14
=
1, оставляя остальные результаты ко-
эффициентов рассеяния без изменения (рис. 3.4, г, е). При этом
24
34
34
34
l12
1,8; l14
=
1,62; l14
=
0,18; l14
=
0,18; l13
0,2; l14
=
0,2;
14 =
14 =
1
1
1
l32
1; Òñð
32 =
2 = 1,65. Так как Тср 2 > Тср 1, рассеивать поток l14 на
транзитном УК2 нецелесообразно. Данное рассеяние не принимается и в последующем потоке l24 на УК2 рассеиваться не будет, т.е. после шага 2 дерево путей для потока l14 изменилось (рис. 3.4, ж).
Шаг 3. Рассеиваем поток l14 на транзитном УК3. Принимаем
34
Q14
40
32
24
=
0,9; Q14
=
0,1; Q14
=
1. Определяем объемы потоков в вет-
4
a)
б)
2
1
2
3
1
3
4
2
2
3
4
4
2
4
в)
1
1
0
2
1
г)
4
0
3
0
2
0
0
3
0
4
0
1
3
4
0
2
0
1
2
0
4
2
4
д)
1
1
0,9
0
2
0,9
е)
4
0
3
0,1
0
3
0
2
1
4
0
3
2
1
0,1
з)
4
1
2
0
4
2
0
1
4
1
4
2
0,9
3
4
4
1
0,9
0
1
4
ж)
1
3
0,1
4
1
4
0,1
2
0,9
3
0,1
4
1
4
и)
0,9
3
к)
2
0,1
4
1
0,1
2
3
0
1
1
0,9
4
2
2
0
2
Рис. 3.4. Последовательность шагов при итерационном методе
отклонения потоков
41
вях
l12
1,8;
14 =
24
l14
=
1,8;
l13
0,2;
14 =
34
l14
=
0,18;
32
l14
=
0,02;
24
1
1
1
l14
=
0,02; Òñð
3 = 1,8. Так как Тср3 > Тср1, то на транзитном УК3
нецелесообразно рассеивать поток l14. Для дальнейшего рассеяния
осталось дерево путей, показанное на рисунке 3.4, з. Поскольку возможные рассеяния потока l14 при постоянном коэффициенте рассеяния Q14 исчерпаны, на последующих шагах первой итерации производится рассеяние потока l32.
Шаг 4. На этом шаге получаем Q34
0,9; Q32
0,1; Q12
1.
32 =
32 =
32 =
Другие коэффициенты оставлены такими, какими они были на ша24
ге 1 (рис. 3.4, д, к). Объемы потоков l12
1,8; l14
=
1,8; l13
0,2;
14 =
14 =
34
1
l14
=
0,2; l32
0,9; l31
0,1; l12
0,1. Определяем Òñð
32 =
32 =
32 =
4 = 2,64.
1
1
Так как Тср 4 > Тср 1, этот вариант рассеяния не принимается, и в дальнейшем поток l32 по ветви b31 рассеиваться не будет.
Для дальнейших шагов остаются два дерева путей: для потока l14
(рис. 3.4, з); для потока l32 (рис. 3.4, и).
Шаг 5 . На этом шаге Q34
0,9; Q34
0,1; Q42
1. Другие ко32 =
32 =
32 =
эффициенты оставлены такими, какими они были на шаге 1
24
(рис. 3.4, з, и). Объемы потоков l12
1,8; l14
=
1,8; l13
0,2;
14 =
14 =
34
1
l14
=
0,2; l32
0,9; l34
0,1; l42
0,1. Находим Òñð
32 =
32 =
32 =
5 = 1,61.
Так как Т1ср 5<Т1ср 1, вариант рассеяния на шаге 5 принимается.
Вторая итерация.
Шаг 1. Увеличиваем рассеяние потока l14 . Получаем Q12
0,8;
14 =
13
13
24
12
Q14 =
0,2; Q14 =
0,4; Q14 =
1. Объемы потоков в ветвях l14 =
1,6;
24
34
32
34
42
l14
=
1,6; l13
=
0
,
4
;
l
=
0
,
4
;
l
=
0,9;
l
=
0
,
1
;
l
=
0
,
1
.
На14
14
32
32
32
2
2
1
ходим Òñð 1 = 1,52. Так как Т ср 1 < Тср 5, то данное рассеяние принимается.
Шаг 2. Увеличиваем рассеяние потока l32. Получаем Q32
0,8;
32 =
24
Q34
0,2; Q42
1. Объемы потоков в ветвях l12
1,6; l14
=
1,6;
32 =
32 =
14 =
34
l13
0,4; l14
=
0,4; l32
0,8; l34
0,2; l42
0,2. Получаем
14 =
32 =
32 =
32 =
2
2
2
Òñð
2 = 1,51. Так как Т ср 2 < Т ср 1, данное рассеяние принимается.
Третья итерация.
0,7;
Шаг 1. Увеличиваем рассеяние потока l14. Получаем Q12
14 =
24
34
24
24
Q14
=
0,3; Q14
=
1; Q14
=
1. Объемы потоков l12
1,4; l14
=
1,46;
14 =
42
λ 32
УК3
λ 32 = 0,9
[ λ 32
32 = 0,9]
λ 14
λ 12 = 1,6
[ λ 12
14 = 1,6]
[ λ 34
32 = 0,1]
λ 42 = 0,1
[ λ 42
32 = 0,1]
λ 13 = 0,4
13
= 0,4]
[ λ 14
УК1
λ 34 = 0,5
[ λ 34
14 = 0,4]
УК2
λ 32
УК4
λ 24 = 1,6
[ λ 24
14 = 1,6]
λ 14
Рис. 3.5. Субоптимальное распределение потока пакетов
34
l13
0,6; l14
=
0,6; l32
0,8; l34
0,2; l42
0,2. Получаем
14 =
32 =
32 =
32 =
3
3
2
Òñð
1 = 1,52. Так как Т ср 1 < Т ср 2, данное рассеяние не принимается.
Шаг 2. Увеличиваем рассеяние потока l32. Получаем Q32
0,7;
32 =
Q34
0,3; Q42
1. Объемы потоков в ветвях потоков l12
1,4;
32 =
32 =
14 =
24
34
l14
=
1,4; l13
0,4; l14
=
0,4; l32
0,7; l34
0,3; l42
0,3.
14 =
32 =
32 =
32 =
3
3
2
Получаем Òñð
2 = 1,52. Так как Т ср 2 > Т ср 2, то данное рассеяние не
принимается.
Так как на третьей итерации не получено ни одного принятого
рассеяния, процесс оптимизации распределения потоков заканчивается. Получено субоптимальное распределение потоков (шаг 2
второй итерации), показанное на рис. 3.5. При этом Т2ср 2 = 1,51. При
субоптимальном рассеянии получено несколько большее среднее
время задержки, чем при минимальном, полученном методом отклонения потока (см. рис. 3.3). Но различие составляет менее 10%,
что вполне приемлемо на практике.
43
4. МЕТОДЫ КОММУТАЦИИ В ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ
4.1. Принципы работы коммутаторов
Мультисервисные сети способны обеспечить доступ значительного числа пользователей в реальном масштабе времени к различным мультимедийным услугам, таким как IP-телефония, передача
и прием аудио- и видеопотоков, телевидение по требованию, телевидение высокой четкости (ТВВЧ) и т. д.[3].
При выборе коммуникационного оборудования необходимо учитывать:
– число абонентов;
– необходимую им полосу пропускания, т. е. необходимую скорость передачи;
– допустимую задержку;
– допустимые колебания задержки (джиттер);
– допустимую вероятность возникновения ошибки и т.д.
Перечисленные параметры в значительной степени зависят от
вида передаваемой информации.
Наибольшую нагрузку на сеть оказывают видеопотоки. Рассмотрим процесс передачи видеограмм по локальной IP-сети для
подключения обычного дома со следующими параметрами информационной нагрузки. Транслируемый абоненту видеопоток кодируется в цифровом виде в соответствии со стандартом MPEG [3].
В соответствии с этим стандартом цифровой видеопоток с частотой
регенерации изображения в 25 или 30 кадр./с состоит из последовательности M/Z-групп видеокадров (GOP – group of pictures). Каждая группа имеет фиксированную длину и структуру.
В составе каждой группы выделяются видеокадры (VOP – Video
Object Plane) трех типов: I – кадр (опорный), P – кадр (предсказанный), B – кадр (двунаправленный).
Каждая группа видеопотока начинается с единственного в ней
I-го кадра. Параметр M видеопотока определяет общее число кадров
в группе, а параметр Z – интервал между P-кадрами.
Структура группы типичного цифрового видеопотока с параметрами 15/3 имеет вид: IBBPBBPBBPBBPBB и параметры, приведенные ниже.
Характеристики видеотрафика для отдельного пользователя:
– интенсивность поступления VOP – 25 VOP/c;
– средний размер VOP – S = 360 × 240 пикселей;:
– схема кодирования I: P: B кадров – I:1 P:4 B:10.
44
Характеристики кадров, поступающих на рабочую станцию
пользователя:
– интенсивность поступления I-кадров для пользователя –
1,67 кадр./c;
– средний размер I-кадра – 1457 байт;
– интенсивность поступления P-кадров для пользователя –
6,67 кадр./c;
– средний размер P-кадра – 486 байт;
– интенсивность поступления B-кадров для пользователя –
16,67 кадр./c;
– средний размер P-кадра – 182 байт;
Технические параметры телекоммуникационной среды для отдельного коммутатора пользователя приведены ниже:
Коммутатор:
– производительность коммутирующей матрицы – 1Г бит/c;
– пропускная способность – 4, 8 Мп/c;
– размер разделяемой памяти коммутатора – 4 Мб;
Порт коммутатора (пропускная способность) 100 Base-T –
14 880 пакет./с.
Порт коммутатора 1000 Base-X – 1 488 000 пакет./c.
При этом 1000 Base-X может быть [5]:
1000 Base-LX (источник излучения – лазер 1300 нм; волокно –
MMF; SMF);
1000 Base-SX (источник излучения – лазер 850 нм; волокно –
MMF);
1000 Base-CX (среда передачи – STP категории 5; длина 25 м).
Имеется в виду, что пакет содержит 1500 байт. Это пакет максимальной длины для сети Ethernet со скоростью 10 Мбит/c.
На принципы построения коммуникационных устройств современных вычислительных сетей существенное влияние оказывают два фактора: необходимость высокой скорости работы коммутатора и стохастический характер потока пакетов. Коммутатор
имеет в своем составе несколько подсистем. Транспортная подсистема коммутатора отвечает за правильную транспортировку пакетов от входного до соответствующего выходного порта с требуемым качеством обслуживания. При этом коммутация, т. е. перенос пакетов от входов коммутатора до соответствующих выходов,
сочетается с мультиплексированием и демультиплексированием
трафика.
В коммуникационных системах должны реализовываться две
функции: пространственная и временная коммутация.
45
Коммутаторы
с общей
памятью (тип 1)
Матричные
структуры
с пространственным
разделением (тип 3)
с общей
средой (тип 2)
Баньяновидного
типа
Буферизированные
структуры
с N2-раздельными
соединениями
Структуры
Бэтчера
Рис. 4.1. Классификация коммуникационного оборудования
В вычислительных сетях часто нет концепции заранее установленного временного интервала, поэтому при одновременном действии двух или нескольких логических каналов в течение одного временного интервала возникает ситуация соревнования. Она
разрешается за счет организации очередей пакетов. Коммутаторы
должны обладать способностью организации и ведения очередей.
При пространственной коммутации могут возникнуть блокировки,
приводящие к потере пакетов.
Основными характеристиками коммутаторов являются: пропускная способность, временные задержки, динамический разброс
временных задержек, вероятность потери пакетов из-за переполнения буферных устройств.
Все коммутаторы делятся на три типа (рис. 4.1): с общей памятью, с общей средой, с пространственным разделением.
4.2. Коммутаторы с общей памятью
В коммутаторе с общей памятью (рис. 4.2) все входные и выходные контроллеры непосредственно соединены с общей памятью, которая является доступной для записи пакетов со всех входных контроллеров и для их чтения. При этом должны выполняться два основных требования. Во-первых, время, необходимое процессору
для того, чтобы определить, в какую очередь поставить поступивший пакет, должно быть достаточно мало, чтобы процессор успевал
справиться с интенсивным потоком поступающих данных.Поэтому
в коммуникационной системе должен быть специальный процессор, способный в течение временного цикла обрабатывать последо46
1
Входной
контроллер
Выходной
контроллер
1
Выходной
контроллер
N
Память
N
Входной
контроллер
Рис. 4.2. Базовая структура коммутатора с общей паматью
вательно N входных пакетов и выбирать N пакетов для последующей передачи. Скорость записи и считывания должна быть достаточно велика, чтобы в течение временного цикла обслужить полностью входной и выходной трафики.
Необходимая скорость записи/считывания может быть определена следующим образом. Если число портов равно N, а скорость обмена через порт равна V, то скорость записи/считывания равна 2NV.
Например, для сетей АТМ для 32-канального коммутатора со скоростью канала V = 155 Мбит/с скорость записи/считывания должна
быть 2 · 32 · 155 Мбит/c = 9920 Мбит/c = 9,92 Гбит/c.
4.3. Коммутаторы с общей средой
В коммутаторах с общей средой (рис. 4.3) пакеты, поступающие
по входным каналам, мультиплексируются в общую среду с высокой скоростью передачи. В качестве такой среды могут выступать общая (разделенная во времени) шина или кольцевая структура. При этом приняты следующие обозначения: АФ – адресный
фильтр; Пс/Пр – преобразователь последовательный/параллельный; Пр/Пc – преобразователь параллельный/последовательный.
Если в качестве общей среды используется параллельная шина,
то ее скорость передачи должна быть в N раз больше, чем скорость
Вход 1
Вход N
Пс/Пр
АФ
Буфер
FIFO
Пр/Пс
Пс/Пр
АФ
Буфер
FIFO
Пр/Пс
Выход 1
Выход N
Рис. 4.3. Базовая конфигурация коммутатора с общей шиной
47
передачи по одному входу. Каждый выходной канал присоединен
к общей шине через интерфейс, содержащий адресный фильтр и
выходной буфер типа FIFO. Адресный фильтр в каждом интерфейсном блоке определяет, следует ли записывать пакет в буфер в зависимости от значений адреса получателя.
Коммутаторы с общей средой и с коллективной памятью осуществляют мультиплексирование всех поступающих пакетов в один
общий поток и в дальнейшем производят демультиплексирование
общего потока пакетов на отдельные потоки пакетов по одному на
каждый выход. Демультиплексирование производится адресными
фильтрами. В данной структуре наблюдается полностью раздельное использование памяти выходами коммутатора.
В качестве блоков буферной памяти используется память типа
FIFO.
4.4. Коммутаторы с пространственным разделением
В коммутаторах этого типа (рис. 4.4) может быть установлено несколько соединений от входов к выходам. При этом скорость передачи по каждому соединению может быть равна скорости передачи
по каждому каналу.
Коммутаторы с пространственным разделением могут быть разбиты на три группы: матричные, баньяновидные (древовидные),
с N2-раздельными соединениями.
Базовая модель коммутатора с пространственным разделением
(см. рис. 4.4) имеет N входов и N выходов, N разветвителей (демультиплексоров) по одному на каждом входе, N2 буферов и N концентраторов (мультиплексоров) по одному на каждый выход.
На каждом входе коммутатора имеется разветвитель (демультиплексор), который направляет пакет в N разных буферов (по одному
на каждый выходной порт). Каждая выходная линия подключена
к концентратору (мультиплексору), который подключает все N буферов к выходной линии.
Матричные (перекрестные) коммуникационные структуры
Матричная коммуникационная структура содержит массив
из переключателей по одному на каждую пару «вход – выход»
(рис. 4.5, а).
Каждый переключатель может находиться в сквозном или перекрестном состоянии (рис. 4.5, б). В сквозном состоянии ключа горизонтальный вход соединяется с горизонтальным выходом, а вер48
Концентраторы
Буферы
Разветвители
1
1
1
1
N
Входные
каналы
1
N
1
N
N
N
Выходные
каналы
N
Рис. 4.4. Базовая модель коммутатора с пространственным разделением
а)
1
2
N
б)
Входной
контроллер
Входной
контроллер
Входной
контроллер
Выходной
контроллер
Выходной
контроллер
Выходной
контроллер
1
2
N
Вертикальный вход
Горизонтальный
вход
Горизонтальный
выход
Перекрестное
состояние
Сквозное
состояние
Рис. 4.5. Коммутатор матричного типа:
а – коммуникационная структура; б – состояния переключателей (ключей)
49
тикальный вход – с вертикальным выходом. В перекрестном состоянии ключа горизонтальный вход соединяется с вертикальным
выходом, а вертикальный вход с горизонтальным выходом. Если
ключ, находящийся в i-й cтроке и j-м столбце, находится в перекрестном состоянии, то происходит соединение i-го входа коммутатора с j-м выходом.
Требуемые переключения ключей в перекрестное состояние могут осуществляться каждым пакетом, если в нем содержится номер
требуемого выходного порта. При этом не требуется дополнительной информации относительно всех других поступающих пакетов и
требуемых ими выходных портов. Таким образом, данная коммуникационная структура обладает свойством самомаршрутизации. Однако, если в одном временном интервале на входные порты поступают несколько пакетов и все они должны быть направлены к одному
выходу, то только один пакет будет направлен к необходимому выходу, а остальные пакеты могут быть утеряны или сохранены, если
они будут занесены в специальные буферные устройства. В последнем случае пакеты будут передаваться на необходимый выход, но
в других временных интервалах. Буферные устройства могут быть
расположены в узлах матрицы или на входах коммутатора.
Коммутаторы баньяновидного (древовидного) типа
Реализация разветвителей и концентраторов происходит с помощью элементарных (2×2) переключателей, которые могут находиться в одном из двух состояний: сквозном или перекрестном. Разветвитель на 2k выходов может быть построен в виде двоичного дерева
с k разветвлениями с помощью (N – 1) элементарных (2×2) переключателей. На рис. 4.6 представлен разветвитель на восемь выходов
с тремя разветвлениями и возможное положение переключателей
(ключей).
Разветвитель на N = 2k выходов может быть построен в виде двоичного дерева c k разветвлениями на (N – 1) двоичном коммуникационном элементе. В каждом таком дереве имеется единственный
путь от корня дерева (входа) до каждого из листьев (выходов). Такой
разветвитель обладает свойством самосинхронизации. Концентратор имеет такую же структуру, но в качестве корня выступает выходной канал.
В таком многокаскадном коммутаторе требуемое число переключателей равно 2N 2 − N, т. е. примерно в два раза больше, чем в коммутаторе матричного типа. При этом требуется N2 промежуточных
буферов и N 2 соединений между разветвителем и концентратором.
50
1
2
000
001
3 010
4 011
Сквозное
состояние
5
6
100
101
7
8
110
111
Перекрестное
состояние
Рис. 4.6. Разветвитель на восемь выходов
с тремя разветвлениями и состояния переключателей
1
1
2
5
3
3
4
7
5
2
6
6
7
4
8
8
Рис. 4.7. Многокаскадная структура
для соединения восьми входов с восемью выходами
Путем добавления пар входных каналов можно соединить между
собой N входов и N выходов, используя только (N / 2)log2 N элементарных двоичных переключателей (рис. 4.7).
При этом в коммутаторах подобного вида наблюдается сокращение количества переключателей по сравнению с другими схемами
51
их построения, но имеется возможность возникновения внутренних конфликтов (блокировок). Данное явление имеет место в тех
случаях, когда на переключатель поступают два пакета, которые
должны быть направлены на один выход, или пакеты не предназначены для одного и того же выхода. Существует большое разнообразие многокаскадных структур.Независимо от конкретной реализации все многокаскадные структуры, имеющие N входов и N выходов, обладают следующими свойствами:
– имеют единственный путь от входного канала к выходному;
– коммутаторы с большим числом входов и выходов на основе
БИС (установление соединения может быть выполнено децентрализованно с помощью процедуры самомаршрутизации);
– возможно одновременное установление не более N соединений;
– структура соединений является регулярной и модульной, что
позволяет строить коммутаторы с большим числом входов и выходов на основе БИС.
Основными способами преодоления внутренних блокировок и
повышения пропускной способности является размещение буферной памяти в местах возможного возникновения блокировок. На
этом принципе строятся буферизованные структуры баньяновидного типа.
Баньяновидная коммуникационная структура Бэтчера содержит ряд дополнительных устройств, с помощью которых разрешаются внутренные конфликты и конфликты на выходе (рис. 4.8).
В баньяновидной коммуникационной структуре Бэтчера пакеты
сначала поступают в так называемый сортировщик.В нем они расставляются в соответствии со своими адресами. При их направлении в коммуникационную сеть с самомаршрутизацией внутренних
конфликтов не должно быть, но могут быть конфликты между паке-
N
Сортировщик
N+M
Сетьловушка
N+M
Концентратор
N
Коммуникационная
сеть типа баньян
Рециркулятор с разделяемой памятью
Рис. 4.8. Баньяновидная коммуникационная структура Бэтчера
52
тами, если они направляются на один и тот же выход. Для преодоления выходных конфликтов сортировщик дополняется специальным устройством (ловушкой), которое распознает в пакетах запрос
одного и того же порта на выходе сортировщика путем сравнения
адресов и во всех кратных адресных запросах оставляет лишь первые пакеты, а остальные пакеты через цепь обратной связи (рециркулятор) вновь поступают на вход сортировщика для дальнейшего
поступления в коммуникационную сеть.
Коммутаторы с пространственным разделением
(количество соединений N2)
В коммутаторах этого типа предусматривается наличие физического ресурса, позволяющего установить N2 раздельных соединений между входами и выходами и тем самым достичь выходной
буферизации. Классическим примером может служить шинноматричная архитектура, рассмотренная выше. Другим примером
может служить так называемый нокаутный коммутатор, структура
которого приведена на рис. 4.9.
Здесь используются N входных шин с множественным доступом,
N выходных шин с множественным доступом, N2 матричных буферных запоминающих устройств, в каждом из которых находится адресный фильтр, соответствующий выходной линии. В данном
случае разветвитель для входной линии содержит входную шину и
N адресных фильтров, подсоединенных к ней (на рис. 4.9 эти фильтры находятся в N выходных интерфейсах). Таким образом, в каждом выходном интерфейсе находится N адресных фильтров. В качестве выходного концентратора выступает соответствующая шина
с множественным доступом. Каждый порт передает свои пакеты на
широковещательную шину, к которой подключены все выходные
1
2
Входы
N
Выходные
интерфейсы
1
2
Выходы
N
Рис. 4.9. Структура нокаутного коммутатора
53
порты. Каждый выходной канал снабжен шинным интерфейсом,
соединяющим его со всеми входными шинами, каждый такой интерфейс содержит N адресных фильтров, которые обнаруживают
пакеты, адресованные соответствующим выходным портам. При N
параллельно работающих фильтрах выходной интерфейс способен
принять N пакетов в одном временном интервале, поэтому входная
полоса пропускания (суммарная скорость) равна NV, где V – скорость передачи по одному входу.
Выходы фильтров подсоединены к NL-концентратору, который
выбирает до L пакетов из числа принятых фильтрами. Если одному
и тому же выходному каналу в данном интервале времени (цикле)
предназначено L пакетов, то в буфер заносится только L пакетов,
а остальные пакеты теряются. Это аналогично принципу «нокаута»
в олимпийской системе (из N претендентов в следующий круг выходит только L претендентов).
ЗАКЛЮЧЕНИЕ
Новые информационные технологии и оптоволоконная техника
позволили передавать по локальным и глобальным вычислительным сетям разнородный поток информации от различных источников с большими скоростями в реальном масштабе времени с высоким качеством. При этом высокие требования предъявляются
к системам маршрутизации и коммутации. Появляются новые алгоритмы поиска кратчайших путей для различных новых видов информации и методы коммутации, обеспечивающие передачу больших массивов данных, а также распределения их по множественным путям с целью сокращения времени доставки.
54
Библиографический список
1. Коммуникационные системы и сети: учеб. пособие. В 3-х томах.
Том 3. – Мультисервисные сети / В. В. Величко, Е. А. Субботин, В. П. Шувалов, А. Ф. Ярославцев; под ред. проф. В. П. Шувалова. М.: Горячая линия-Телеком, 2005. – 592 c.
2. Лазарев В. Г. Интеллектуальные цифровые сети: справочник / под
ред. Н. А. Кузнецова. М.: Финансы и статистика, 1996. 224с.
3. Смирнов А. В., Пескин А. Е. Цифровое телевидение: от теории к практике. М.: Горячая линия-Телеком, 2005. 352 c.
4. Олифер В. Г., Олифер Н. А. Компьютерные сети. Принципы, технологии, протоколы. СПб.: Питер, 2006. 672 с.
5. Сети Gigabit Ethernet // Bite, Россия. 1998. № 1. С. 57–63.
Содержание
Перечень условных обозначений и сокращений......................... Предисловие........................................................................ 1. Основные методы маршрутизации....................................... 1.1. Основные методы маршрутизации
в стеке протоколов TCP/IP.......................................... 1.2. Протокол OSPF.......................................................... 2. Методы маршрутизации в высокоскоростных
и интегрированных вычислительных сетях.............................. 2.1. Определение кратчайших путей
по матричному методу и методу Флойда........................ 2.2. Метод рельефов.......................................................... 2.3. Способы маршрутизации в АТМ-сетях........................... 2.4. Управление в АТМ-сетях............................................. 3. Повышение производительности
в вычислительных сетях........................................................ 3.1. Множественные маршруты в протоколе OSPF................. 3.2. Метод отклонений потока............................................ 4. Методы коммутации в вычислительных сетях....................... 4.1. Принципы работы коммунаторов.................................. 4.2. Коммутаторы с общей памятью.................................... 4.3. Коммутаторы с общей средой. ...................................... 4.4. Коммутаторы с пространственным разделением.............. Заключение......................................................................... Библиографический список.................................................... 3
4
5
5
8
11
11
18
23
28
33
33
34
44
44
46
47
48
54
55
55
Учебное издание
Крылов Юрий Дмитриевич
МЕТОДЫ МАРШРУТИЗАЦИИ И КОММУТАЦИИ
В ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ
Учебное пособие
Редактор Л. Я. Яковлева
Компьютерная верстка Н. Н. Караваевой
Сдано в набор 09.09.15. Подписано к печати 20.10.15.
Формат 60×84 1/16. Бумага офсетная. Усл. печ. л. 3,25.
Уч.-изд. л. 3,5. Тираж 100 экз. Заказ № 395.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
56
Документ
Категория
Без категории
Просмотров
1
Размер файла
2 842 Кб
Теги
krylov
1/--страниц
Пожаловаться на содержимое документа