Коммутация в сетях с использованием асинхронного метода переноса и доставки 
исунок 3.11 - Схема реализации кольцевого резервированияв предыдущий временной интервал, то ячейка у входа 2 не может быть отправлена. В пятый и шестой промежутки времени ячейки у вводов 3 и 4 так же не могут быть отправлены к выводам 1 и 3 соответственно, т.к. уже были зарезервированы в предыдущий временной интервал. В итоге ячейки у входных проверенных портов оказываются в конфликтной ситуации. В данном примере арбитражный цикл может быть завершен за шесть временных интервалов, поскольку имеется шесть входных портов. В этой схеме используется серийный механизм, и в целом арбитражный цикл может состоять из N бит временных интервалов, где N обозначает число портов ввода и вывода коммутатора, что может стать критическим параметром при большом количестве портов. Однако, эта схема обеспечивает равноправие портов, произвольно устанавливая нужные значения счетчиков перед арбитражем. Эта схема может быть использована на вводах любой коммутационной системы.3.4 СОЛНЕЧНЫЙ КОММУТАТОРВ этом коммутаторе сочетается сортирующая Батчер сеть и параллельно-направляющая Баньян сеть. Таким образом, к каждому выводу подходит более одного канала. На рис. 3.12 дана блок-схема строения этого коммутатора [17,18,19]. Параллельная сеть маршрутизации с автоблокировкой k обеспечивает k отдельных трактов каждому выводу. Если более, чем k ячеек делают запрос на определенный вывод за один временной интервал, тогда часть ячеек отправляется в очередь общей рециркуляции и затем снова передаются в коммутационную систему к назначенным вводам. Очередь рециркуляции состоит из Т параллельных цепей и Т назначенных вводов в сортирующую сеть с накопителем. Каждая цепь рециркуляции может сохранять одну ячейку. В каждой цепи имеется блок задержки для выстраивания рециркулирующих ячеек с ячейками, прибывшими из контролирующих устройств вводныхРисунок 3.12 - Блок-схема солнечного коммутатораканалов (IPC) в следующий временной интервал. В течение каждого интервала сеть с накопителем сортирует новоприбывшие и рециркулирующие ячейки в порядке приоритета и адресов назначения. Это позволяет заграждающей сети, выбирая k ячейки высшего приоритета для каждого вывода, разрешать конфликты у выходных портов. Поскольку в устройстве существует k параллельных сетей с автоблокировкой, каждый вывод может принимать k ячеек каждый временной интервал. Если для одного вывода назначено больше, чем k ячеек, их излишек будет отправляться в очередь рециркуляции. Концентратор и селектор направляют лишние ячейки в цепи рециркуляции, а выбранные ячейки будут направлены в сети с автоблокировкой. Каждая ячейка проходит в контролер входного порта со служебным заголовком.В него входят два контрольных поля: поле трассировки и приоритетное поле (рисунок 3.13).Рисунок 3.13- Формат заголовкаОба упорядочиваются, начиная с наиболее значительного бита. В поле трассировки первый бит -бит активности ячейки, указывающий, содержит ли ячейка значимую информацию (А=1) или она пуста (А=0). Затем следует поле адресов назначения (DA), определяющее нужный выходной порт. Приоритетное поле состоит из индикатора качества и класса услуг передачи (QoS) и внутреннего приоритета коммутатора (SP). QoS поле различает ячейки услуг высшего приоритета и услуг низшего приоритета. К первым относится схемная эмуляция, а ко вторым услуги без установления связи. QoS поле следит за тем, чтобы в случае конфликта, ячейки высшего приоритета трассировались первыми. SP поле используется коммутатором для указания числа временных интервалов, в течение которых задерживалась ячейка. Оно также дает высший приоритет рециркулирующим ячейкам. Поэтому ячейки из данного источника трассируются последовательно.При сортировке ячейки распределяются в возрастающем порядке их адресов назначения. Приоритетное поле, в котором высшее численное значение соответствует высшему уровню приоритета, является продолжением поля трассировки. Это является причиной того, что ячейки, назначенные в один порт выхода, располагаются в убывающем порядке приоритета. В сети заграждения адреса ячеек сравниваются с адресом ячейки, находящейся на k позиций выше. Если они совпадают с адресом ячейки, стоящей на k позиций выше (а это значит, что имеется, по крайней мере, k ячеек высшего приоритета), они отмечаются и отправляются на рециркуляцию. Их поля трассировки заменяются приоритетными полями, т.к. последние важнее для последующей работы сортирующей системы и предотвращения потерь ячеек при рециркуляции. Если их адреса не совпадают, значит ячейка является одной из k ячеек высшего приоритета и может трассироваться.В концентрационных сетях с накопителем существует две группы ячеек: одна для трассировки, другая для рециркуляции. Обе группы сортируются в непрерывные списки. Чтобы предотвратить блокирование в сети с автоблокировкой, группа ячеек трассируется из списка в восходящем порядке адресов. Группы ячеек для циркуляции сортируются в отдельный список в порядке приоритета и адресов назначения. Если очередь рециркуляции переполняется, для ячеек, направленных в выводы с высокими номерами, больше вероятности быть удаленными, чем для ячеек, направленных в выводы с низкими номерами.Затем, ячейки направляются в селектор, который разделяет их на две группы и направляет их либо в k сеть с автоблокировкой, либо в Т рециркуляторы. Ячейки, попадающие в рециркулятор, изменяют поля приоритета и трассировки в первоначальный формат. После рециркуляции их приоритет (SP) повышается [14].Выводы селекторов распределены между k сетями с автоблокировкой, путем соединения k выводов с соответствующей сетью с автоблокировкой. Поэтому, если две ячейки назначены в один вывод, они будут направляться в разные сети с автоблокировкой. В каждой сети с автоблокировкой ячейки формируют непрерывные списки, направленные в определенные выводы, что обеспечивает деблокирование в сети с автоблокировкой. Каждая ячейка достигает нужного вывода в сети с автоблокировкой, и затем все соответствующие выводы группируются и образуют очередь в контролере выходного порта (ОРС).3.5 МАРШРУТИЗАЦИЯ С ОТКЛОНЕНИЕМ3.5.1 ТАНДЕМНЫЙ (СПАРЕННЫЙ) БАНЬЯН КОММУТАТОРНа рисунке 3.14 изображена тандемная коммутационная Баньян сеть (TBSF) [17].Рисунок 3.12 - Тандемная коммутационная Баньян сетьДанная сеть состоит из множества Баньян сетей. При конфликте ячеек в каком-либо узле системы, одна из них будет отклоняться в неверный вывод узла и придет по неверному адресу назначения в Баньян сети. Затем отклонившаяся ячейка передается в следующую Баньян сеть. Этот процесс повторяется до тех пор, пока ячейка не достигнет нужного вывода, или же пока она не выйдет в неверный вывод последней Баньян сети и, таким образом будет считаться потерянной. Каждый вывод Баньян сети соединен с соответствующим выходным буфером. Каждая отклонившаяся ячейка отмечается, чтобы ее можно было отличить от ячейки, идущей верно и не изменит ее маршрута в последующих каскадах сети. На выводах каждой Баньян сети, все ячейки, достигшие своего пункта назначения, извлекаются из коммутационной системы и буферизуются. Таким образом, нагрузка в последовательно соединенных Баньн сетях, а также вероятность конфликтов уменьшается. При достаточно большом числе таких последовательно соединенных сетей, можно уменьшить коэффициент потерь до желаемого. Численные результаты показывают, что каждая, добавленная к этой последовательности Баньян сеть, уменьшает вероятность потерь на один порядок величины. TBSF работает следующим образом. К каждой входящей в коммутационную систему ячейке прилагается коммутационный заголовок, содержащий 4 следующих поля:1. Бит активности а: указывающий, содержит ли область ячейку (я=1) или она пуста(я=0).2. Бит конфликтов с: указывающий, отклонялась ячейка в предыдущих каскадах данной сети (с=1) или нет (с=0).3. Приоритетно поле Р: оно является факультативным и используется при наличии в коммутаторе большого числа приоритетов.4. Адресное поле D: содержащее адреса назначений d1, d2,...dn n=(log2N).Состояние коммутационного элемента в каскаде s сети с автоблокировкой первоначально определяется тремя битами в заголовке двух вводимых ячеек, а именно а, с, ds. При большом количестве приоритетов используется так же поле Р. В следующем алгоритме биты, обозначенные 1 и 2, соответствуют двум вводным ячейкам.1. Если а1=a2=0, ничего не предпринимайте.2. Если а1=1, a a2=0, установите коммутатор в соответствии с ds13. Если а1=0, а2=1, установите коммутатор в соответствии с ds24. а1=а2=1, тогдаа) если c1=c2=1, ничего не предпринимайтеб) если c1=0, а c2=1, установите коммутатор в соответствии с ds1c) если c1=1, а c2=0, установите коммутатор в соответствии с ds2d) если c1=c2= 0, тогда:I. если P1>P2, то установите коммутатор в соответствии с ds1II. если P1<Р2, то установите коммутатор в соответствии с ds2III.если Р1=Р2, то установите коммутатор в соответствии с ds1или ds2.Чтобы уменьшить число буферизуемых на каждом каскаде битов при выполнении этого алгоритма и сократить задержку, адрес бита помещается в исходное положение адресного поля. Для этого нужно циклически сдвигать адресное поле на один бит в каждом каскаде. Таким образом, можно сократить задержку до времени, соответствующего прохождению 3-х бит, в каждом каскаде, без учета поддержки множественного приоритета и сохранять ее постоянной.С конфликтным битом легко отличить ячейки, отклонившиеся от маршрута и ячейки с верным маршрутом на выходе каждой сети с автоблокировкой: если с=0, значит ячейка трассировалась верно, а если с=1, значит эта ячейка отклонилась. Ячейка с c=0 буферизуется и не принимается следующей сетью с автоблокировкой. Ее бит активности становится равным 0. Ячейка с с=1 не буферизуется на выходе, но принимается следующей сетью с автоблокировкой, и ее конфликтный бит становится = 0 для дальнейшей маршрутизации.Все ячейки, поступающие в тандемный Баньян коммутатор за один временной интервал, синхронизируются по тактам через всю коммутационную систему. Если не учитывать задержки на распространение сигнала, то задержка каждой ячейки в сети постоянна и равна п задержкам на обработку в коммутационном элементе, что составляет временную разницу прибытия двух ячеек из соседних Баньян сетей. Для того, чтобы ячейки из разных сетей поступили в выходной буфер одновременно, между каждым выводом и Баньян сетью можно поместить соответствующий элемент задержки. Кроме того, память выходного буфера должна иметь выходную пропускную способность равную V бит/с и входную пропускную способность равную KV бит/с, для того чтобы принять все К ячейки, прибывающие за один временной интервал. 3.5.2 КОММУТАЦИОННАЯ СИСТЕМА С ПЕРЕСТАНОВКОЙ И МАРШРУТИЗАЦИЕЙ С ОТКЛОНЕНИЕМРассмотрим NN коммутационную систему с перестановкой (SN) с n=log2N каскадами, каждый из которых состоит из N/2 22 коммутационных элементов. На рисунки 3.15 представлена коммутационная система с перестановкой 88 [19,20].Рисунок 3.15 - Коммутационная система с перестановкой 88Коммутационные узлы на каждом каскаде отмечены сверху вниз двоичным числом в (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]:Последовательность узлов на канале выражается двоичной цепью s2...sn, d1...dn-1, представленной (n-1) разрядным окном, сдвигающимся на один бит слева направо в каждом каскаде. Трассировку ячейки по SN можно обозначить парой (R,X), где R - текущая трассировка, а X - узел постоянного хранения ячейки. В первом каскаде ячейка находится в состоянии (dn...d1, s2...sn) Состояние передачи определяется алгоритмом самотрассировки так [19,20]:Заметьте что в конце каждого каскада трассировочный бит удаляется. Наконец, из состояния.... ячейка будет коммутирована следующим 22 элементом по назначению.При конфликте в узле, только одна ячейка будет трассирована верно, а все остальные не попадут к нужным выходам. Отклонившаяся ячейка может начать трассировку вновь (с трассировочным ярлыком в исходном состоянии dn...d1) с того места, где произошло отклонение. Поэтому, если расширить 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=s1...sn и адресом назначения D=d1...dn может быть выражен так[18,14]:(n-1) разрядное окно, перемещающееся по двоичной цепи d2...dn, s1...sn-1 на один бит каждый каскад справа на лево, представляет последовательность узлов на канале трассировки.Первоначальное состояние ячейки (d1...dn, s1...sn-1) и состояние перехода дано как: На последнем каскаде ячейка находится в состоянии (-d1d2...dn) и достигает назначения [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. Более точно этот процесс можно сформулировать так. Рассмотрим ячейку в состоянии (r1…rk, x1…xn-1) Ячейка должна быть трассирована в канал <rk, x1> в SN. Положим, она отклонилась, вместо того, чтобы попасть в канал <rk, x1> ячейка достигает узла (x2.....хn-1rk) в следующем каскаде. Исправление ошибки трассировки начинается с присоединения бита x1 к ярлыку трассировки, вместо перемещения бита rk, таким образом, состояние ячейки в следующем каскаде будет x1. Затем ячейка перемещается в аналогичный узел в USN для исправления ошибки. В случае успешной трассировки, она будет направлена в канал rk и вернется в предыдущее состояние (r1…rk x1, x2…xn-1 rk). Taким же образом, ошибка, происходящая в USN исправляется с помощью SN за один шаг. Т.е. ячейка в SN может отклониться в канал USN и наоборот [14,20].Рисунок 3.21- Двойная коммутационная система 8x8 с перестановкой Это учитывается в следующем алгоритме. Сначала 22 аналогичных коммутационных элемента SN и USN объединяются и образуют 4x4 коммутационных элемента для того, чтобы можно было коммутировать ячейки между SN и USN. На рисунке 3.21 представлена двойная SN, образованная 44 коммутационными элементами. Используется новая схема маркирования. Четыре ввода/вывода коммутационного узла помечаются 00, 01, 10, 11 сверху вниз. Выходы 00 и 01 соединяются со следующим каскадом по примеру USN, а выводы 10 и 11 соединяются со следующим каскадом по примеру SN.Вводы 00 и 01 соединяются с предыдущим каскадом по SN образцу, а вводы 10 и 11 соединяются с предыдущим каскадом по образцу USN. Канал с меткой <la,0b> - это не тасующий канал, а канал с меткой <0a,1b> - тасующий. Два узла (a1, an-1) И (bi, bn-1) соединены не тасующим каналом, если <0b1, 1an-1> и они соединены тасующим каналом, если a1...an-2 = b2...bn-1 Так как каждый коммутационный узел имеет четыре вывода, то для определения требуемого вывода ячейки на каждом каскаде, необходимо два бита маршрутизации. Ячейка с назначением D=d1...dn может трассироваться как через USN, так и через SN. Соответственно, изначальный ярлык маршрутизации ячейки установлен на 0d1…0dn (USN) или на 1dn...1d1 (SN) Состояние ячейки в определенные временные интервалы обозначается (c1r1..ckrkx1…xn-1) Возможны две регулярные передачи в коммутационный узел. Ячейка будет отправлена в не тасующий канал, если ck=0 и в тасующий, если ck=1 [14,19].Соответственные состояния передачи выражаются:Ячейки с начальной трассировкой, установленной на 0d1…0dn (1dn …1d1) будут оставаться в каналах USN (SN) в течение всего процесса трассировки, пока он не завершится в одном из каналов USN(SN).Направление трассировки:1. Если вывод ckrk доступен и k=1, ячейка доходит по назначению. Выводим ячейку перед следующем перемешиванием, если с=1 и после следующей не тасовки, если с=0.2. Если вывод ckrk доступен и k>l, удаляем два наименее значимых бита из ярлыка трассировки и отправляем ячейку в следующий каскад.3. Если вывод ckrk недоступен и k<n выбираем любой другой доступный вывод, присоединяем к ярлыку трассировки два соответствующих бита для исправления ошибок и отправляем ячейку в следующий каскад.Если вывод ckrk недоступен и k=n устанавливаем исходное значение ярлыка трассировки 0d1…0dn (1dn …1d1), чтобы предотвратить рост длины ярлыка.На рисунке 3.22 представлен полный алгоритм для исправления ошибок [14].Рисунок 3.22 - Полный алгоритм исправления ошибок Для любого узла с меткой (x1...xn-1) ярлык исправления ошибок выводов 00 и 01 xn-1 и выводов 10 и 11 0х. В обоих случаях ярлык исправления ошибок - второй компонент в канальном ярлыке <cr, > где x=xc+c(n-1). Поэтому, ячейка, отклонившаяся в канал будет возвращена в предыдущее состояние через канал <cr, > в следующем каскаде (рисунок 3.23 [20].Рисунок 3.23- Пример исправления ошибок трассировки в DSN3.5.4 КОПИРУЮЩИЕ СИСТЕМЫ ДЛЯ МНОГОАДРЕСНОЙ ПЕРЕДАЧИНа рисунке 3.24 показана серийная комбинация копирующей сети и двухточечного коммутатора для обеспечения многоточечной связи. Копирующая система одновременно тиражирует ячейки из разных вводов и затем трассирует копии ячеек широкой рассылки по их назначению с помощью двухточечного коммутатора [12,14].Копирующая система состоит из следующих основных частей (рисунок 3.25) [14]:1. схема сумматора (RAN), генерирующая текущие суммы номеров копий, обозначенных в заголовках входящих ячеек.2. шифратор адресов (DAE), создающий новые заголовки ячеек из соседних текущих сумм.3. коммутационная широкополосная Баньян сеть (BBN), в которой коммутационные узлы широкой рассылки делают копии ячеек с заголовками в два бита.Рисунок 3.24 - Коммутатор многоадресной рассылки4. шифратор адресов (DAE), создающий новые заголовки ячеек из соседних текущих сумм.5. коммутационная широкополосная Баньян сеть (BBN), в которой коммутационные узлы широкой рассылки делают копии ячеек с заголовками в два бита.6. транслятор номеров каналов (TNT), определяющий номера выходных каналов для каждой копии ячейки.Рисунок 3.25 - Основные компоненты не блокирующей копирующей системы Механизм многоадресной передачи копирующей системы основан на передаче и преобразовании заголовков (рисунок 3.26). Номера копий (CN), указанные в заголовках ячеек рекурсивно суммируются в схеме сумматора. На основе полученных сумм шифраторы адресов создают новые заголовки ячеек с двумя полями: поле фиктивного адресного интервала и поле индексного эталона (IR). Поле адресного интервала образовано соседними текущими суммами, минимальными (MIN) и максимальными (МАХ). Индексный эталон приравнивается минимуму адресного интервала и впоследствии используется транслятором номеров каналов для определения индекса копии (СI).Широкополосная Баньян сеть копирует ячейки по алгоритму логического деления интервалов на основе адресного интервала в новом заголовке. Когда копия прибывает в нужный вывод, TNT вычисляет ее CI на основе адреса вывода и индексного эталона. Номер канала широкой рассылки (BCN) и CI образуют уникальный идентификатор, указывающий на номер канала (TN), который добавляется заголовку ячейки и используется для ее трассировки по назначению [14,20].Рисунок 3.26 - Трансляция заголовков в копирующей системе 4 ШИРОКОПОЛОСНАЯ БАНЬЯН СЕТЬ4.1 ОСНОВЫ ШИРОКОПОЛОСНАЯ БАНЬЯН СЕТЬ4.1.1 ОБОБЩЕННЫЙ АЛГОРИТМ САМОТРАССИРОВКИШирокополосная Баньян сеть - это сеть с коммутационными узлами, копирующими ячейки. Ячейка, прибывающая в каждый узел, может быть либо трассирована в один из выводных каналов, либо дублирована и отправлена по двум выводным каналам. Существует три варианта Log23=1.585, а это значит, что минимальный объем информации заголовка = 2 бит а каждый узел [1,10].На рисунке 4.1 представлен обобщенный алгоритм одно - битовой самотрассировки для ряда N-битных адресов с произвольным назначением. Когда ячейки прибывает в узел k-каскада, трассировка ячейки определяется k битами заголовков всех адресов назначения. Если все они равны 0 или 1, тогда ячейка отправляется в выводы 0 или 1 соответственно. В противном случае, копии ячеек отправляются в оба вывода, и соответственно копиям этих двух ячеек в заголовках изменяются адреса назначения: заголовки копий ячеек, отправленных в вывод 0 или 1, содержат адреса первоначальных заголовков в k бит, равных 1 или 0 соответственно.Рисунок 4.1 - Обобщенный алгоритм самомаршрутизации На рисунке 4.2 дерево ввода-вывода, образуемое обобщающим алгоритмом самомаршрутизации.Рисунок 4.2 - Дерево ввода-вывода, образуемое обобщающим алгоритмом самомаршутизацииПри выполнении обобщенного алгоритма самотрассировки могут возникнуть трудности [12,18].o заголовки ячеек содержат изменяющиеся адресные номера и коммутационным узлам приходится считывать их все.o при модификации заголовков ячеек учитывается вся совокупность адресов, что усложняет работу коммутационных узлов.o схема всех каналов выводов и вводов образует дерево в сети.Деревья, образованные произвольным рядом входных ячеек, зависят от каналов. Таким образом, из-за нерегулярности ряда абсолютных адресов назначения в заголовках ячеек, система является блокирующей. Но в копирующей системе, где ячейки копируются, но не отправляются по абсолютным адресам, вместо абсолютных адресов могут использоваться фиктивные.Фиктивные адреса каждой ячейки могут выстраиваться непрерывно, так чтобы весь ряд фиктивных адресов представлял интервал (адресный), состоящий из MIN и МАХ текущих сумм. Адресный интервал входных ячеек можно сделать монотонным для обеспечения деблокирования в нижеописанной широкополосной Баньян сети. 4.1.2 АЛГОРИТМ ЛОГИЧЕСКОГО ДЕЛЕНИЯ ИНТЕРВАЛОВАдресный интервал - это непрерывный ряд двоичных N-битных номеров, которые можно представить двумя номерами: минимальным и максимальным. Допустим, что узел в k каскаде получает ячейку, заголовок которой содержит адресный интервал, состоящий из двух бинарных номеров min(k-1)=m1...mN и max(k-1)=M1...MN, где k-1 обозначает каскад, из которого ячейка прибыла в k каскад. По обобщенному алгоритму самотрассировки маршрут ячейки определяется так (рисунок 4.3) [14]:1. если mk=Мk=0 или mk=Мk=1, тогда отправьте ячейку в выводы 0 или 1 соответственно.2. Если mk=0 и Мk=1, тогда копируйте ячейку, модифицируйте заголовки обеих копий (по ниже данной схеме) и отправьте копии в соответствующий канал.Рисунок 4.3 - Логическая схема коммутационного узла в k каскаде широкополосной Баньян сетиМодификация заголовка ячейки заключается в делении исходного адресного интервала на два подинтервала, что выражается в следующей рекурсии: для ячейки, отправленной в канал 0min(k)=min (k-1)=sm1...mN,max(k)=M1.....Mk-101....1,И для ячейки, отправленной в канал 1min(k)=m1....mk-1 10....0,max(k)=max(k-1)=M1.....МNНа рисунке 4.4 (а) представлена схема алгоритма логического деления интервалов. Из правил ясно, что mi=Mi, i=1...k-1 действительно для каждой прибывающей в каскад k ячейки. Событие mk=1 и Mk=0 исключено.Рисунок 4.4 (а) - Схема алгоритма логического деления интерваловНа рисунке 4.4 (b) представлено дерево, которое образуется при копировании ячеек в соответствии с их адресными интервалами [12,14].Рисунок 4.4 (b) - Дерево, образованное при копировании ячеек в соответствии с их адресными интервалами 4.1.3 УСЛОВИЯ НЕ БЛОКИРОВАНИЯ В ШИРОКОПОЛОСНЫХ БАНЬЯН СЕТЯХШирокополосная Баньян сеть является не блокирующей, если активные входы х1…xk и соответствующие выходы Y1...Yk соответствуют следующим требованиям [13,18]:- Монотонность Y1<Y2 <....<Yk или Y1>Y2>...>Yk- Концентрация: любой ввод между двумя активными вводами так же является активным.Неравенство Yi<YJ означает, что каждый адрес выхода в YJ меньше адреса выхода в YJ. На рисунке 4.5 дан пример неблокирования с активными вводами x1=7, х2=8, х3=9 и соответствующими выходами Y1={1,3}, Y1= {4,5,6}, Y3={7,8,10,13,14}.Рисунок 4.5 - Условия не блокирования в широкополосной Баньян сети4.1.4 ПРОЦЕСС КОДИРОВАНИЯСхема сумматора (RAN), совместно с шифратором адресов (DAE), используется для организации адресов назначения каждой ячейки таким образом, чтобы каждая существенная ячейка была копирована без конфликтов в широкопосной Баньян сети. В ней проходят два процесса копирования ячеек: процесс кодирования и процесс декодирования. В процессе кодирования осуществляется преобразование рядов номеров копий, указанных в заголовках входящих ячеек, в ряд монотонных адресных интервалов, образующих заголовки ячеек в широполосной Баньян сети. Этот процесс осуществляется схемой сумматора и рядом шифраторов фиктивных номеров. От процесса декодирования зависит адрес назначения копий с транслятора номеров канала (TNT) [12,14].Рекурсивная структура log2N схемы сумматора показана на рисунке 4.6.Рисунок 4.6 - Схема сумматора и шифратора фиктивных адресовСхема сумматора состоит из (N/2)log2N сумматоров, каждый с двумя вводами и выводами. Вертикальная линия обозначает пересылку. Восточный ввод равен сумме западного и северного вводов, а южный вывод продолжает северный ввод. Текущие суммы CN генерируются у каждого порта в конце log2N каскадов, а затем шифраторы фиктивных адресов образуют новые заголовки из соседних текущих сумм. Новый заголовок содержит два поля: интервал фиктивных адресов, представленный двумя 1оg2N-битовыми двоичными номерами (минимальным и максимальным). Другое поле содержит индексный эталон, равный минимуму адресного интервала. Заметьте, что длина каждого интервала равна соответствующему номеру копии в обоих адресных схемах. Примем за Si i-текущую сумму. Тогда последовательность интервалов фиктивных адресов производится так [18]:(0,S0-1),(S0,S1)……..(SN-2,SN-1-1)где адрес размещается, начиная с 0. Эта последовательность обеспечивает деблокирование в баньян сети широкой рассылки.4.1.5 КОНЦЕНТРАЦИЯДля того, чтобы широкополосная Баньян сеть была не блокирующей, необходимо сократить число свободных вводов, находящимися между активными вводами. Это должно быть сделано до ввода ячеек в сеть, т.е. до RAN или сразу же после DAE.Так обратная Баньян сеть используется для концентрации активных вводов в непрерывный список [11,13]. Для получения ряда непрерывных монотонных адресов в обратной Баньян сети трассировочный адрес определяется текущими суммами на бит активности, (рисунок 4.6).Рисунок 4.7 - Входной концентратор состоящий из сумматора адресов и обратной Баньян сети 4.1.6 ПРОЦЕСС ДЕКОДИРОВАНИЯКогда ячейка выходит из баньян сети широкой рассылки, адресный интервал в ее заголовке содержит только один адрес, т.е. по алгоритму логического разделения интервалов[13]:min(log2N)=max(log2N)=Выходному адресуКопии ячеек, из одного и того же канала широкой рассылки отмечаются CI, который определяется на выходе широкополосной Баньян сети следующим образом (рисунок 4.7):СI=Выходной адрес-индексный эталонРисунок 4.7 - Вычисление индексов копийИндексный эталон изначально приравнивается минимуму адресного интервала. TNT (транслятор номера канала) присваивает абсолютный адрес каждой копии ячейки, и она трассируется к своему конечному назначению в последующий двухточечный коммутатор. Присвоение TN (номера канала) завершается простым табличным поиском, при котором идентификатор состоит из BCN (канала широкой рассылки) и CI (индекса копии), связанными с каждой ячейкой. Когда TNT (транслятор номера канала) получает копию ячейки, сначала он преобразует выходной адрес и IR (индексный эталон) в CI (индекс копии), а затем заменяет BCN (канал широкой рассылки) и CI (индекс копии) соответствующими TN (номерами каналов) в таблице перевода [14]. Процесс пересчета иллюстрирован на рисунке 4.8.Рисунок 4.8 - Пересчет номера канала с помощью табличного поиска4.2 ПЕРЕПОЛНЕНИЕ И РАЗДЕЛЕНИЕ ВЫЗОВАВ RAN (схеме сумматоров) копирующей системы происходит перегрузка, в том случае, когда число запросов копий превышает пропускную способность копирующей системы. Если частичное обслуживание (которое так же называется разделением вызова) невозможно при копировании ячейки, и ячейка должна произвести все свои копии за один временной интервал, тогда в случае переполнения пропускная способность может снижаться. На рисунке 4.9 показано переполнение, которое произошло у 3-го порта, и пропускаются только пять копий ячеек, при наличии более восьми запросов [14]. Рисунок 4.9 - Не блокирующая копирующая система 88 без разделения вызовов
Страницы: 1, 2, 3, 4, 5
|
|
