Коммутация в сетях с использованием асинхронного метода переноса и доставки (стр. 9 из 17)

2. Бит конфликтов с: указывающий, отклонялась ячейка в предыдущих каскадах данной сети (с=1) или нет (с=0).

3. Приоритетно поле Р: оно является факультативным и используется при наличии в коммутаторе большого числа приоритетов.

4. Адресное поле D: содержащее адреса назначений d₁, d₂,...d_n n=(log₂N).

Состояние коммутационного элемента в каскаде s сети с автоблокировкой первоначально определяется тремя битами в заголовке двух вводимых ячеек, а именно а, с, d_s. При большом количестве приоритетов используется так же поле Р. В следующем алгоритме биты, обозначенные 1 и 2, соответствуют двум вводным ячейкам.

1. Если а₁=a₂=0, ничего не предпринимайте.

2. Если а₁=1, a a₂=0, установите коммутатор в соответствии с ds₁

3. Если а₁=0, а₂=1, установите коммутатор в соответствии с ds₂

4. а₁=а₂=1, тогда

а) если c₁=c₂=1, ничего не предпринимайте

б) если c₁=0, а c₂=1, установите коммутатор в соответствии с ds₁

c) если c₁=1, а c₂=0, установите коммутатор в соответствии с ds₂

d) если c₁=c₂= 0, тогда:

I. если P₁>P₂, то установите коммутатор в соответствии с ds₁

II. если P₁<Р₂, то установите коммутатор в соответствии с ds₂

III.если Р₁=Р₂, то установите коммутатор в соответствии с ds₁

или ds₂.

Чтобы уменьшить число буферизуемых на каждом каскаде битов при выполнении этого алгоритма и сократить задержку, адрес бита помещается в исходное положение адресного поля. Для этого нужно циклически сдвигать адресное поле на один бит в каждом каскаде. Таким образом, можно сократить задержку до времени, соответствующего прохождению 3-х бит, в каждом каскаде, без учета поддержки множественного приоритета и сохранять ее постоянной.С конфликтным битом легко отличить ячейки, отклонившиеся от маршрута и ячейки с верным маршрутом на выходе каждой сети с автоблокировкой: если с=0, значит ячейка трассировалась верно, а если с=1, значит эта ячейка отклонилась. Ячейка с c=0 буферизуется и не принимается следующей сетью с автоблокировкой. Ее бит активности становится равным 0. Ячейка с с=1 не буферизуется на выходе, но принимается следующей сетью с автоблокировкой, и ее конфликтный бит становится = 0 для дальнейшей маршрутизации.

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

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

3.5.2 КОММУТАЦИОННАЯ СИСТЕМА С ПЕРЕСТАНОВКОЙ И МАРШРУТИЗАЦИЕЙ С ОТКЛОНЕНИЕМ

Рассмотрим N´N коммутационную систему с перестановкой (SN) с n=log₂N каскадами, каждый из которых состоит из N/2 2´2 коммутационных элементов. На рисунки 3.15 представлена коммутационная система с перестановкой 8´8 [19,20].

Рисунок 3.15 - Коммутационная система с перестановкой 8´8

Коммутационные узлы на каждом каскаде отмечены сверху вниз двоичным числом в (n-1) бит. Верхний ввод/вывод узла отмечен 0, а нижний - 1. Ячейка будет направлена в вывод 0 (1) в каскаде i, если i наиболее значительный бит адреса ее назначения =0 (1). Взаимосвязь между 0 двумя, следующими друг за другом каскадами называется перестановкой. Вывод am узла X=(a1, a2...an-1) соединен со вводом а1 узла Y=(a2, а3......аn) следующего каскада. Связь между узлами X и Y обозначена <an, а1>.

Канал от ввода к выводу, по которому трассируется ячейка определяется ее адресом источника S=sl...sn и адресом ее назначения D=d1...dn, что символически выражается так [19,20]:

Последовательность узлов на канале выражается двоичной цепью s₂...s_n, d₁...d_n-1, представленной (n-1) разрядным окном, сдвигающимся на один бит слева направо в каждом каскаде. Трассировку ячейки по SN можно обозначить парой (R,X), где R - текущая трассировка, а X - узел постоянного хранения ячейки. В первом каскаде ячейка находится в состоянии (d_n...d₁, s₂...s_n) Состояние передачи определяется алгоритмом самотрассировки так [19,20]:

Заметьте что в конце каждого каскада трассировочный бит удаляется. Наконец, из состояния.... ячейка будет коммутирована следующим 2´2 элементом по назначению.

При конфликте в узле, только одна ячейка будет трассирована верно, а все остальные не попадут к нужным выходам. Отклонившаяся ячейка может начать трассировку вновь (с трассировочным ярлыком в исходном состоянии d_n...d₁) с того места, где произошло отклонение. Поэтому, если расширить SN систему так, чтобы она включала более n каскадов, то отклонившиеся ячейки могут достигнуть своего вывода на последующих каскадах. Т.к. некоторые ячейки достигнут своего вывода позже других на несколько каскадов, необходим мультиплексор для сбора ячеек, достигающих физических каналов одного и того же логического адреса на разных каскадах. В итоге, ячейка попадет по адресу своего назначения, при условии, что число L каскадов достаточно велико. Если она не находит своего вывода и на последнем из L каскадов, она считается потерянной.

3.5.3 ДВОЙНАЯ СИСТЕМА С ПЕРЕСТАНОВКОЙ И ИСПРАВЛЕНИЕ ОШИБОК МАРШРУТИЗАЦИИ

SN система с исправлением ошибок очень эффективна, особенно при большом значении п. Так как, при каждом отклонении ячейки, ее трассировка должна начинаться снова [20]. Рассмотрим диаграмму состояний на рисунке 3.16.

Рисунок 3.16 - Фазовая диаграмма ячейки в SN сети

Состояние (положение) - это расстояние или число каскадов до вывода. Требуемая сеть должна быть такой, как показано на рис. 3.17, в которой штраф - это возврат только на один каскад [18,14].

Рисунок 3.17 - Фазовая диаграмма со штрафным состоянием

На рисунке 3.18 изображена коммутационная система 8x8 без перестановки (USN). Она является зеркальным отражением системы SN. Трассировка через последовательность каскадов основана на принципе наименее значимый бит через наиболее значимый бит

Рисунок 3.18 - Коммутационная система без перестановки с пятью Каскадами

Пользуясь той же схемой вычислений, как в случае с SN, канал ячейки с адресом источника S=s₁...s_n и адресом назначения D=d₁...d_n может быть выражен так[18,14]:

(n-1) разрядное окно, перемещающееся по двоичной цепи d₂...d_n, s₁...s_n-1 на один бит каждый каскад справа на лево, представляет последовательность узлов на канале трассировки.

Первоначальное состояние ячейки (d₁...d_n, s₁...s_n-1) и состояние перехода дано как:

На последнем каскаде ячейка находится в состоянии (-d₁d₂...d_n) и достигает назначения [18].

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

Рисунок 3.19 - Исправление ошибок в сетях SN с помощью USN

Рисунок 3.20

На рисунке 3.20 ячейка А поступает в SN из входа 010 и выходит из вывода 101, ячейка В поступает во ввод 100 и выходит через вывод 100. Во втором каскаде они сталкиваются, когда обе прибывают в узел 01 и делают запрос выводу 0. Допустим, что ячейка В выигрывает, а ячейка А отклоняется и попадает в 11 узел третьего каскада. Допустим, что ячейка А попадает в аналогичный 11 узел в USN и коммутируется в вывод 0. Затем она возвращается в узел 01, тот самый узел, где произошла ошибка в двух каскадах. В этом месте ошибка отклонения была исправлена и ячейка А продолжила свой путь по нужному каналу в SN. Любая ошибка трассировки исправляется в SN обратной операцией трассировки в USN. Более точно этот процесс можно сформулировать так. Рассмотрим ячейку в состоянии (r₁…r_k, x₁…x_n-1) Ячейка должна быть трассирована в канал <r_k, x₁> в SN. Положим, она отклонилась, вместо того, чтобы попасть в канал <r_k, x₁> ячейка достигает узла (x₂.....х_n-1r_k) в следующем каскаде. Исправление ошибки трассировки начинается с присоединения бита x₁ к ярлыку трассировки, вместо перемещения бита r_k, таким образом, состояние ячейки в следующем каскаде будет x₁. Затем ячейка перемещается в аналогичный узел в USN для исправления ошибки. В случае успешной трассировки, она будет направлена в канал r_k и вернется в предыдущее состояние (r₁…r_k x₁, x₂…x_n-1 r_k). Taким же образом, ошибка, происходящая в USN исправляется с помощью SN за один шаг. Т.е. ячейка в SN может отклониться в канал USN и наоборот [14,20].