DEVELOPMENT OF UNIVERSAL ALGORITHM FOR MULTISTAGE SWITCHES WITH PARALLEL ADJUSTMENT
Authors:
1.
V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences
(Doctor of Technical Sciences, Assistant Professor; Leading Researcher of the Laboratory of Network Systems Control)
Moscow, Russian Federation
Moscow, Russian Federation
2.
Astrakhan State Technical University
(Candidate of Sciences in Technology, Assistant Professor; Assistant Professor of the Department of Radio Communication)
3.
Astrakhan State Technical University
Type:
Article
Pages:
from 118
to 125
Status:
Published
Received:
05.01.2013
Accepted:
25.01.2013
Published:
25.01.2013
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 621.394.6:004.7
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
BBK 32.882-52:32.988
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 621.394.6:004.7
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
BBK 32.882-52:32.988
Language:
Russian
Keywords:
multistage switching system, parallel searching, parallel identification, algorithm, switching block, switching cell
Abstract (English):
The schemes and algorithms of multistage switching systems with parallel adjustment are the subject of the study. The aim of the study is to develop a universal algorithm of multistage switching system with parallel adjustment for its using in packet-switched networks. Multistage switches with parallel adjustment are configurated on an iterative principle of building stages. The new algorithms of multistage switches with parallel adjustment are based on the principle of expansion of the central stage into the three-stage system and the basic algorithm of searching of free communication channels within a three-stage scheme.
The schemes and algorithms of multistage switching systems with parallel adjustment are the subject of the study. The aim of the study is to develop a universal algorithm of multistage switching system with parallel adjustment for its using in packet-switched networks. Multistage switches with parallel adjustment are configurated on an iterative principle of building stages. The new algorithms of multistage switches with parallel adjustment are based on the principle of expansion of the central stage into the three-stage system and the basic algorithm of searching of free communication channels within a three-stage scheme.
Keywords:
multistage switching system, parallel searching, parallel identification, algorithm, switching block, switching cell
multistage switching system, parallel searching, parallel identification, algorithm, switching block, switching cell
Введение Главной задачей при разработке современных коммутаторов является увеличение пропускной способности оборудования. Коммутационная техника в настоящее время использует высокоскоростные интерфейсы, а производительность внутренней коммутационной матрицы может достигать десятков гигабит в секунду. В магистральных сетях передачи данных к производительности коммутационных устройств предъявляются ещё более жёсткие требования. Традиционно производители коммутационного оборудования используют в качестве коммутирующей среды матричный коммутатор, основное достоинство которого – простота конструкции, а недостаток – ограничение на число входов, т. к. при увеличении числа входов сложность системы резко возрастает. Выход из сложившейся ситуации – использование трех и более каскадных схем, которые позволяют добиться увеличения пропускной способности системы, но при меньших затратах [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. Podlazov V. S. Parallel'naya beskonfliktnaya samomarshrutizaciya v setyah Benesha // Tr. I Ros. konf. s mezhdunar. uchastiem «Tehnicheskie i programmnye sredstva upravleniya, kontrolya i izmereniya». - M.: IPU RAN, 2010. - S. 926-930.
2. Barabanova E. A., Mal'ceva N. S. Algoritmy raboty kommutacionnyh sistem s parallel'noy nastroykoy // Vestn. Astrahan. gos. tehn. un-ta. Ser.: Upravlenie, vychislitel'naya tehnika i informatika. - 2011. - № 1. - S. 150-156.
3. Pat. 2359313 Ros. Federaciya: MPK G06F 7/00. Trehkaskadnaya kommutacionnaya sistema / Zhila V. V., Barabanova E. A., Mal'ceva N. S. (RU). № 2007107780/09; zayavl.01.03.2007; opubl. 20.06.2009; Byul. № 17.
4. Barabanova E. A., Mal'ceva N. S., Polina O. N. Algoritm parallel'nogo poiska dlya pyatikaskadnoy kommutacionnoy sistemy // Vestn. Astrahan. gos. tehn. un-ta. Ser.: Upravlenie, vychislitel'naya tehnika i informatika. - 2011. - № 2. - S. 107-113.
5. Podlazov V. S., Sokolov V. V. Obobschennye seti Kloza // Avtomatika i telemehanika. - 2009. - № 10. - S. 158-170.
