РАЗРАБОТКА УНИВЕРСАЛЬНОГО АЛГОРИТМА ДЛЯ МНОГОКАСКАДНЫХ КОММУТАТОРОВ С ПАРАЛЛЕЛЬНОЙ НАСТРОЙКОЙ
Авторы:
1.
Институт проблем управления им. В.А. Трапезникова Российской академии наук
(доктор технических наук, доцент; ведущий научный сотрудник лаборатории управления сетевыми системами)
Москва, Россия
Москва, Россия
2.
Астраханский государственный технический университет
(кандидат технических наук, доцент; доцент кафедры связи)
3.
Астраханский государственный технический университет
Тип:
Статья
Страницы:
с 118
по 125
Статус:
Опубликован
Получено:
05.01.2013
Одобрено:
25.01.2013
Опубликовано:
25.01.2013
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 621.394.6:004.7
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ББК 32.882-52:32.988
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 621.394.6:004.7
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ББК 32.882-52:32.988
Язык материала:
русский
Ключевые слова:
многокаскадная коммутационная система, параллельный поиск, параллельная идентификация, алгоритм, коммутационный блок, ячейка коммутации
Аннотация (русский):
Предметом исследования являлись схемы и алгоритмы работы многокаскадных коммутационных систем с параллельной настройкой. Цель исследования – разработать универсальный алгоритм работы многокаскадных коммутационных систем с параллельной настройкой для использования их в сетях с коммутацией пакетов. Многокаскадные коммутаторы с параллельной настройкой строятся на итерационном принципе наращивания каскадов. В основе новых алгоритмов работы многокаскадных коммутаторов с параллельной настройкой лежит принцип разложения центрального каскада в трёхкаскадную систему и базовый алгоритм поиска свободных каналов связи внутри трёхкаскадной схемы.
Предметом исследования являлись схемы и алгоритмы работы многокаскадных коммутационных систем с параллельной настройкой. Цель исследования – разработать универсальный алгоритм работы многокаскадных коммутационных систем с параллельной настройкой для использования их в сетях с коммутацией пакетов. Многокаскадные коммутаторы с параллельной настройкой строятся на итерационном принципе наращивания каскадов. В основе новых алгоритмов работы многокаскадных коммутаторов с параллельной настройкой лежит принцип разложения центрального каскада в трёхкаскадную систему и базовый алгоритм поиска свободных каналов связи внутри трёхкаскадной схемы.
Ключевые слова:
многокаскадная коммутационная система, параллельный поиск, параллельная идентификация, алгоритм, коммутационный блок, ячейка коммутации
многокаскадная коммутационная система, параллельный поиск, параллельная идентификация, алгоритм, коммутационный блок, ячейка коммутации
Введение Главной задачей при разработке современных коммутаторов является увеличение пропускной способности оборудования. Коммутационная техника в настоящее время использует высокоскоростные интерфейсы, а производительность внутренней коммутационной матрицы может достигать десятков гигабит в секунду. В магистральных сетях передачи данных к производительности коммутационных устройств предъявляются ещё более жёсткие требования. Традиционно производители коммутационного оборудования используют в качестве коммутирующей среды матричный коммутатор, основное достоинство которого – простота конструкции, а недостаток – ограничение на число входов, т. к. при увеличении числа входов сложность системы резко возрастает. Выход из сложившейся ситуации – использование трех и более каскадных схем, которые позволяют добиться увеличения пропускной способности системы, но при меньших затратах [1]. Поэтому при небольшом числе входов применяют однокаскадные, а при большом числе входов – многокаскадные структуры. Данное правило применимо и для коммутационных систем (КС) с параллельной настройкой [2], которые строятся по принципу итерационного наращивания каскадов. Коммутационные системы с параллельной настройкой предназначены для использования в высокопроизводительных вычислительных системах и высокоскоростных сетях передачи данных, где требуются системы как с небольшим числом входов, так и многопортовые коммутаторы. В связи с этим исследование принципов построения многокаскадных КС с параллельной настройкой является актуальным и своевременным. Предмет исследования – схемы и алгоритмы работы многокаскадных КС с параллельной настройкой. Цель исследования – разработать универсальный алгоритм работы многокаскадных КС с параллельной настройкой для использования их в сетях с коммутацией пакетов. Структурная схема многокаскадной коммутационной системы с параллельной идентификацией каналов данных Многокаскадные КС позволяют использовать совокупность точек коммутации для образования нескольких соединительных путей через коммутационную схему. Структурная схема многокаскадной КС с параллельной идентификацией каналов связи приведена на рис. 1. Многокаскадная КС с параллельной идентификацией каналов связи содержит нечётное число каскадов: входной, промежуточные и выходной. Входы и выходы КС разделены на подгруппы трёх типов: из p входов и p выходов, из х входов и х выходов и из х входов и p выходов. Входы каждой подгруппы обслуживаются отдельной прямоугольной коммутационной схемой – коммутационном блоком (на рис. 1 они обозначены 1…X, 1…Q и 1…Х). Коммутационные блоки всех каскадов содержат ячейки коммутации. Для обеспечения полнодоступности и неблокируемости многокаскадного коммутационного поля с параллельной идентификацией каналов связи необходимо соблюдение критерия Пола. Суть данного критерия состоит в том, что число выходов каждого коммутационного блока входного каскада, а следовательно, и число коммутационных блоков в промежуточном каскаде должно быть не менее Q = 2p – 1, где p – число входов в коммутационном блоке входного каскада. Например, если КС имеет 2 048 входов и 2 048 выходов и должна состоять из 5 каскадов, входной и выходной каскады системы будут иметь по 128 блоков размерностью 16 × 64 и 64 × 16 соответственно. Второй и четвёртый каскад будут состоять из 64 коммутационных блоков размерностью 128 × 128. Промежуточный каскад системы состоит из 256 коммутационных блоков размерностью 128 × 128. Рис. 1. Структурная схема многокаскадной коммутационной системы К выходам КС подключены контроллеры, все они связаны между собой общей шиной, предназначенной для обмена информацией, и соединены с единым для всей системы устройством управления (УУ) (рис. 2). Рис. 2. Структурная схема многокаскадной коммутационной системы с параллельной идентификацией свободных каналов связи Устройство управления обеспечивает функционирование коммутационного поля с параллельной идентификацией каналов связи. В качестве УУ может быть выбран автомат с жёсткой логикой. Коммутационная система относится к системам с разделенными полюсами, хотя имеет двунаправленные линии связи. Это связано с особенностями функционирования системы в процессе установления соединений и в процессе передачи информации. В процессе идентификации свободных путей и установления соединений настроечная информация может циркулировать и в направлении от входов к выходам и наоборот (но в каждый такт только в одном направлении – это определяется алгоритмом работы системы) [2]. После установления всех необходимых соединений в КС информация может двигаться только в одном направлении – от информационных входов системы к ее выходам. Генератор имени (ГИ) представляет собой устройство, позволяющее в определенный момент времени подавать на соответствующий вход ячейки коммутации имя выходной линии коммутационного блока, к которой подключена данная ячейка коммутации. Многокаскадная КС с параллельной идентификацией свободных каналов связи с подключенными ГИ представлена на рис. 3. Рис. 3. Многокаскадная коммутационная система с генераторами имён При реализации метода параллельной идентификации свободных каналов поиск параллельных идентификаторов свободных каналов связи происходит во внешних по отношению к коммутационному полю устройствах. В качестве таких устройств могут быть выбраны avr-микроконтроллеры. Микроконтроллеры являются основой многих современных устройств и приборов, в том числе и бытовых. Самой главной особенностью микроконтроллеров является то, что они позволяют реализовывать схемы любой степени сложности. Микроконтроллер управляет различными устройствами с минимальными аппаратными затратами, т. к. большое число периферийных схем уже имеется на кристалле микроконтроллера. За счёт этого уменьшаются размеры конструкции, и снижается потребление энергии. Структурные схемы многокаскадных коммутационных систем с параллельным поиском Многокаскадные КС с параллельным поиском строятся на базе трёхкаскадной КС [3]. Трёхкаскадная КС (рис. 4) содержит z коммутационных блоков 1.1, 1.2, ..., 1.Z, образующих выходной каскад, y блоков коммутаций 2.1, 2.2, ..., 2.Y, образующих промежуточный каскад, х блоков коммутации 3.1, 3.2, ..., 3.X, образующих входной каскад, n × х информационных входов системы (U.х.n), m × z информационных выходов системы (V.z.m), линии связи (С.х.y) между блоками 3.Х и 2.Y входного и промежуточного каскадов, соединяющие выходы данных блоков 3.Х входного каскада с входами данных блоков 2.Y промежуточного каскада, и линии связи (D.y.z) между блоками 2.Y и 1.Z промежуточного и выходного каскадов, соединяющие соответствующие выходы данных блоков 2.Y с входами данных блоков 1.Z. Рис. 4. Трёхкаскадная КС с параллельным поиском каналов связи На рис. 5 для примера приведена структурная схема пятикаскадной КС с параллельным поиском, она построена из коммутационных блоков двух типов: 32 × 64 для входного каскада, 64 × 32 – для выходного и 64 × 64 – для промежуточных каскадов [4]. Алгоритм работы КС представляет собой вычисление номеров входов в коммутационные блоки всех каскадов КС и состоит из нескольких этапов: – формируется массив данных, содержащий сведения о состоянии КС. При этом пятикаскадная КС условно считается трёхкаскадной. В массиве не существует ячеек с одинаковыми значениями параметра b и разными значениями параметра p; – при поступлении заявки на новое соединение массив проверяется на наличие в одной строке элементов с одинаковым значением b. Если такой элемент находится, то он переписывается на строку ниже, и так до тех пор, пока не найдётся строка, не содержащая подобный элемент. Таким образом, устраняется возможность блокировки в КС; – аналогичные действия проводятся для центрального каскада КС. Заполняется массив данных для трёх промежуточных каскадов. При этом по горизонтали откладывается количество коммутационных блоков выходного каскада (в данном случае это Z). По вертикали откладывается число коммутационных блоков среднего каскада R. Входными и выходными данными считаются результаты, полученные при выполнении предыдущего пункта. Рис. 5. Структурная схема пятикаскадной КС Каждый такт настройки выполняется за два полутакта. В течение первого производится поиск каналов связи через блоки промежуточных каскадов к блокам входного каскада. Во время второго полутакта производится поиск каналов связи к конкретным входам в блоках входного каскада и образование ветвящихся в блоках промежуточного каскада соединений. Максимальное число тактов, за которое должна настроиться вся рассматриваемая КС, равно 64. Отличие КС с параллельным поиском заключается в том, что поиск свободных каналов связи происходит внутри коммутационного поля, за счёт чего усложняется структура КС. Поэтому необходимо сравнить сложность многокаскадных КС и определить, в каком диапазоне числа выходов предпочтительно использовать пятикаскадные КС, а в каком трёхкаскадные структуры. Сравнение многокаскадных коммутационных систем Во всех многокаскадных КС сокращение числа коммутационных точек достигается за счет усложнения соединительных путей. Одновременно с этим увеличивается возможное число соединений для каждой пары «вход – выход» и появляется возможность обхода неисправных или занятых участков системы, т. е. увеличивается надежность всей системы. Чем больше каскадов содержит КС, тем больше каналов связи можно организовать между заданным входом и заданным выходом. Вместе с тем, чем больше число каскадов, тем длиннее соединительный путь от входа к выходу, а значит, больше вероятность появления неисправности в соединительном пути, т. е. меньше надежность системы. Кроме того, с увеличением числа каскадов усложняется процесс установления соединений, а для условно неблокирующих систем – и алгоритм поиска соединительных путей. Но КС с малым числом каскадов имеют приемлемую сложность только до определенных значений числа N входов и M – выходов. При увеличении N и M сложность многокаскадных систем с большим числом каскадов становится меньшей, чем у систем с малым числом каскадов. Более того, начиная с некоторых N, сложность последних резко возрастает и может даже стать большей, чем у матричного коммутатора. Из сказанного видно, что КС трудно характеризовать одновременно сложностью, числом каскадов и простотой установления соединений. Выбор типа КС целесообразно производить в каждом конкретном случае на основе совокупности лишь наиболее важных из указанных характеристик. Коммутационные системы с параллельным поиском строятся на основе базовой трёхкаскадной схемы Клоза [5]. При числе входов системы меньше 32 более выгодными являются матричные схемы. Если число входов более 32, рекомендуется использование трёхкаскадной системы, использование пятикаскадной системы становится выгодным при числе входов более 1 130. При дальнейшем увеличении числа входов необходимо итерационно наращивать систему до 7, 9, 11 и т. д. каскадов. При этом пятикаскадная схема строится из трёхкаскадной путём разложения коммутатора среднего каскада в трёхкаскадную схему, семикаскадная – путём разложения коммутатора третьего каскада пятикаскадной системы в трёхкаскадную схему и т. д. На этом принципе строятся итерационные методы наращивания каскадов в многокаскадных КС. Общее число точек коммутации К в трёхкаскадной неблокирующей полнодоступной системе определяется как , где n – число входов в КБ входного каскада. Минимальное число точек коммутации трехкаскадной неблокирующей схемы вычисляется следующим образом: Сложность пятикаскадной системы можно оценить, определив число ячеек коммутации К в пятикаскадной системе с числом входов N по формуле При дальнейшем увеличении числа входов N более экономичной становится семикаскадная схема и т. д. Если s – число каскадов и t = , то рекомендуется выбирать n = . В этом случае число точек коммутации многокаскадной схемы определяется по формуле К(t) = . Для определения области эффективного использования трёхкаскадных КС с параллельным поиском построены графики зависимости числа точек коммутации от числа входов системы при числе входов в коммутационные блоки входного каскада равным 32 (рис. 6). Рис. 6. Графики зависимости числа точек коммутации от числа входов многокаскадной коммутационной системы: K3(N) – общее число точек коммутации трёхкаскадной КС; K3MIN(N) – минимальное число точек коммутации трёхкаскадной КС; K5(N) – общее число точек коммутации пятикаскадной КС; Kmat(N) – общее число точек коммутации матричной КС Из данного графика можно сделать вывод, что трёхкаскадные КС с параллельным поиском следует использовать при числе входов от 32 до 4 896. Таким образом, трехкаскадная КС обеспечивает значительное уменьшение числа точек коммутации, особенно при большой емкости коммутационной схемы. Однако даже для трехкаскадных коммутационных схем большой емкости число точек коммутации недопустимо велико, поэтому при числе входов от 4 896 следует применять пятикаскадные КС. Заключение В ходе исследования разработаны алгоритмы поиска свободных каналов связи для многокаскадных КС с параллельной настройкой, которые строятся на принципах итерационного наращивания каскадов. Такой принцип построения позволяет увеличить число входов КС и при этом сократить число ячеек коммутации. Алгоритмы параллельной идентификации и параллельного поиска позволяют повысить производительность многопроцессорных вычислительных систем и пропускную способность сетей передачи данных соответственно. Предлагаются критерии, по которым подбирается та или иная схема КС с параллельной настройкой. При выборе типа КС руководствуются одной характеристикой – сложностью системы и для выбранной системы разрабатывают приемлемый по сложности и обеспечивающий определенное качество поиска соединительных путей алгоритм.
1. Подлазов В. С. Параллельная бесконфликтная самомаршрутизация в сетях Бенеша // Тр. I Рос. конф. с междунар. участием «Технические и программные средства управления, контроля и измерения». - М.: ИПУ РАН, 2010. - С. 926-930.
2. Барабанова Е. А., Мальцева Н. С. Алгоритмы работы коммутационных систем с параллельной настройкой // Вестн. Астрахан. гос. техн. ун-та. Сер.: Управление, вычислительная техника и информатика. - 2011. - № 1. - С. 150-156.
3. Пат. 2359313 Рос. Федерация: МПК G06F 7/00. Трёхкаскадная коммутационная система / Жила В. В., Барабанова Е. А., Мальцева Н. С. (RU). № 2007107780/09; заявл.01.03.2007; опубл. 20.06.2009; Бюл. № 17.
4. Барабанова Е. А., Мальцева Н. С., Полина О. Н. Алгоритм параллельного поиска для пятикаскадной коммутационной системы // Вестн. Астрахан. гос. техн. ун-та. Сер.: Управление, вычислительная техника и информатика. - 2011. - № 2. - С. 107-113.
5. Подлазов В. С., Соколов В. В. Обобщенные сети Клоза // Автоматика и телемеханика. - 2009. - № 10. - С. 158-170.
