| |
Коммутация в сетях с использованием асинхронного метода переноса и доставки 
трицательным свойством Баньяновидных сетей является их принадлежность к блокирующим схемам, причем вероятность блокировки ячейки при ее маршрутизации быстро возрастает с ростом сети [8]. Очевидно, что в таких сетях существует единственный путь с любого входного порта на любой выходной. Регулярные Баньяновидные сети используют только один тип коммутационных элементов. В их разновидности (так называемых SW-Баньяновидных сетях) вероятность блокировки ячеек удается уменьшить, применяя кроссы больших размеров, -- они строятся рекурсивно из коммутационных элементов размером LМ, где L>2 и М>2.Дельта-сети представляют собой подкласс SW - Баньяновидных сетей и обладают свойством самомаршрутизации. Существует несколько типов дельта-сетей: прямоугольная (кроссы имеют одинаковое число входов и выходов), базовая (baseline), омега, флип, куб, обратный куб и др. Сеть дельта-b размером NN содержит logbN каскадов, причем каждый каскад состоит из N/b коммутационных элементов bЬ.Как уже говорилось, число точек коммутации в Баньяновидных сетях меньше N2, что может приводить к конфликту маршрутов двух ячеек, адресованных на разные выходные порты. При возникновении подобной ситуации, именуемой внутренней блокировкой, лишь одна из двух ячеек способна достичь следующего каскада, а в результате общая производительность снижается.Одно из решений проблемы состоит в добавлении специальной сети предварительной сортировки (например, так называемого сортировщика Батчера), которая направляет ячейки в Баньяновидную сеть. Сортировщик позволяет избежать блокировок при адресации ячеек на различные выходные порты, но если они одновременно адресуются на один и тот же выход, единственным решением становится буферизация [8,1,14].2.19 РАЗДЕЛЕНИЕ БУФЕРОВЧисло и размер буферов имеют важное значение при разработке коммутатора. В устройствах с общей памятью централизованный буфер зачастую имеет преимущество перед средствами статистического разделения. Принимая интенсивный поток ячеек на некоторый выходной порт, коммутатор выделяет для них максимально возможную часть буферного пространства, что приводит к экономии последнего, поскольку ячейки поступают на различные порты случайным образом [1,12].Для коммутационного поля с TDM-шиной и N выходными буферами большая группа ячеек, одновременно поступивших на какой-либо выход, естественно, не может быть принята другим выходным буфером. Тем не менее каждый выходной буфер способен статистически мультиплексировать трафике N входов.В структурах с N2 выходными буферами, имеющих полносвязную топологию, статистическое мультиплексирование между выходными портами или на любом выходном порте невозможно. В этом случае размер буферного пространства растет экспоненциально.Буферы могут быть установлены на входе сети Батчера (рисунок 2.6).Рисунок 2.6 - Входная буферизацияОднако в этом случае возможна блокировка очереди ячейкой, находящейся в ее начале направляемой на занятый выходной порт, даже если выходные порты ячеек, расположенных позади данной, свободны [1,3,5].В такой ситуации способна выручить дисциплина «пришедший первым обслуживается в случайном порядке» (First In Random Out, FIRO), но, к сожалению, она не имеет простой реализации. Другой способ избежать конфликтов маршрутов -- установить буфер непосредственно внутри коммутационных элементов Баньяновидной сети. Если две ячейки одновременно направляются в один и тот же выходной канал, одна из них буферизуется внутри коммутационного элемента. Внутренняя буферизация используется и механизмом управления с помощью обратной блокировки (backpressure): очереди в одном каскаде сети задерживают ячейки предыдущего каскада сигналом обратной связи. Влияние процедуры обратной блокировки может достигнуть первого каскада и привести к созданию очередей на входах. Следует отметить, что внутренняя буферизация способна вызвать блокировку ячейки в начале очереди на каждом коммутационном элементе и, следовательно, не позволяет достичь максимальной производительности.Еще один вариант -- использование рециркуляционного буфера, внешнего к коммутационному полю (рисунок 2.7).Рисунок 2.7 - Рециркуляционные буферыЭтот подход применяется в широкополосных цифровых коммутаторах Sunshine фирмы Bellcore и Starlite компании AT&T. В данном случае конфликты на выходе обнаруживаются после прохождения сортировщика Батчера, затем сеть выбирает ячейку для дальнейшей передачи, а оставшиеся ячейки через рециркуляционный буфер возвращаются на входные порты сети Батчера. К сожалению, данный метод требует сложного приоритетного управления для сохранения исходной последовательности передаваемых ячеек и применения сети Батчера большего размера для размещения рециркулированных ячеек.Помимо рассмотренных выше видов Баньяновидных сетей существует немало типов сетей.M1N с множественными путями между входными и выходными портами. Классическими примерами являются неблокирующие сети Бэнеша и Клоза, сети со свойством самомаршрутизации и распределением нагрузки, снижающими потребность во внутренней буферизации, групповые Баньяновидные коммутационные структуры (например, тандем Баньянов).Для формирования таких сетей возможно параллельное использование нескольких Баньяновидных соединительных сетей [8,9].Сети MIN с множественными путями обеспечивают более однородное распределение трафика, необходимое для минимизации внутренних блокировок и повышения отказоустойчивости [14]. Тем не менее если ячейки направляются по независимым путям с переменными задержками, необходимо предусмотреть сохранение исходной последовательности ячеек в виртуальном соединении на выходном порте. Поскольку данный процесс может потребовать значительных затрат вычислительных ресурсов процессора, предпочтительнее выбирать путь передачи ячеек на стадии установления и использовать его в течение всего времени существования соединения. Особое внимание должно уделяться предотвращению блокировки последовательных вызовов.2.20 ОТКАЗОУСТОЙЧИВОСТЬПоскольку надежность является существенным аспектом функционирования коммутационных систем, необходимо обеспечить избыточность их критически важных компонентов. Поле маршрутизации и структура буферов, являющиеся важнейшими элементами коммутационной системы, могут быть продублированными или избыточными, что влияет на организацию механизмов обнаружения отказов и восстановления работоспособности [15].Простейший способ повышения надежности сводится к разбиению всей совокупности коммутируемых ячеек на непересекающиеся подмножества, распределяемые между параллельными плоскостями поля маршрутизации. Этот метод весьма эффективен, так как он обеспечивает наименьшую избыточность, а каждая плоскость несет лишь малую долю общего трафика. Другой вариант -- тождественное дублирование всего множества ячеек -- обеспечивает большую отказоустойчивость при меньшей производительности. Компромиссным решением может быть использование частично перекрывающихся подмножеств.Распараллеливание плоскостей поля маршрутизации и структуры буферов поднимает степень отказоустойчивости, однако гораздо важнее повысить избыточность в пределах отдельных плоскостей. Баньяновидные сети склонны к отказам, поскольку содержат единственный путь в каждой паре «вход--выход»; сети с множественными путями отличаются большей отказоустойчивостью. Для повышения избыточности следует включать в состав Баньяновидных сетей дополнительные коммутационные элементы и каскады, избыточные и альтернативные соединения либо увеличивать число входных и выходных портов. Платой за это становится усложнение как схем буферизации и маршрутизации, так и средств управления [8].Для организации эффективного контроля за отказоустойчивостью коммутационной системы применяются разнообразные тестирующие механизмы. Маршрутизация специальных ячеек через тестовые элементы и отслеживание их появления на выходах, а также добавление служебной информации в заголовок ячейки позволяют обнаружить потери ячеек, ошибочные пути или неоправданные задержки. При выявлении отказа трафик перераспределяется до устранения причины сбоя, причем функция перераспределения может выполняться как концентраторами, так и самим коммутационным полем. 3 ОСНОВЫ БАНЬЯН-КОММУТАЦИИ3.1 БАНЬЯН СЕТИОтличительное свойство Баньян сети - это существование перехода от любого входа к любому выходу [8],Рисунок 3.1- показывает четыре вида сетей, принадлежащих к этому классу:а) смешанные (Омега) сеть;b) реверсная смешанная сеть;c) особо чувствительная Баньян сеть;d) обыкновенная сеть;Основное свойство этих сетей:1. Они состоят из n=log2N и N/2 узлов на уровень.2. Они имеют самонастраивающееся свойство - уникальный n-битный адрес назначения может использоваться для передачи ячейки от любого входа к любому выходу, по одному биту на каждый уровень.3. Их регулярность и взаимосвязная схема очень привлекательна для применения в VLSI (VLSI - сверх большая степень интеграции).Рисунок 3.2 показывает пример соединения в Баньян сети 88, где темные линии отражают передающие пути. С правой стороны адрес каждого выходного сигнала обозначен как ряд n-битов, b1...bn. Адрес ячейки сигнала закодирован в заголовке ячейки. На первом уровне проверяется бит b1, еслиэто 0, ячейка будет выдвинута на высший, исходящий уровень; если это 1,то ячейка отправляется на низший уровень. На следующем уровне проверяется бит b1, передача сигнала происходит аналогично.Рисунок 3.2 - Баньян сеть 88Внутренняя блокировка происходит в случае когда ячейка потеряна из-за конфликтных ситуаций на уровне сети. Рисунок 3.3 приводит пример внутренней блокировки внутри Баньян сети 8x8. Тем не менее, Баньян сеть не будет иметь внутренних блокировок, если будут соблюдены следующие условия [12]:· Нет свободного входного сигнала между любыми двумя активными входами.· Выходные адреса ячеек находятся либо в прямом, либо в обратном порядке. Рисунок 3.3 - Блокировка в Баньян сети 88Рисунок 3.4(a) - Не блокируемая Баньян сеть для входных сигналов(b) - Сортирующая Баньян сетьРассмотрим рисунок 3.4. Предположим, что Баньян сети предшествует сети которая накапливает ячейки и сортирует их, учитывая их выходные значения. Получившаяся в результате структура является деблокирующей сортирующей Баньян сетью.3.2 СОРТИРУЮЩАЯ БАТЧЕР СЕТЬЭта сеть формируется серией объединенных сетей различных размеров [12,14]. Рисунок 3.5 демонстрирует сортирующую Батчер сеть 8x8, состоящую из объединенных сетей трех различных размеров. Объединенная сеть на рис.3.6 состоит из 22 сортирующих элементов в каскадах, и схема соединения между каждой парой смежных каскадов аналогична схеме Баньян сети. Можно заметить, что если адреса первой половины входящих ячеек расположены в возрастающем порядке, а адреса второй половины - в убывающем, то объединенная сеть будет сортировать ячейки на выходе в прямом порядке. Сортирующая сеть 88 будет сформирована, если 88 объединенной сети предшествуют две объединенных сети 44 и четыре объединенных (сортирующих) элемента 22. Произвольный список из восьми входных ячеек будет распределен сначала на четыре списка по две ячейки, а затем - в два списка по четыре ячейки и наконец - в список из восьми ячеек.Объединенная сеть NN состоит из log2N уровней и (N log2N)/2 уровней. Сортирующая сеть имеет 1+2+......+ log2N=(log2N)(log2N+l)/2 уровней и (N log2N)(log2N+l)/2 элементов [14].Рисунок 3.5 - Сортирующая Батчер сеть 88 Рисунок 3.6 - Структура передающей сети3.3 АЛГОРИТМЫ РАЗРЕШЕНИЯ КОНФЛИКТОВ НА ВЫХОДЕ3.3.1 ТРЕХФАЗОВАЯ РЕАЛИЗАЦИИСледующий 3-х эталонный алгоритм является решением для выходного спорного сигнала в Батчер-Баньян коммутаторе.(рис 3.7(а)).Рисунок 3.7 - 1 этап: отправка запросаВ первую фазу алгоритма (фазу арбитража) каждый вводной порт I посылает в сортирующую сеть краткий запрос, содерж6щий только информацию об источнике и назначении (ячейки). В сортирующей сети ячейки рассматриваются в порядке возрастания, по адресам их назначения. Запросы сортируются все вместе и выбирается тот, чей адрес назначения отличен от предыдущего в сортировочном списке [14,17].Поскольку результаты арбитража не известны входным портам, выбранные запросы посылают уведомление своим вводным портам через взаимосвязанную сеть во вторую фазу (фазу уведомления). Сеть с обратной связью представлена на рисунке 3.7(в), состоит из N фиксированных соединений, каждый выход сети Батчера соединен с входом сети Батчера.Рисунок 3.8 - 2 этап: уведомление решающих портовКаждое подтверждение несет источник, который получил разрешение на вход Батчер сети. Эти источники проходят через всю Батчер-Баньян сеть на различные выхода, учитывая адрес источника. Когда трассировка уведомлений обратно через идентичную специализированную сеть ко вводам закончена, выводы узнают свои результаты арбитража. Вводам, получившим уведомление, обеспечивается бесконфликтный вывод ячеек.Рисунок 3.9 - 3 этап: отправка ячеек с информациейЭти входные порты перемещают полную ячейку на третьем последнем этапе, через такую же Батчер-Баньян сеть (рисунок 3.7(с)). Вводы, не получившие уведомления, сохраняют свои ячейки в буфере следующего трехфазового цикла. 3.3.2 КОЛЬЦЕВОЕ РЕЗЕРВИРОВАНИЕВ Баньян коммутаторе с накопителем предусмотрено кольцевое резервирование (рисунок 3.10). Этот коммутатор состоит из Баньян коммутационной системы с накопителем, нескольких коммутационных интерфейсов, кольцевой адаптер (RHE) и синхронизатора [17,19].Рисунок 3.10 - Батчер - Баньян коммутатор с кольцевым резервированиеИнтерфейс коммутатора осуществляет кольцевое резервирование, буферизацию входящих ячеек, синхронизацию ячеек, отправленных в коммутационную систему и буферизацию ячеек на выходе. Входящие в коммутатор ячейки буферизуются в FIFO, до резервирования. Когда резервирование на выводе успешно завершено, ячейка доставляется в коммутационную систему в начале следующего цикла. После этого следующая ячейка из очереди может проходить резервирование. При выходе из коммутационной системы, ячейка буферизуется в интерфейс, чтобы затем быть переданной по назначению RHE дает два сигнала синхронизации в коммутаторе: (синхронизации битов и начала цикла), три сигнала кольцевого резервирования (сигнал включения в работу кольца, сигнал данных кольца и синхронизации кольца). Сигнал данных кольца - это серия битов выходного резервирования, а сигнал синхронизации кольца указывает местоположение первого выходного порта в серии кольцевых данных. Эти два сигнала циркулируют через RHE и интерфейсы коммутатора по одному биту каждый раз, в течение всего процесса резервирования. Кольцевое резервирование происходит в начале каждого цикла, после того, как каждый кольцевой интерфейс получает заголовки копий самых старших ячеек. С началом каждого цикла данные кольца в RHE и каждый кольцевой интерфейс устанавливаются в исходное состояние («свободно»). Серии кольцевых данных начинают затем циркулировать через интерфейс бит за битом. Каждый интерфейс имеет портовой счетчик, который увеличивается (дает приращение) при каждом прохождении бита кольцевых данных. Каждый временной интервал портовой счетчик сравнивается с адресом назначения самой старшей ячейки для того, чтобы определить, должна ли ячейка быть отправлена на выход в следующий промежуток. При прохождении бита данных кольца, все интерфейсы коммутатора рассматривают кольцевую синхронизацию и кольцевые данные бита. Если сигнал кольцевой синхронизации верен, (это значит, что следующий бит кольцевых данных соответствует первому выводу), тогда портовой счетчик устанавливается в исходное состояние при прохождении следующего бита. Если назначение ячейки согласовано с портовым счетчиком и бит данных кольца свободен, интерфейс коммутатора делает на кольце запись «занято», означающую, что в следующий коммутационный цикл вывод будет занят. Если бит данных кольца уже занят, или если портовой счетчик не согласован с назначением старшей ячейки, бит данных кольца не изменяется. Т.к. каждый коммутационный цикл интерфейса делает не более одного резервирования, конфликтные ситуации в коммутационной системе исключены. Во время кольцевого резервирования, ячейки, зарезервированные в предыдущий коммутационный цикл, отправляются в коммутационную систему. На рисунке 3.11 показано, что в первый промежуток времени согласуются адреса выходных портов ячеек из вводов 1 и 5, и используются пункты, обозначающие, что ячейки могут пройти в эти порты. Ячейкам которые отмечены битами X1 и Х5 присваивается одно значение, указывающее на то, что выходные порты 1 и 5 уже заняты. Все отмеченные биты сдвигаются в сторону одного, и значения счетчиков так же увеличиваются на один по модулю во второй временной интервал. Во второй и третий промежутки времени согласования не происходит. В четвертый согласовываются адреса выходных портов ячеек из 0 и 2 вводов. Т.к. выходной порт 5 уже был зарезервирован для ячейки (на которой указано значение отмеченного бита X5)
Страницы: 1, 2, 3, 4, 5
|
|
|
