Содержание к диссертации
Введение
Глава 1. Обзор способов построения и алгоритмов работы коммутаторов сетей передачи данных 15
1.1 Анализ архитектур коммутаторов сетей передачи данных 15
1.1.1 Общая шина 15
1.1.2 Коммутаторы с разделяемой памятью 17
1.1.3 Коммутатор с полносвязной топологией 18
1.1.4 Матричные коммутаторы : 19
1.2 Анализ алгоритмов работы многокаскадных схем 20
1.2.1 Особенности процесса установления соединений 20
1.2.2 Многокаскадные схемы коммутации для СПД 25
1.2.3 Баньяноподобные коммутационные структуры 30
1.3 Патентный анализ многокаскадных коммутационных систем 32
1.4 Постановка задачи исследования: 46
Выводы по первой главе: 49
Глава 2. Формализованное описание структуры и алгоритма работы трехкаскадной коммутационной системы для сетей передачи данных 51
2.1 Задание структуры трехкаскадной коммутационной системы 51
2.2 Разработка алгоритма работы трехкаскадной коммутационной системы 57
2.3 Описание алгоритма работы трехкаскадной коммутационной системы... 63
Выводы по второй главе 67
Глава 3 Разработка функциональных схем элементов трехкаскадной коммутационной системы с параллельным поиском каналов связи 68
3.1 Функциональные схемы коммутационных блоков 68
3.2 Функциональные схемы ячеек коммутации 73
3.3 Процесс функционирования трехкаскадной коммутационной системы... 78
3.4 Технический результат разработки трехкаскадной коммутационной системы 90
3.5 Рекомендации по выбору технологии изготовления трехкаскадной коммутационной системы 94
Выводы по третьей главе: 99
Глава 4 Экспериментальные исследования работы трехкаскадной коммутационной системы 101
4.1 Имитационное моделирование работы ячеек коммутации 101
4.1.1 Анализ работы ячейки коммутации выходного каскада 102
4.1.2 Анализ работы ячейки коммутации промежуточного каскада 105
4.1.3 Анализ работы ячейки коммутации входного каскада 107
4.2 Имитационное моделирование алгоритма работы трехкаскадной коммутационной системы 108
4.2.1 Структура программы моделирования коммутационной системы 108
4.2.2 Моделирование структуры коммутационной системы 111
4.2.3 Случайное генерирование команд коммутации : 111
4.2.4 Моделирование процесса коммутации 113
4.2.5 Расчёт характеристик качества обслуживания КС 119
4.2.6 Сравнительный анализ работы КС 126
Выводы по четвёртой главе 131
Заключение 133
Библиографический список 136
Приложения
- Коммутаторы с разделяемой памятью
- Разработка алгоритма работы трехкаскадной коммутационной системы
- Функциональные схемы ячеек коммутации
- Анализ работы ячейки коммутации выходного каскада
Введение к работе
Экономическая эффективность- сети передачи данных зависит от суммарной стоимости услуг, предоставляемых этой сетью. Данная величина определяется пропускной способностью сети, которая, в свою очередь, зависит от возможностей коммутационного оборудования.
Пропускная способность коммутаторов сетей передачи данных характеризуется следующими параметрами: ёмкостью коммутационной системы (КС), скоростью передачи пакетов и скоростью коммутации.
Вопросом повышения скорости передачи пакетов активно занимаются разработчики коммутационного оборудования многих стран мира, которые стремятся повысить пропускную способность своих систем за счёт новых и порою недоступных на сегодняшний день технологий [17,27,58,59,80]. Скорости коммутации, под которой подразумевается время установления соединений, напротив, уделяется недостаточное внимание.
Вопросам разработки архитектуры и алгоритма работы КС, от которых зависит скорость коммутации, посвящен ряд работ российских и зарубежных учёных: В.В. Жилы, Н.И. Витиски, О.Б. Макаревича, А.В. Каляева, В.И. Кодачигова, К.Е. Batcher, С.A. Closs, V.E. Benes и др. [25-26, 31-32, 35-38, 69-79]. Анализ данных исследований позволяет сделать вывод о том, что существенное преимущество в скорости установления соединений имеют алгоритмы параллельного поиска каналов связи.
Известные в настоящее время КС с параллельным принципом установления соединений (коммутатор Баньяна, сортирующие схемы), используемые для построения коммутаторов сетей передачи данных, работают в режиме разовой коммутации, предполагающем чёткое разделение во времени процесса установления соединений и передачи пакетов [18,24,28]. Это служит ограничением дальнейшего роста пропускной способности таких коммутаторов.
Не позволяют добиться высокой пропускной способности и существующие КС сетей передачи данных с последовательным принципом
б установления соединений, к которым относят коммутаторы с разделяемой памятью и общей средой передачи (шиной). Для коммутаторов с разделяемой памятью критическим параметром является скорость обращения к запоминающему устройству, а для общей шины — её пропускная способность. Эти параметры ограничивают масштабируемость и пропускную способность таких коммутаторов.
В связи с вышеизложенным возникает необходимость в разработке научных основ создания и исследования общих свойств и принципов функционирования элементов коммутационных систем с параллельным принципом установления соединений, использование которых позволит повысить пропускную способность и масштабируемость коммутационного оборудования сетей передачи данных.
В качестве исследуемых элементов коммутации предлагается использовать коммутационные блоки трёхкаскадных коммутационных систем, выбор которых обуславливается требованием меньшего числа коммутационных элементов для построения трёхкаскадной КС, по сравнению с матричными коммутаторами при одинаковом числе входов.
Актуальность данной тематики подтверждается ее соответствием утвержденным 21.05.2006 г. Президентом Российской Федерации приоритетным направлениям развития телекоммуникационных систем (№ Пр-843).
Целью работы является повышение пропускной способности сетей передачи данных за счёт использования коммутационного оборудования, позволяющего совмещать процесс параллельного установления соединений с передачей пакетов.
Задачи исследования. Для достижения цели в диссертационной работе решены следующие задачи:
- проведен сравнительный анализ существующих архитектур коммутаторов сетей передачи данных, а также используемых ими алгоритмов установления соединений, определены достоинства и недостатки;
,1
разработано формализованное описание структуры трёхкаскадной КС и алгоритма её работы;
разработаны функциональные схемы элементов трёхкаскадной КС, позволяющие осуществлять процесс параллельного установления соединений совместно с передачей пакетов;
проведены экспериментальные исследования работы трёхкаскадной КС с целью доказать корректность разработанных функциональных схем, определить основные характеристики работы КС и указать область её эффективного использования.
Объектом исследования является трёхкаскадная КС и её элементы коммутации - коммутационные блоки (КБ).
Предметом исследования является алгоритм работы трёхкаскадной КС, позволяющий производить процесс параллельного установления соединений совместно с передачей пакетов.
Методы исследований. Исследования, проводимые в работе, базируются на принципах построения и проектирования функциональных устройств цифровой и вычислительной техники, теории множеств, теории телетрафика.
Исследование процесса функционирования разработанных элементов коммутации проводилось с использованием специально разработанной программы в среде программирования Visual Basic for Applications на базе методов статистического моделирования. Для математической обработки
результатов экспериментов использовались методы математической статистики и теория погрешностей.
Научная новизна работы:
- предложен метод параллельного поиска каналов связи в КС с
децентрализованным управлением, отличающийся от известных реализацией
процесса установления соединений совместно с передачей пакетов, что
позволит повысить пропускную способность коммутаторов сетей передачи
данных;
8 t
предложен алгоритм поиска каналов в трёхкаскадной КС, базирующийся на теоретико-множественной модели функционирования устройства;
разработана имитационная модель, реализующая алгоритм функционирования трёхкаскадной КС, согласно которому процесс параллельного установления соединений совмещён с передачей пакетов.
На защиту выносятся следующие положения:
алгоритм работы трёхкаскадной КС на базе аппарата теории множеств, согласно которому процесс параллельного установления соединений совмещён с передачей пакетов;
функциональные схемы элементов трёхкаскадной КС, позволяющей осуществлять процесс параллельного установления соединений совместно с передачей пакетов по уже установленным каналам связи;
метод параллельного поиска каналов связи в КС с децентрализованным управлением, согласно которому процесс установления соединений совмещён с передачей пакетов, поступающих в случайные моменты времени;
имитационная модель трёхкаскадной КС, позволяющая определить зависимости пропускной способности КС от основных параметров её структуры и характеристик входного потока пакетов, а также провести сравнение результатов работы предложенного алгоритма с известными алгоритмами работы КС сетей передачи данных.
' Практическая ценность работы. Предложены функциональные схемы элементов коммутации трёхкаскадной КС и алгоритм их работы, использование которых в построении коммутационного оборудования сетей передачи данных позволит повысить пропускную способность последнего в среднем в 2 раза за счёт совмещения процесса, параллельного установления соединений с передачей пакетов.
Программа, написанная для исследования процесса функционирования разработанных элементов коммутации, может применяться в учебном процессе
при изучении специальных дисциплин студентами специальностей 210406.65 «Сети связи и системы коммутации», и 210402.65 «Средства связи с подвижными объектами».
Результаты диссертационной работы использованы на практике в учебном процессе Астраханского государственного технического университета.
Апробация работы. Основные результаты работы докладывались и обсуждались на: II Всероссийской конференции с международным участием «Инфокоммуникационные и вычислительные технологии и системы» (Улан-Удэ, 2006); Российской школе-конференции «Мобильные системы передачи данных» с участием молодых учёных и преподавателей (Москва,2006); XIX Международной научной конференции «Математические методы в технике и технологиях» (Воронеж, 2006); XX Международной научной конференции «Математические методы в технике и технологиях» (Ярославль, 2007); на научно-технических конференциях профессорско-преподавательского состава Астраханского государственного технического университета (Астрахань, 2005— 2008).
Работа выполнена в соответствии: с госбюджетными научно-исследовательскими работами Астраханского государственного технического университета по теме исследований «Анализ и синтез элементов и устройств телекоммуникационных, информационно-измерительных систем и систем управления». Научный руководитель - д-р техн. наук Дмитриев В.Н. ГР № 01.2.006 08076, Астрахань АГТУ, 2005-2006 гг.; с госбюджетной научно-исследовательской работой Московского государственного института электронной техники по теме исследований «Качество обслуживания мобильных систем передачи данных» в 2006 г. (выигран грант).
Публикации. По теме диссертации опубликовано 10 печатных работ, в том числе 4 - в журналах по списку ВАК; Зарегистрирован 1 программный продукт в реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам. Без соавторства опубликовано 4
работы. По результатам исследований подана заявка на изобретение «Трёхкаскадная коммутационная система» № 2007107780 от 01.03.07.
Структура и объем работы. Диссертация содержит 144 страниц машинописного текста, 56 рисунков, 8 таблиц и состоит из введения, 4 глав, заключения, списка литературы из 92 наименований и приложения на 15 листах.
Краткое содержание:
Во введении обоснована актуальность темы диссертационной работы, сформулированы цели и задачи исследования, показана научная новизна и практическая значимость результатов, указаны основные положения, выносимые на защиту, проводится краткий обзор структуры работы.
В первой главе выполнен обзор способов построения коммутаторов сетей передачи данных. В результате анализа возможных топологий коммутационных систем сделан вывод о том, что наиболее эффективным с точки зрения организации параллельных процессов является пространственный коммутатор, позволяющий реализовать все варианты соединения устройств сетей передачи данных между собой.
Простейшим примером пространственных коммутаторов является коммутационная матрица. Однако недостаток матричных коммутаторов — большое число коммутирующих элементов, а именно, N", где N - число входов в коммутатор. Поэтому КС, с числом входов более 64, экономичнее выполнять в виде многокаскадной схемы, частным случаем которой является трёхкаскадная КС.
Данная работа посвящена разработке и исследованию элементов коммутации, использующих принципы децентрализованного управления. Это позволяет: разгрузить ЦУУ за счёт обработки настроечной информации в самом коммутационном поле; уменьшить объём памяти ЦУУ, так как исключается необходимость хранения таблиц занятости промежуточных путей КС.
В данной работе предлагается использовать параллельный способ настройки элементов коммутации, .что позволяет значительно повысить скорость поиска каналов связи.
В результате анализа литературных источников, патентной информации, открытой технической документации разработчиков коммутаторов ведущих стран (Россия, США, Япония, страны Евросоюза) за 25 лет, можно сделать вывод о том, что:
В сетях передачи данных для обеспечения полнодоступной неблокирующей коммутации в качестве коммуникационной среды рекомендуется использовать многокаскадные КС преимущественно с децентрализованной настройкой (баньяновидные, сортирующие схемы);
Использование метода параллельного установления соединений позволяет значительно повысить пропускную способность сетей ПД;
' 3) Использование режима децентрализованного управления элементами коммутации является перспективным с точки зрения возрастания емкости КС и соответственно увеличения нагрузки на ЦУУ, а также с точки зрения реализации элементов коммутации в виде интегральной схемы.
Большинство KCf с параллельным принципом установления соединений работают в разовом режиме коммутации.
Известен алгоритм и схемотехническое решение [2], позволяющие производить параллельную настройку трёхкаскадных коммутационных систем с децентрализованным управлением в разовом режиме, однако они не могут быть применены для параллельной настройки таких систем в том случае, если требования на обслуживание поступают в случайные моменты времени.
В результате проведённого анализа предметной области поставлена задача исследования: разработать алгоритм параллельного поиска каналов связи, согласно которому ^процесс установления соединений происходит совместно с передачей пакетов, а также функциональные схемы элементов трехкаскаднои коммутационной системы, реализующих данный алгоритм
поиска, с целью повысить пропускную способность коммутационного оборудования сетей передачи данных. :
Вторая глава посвящена разработке алгоритма работы трёхкаскадной КС.
Для формализованного описания структуры трёхкаскадной КС используется аппарат теории множеств. Разработка алгоритма, позволяющего совмещать процесс параллельного установления соединений с передачей пакетов, проводится на основе матричного способа задания структуры КС.
Для описания алгоритма работы КС задаются следующие матрицы: трёхмерная матрица AF, моделирующая структуру буферных запоминающих устройств, в которую записываются команды коммутации, поступающие на выходы КС. Одна координата матрицы соответствует номеру пакета в очереди данного выходов КС (и), вторая — номеру коммутационных блоков (КБ) промежуточного каскада (у), третья — номеру КБ выходного каскада (z).
В каждую позицию матрицы, соответствующую одному и тому же номеру выхода КС ц- и расположенную на пересечении строки 'у =1,7 и столбца z =l,Z, записываются элементы a(y,z) = (х,п), представляющие собой команды коммутации.
Распределение команд коммутации по КБ промежуточного каскада сводится к построению двумерной матрицы команд коммутации Ак, соответствующей одному из состояний КС (а именно в данный такт процесса установления соединений).
При этом все элементы матрицы Ак удовлетворяют следующим ограничениям: число записей в каждом столбце не может превышать числа т, т.е. количества выходов в одном КБ выходного каскада; одинаковые записи не могут более одного раза встречаться в одном столбце.
Вводится матрица А*к. Матрица А*к отличается от матрицы Ак тем, что ее элементы a (y,z)=(x,n) должны удовлетворять следующему третьему ограничению: в этой матрице не допускаются пересечения каналов связи в промежуточном каскаде. Вводится матрица А'^, ненулевые элементы которой
'13
на шаге / принадлежат также матрице Ак , но не принадлежат матрице А*к. Начальной информацией для работы алгоритма служит программа коммутации Р, определяющая номер входа, с которым необходимо соединить соответствующий выход.
Третья глава посвящена разработке структуры трёхкаскадной КС с параллельным поиском каналов связи и описанию её работы.
Предлагаемая КС содержит z элементов коммутации 1.1,1.2,...,1.Z, образующих выходной каскад, у элементов коммутации 2.1,2.2,...,2.7, образующих промежуточный каскад, х элементов коммутации 3.1, 3.2,.,.,3 Jf, образующих входной каскад. Элементы коммутации в данном случае представляют собой коммутационные блоки (КБ).
В известной трёхкаскадной КС с параллельныой настройкой для установления соединений применяется разовый режим коммутации, в соответствии с которым система функционирует в три этапа: 1ьш этап-настройка схемы; 2ой этап-передача информации; Зии этап-разборка каналов связи.
' На этапе процесса установления: соединений осуществляется поиск свободных промежуточных путей, на втором этапе происходит передача полезной информации по настроенным каналам связи. При этом новый этап установления соединений может начаться только после окончания процесса передачи всеми устройствами.
Предлагаемая трехкаскадная КС с параллельным поиском каналов связи может работать в трех режимах: в режиме установления соединений, при котором производится поиск и фиксация каналов связи, в режиме передачи информации и в режиме разборки каналов связи, ставших ненужными. При этом новый этап установления соединений может происходить совместно с передачей пакетов и разборки каналов связи.
Новое свойство системы заключается в возможности параллельной обработки требований, поступающих в случайные моменты времени. Последнее достигается за f счёт введения новых элементов, при этом
14 t
предположительная сложность системы (количество вентилей) возрастёт не более чем на 5,7 % по сравнению с прототипом.
В четвёртой главе описана методика проведения экспериментальных исследований работы элементов коммутации, подтверждающая теоретические результаты, полученные во второй и третьей главах.
Для экспериментальной проверки работы элементов коммутации, в программе Multisim 7 собраны функциональные схемы разработанных ячеек коммутации. В результате проведённого анализа экспериментальных данных можно придти к выводу, что введённые дополнительные элементы позволяют блокировать ячейки, по которым осуществляется передача пакетов, для того, чтобы свободные ячейки были задействованы в новом процессе установления соединений.
Для экспериментальной проверки корректности алгоритма работы в среде Visual Basic for Applications создана имитационная модель трёхкаскадной коммутационной системы.
Результаты имитационного моделирования подтверждают выводы о повышении пропускной способности коммутаторов сетей передачи данных в случае использования разработанного алгоритма параллельного поиска и реализующих его функциональных схем элементов коммутации.
В заключении формулируются основные результаты, полученные в ходе выполнения диссертационной работы, и выделяются возможные направления дальнейших исследований.
Коммутаторы с разделяемой памятью
Входные процессоры принимают пакеты. Устройство управления очередью определяет последовательность записи пакетов в ячейки разделяемой памяти и считывания пакетов из памяти в буферы выходных процессоров [41].
Коммутатор ASX-1000 на 128 портов имеет усовершенствованную, масштабируемую архитектуру с распределенной совместно используемой памятью, что позволяет поддерживать пропускную способность от 2,5 до 10 Гбит/с[51].
Так как увеличение количества портов требует соответствующего повышения быстродействия памяти, данная коммутационная структура плохо расширяется. Если коммутатор содержит N входных (и выходных) портов, быстродействие памяти должно быть в N раз выше, чем скорость поступления данных в порт. Для выполнения этого условия коммутаторы с разделяемой памятью оборудуются высокоскоростной внутренней многоразрядной шиной, а поступающий поток бит из последовательного кода преобразуется в параллельный. Для обеспечения приемлемой тактовой частоты шину делают достаточно широкой. Так, если W- разрядность шины, то необходимая тактовая частота будет в N/Wpa3 меньше, чем пропускная способность порта.
Устройство, управляющее очередью выходного порта (контроллер памяти), должно обрабатывать заголовки пакетов с той же скоростью, с которой работает память. Чтобы преодолеть вышеуказанные технические трудности, возникающие при использовании множественных классов приоритета трафика, при сложном распределении пакетов, многоадресной и широковещательной передаче, требуется высокое быстродействие памяти и контроллера. Поэтому такая архитектура наиболее часто используется для построения небольших скоростных коммутаторов. Но даже для коммутаторов средней (по количеству портов) величины требуемая частота внутренней шины становится очень большой. Так, для коммутатора с 32 входными портами и 16-разрядной шиной при скорости поступления данных 155 Мбит/с на порт необходимая тактовая частота внутренней шины составляет 310 МГц.
Отличительной особенностью данной архитектуры коммутатора является существование независимого пути для каждой из N возможных пар входов и выходов (рис. 1.3). Таким образом, входящие пакеты транслируются на раздельные шины выходных каналов, а адресные фильтры (АФ) пропускают эти пакеты в выходные буферы (Б).
Преимуществом данной архитектуры коммутатора является отсутствие ограничения на групповую и широковещательную передачу, так как буферизация пакетов происходит на выходных портах, аналогично коммутатору с общей средой.
Примерами использования описанного подхода являются устройства с матричной шиной фирмы Fujitsu и система SPANet компании GTE.
Скорость обмена через порт коммутатора ограничивается только физическим быстродействием адресных фильтров и выходных буферов. Так как между числом портов N и числом буферов В существует квадратичная зависимость B=N\ то основным недостатком такой архитектуры коммутатора является плохая масштабируемость [56].
Структура матричного коммутатора В матричном коммутаторе размером NxM N входных портов подключены к горизонтальным шинам, а М выходных портов - к вертикальным (рис. 1.4).
В узлах матрицы имеются коммутирующие элементы, причем в каждом столбце матрицы может быть открыто не более чем по одному элементу. Обычно применяются коммутаторы с равным числом входов и выходов NxN.
На каждом такте синхронизирующего генератора контроллер анализирует адресную информацию поступивших на входные порты пакетов и устанавливает соединения между портами по выделенному каналу.
Поскольку пропускная способность выделенного канала определяется только физическими характеристиками передающей среды, то суммарная скорость передачи данных в таких коммутаторах может достигать более 100 Гбит/с. Однако в некоторых случаях, при неравномерно распределенном относительно портов трафике, производительность матричных коммутаторов может оказаться ниже, чем устройств с, разделяемой памятью.
Широкое использование матричных коммутаторов в СПД объясняется простотой их структуры и возможностью относительно быстро производить коммутацию пакетов. Однако их недостаток — большое число коммутирующих элементов, что служит ограничением на число портов. Так, для квадратной матрицы число коммутирующих элементов равно N". В целях сокращения числа коммутационных элементов (кроссов) для организации взаимосвязей между вычислительными узлами в многопроцессорных вычислительных системах, а позднее между портами коммутаторов СПД, были разработаны многокаскадные коммутационные структуры.
Разработка алгоритма работы трехкаскадной коммутационной системы
На основе выше опиаанного формализованного описания разработан алгоритм параллельного поиска каналов связи. Для этой цели используется матричный способ задания структуры КС. Зададим трёхмерную матрицу AF, , в которую записываются команды коммутации, поступающие на выходы КС. Одно измерение матрицы соответствует номерам выходов КС (и), второе — номерам КБ промежуточного каскада (у), третье - номерам КБ выходного каскада (z). Очевидно, что матрица Ар моделирует множество MF.
В каждую позицию матрицы, соответствующую одному и тому же номеру выхода КС ц и расположенную на пересечении строки у =1,7 и столбца z =1,Z, записываются элементы a(y,z) = (х,п), представляющие собой команды коммутации. Каждая команда коммутации однозначно определяет вход, с которым должен быть соединён один из выходов КБ z =\,Z я т =1,М где п - номер входа в пределах х-того КБ входного каскада.
При этом все элементы матрицы Ак удовлетворяют следующим ограничениям: число записей в каждом столбце не может превышать числа т, т.е. количества выходов в одном КБ выходного каскада; одинаковые записи не могут более одного раза встречаться в одном столбце.
Согласно этой технологии последовательность бит от передатчика заключаются в контейнер, который называется пакетом. Пакет снабжен заголовком, где указана служебная информация — адрес отправителя, адрес получателя, указан способ проверки целостности содержимого пакета и т.д. Пакет поступает на коммутатор сети, где, используя информацию заголовка, последний обрабатывает пакеты и рассылает их по адресам через другие коммутаторы по линиям связи.
В данной работе интерес представляет только часть служебной информации, хранимой в заголовке пакета, а именно адресная информация (и„ vj, необходимая для доставки пакета от входа порта щ к выходу и, (рис.2.4). заголовок пакета полезная нагрзгзка х. пг г Рис. 2.4. Формат пакета, обрабатываемого в КС
Структура коммутатора СПД представлена на рис. 2.5. В состав коммутатора входит входной модуль, где происходит обработка поступившего пакета. Из заголовка пакета выделяется номер входа w,, который преобразуется во внутренний тег коммутации — команду коммутации (х1гп).
Команды коммутации (х» п) подаются на соответствующие им выходы и, КС. Так происходит заполнейие множества MF. На входы и, подается полезная информация, считываемая из соответствующих пакетов.
Кроме управляющей информации пакет содержит полезную информацию. Чтобы предотвратить потерю полезной информации, необходимо организовать её буферизацию, также как это предусмотрено с командами коммутации, записывающимися в матрице Ар. Для этого алгоритм предусматривает обращение к некоторому множеству MQ, которое может быть реализовано также в виде бурного запоминающего устройства.
Согласно выше описанному алгоритму трёхкаскадная КС с параллельным поиском каналов связи работает в трёх режимах: в режиме настройки, под которым подразумевается процесс установления соединений, в режиме передачи пакетов и в режиме разборки каналов связи (на рис.2.2 режим разборки не указан). Разборка каналов связи происходит динамически как во время передачи информации, так и во время процесса установления соединений. При этом поиск новых каналов связи и разборка старых может происходить параллельно с процессом передачи пакетов по установленным каналам связи [9-13].
Каждый такт процесса установления соединений выполняется за два полутакта. В течение первого производится поиск каналов связи через блоки промежуточного каскада Y к блокам входного каскада X. Во время второго полутакта производится поиск каналов связи к конкретным входам щ в блоках входного каскада и образование ветвящихся в блоках промежуточного каскада соединений. Команды коммутации считываются параллельно на выходы КС и„ свободные от передачи информации.
Параллельный поиск каналов связи между двумя портами коммутатора производится методом последовательного перебора всех возможных каналов связи через промежуточный каскад у{ КС до тех пор, пока не будет найден свободный промежуточный путь. Последовательный перебор осуществляется в соответствии с определением функции 4 , для этого в начальный момент поиска элементы памяти ячеек коммутации - триггеры, расположенные в главной диагонали выходного КБ, устанавливается в единичное состояние. Таким образом, первый выход т\ выходного КБ z, будет подключен к первому КБ промежуточного каскада уъ второй выход т2 - ко второму КБ у2 промежуточного каскада. Последний выход т} будет подключен к соответствующему КБ yj промежуточного каскада.
Каждая команда коммутации (х„п , по образовавшемся в результате включения триггеров главной диагонали каналам связи, поступает на выходы КБ промежуточного каскада. В промежуточном каскаде производится сравнение первых элементов пар и номеров КБ входного каскада. Номера входных блоков входного каскада поступают на входы КБ промежуточного каскада из ПЗУ (постоянное запоминающее устройство), подключенных к каждому входу КБ промежуточного каскада.
В ячейках КБ промежуточного каскада, в которых произошло сравнение первого элемента команды коммутации х, пришедшего с выходного блока и номера пришедшего из входного блока, образуется предварительный канал связи. Но из двоек, поступивших на промежуточный каскад, первые элементы могут быть равны, а вторые - нет. Из таких двоек необходимо выбрать одну для фиксации каналов связи. В трёхкаскадной КС предполагается, что выбирается двойка с меньшим по своей величине вторым элементом. Канал связи указанный такой двойкой фиксируется, а второй элемент соответствующей двойки пропускается на сравнение во входной КБ. Во входном КБ в каждой ячейке производится сравнение второго элемента соответствующей команды коммутации и номера входа поступающего из ПЗУ подключенного к соответствующему входу. В ячейках, где произошло сравнение, фиксируется канал связи. Для того чтобы зафиксировать канал связи в КБ выходного каскада, из КБ промежуточного каскада выдается сигнал фиксации. После этого происходит переход ко второму шагу поиска канала связи. Для этого производится сдвиг на следующую диагональ. При этом ячейки выходного каскада, в которых зафиксирован канал связи, в поиске не участвует. Процедура поиска по побочным диагоналям выполняется точно так же, как и по главной диагонали. Отличием является то, что в поиске не участвуют команды коммутации, для которых каналы связи уже найдены.
После установления всех необходимых соединений в КС, начинается процесс передачи информации. При этом информация передается только в одном направлении - от информационных входов системы к ее выходам.
Для завершения полного процесса поиска и фиксации всех требуемых каналов связи необходимо выполнить несколько шагов настройки. Максимальное число шагов определяется тем, сколько существует различных каналов связи между входами и выходами через промежуточный каскад КС и рано Y. Для неблокируемой трехкаскадной КС, по крайней мере, один из них будет не заблокирован независимо от того, в каком порядке производится поиск этих каналов [9-12].
Функциональные схемы ячеек коммутации
Предлагаемая трехкаскадная КС с параллельной настройкой и передачей информации может работать в трех режимах: в режиме установления соединений, при котором производится поиск и фиксация каналов связи, в режиме передачи информации и в режиме разборки каналов связи, ставших ненужными. При этом передача информации может идти совместно с процессом установления соединений и разборки каналов связи.
Работа КС начинается с установки в прямое состояние триггеров 13 JC. Это осуществляется импульсом, поданным на вход НО КС. Установка КС в такое исходное состояние подготавливает её для процесса установления соединений.
Импульс НО также устанавливает в инверсное состояние триггеры 21 через узлы разборки каналов связи 22 в каждой ячейке 4.Y.M., триггеры 31 через узлы разборки каналов связи 33 и элемент ИЛИ 28, триггеры 31 через узлы разборки каналов связи 33 в каждой ячейке 12.Z.X. и триггеры 43 через узлы разборки каналов связи 40 и элементы ИЛИ 41 в каждой ячейке 16.N.Y.
Процесс установления соединений, в КС начинается с установки всех регистров циклического сдвига 5.М. в исходное состояние. Это осуществляется импульсом, поданным на вход СИО КС.
Этот импульс, поступая на входы регистров циклического сдвига 5.М., записывает в них соответствующий код, содержащий только одну единицу в том разряде, к прямому входу которого подключен вход СИО. Таким образом, после записи этих кодов в регистрах 5.М., расположенных в пределах одного блока I.Z., не будет существовать одинаковых кодов. В регистрах сдвига 5.1. единица записана в первом разряде, в регистрах сдвига 5.2 - во втором и т.д. Наконец, в регистрах сдвига 5.М. единица записана в разряде М. После записи кодов потенциал с прямого выхода S.m.y. разряда, содержащего единицу, каждого регистра 5.М. поступает на соответствующие элементы И 23 и 24 и готовят их к приему информации.
Команда коммутации состоит из т = log2{NxX) разрядов. При записи команд коммутации в буферное ОЗУ из внешнего ОЗУ по шине I.M к т-разрядной команде коммутации добавляется дополнительный нулевой бит. Таким образом, в каждом БЗУ 8.Мхранятся 7 /"(т+1)-разрядных пар (п.х.). Из внешнего ОЗУ в КС поступает управляющая информация (команды коммутации) и полезная информация. Управляющая информация записывается в то БЗУ 8.М., которое соответствует нужному выходу, а полезная информация в то,БЗУ 20.X.N, которое соответствует нужному входу.
Команды коммутации, поступающие из внешнего ОЗУ, записываются в БЗУ 8.М под управлением счётчиков 46.М, подключенных к адресным входам ОЗУ 47М. На вход данных DI ОЗУ 47.М поступают (т+1)- разрядные команды коммутации из внешнего ЬЗУ по шине I.M. Выходы 0\-Оп счётчиков соединены с адресными входами А\-Ап ОЗУ 47М. На вход CS ОЗУ AIM поступают тактовые импульсы ТИ. На вход разрешения записи/чтения W/R из ОЗУ 47.М. поступают сигналы управления ПО.
Дальнейшая работа КС в режиме установления соединений непосредственно связана с поиском и фиксацией каналов связи в соответствии с подпрограммой коммутации. Подпрограмма коммутации — это совокупность (т+1) - разрядных пар (п.х.), одновременно поступающих на выходы буферных ОЗУ 8.М. Особенностью работы предлагаемой КС в этом режиме является то, что в системе ведется поиск одновременно всех необходимых каналов связи в соответствии с подпрограммой коммутации.
Каждый шаг процесса установления выполняется за два полушага. В течение первого полушага производится поиск каналов связи через блоки 2.Y. промежуточного каскада к блокам 3 X. входного каскада. На втором полушаге производится поиск каналов связи для конкретных входов U.x.n. в блоках коммутации 3JC., образование ветвящихся в блоках коммутации 2.Y. каналов связи с выходами V.z.m., если в подключенных к ним буферных ОЗУ 8.М., хранится одинаковая адресная информация, и фиксация найденных каналов во всех блоках коммутации КС.
В начальный момент процесса установления соединений накопившееся к данному моменту времени множество команд коммутации, представляющих собой подпрограмму коммутации, параллельно считывается из буферных ОЗУ 8.М. и поступает на свободные информационные выходы системы V.z.m. Первый полушаг первого шага процесса установления соединений начинается подачей на входы ПО, Ш и СИ1 управляющих сигналов, изображенных на временной диаграмме.
Сигнал ПО, поступая на вход записи/чтения информации W/R буферных ОЗУ 8.М., разрешает выдачу хранящихся в них команд коммутации на соответствующие выходы V.z.m. КС. Этот же сигнал поступает на входы всех элементов И 27 во всех ячейках 4.Y.M. В результате те элементы И 27, на вторые входы которых поступил сигнал «1» с инверсных выходов триггеров 21, будут подготовлены к приёму настроечной информации. В свою очередь сигнал с выходов элементов И 27, сигнал с прямых выходов S.m.y. тех разрядов циклического сдвига 5.М., которые хранят единицы, и разрешающий сигнал с выхода В.у. элементов И 6.Y., поступающий на третьи управляющие входы элементов И 24, готовят эти элементы к приему настроечной информации.
Среди всех элементов Й 24, подключенных входом к одному и тому же выходу V.z.m., будет только один подготовлен к приему информации. Аналогично среди всех элементов И 24, подключенных к одной линии связи D.y.Z, будет только один подготовлен к передаче информации.
Потенциал ПО разрешает выдачу (т+1) разрядов команд коммутации из буферного ОЗУ 8.М Нулевой бит команд коммутации «О» поступает на вход сброса «R » триггеров 9.М. и переводит их в нулевое состояние. Оставшиеся т разрядов команд коммутации поразрядно поступают по подключенному к буферному ОЗУ 8.М. выходу V.z.m через подготовленный элемент И 24 по соответствующей линии связи D.y.Z. на входы узлов сравнения 29, расположенных в ячейках 12.Z.X., подключенных к одной линии связи. Сначала поступают разряды адреса X блоков З.Х.
Анализ работы ячейки коммутации выходного каскада
Схема ячейки коммутации выходного каскада собирается в программе «Multisim 7» на основе вышеприведённых элементов вычислительной техники и полностью соответствует разработанной функциональной схеме, приведенной на рис. 3.6. Схема узла разборки соответствует функциональной схеме приведенной на рис.3.10.
Исходными данными для работы ячейки служат управляющие сигналы, порядок следования которых полностью соответствует временной диаграмме работы трёхкаскадной КС, приведённой на рис. 3.12 в главе 3. Управляющие сигналы представляют собой двоичные импульсы, которые в программе Multisim 7 задаются с помощью Генератора слов (World Generator).
В начальный момент времени НО триггер ячейки сбрасывается и на выход Т.у.т (Q) поступает «1», а на «выход V.z.m и L.z.m (Q) поступает «0». -триггер срабатывается, когда на его вход S поступает «1», это в свою очередь происходит, когда на вход элемента 23 И поступает сигнал фиксации СИ4. Триггер сбрасывается, когда из узла разборки поступает сигнал разборки ПЗ, а по линии связи D.y.z приходит единичный сигнал.
Временная диаграмма процесса функционирования ячейки коммутации выходного каскада, полученная с помощью логического анализатора, показана на рис. 4.3. На временной диаграмме показаны сигналы с выходов элемента 27 HRSpnrrepa21.
В начальный момент времени НО триггеры ячейки сбрасываются через узел разборки (Yz_r_33) и на их выходах Q фиксируется сигнал «1». В момент СИ1, в случае если с узла сравнения (Yz_c_29) приходит сигнал «1» ДО-триггер 30 устанавливается в единичное состояние. В момент СИЗ, в случае, если с узла сравнения (Yz_c_29) приходит сигнал «1» и -триггер 30 находится в единичном состоянии, iuS-триггер 31 устанавливается в единичное состояние. При данных условиях через ячейку устанавливается канал связи, и она будет участвовать в процессе передачи информации.
В случае, если ячейка занята и участвует в образовании канала связи, то её блокировка на следующем этапе процесса установления соединений обеспечивается элементом И 38. На этот элемент приходит управляющий сигнал ПО и сигнал с инверсного выхода і -трштера 31, поэтому если триггер находится в состоянии «1», то данная ячейка не будет участвовать в новом процессе установления соединений. Этот вывод подтверждает временная диаграмма работы ячейки коммутации.
В начальный момент времени НО -триггер 43 ячейки сбрасывается через (Yz_r_40) и на его выходе Q фиксируется сигнал «1». В момент СИЗ, в случае если с узла сравнения (Yz_c_42) приходит сигнал «1», происходит срабатывание і?5-триггера 43. Это говорит о том, что данная ячейка будет участвовать в процессе передачи информации.
В случае, если ячейка занята и участвует в образовании канала связи, то её блокировка на следующем этапе настройки обеспечивается элементом 44 И. На этот элемент приходит управляющий сигнал П2 и сигнал с инверсного выхода і?-триггера 43, поэтому если триггер находится в состоянии «1», то данная ячейка не будет участвовать в новом процессе установления соединений, что подтверждается сигналами, представленными на временной диаграмме.
Имитационная модель представляет собой компьютерную программу, написанную на языке Visual Basic for Application, которая шаг за шагом воспроизводит алгоритм работы КС [55]. Результатом работы имитационной модели являются собранные в ходе наблюдения за протекающими событиями следующие статистические данные: число поступивших и обработанных команд коммутации, размер буфера., На основе полученных данных рассчитываются наиболее важные характеристики работы устройства: пропускная способность, время ожидания пакета, вероятность ожидания (см. приложение 3).
В силу случайного характера моментов поступления команд коммутации, процесс их обслуживания является случайным, поэтому для описания процесса обслуживания команд коммутации в работе используются термины теории массового обслуживания [39, 45].
Исходными данными для заполнения матриц являются команды коммутации, представляющие собой пары (х,п). Команды коммутации выбираются из программы коммутации. Программа коммутации содержит элементы, каждый из которых представляет собой номер входа оь с которым нужно соединить требуемый выход щ:
Исполнение алгоритма начинается с заполнения матрицы AF. Столбцы матрицы AF соответствуют номерам КБ выходного каскада z= \,Z, а строки -номерам КБ промежуточного каскада у =1,7. Элементы этой матрицы заданы в виде пары, первым членом каждой из которых является номер КБ входного каскада х=\,Х, вторым - номер входа n=\,N, в пределах одного КБ входного каскада. По оси и задаётся ячейка в БЗУ, соединённом с конкретным выходом и
Далее алгоритм предусматривает заполнение матрицы Ак элементами из матрицы Ар. Структура матрицы Ак аналогична структуре матрицы AF, за исключением того, что элементами матрицы Ак являются команды коммутации (х,п), находящиеся первые в очереди БЗУ. Столбцы матрицы Ак соответствуют номерам КБ выходного каскада z - \,Z, а строки - номерам КБ промежуточного каскада у =1,7.
Наличие элемента (х,п) на пересечении строки у и столбца z матрицы Ак означает, что требуется организовать канал связи, который начинается со входа п в КБ х входного каскада, проходит через КБ у промежуточного каскада и заканчивается на выходе т КБ z выходного каскада.
В качестве первоначальных номеров строк при заполнении матрицы в рассматриваемой модели выбраны номера выходов, взятые из каждого элемента программы коммутации. Действительно в этом случае условие (4.6.) будет автоматически выполнено, так как в каждом КБ выходного каскада каждый номер выхода используется только один раз, а наибольший номер выхода в КБ заведомо меньше количества КБ в промежуточном каскаде в соответствии с условием неблокируемостй КС. Выполнение условия 4.5 исключает наличие в матрице Ак одинаковых пар, т.е. пар, для которых справедливо условие: (Зс,- = xj) & (щ = п), при / j. Далее работа алгоритма основывается на заполнении матрицы А к, структура которой аналогична структуре матрицы Ак. Для того, чтобы получить команду на установление соединений в соответствии со всей программой коммутации, необходимо все элементы (х,п) программы коммутации распределить по КБ промежуточного каскада. В результате правильного распределения в каждой строке матрицы Ак должны находиться элементы, удовлетворяющие условиям неблокируемостй для любых двух каналов связи, т.е. должно выполняться условие: (xi = xj) & (пфу) v fa =zj) = (уФу) (4.7) Вся дальнейшая работа модели направлена на выполнение условия (4.7.). Для этого в каждой строке матрицы Ак просматриваются пары (х,п), у которых значение х - одинаковое. После исполнения этого действия из всех пар (х,п) с одинаковым значением х в каждой строке остаётся только одна пара, находящиеся в столбце с самым маленьким номером. Все остальные элементы переносятся в идентичные позиции вспомогательной матрицы Ак , форма которой полностью адекватна описанным выше матрицам.
