Здесь мы рассмотрим основные принципы организации АТМ переключателей и их функционирования.
Рис.2-57 показана общая схема организации АТМ переключателя. Есть набор входных линий, по которым ячейки поступают в переключатель, и, как правило, такое же число выходных линий, по которым ячейки двигаются после коммутации. Обычно переключатель работает синхронно, в том смысле, что длительность цикла строго фиксирована. В течение каждого цикла просматриваются все входные линии и, если на линию к этому моменту целиком поступила ячейка, то она считывается и передается в центр коммутации, а затем на выходную линию.
Переключатель может быть конвейерным, т.е. обработка одной ячейки может занимать более одного цикла. Ячейки поступают асинхронно, т.е. таймер переключателя отмечает момент начала очередного цикла. Если ячейка не поступила целиком за один цикл, то она должна ожидать начала следующего цикла.
Обычно ячейки поступают со скоростью 150 Mбит/сек. Учитывая размер ячейки в 53 байта, получаем около 360 000 ячеек/сек. Таким образом, на обработку одной ячейки приходится около 2.7 мксек. Выпускаемые на сегодня переключатели имеют от 16 до 1024 входных линий, т.е. переключатель должен быть в состоянии обрабатывать за 2.7 мксек от 16 до 1024 ячеек. При скорости 622 Mбит/сек переключающий центр должен обрабатывать очередную порцию ячеек за 700 нсек. Благодаря тому, что ячейки фиксированной длины и небольшого размера (53 байта), коммутация на таких скоростях становится возможной. При переменной длине и большем размере ячейки задача создания АТМ переключателя была бы намного сложнее.
Все АТМ переключатели обязаны удовлетворять следующим требованиям:
· терять как можно меньше ячеек;
· никогда не менять порядок поступления ячеек по каждому виртуальному соединению.
Первое требование означает, что АТМ переключатель должен обеспечивать достаточно большую скорость переключения, но так, чтобы не терять ячейки. Считается допустимой потеря 1 ячейки на 1012 ячеек. В больших переключателях считается допустимой потеря 1-2 ячеек за час работы. Второе требование сохранять порядок поступления ячеек неизменным естественно существенно усложняет конструкцию переключателя, но это требование АТМ стандарта.
Одна из ключевых проблем конструкции АТМ переключателей состоит в том, что делать когда сразу по нескольким линиям пришли ячейки, которые должны быть отправлены по одной и той же выходной линии? Напрашивается решение: взять одну ячейку, обработать ее, а другую сбросить. Но в силу требования 1 оно не годиться.
Возможно другое решение: буферизовать ячейки на входе. Идея этого решения показана на рис.2-58. Пусть в начале цикла 1 (рис.2-58 а) поступило четыре ячейки, две из которых должны быть отправлены по линии 2. Поскольку из-за линии 2 возник конфликт, то только три ячейки предаются на выходные линии. Поэтому к началу цикла 2 (рис.2-58 b) на выходе переключателя появятся три ячейки, но на вход поступят новые. К началу цикла 3 (рис.2-58 с) на входе останется только одна ячейка, и очередь рассосется только на четвертом цикле. В случае буферизации на входе надо следить за тем, чтобы дисциплина обслуживания возникающих очередей была бы справедливой и равномерно обслуживала очереди на всех линиях.
Недостаток этого решения в том, что очередь на входе может блокировать даже те ячейки, которые должны быть перекоммутированы на те линии, не которых нет конфликтов. Поэтому по соответствующему виртуальному соединению скорость упадет. Этот эффект называется блокировкой на входе. Кроме этого буферизация ячейки на входе требует дополнительной логики в схемах, что усложняет конструкцию АТМ переключателя.
Альтернативным решение может быть буферизация на выходе. Это решение показано на рис.2-59. Если несколько ячеек должно уйти по одной и той же линии, то они передаются на выход и буферизуются там. Это требует меньше циклов. В нашем примере только 3. В общем случае Karol 1987 показал, что буферизация на выходе эффективнее, чем буферизация на входе.
Рассмотрим конструкцию АТМ переключателя, использующего буферизацию на выходе. Этот тип переключателей называется переключатель выталкивающего типа. Он показан на рис.2-60 для конфигурации 8х8 линий. Здесь каждая входная линия соединена с шиной, к которой подключены все выходные линии. Каждая входная шина имеет свой механизм управления, не зависящий от других, что существенно упрощает конструкцию.
У каждой поступающей ячейки аппаратно анализируется заголовок, чтобы определить какому виртуальному соединению она принадлежит. Затем, с помощью таблицы коммутации, определяется выходная линия, через которую эта ячейка должна покинуть переключатель. Пересечение с соответствующей выходной линией активизируется, и, когда ячейка доходит до этого пересечения, она попадает в буфер. Ресурсов переключателя достаточно, чтобы буферизовать на одном выходе ячейки со всех входов, если это потребуется, или размножить ячейки, если их надо разослать по нескольким виртуальным соединениям.
Естественно было бы буферизовать все конфликтующие ячейки в выходном буфере. Однако, для переключателей, например, на 1024 линии, нам потребовалось 1024 буферов по 1024х53 байтов. Слишком много! Выходом из этой ситуации - выделение лишь n байтов на буфер, где n – параметр настройки. Если конфликтующих ячеек больше, то ячейки, не попавшие в буфер, сбрасываются. Здесь опять-таки надо быть осторожным, определяя на каких входных линиях сбрасывать ячейки, из каких выходных буферов выталкивать ячейки на очередном цикле так, чтобы не было дискриминации. Регулируя параметром n, можно варьировать стоимость и число сбрасываемых ячеек, что влияет на цену переключателя.
Переключатели Батчера-Баньяна.
Основным недостатком переключателей выталкивающего типа является то, что центр коммутации - простой коммутатор, а это означает, что его сложность растет квадратично от числа коммутируемых линий. Из рассмотрения принципов построения коммутаторов для коммутации каналов мы уже знаем, что одно из решений - каскадные коммутаторы. Аналогичное решение возможно и для коммутации пакетов.
Это решение называют переключателем Батчера-Баньяна. Как и переключатели выталкивающего типа, переключатель Батчера-Баньяна синхронный, т.е. за один цикл он может обрабатывает несколько входных линий. На рис.2-61 а показан трех ступенчатый 8х8 переключатель Баньяна. Он называется так, поскольку похож на корни баньянового дерева. В баньяновых переключателях для каждого входа существует ровно один путь к любому из выходов. Маршрутизация пакета происходит в каждом узле на основе адреса выходной линии, которую должен достичь пакет. Адрес выходной линии определяют на входе по номеру виртуального соединения. В данном случае трех битовый номер впереди ячейки используется в каждом узле для маршрутизации.
В каждом из 12 переключающих элементов есть два входа и два выхода. В зависимости от значения соответствующего разряда ячейка направляется либо в порт 0 либо в порт 1. Если обе ячейки, поступившие на вход одного и того же коммутирующего элемента, должны быть направлены на один и тот же порт, то направляется одна, а вторая сбрасывается.
Итак, адрес выходной линии анализируется в каждом элементе слева направо. Например, код 001 означает, что соответствующая ячейка будет направлена на верхний, потом еще раз на верхний, а затем на нижний порты. Коллизии в баньяновской сети возникают, когда в одном и том же элементе в одно и тоже время надо использовать один и тот же порт. На рис.2-62 а показаны коллизии. На рис.2-62 b те же 8 ячеек коммутируют без коллизий. Вывод: в зависимости от распределения ячеек на входе баньяновская сеть либо будет терять ячейки, либо нет.
Идея Батчера состояла в том, чтобы переставить ячейки на входах так, чтобы в баньяновской сети конфликтов не возникало. Такая перестановка показана на рис.2-62 b.
Для сортировки входов Батчер в 1968 году предложил специальный переключатель. Подобно баньяновскому переключателю, переключатель Батчера строится из элементов 2х2, работает синхронно и дискретно. В каждом элементе выходные адреса ячеек сравниваются. Больший направляется по стрелке, а меньший в противоположном направлении. Если ячейка одна, то против стрелки. Подчеркнем, что сравниваются не отдельные биты, а весь адрес как число.
На рис.2-63 показан переключатель Батчера 8х8. Сложность операции перестановки для устройства Батчера - . Ячейки, отсортированные Батчеровской сетью, подаются на вход сети баньяна, где они пересылаются без конфликтов. На рис.2-64 показана комбинация Батчеровской и баньяновской сетей.
Известны две трудности, которые переключатели Батчера-Баньяна не умеют преодолевать:
· если коллизия на выходе все-таки возникает, то они не умеют с ней бороться, решением является только сброс;
· рассылка одной и той же ячейки сразу на несколько выходов.
Было предложено несколько промышленных переключателей этого типа, которые по-разному преодолевают эти недостатки. Основная их идея, это встраивание между переключателем Батчера и сетью баньяна специальной схемы, которая позволяет преодолеть эти две трудности.
. Ячейки, отсортированные Батчеровской сетью, подаются на вход сети баньяна, где они пересылаются без конфликтов. На рис.2-64 показана комбинация Батчеровской и баньяновской сетей.