kryl_vych_seti

rNi = min (rN ,i1,..., rN ,1, rN ,m ,..., rN ,in )+1.

Эти элементы образуют вектор

Ri (r1i ,...,rji ,...,rNi ).

После того как вектор Ri полностью вычислен управляющим устройством, УКi передает его в УУ всех соседних УК (рис. 5.7, a). При этом он записывается в ЗУ этих УК в качестве столбцов матрицы рельефов (см. рис. 5.7, б). Точно такие же операции выполняют управляющие устройства всех остальных УК.

Если в ветви, например βi,m, отсутствуют каналы или она повреждена, то при вычислении элемента Rei , e =1,..., N принимаем rε,m = ∞.

111

6. МЕТОДЫ КОММУТАЦИИ В ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ

6.1. Принципы работы коммутаторов

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

Коммутация в современных вычислительных сетях, например сетях АТМ, требует выбора необходимого логического канала из множества исходящих логических каналов в каждом коммутаторе сети. При этом логический канал в коммутаторах сетей АТМ характеризуется физическим входом или выходом, определяемым номером физического порта и логическим каналом физического порта, который определяется идентификатором виртуального пути (VPI) и идентификатором виртуального канала (VCI).

Вкоммуникационных системах должны реализовываться две функции: пространственная и временная коммутация.

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

112

Основными характеристиками коммутаторов являются: пропускная способность; временные задержки;

динамический разброс временных задержек; вероятность потери пакетов из-за переполнения буферных устройств. Все коммутаторы делятся на три типа (рис. 6.1):

c общей (коллективной) памятью; c общей средой;

c пространственным разделением.

Коммутаторы

С общей

С общей средой

С пространственным

памятью

разделением

Матричные

Баньяновидного

С N2 раздельными

структуры

(древовидного) типа

соединениями

Буферизованные

Структуры

структуры

Бэтчера

Рис. 6.1. Классификация коммуникационного оборудования

6.2. Коммутаторы с общей памятью

Структура коммутаторов этого типа изображена на рис. 6.2.

	Входной				Входной	1
1	контроллер				контроллер
			Память
N	Выходной				Входной
	контроллер				контроллер	N

Рис. 6.2. Базовая структура коммутатора с общей памятью

113

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

Необходимая скорость записи/считывания может быть определена следующим образом. Если число портов равно N, а скорость обмена через порт равна V, то скорость записи/считывания равна 2NV. Например, для сетей АТМ для 32-канального коммутатора со скорость канала V = 155 Мбит/с скорость записи считывания должна быть 2 × 32 ×

×155 Мбит/с = 10320 Мбит/с = 10,2 Гбит/с.

6.3.Коммутаторы с общей средой

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

	Вход 1			Выход 1
	Пс/Пр		Буфер
		АФ		Пр/Пс
			FIFO
	Вход 2		Буфер	Выход 2
	Пс/Пр	АФ		Пр/Пс
			FIFO

	Вход N	АФ	Буфер	Выход N
	Пс/Пр			Пр/Пс
			FIFO

Рис. 6.3. Базовая структура коммутатора с общей шиной

114

На рис. 6.3 приняты следующие обозначения: АФ – адресный фильтр;

Пс/Пр – преобразователь последовательный/параллельный; Пр/Пс – преобразователь параллельный/последовательный.

Если в качестве общей среды используется параллельная шина, то ее скорость передачи должна быть в N раз больше, чем скорость передачи по одному входу. Каждый выходной канал присоединен к общей шине через интерфейс, содержащий адресный фильтр и выходной буфер типа FIFO.

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

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

6.4.Коммутаторы с пространственным разделением

Вкоммутаторах этого типа может быть установлено несколько соединений от входов к выходам. При этом скорость передачи по каждому соединению может быть равна скорости передачи по одному каналу.

Коммутаторы с пространственным разделением могут быть разбиты на три группы:

матричные; баньяновидные (древовидные);

с N 2 раздельными соединениями.

Базовая модель коммутатора с пространственным разделением (рис. 6.4) имеет N входов и N выходов, N разветвителей (демультиплексоров) по одному на каждом входе, N2 буферов и N концентраторов (мультиплексоров) по одному на каждый выход.

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

115

тратору (мультиплексору, который подключает все N буферов к выходнойлинии).

Разветвители

Буферы

Концентраторы

1

1

1

N

1

Входные

1

N1

Выходные

каналы

каналы

N

N

N

Рис. 6.4. Базовая модель коммутатора с пространственным разделением

Матричные (перекрестные) коммуникационные структуры

Матричная коммуникационная структура содержит массив из переключателей по одному на каждую пару ''вход–выход" (рис. 6.5, а).

Каждый переключатель может находиться в сквозном или перекрестном состоянии (рис. 6.5, б). В сквозном состоянии ключа горизонтальный вход соединяется с горизонтальным выходом, а вертикальный вход с вертикальным выходом. В перекрестном состоянии ключа горизонтальный вход соединяется с вертикальным выходом, а вертикальный вход с горизонтальным выходом. Если ключ, находящийся в i-й строке и j-м столбце, находится в перекрестном состоянии, то происходит соединение i-го входа коммутатора с j-м выходом.

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

116

а)

1

Входной

контроллер

2

Входной

контроллер

N

Входной

контроллер

Выходной

Выходной

Выходной

контроллер

контроллер

контроллер

1

2

N

Вертикальный вход

Выходы

б)

Горизонталь-

Горизонталь-

ный вход

ный выход

Вертикальный выход

Перекрестное Сквозное состояние состояние

Рис. 6.5. Коммутатор матричного типа: а – коммуникационная структура; б – состояния переключателей (ключей)

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

Коммутаторы баньяновидного (древовидного) типа

Рассмотрим реализацию разветвителей и концентроторов с помощью элементарных (2 × 2) переключателей, которые могут находится в од-

117

ном из двух состояний : сквозном и перекрестном. Разветвитель на N = 2k выходов может быть построен в виде двоичного дерева с k разветвлениями с помощью (N–1) элементарных (2 × 2) переключателей.

На рис. 6.6 изображен разветвитель на восемь выходов с тремя разветвлениями и возможное положение переключателей (ключей).

		1	000
		2	001
			010
		3
		4	011
			100
		5
		6	101
			110
		7
		8	111

Сквозное состояние

Перекрестное состояние

Рис. 6.6. Разветвитель на восемь выходов с тремя разветвлениями и состояния переключателей

Разветвитель на N = 2k выходов может быть построен в виде двоичного дерева с k разветвлениями на (N–1) двоичном коммуникационном элементе . В каждом таком дереве имеется единственный путь от корня дерева (входа) до каждого из листьев (выходов). Такой разветвитель обладает свойством самомаршрутизации.

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

118

В таком многокаскадном коммутаторе требуемое число переключателей равно 2N2 – N, т. е. примерно в два раза больше, чем в коммутаторе матричного типа. При этом требуется N2 промежуточных буферов и N2 соединений между разветвителем и концентратором. Путем добавления пар входных каналов можно соединить между собой N входов и N выходов, используя только (N/2) × log2 N элементарных двоичных переключателей (рис. 6.7).

1						1
2						5
3						3
4						7
5							2
6						6
7						4
8							8

Рис. 6.7. Многокаскадная структура для соединения восьми входов с восьмью выходами

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

Существует большое разнообразие многокаскадных структур. Независимо от конкретной реализации все многокаскадные структуры , имеющие N входов и N выходов, обладают следующими свойствами:

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

но с помощью процедуры самомаршрутизации;

возможно одновременное установление не более N соединений; структура соединений является регулярной и модульной, что позво-

ляет строить коммутаторы с большим числом входов и выходов на основе БИС.

119

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

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

Рециркулятор с разделяемой очередью

		Сорти-		Сеть-		Концен-		Коммуника-
		ровщик	N+M	ловушка	N+M	тратор
	N						N	ционная сеть
								типа баньян

Рис. 6.8. Баньяновидная коммуникационная структура Бэтчера

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

Коммутаторы с пространственным разделением

сN 2 раздельными соединениями

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

120