Алгоритм работы буферного устройства АТМ-коммутатора с параллельной настройкой

УДК 621.395.74

Е. А. Барабанова, Н. С. Мальцева, И. О. Барабанов

АЛГОРИТМ РАБОТЫ БУФЕРНОГО УСТРОЙСТВА АТМ-КОММУТАТОРА С ПАРАЛЛЕЛЬНОЙ НАСТРОЙКОЙ

E. A. Barabanova, N. S. Maltseva, I. O. Barabanov

ALGORITHM OF BUFFER DEVICE WORKING OF ATM-SWITCH WITH PARALLEL ADJUSTMENT

Предлагаемый алгоритм работы буферного устройства АТМ-коммутатора с параллельной настройкой предназначен для использования в мультисервисной сети связи. Алгоритм предусматривает распределение команд коммутации по коммутационным блокам выходного каскада с учётом значения приоритетов соответствующих им данных.

Ключевые слова: трехкаскадная коммутационная система, параллельный поиск, алгоритм, коммутационный блок, АТМ-технология, буферное устройство.

The offered algorithm of buffer device working of ATM-switch with a parallel adjustment is assigned to be used in multi-service network. The algorithm provides the distribution of switching comands through switching blocks of output stage, taking into account the values of the priorities of their respective data.

Key words: three-stage switching system, parallel searching, algorithm, switching block, ATM technology, buffer device.

Введение

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

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

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

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

В связи с этим исследование алгоритмов работы буферных устройств ATM-коммутаторов является актуальными и своевременными.

Предмет исследования. Буферное устройство АТМ-коммутатора с параллельной настройкой. Цель исследования. Разработать алгоритм работы буферного устройства АТМ-коммутатора с параллельной настройкой для использования его в мультисервисной сети связи.

Выбор способа буферизации в АТМ-коммутаторе

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

Этих недостатков нет у пространственных коммутаторов, которые нашли широкое применение в сетях ATM.

Так как коммутаторы могут осуществлять операции мультиплексирования, коммутируя несколько входных потоков/портов в один поток/порт, они должны иметь буфер (на входе и (или) на выходе для выравнивания потоков перед мультиплексированием) и уметь управлять очередью. Таким образом, ATM-коммутаторы выполняют следующие функции: пространственную коммутацию, маршрутизацию, мультиплексирование, организацию/управление очередями и трансляцию заголовков [1].

В случае, если в качестве АТМ-коммутатора выбрана трёхкаскадная коммутационная система (КС) с параллельным поиском [2], возможны два способа буферизации: буферизация в точках пересечения коммутатора и входная буферизация.

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

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

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

Размещение буферов на входе коммутатора позволяет разделить функции буферизации и коммутации, что весьма желательно с точки зрения компактности микросхем и их компоновки.

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

Если на один выход претендуют, например, k пакетов, то за время длительности цикла будет обслужен только один пакет, а остальные k - 1 останутся ждать следующего интервала. При этом ячейки, расположенные в очереди за блокированной ячейкой, также блокируются, даже если им нужен другой выход. Это приводит к снижению пропускной способности КС со входными буферными устройствами.

Для преодоления недостатка блокирования ячеек в голове очереди буфер с дисциплиной обслуживания FIFO следует заменить на запоминающее устройство с произвольной выборкой (RAM - Random Access Memory). Если первая ячейка заблокирована, то для передачи выбирается следующая при условии, что ее порт назначения свободен. Однако такой режим функционирования требует более сложного управления буферами для нахождения нужных ячеек и сохранения порядка их следования. Общая емкость буфера должна логически разделяться в зависимости от нагрузки на разные буфера с дисциплиной FIFO по количеству выходных линий.

В исследуемой трёхкаскадной КС предусмотрены буферные устройства на входе (для полезной информации) и выходе (для команд коммутации). Буферное запоминающее устройство (БЗУ) может быть построено на основе памяти с произвольной выборкой.

Анализ параметров буфера АТМ-коммутатора

Определим среднее значение времени задержки ячейки в узле коммутации или канале связи Ti. При этом будем полагать, что все каналы связи в виртуальных соединениях имеют одинаковую пропускную способность и все узлы коммутации в сети имеют равную производительность. Под виртуальным соединением в данном случае будем понимать последовательность ^-схем, отображающих узлы коммутации и каналы связи, через которые пролегает путь ячейки от источника с номером s до получателя с номером d. Виртуальное соединение, связывающее источник и получателя, будем обозначать s  d .

Среднее время задержки ячейки в буфере узла коммутации или канала связи широкополосной сети можно определить с использованием формулы Литтла:

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

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

Интенсивность суммарного входного потока ячеек в /-й узел коммутации можно определить по формуле

где 1г£ - интенсивность транзитного потока ячеек; 1^- интенсивность потока собственных ячеек от 5 источника.

Интенсивность суммарного входного потока ячеек в /-й канал связи можно определить по формуле

ляющихся к другим узлам коммутации сети; 1/ ^ - интенсивность потока собственных ячеек,

принадлежащих й узлам коммутации.

Тогда размер буфера для 0-схемы типа МЮ/1 можно определить следующим образом:

Таким образом, получено значение среднего времени задержки ячейки в узле коммутации или канале связи для 0-схемы типа МЮ/1 с буфером бесконечной емкости (М обозначает марковский процесс, В обозначает, что время обслуживания всегда одинаково: фиксированное или детерминированное, и 1 означает один сервер). Рассмотрим 0-схему типа МЮ/УХ, где X- емкость буфера узла коммутации, и определим максимальное значение времени задержки ячейки в /-м узле коммутации или канале связи в зависимости от размера буфера X данного узла или канала и времени обслуживания Тобс в буфере одной ячейки. Если емкость буфера полностью заполнена ячейками, то максимальное время, которое ячейка проведет в узле коммутации или канале связи, ожидая обслуживания, составит

Найдем зависимость средней и максимальной задержки ячейки в /-м буфере узла коммутации или канала связи, представленных однофазной 0-схемой с конечным буфером, емкость которого X изменялась в широком диапазоне.

где Ы/ - среднее количество ячеек в /-м буфере (в очереди и на обслуживании); 1/ - средняя

N

N

d=1

где 1i?T - интенсивность транзитного потока ячеек, проходящих по каналам связи и направ-

где р/ - коэффициент загрузки модели /-го узла коммутации или канала связи: р/ = 1/Тобс < р/; Тобс - время обслуживания ячейки в узле коммутации или канале связи.

Отсюда среднее время задержки ячейки в /-м узле коммутации или канале связи

T = Тобс

1 І ~ҐЛ ч

2

В КС узла коммутации обеспечивается коммутация широкополосных каналов связи. Широкополосный доступ ориентируется на стандартные скорости передачи 155,52 и 622,08 Мбит/с. Размер буфера для 0-схемы типа M/D/1 найдем из формулы

X = - ^ln Ploss

2

где p - загрузка; Pioss (X) - вероятность потери ячеек из-за искажений при передаче в канале связи, переполнения буфера узла коммутации и т. д.

Время обслуживания Гобс определим по формуле

T = 27 Р1я

Тобс 26С ’

где 1я - длина ячейки, C - пропускная способность канала связи.

Проанализируем, как изменяется размер буфера при различном значении вероятности потерь ячеек (рис. 1). Исходными параметрами для проводимых исследований были приняты следующие: 1Я - длина ячейки; 1Я = 0,424 Мбит; вероятность потери ячеек из-за искажений при передаче в канале связи, переполнения буфера узла коммутации и т. д. Ploss (X) = 10-8, 10-10 и 10-12.

Р«

Рис. 1. График зависимости размера буфера (числа ячеек АТМ) от загрузки при различной вероятности потерь ячеек

Из графиков следует, что при загрузке системы рг- = 0,9 (от 90 %) размер буфера колеблется от 80-120 ячеек при различных значениях вероятности потерь (д - размер буфера при вероятности потерь 10-8, д2 - размер буфера при вероятности потерь 10-10, д3 - размер буфера при вероятности потерь 10-12).

Время обслуживания пакета Тобс зависит от размера буфера: при пропускной способности канала связи С = 155,52 Мбит/с Тобс = 2,831 мкс; при пропускной способности канала связи С = 622,08 Мбит/с Тобс = 0,708 мкс.

Из графика зависимостей времени обслуживания от размера буфера при вероятности потерь ячеек р = 10-8 и различной пропускной способности коммутатора (рис. 2) следует, что при размере буфера от 20 ячеек время обслуживания при пропускной способности 622 Мбит/с в 4 раза меньше времени обслуживания при пропускной способности 155 Мбит/с. Поэтому для повышения времени обслуживания ячеек следует использовать КС, позволяющие более быстро производить поиск соединительных путей. В качестве такой КС рассмотрим трёхкаскадную КС с параллельной обработкой.

- ячейки

Рис. 2. График зависимостей времени обслуживания от размера буфера при вероятности потерь ячеек р = 10-8

Алгоритм работы АТМ-коммутатора с параллельной обработкой

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

Для примера рассмотрим трёхкаскадную КС на 64 входа и 128 выходов. Такая КС будет содержать 8 коммутационных блоков (КБ) входного каскада размерами 8 х 16, 16 КБ промежуточного каскада размерами 8 х 8 и 8 КБ выходного каскада размерами 16 х 16. Предлагается заполнять буферные запоминающие устройства в соответствии с приоритетом передаваемых данных. Максимальное число приоритетов может быть равно числу КБ выходного каскада и в рассматриваемом примере равно 8. Структурная схема трехкаскадной КС представлена на рис. 3.

Рис. 3. Структурная схема трехкаскадной КС размерами 64 х 128

Для передачи видеоинформации предлагается использовать 1-2 приоритеты, для передачи речи - 3-4 приоритеты и для передачи компьютерных данных - 5-8 приоритеты. В действительности должна предусматриваться динамическая настройка коммутаторов в зависимости от вероятности передачи того или иного вида трафика по сети.

Особенность алгоритма параллельного поиска состоит в поиске свободных каналов связи, который начинается с выходов системы [3]. При поступлении на разные КБ выходного каскада команд коммутации с разным значением п, но одинаковым х, КС выбирает команду коммутации с наименьшим значением КБ выходного каскада 2 (х - номер КБ входного каскада, п - номер входа в КБ входного каскада).

В зависимости от приоритета, который присвоен данной ячейке, предлагается помещать её в соответствующий КБ выходного каскада. Например, пусть ячейке присвоен приоритет номер 1 - наивысший приоритет, тогда, согласно алгоритму, следует поместить команду коммутации, определяющую данную ячейку, в КБ выходного каскада 2\\ соответственно, если ячейке присвоен приоритет 2, то, согласно алгоритму, следует поместить команду коммутации, определяющую данную ячейку, в КБ выходного каскада 22 и т. д.

Таким образом, несмотря на то, что физически такой коммутатор содержит 128 выходов, реальное число выходов будет составлять 16 (максимальное число выходов из КБ выходного каскада).

Предлагаемый алгоритм работы буферного устройства трёхкаскадной КС с параллельным поиском представлен на рис. 4.

[ Начало ]

Рис. 4. Алгоритм работы буферного устройства в трёхкаскадной КС с параллельным поиском

Рассмотрим работу данного алгоритма при поступлении двух команд коммутации. Первая команда - на соединение второго входа с десятым выходом (приоритет «1»). Вторая команда -на соединение восьмого входа с пятым выходом (приоритет «3»). Согласно предлагаемому алгоритму заполнения буферов в БЗУ первого КБ на 10 выход поступит пара (1.2), а в БЗУ третьего КБ на 5 выход поступит пара (1.8). Так как на первом шаге процесса настройки возникнет конфликт на занятие промежуточной линии связи С.1.У, то для настройки на первом шаге будет выбрана команда коммутации, хранящая в БЗУ первого КБ, и, таким образом, информация со входа 2 к выходу 10 поступит раньше, чем информация со входа 8 на выход 5.

Такой алгоритм работы буферного устройства позволяет значительно оптимизировать работу трёхкаскадной КС с параллельным поиском, особенно если учитывать, что процесс передачи информации и следующий этап настройки происходят одновременно. Это позволяет использовать КС с параллельным поиском для передачи разнородного трафика в мультисервис-ных сетях связи.

Заключение

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

Предлагается новый алгоритм работы буферного устройства АТМ-коммутатора с параллельным поиском каналов связи, предусматривающий распределение команд коммутации по КБ выходного каскада с учётом значения приоритетов соответствующих им данных.

СПИСОК ЛИТЕРАТУРЫ

1. Слепов Н. Н. Современные цифровые технологии глобальных сетей связи. - М.: Астра Полиграфия, 2011. - 298 с.

2. Пат. на изобретение 2359313 Российская Федерация, МПК 006Г 7/00. Трёхкаскадная коммутационная система / Жила В. В., Барабанова Е. А., Мальцева Н. С (ДЦ). - № 2007107780/09; заявл. 01.03.2007; опубл. 20.06.2009, Бюл. № 17.

3. Барабанова Е. А., Мальцева Н. С. Алгоритмы работы коммутационных систем с параллельной настройкой // Вестн. Астрахан. гос. техн. ун-та. Сер.: Управление, вычислительная техника и информатика. - 2011. - № 1. - С. 150-156.

Статья поступила в редакцию 1.12.2011

ИНФОРМАЦИЯ ОБ АВТОРАХ

Барабанова Елизавета Александровна - Астраханский государственный технический университет; канд. техн. наук; доцент кафедры «Связь»; ElizavetaAlexB@yandex.ru.

Barabanova Elizaveta Aleksandrovna - Astrakhan State Technical University; Candidate of Technical Science, Assistant Professor of the Department "Communication"; ElizavetaAlexB@yandex.ru.

Мальцева Наталия Сергеевна - Астраханский государственный технический университет; канд. техн. наук; доцент кафедры «Связь»; sviaz@astu.org.

Maltseva Natalia Sergeevna - Astrakhan State Technical University; Candidate of Technical Science; Assistant Professor of the Department "Communication"; sviaz@astu.org.

Барабанов Игорь Олегович - Астраханский государственный технический университет; магистрант кафедры «Связь»; sviaz@astu.org.

Barabanov Igor Olegovich - Astrakhan State Technical University; Undergraduate of the Department "Communication"; sviaz@astu.org.