автореферат диссертации по радиотехнике и связи, 05.12.14, диссертация на тему:Разработка и исследование метода оптимизации межстанционных связей на сетях с иерархической структурой

.та о» - 8 ом «

МИНИСТЕРСТВО СВЯЗИ РОССИЙСКОЙ ФЕДЕРАЦИИ Московский технический университет.связи и информатики

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

Шулешова Ирина Николаевна

УДК 621.395.

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДА ОПТИМИЗАЦИИ МЕЖСТАНЦИОННЫХ СВЯЗЕЙ НА СЕТЯХ С НЕИЕРАРХИЧЕСКОЙ СТРУКТУРОЙ

Специальность: 05.12.14 - Сети, узлы связи и распределение информации

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

Москва 1996

Работа выполнена на кафедре автоматической электросвязи Московского технического университета связи и информатики (МТУСИ).

Научный руководитель - доктор технических наук, профессор Ю.В. Лазарев.

Официальные оппоненты

- доктор технических наук, профессор С.Н. Степанов, кандидат технических наук, доцент Т.В. Иевлева

Ведущее предприятие - Центральный научно-исследовательский институт связи Министерства связи РФ

Защита состоится " ¿Г " б^ТР^гЛ^А'^ 1996 т. в часов на

заседании диссертационного совета 'К 118.06.02 при Московском техническом университете связи и информатики по адресу: 111024, г.Москва, ул. Авиамоторная, 8а, МТУСИ.

С диссертацией можно ознакомиться в библиотеке МТУСИ. Автореферат разослан ** -У " (Ь/иЛ 1996 г.

Ученый секретарь

диссертационного совета К 118.06.02 кандидат технических наук, доцент

/{¿ЦК

Е.В. Демина

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

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

Цель и задачи исследования. Целью диссертационной работы является исследование и разработка метода оптимизации межстанционных связей на сети с неиерархической структурой, учитывающего существование обходных направлений и различные способы коммутации на сети: каналов, пакетов и совместной коммутации каналов и пакетов. Для -решения этой задачи предложен критерий эффективности для сетей связи с различными способами коммутации. В диссертации разработана итерационная процедура, позволяющая рассчитать качество обслуживания поступающих вызовов на неиерархической сети с коммутацией каналов и пакетов при статической маршрутизации вызовов с учетом двух моментов поступающей нагрузки - математического ожидания и дисперсии. Практической задачей исследования является разработка метода оптимизации межстанционных связей на нсиерархнческен сети, позволяющего построить сеть, локально-оптнмалысую по критерию эффективности использования ее ресурсов.

Методы исследования. Для проведения исследований в диссертации использовались теория графов, теория вероятностей, теория телетрафика, теория сетей связи, а также теория оптимизации.

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

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

з

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

- для ссгн с коммутацией каналов - произведение коэффициента готовности и вероятности потерь на пучке каналов;

- для сети с коммутацией пакетов - отношение времени задержки в передаче информации на линии связи к допустимому времени задержки передачи информации;

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

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

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

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

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

Практическая ценность работы и использование ее результатов. Предложенные диссертационной работе критерий эффективности сети связи, метод и программа оптимизации структуры межстанционных связей, а также процедура оценки качественных показателей обслуживания были использованы в 16 ЦНИИИ МО РФ при проведении научно-исследовательских работ. Проведенный анализ методов оптимизации структуры сети связи был использован в учебном процессе МТУСИ. Использование результатов диссертационной работы подтверждено соответствующими актами.

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

Апробация работы. Основные результаты диссертации докладывались, обсуждались и получили положительную оценку на: 8-й и 9-й Белорусских школах-семинарах по теории массового обслуживания(Брест, 1992; Минск, 1993), Международной конференции но информационным сетям и системам(С.Петербург. 1994), Международном форуме информатизации (Москва, 1995), научно-технических конференциях профессорско-преподавательского состава

МТУСЩМосква, 1993,1994), заседаниях кафедры автоматической электросвязи(Москва, 1992-1994).

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 96 наименований и трех приложений. Диссертация включает 135 страниц машинописного текста, 32 рисунка, 1 таблицу.

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность диссертационной работы, сформулированы основная цель и задачи исследования.

В первой главе диссертации анализируются причины создания цифровой сети с шггеграцией служб (ЦСИС).

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

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

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

Рассмотрены существующие методы оптимизации структуры информациошюй сети связи. Их классификация приведена на рис. 1.

Метод насыщенного сечения Метод исключения замя^тых пепей

Метод слабейшего сечения Метод замены ветвей '

Рис. I

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

Методы математического программирования позволяют найти точное решение поставленной задачи и их теоретическая сходимость не вызывает

б

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

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

Для алгоритмов эвристических методов характерно последовательное изменение одного или одновременно нескольких структурных параметров или "координат", в связи с чем эти алгоритмы получили название алгоритмов покоординатной оптимизации. В зависимости от способа изменения параметров алгоритмы эвристических методов разделены на три класса: удаления ветвей, добавления ветвей и перестановки ветвей. Многие эвристические алгоритмы, сходимость которых не удается доказать, оказываются весьма эффективными при расчетах на ЭВМ. Причина этого, по всей видимости, кроется в том, что инженерный или эвристический подход к построению алгоритма основан на глубоком знании физической и технической сути задачи.

Каждому классу эвристических методов присущ ряд недостатков. В частности, методы, относящиеся к классам добавления и перестановки ветвей требуют синтеза начальной структуры. Существуют методы синтеза начальной структуры, такие, как алгоритмы Прима, Гомори и Ху, метод М-структур и другие, но среди них нет ни одного точного, что вносит дополнительную погрешность при проектировании сети связи. Для методов, относящихся к классу удаления ветвей, исходной является полносвязная или заданная избыточная структуры сети и не требуется построение начальной структуры. Исходя из этого в диссертации разработан метод оптимизации, относящийся к этому классу.

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

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

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

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

При разработке алгоритма были приняты следующие допущения.

1. Каналы одностороннего действия.

2. Потоки вызовов, поступающие в сеть, взаимно статистически независимы и являются пуассоновскими.

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

Исходными данными для синтеза сети являются:

- число узлов на сети К;

- матрица требований на установление соединений У. Элементы матрицы равны интенсивности нагрузки в Эрл., возникающей от узла \ к узлу j в ЧНН. Если между этими узлами нет потока нафузки, то соответствующий элемент матрицы требований равен нулю;

- матрица каналов V. Если от узла 1 к узлу j может быть проложена линия связи, то соответствующий элемент матрицы каналов равен числу каналов в ней. Если между узлами линию связи проложить нельзя, то соответствующий элемент матрицы каналов равен нулю;

- матрица коэффициентов готовности ветвей Н. Если элемент матрицы каналов равен нулю, то и соответствующий элемент мафицы

надежности равен нулю, т.к. вегвь (i,j) в сети отсутствует. Если элемент матрицы каналов не равен нулю, то элемент матрицы II - вероятность того, что ветвь находится в работоспособном состоянии т.е. значение элемента li(i,j) равно коэффициенту готовности ветви (i,j):

- качество обслуживания потоков вызовов на сети Р. Вероятность отказа для каждого потока должна быть меньше или равна Р. :

В качестве критерия оптимизации сети в предлагаемом методе используется эффективность использования ресурсов сети G, которая определяется но формуле: 1 NN

О = max— • £ У, g(i, j), (1)

М i=1j=1

где ß(ij) - эффективность ветви (i,j);

N - число узлов на сети;

М - число ветвей на сети.

Вводится понятие эффективности ветви g(ij) графа сети связи, под которой понимается вероятность того, что все каналы находятся в работоспособном состоянии и заняты:

g(i,j)-h(ij)p(i,j), (2)

где h(ij) - коэффициент готовности ветви (ij); p(ij) - вероятность потерь на этой ветви.

При этом вводится ограничение на p(k,I), исходя из заданного качества обслуживания поступающих вызовов:

р(к,1) £ рд, для всех поступающих в сеть потоков y(k,I).

В более общем случае:

g(iJ)=Ä,ij-h(i,j)-p(i,j), (3)

п ■

где Л. = Я -1 ~~- стоимостной коэффициент, vy WJ п Uj

(v - стоимость прокладки линии связи (ij), или стоимость аренды выделешюго канала,

Cmin = min Су

i,j=l+N

я - весовой коэффициент ветви (i,j), характеризующий с точки

зрения проектировщика целесообразность использования данной ветви.

Таким образом, при определении эффективности ветвн учитываются такие показатели, как ее надежность, стоимость и вероятность потерь.

При решении задачи оптимизации структуры сети связи, сеть удобно представлять в и ид с графа, при этом узлы коммутации соответствуют

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

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

Рис 2.

Для определения порядка выбора исходящих направлений модифицирован обобщенный алгоритм Флойда для нахождения к -кратчайших путей таким образом, чтобы для каждой пары вершин (Ц)

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

В качестве основного критерия выбора пути принято минимальное число транзитных участков при относительно равномерной длине ветвей, в противном случае в качестве основного критерия выбирается длина ветви КУ)- Дополнительным критерием выбора пути при равнозначных основных критериях служит величина, обратная коэффнциету готовности ветви -(1-Ь(У)). Таким образом, при относительно равномерной длине ветвей графа сети каждой из них присваивается вес:

аш(м)=1+<1-Ь(ч))=2-Ь(.о), (4)

а в противном случае:

4п(ц>1(У)+1-11(ц). (5)

Предпочтение отдается маршрутам передачи потоков нагрузки с наименьшим суммарным весом входящих в них ветвей.

Вероятности потерь на ветвях графа сети связи определяются итерационным методом. На всех итерациях, за исключением нулевой, расчет осуществляется методом эквивалентных замен, т.к. на сети приняты обходные направления. На нулевой итерации расчет производится по первой формуле Эрланга. Матрица вероятностей потерь на ветвях графа сети, полученная на предыдущей итерации, служит исходной для последующей. На нулевой итерации в качестве исходной служит нулевая матрица потерь. После определения вероятностей потерь для поступающих на ветви графа сети потоков нагрузки рассчитываются эффективности каждой ветви но формулам (4) или (5) в зависимости от исходных данных.

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

После расчета матриц суммарных нагрузок на ветви и суммарных дисперсий в соответствии методом эквивалентных замен для каждой ветви определяется эквивалентная нагрузка уг>(У) и эквивалентное число каналов уб(у) на ветвях графа. В этом случае возможны три варианта расчета вероятности потерь на ветви в зависимости от знака <1я(у):

1. Если суммарная дисперсия с1з(у)>0, то суммарный поток, поступающий на эту ветвь, является избыточным. Неизвестные параметры

и v.s(i,j) эквивалентного пучка можно найти Т|>емя способами: по номограммам, таблицам или решив систему уравнений.

11оследний наиболее предпочтителен при решении задачи на ЭВМ. Существует множество методов отыскания решения систем нелинейных уравнений. Выбирается итерационный метод покоординатной релаксации, т.к. он не требует вычисления производных, что при наличии неизвестного в первой формуле Эрланга под знаком факториала существенно усложнило бы задачу.

2. Если суммарная дисперсия на ветви <1з(у)<0, то суммарный поток, поступающий на ветвь (у), является обслуженным. Неизвестные параметры ук(у) и уб^о) находятся как решение следующей системы уравнений:

Г<М>О) = - У^, .Ш • й - Я1(1,й); { »к;, д = у^, 3) • (1 - Е^и)^'"'

3. В случае если <15(у)=0, поступающий на ветвь поток является пуассоновским, и расчет вероятности потерь ведется не методом эквивалентных замен, а по формуле Эрланга.

После расчета матриц УБ и УБ вычисляется матрица Ив избыточного потока с объединенного пучка каналов (те(ц)+у5(У)):

У*1' ■>) • Е^^и/У^)). <*5(и) < 0; • < ОМУ) >

УяС^.Л-Е^.иО.Л ¿з(У)<0МУ)<У5(У).

Вероятность потерь на ветви определяется по формуле: . .

Далее элеме1тгы полученной матрицы РБ сравниваются с элементами матрицы Р, полученной на предыдущей итерации. Если

1р(д)-р5(у)|<едляБСех(У), (6)

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

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

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

12

"(¡.л»

обслуживания. Если качество обслуживания всех потоков не ниже заданного, IX) осуществляется переход к процедуре удаления ветви. В противном случае исходная сеть не обеспечивает заданное качество обслуживания потоков, и алгоритм заканчивает работу. В этом случая для решения задачи оптимизации структуры сети необходимо внести изменения в исходные данные. Возможны два решения: добавление в сеть всшей (если исходная сеть была неполносвязной) или снижение требовании к качеству обслуживания.

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

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

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

При разработке алгоритма синтеза сети были приняты следующие допущения:

1. Каналы в сети одностороннего действия.

2. Потоки вызовов, поступающие в сеть, взаимно статистически независимы и являются пуассоноскими.

3. Линии и узлы связи считаются абсолютно надежными.

4. Время обработки одного пакета в узле коммутации постоянно и, более того, пренебрежимо мало.

5. Для размещения пакетов в узлах сети имеются буферы неограниченного объема.

Исходными данными для синтеза сети связи с коммутацией пакетов являются:

- число узлов на сети И;

- матрица пропускных способностей линий связи О, элементы которой

равны пропускной способности ветви (у) в бит/с, если ветвь (у) входит

в структуру сети, и нулю в противном случае;

- матрица требований В, элемент которой Ь(у) определяет объем передаваемой информации между узлами I и ] п битах;

- допустимое время задержки для поступающих в сеть протоков вызовов

<д-

В качестве критерия оптимизации в предлагаемом методе используется величина Оцл, определяемая по формуле(1).

Вводится понятие эф4>скгивности ветви графа сети с коммутацией пакетов

1д

где - рассчитанное время задержки на ветви (Ц).

Вариант сети, для кагорого рассчитывается эффективность линий связи

удовлетворяет требованиям к качеству обслуживания и отношение —

всегда будет меньше единицы

В отличие от сетей с коммутацией каналов основным параметром качества обслуживания в сетях с коммутацией пакетов служит среднее время задержки при передаче сообщения или вероятность своевременной доставки сообщения. Расчет второго параметра требует построения достаточно сложной аналитической модели рассматриваемой сети. Кроме того, основным недостатком аналитических моделей является их методическая неточность, связанная с аппроксимацией реальной сети той или иной аналитической моделью. Исходя из этого в качестве основного параметра ¡качества обслуживания выбрано среднее время задержки. Для расчета среднего времени задержки на сети необходимо в первую очередь распределить потоки вызовов, поступающие в сеть по ветвям графа сети. При этом используется алгоритм Флойда для выбора кратчайших путей. Для распределения поступающих потоков используется модифицированный алгоритм отклонения потока, который, в отличии от классического метода отклонения потока, разработанного Клейнроком и Гсрлой, исключает выход полученного потока за пределы допустимой области. В результате расчета сети определяется время задержки на каждой ветви. Этот расчет позволяет рассчитать их эффективность по формуле (7).

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

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

разнородной информации (представленная в цифровой форме аналоговая информация и данные). В связи с этим на УК ЦСИС целесообразно использовать совместную коммутацию каналов и пакетов, когда в зависимости от требований, предъявляемых к качеству обслуживания различных потоков, для их передачи выбирается тог или иной способ коммутации на УК.

Простейшая концепция передачи в ЦСИС нагрузки КК и КП заключается в предоставлении фиксированного числа временных каналов способам КК и КП соответственно. Более перспективной для ЦСИС является концепция "гибкой технологии доставки", которая сводится к использованию метода перемещающейся границы между ресурсами ЛС для двух режимов коммутации.

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

где 1Я - допустимое время задержки для поступающих в сеть вызовов. Коэффициенты а.) и а^ являются весовыми коэффициентами способов коммутации каналов или пакетов. Если вызовы этих двух режимов принимаются равнозначными, то а1=а2=1 и формула (8) принимает следующий вид:

Варьируя значения а! и аь можно изменять приоритет критериев, характеризующих ветвь графа сети связи.

Рассматриваемый метод оптимизации структуры сети с интеграцией служб относится к классу эвристических методов удаления ветвей. На первом этапе происходит процесс определения последовательности выбора обходных направлений для каждого поступающего в сеть потока вызовов. Затем выполняется расчет показателей качества обслуживания вызовов. После этого становится возможным рассчитать эффективность каждой ветви по формуле (8) или (9). На следующем этапе выбирается наименее эффективная ветвь и удаляется из структуры сети. Затем вновь рассчитывается качество обслуживания поступающих в сеть потоков. Если оно ниже допустимого, то ранее удаленная ветвь возвращается в сеть. Таким

(8)

■д

(9)

■"Г

образом просматриваются все ветви в порядке возрастания их эффективности.

При разработке алгоритма для решения любой задачи встает вопрос: Какова ее вычислительная сложность? Зная теоретическую нижнюю 1раницу для эффективности алгоритма, можно лучше оценить имеющиеся алгоритмы и определить, сколь много усилий следует тратить на поиск лучшего решения. Например, если известно, что задача труднорешаемая, можно довольствоваться эвристическими способами нахождения приближенных решений.

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

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

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

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

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

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

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

Основные результаты выполненной работы заключаются в следующем:

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

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

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

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

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

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

7. Оценена производ1ггслыгость разработанных для ЭВМ программ с точки зрения объема занимаемой памяти и времени выполнения.

Основные положения диссертации опубликованы в следующих работах:

1. Лазарев Ю.В., Цирик И.А., Шулешова И.Н. Оптимизация структуры информационной сети.// Сети связи и сети ЭВМ. Анализ и применение. - г. Минск, 1992 г. - с. 47-48(8-ая Белорусская школа-семинар по теории массово!« обслуживания, г. Брест, 1992 г. ).

2. Лазарев Ю.В., Цирик И.А., Шулешова И.Н. Метод оптимизации сети связи при развитии ее структуры. // Математические методы исследования систем и сетей массового обслуживания. Тезисы докладов. - Минск, 1993 (9-ая Белорусская школа-ссмнпар по теории массового обслуживания ), с. 53.

Я. Шулсшова И.Н. Итерационный меюд оптимизации структуры сети элсктросиязи. // Тез. докл. Научно-техн. конференция профессорско-преподавательской) и инженерно-технического состава МТУСИ. - М., 1993 с.48.

4. Цирик И.А., Шулсшова И.Н. Методы синтеза информационной сети с обходными направлениями. // Тез. докл. НТК профессорско-преподавательского и инженерно-технического состава МТУСИ. - М., 1994, с.46.

5. Шулешова И.Н. Метод оптимизации цифровой информационной сети. Международная конференция по информационным сетям и системам. -С.Петербург, ЛОНИИС, ГУТ им. М.Бонч-Бруевича, 1994, с.265-268.

6. Цирик И.Л., Шулсшова И.Н. Метод синтеза информационной сети с обходными направлениями, деп. ЦНТИ Информсвязь №2005 св 1994.

Подписано в печать 06.06.96г. Формат 60x84/16.Печать офсетная. Объем 1,0 усл.п.л. Тираж 100 экз. Заказ 224. Бесплатно.

ООП МП "Информсвязьиздат". Москва, ул. Авиамоторная, 8.