Методика формирования потоковой структуры технологической сети связи ОАО «РЖД» тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат наук Лукичев Михаил Михайлович

• Лукичев Михаил Михайлович
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Лукичев Михаил Михайлович

Список сокращений

ВВЕДЕНИЕ

1 Анализ характеристик технологической сети связи и подходов к построению первичных потоковых структур

1.1 Общая характеристика технологической сети и первичной потоковой структуры

1.1.1 Анализ технологической сети связи ОАО «РЖД»

1.1.2 Анализ первичной потоковой структуры

1.2 Анализ формирования множества маршрутов при проектировании технологических сетей связи

1.2.1 Анализ алгоритмов поиска кратчайших маршрутов

1.2.2 Анализ алгоритмов определения нескольких независимых маршрутов

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

1.4 Постановка задачи и формирование структуры научного исследования

1.5 Выводы по разделу

2 Разработка моделей генераторов трафика различных источников в технологических сетях связи

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

2.1.1 Определение вероятностно-временных характеристик трафика протокола контроля и сетевого управления (SNMP)

2.1.2 Определение вероятностно-временных характеристик аудио трафика VoIP

2.1.3 Определение вероятностно-временных характеристик видео трафика реального времени (H.264)

2.2 Формирование имитационных моделей различных эквивалентных генераторов сетевой нагрузки

2.2.1 Формирование имитационной модели эквивалентного генератора трафика

протокола контроля и сетевого управления (SNMP)

2.2.2 Формирование имитационной модели эквивалентного генератора аудио трафика (VoIP)

2.2.3 Формирование имитационной модели эквивалентного генератора видео трафика реального времени (H.264)

2.3 Методика формирования имитационной модели эквивалентных генераторов сетевой нагрузки

2.4 Выводы по разделу

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

3.1 Имитационная модель фрагмента сети с распределением потоков и оценка параметров качества обслуживания сети на ее основе

3.1.1 Исходные данные для формирования модели фрагмента сети с распределением потоков

3.1.2 Описание модели узлов сети

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

3.1.4 Характеристики генераторов трафика

3.1.5 Разработка модели фрагмента сети

3.1.6 Результаты моделирования

3.2 Разработка модели распределенной технологической сети связи для оценки

ряда показателей качества обслуживания сети

3.2.1 Описание модели

3.2.1 Формирование модели обработки потоков в узлах сети

3.2.2 Характеристики генераторов трафика

3.2.3 Результаты моделирования

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

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

3.4.1 Описание модели

3.4.2 Результаты моделирования

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

3.6 Выводы по разделу

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

4.1 Модифицированная методика определения набора реберно-независимых маршрутов

4.2 Практическая реализация алгоритма поиска к оптимальных независимых маршрутов

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

4.2.2 Оценка времени получения всех маршрутов

4.3 Модифицированная методика формирования ПС путевым методом на базе оптимальных реберно-независимых маршрутов

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

4.5 Определение коэффициента готовности методом Монте-Карло

4.6 Выводы по разделу

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

Приложение А. Расчет ППС путевым алгоритмом

Приложение Б. Расчет ППС методом сечений

Приложение В. Исследования видео-трафика реального времени

Приложение Г. Анализ подходов к моделированию сетей

Приложение Д. Распределение потоков при однопутевой маршрутизации

Приложение Е. Распределение потоков с применением модифицированного

алгоритма поиска маршрутов

Приложение Ж. Распределение потоков с применением модифицированного алгоритма поиска частично-зависимых маршрутов

СПИСОК СОКРАЩЕНИЙ

Сокращение Расшифровка

1

ОбТС Общеслужебная (общетехническая) сеть связи

ОТС Оперативно-техническая сеть связи

КП Корреспондирующая пара

ПС Потоковая структура

ППС Первичная Потоковая структура

ТСС Технологические сети связи

IPTD IP packet Transfer Delay - задержка передачи IP пакета

IPDV IP packet Delay Variation - девиация задержки передачи IP пакета

IPER IP packet Error Ratio - коэффициент ошибок IP пакетов

IPLR IP packet Loss Ratio - коэффициент потерь IP пакетов

VoIP Телефонная связь по протоколу IP

H.264 Стандарт сжатия видео

QoS Качество обслуживания (Quality of Service)

SNMP Простой протокол сетевого управления (Simple Network Management Protocol)

IP Протокол сетевого уровня (Internet Protocol)

Введение диссертации (часть автореферата) на тему «Методика формирования потоковой структуры технологической сети связи ОАО «РЖД»»

ВВЕДЕНИЕ

Актуальность темы исследования. Обеспечение эффективного и безопасного процесса перевозок пассажиров и грузов напрямую зависит от системы управления территориально-распределенными объектами инфраструктуры ОАО «РЖД». Основной системой, обеспечивающей доставку управляющей, диагностической и прочей информацией является технологическая сеть связи (ТСС), в основном базирующаяся на пакетно-ориентированных технологиях.

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

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

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

Степень разработанности темы. Потоковые структуры сетей связи позволяют решить задачу о возможности проектируемой сети связи реализовать заданные требования при ограниченных ресурсах узловых устройств и линий связи. Решением граф-аналитических задач, связанных с потоковыми структурами сетей связи посвящены работы: А.Т. Лебедева, А.М. Лихачева, В.Е. Кузнецова, А.А. Муравцова, А.В. Бабкина, А.Н. Назарова, К.И. Сычева, А.Н. Соколова, М.П.

Березко, В.М. Вишневского, Е.В. Левнера, Е.В. Федотова, Е.В. Опарина, Д. Бертсекас, Р. Галлагер, М.Б. Ахмади, Ю.Е. Малашенко, Н.М. Новикова и пр.

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

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

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

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

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

Для достижения поставленной цели в диссертационной работе решены следующие задачи:

1. Проведен системный анализ существующих подходов к формированию 1111С, определены области применения каждого из рассмотренных методов, разработана методика построения ППС.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- при составлении типовых материалов для проектирования 411404-ТМП «Сети передачи данных ОАО «РЖД» на базе современных телекоммуникационных технологий и технических решений» в институте по проектированию сигнализации, централизации, связи и радио на железнодорожном транспорте «Гипротранссигналсвязь» - филиал открытого акционерного общества «Росжелдорпроект»;

- в учебном процессе федерального государственного бюджетного образовательного учреждения высшего образования «Петербургский государственный университет путей сообщения Императора Александра I» кафедры «Электрическая связь» при проведении занятий по дисциплинам «Системы управления телекоммуникациями» и «Системы и сети передачи информации»;

- при выполнении составной части НИР «Демо-УММ» в ЗАО «Институт телекоммуникаций»;

- при формировании проектной документации, проведении пусконаладочных испытаний, а также при эксплуатации ООО «Телетакс» технологических и сетей связи общего пользования на объектах ГУП «Петербургского метрополитена».

Внедрение результатов диссертации подтверждается соответствующими актами. Результаты работы могут быть использованы также исследовательскими организациями, учебными заведениями, производителями оборудования электросвязи и эксплуатационными компаниями по тематике «Телекоммуникационные сети связи».

Апробация работы. Основные результаты и положения диссертационной работы обсуждались на научных конференциях и семинарах: IEEE Xplore 2018 Systems of Signals Generating and Processing in the Field of on Board Communications, (г. Москва, 14-15 марта 2018г.), IV международная научно-технической и научно-методической конференции «Актуальные проблемы инфотелекоммуникаций в

науке и образовании» (г. Санкт-Петербург, СПбГУТ им. проф. М. А. Бонч-Бруевича, 3-4 марта 2015 г.); VII Международная научно-практическая конференция «Актуальные вопросы науки, технологии и производства» (г. Санкт-Петербург, 20 - 21 марта 2015 г.); 67, 69, 70, всероссийские научно-технические конференции, посвященные Дню Радио (г. Санкт-Петербург, СПбНТОРЭС, 18 - 26 апреля 2012 г., 17 - 25 апреля 2014 г., 17 - 25 апреля 2015 г.).

Публикации. Всего по теме диссертации опубликована 21 печатная работа, в том числе шесть - в рецензируемых изданиях, включенных в перечень ВАК при Министерстве науки и образования Российской Федерации и одна рецензируемая в зарубежных изданиях Scopus и Web of Science.

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

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

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

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

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

Объем и структура работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка литературы из 93 наименований, 8 приложений, изложена на 208 страницах машинописного текста, содержит 31 таблицу и 102 рисунка.

1 АНАЛИЗ ХАРАКТЕРИСТИК ТЕХНОЛОГИЧЕСКОЙ СЕТИ СВЯЗИ И ПОДХОДОВ К ПОСТРОЕНИЮ ПЕРВИЧНЫХ ПОТОКОВЫХ СТРУКТУР

1.1 Общая характеристика технологической сети и первичной потоковой

структуры

1.1.1 Анализ технологической сети связи ОАО «РЖД»

Технологическая сеть связи (ТСС) ОАО «РЖД» предназначена для ведения производственной деятельности организации, управления техническими процессами при транспортировке пассажиров и грузов. Эффективность и безопасность перевозочного процесса напрямую зависит от функционирования ТСС, которая является одним из важнейших элементов ее инфраструктуры.

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

В силу указанной особенности важную роль приобретает оценка качества функционирования ТСС ОАО «РЖД». На данный момент оценку состояния структурных элементов сети связи производит единая система мониторинга и администрирования (ЕСМА). Однако в течении длительного времени существенно возрастают потребности в увеличении объемов передаваемой информации за счет роста объектов инфраструктуры ОАО «РЖД», оказывающих влияние на перевозочный процесс. В связи с этим регулярно ОАО «РЖД» проводит постоянную модернизацию сетевого оборудования. Например, анализ руководящих технических документов с 2000 по 2015 г, приведенный в таблице 1.1, показал, что технологическая связь ОАО «РЖД» каждые 5 лет требует замены

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

Таблица 1.1 - Анализ руководящих технических документов по проектированию и

внедрению систем связи ОАО «РЖД»

Название документа Создан, утвержден Место, год Основные предложения

Руководящий технический материал по проектированию цифровых и цифро-аналоговых сетей оперативно-технологической связи РТМ-1 ОТС-Ц-2000 Министерство путей сообщения России (ВНИИАС МПС России) Утвержден Заместитель министра путей сообщения России А.С. Мишарин Согласован В.С. Воронин, С.Г. Караткевич, К.Г. Шаповаленко, П.А. Козлов, В.Б. Мехов Москва 2000 Предложено использовать на уровне транспорта сети STM-4(16)

Руководящий технический материал по построению первичной сети технологического сегмента ртм 32 цис 10.12-2002 Министерство путей сообщения Российской Федерации Утвержден Рук. Департамента информатизации и связи МПС России В.С. Воронин Разработал ВНИИУП МПС России Е.Н. Розенберг Москва 2002 Предложено использовать на уровне транспорта сети STM-4(16)

Концепция технического и организационного развития телекоммуникаций ОАО «РЖД» ЦСВТ (Маневич П.Ю., Слюняев А.Н.) МАС (Варакин Л.Е., Меккель А.М.) ВНИИАС (Кнышев И.П., Савенко Л.Я., и др.) Москва 2005 Обоснование перехода на цифровую связь

Предложения по перспективам развития ОАО «Российские железные дороги» на 2008-2010 г.г. и период до 2030 г. ДЕПАРТАМЕНТ СВЯЗИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ Москва 2007 Предложено использовать на уровне транспорта сети STM-16

Протокол заседания секции «Связь» научно-технического совета ОАО «РЖД» ОАО «РЖД» утвержден Вице-президент ОАО «РЖД» А.В. Целько. Председательствовал генеральный директор ЦСС В.Э. Вохмянин 2013г. Загрузка более половины текущего оборудования STM-1(4) от 75 до 100% Предложения использования CWDM и DWDM

Концепция развития первичной сети связи ОАО «РЖД» до 2015 года ЦСС - филиал ОАО «РЖД» Утверждено генеральный директор ЦСС В.Э. Вохмянин Москва 2013 Предложения использования CWDM(4x2,5/10 Гбит/с) и DWDM(16x2,5/40 Гбит/с), на сетевом уровне IP/MPLS-TP

Таким образом, в ходе проектирования и модернизации существующей сети связи ОАО «РЖД» особое внимание заслуживает система поддержки принятия решений (СППР) при проектировании, либо систем автоматизированного проектирования (САПР), в части выделения необходимых пропускных способностей и возможностью обеспечения заданного качества.

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

1.1.2 Анализ первичной потоковой структуры

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

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

1.2 Анализ формирования множества маршрутов при проектировании

технологических сетей связи

1.2.1 Анализ алгоритмов поиска кратчайших маршрутов

При построении ПС, а также при построении таблиц маршрутизации в телекоммуникационном оборудовании связи, необходим алгоритм, позволяющий определить направление перемещения информации от узла источника к узлу назначения. Таким образом, при построении указанного алгоритма решается задача поиска маршрутов для каждого возможного узла назначения. Исходными данными для данного рода задач являются граф телекоммуникационной сети связи. Данный граф включает в себя набор вершин - узлы сети, набор ребер - линии связи между узлами, а также множество возможных корреспондирующих пар - множество устройств, для которых необходимо организовать канал связи. На данный момент указанная задача решается известными алгоритмами поиска кратчайших маршрутов. К наиболее распространенным алгоритмам относятся: алгоритм Дейкстры [1, 2], Белмана-Форда [3, 4, 5] и Флойда - Уоршелла [6]. Рассмотрим наиболее распространенные из них. Кроме представленных алгоритмов поиска кратчайших маршрутов, существуют и другие, однако они являются менее популярными и значительно реже встречаются на практике. Приведем сравнительную таблицу 1.2 характеристик алгоритмов поиска кратчайших маршрутов.

Таблица 1.2 - Сравнение характеристик алгоритмов поиска кратчайших маршрутов

Тап параметра Алгоритм Дейкстры Алгоритм Белмана-Форда Алгоритм Флойда -Уоршелла

Время выполнения 0 (А2 + Е) 0(А X И) в(А3)

Объем выходных данных 0(А) 0 (А2) 0 (А2)

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

рационально использование алгоритма Дейкстры [7]. В случае необходимости построения маршрутов от одного узла до всех остальных (multicast трафик) также используют алгоритм Дейкстры, так как он позволяет найти маршруты от источника до каждого узла сети.

1.2.2 Анализ алгоритмов определения нескольких независимых маршрутов

При построении и эксплуатации современных систем связи одним из важнейших элементов является определение маршрутов прохождения потоков информации между узлами сети. Совокупность всех маршрутов, представленная на физическом графе сети, непосредственно определяет потоковую структуру, которая однозначно определяет физическую возможность реализации потребностей в пропускной способности всех клиентов данной ТСС [8, 9, 10, 11].

С целью обеспечения эффективности распределения ресурсов пропускной способности, либо обеспечения отказоустойчивости телекоммуникационных сетей целесообразно применять метод многопутевой маршрутизации [12, 13]. Для его реализации требуется определить несколько кратчайших маршрутов между рассматриваемыми корреспондирующими парами. Как правило, для получения нескольких маршрутов используют алгоритм Йена, либо его модификации [7, 14], суть которого сводиться к нахождению кратчайших маршрутов любым известным методом [15, 16]. Затем, исключают ребра кратчайшего маршрута из рассматриваемого графа для нахождения следующего маршрута, путем повторного использования алгоритма поиска кратчайшего маршрута на уже модифицированном графе. Данную операцию производят до тех пор, пока не выполнится условие надежности либо эффективности рассматриваемого графа.

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

Рассмотрим модифицированный алгоритм Йена для получения рёберно-независимых маршрутов. В качестве исходных данных задан взвешенный неориентированный граф сети О{Л,Я,С}, где Л {а} - множество вершин графа сети,

I = 1,10, количество узлов в рассматриваемом примере, Я - множество ребер,

значения элементов которого С = > о} - интегральный весовой

коэффициент (метрика) данного ребра. Данный граф изображен на рисунке 1.1 с указанием веса (расстояния между узлами) на ребрах, например, между узлами а1 и а2 существует линия связи с интегральным весовым коэффициентом равным 4. Таким образом основной параметр - метрика ребра сети, определим как интегральный коэффициент - который определяются индивидуально для каждой линии связи ТСС на основе приоритета того или иного параметра (например, длинна линии связи, стоимость аренды канала, физическая среда придачи, время прохождения сигнала по линии связи и пр.), таким образом получим:

= (1.1)

К=1

где е - количество рассматриваемых параметров, а ин - коэффициент приоритета рассматриваемого параметра. Часто на практике, при проектировании сети связи вес ребра определяется одним из указанных выше параметров либо длинной линии, либо считают все весовые коэффициенты как = 1, тогда маршруты будут строиться по количеству ребер, т.е. с наименьшим количеством транзитных узлов сети. Требуется найти к- путей от вершины источника ^ к вершине приемнику - I. Для поиска кратчайших маршрутов будем использовать алгоритм Дейкстры. Тогда модифицированный алгоритм будет выглядеть так:

Шаг 1. Определение кратчайшего маршрута от ^ к ? путем использования алгоритма Дейкстры с модификацией, позволяющей восстановить маршрут = [а5а11,а11а12, ^ где1,у, я, ¿£1 , п, ар- текущее количество

найденных независимых маршрутов;

Шаг 2. Исключить из графа О ребра, найденные на предыдущем шаге;

е

Шаг 3. Определить кратчайший маршрут путем использования алгоритма Дейкстры с модификацией, позволяющей восстановить маршрут М^ = {а3а11, а^а^,..., а^, где Ь,] Е 1, п. Если р=к, то конец, иначе вернуться к шагу 2.

Основную вычислительную сложность алгоритма составляет выполнение поиска кратчайших маршрутов. Так как в модификации алгоритма Йена из графа исключаются все ребра, входящие в маршрут, найденный алгоритмом поиска кратчайшего пути, то сложность модифицированного алгоритма Йена для поиска к реберно-независимых маршрутов, в основе которого используется алгоритм Дейкстры, составит в(к X А2).

Рисунок 1.1 - Исходный граф технологической сети связи

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

Для этого создадим массив расстояний:

\ а1 а2 аз а4 а5 а6 а7 а8 а9 аю

а1 4 6 6

а2 4 5 9

аз 6 5 5 3

а4 5 5 10

а5 9 5 14

аб 6 5 5

а7 3 5 11 11

а8 5 11 8

а9 10 14 11 11 6

аю 11 8 6

Затем, применим алгоритм Дейкстры, начиная с узла а3. Для этого каждой не посещенной вершине присвоим метку, равную с1, ] =124, а начальной

вершине а3 - метку равную 0. После выполнения алгоритма Дейкстры, получим массив меток, соответствующий расстоянию от а3 до каждой вершины.

■р=1

После восстановления первого маршрута, получим вектор М38 = [а3а7, а7а6, а6а8}, при этом стоимость маршрута составит М3=1 = 13

Следующим шагом, исключим из рассматриваемого графа ребра, входящие в

7) = 1

маршрут М38 . На получившемся графе, также выполним алгоритм Дейкстры. После восстановления маршрута получим М38 = {а3а4, а4а9, а9а8} = 26

Результатом выполнения алгоритма Дейкстры будет маршрут Мд8 = [а3а2, а2а5, а5а9, а9а10, а10а8} = 42.

Таким образом, путем использования модифицированного алгоритма Йена, в основе которого лежит алгоритм Дейкстры, для рассматриваемого графа сети получены три рёберно-независимых маршрута между узлами у3 и у8\

М3=1 = {а3а7,а7а6,а6а8} = 13 М3=2 = {а3а4, а4а9, а9а8} = 26 М3=3 = {а3а2, а2а5, а5а9, а9а10, а10а8} = 42

Если произвести суммирование длин всех полученных маршрутов, то получим: М3=1 = 81, коэффициент путей, характеризующий интегральный вес всех маршрутов от ^ к Данный коэффициент позволяет оценить эффективность использования набора из нескольких маршрутов на рассматриваемой сети связи. Однако существуют другие независимые маршруты, суммарным весом меньше, чем маршруты, полученные модифицированным алгоритмом Йена.

Список литературы диссертационного исследования кандидат наук Лукичев Михаил Михайлович, 2021 год

СПИСОК ЛИТЕРАТУРЫ

1. Dijkstra, E. W. A note on two problems in connexion with graphs / E. W. Dijkstra // Numerische Mathematik. - 1959. - Vol. 1, No 1. - P. 269-271.

2. Ананий, В. Алгоритмы: введение в разработку и анализ / В. Ананий. -Москва: Вильямс, 2006. - 548 с. - ISBN 5-8459-0987-2

3. Асанов, М. О. Дискретная математика: графы, матроиды, Алгоритмы / М. О. Асанов, В. А. Баранский, В. В. Расин. - Ижевск : НИЦ «РХД», 2001. - 288 с.

4. Bellman, R. On a Routing Problem / R. Bellman // Quarterly of Applied Mathematics. - 1958. - Vol. 16, No. 1. - P. 87-90.

5. Ford, L. R. Flows in Networks Ford, L. R. Flows in Networks / L. R. Ford, D. R. Fulkerson / Princeton University Press, 1962. - 210 с.

6. Алгоритмы: построение и анализ / Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн. - Москва : Вильямс, 2012. - 1296 с.

7. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. - Москва, 1978. - 432 с.

8. Алиев, Т. И. Моделирование и анализ подуровня агрегирования мультисервисной телекоммуникационной сети / Т. И. Алиев, И. Е. Никульский, В. О. Пяттаев // Техника связи. - 2009. - № 2. - С. 12-18.

9. Математические модели исследования алгоритмов маршрутизации в сетях передачи данных / М. П. Березко, В. М. Вишневский, Е. В. Левнер, Е. В. Федотов. // Информационные процессы. Электронный научный журнал. - 2001. - Том 1, .№2. - С. 103-125.

10. Канаев, А. К. Нейросетевая модель управления трафиком СПД с применением регулятора с предсказанием / А. К. Канаев, М. А. Сахарова // 69-я научно-техническая конференция, посвященная Дню радио. Труды конференции. Санкт-Петербург. - 2014. - С. 203-204.

11. Советов, Б. Я. Построение сетей интегрального обслуживания / Б. Я. Советов, С. А. Яковлев. - [3-е изд.]. - Ленинград : Издательство «Высшая школа», 1990. - 332 с. - ISBN 5-217-00937-3.

12. Вишневский, В .М. Теоретические основы проектирования компьютерных сетей / В. М. Вишневский. - Москва : Техносфера, 2003. - 512 с. - ISBN 5-94836011-3.

13. Канаев, А.К. Моделирование процессов обработки потоков IP-пакетов с различными типами информационных составляющих на основе глубокого анализа трафика / А. К. Канаев, М. А. Сахарова // Бюллетень результатов научных исследований. - 2014. - № 3 (12). - С. 85-93.

14. Соколов, В. М. Результаты сравнения применения исходной и модифицированной методик синтеза структуры транспортной сети телекоммуникационной системы / В. М. Соколов, С. А. Ясинский // Информация и Космос. - 2016. - № 1. - С. 36-41.

15. Афанасьев, А. П. «Равномерные» алгоритмы последовательного заполнения потоковой сети потоками продуктов / А. П. Афанасьев, Я. Р. Гринберг, И. И. Курочкин // Труды ИСА РАН (инситсут). - 2005. - Т. 14 - С. 118-140.

16. Малашенко, Ю. Е. Суперконкурентное распределение потоков в многопродуктовых сетях / Ю. Е. Малашенко, Н. М. Новикова // Дискретный анализ и исследование операций. - 1997. - Т. 2, № 4:2. - С. 34-54.

17. Бертсекас, Д. Сети передачи данных / Д. Бертсекас, Р. Галлагер. - Москва : Мир, 1989. - 544 с. - ISBN 5-03-000639-7.

18. Гетьман, А. И. Анализ сетевого трафика в режиме реального времени: обзор прикладных задач, подходов и решений / А. И. Гетьман, Е. Ф. Евстропов, Ю. В. Маркин // Препринт ИСП РАН (инситсут). - 2015. - С. 1-52.

19. Request for Comments: 1157 A Simple Network Management Protocol (SNMP) / RFC. - RFC, 1990.

20. Михеев, А. В. Исследование методов сбора статистических данных о трафике в IP-сетях передачи данных / А. В. Михеев // 2я Международная конференция студентов, аспирантов и молодых ученых "Информационные технологии, телекоммуникации и системы управления" : сборник докладов. -Екатеринбург : УрФУ (университет). - 2016. - С. 121-130.

21. Маркин, Ю. В. Обзор современных инструментов анализа сетевого трафика / Ю. В. Маркин, А. С. Санаров // Препринты ИСП РАН (инситсут). - 2014.

- №27. - С. 1-24.

22. Гребешков, А. Ю. Стандарты и технологии управления сетями связи / А. Ю. Гребешков. - Москва : Эко-Трендз, 2003. - 287 с. - ISBN 978-5-88405-047-1.

23. Никульский, И. Е. Оценка характеристик качества обслуживания IP-трафика в кольцевой оптической сети доступа / И. Е. Никульский, А. И. Осадчий // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика, телекоммуникации и управление.

- 2011. - № 2(120). - С. 126-133.

24. Михайлов, С. К. Расчет вариации задержки (IPDV) для телефонного соединения / С. К. Михайлов, Т. П. Сергеева // T-Comm : Телекоммуникации и транспорт. - 2013. - № 7. - С. 87-89.

25. Recommendation ITU-T Y.1541 Network performance objectives for IP-based services / ITU-T. - ITU-T, 2011.

26. Рекомендация МСЭ-Т Т.38 Процедуры факсимильной связи Группы 3 / МСЭ-Т. - МСЭ-Т, 2004.

27. Request for Comments: 6405. Voice over IP (VoIP) SIP Peering Use Cases. / RFC. - RFC, 2003.

28. Request for Comments: 3550 RTP A Transport Protocol for Real-Time Applications / RFC. - RFC, 2011.

29. Канаев, А.К. Формирование имитационной модели эквивалентного генератора речевого трафика, используемого в пакетно-ориентированных транспортных сетях связи / А. К. Канаев, М. М. Лукичев, А. А. Привалов // T-Comm : Телекоммуникации и транспорт. - 2019. - Т. 13., № 10. - С. 4-13.

30. Recommendation ITU-T G.711 Pulse code modulation (PCM) of voice frequencies / ITU-T. - ITU-T, 1989.

31. Recommendation ITU-T H.264. Advanced video coding for generic audiovisual services / ITU-T. - ITU-T, 2019.

32. Request for Comments: 3984 RTP Payload Format for H.264 Video / RFC. -RFC, 2005.

33. Request for Comments: 2435. RTP Payload Format for JPEG-compressed Video / RFC. - RFC, 1998.

34. Боев, В. Д. Моделирование систем. Инструментальные средства GPSS World: учебное пособие / В. Д. Боев. - Санкт-Петербург : БХВ-Петербург, 2004. -368 с. - ISBN 5-94157-515-7.

35. Боев, В. Д. Иследование адекватности GPSS World и AnyLogic при моделировании дискретно-событийных процессов / В. Д. Боев. - Санкт-Петербург : ВАС, 2011. - 404 с.

36. Вадзинский, Р. Н. Справочник по вероятностным распределениям / Р. Н. Вадзинский. - Санкт-Петербург : Наука, 2001. - 295 с. - ISBN 5-02-024919-Х.

37. Венцель, Е. С. Теория вероятностей / Е. С. Венцель. - [4-е изд.]. - Москва : Издательство "Наука", 1969. - 576 с.

38. Карпов, Ю. Г. Имитационное моделирование систем. Введение в моделирование с AnyLogic 5 / Ю. Г. Карпов. - Санкт-Петербург : БХВ-Петербург, 2005. - 400 с. - ISBN 5-94157-148-8.

39. Кацман, Ю. Я. Моделирование: Учебное пособие / Ю. Я. Кацман. - Томск: Томский политехнический университет (ТПУ), Институт дистанционного образования (ИДО), 2003. - 91 с.

40. Шеннон, Р. Имитационное моделирование систем - искусство и наука / Р. Шеннон. - Москва : Мир, 1978. - 418 с.

41. Lukichev, M. M. Formation of an equivalent simulation model of a real-time video stream generator used in packet-oriented communication networks, taking into account the structure of the H.264 compression algorithm / M. M. Lukichev // T-Comm: Telecommunications and transport. - 2019. - Vol. 13, No. 11. - P. 43-52.

42. Клейнрок, Л. Коммуникационные сети (стохастические потоки и задержки сообщений) / Л. Клейнрок. - Москва : Наука, 1970. - 256 с.

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

сетей связи следующего поколения / А. Н. Назаров, К. И. Сычев. - Красноярск : ООО «Поликом», 2011. - 491 с. - ISBN 978-5-94876-093-3.

44. Алгазинов, Э. К. Анализ и компьютерное моделирование информационных процессов и систем / Э. К. Алгазинов, А. А. Сирота. - Москва : Диалог-МИФИ, 2009. - 416 с. - ISBN 978-5-86404-233-5.

45. Алиев, Т. И. Основы моделирования дискретных систем / Т. И. Алиев. -Санкт-Петербург : СПбГУ ИТМО, 2009. - 363 с. - ISBN 978-5-7577-0336-7.

46. Сирота, А. А. Компьютерное моделирование и оценка эффективности сложных систем / А. А. Сирота. - Москва : Техносфера, 2006. - 280 с. - ISBN 594836-080-6.

47. Олифер, В. Г. Компьютерные сети. Принципы, технологии, протоколы / В. Г. Олифер, Н. А. Олифер. - [4-е изд.]. - Санкт-Петербург : Питер, 2011. - 917 с.

- ISBN 978-5-496-00004-8.

48. Платунова, С. М. Методы проектирования фрагментов компьютерной сети / С. М. Платунова. - Санкт-Петербург : НИУ ИТМО (университет), 2012. - 51 с.

49. Канаев, А. К. Синтез потоковой структуры транспортной сети связи с использованием имитационного моделирования / А. К. Канаев, М. М. Лукичев, А. А. Муравцов // Известия петербургского университета путей сообщения. - 2015.

- № 2 (43). - С. 105-111.

50. Салифов, И. И. Расчет и сравнение сред передачи современных магистральных сетей связи по критерию латентности (задержки) / И. И. Салифов // T-Comm : Телекоммуникации и транспорт. - 2009. -№ 4. - С. 42-45.

51. Рекомендация МСЭ-Т G.652 Характеристики среды передачи и оптических систем - Волоконно-оптические кабели / МСЭ-Т. - МСЭ-Т, 2016.

52. ГОСТ 11326.0-78 Кабели радиочастотные. Общие технические условия. -Москва : ИПК Издательство стандартов, 2003.

53. ГОСТ Р 54429-2011 Кабели связи симметричные для цифровых систем передачи. - Москва : Стандартинформ, 2012.

54. Канаев, А. К. Методика расчета потоковой структуры сети передач и управляющей информации в системе управления сетью тактовой сетевой

синхронизации / А. К. Канаев, Е. В. Опарин, М. А. Камынина // Бюллетень результатов научных исследований. - 2012. - №4 (3). - С. 149-159.

55. Лемешко, А. В. Разработка и исследование потоковой модели адаптивной маршрутизации в программно-конфигурируемых сетях с балансировкой нагрузки / А. В. Лемешко, Т. В. Вавенко // Доклад ТУСУРа (университет). - 2013. - №2. 3 (29). - С. 100-108.

56. Михайлов, С. К. Моделирование времени задержки обслуживания междугородного телефонного трафика в маршрутизаторах пакетных сетей / С. К. Михайлов, Т. П. Сергеева // T-Comm : Телекоммуникации и транспорт. - 2019. -№ 3. - С. 154-156.

57. Томашевский, В. Имитационное моделирование в среде GPSS / В. Томашевский, Е. Жданова. - Москва : Бестселлер, 2003. - 416 с. - ISBN 5-98158004-6

58. Шелухин, О. И. Фрактальные процессы в телекоммуникациях / О. И. Шелухин. - Москва : Радиотехника, 2003. - 480 с. - ISBN 5-93108-030-9.

59. Velasquez, K. Benchmarking Methodology for Network Interconnect Devices / K. Velasquez, E. Gamess // - RFC 2544. - Journal of Computer Sciences and Applications. - 2014. - Vol. 2, No. 2. - P. 14-22.

60. Вентцель, Е. С. Теория вероятностей: учебник для вузов / Вентцель Е.С. -[11-е изд.]. - Москва : КноРус, - 2010. - 664 с. - ISBN 978-5-406-00476-0.

61. Канаев, А. К. Методика формирования эквивалентного мульти сервисного узла технологической сети связи в среде имитационного моделирования, учитывающая параметры качества ее функционирования в установившемся режиме / А. К. Канаев, М. М. Лукичев, В. Л. Лукичева // T-Comm: Телекоммуникации и транспорт. - 2019. - Т. 13, № 12. - C. 13-24.

62. Соколов, В. М. Методика синтеза структуры транспортной сети телекоммуникационной системы / В. М. Соколов, С. А. Ясинский // Бюллетень результатов научных исследований. - 2012. - №. 3 (2). - С. 114-120.

63. Базовые положения методики формирования (построения) рационального варианта автоматической полевой сети связи общего пользования специального

назначения / С. Ф. Лебедев, Г. В. Сызранцев, В. С. Добровольский, К. И. Лукин // Вопросы оборонной техники. - 2012. - № 1 -2, - С. 79-84.

64. Буслаев, А. П. Моделирование потоков на графах. Теоретические и вычислительные аспекты : Учебное пособие / А. П. Буслаев, А. А. Лебедев, М. В. Яшина. - Москва: МАДИ (университет), 2011. - 105 с.

65. Окулов, С. М. Программирование в алгоритмах / С. М. Окулов. - Москва : БИНОМ. Лаборатория знаний, 2002. - 341 с. - ISBN 5-94774-010-9

66. Чуйко, Ю. В. Задача маршрутизации с разделяемым трафиком и неполной информацией / Ю. В. Чуйко // Управление большими системами. - 2009. - № 26.1.

- С. 164-176.

67. Скиена, С. Алгоритмы. Руководство по разработке / С. Скиена. - [2-е изд.].

- Санкт-Петербург : БХВ-Петербург, 2011. -720 с. - ISBN 978-5-9775-0560-4.

68. ГОСТ Р 53111-2008. Устойчивость функционирования сети связи общего пользования. Требования и методы проверки. - Москва : Стандартинформ, 2012.

69. Замятина, О. М. Моделирование сетей: учебное пособие / О. М. Замятина.

- Томск: Издательство Томского политехнического университета, 2011. - 168 с. -ISBN 978-5-534-00335-2.

70. Морозов, В. К. Основы теории информационных сетей / В. К. Морозов, А. В. Долганов. - Москва: Высшая школа, 1987. - 271 с.

71. Бусленко, Н. П. Моделирование сложных систем / Н. П. Бусленко. - [2-е изд.]. - Москва : Наука, 1978. - 399 с.

72. Кулешов, И. А. Анализ методов моделирования сетей связи / И. А. Кулешов, М. А. Дуплинский, Ю. А. Малахов // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика, телекоммуникации и управление. - 2010. - № 2(97). - С. 148-152.

73. Советов, Б. Я. Имитационное моделирование систем / Б. Я. Советов, С. А. Яковлев. - [7-е изд.]. - Москва : Юрайт, 2019. - 343 с. - ISBN 978-5-9916-3916-3.

74. Девятков, В. В. Методология и технология имитационных исследований сложных систем: современное состояние и перспективы развития / В. В. Девятков.

- Москва : ИНФРА-М, 2014. - 448 с. - ISBN 978-5-9558-0338-8.

75. Плотников, А. М. Современное состояние и тенденции развития имитационного моделирования в Российской Федерации / А. М. Плотников, Ю. И. Рыжиков, Б. В. Соколов // Санкт-Петербург : Труды СПИИРАН (университет), 2013. - № 2(25). - С. 42-112.

76. Рыжиков, Ю. И. Имитационное моделирование. Теория и технологии / Ю. И. Рыжиков. - Санкт-Петербург : Корона, 2004. - 380 с.

77. Рыжиков, Ю. И. Оценка системы моделирования GPSS WORLD / Ю. И. Рыжиков // Информационно-управляющие системы. - 2003. - № 2-3. - С. 30-38.

78. Габалин, А. В. Вопросы выбора системы имитационного моделирования при исследовании сложных систем / А. В. Габалин // Труды 17-й Международной конференции «Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта» (CAD/CAM/PDM-2017) Москва : ИПУ РАН (институт). - 2017. - Т. 1. - С. 107-109.

79. Шелухин, О. И. Моделирование информационных систем : учебное пособие / О. И. Шелухин. - [2-е изд.]. - Москва : Радиотехника, 2012. - 516 с. -ISBN 978-5-9912-0193-3.

80. Даденков, С. А. Выбор среды имитационного моделирования информационно-управляющих сетей / С. А. Даденков, Е. Л. Кон. // Вестник Пермского университета. - 2019. - № 1(44). - С. 58-69

81. Максимей, И. В. Имитационное моделирование на ЭВМ. / Максимей И.В. - Москва : Радио и связь, 1988. - 232 с.

82. Кельтон, В. Имитационное моделирование. Классика CS / В. Кельтон, А. Лоу. - Санкт-Петербург : Питер, 2004 - 847 с. - ISBN 5-94723-981-7.

83. Клейнен, Д. Статистические методы в имитационном моделировании / Д. Клейнен. - Москва : Статистика, 1978. - 222 с.

84. Калан, Р. Основные концепции нейронных сетей / Р. Калан. - Москва : Издательский дом «Вильямс», 2001. - 288 с. - ISBN 5-8459-0210-Х.

85. Попков, Г. В. Математические основы моделирования сетей связи. Учебное пособие для вузов / Г. В. Попков, В. К. Попков, В. В. Величко. - Москва : Горячая линия-Телеком, 2012. 183 с. - ISBN 978-5-9912-0266-7.

86. Васильев, К. К. Математическое моделирование систем связи : учебное пособие / К. К. Васильев, М. Н. Служивый. - [2-е изд.]. - Ульяновск: УлГТУ (университет), 2010. - 170 с. - ISBN 978-5-9795-0650-0.

87. Проектирование и моделирование сетей связи. Лабораторный практикум / В. Н. Тарасов, Н. Ф. Бахарева, С. В. Малахов, Ю. А. Ушаков. - Санкт-Петербург : Лань, 2019. - 240 с. - ISBN 987-5-904029-58-6.

88. Гилязов, Р. Л. Математическое моделирование и многокритериальная оптимизация мультисервисных сетей связи с учетом нечетких предпочтений пользователей / Гилязов Руслан Леонидович. - Москва, 2009. - 19 с.

89. Хаустович, А. В. Методология автоматизированного проектирования информационно-телекоммуникационных систем: На основе моделирования и оптимизации сетей передачи данных / Хаустович Александр Владимирович. -Воронеж, 2002. - 16 с.

90. Пяттаев, В. О. Разработка моделей и исследование иерархических подуровней городских мультисервисных сетей / Пяттаев Владислав Олегович. -Санкт-Петербург : СПбГУТ им. проф. М.А. Бонч-Бруевича (университет), 2007. - 155 с.

91. Recommendation ITU-T Q.3900. Methods of testing and model network architecture for NGN technical means testing as applied to public telecommunication networks / ITU-T. - ITU-T, 2006. - 30 с.

92. Захаров, Г. П. Методы исследования сетей передачи данных / Г. П. Захаров. - Москва : Радио и связь, 1982. - 208 с.

93. Лохмотко, В. В. Анализ и оптимизация цифровых сетей для интегрального обслуживания / В. В. Лохмотко, К. И. Пирогов. - Минск: Наука и техника, 1991. -192 с.

ПРИЛОЖЕНИЕ А. РАСЧЕТ ППС ПУТЕВЫМ АЛГОРИТМОМ

Исходный граф телекоммуникационной сети представлен на рисунке А. 1. Данный граф включает в себя 10 узлов, между которыми необходимо организовать передачу информации. Матрица расстояний приведённой ТСС примет вид таблицы А.1.

Рисунок А. 1 - Исходный граф О телекоммуникационной сети Таблица А.1 - Матрица расстояний ТСС

\ а1 а2 аз а4 а5 а6 а7 а8 а9 аю

а1 4 6 6

а2 4 5 9

аз 6 5 5 3

а4 5 5 10

а5 9 5 14

аб 6 5 5

а7 3 5 11 11

а8 5 11 8

а9 10 14 11 11 9

аю 11 8 9

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

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

2 =

«1 «4 а1а5 а1а6 а1а7 «1 «8 Яд «1 «10^

«2«3 &2«4 «2 «5 «2 «6 а2а7 «2 «8 Я 2 «2 «10

«3«5 аз«б а3а7 «3 «8 ^3 Яд «3 «10

«4 «10

а5а7 «5 «8 ^5 Яд «5 «10

а6а7 «6 «8 «6 «10

Я 7 0-8 «7 «10

«8 «10

«д«10}

Заданные направления связи и объём передаваемой информации по каждому из них сведём в соответствующую таблицу А.2. _Таблица А.2 - Заданные направления связи, Мбит/с

\ а1 а2 аз а4 а5 аб а7 а8 а9 аю

а1 10 10 10 10 10 10 10 10 10

а2 10 10 10 10 10 10 10 10

аз 10 10 10 10 10 10 10

а4 10 10 10 10 10 10

а5 10 10 10 10 10

аб 10 10 10 10

а7 10 10 10

а8 10 10

а9 10

аю

Определим потоковую структуру, для заданного примера.

1. Определение первого кратчайшего пути для КП а1а2.

Используя алгоритм Дейкстры, определим кратчайший путь для КП а1а2. Для этого введем метки для всех вершин. Метка самой вершины аг полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от аг до других вершин пока неизвестны рисунок А.2. Все вершины графа помечаются как «не посещённые». Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина и, имеющая минимальную метку. Вершины, в которые ведут рёбра из и, назовем соседями этой вершины. Для каждого соседа вершины и, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки и и длины ребра, соединяющего и с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину и как посещенную и повторим шаг алгоритма.

00

00

Рисунок А.2 - Первый этап алгоритма Дейкстры Таким образом, можно отобразить результат на рисунке А.3.

Рисунок А.3 - Итог формирования 1ого кратчайшего маршрута по алгоритму Дейкстры

Таким образом, первый кратчайший путь для КП ага2 составит 4 и будет проходить по ребру Ь1,2: М"1Й2 = {Ь 1,2} = 4

2. Исключение ребра Ь 1,2 из графа О и нахождение второго кратчайшего пути. Графическое решение алгоритма Дейкстры, после исключения ребра Ь1,2 из графа О, можно представить на рисунке А.4.

Рисунок А.4 - Итог формирования 2ого кратчайшего маршрута по алгоритму Дейкстры

Таким образом, второй кратчайший путь для КП ага2 составит 11 и будет проходить по рёбрам Ь1,3 и Ь2,3: М"1Й2 = {Ь1,3; Ь2,3} = 11

3. Исключение ребер Ь1,2; Ь1,3; Ь2,3 из графа О и нахождение третьего кратчайшего пути.

Расчет произведем аналогично, результат представим на рисунке А.5.

Рисунок А.5 - Итог формирования 3ого кратчайшего маршрута по алгоритму Дейкстры

Таким образом, третий кратчайший путь для КП %а2 составит 33 и будет проходить по рёбрам Ь1,6; Ь6,7; Ь7,3; Ь3,4; Ь4,5; Ь5,2:

Мз"1"2 = (61,6; Ь6,7; Ь3,7; Ь3,4; Ь4,5; Ь2,5} = 33

4. Распределение потока от КП %а2 между 3 путями пропорционально длине маршрута.

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

Ц^а; = ___ ; ^у} = ^а, # ^

Заметим, что в сумме соответствующие коэффициенты умножения должны давать единицу:

^г(ст) Г=1

В результате последующего расчета получаем:

У1а±а2 = {61,2} = Уа1а2 * ^=6,735 Мбит/с;

У2ага2 = {Ь1,3. ¿2,3} = Уа1а2 * к2=2,449 Мбит/с;

К/1"2 = {Ь1,6; Ь6,7; Ь3,7; Ь3,4; Ь4,5; Ь2,5} = * £3=0,816 Мбит/с.

5. Результат расчета нагрузки на ТКС от остальных КП. Результат вычислений удобно свести в матрицу ЬТКС представленную в виде таблицы А.3, а также добавить столбцы М^1^ и п - количество промежуточных узлов (кроме КП), через которые проходит данный маршрут.

Таблица А.3 - Матрица распределений потоков ¿ТКС

<4 ,3 ,6 ,3 ,5 ,4 ,7 ,5 ,9 ,9 5, ,7 ,8 ,9 0 ,9 оо" 0 0 оС

У1(а1,а2) 6,7

У2(а1,а2) 2,4 2,4

У3(а1,а2) 0,8 0,8 0,8 0,8 0,8 0,8

У1(а1,а3) 4,8

У2(а1,а3) 3,2 3,2

У3(а1,а3) 2,0 2,0 2,0

У1(а2,а3) 5,7

У2(а2,а3) 2,8 2,8

У3(а2,а3) 1,5 1,5 1,5

У1(а1,а4) 5,1 5,1

У2(а1,а4) 3,1 3,1 3,1

У3(а1,а4) 1,8 1,8 1,8 1,8

У1(а2,а4) 5,0 5,0

У2(а2,а4) 3,6 3,6

У3(а2,а4) 1,5 1,5 1,5 1,5 1,5

У1(а3,а4) 6,8

У2(а3,а4) 1,8 1,8 1,8

У3(а3,а4) 1,4 1,4 1,4

У1(а1,а5) 4,6 4,6

У2(а1,а5) 3,7 3,7 3,7

У3(а1,а5) 1,7 1,7 1,7 1,7

У1(а2,а5) 5,4

У2(а2,а5) 3,3 3,3 3,3

У3(а2,а5) 1,3 1,3 1,3 1,3 1,3

У1(а3,а5) 4,8 4,8

У2(а3,а5) 3,4 3,4

< ^рэ4 jo рэ 00 < UJ рэ 00 < ю ^рэ4 рз 00 < P2 00 < LtJ ^ On P2 < to "рэ4 On P2 < On P2 < LtJ P2 < to ^ P2 < P2 < LtJ P2 < to "рэ4 P2 < P2 < LtJ ^ LtJ P2 < to LtJ P2 < LtJ P2 < LtJ JO P2 < to "рэ4 JO P2 < JO P2 < LtJ ^ P2 < Is) ^ P2 < рэ < LtJ ^рэ4 P2 On < Is) "рэ4 P2 On < P2 On < LtJ ^ P2 On < Is) ^ P2 On < "рэ4 P2 On < OJ ^ OJ P2 On < Is) ^ OJ P2 On < OJ P2 On < LtJ JO P2 On < Is) JO P2 On < JO P2 On < LtJ ^ P2 On < Is) рз On < рз On < OJ "рэ4 P2 < Is) рэ < рз < OJ LtJ рз

о Ъо JO On LtJ о Is) JO "vo О Ь1,2

JO to Is) V "vo LtJ "ui JO Ь1,3

о "vo to Is) JO On V LtJ о 4^ О LtJ JO OJ "UI "vo On "UJ Ь1,6

Ъо LtJ Ъо О Ъо Ь2,3

JO On "UJ Is) LtJ JO "UJ Ъо Ь2,5

Ъо "vo On О О "vo "vo "vo "UJ О Ъо Ь3,4

JO to Is) "vo On О "vo LtJ "vo "vo Is) OJ Ъо JO Ь3,7

"vo LtJ "vo JO On Ъо Ь4,5

Ъо JO "uj о "vo JO V о Ь4,9

JO "UI "UJ Is) Is) V "UJ Ь5,9

On 1л JO On LtJ о 4^ О LtJ "vo "vo Is) OJ Ъо JO Ь6,7

о "vo V Is) V Is) V "UJ "UJ о Ь6,8

JO 1л JO "uj о "vo "uj Is) Ь7,9

JO V Ь7,10

Ъо JO JO о Ь8,9

JO "UJ Ь8,10

Ь9,10

-J

о

V3(a8,a9) < IS) ^ oo "fa VO < J30 "fa VO < LtJ -J "fa VO < IS) -J "fa VO < -J "fa VO < LtJ "fa VO < IS) "fa VO < "fa VO < LtJ "fa VO < IS) "fa VO < "fa VO < LtJ "fa VO < IS) "fa VO < "fa VO < LtJ ^ LtJ "fa VO < IS) ^ LtJ "fa VO < LtJ "fa VO < LtJ JO "fa VO < IS) JO "fa VO < JO "fa VO < LtJ "fa VO < IS) "fa VO < "fa VO < LtJ -J "fa 00 < IS) -J "fa 00 < -J "fa 00 < LtJ ^ ON "fa 00 < IS) ^ ON "fa 00 < On "fa 00 < LtJ "fa 00 < IS) "fa 00 < "fa 00 < LtJ ^ "fa 00 < IS) ^ "fa 00 < "fa 00 < OJ LtJ "fa 00 < IS) ^ OJ "fa 00 < OJ "fa 00 < OJ JO "fa 00 < IS) JO "fa 00

JO "vo LtJ О LtJ "-J bl,2

JO "UJ JO JO "vo LtJ On "o bl,3

JO "UJ JO "OJ "o OJ "-J bl,6

JO "vo LtJ "o On JO "oo b2,3

JO LtJ "to LtJ "-J On IS) "to b2,5

JO "vo JO "UJ JO On "oo JO "vo LtJ "o "vo "o JO "oo "to JO "oo b3,4

JO "vo JO JO On LtJ "vo LtJ On "vo JO "oo "to On JO "oo b3,7

LtJ "oo JO On JO "oo JO b4,5

JO "vo JO "uj LtJ "oo "vo LtJ "oo JO "vo LtJ "o "vo "o LtJ On JO "oo b4,9

4^ JO On LtJ "to LtJ JO On IS) "to b5,9

jo "UJ JO 1л LtJ "vo "OJ On "to On b6,7

jo "UJ JO "UI LtJ "vo JO LtJ "OJ "OJ -J OJ "-J "to On b6,8

Js) "uj "-J LtJ "vo JO JO On 4^ LtJ "vo LtJ On b7,9

JO "oo On JO "oo JO "oo b7,10

"uj JO 1л LtJ "vo JO LtJ "OJ "vo "o LtJ OJ On JO "oo JO "to b8,9

LtJ V JO "oo On JO "oo JO On JO "oo b8,10

LtJ JO On b9,10

b1,2 CO b1 b1,6 ,3 csf b ,5 b ,4 fT b ,7 b ,5 b ,9 b ,9 b ,7 vcT b ,8 VCT b ,9 b 0 b ,9 oo" b 0 ОО* b 0 o9 b

V1(a1,a10) 4,0 4,0 4,0

V2(a1,a10) 3,8 3,8 3,8

V3(a1,a10) 2,1 2,1 2,1 2,1 2,1

V1(a2,a10) 4,1 4,1 4,1

V2(a2,a10) 3,4 3,4 3,4 3,4

V3(a2,a10) 2,5 2,5 2,5

V1(a3,a10) 4,7 4,7

V2(a3,a10) 2,7 2,7 2,7

V3(a3,a10) 2,6 2,6 2,6 2,6

V1(a4,a10) 4,0 4,0 4,0

V2(a4,a10) 4,0 4,0

V3(a4,a10) 2,0 2,0 2,0 2,0 2,0 2,0

V1(a5,a10) 3,7 3,7

V2(a5,a10) 3,6 3,6 3,6 3,6

V3(a5,a10) 2,7 2,7 2,7 2,7 2,7

V1(a6,a10) 4,6 4,6

V2(a6,a10) 3,7 3,7

V3(a6,a10) 1,7 1,7 1,7 1,7 1,7

V1(a7,a10) 4,6

V2(a7,a10) 2,8 2,8 2,8

V3(a7,a10) 2,5 2,5

V1(a8,a10) 5,6

V2(a8,a10) 2,2 2,2

V3(a8,a10) 2,1 2,1 2,1

V1(a9,a10) 5,3

V2(a9,a10) 2,5 2,5

V3(a9,a10) 2,2 2,2

Итог: 70,7 58,6 81,9 58,4 60,4 100,2 121,2 59,4 57,6 40,3 76,5 88,6 47,6 46,4 49,5 51,0 34,0

Таким образом, проведя суммирование по столбцам матрицы £ТКС, получаем потоковую структуру для исходного графа G. Однако, на практике удобнее использовать потоки кратные технологии передачи (SDH - 2.048 Мбит/с, Ethernet - 1 Мбит/с ...), предположим, что в вышеуказанной сети используется технология Ethernet, тогда, потребуется округлить все значения потоков (Vraiaj) от каждой КП,

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

В итоге получим результат, приведенный в таблице А.3, который можно указать на графе О, Рисунок А. 6.

Таблица А.4 - Итоговые значения загрузки ветвей, Мбит/с

<4 го с<Г счГ С1Г Г7 Г5 Г9 Г9 »/-Т Г7 Г8 Г9 0 Г9 0 0 о9

Итог: 71 59 84 65 60 101 123 61 56 37 80 88 47 47 48 54 34

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

незначительно (не более 1 %).

Рисунок А.6 - Первичная потоковая структура ТСС.

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

ПРИЛОЖЕНИЕ Б. РАСЧЕТ ППС МЕТОДОМ СЕЧЕНИЙ

Исходный граф телекоммуникационной сети представлен на рисунке Б.1. Данный граф включает в себя 10 узлов, между которыми необходимо организовать передачу информации. Матрица расстояний ь = приведённой

телекоммуникационной сети будет иметь следующий приведенный в таблице Б.1.

Рисунок Б.1 - Исходный граф G телекоммуникационной сети

Таблица Б.1 - Матрица расстояний телекоммуникационной сети

Для формирования ППС необходимо предварительно построить минимальное остовное дерево исходного графа Оттоа, минимальное остовное дерево. Оттос1 строится одним из указанных выше алгоритмов, в результате чего минимальное остовное дерево ОттОС1 исходного графа примет вид, указанный на рисунке Б.2.

Рисунок Б.2 - Минимальное остовное дерево исходного графа Отша

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

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

О1О3 0-1О4 а1а5 а1а6 а1а7 0.-10.8 о.—09 О— а10>

а2а3 О2О4 0-2^-5 0-2^-6 а2а7 а2 а8 0-2 О9 а2 а10

О3О4 а3а5 а3а6 а3а7 0-3 а8 0.3 О9 03 а—о

О4О5 О4О7 О4О9 О4О10

а5а6 а5а7 а5а8 О5 0.9 а5а10

а6а7 а6а8 0.6&9 а6а10

О7 0.70.9 а7а10

О8О9 а8 а10

< О9О10}

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

Заданные направления связи и объём передаваемой информации по каждому из них сведём в соответствующую таблицу Б.2. Отметим, что в данной таблице узел, находящийся в строке, соответствует узлу, из которого передаётся информация управления, а узел, соответствующий столбцу, является узлом, принимающим информацию управления.

Таблица Б.2 - Заданные направления связи

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

Для построения ПС необходимо иметь минимальное остовное дерево ОттОа, примем, что минимальное остовное дерево ОттОС1 состоит из N узлов, тогда оно будет содержать N-1 ветвей.

Ниже представлены рассчитанные пропускные способности рёбер графа с учётом заданного критерия структурной надёжности.

(

№ п/п Расчет, Мбит/с Итог, Мбит/с

1 ■О(1,2;1,3;1,4;1,5;1,6;1,7;1,8;1,9;1,10) =38 571 38,571

2 Ы6 В(1,2;1,3;1,4;1,5;1,6;1,7;1,8;1,9;1,10) =25 714

3 п13 В(1,2;1,3;1,4;1,5;1,6;1,7;1,8;1,9;1,10) =25 714 25,714

4 В11,3;1,4;1,5;1,6;1,7;1,8;1,9;1,10;2,3;2,4;2,5;2,6;2,7;2,8;2,9;2,10) =60

5 д25 _гп В(1,3;1,4;1,5;1,6;1,7;1,8;1,9;1,10;2,3;2,4;2,5;2,6;2,7;2,8;2,9;2,10) 50

6 д23 _гп В(1,3;1,4;1,5;1,6;1,7;1,8;1,9;1,10;2,3;2,4;2,5;2,6;2,7;2,8;2,9;2,10) 50 50

7 о 34 В(1, 4;2,4;3,4;4,6;4,7;4,8;4,9;4,10;1,5;2,5;3,5;5,6;5,7;5, 8;5,9;5,10) =77 83 8 77,838

8 1,49 В(1,4;2,4;3,4;4,6;4,7;4,8;4,9;4,10;1,5;2,5;3,5;5,6;5,7;5,8;5,9;5,10) =38 919

9 1,25 В(1,4;2,4;3,4;4,6;4,7;4,8;4,9;4,10;1,5;2,5;3,5;5,6;5,7;5,8;5,9;5,10) =43 243 110,048

10 В(1,5;2,5;3,5;4,5;5,6;5,7;5,8;5,9;5,10) = 16,805

11 В45 =47 054 В(1,5;2,5;3,5;4,5;5,6;5,7;5,8;5,9;5,10) 4/ ,054 47,054

12 В(1,5;2,5;3,5;4,5;5,6;5,7;5,8;5,9;5,10) =26,141 26,141

13 В16 =69 444 В(1,6;2,6;3,6;4,6;5,6;1,7;2,7;3,7;4,7;5,7;1,8;2,8;3,8;4,8;5,8;1,9;2,9;3,9;4,9;5,9;1,10;2,10;3,10;4,10;5,10) 69,444 240,872

14 В(1,6;2,6;3,6;4,6;5,6;1,7;2,7;3,7;4,7;5,7;1,8;2,8;3,8;4,8;5,8;1,9;2,9;3,9;4,9;5,9;1,10;2,10;3,10;4,10;5,10) =41,667

15 В(1,6;2,6;3,6;4,6;5,6;1,7;2,7;3,7;4,7;5,7;1,8;2,8;3,8;4,8;5,8;1,9;2,9;3,9;4,9;5,9;1,10;2,10;3,10;4,10;5,10) = 138,889 138,889

16 В11,6;2,6;3,6;4,6;5,6;6,7;1,8;2,8;3,8;4,8;5,8;7,8;1,9;2,9;3,9;4,9;5,9;7,9;1,10;2,10;3,10;4,10;5,10;7,10) = 85,714

17 В49 =51 429 230,053

18 п67 _1 осп В(1,6;2,6;3,6;4,6;5,6;6,7;1,8;2,8;3,8;4,8;5,8;7,8;1,9;2,9;3,9;4,9;5,9;7,9;1,10;2,10;3,10;4,10;5,10;7,10) 102,8 57 102,857

19 Д68 _1 г\п ЛЛГ) В(1,8;2,8;3,8;4,8;5,8;6,8;7,8;1,9;2,9;3,9;4,9;5,9;6,9;7,9;1,10;2,10;3,10;4,10;5,10;6,10;7,10) 10 7 ,442 107,442

20 Д49 _со пг\ 1 В(1,8;2,8;3,8;4,8;5,8;6,8;7,8;1,9;2,9;3,9;4,9;5,9;6,9;7,9;1,10;2,10;3,10;4,10;5,10;6,10;7,10) 53,721

21 1,710 —ЛЯ ЯЧ7 В(1,8;2,8;3,8;4,8;5,8;6,8;7,8;1,9;2,9;3,9;4,9;5,9;6,9;7,9;1,10;2,10;3,10;4,10;5,10;6,10;7,10) 48,837 70,223

22 В49 =44 317 В(1, 9;2, 9;3, 9;4, 9;5, 9;6, 9;7, 9;8, 9;1, 10;2, 10;3, 10;4, 10;5,10;6, 10;7,10;8, 10) 44,3 1 '

23 В(1,9;2, 9;3,9;4,9;5,9;6,9;7,9;8,9;1, 10;2, 10;3, 10;4, 10;5,10;6,10;7,10;8,10) =40,288 40,288

24 В(1,9;2,9;3,9;4,9;5,9;6,9;7,9;8,9;1,10;2,10;3,10;4,10;5,10;6,10;7,10;8,10) =55,396 84,802

25 1,710 _г\ 1 то/- В(1,10;2,10;3,10;4,10;5,10;6,10;7,10;8,10;9,10) 21,386

26 1,810 —ОС) АО(-\ В(1,10;2,10;3,10;4,10;5,10;6,10;7,10;8,10;9,10) 29,406

27 1,910 В(1,10;2,10;3,10;4,10;5,10;6,10;7,10;8,10;9,10) =39 208 39,208

Рисунок Б.3 - Пропускные способности ПС

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

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

Таким образом, потоковая структура примет следующий вид, представленный на рисунке Б.4.

Рисунок Б.4 - Первичная потоковая структура ТСС

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

ПРИЛОЖЕНИЕ В. ИССЛЕДОВАНИЯ ВИДЕО-ТРАФИКА РЕАЛЬНОГО

ВРЕМЕНИ

Для определения характера видео-трафика с использованием кодека h.264 был собран макет, представленный на рисунке В.1.

Рисунок В.1 - Схема сети, построенная для исследования характеристик видео-трафика H.264

К коммутатору с поддержкой POE подключалась сетевая видеокамера со следующими настройками:

1. Разрешение видео 1920х1080р (FullHD)

2. Частота кадров - 20 кадр/с

3. Интервал I-кадра - 20

4. MTU - 1500

5. ConstantBitRate

6. Максимальный BitRate - 8192 Кбит/с

7. Видеокодек H.264

Также к этому же коммутатору подключалась рабочая станция видеонаблюдения, на которой одновременно запускались отображение видеопотока и трафик-сниффер. Изображение, попадавшее в объектив видеокамеры, было статичным и неизменным в течении проведения исследования. Время исследования - 25 мин оказалось достаточным для выявления характеристик видео-трафика, а также позволило произвести его обработку. За указанное время было получено 1 047 586 RTP кадров, которые инкапсулировались в UDP пакеты, затем в IP и Ethernet -кадры как указано на рисунке В.2. (Максимальное число срок в MSExcel - 1 048 576)

си

с о. о.

си .с > о. о э н сс Н.264

4-1 ш

Рисунок В.2 - Структура 1 фрейма видеопотока

В ходе анализа промежутков времени между последовательно приходящими иОРпакетами на интерфейс рабочей станции с использованием подхода классической статистики [36] (правило Стерджеса) получена гистограмма, изображенная на рисунке В.3, при этом средний интервал времени между пакетами равен 0,0013 с, а средняя длительность фрейма - 1458 байт, что соответствует битовой скорости равной примерно 8 Мбит/с ((1458+14)*8/0,0013)=8,035 Мбит/с

Рисунок В.3 - Гистограмма временного ряда между пакетами исследуемого видеопотока

построенная по правилу Стреджеса

Однако такой подход не отображает сути происходящих процессов и сетевых механизмов. При изменении масштабов временной шкалы, а также фильтрации временных интервалов можно получить некоторые закономерности, однако для точного определения временных характеристик видеопотока необходимо определить, как происходит кодирование видео с использованием кодека Н.264. Для этого определим, как происходит кодирование видео с использованием кодека Н.264 [31].Структура видеопотока (применительно к указанным выше исходным данным) может принимать вид, представленный на рисунке 2.11, что впоследствии

было доказано в ходе анализа отдельных компонентов видео-трафика. С учетом исходных данных, получаем, что каждую 1 с., необходимо передать полную картинку, попавшую в объектив видеокамеры. Далее следует P-фрейм, содержащий информацию об изменении изображения за 1/20 с, относительно I-фрейма. Тогда B-фрейм содержит информацию об изменении изображения за те же 1/20 с, но относительно как P-фрейма, так и I фрейма. Такой подход кодирования видеопотока позволяет снизить требования к пропускным способностям канала связи, а также позволяет увеличить «глубину» архива видеоданных. Однако, при воспроизведении такого потока, предъявляются повышенные требования к производительности устройства видео воспроизведения, т.к. необходимо хранить данные I и P -фреймов и постоянно вычислять изменения в кадре относительно указанных фреймов.

Таким образом, для получения структурированной модели генератора задержек, из полученного временного ряда прихода пакетов на интерфейс исследуемой станции видеонаблюдения в работе выделены границы для всех кадров I, P и B. Проведена оценка временных задержек между указанными кадрами, также длительности каждого кадра и определены временные интервалы между соседними фреймами внутри каждого кадра. Для определения начала и конца кадра необходимо использовать временную метку Timestamp, которая указывает абсолютное время, принадлежащее каждому кадру. Здесь и далее будем считать «кадр» — это изображение, полученное в данный момент времени, а «фрейм» или «IP пакет» - состоящий из заголовков Ethernet, IP и UDP включая управляющие протоколы и полезную нагрузку, необходимые для восстановления видеоизображения. Так как информация, содержащаяся в одном кадре, не может уместиться в одном фрейме, то несколько фреймов несет информацию об одном кадре. При этом не корректно говорить о фрагментации IP пакета, т.к. информация одного кадра на устройстве порождающим видеопоток таким образом разбивается на определенное число фреймов. Общий вид данных полученный сниффером, изображен на рисунке В.4. Из рисунка видно, что в качестве дополнительного инструмента, подтверждающего принадлежность пакетов кадрам, является

служебная метка РТС 3984 [32].

конца каждого кадра - Mark, согласно

рекомендации

772

773

774

775

776

777 77S

779

780

781

782

783

784

785

786

787

788

789

790

791

792

793

794

795

796

797

798

799

800 801 802

803

804 S05 806

807

808

809

810 811 812

813

814

815

Time

21.165049