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

Тип работы:
Реферат
Предмет:


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 004
МЕТОДИКА ОЦЕНКИ СТРУКТУР ТРАНСПОРТНЫХ СЕТЕЙ СВЯЗИ ЧИСЛЕННЫМИ МЕТОДАМИ
Орлова Л. И.
Военная академия связи им. Буденного С. М., Санкт-Петербург, Россия (194 064, г. Санкт-Петербург,
Тихорецкий пр-т, 3), е-mail: akacia25@rambler. ru_
В работе рассматривается универсальная методика, позволяющая оценивать предпочтительное множество планируемых к использованию структур транспортных сетей связи с целью выбора оптимальной в конкретных условиях ее эксплуатации. Оценка структур проводится с использованием метода Монте-Карло по параметру связности графа сети и параметру кондиционности маршрутов. Методика позволяет учитывать влияние случайных факторов и особенности применяемой на сети телекоммуникационной технологии. Научная задача решается исходя из основных принципов системного подхода с использованием математического моделирования. Представленная методика оценки имеет практическое значение в области построения транспортных сетей связи с использованием современных телекоммуникационных технологий. Методика рассчитана на оценку возможностей структур произвольного вида без ограничений на число их узлов и линий. Найден способ введения дополнительного ребра, приводящий к самым лучшим показателям структуры — ее связности и кондиционности маршрутов. Оценка кондиционности маршрутов структур показала, что она существенно зависит от технологии. В работе определено, что число центров коммутации при передаче речевой информации на сетях с коммутацией пакетов должно быть не более 4.
Ключевые слова: граф сети, параметр связности, количество остовных деревьев, параметр кондиционности маршрутов, метод Монте-Карло, алгоритм Флойда.
THE EVALUATION METHODOLOGY OF COMMUNICATION NETWORK TRANSPORT STRUCTURES BY NUMERICAL METHODS
Orlova L.Y.
Military Communications Academy Budennyi, Saint Petersburg, Russia (194 064, St. Petersburg, Tikhoretsky Ave., 3),
е-mail: akacia25@rambler. ru_
In this paper the universal methodology, is considered which allows to evaluate the set of planned structures for using of the networks communication transport structure to select the best in specific conditions of its operation. Evaluation of structures is carried out with using of the Monte Carlo method on the connectivity parameter of the network graph and parameter of the konditsionnost of routes. The methodology allows to consider the influence of random factors and the features used on the technology telecommunication network. The scientific problem is decided based on the basic principles of the system approach to the using of the mathematical modeling. The presented methodology of evaluation is practical significance in the field of construction of transport networks to using the modern telecommunications technologies. The methodology is designed to evaluate the abilities structure of any forms without restrictions on the number of nodes and lines. The way of enter additional rib, have been found which leads to the best metrics structure the connectivity and the konditsionnost of routes. The evaluation of a konditsionnost of routes structures has shown that it essentially dependents on technology. In this paper it is determined that the number of switching centers for transmitting speech information on packet switch networks must be not more than 4.
Keywords: network graph, connectivity parameter, number of spanning trees, parameter of a konditsionnost of routes, Monte Carlo method, Floyd'-s algorithm.
Потребность в оценке структур транспортных сетей связи (ТСС), а соответственно и в наличии самой методики оценки, связана с необходимостью выбора оптимальных структур сети еще на стадии их разработки (проектирования).
Наиболее удобным способом описания структуры сети связи является ее задание в виде графа [3]. Если структуры сравниваемых сетей не ориентированы на некоторую
базовую структуру, то наиболее полная их оценка может быть получена с использованием численных методов. Это определяется тем, что в условиях дестабилизирующих факторов параметры структур сетей могут существенно отличаться от параметров, полученных в их исходных состояниях. Поэтому в данном случае наиболее удобным способом оценки структур сетей связи в виде графов являются статистические методы, к которым относится метод Монте-Карло [2- 5].
Основная часть
Оценку структур транспортных сетей часто проводили по критерию связности графа сети. На наш взгляд, параметр связности сети достаточно информативно определяется показателем количества остовных деревьев Кост дер, соответствующих графу сети, предлагаемому к рассмотрению, поскольку на сети связи прежде всего важна полная взаимная доступность всех корреспондирующих узлов между собой. Наличие хотя бы одного остовного дерева обеспечивает такую взаимную достижимость, характеризуя самый критический вариант организации связи.
При выборе той или другой структуры ТСС важно прогнозировать их поведение в условиях различных деструктивных воздействий, поэтому оценивать эти структуры предлагается более информативным показателем — суммарным количеством остовных деревьев Кост дер, определяемым с помощью метода Монте-Карло. В одном испытании Кост дер вычисляется как минор последнего элемента главной диагонали Мпп матрицы связности
исследуемой сети К=[?у] после воздействия (Кост дер = Мпп).
При оценке сети связи с коммутацией пакетов (КП) параметра связности ее графа оказалось недостаточно. В таких сетях возникает дефицит времени на передачу пакетов трафика реального времени. Так, в сетях с КП даже в исходном их состоянии не все маршруты пригодны для передачи телефонных сигналов, где время задержки сигналов не должно превышать 250 мс [1- 4]. С учетом данного обстоятельства для сетей с КП следует ввести дополнительный параметр, характеризующий структуры сетей.
Вторым параметром, который, на наш взгляд, в наибольшей степени характеризует структуру сети, является кондиционность маршрутов для всех корреспондирующих пар узлов (КПУ) сети. Под кондиционностью маршрута будем понимать время, затрачиваемое на установление телефонной связи (технология с коммутацией каналов (КК)) и время на пересылку пакета той же телефонной связи (технология с КП) по данному маршруту.
Для технологии с КК кондиционный маршрут должен иметь не более 5 транзитных станций в своем составе (таковы требования сети «Памир»).
Как оказалось, найти однозначные оценки параметра кондиционности маршрутов при использовании на сети технологии с КП достаточно сложно. В первую очередь это связано с
наличием некоторого множества самих технологий с КП и большого числа производителей оборудования, при использовании которого эти оценки могут существенно отличаться друг от друга. Если предположить, что речевую информацию требуется передать с Дальнего Востока и на Запад России (Ь=10 000 км), то согласно расчетной формуле (1) [1], общее время задержки не превысит требуемое при 3, 4 узлах коммутации.
Тзад = Тр+Тпк+Тпр+Тб, (1)
где: Тр — задержка, определяемая временем распространения электрического сигнала по кабелю связи, проложенному между отправителем и получателем. Оно зависит от типа кабеля и для оптических кабелей равно 5 мкс/км-
Тпк — задержка, определяемая временем, необходимым на выполнение операции преобразования речевого сигнала в цифровой вид и его пакетизацию. Данное время зависит от типа используемого алгоритма преобразования речевого сигнала. Так, например [1], при использовании стандарта 0. 711 это время равно 30 мс. При использовании других алгоритмов время может увеличиваться-
Тпр — задержка, определяемая временем прохождения пакетов по узлам коммутации транспортной сети. Время задержки зависит от числа различных сетевых устройств, включенных в маршрут прохождения пакетов, а также от времени работы устройств при обработке пересылаемых пакетов. Данный тип задержки в наибольшей степени зависит от используемых технологий, типа сетевого оборудования и возможности его стыковки [1- 4], а также от величины буфера сетевого оборудования в транзитных узлах коммутации. Причем при расчетах необходимо ориентироваться на максимальную величину этой задержки, соответствующую наихудшим условиям функционирования сети при перегрузках (резких всплесках, свойство самоподобия трафика). В среднем данную величину задержки можно оценить в 30 мс, которая, однако, должна уточнятся по реальным сведениям о технологии и возможностям используемых сетевых средств связи-
Тб — задержка, определяемая временем работы устройств на узле получателя. Как и задержка Тпк, она определяется алгоритмами обработки пакетов приемного пункта, а также временем буфера джиттера. Величина задержки данного типа [1] может быть оценена в 40 мс.
Предлагаемая методика оценки является универсальной и позволяет анализировать рассматриваемые структуры как в исходном состоянии, так и при воздействиях различного рода, задаваемых в виде вероятности повреждения ее ребер и узлов. Кроме того, методика позволяет прогнозировать состояние структур сетей и производить их сравнение с учетом возможностей, используемых на ТСС телекоммуникационных технологий.
Исходными данными для работы алгоритма являются:
1) граф транспортной сети, задаваемый матрицей связности К = [^?. у],
-1, если вершины Ь? и? у смежны,
0, если вершины ^ и? у не смежны, (2)
degЬ^, если I = _/-
2) узлы связи потребителей телекоммуникационных услуг и линии их привязки к узлам коммутации-
3) вероятности повреждения узлов и линий связи (Руз, Рлин) —
4) число испытаний, необходимых для работы алгоритма Монте-Карло с требуемой точностью-
5) г — число пунктов транзита (узлов коммутации) в составе кондиционного маршрута
сети.
Блочная схема алгоритма оценки структуры транспортной сети приведена на рисунке 1. Она состоит из следующих блоков и отдельных процедур:
— блока статистических испытаний (метод Монте-Карло),
— блока нахождения маршрутов между требуемыми парами корреспондирующих узлов связи потребителей телекоммуникационных услуг (алгоритм Флойда),
— процедуры нахождения суммарного числа остовных деревьев КосТдер,
— процедуры определения поврежденных линий сети связи,
— процедуры вычисления вероятности сохранения связности сетью (р),
— процедуры оценки кондиционности маршрутов.
В качестве промежуточных данных, необходимых для перехода от работы одного алгоритма к работе другого, следует считать структуры сетей, соответствующие определенным вероятностям связности анализируемой сети.
Ограничение:
при использовании метода Монте-Карло для оценки параметров структур вероятности выхода из строя предполагаемых узлов и линий связи выбирались одинаковыми, поскольку все эти параметры оценки относятся к графу сети:
?m =, где iG)=1, т и Pyi = Руз, где iG)=1, п.
Для определения кратчайших путей между всеми парами корреспондирующих узлов использовался специальный алгоритм Флойда, поскольку его сложность составляет O (n3), что на порядок лучше по сравнению с n-кратным применением алгоритма Беллмана-Форда (O (n4)) и экономит 50% времени по сравнению с n-кратным применением алгоритма Дейкстры. В работе определялось по два кратчайших маршрута для каждой КПУ, поскольку они обеспечивают наибольшую живучесть направлений связи.
Рис. 1. Блок-схема алгоритма оценки структуры ТСС. В наибольшей степени сравнительная оценка структур транспортных сетей между собой может быть использована как на этапе планирования, так и при восстановлении связи. При восстановлении связи очень важно понимать, какая из восстановленных линий приводит к лучшей связности сети и прибавляет большее количество кондиционных маршрутов 5 конд.
По этой причине в качестве примера для сравнения выбраны структуры, отличающиеся дополнительным ребром, вводимым в некоторую базовую сеть. Базовая сеть представлена в виде решетки с числом узлов п=12 и подключенными к ним шестью оконечными узлами связи потребителей телекоммуникационных услуг (рисунок 2а).
Сеть КЕТ 11 (рисунок 2б) образована путем введения дополнительного ребра между узлами 14−18, КЕТ 12 (рисунок 2в) — между узлами 8−16, КЕТ 13 (рисунок 2г) — между узлами 7−18, КЕТ 14 (рисунок 2д) — между узлами 8−16 и 7−18, а сеть КЕТ 15 (рисунок 2г) — между узлами 9−16 и 7−18.
а) МЕ'-Г 00 б) ЫЬТ 11 и^ NI г 12 г]и д) ЫКП4 е)1ЧКТ13
Рис. 2. Исследуемые структуры сетей в виде «решетки». Вид структур после воздействия представлен на рис. 3 (а-в). Каждому воздействию на узлы и линии будет соответствовать вероятность сохранения связности сетью р/.
9-^-5? 9-^--ф Ф-& amp---ф о-Ф-
Рис. 3а. Исследуемые структуры сетей в виде «решетки»
при Руз =0,005=соп81 и Рлин=0,01 (р/= 0,9).
Ф-®-(r) С-(c) —
Рис. 3б. Исследуемые структуры сетей в виде «решетки» при Руз =0,005=сопБ1 и Рлин=0,12 (р/ =0,8).
а) б) В) Г) Д) с)
Рис. 3 В. Исследуемые структуры сетей в виде «решетки» при Руз =0,005=00^ и Рлин=0,19 (р/ =0,7).
Вначале оценим суммарную величину остовных деревьев К*0сгдер в различных условиях воздействия на структуры сетей (р/) и определим выигрыш по их числу в зависимости от количества и способа введения дополнительных линий.
Анализ таблицы 1 показал, что ввод в структуру сети ребра между узлами, образующими путь максимального ранга п (гтах) более чем в 2 раза увеличивает д (°р, т. е. связность максимальна при введении линии между узлами, образующими п (гтах) в данной сети.
Таблица 1
Выигрыш по еРр1СГ. дрр для анализируемых структур при различных воздействиях
!~)тп г. паниа К Н77-а-п.™ту стрчпур к]]х ЧБИлу в сцмгурз МЬТ 00 Бывтрыш Б3 Кф^ Приразличныхр-
1 ¦119 ?3 ¦V
1. -6 1: 51 1,7 В 113
ш 161 146 1,3
а. Ог. 29 1: 05 ш
б* вне =, 14 4,71 ?1-
634 452 4: :7 151
Результаты оценки структур по параметру кондиционности маршрутов для случая
построения таких сетей с рисунках 4, 5.
использованием технологий КК и КП представлены на
Рис. 4. Зависимость Енконд от связности структуры сети (для технологии с КП).
(!
I и ¦& gt- 4J i jf
Рис. 5. Зависимость Енконд от связности структуры сети (для технологии с КК).
По их данным, технология с КК имеет существенный выигрыш над технологией КП по числу кондиционных маршрутов во всех анализируемых структурах. Выводы
1. Представленная методика имеет практическое значение в области построения ТСС с использованием современных телекоммуникационных технологий.
2. Методика оценки является универсальной и позволяет анализировать предлагаемые структуры при различных воздействиях на сеть связи.
3. Методика рассчитана на оценку возможностей структур произвольного вида без ограничений на число их узлов и линий, что позволяет использовать ее при разработке структур ТСС для конкретных операций и задач.
4. Найден способ введения дополнительного ребра, приводящий к самым лучшим показателям структуры — ее связности и кондиционности маршрутов.
5. Оценка кондиционности маршрутов структур показала, что она существенно зависит от технологии. В работе определено, что число центров коммутации при передаче речевой информации на сетях с КП должно быть не более 4.
Список литературы
1. Гольдштейн Б. С., Соколов Н. А., Яновский Г. Г. Сети связи. — СПб.: БХВ-Петербург, 2011. — 400 с.
2. ГОСТ Р 51 901. 5- 2005 (МЭК 60 300−3-1: 2003. Управление надежностью. Часть 3−1. Руководство по применению. Методы анализа надежности. Руководство по методологии).
3. Кристофидес Н. Теория графов. Алгоритмический подход / пер. с англ. — М.: Мир, 1978. -432 с.
4. Мак-Квери, Мак-Грю, Фой Передача голосовых данных по сетям Cisco Frame Relay, ATM и IP / пер. с англ. — М.: Издательский дом «Вильямс», 2002. — 512 с.
5. Соболь И М. Метод Монте-Карло. — М.: Наука, 1968. — 64 с.
Рецензенты:
Саенко И. Б. д.т.н., профессор, профессор Военной академии связи им. Буденного С. М., г. Санкт-Петербург-
Мякотин А. В., д.т.н., профессор, профессор Военной академии связи им. Буденного С. М., г. Санкт-Петербург.

ПоказатьСвернуть
Заполнить форму текущей работой