MODEL OF CALCULATING DIFFICULTY OF NEW GENERATION OPTICAL COMMUTATION SYSTEMS
Authors:
1.
Astrakhan State Technical University
2.
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
3.
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)
Russian Federation
Russian Federation
Type:
Article
Pages:
from 34
to 43
Status:
Published
Received:
05.07.2019
Accepted:
25.07.2019
Published:
25.07.2019
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.391.64
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 621.391.64
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
optical switch, non-blocking capacity, self-routing, multi-stage scheme, switching difficulty
Abstract (English):
The article presents the analysis of various circuits of the multistage switching systems and their main characteristics. The model of calculating the complexity of the new generation optical switching systems based on 4x4 switches has been developed. These switching systems have a new property, which no one multi-stage scheme possesses: the strict non-blocking capacity with parallel data transfer and arbitrary packet swapping. There has been compared the difficulty of the proposed systems, such as the switching difficulty of the base element and the diameter with well-known multi-stage schemes. The analysis showed that the optical switching systems of the new generation have an advantage - a fewer number of cascades.
The article presents the analysis of various circuits of the multistage switching systems and their main characteristics. The model of calculating the complexity of the new generation optical switching systems based on 4x4 switches has been developed. These switching systems have a new property, which no one multi-stage scheme possesses: the strict non-blocking capacity with parallel data transfer and arbitrary packet swapping. There has been compared the difficulty of the proposed systems, such as the switching difficulty of the base element and the diameter with well-known multi-stage schemes. The analysis showed that the optical switching systems of the new generation have an advantage - a fewer number of cascades.
Keywords:
optical switch, non-blocking capacity, self-routing, multi-stage scheme, switching difficulty
optical switch, non-blocking capacity, self-routing, multi-stage scheme, switching difficulty
Оптические сети являются неотъемлемой частью современных систем телекоммуникаций. Достоинства оптических сетей очевидны: это и высокие скорости обработки сигналов при коммутации, и высокая защищенность при передаче данных. Разработка оптических коммутаторов является необходимой и актуальной задачей в области волоконно-оптических технологий [1]. Внедрение полностью оптических коммутаторов станет следующим этапом развития оптических сетей связи и будет способствовать решению широкого ряда телекоммуникационных задач. Поэтому анализ технологий построения оптических коммутаторов, а также разработка моделей для расчета их параметров являются актуальными задачами. Традиционные оптические коммутаторы используют в качестве коммутирующей среды матричный коммутатор, основное достоинство которого - простота конструкции, а недостаток - ограничение на количество входов и выходов, т. к. при увеличении количества входов увеличивается сложность коммутационной системы. Использование технологий построения многокаскадных коммутаторов позволяет строить коммутаторы большого размера, при этом их сложность существенно ниже сложности матричных коммутаторов. На сегодняшний день известны различные технологии построения полностью оптических коммутаторов, среди них наибольшим быстродействием обладают электрооптические коммутаторы [2]. Технологии электрооптической коммутации, а также многокаскадного построения лежат в основе архитектуры оптических коммутаторов нового поколения [3-5]. Особенностью данных систем является самомаршрутизация и неблокируемость при параллельной передаче данных и произвольных перестановках. Важным вопросом при проектировании такого рода коммутационных систем является расчет сложности схем, т. к. схемы, обладающие меньшей сложностью, при одинаковом наборе функций являются более надежными и имеют большее быстродействие. Различают несколько методик расчета сложности схем, среди них наиболее простыми являются методы, основанные на синтезе функциональных элементов, и метод К. Э. Шеннона для контактных схем [6]. В данном исследовании проводится анализ сложностей оптических коммутационных схем на основе метода синтеза схем из функциональных элементов и разрабатывается модель для расчета сложности оптического коммутатора нового поколения для систем связи. Характеристика многокаскадных оптических коммутаторов Многокаскадные оптические коммутаторы характеризуются рядом параметров, наиболее важными из которых являются [7, 8]: - число базовых элементов, которое напрямую влияет на стоимость коммутатора, его надежность и быстродействие; - число каскадов коммутатора (диаметр), которое влияет на его быстродействие и уровень сигнала; - доступность, означающая степень доступности входов коммутатора его выходам. В случае, когда любому входу доступен любой выход, система является полнодоступной; - вид блокировки, по которому все многокаскадные коммутаторы делятся на блокирующие или неблокирующие. Коммутатор называется неблокирующим, если любой незанятый входной порт может быть соединен с любым неиспользуемым выходным портом, в противном случае (т. е. если какое-то соединение не может быть установлено) коммутатор является блокирующим. В свою очередь, неблокирующие коммутаторы делятся: - на коммутаторы неблокирующие в строгом смысле, т. е. такие неблокирующие коммутаторы, которые при использовании любой процедуры соединения не требуют переустановления уже имеющегося канала связи; - перестраиваемые неблокирующие коммутаторы, т. е. такие неблокирующие коммутаторы, которые в любом случае требуют перемаршрутизации какого-то из соединений. При построении полностью оптических коммутационных систем свойство строгой неблокируемости является обязательным, т. к. любое перестроение требует участия внешнего управляющего устройства, а значит, применения специального алгоритма перестроения. Анализ многокаскадных схем оптических коммутаторов Рассмотрим четыре основные схемы, которые могут быть использованы в каскадных оптических коммутаторах большого размера: схему Клоза, схему Бенеша, схему Шпанке, схему Шпанке - Бенеша. Схема Клоза - вид многокаскадной схемы, впервые формально описанной Чарльзом Клозом в 1953 г. Клоз показал, что многокаскадный коммутатор, содержащий не менее 3-х каскадов, может обладать характеристиками неблокирующей сети. Он доказал следующее: чтобы трехкаскадный коммутатор имел неблокирующую архитектуру, необходимо выполнение условия , где k - число коммутаторов среднего каскада, n - число входов в один коммутационный блок входного каскада [7] (рис. 1, а). Рис. 1. Схемы построения многокаскадных коммутационных систем: схема Клоза (а); схема Бенеша (б); схема Шпанке (в); схема Шпанке - Бенеша (г) В общем виде схема Клоза является блокируемой, т. к. при параллельной передаче данных и произвольных перестановках даже при выполнении вышеуказанного условия в системе могут возникнуть блокировки. Для частного случая схемы Клоза, схемы Бенеша (рис. 1, б), такой блокировки можно избежать, используя алгоритмы перестроения, т. е. перемаршрутизации предыдущего соединения для установления нового и сохранения старого каналов связи. Но на сегодняшний день не существует алгоритмов, решающих вышеуказанную задачу. Разновидностью многокаскадных схем, построенных на простых базовых элементах, являются также схемы Шпанке и Шпанке - Бенеша [8] (рис. 1, в, г). Преимуществом данных схем является то, что для их построения используются простые коммутационные элементы 1 × 2 и 2 × 2, а недостатком - большие сложность и диаметр при большом числе входов. Кроме этого, данные схемы являются блокируемыми при параллельной передаче данных и произвольных перестановках. Модель оценки сложности оптической коммутационной системы нового поколения В данном разделе представлена модель оптической коммутационной системы нового поколения, схема и принцип работы раскрывались авторами ранее в [5]. Структурная схема коммутатора 4 × 4 показана на рис. 2. Рис. 2. Оптический коммутатор 4 × 4 нового поколения: ОИУ - оптическое интегральное устройство; ФБ - фильтр Брэгга; ЧД - частотный детектор; ФУС - формирователь управляющего сигнала; ЛЗ - линии задержки Особенностью данных схем является то, что предлагаемые коммутационные устройства являются самонастраивающимися. Для этого в состав устройств помимо непосредственно коммутационного элемента входят устройства управления: оптическое интегральное устройство, фильтр Брэгга, частотный детектор, формирователь управляющего сигнала. Это позволяет использовать алгоритмы самомаршрутизации, т. е. использовать управляющую информацию, содержащуюся в пакете для настройки схемы, без обращения к внешнему устройству управления. Линии задержки обеспечивают неблокируемость соединений. Для создания модели представим схему коммутатора 4 × 4 в виде упрощенной схемы, которая содержит последовательно соединенные мультиплексор (MUX 4) на 4 входа и демультиплексор (DMUX 4) на 4 выхода (рис. 3). Рис. 3. Обобщенная схема оптического коммутатора 4 × 4 нового поколения В данном случае мультиплексор является обобщением оптического интегрального устройства, а демультиплексор - отклоняющей системы. Для создания модели базового элемента разработанной коммутационной системы используется один из методов синтеза схем из функциональных элементов & (И), v (ИЛИ) и (НЕ), основанный на моделировании СДНФ (совершенной дизъюнктивной нормальной формы). Элементы, которым сопоставлены функции булевой алгебры & (И), v (ИЛИ) и (НЕ), называются конъюнктером, дизъюнктером и инвертором соответственно. Представим функции, которые могут определять выход мультиплексора М4 коммутатора 4 × 4 с учетом работы линии задержки ЛЗi, следующими выражениями: где λ1 и λ2 - управляющие сигналы. Представим функции на выходах демультиплексора Д4 коммутатора 4 × 4 следующими выражениями: Рассмотрим каждую конъюнкцию и определим ее сложность. Веса элементов предполагаются равными единице. Сложность схемы определяется числом элементов, из которых состоит базовый элемент. Для наглядности представим первую конъюнкцию в виде схемы, которая состоит из двух инверторов и двух конъюнкций (рис. 4). Рис. 4. Схема конъюнкции Аналогично можно представить в виде схем и другие конъюнкции. При этом максимальная сложность одной конъюнкции будет равна 4 (S()) = 4, где S - сложность схемы; -совершенная дизъюнктивная нормальная форма. Пусть xn = f / (, l1, l2), а v v v - это ее совершенная дизъюнктивная нормальная форма. Схема f/ строится из цепочки из m конъюнкций и цепочки из m-1 дизъюнкторов (цепочка имеет m входов) (рис. 5) и объединяет выходы схем конъюнкций, ее сложность будет равна S4 = 4 ∙ m + 3 = 4 ∙ 4 + 3 = 16 + 3 = 19. Рис. 5. Схема функции xn = f/ () Аналогично можно представить в виде схем и конъюнкции, из которых строятся функции yn. При этом максимальная сложность одной конъюнкции Kn будет равна 19 + 4 = 23 (рис. 6). Рис. 6. Схема конъюнкции Пусть yn = f (xn, l1, l2), а K1 v K2 v K3 v K4 - это ее совершенная дизъюнктивная нормальная форма. Схема f строится из цепочки из m конъюнкций Ki и цепочки из m-1 дизъюнкторов (цепочка имеет m входов) и объединяет выходы схем конъюнкций (рис. 7). Рис. 7. Схема функции y1 Сложность представленной схемы можно определить следующим образом: S4 = 4 ∙ m + 3 = = 4 ∙ 23 + 3 = 92 + 3 = 95 ~ 96. Таким образом, сложность одного базового элемента равна 96, что составляет примерно 6N2. Используем вышеописанную методику для расчета сложности базового элемента многокаскадных систем типа Шпанке, Шпанке - Бенеша, в основе которых лежат базовые элементы 2 × 2. Будем считать, что схемы имеют два входа (х1 и x2) и два выхода (y1 и y2) и управляются одним сигналом: На рис. 8 представлена логическая схема, реализующая один выход. Рис. 8. Схема функции Из схемы следует, что число логических элементов, используемых для ее построения, равно 4. Учитывая количество логических функций, описывающих выходы y1 и y2, сложность схем можно оценить как 4 + 4 = 8. Если использовать данный базовый элемент для построения, например, схемы Бенеша 4 × 4 (см. рис. 1, б), то сложность такой схемы составит 6 ∙ 8 = 48. Таким образом, сложность базового элемента коммутатора 4 × 4 нового поколения [4] в 2 раза превышает сложность коммутатора 4 × 4, построенного на элементах 2 × 2. Это объясняется наличием устройств управления внутри коммутатора 4 × 4, что позволяет использовать принцип самомаршрутизации и обеспечивает неблокируемость схемы. Оценим диаметр многокаскадных схем, построенных на основе предлагаемого коммутатора 4 × 4, и сравним его с диаметром известных более простых коммутационных схем. В таблице представлены конкретные значения диаметра коммутационных систем с числом входов 4, 16, 256. Значения диаметра коммутационных систем на 4, 16 и 256 входов Коммутационная схема Число входов 4 16 256 Схема Бенеша 3 7 15 Схема Шпанке 4 8 16 Схема Шпанке - Бенеша 4 16 256 Предлагаемые схемы на основе элементов 4 × 4 1 2 4 Анализируя данные, представленные в таблице и на рис. 9, можно сделать вывод, что диаметр предлагаемых оптических коммутационных схем в 3-3,75 раз меньше диаметра известных многокаскадных коммутационных систем. В частности, при числе входов и выходов N = 256 диаметр k предлагаемой двухкаскадной схемы будет примерно в 4 раза меньше схемы Шпанке и в 64 раза меньше схемы Шпанке -Бенеша. При этом необходимо отметить, что предлагаемые схемы являются строго неблокируемыми в отличие от более простых известных схем. Заключение В данной работе впервые разработана модель для оценки сложности оптических многокаскадных коммутационных систем нового поколения. Модель описывает функционирование базового элемента 4 × 4 таких систем, состоящего из мультиплексора 4 × 1 и демультиплексора 1 × 4 на основе функций булевой алгебры. Отметим, что до сегодняшнего дня вообще не существовало моделей и методик расчета параметров подобных неблокируемых схем, поскольку возможность построения коммутационных систем на их основе была показана только в 2018 г. [3, 5]. Из результатов расчета в соответствии с построенной моделью следует, что сложность предлагаемого 4 × 4 базового элемента в 2 раза больше сложности базовых элементов типовых коммутационных схем, таких как схемы Шпанке, Шпанке - Бенеша, Бенеша. Более высокое значение сложности предлагаемых элементов объясняется наличием в них собственных устройств управления, позволяющих впервые реализовать принцип самомаршрутизации и параллельной передачи данных. Другими словами, неблокируемость анализируемой коммутационной схемы обеспечивается за счет повышения ее сложности. Однако сложность предлагаемых многокаскадных схем в целом (а именно диаметр этих схем) имеет существенные преимущество, поскольку они содержат существенно меньшее число каскадов по сравнению с известными схемами.
1. Slepov N. N. Sovremennye tehnologii cifrovyh optovolokonnyh setey svyazi (ATM, PDH, SDH, SONET i WDM). M.: Radio i svyaz', 2003. 468 s.
2. Testa F., Pavesi L. Optical Switching in Next Generation Data Centers. Springer International Publishing AG, 2008. P. 336.
3. Barabanova E. A. Opticheskaya dvuhkaskadnaya kommutacionnaya sistema dlya obrabotki bol'shih ob'emov dannyh // Nauch. vestn. Novosib. gos. tehn. un-ta. 2018. № 1 (70). S. 7-18. DOI: http://dx.doi.org/https://doi.org/10.17212/1814-1196-2018-1-7-18.
4. Barabanova E. A., Vytovtov K. A., Maltseva N. S., Kravchenko O. V., Kravchenko V. F. Models and algorithms of optical switching systems with decentralized control // 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (Moskva, Sankt-Peterburg, 28-31 yanvarya 2019 g.). Institute of Electrical and Electronics Engineers, 2019. S. 64-68.
5. Barabanova E. A., Nguen Chong Than'. Fotonnaya kommutacionnaya yacheyka na osnove metamateriala // Informacionnye tehnologii i tehnologii kommunikacii: sovremennye dostizheniya: materialy II Mezhdunar. molodezh. konf. (Astrahan', 10 sentyabrya 2018 g.). URL: https://elibrary.ru/item.asp?id =36373647 (data obrascheniya: 15.04.19).
6. Lupanov O. B. Asimptoticheskie ocenki slozhnosti upravlyayuschih sistem. M.: Izd-vo Mosk. un-ta, 1984. 138 s.
7. Hawang F. K., Hwang F. Mathematical Theory // World Scientific Publishing Company. 2004. P. 200.
8. Rudenko D. V. Strukturnye harakteristiki opticheskih kommutatorov. Problemy upravleniya // Mir transporta. 2012. № 4. S. 124-129.
9. Hwang F. K. A Survey of Nonblocking Multicast Three-Stage Clos Networks // IEEE Communications Magazine. 2003. N. 41 (10). P. 34-37.
