Узбекское агентство связи и информатизации

Ташкентский университет информационных технологий

На правах рукописи

УДК 621.396.1

Садчикова Светлана Александровна

Модели и методы расчета широкополосных ассоциативных

сетей коммутации

05.12.13. – Системы, сети и устройства телекоммуникаций, распределение информации

АВТОРЕФЕРАТ

диссертации на соискание учной степени кандидата технических наук

Ташкент-2011

Работа выполнена в Ташкентском университете информационных технологий.

Научный руководитель кандидат технических наук, профессор Сон Владимир Мунхович

Официальные оппоненты: доктор технических наук, профессор Нишанбаев Туйгун Нишанбаевич кандидат технических наук, доцент Исаев Рихси Исахужаевич

Ведущая организация Акционерная компания «Узбектелеком»

Защита состоится «_» 2012 г. в _ часов на заседании разового специализированного совета при специализированном совете Д.001.25.01 Ташкентского университета информационных технологий по адресу: 100202, г.Ташкент, ул. А.Темура,108.

С диссертацией можно ознакомиться в библиотеке Ташкентского университета информационных технологий.

Автореферат разослан « _ » 2012 г.

Учный секретарь специализированного совета Зайниддинов Х.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА ДИССЕРТАЦИИ

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

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

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

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

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

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

Степень изученности проблемы. Задача построения модели ассоциативных систем коммутации является частью общей проблемы ассоциативных систем и теории групп. Теория ассоциативных систем и теории групп разработаны в трудах А.А.Маркова, П.С.Новикова, С.И.Адяна и других. Развитие теоретических основ и приложений в технике и технологии отражены в работах Э.В.Евреинова, Я.И.Фета, В.И.Неймана и других авторов, где отражены возможности реализации ассоциативных систем. Дальнейшее исследование было продолжено и нашло отражение в работах Д.А.Абдуллаева и В.М.Сона. В этой связи представляется актуальным исследование и разработка моделей и методов расчета ассоциативных сетей, обеспечивающих высокоскоростную обработку данных.

Связь диссертационной работы с тематическими планами НИР.

Работа выполнена на кафедре «Телекоммуникационные сети и системы коммутации» Ташкентского университета информационных технологий в рамках хоздоговорной НИР «Исследование и разработка ассоциативной системы коммутации» (5-04 от 01.05.2004) и договора-гранта с Госкомитетом по Науке и Технике Узбекистана «Разработка и исследование оптической коммутационной фабрики» (№ 17-020 от 01.01.2009).

Цель исследований. Целью настоящей работы является исследование и разработка моделей узлов коммутации и методов расчта характеристик широкополосных многоуровневых N-мерных ассоциативных сетей коммутации.

Задачи исследования:

1. Исследование и разработка математических моделей ассоциативного коммутационного модуля при управлении процессом установления соединения.

2. Исследование модели параллельных процессоров для ускорения решения задачи маршрутизации и коммутации информации.

3. Разработка моделей сетей АСК кольцевой структуры одно- и двухуровневой иерархии, а также модели сетей АСК звездообразной структуры.

4. Разработка методов расчета вероятностно-временных характеристик сетей 5. Разработка алгоритма определения структуры ассоциативных сетей коммутации, удовлетворяющих условиям по ВВХ.

Объект и предмет исследования. Объектом исследования является структура ассоциативной системы коммутации, сети ассоциативных систем коммутации. Предметом исследования - модели и методы расчта ассоциативной коммутации и маршрутизации.

Методы исследования. В работе использованы методы алгебраической системы ассоциативной коммутации, методы теории вероятностей, теории массового обслуживания, теории групп, Z-преобразования рядов распределения, а также методы матричных алгоритмов, параметрического анализа вероятностно-временных характеристик и оптимизации структуры сети.

Гипотеза исследования. Базовые принципы параллельности обработки информации, переменности и однородности построения модулей коммутации позволяют строить сети АСК со сверхвысокими скоростями коммутации и обработки информации при конструктивной однородности структуры сети АСК.

Основные положения, выносимые на защиту:

1. Аналитическая модель системы ассоциативной коммутации.

2. Метод построения ассоциативного коммутационного модуля на основе ассоциативного исчисления.

3. Метод синтеза структуры ассоциативной коммутационной фабрики (АКФ) и основных узлов управления, позволяющий решить задачи маршрутизации и коммутации информации в АСК.

4. Метод расчета ассоциативных сетей коммутации, основанный на аппарате Z-преобразования, и модель формального описания протоколов передачи Марковскими стохастическими системами в дискретном времени.

5. Аналитические модели ассоциативных сетей коммутации кольцевой и звездообразной структур.

6. Алгоритм определения структуры ассоциативных сетей коммутации.

Научная новизна исследований данной диссертационной работы заключается в следующем:

1. В результате исследования разработана модель ассоциативной коммутационной фабрики, базирующейся на алгебре групп.

2. Предложен метод решения задачи поиска соединительного пути на базе математических формул алгебры групп.

3. Разработана модель формального описания структуры АСК и коммутационных процессов в модулях сети.

4. Разработаны аналитические модели ассоциативных сетей коммутации кольцевой и звездообразной структур.

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

Научная и практическая значимость результатов исследования:

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

2. Предложена АСК в виде ассоциативной коммутационной фабрики, позволяющая строить локальные и глобальные сети связи с распределенной структурой.

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

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

5. Показано, что применение АКФ в составе коммутационных систем обеспечивает большую производительность обработки пакетов, в сравнении с традиционными коммутационными средствами сетей SDH и IP/Datacom.

Практическая ценность результатов диссертационной работы подтверждена актами внедрения.

Реализация результатов. Диссертационная работа является составной частью научно-исследовательских работ, проводимых кафедрой «Телекоммуникационные сети и системы коммутации» Ташкентского университета информационных технологий по исследованию ассоциативной системы коммутации. Результаты работы внедрены в АК «Узбектелеком» и в учебный процесс Ташкентского университета информационных технологий, что подтверждается соответствующими документами.

Апробация работы. Основные положения и результаты работы докладывались, обсуждались и получили одобрение на научно-технических конференциях профессорско-преподавательского состава Ташкентского университета информационных технологий; на Техническом комитете АК «Узбектелеком»; на международной научно-технической конференции «Узбекистан-Корея: научное и культурное сотрудничество» в г.Ташкент в 2000г.; на IV международной научно-технической конференции «Техника и технология связи» студентов, аспирантов и молодых специалистов стран СНГ в г.Алматы Республика Казахстан в 2002г.; на международной научнотехнической конференции ITC-CSCC 2003 в г.Kangwon-Do Korea в 2003г.;

на двух международных научно-технических конференциях «Состояние и перспективы развития связи и информационных технологий Узбекистана» и «Роль и значение телекоммуникаций и информационных технологий в современном обществе» в г.Ташкент в 2005г.; на Республиканской научнотехнической конференции «Фан ва таълимда ахборот – коммуникация технологиялари» в 2006г. на международных научно-технических конференциях IEEE - ICI2006 в 2006, ICI2007 в 2007 и AICT2010 в 2010г.г., на научном семинаре при специализированном совете Д.001.25.01 ТУИТ от 27.12.2011г..

Опубликованность результатов. Основные результаты работы опубликованы в научных журналах «ТАТУ хабарлари» в 2008,2009г.г.;

«Проблемы информатики и энергетики» в 2002,2003г.г.; в Сборниках научных трудов «Радиотехник тизимлар ва урилмалар» в 2001г., «Proceeding PadiTel», Part I,II в 1998,1999г.г.; в материалах Международных и Республиканских научно-технических конференций – всего 20 работ.

Структура и объм работы. Диссертационная работа состоит из введения, четырх глав, заключения, списка использованной литературы и приложений. Общий объм диссертации 174 страницы, в том числе страницы основного текста, 20 страниц приложений, 37 рисунков, 11 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении обоснована актуальность темы диссертации, сформулирована цель работы, описаны объект, предмет и задачи исследования.

Приведены основные положения, выносимые на защиту, и сведения об апробации и внедрении результатов работы.

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

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

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

Далее, в работе разработаны основные положения и приложения теории ассоциативной коммутации на принципах теории ассоциативных систем и теории групп при заданных элементах алфавита А, системы подстановки F и размерности n ассоциативного пространства.

Теория ассоциативной коммутации базируется на следующих положениях:

1. Строится АСК в виде графа с множеством М коммутационных узлов и сигнатурой. Сигнатура включает в себя операции сложения, подстановки, и умножения, которые решаются методом матричных алгоритмов. Граф топологии графа, (,, ) - сигнатура графа. АСК в виде графа ячеистой или кольцевой структуры обладает свойством изоморфизма.

2. Определяется метрика - вектор соединения между вершинами графа, которая затем преобразуется на основе принципов рефлексивности, симметричности и транзитивности в алгебре векторов.

3. Производится синтез топологической структуры, которая реализуется в виде итеративных сетей ассоциативных коммутационной фабрики.

4. Строится математическая модель АКФ на основе алгебраической системы уравнений.

Во второй главе рассматриваются вопросы структурного синтеза ассоциативных коммутационных систем.

Коммутатор NxM разбивается на A коммутаторов меньшей размерности в соответствии с системой подстановки ассоциативного исчисления F. Так, трехмерная итеративная сеть (рис.1) состоит из четырх взаимосвязанных двухмерных итеративных подсетей, составленных из модулей:

подсеть 1 (222,231,221, 211,212,213, 223, 233,232);

подсеть 2 (222, 121,122, 123,223,232, 322, 321,221);

подсеть 3 (222,131,132, 133,223,313, 312,311,221);

подсеть 4 (222,111,112, 113,223,333, 332, 331,221).

Рис.1. Структура трхмерной итеративной сети с параметрами Полученные итеративные подсети также представляют собой ассоциативные коммутационные фабрики, в которых каждый узел (модуль) содержит операционный и управляющий автоматы. Число межмодульных связей определяется исходя из параметров ассоциативных коммутационных систем. Например, при A 3, n 3, F 1 - 1,1 - 2, 2 - 2, 2 - 3, 3 - 3, 3 - 1 число модулями, как разность векторов. Операция вычитания координат модулей сводится к нахождению разности соответствующих разрядов координат.

Вс множество расстояний арифметического пространства n составляет алгебраическую группу. В этой группе имеются - нулевое расстояние, обратное расстояние (вектор) и ассоциативное отношение разностей векторов.

Определение расстояния между модулями необходимо для решения задач маршрутизации в АКФ. Каждый модуль характеризуется номерами, которые интерпретируются как его внутреннее состояние. К каждому модулю подходят по L An 1 межмодульных симметричных цепей, найденных по системе подстановок, и столько же внешних цепей для ввода и вывода трафика из/в АКФ.

Если Sj и Si являются номерами модулей, тогда граф АКФ обозначается как модулями, определяемый системой подстановки.

Каждый модуль имеет прямое соединение с другими модулями – прямой маршрут. В случае занятости прямого маршрута, ищется обходной путь. Поиск обходного направления осуществляется на основе алгоритма, суть которого заключается в следующем: любой обходной маршрут между узлами i и j может быть составлен из определнного числа прямых маршрутов, существующих для узлов Для примера рассмотрим варианты поиска обходного маршрута между узлами 222 и 221, при занятости прямого пути (вектор m модуля 222).

Вектор a модуля 222 является прямым маршрутом между модулями 222 и 111. Этот вектор стыкуется с началом вектора z модуля 111. Прямой путь между узлами 222 и 221 (вектор m модуля 222) является суммой вектора a модуля и вектора z модуля 111. Для определения свободности/занятости данного маршрута необходимо учесть внутреннее состояние модуля 111, а именно состояние межмодульной связи, соответствующей вектору z модуля 111.

Отношение между модулями 222 и 111 определяется подстановкой векторов z. При занятости пути, соответствующего вектору модуля 111, маршрут может быть заменн на следующий. Для этого воспользуемся свойством транзитивности бинарного отношения эквивалентности графа G. К вектору a модуля 222 по закону треугольника примыкает вектор b модуля 222 (прямой маршрут между модулями 222 и 112), а к нему вектор y модуля 112 (прямой маршрут между модулями 112 и 111). С другой стороны, к концу вектора b модуля 222 последовательно примыкает вектор m (прямой маршрут между модулями 112 и 111 относительно модуля 112) и вектор n (прямой маршрут между модулями 111 и 112 относительно модуля 111), т.е. подстановка имеет вид. Обозначив группу подстановки ОЕР выражением S подстановку запишем для ассоциативной коммутационной фабрики:

Подстановка S 26 определяет конечную группу и е операцией является умножение имеющихся векторов маршрутов на вектор свободности/занятости маршрутов данного модуля. Выполняя подобные подстановки, рассчитывается таблица перестановки из 26 векторов модуля 222.

Таблица перестановки определяет маршруты установления соединений в ассоциативной коммутационной сети. В самой верхней строке таблицы в первом столбце записывается номер исходящего модуля - в рассматриваемом примере модуль 222. Далее в столбце записываются номера модулей, которые идут в алфавитном порядке по отношению к выходам модуля-источника. В результате, получается алгебра множества отношений (111,112,113,-…331,332,333) с унарными операциями векторов (a,b,c,…,x,y,z).

Применяя аналогичные рассуждения к остальным модулям, получаем обобщенную таблицу для схемы рис.1. В этой таблице номер модуля-источника помещается в верхней строке. В первом столбце данной таблицы записываются номера выходов модуля-источника, которые имеют жстко закреплнный порядок назначения номеров-индексов. Остальные столбцы показывают номера модулей-получателей (модулей назначения), закреплнные за данными выходами модуля-источника. Рассматриваемый выше пример относительно модуляисточника 222 записан в пятнадцатом столбце. Подробное описание определения таблиц перестановки векторов и алгебры множества модулей приводится в диссертации.

Поскольку итеративные сети АСК имеют регулярную (одинаковую) структуру, определяемую системой подстановки, то для определения их характеристик рационально рассматривать двумерную топологию, приведенную на рис.2.

Итеративная сеть представляет систему массового обслуживания, где каждый модуль выполняет функции обработки информации, которые Рис.2. Структура двухмерной итеративной сети реализуются с помощью операционного автомата (коммутационное поле) и системы управления, состоящей из следующих автоматов: функциональной схемы автомата (ФСА), программного автомата с памятью ПЗУ и оперативного автомата с памятью ОЗУ. Задача ФСА – вычислить направление маршрута,т.е.

соединительной линии, а программного и оперативного автоматов – вычислить конкретные доступные соединительные пути и загрузить опера-ционный автомат информацией для включения тракта соединительных линий.

Алгоритм решения задачи маршрутизации и коммутации сводится к вычислительной задаче, состоящей из двух этапов: первый этап – определение автоматом ФСА и программным автоматом направления маршрута и вычисление вектора Н(х)= ; второй этап – вычисление произвольного вектора коммутации Х на основе вектора Н(х) и произвольного вектора ОЕР свободности/занятости. Так, например, при Н(х)= и произвольном векторе ОЕР= вектор коммутации Х равен:

Это означает, что между заданными модулями имеются четыре свободных доступных соединительных линии. Выражение X H(x) OEP - означает формулу параллельного матричного вычисления (внешнее произведение матриц). Поскольку все автоматы рассматриваемого модуля выполнены по однотактной схеме, то процесс вычисления ускоряется в 1000 и более раз по сравнению с решением (вычислением) той же самой задачи фон-Неймановским методом последовательного вычисления. Сверхвысокая скорость обработки информации позволяет строить АКФ с обходным аппаратным управлением коммутацией пакетов.

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

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

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

При обмене информацией между двумя абонентами речевой сигнал проходит три этапа преобразований. На первом этапе аналоговый сигнал передатчика преобразовывается в цифровой сигнал с присвоенным адресом и записывается в блок памяти передачи со стандартной скоростью С=64кбит/с.

На втором этапе этот пакет считывается и через КМ (А) передается в память приема узла Б (в соответствии с адресом назначения пакета) со скоростью в K раз большей, чем на первом этапе. Сжатие пакета осуществляется уплотнителем. Скорость передачи преобразованной информации S по групповому тракту - определяется как:

K - коэффициент компрессии.

где На третьем этапе пакет считывается из памяти узла КМ (Б) с исходной скоростью С = 64кбит/с, что обеспечивается расширителем.

В приемнике абонента происходит преобразование речевого сигнала из цифровой формы в аналоговую форму.

Предлагаемая ассоциативная система коммутации отличается осуществлением на втором этапе K -кратного сжатия информационного пакета во времени, что позволяет во столько же раз повысить эффективность использования группового тракта всей системы.

Считывание пакетов производится со скоростью S, поэтому время обслуживания коммутационным модулем каждого активного абонента будет равно:

где длительность формирования информационного пакета.

Выигрыш времени пакета с большей скоростью составляет:

В течение интервала t система готова обслуживать других абонентов, т.е.

происходит вторичное временное уплотнение.

В работе рассмотрены два режима работы КМ: режим с потерями (А), когда пакеты некоторых абонентов при считывании со скоростью S совпадают во времени; режим с ожиданием (Б), когда считывание пакетов будет осуществляться с ожиданием после высвобождения группового тракта и определены вероятностные характеристики обоих режимов. Расчет вероятностей состояния коммутационного модуля АСК приведн в Приложении диссертации.

Разработаны модель и метод расчета АСК звездообразной структуры в дискретном времени на основе аппарата Z-преобразования, для описания протокольных процессов канального и сетевого уровней использованы Марковские стохастические процессы. Для этой структуры определены зависимости характеристик сетей АСК ( QM - вероятность незанятого окна, t q - средняя задержка, t S - среднее время обслуживания, П q - вероятность своевременной доставки) от скоростей передачи информации, длины пакета, параметра доступа, числа абонентов, интенсивности входного потока заявок.

Разработаны модель и метод расчета 2-х уровневой кольцевой АСК в дискретном времени. Определены вероятностно-временные характеристики средней задержки, вероятности своевременной доставки и информационной скорости для трех фаз передачи информации между абонентами, принадлежащими разным локальным группам 1-го уровня при равновероятном тяготении абонентов и при разных значениях коэффициента замыкании нагрузки Кз в пределах локальной группы (рис.3).

В диссертации рассмотрены следующие фазы процессов передачи информации между двумя терминальными станциями, принадлежащими разным АКФ:

- фаза А – передача от терминальной станции ma в шлюзовую станцию Sa;

- фаза 0 – передача от шлюзовой станции Sa в шлюзовую станцию Sb;

- фаза В – передача от шлюзовой станции Sb в терминальную станцию mв.

Процесс предоставления доступа свободного временного окна j -й станции является случайным процессом с рядом распределения Бернулли, который характеризуется параметрами: qИ -вероятность появления заявки в сети АКФ; pИ -вероятность не появления заявки в сети АКФ; QM - вероятность незанятого окна. В таком случае обслуживание потока заявок в сети АКФ может быть представлено системой вида M Д / M Д / 1, и при равновероятной адресации информации, вероятность занятости буфера станции где m – число станций, подключенных к каждой АКФ; N- число входных буферов АКФ; mi – число терминальных станций, требующих доступ к АКФ на интервале окна; (mj – 1) – число станций, с которыми j-ая станция соперничает в занятии окна.

Кольцевая сеть локальной группы Рис.3. Структура 2-х уровневой иерархической сети кольцевого типа Разработан пакет прикладного программного обеспечения для расчета вероятностно-временных характеристик сетей АСК.

В четвртой главе решается задача параметрического анализа сети АСК и определяется топологическая структура, удовлетворяющая условиям ВВХ.

В общем виде топологическую структуру АСК можно представить в следующем виде где вектор Y отображает типы топологической структуры АСК; X - вектор типов протоколов управления; YT - компонента, учитывающая число r уровней иерархии топологии сети АСК; Yу - компонента, учитывающая тип топологической структуры АСК; YN - компонента, учитывающая число локальных групп АСК; YK - компонента числа каналов связи между АКФ;

X Vij - компонента, учитывающая скорость передачи информации в i -той локальной группе j -го уровня; X Dij - компонента, учитывающая тип протокола доступа в i -той локальной группе j -го уровня; X Сij компонента, учитывающая тип среды передачи в i -той локальной группе j го уровня.

Параметрами топологической структуры Y являются: r -число уровней иерархии топологии; N j - число АКФ на j-м уровне, j 1, r ; Dmij - длина канала связи i-локальной группы j-го уровня, j 1, r, i канала связи между i-й и j-й АКФ, j 1, r, i 1, N j.

Компонента Y уi может принимать значение Y – для звездообразной сети и Yk – для кольцевой сети.

Параметрами типов протоколов управления, зафиксированных в векторе Х, являются длины полей адреса ra, управления ry, контрольных разрядов rk, флага rф информационного кадра, длина квитанции nкв, вероятность ошибки в канале связи p, коэффициент готовности канала kг.

Компонента Xдij в данной работе принимает значение Xаск – для локальных групп АКФ и между АКФ.

Таким образом, задано некоторое множество F вариантов структуры АСК, различающихся типом топологической структуры, средой передачи, скоростью передачи, протоколом доступа, алгоритмом защиты от ошибок и других. Тогда, задача оптимизации АСК сводится к поиску вектора W*, обеспечивающего минимум функции приведнных затрат П3:

при выполнении ограничений на: среднее время задержки пакета и вероятность своевременной доставки Заметим, что компоненты Х вектора W носит дискретно-табличный характер, а также сеть АСК физически реализуема.

Область допустимых решений F в данном случае представляет собой множество индексов, обозначающих допустимые к использованию комбинации вектора W*. Параметры длин каналов не включаются в состав вектора W* управляемых параметров, т.к. они могут быть определены исходя из топологии Y и географических координат терминальных станций локальных групп. Конкретные выражения П з (W *), t q (W *) и Пq (W *) определяется моделями АСК.

При однотипности оборудования сети АСК функция приведнных затрат может быть представлена в виде:

где: ЕН – нормативный коэффициент эффективности капитальных вложений;

C T (i) - стоимость терминальной станции i-го типа; C G (i) – стоимость шлюзовой станции i-го типа; B(Umij, Uaij) – стоимости канальных сооружений локальных групп и между АКФ длиной Umij и Uaij соответственно, j 1, r, 1, N * j ; Se – стоимость системы управления сетью АСК.

В работе разработан алгоритм, реализующий направленный поиск оптимального варианта сети. Данный алгоритм базируется на соблюдении системы неравенств, основанных на результатах параметрического анализа сетей АСК. Апробация алгоритма проводилась при следующих исходных данных: М=20; N1=9; Vс=1Гбит/с; nk=[300, 450, 600] бит; p=1 10-9;

T Д =0.0005; Кз= [0.2, 0.5, 0.8]. На рис.4,5 приведены результаты вычислительного эксперимента. Как видно из рис. 4 при увеличении длины пакета в 2 раза (с 300 бит до 600 бит) область эргодичности сети уменьшается в 2.3 раза до 1350 Пак/с. При длине пакета 300 бит и интенсивности входного потока =1300 Пак/с средняя задержка составляет 0.075с, а при =500 Пак/с t q =0.017с. Рис.5 демонстрирует зависимости ВВХ средней задержки t q при изменении параметра доступа qД. Средняя задержка достигает величины 0.032с: для qД=0.1 при значении =271 Пак/с; для qД=0.2 при значении =628Пак/с, а для qД=0.4 при значении =1249 Пак/с. Таким образом, область эргодичности возрастает в 4.6 раза.

Приведен численный пример оптимизационной задачи. Искомым вариантом в рассматриваемой задаче определения структуры сети АСК является 89 вариант, имеющий оптимальную структуру, с параметрами МТ=180; МG=9; muj=9; Кз=0,8; Vc =100Гбит/с, вероятность своевременной доставки равна П q =0,9912.

1.330 е+ 7.982 е- 5.325 е- 2.668 е- 1.082 е- Рис.4. Графики зависимости средней задержки t q при изменении параметра длины однопакетного сообщения В процедуру поиска искомой структуры включен алгоритм разбиения терминальных станций сети АСК на отдельные локальные группы.

Координаты станций задавались с помощью генератора случайных чисел и пересчитывались в длины каналов связи локальных групп на условную площадь 1х1 км2. Процедуры расчета реализованы с помощью прикладного пакета GCC 4.98 в операционной системе UNIX Ubuntu9.1.

На рис.6 приведены варианты АСК в пространстве «приведнные затраты – средняя задержка». Процедура выделения множества локальнооптимальных решений сопровождается отсеиванием вариантов, для которых не выполнены заданные ограничения.

Задача определения искомых структур сводится к поиску вектора W *, одновременно обеспечивающего минимум функции приведнных затрат и минимум функции средней задержки при выполнении ограничений на вероятность своевременной доставки 1.674 е+ 1.520 е+ 1.366 е+ 1.213 е+ 1.059 е+ Рис.6. Варианты АСК в пространстве «стоимость – задержка»

На графике пунктирной линией выделено искомое множество локальнооптимальных вариантов АСК в решаемой задаче: {96, 95, 94, 93, 92, 89, 83, 82, 81}.

ЗАКЛЮЧЕНИЕ

Основные результаты исследований, проведенных в диссертационной работе, состоят в следующем.

1. Разработаны математические модели ассоциативных коммутационных модулей при управлении процессом установления соединения.

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

3. Разработаны модели сети АСК звездообразной структуры и кольцевой двухуровневой структуры. Модели базируются на аппарате Zпреобразования рядов распределения в дискретном времени.

4. Решены задачи анализа и выбора параметров сети АСК. Выявлены зависимости вероятностно-временных характеристик при изменении параметров сети.

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

6. Разработаны алгоритмы и программы расчета вероятностно-временных характеристик сетей АСК звездообразной и кольцевой двухуровневой структур.

7. Предложенные алгоритмы, аналитические модели и методы расчета, программное обеспечение расчетов ВВХ внедрены в НИР и учебный процесс ТУИТ.

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ

1. V.M.Son, A.V.Son, S.A.Sadchikova. Group formation of digital switching systems. Development of associative digital switching systems// Сб. науч.

трудов Proceeding PadiTel, Part I. - Tashkent-Antwerp, 1998. - p.120-127.

2. V.M.Son, A.V.Son, S.A.Sadchikova. Concept of call setup path searching in switching nodes// Сб. науч. трудов Proceeding PadiTel, Part II. - TashkentAntwerp, 1999. - p.115-120.

3. Сон А.В., Садчикова С.А, Сон В.М. Теоретические основы ассоциативной коммутации// Узбекистан-Корея: научное и культурное сотрудничество:

Тез. докл. международной конференции. – Ташкент, 2000. – с.68-77.

4. Сон В.М., Сон А.В., Садчикова С.А. Принципы построения коммутационных схем распределения информации// Сб. науч. трудов Радиотехник тизимлар ва уримлар. – Ташкент ТЭИС, 2001. – с.143-152.

5. С.А.Садчикова. Модель ассоциативной системы коммутации// Техника и технология связи: Труды IV междунар. науч.-тех. конф. студентов, аспирантов и молодых специалистов стран СНГ. – Алматы: АИЭС, 2002.

с.91-94.

6. А.В.Сон, Д.К.Ри, Х.М.Пак, С.А.Садчикова. Автоматная модель ассоциативной системы коммутации // Проблемы информатики и энергетики, ФАН АК РУз. – Ташкент, 2002. – №.5. – с.67-75.

7. А.В.Сон, С.А.Садчикова, Х.М.Пак, Д.К.Ри. Теоретические основы ассоциативных коммутационных полей // Проблемы информатики и энергетики, ФАН АК РУз. – Ташкент, 2003. – №.3. – с.11-17.

8. A.V.Son, S.A. Sadchikova, V.M.Son, H.M.Park and J.K. Rhee. Routing in the multi-coordinate associative switching systems // ITC-CSCC 2003:

International Conference. – Kangwon-Do, Korea, 2003. – pp. 1515-1519.

9. Сон В.М., Сон А.В., Садчикова С.А. Способ искания объектов в ассоциативных коммутационных узлах // Состояние и перспективы развития связи и информационных технологий Узбекистана: Тез. докл.

междунар. науч. конф. 11-12 мая 2005. – Ташкент, ТУИТ, 2005. с.46.

10.В.М.Сон, С.А.Садчикова, А.В.Сон. Ассоциативная коммутационная фабрика// Роль и значение телекоммуникаций и информационных технологий в современном обществе: Труды междунар. науч. конф. 27- сент. 2005. – Ташкент, ТУИТ, 2005. – т.1. – с.66- 11.В.М.Сон, А.В.Сон, С.А.Садчикова, С.А.Агзамов. Асинхронный высокоскоростной адресно-кодовый коммутатор // Роль и значение телекоммуникаций и информационных технологий в современном обществе: Труды междунар. науч. конф. 27-30 сент. 2005. – Ташкент, ТУИТ, 2005. – т.1. – с.72-76.

12.С.А.Садчикова, В.М.Сон. Ассоциативная коммутационная фабрика как модель коллектива коммутаторов// Фан ва таълимда ахборот – коммуникация технологиялари: Тез. докл. Респ. науч. конф. 6-7 апр, 2006.

– Ташкент, ТУИТ, 2006. – с.108-109.

13.A.Son, S.A. Sadchikova V.Son, S.Myong-Sek. Model of Telecommunications Switching System design // ICI2006: International Conference in Central Asia on Internet. – Uzbekistan, IEEE, 2006. – IEEE Catalog Number: 06EX1492C ISBN: 1-4244-0543-2 Library of Congress: 14.S.A. Sadchikova, A.Son, V.Son. Model of Telecommunications Switching System design // ICI2007: International Conference in Central Asia on Internet.

– Uzbekistan, IEEE, 2007. – IEEE Catalog Number: 06EX1492C ISBN: 1Х/07 Library of Congress: 15. А.В.Сон, С.А. Садчикова, В.М.Сон. Параллельная групповая обработка управляющих сигналов коммутационных систем // ТАТУ хабарлари. – Ташкент, 2008. – №1. – с.30-37.

16.С.А. Садчикова, А.В.Сон, В.М.Сон. Группообразование ассоциативных систем коммутации // ТАТУ хабарлари. – Ташкент, 2008. – №2. – с.20-26.

17.Сон В.М. Садчикова С.А. Сон А.В. Ассоциативная система оптической коммутации // ТАТУ хабарлари. – Ташкент, 2008. – №3. – с.39-45.

18.С.А. Садчикова, А.В.Сон, В.М.Сон. Базовые положения теории ассоциативной коммутации // ТАТУ хабарлари. – Ташкент, 2009. – №2. – с.36-42.

19.Садчикова С.А. Принцип построения ассоциативной сети коммутации кольцевой структуры // ТАТУ хабарлари. – Ташкент, 2009.– №3. – с.36-42.

20.D.E.Yunusova, S.A.Sadchikova, V.M.Son. Time-probability characteristic’s analysis of Associative Switching Fabric// AICT2010: 4th International Conference on Application of Information and Communication Technologies – Uzbekistan, IEEE, 2010. – p.213-216.

Техника фанлари номзоди илмий даражасига талабгор Садчикова Светлана Александровнанинг 05.12.13. – Телекоммуникация тизимлари, тармолари ва урилмалари, ахборотларни тасимлаш ихтисослиги бўйича «Кенг полосали ассоциатив тармоларини исоблаш моделлари ва усуллари»

мавзусидаги диссертациясининг

РЕЗЮМЕСИ

Таянч (энг муим) сўзлар: ассоциатив коммутация, ассоциатив коммутацион модули, параллел процессорлари, тармоларининг алка, юлдузли структуралари Тадиот объектлари: ассоциатив коммутация алоа тармоларининг структураси, ассоциатив коммутация тизимларининг тармолари, ассоциатив коммутация ва маршрутизацияси, амда уларнинг моделлари ва исоблаш усуллари.

Ишнинг масади: кенг полосали кўп сатли N-текисли ассоциатив коммутация тармоларининг усулларини ва коммутация тугунларининг моделларини тадиот илиш ва ишлаб чииш.

Тадиот методлари: олиб боратган тадиотлар ассоциатив коммутациянинг алгебраик тизими, этимоллик назарияси, оммавий хизмат кўрсатиш назарияси, гурулар назарияси, тасимлаш аторларининг Zзгартииришлари, матрица алгоритмлари, ват-этимол характеристикаларнинг параметрик талили ва тармо тузилиши оптимизациясига асосланган.

Олинган натижалар ва уларнинг янгилиги: A алфавит ва F ўрин алмаштириш тизимига оид гурулар алгебрасига асосланган ассоциатив коммутацион фабрикасининг модели; АКТ тармоларининг модулларида коммутация вазифаларини ечиш оператив ва дастурий хотиранинг матрица элементларининг ўринларни алмаштириш бўйича алгебраик мультипликатив гуруларини кўпайтириш операция – ОЕР модулларинин тўпламининг анилаш соаси орали ифодалаб берилган; алка ва юлдуз структурали ассоциатив коммутация тармоларининг аналитик моделлари.

Амалий аамияти: берилган талаблар ва дастлабки маълумотларга асосланиб тармо параметрларини танлаш имконини берадиган ассоциатив коммутация тармоларини инженерлик исоблаш учун ифодалар ишлаб чиилган. АКФни коммутация тизимларининг таркибида ўлланиши анъанавий коммутация тармоларига кўра юори унумдорликка эга бўлгани аниланди.

Татби этиш даражаси ва итисодий самарадорлиги: ишнинг атижалари АК «Ўзбектелеком» ва Тошкент ахборот технологиялари университетининг ўув жаранига жорий этилди.

телекоммуникация тармоларининг маршрутизация ва ассоциатив коммутация механизмини исоблаш, лойиалаш, ишга тушириш.

РЕЗЮМЕ

диссертации Садчиковой Светланы Александровны на тему: «Модели и методы расчета широкополосных ассоциативных сетей коммутации» на соискание учной степени кандидата технических наук по специальности 05.12.13. – Системы, сети и устройства телекоммуникаций, распределение информации Ключевые слова: ассоциативная коммутация, ассоциативный коммутационный модуль, параллельные процессоры, кольцевая, звездообразная структуры сетей Объекты исследования: структура ассоциативной системы коммутации, сети ассоциативных систем коммутации, ассоциативная коммутация и маршрутизация, а также их модели и методы расчта Цель работы: исследование и разработка моделей узлов коммутации и методов расчта широкополосных многоуровневых N-мерных ассоциативных сетей коммутации.

Методы исследования: проводимые исследования базируются на алгебраической системе ассоциативной коммутации, теории вероятностей, теории массового обслуживания, теории групп, Z-преобразования рядов распределения, матричных алгоритмах, параметрическом анализе вероятностно-временных характеристик и оптимизации структуры сети.

Полученные результаты и их новизна: модель ассоциативной коммутационной фабрики, базирующейся на алгебре групп с алфавитом A и системой подстановки F; решение задач коммутации в модулях сети АСК представлено через операцию умножения алгебраической мультипликативной группы подстановки матричных элементов оперативной и программной памяти – области определения множества ОЕР модулей;

аналитические модели ассоциативных сетей коммутации кольцевой и звездообразной структур.

Практическая значимость: получены выражения для инженерного расчета ассоциативных сетей коммутации, позволяющие по заданным требованиям и исходным данным выбирать ее параметры. Определено, что применение АКФ в составе коммутационных систем обладает большей производительностью выше традиционных коммутационных сетей.

Степень внедрения и экономическая эффективность: результаты работы внедрены в АК «Узбектелеком» и в учебный процесс Ташкентского университета информационных технологий.

Область применения: расчет, проектирование, реализация механизма маршрутизации и ассоциативной коммутации для сетей доступа и транспортных сетей телекоммуникации.

RESUME

Thesis of Sadchikova Svetlana on the scientific degree competition of the doctor of philosophy in technical sciences on speciality 05.12.13. – Systems, networks and devices of telecommunication, information distribution subject: “Models and design methods of the broadband associative switching networks” Key words: associative switching, associative switching module, parallel processors, ring and star network structures Subjects of research: associative switching system structure, associative switching system networks, associative switching and routing, their models and design methods Purpose of work: research and design of switching node models and designing methods of the broadband multilevel N-dimension associative switching networks.

Methods of research: researches based on algebraic system of associative switching, probability theory, queueing theory, group theory, z-transform methods, matrix algorithms, parametric analysis of time-probabilistic characteristics and network stricture optimization.

The results obtained and their novelty: associative switching fabric model based on group theory with alphabet A and substitution system F; switching task solution in the network modules of the associative switching system is represented as multiplication operation of multiplicative algebraic substitution group of matrix elements in RAM and program memory (function domain of Neighbourhood Single Radius NSR); analytical models of associative switching system of the ring and star structures.

Practical value: Formulas for practical design of associative switching system are obtained. Formulas allow to choosing associative switching system parameters according specified requirements and initial data. It’s defined associative switching fabric application in switching systems have more higher performance in comparison with traditional switching systems.

Degree of embed and economic effectivity: results have been implemented to JSC “Uzbektelecom” and into educational program of Tashkent university of information technologies TUIT.

Field of application: dimension, design, realization of associative routing and switching mechanism for access and transport telecommunication networks.