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

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

Тупицын Виталий Валерьевич

РАЗРАБОТКА И АНАЛИЗ АЛГОРИТМА ПОСТРОЕНИЯ ТОПОЛОГИИ СЕТИ МНОГОТОЧЕЧНОЙ ВИДЕОКОНФЕРЕНЦСВЯЗИ

Специальность: 05.12.13 Системы, сети и устройства телекоммуникаций

Автореферат

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

Ярославль - 2013 Оиоэ—-

005546875

Работа выполнена на кафедре динамики электронных систем ФГБОУ ВПО «Ярославский государственный университет им. П.Г. Демидова»

Научный руководитель: Доцент кафедры динамики электронных систем ЯрГУ

им. П.Г. Демидова, кандидат технических наук, доцент Тараканов Алексей Николаевич

Официальные оппоненты: доктор технических наук, профессор,

кафедры радиотехники и радиосистем ВлГУ Галкнн Александр Павлович

кандидат технических наук, нач. отдела защиты информации филиала ОАО АКБ «Югра», г. Ярославль Меньшиков Борис Николаевич

Ведущая организация: ОАО «Ярославский радиозавод»

Защита диссертации состоится «20» декабря 2013 г. в 16.00 часов на заседании диссертационного совета Д.212.025.04 при ФГБОУ ВПО «Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых» по адресу: 600000, г. Владимир, ул. Горького, 87, ВлГУ, корпус 3, ФРЭМТ, ауд. 301.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО Владимирского государственного университета имени Александра Григорьевича и Николая Григорьевича Столетовых.

Автореферат разослан «19» ноября 2013 г.

Отзывы на автореферат, заверенные печатью, просим направлять по адресу: 600000, г. Владимир, ул. Горького, д. 87, ВлГУ, ФРЭМТ.

Ученый секретарь диссертационного совета, доктор технических наук, профессор

А.Г. Самойлов

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

Актуальность темы исследования

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

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

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

Для выполнения установленных требований для разного количества участников необходимо обеспечить баланс информационных потоков с учетом характеристик всех каналов и устройств в сети. При проведении сессии ВКС крупного масштаба от 20 участников с использованием централизованного подхода вся нагрузка на обеспечение качественной связи ложится на MCU (Media Control Unit - сервер многоточечной ВКС), что требует высокопроизводительного оборудования, обладающего высокой стоимостью и высокопроизводительные каналы связи.

Децентрализованная система ВКС позволяет распределить нагрузку на все элементы пропорционально их ресурсам и характеристикам, тем самым увеличивая масштабируемость и уменьшая стоимость такого решения. Исследования, проведенные в данном направлении, показали, что наилучших результатов можно добиться при организации многоточечной ВКС на основе децентрализованных самоорганизующихся сетей и специальных алгоритмов построения топологии сети на прикладном уровне модели OSI (NICE, SAHC, ZigZag). Главным достоинством таких алгоритмов является отсутствие необходимости поддержки протоколов прикладного уровня на сетевом оборудовании и высокая степень масштабируемости. Однако большинство из этих алгоритмов используют один узел в виде центрального элемента, и информационный поток передается по одному маршруту на все узлы сети, что негативно сказывается на характеристиках работы системы в случае проведения сессии крупной многоточечной ВКС от двадцати участников.

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

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

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

Таким образом, актуальной является задача разработки алгоритма построения логической топологии 1Р-сети с использованием новой метрики для организации МВКС на прикладном уровне.

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

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

1. Разработка новой метрики расчета топологии сети ВКС, состоящей из трех критериев и учитывающей рекомендации МСЭ.

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

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

4. Исследование сетевых характеристик получаемого решения и его м ас штаб и ру е м ости.

Объектом исследования являются распределенные системы МВКС в 1Р-сетях на прикладном уровне.

Предметом исследования является разработка алгоритма построения логической топологии сети на основе множественных деревьев в распределенных системах МВКС

Методы исследования

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

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

1. Предложена метрика расчета стоимости связей в распределенных системах на основе времени задержки сигнала, количества потерянных пакетов и используемой полосой пропускания, в соответствии с Рекомендациями Международного Союза Электросвязи (МСЭ).

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

3. Разработан алгоритм построения логической топологии распределенной 1Р-сети на прикладном уровне для организации МВКС.

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

Практическая значимость

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

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

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

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

Результаты работы внедрены в соответствующие разработки предприятия ООО «Медиа-мир», г. Ярославль. Отдельные результаты диссертационной работы внедрены в учебный процесс ЯрГУ им. П.Г. Демидова в рамках дисциплин «Системы коммутации», «Сети связи».

Личный вклад автора.

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

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

Апробация работы

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

- 12-ой, 14-ой Международной конференции «Цифровая обработка сигналов и ее применение». Москва, 2010, 2012.

- 21-ой Международной научно-технической конференции «Информационные средства и технологии». Москва, 2013.

- 12-ой Международной научно-практической конференции «Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности». Санкт-Петербург, 2012.

- 13-ой Всероссийской научно-практической конференции «Проблемы развития и применения средств ПВО в современных условиях». Ярославль, 2012.

- 1Х-ой Международной научно-технической конференции «Техника и технология: Новые перспективы развития». Москва, 2011.

Публикации по работе

По теме диссертации опубликовано 12 научных работ, из них 2 статьи в журналах, рекомендованных ВАК для публикации результатов диссертационных исследований, 10 докладов на научных конференциях, получено свидетельство о регистрации программы для ЭВМ.

Структура и объем работы

Диссертация состоит из введения, трех разделов, заключения, списка использованных источников, содержащего 112 наименования, и приложения. Она изложена 119 страницах машинописного текста, содержит 32 рисунка и 8 таблиц.

На защиту выносятся

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

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

3. Алгоритм построения логической топологии 1Р-сети на прикладном уровне модели ОБ1 на основе множественных деревьев, с использованием предложенной методики и метрики для организации системы многоточечной ВКС.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе выполняется аналитический обзор современных подходов построения и анализа топологии сети на прикладном уровне модели 0Б1 для организации МВКС.

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

Самоорганизующиеся сети являются наложенными на IP-сети различного масштаба (интранет, интернет). Такие сети работают на прикладном уровне, над транспортным уровнем модели OS1, который соответствует уровню UDP/TCP стека протоколов TCP/IP. В связи с этим следует различать маршрутизацию на сетевом уровне, где процесс распределения IP пакетов выполняют маршрутизаторы и маршрутизацию на прикладном уровне, где потоки информации распределяются с помощью оконечных абонентских устройств. Узлы в наложенной сети соединены логическими каналами связи на прикладном уровне и они не связаны с физической и логической топологией сети (рис. 1).

Рис. 1. Распределенная наложенная сеть на прикладном уровне.

Выбор конкретного маршрута передачи данных осуществляется в соответствии с используемым критерием эффективности - метрикой. В большинстве случаев к метрикам относятся следующие критерии: длина маршрута или число перенаправлений через транзитные узлы (hop); ширина полосы пропускания (bandwidth); задержка (delay); надежность (reliability); нагрузка сети (load) и стоимость связи (cost).

Рассмотрим существующие алгоритмы построения топологии сети на уровне приложения модели - алгоритм «Найс» (NICE) и алгоритм «САКС» (SAHC). В алгоритме «Найс» топология сети представляет собой иерархическое дерево с набором уровней, состоящих из кластеров. Узлы в дереве располагаются по метрике, рассчитываемой из двух параметров: временем между отправкой запроса и получением ответа (RTT - Round trip time) и числом промежуточных узлов между начальной точкой отправки запроса и конечной (Hops). В алгоритме «САКС» топология сети так же представляет собой иерархическое дерево, состоящее из нескольких уровней, которые состоят из узлов, находящихся в концентрических кольцах. Радиус колец определяется в соответствии с RTT. К недостаткам этих алгоритмов можно отнести отсутствие одновременного учета таких параметров, как надежность канала связи, используемая ширина полосы пропускания, задержки доставки сигнала. Эти параметры позволяют более равномерно распределить нагрузку на каждый элемент сети.

Рассмотрим метод идеальной точки для расчёта расстояния в многомерном пространстве критериев между точкой, соответствующей идеальному значению критериев, и точкой, соответствующей рассматриваемой значению. Положение идеальной точки в многомерном пространстве соответствует наилучшему значению всех критериев. Наиболее приемлемой из всех вариантов считается та точка, у которой расстояние от «идеальной точки» минимально:

где Л^ — количество критериев оценки альтернатив;

Хш — идеальное значение по .¡-му критерию для идеального варианта;

ЛТ,; - значение по.¡-му критерию для ¡-ой альтернативы.

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

Задачу организации МВКС можно разбить на несколько подзадач:

- определение суперузлов в дереве, с наименьшими значениями С/(/,/);

- построение деревьев с корнями в виде суперузлов, используя алгоритм поиска

- вещание трафика в сети, используя алгоритм распределения информации по

в ширину;

сети.

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

Свертка данных метрики методом «идеальной точки» требует одинаковой размерности всех величин. Для этого зададим следующие критерии: • для количества потерянных пакетов

Р,

• тш, Р,

1--

N.

М,

'<] /

где Тч^ j — количество принятых пакетов, Му - количество переданных пакетов; • для сквозной задержки

I

-И,

С

где С-это константа, определяемая согласно рекомендации МСЭ У. 154Г.

- первый уровень до 100 мс - отличное качество связи;

- второй уровень от 100 мс до 400 мс — считается хорошим качеством связи. Такое качество связи вызывает проблемы при осуществлении приложений, работающих в реальном времени;

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

и 0 <¿, , <100

С= 12, 100 < < 400

з, а,, > 4оо

для ширины полосы пропускания

В„т

-И,

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

смежности.

Свертка трех критериев методом идеальной точки будет иметь:

' 1.. У

С 4

(

V

+ ЛГ,

+ к.

'В Л2

V у

Для коэффициентов А',, А", и К. в этой формуле положим, что они изменяются в диапазоне от 0 до 1, и их сумма должна быть равна единице:

Kl +K2+K3= 1. 0< K{ <1, О < К 2 < 1, 0< Кг <1.

Использование весовых коэффициентов в метрике является необходимостью

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

функции.

Алгоритм построения топологии сети на основе множественных деревьев

1. Узел-источник F становится корнем дерева.

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

GSi (F, Sl) = min{G(F, j)}. j = 1... /V.

3. Определяются остальные суперузлы G, (F.Sj) = min{G(F,/)} J = 1...Л'

(GS. (F.SJ)-GSI (F,SH ))<CSt(F.Srl) ■

4. Определяется количество суперузлов

A

/

5. Рассчитывается топология от каждого суперузла до всех дочерних узлов по алгоритму АМД с использованием метрики, описанной выше для вычисления G(i.j).

6. Вычисляются основные характеристики, влияющие на качество работы системы ВКС на основе АМД (рис. 2), при заданном интервале возможных значений коэффициентов К: количество узлов на уровнях С, количество дочерних узлов М и количество повторяющихся маршрутов У в разных деревьях топологии. Предлагается использовать эти характеристики для определения минимального значения функции T(C,M,Y), которая указывает на наиболее эффективное строение топологии сети для организации ВКС:

г

Ус

1 -М 7 (?}

L2 у=2 5 3

количество узлов на уровнях, начиная с третьего количество линий связи, начиная с двух, у несуперузла с дочерними узлами; уровень, где расположен узел с Л/ ■;

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

где С, -

МГ

s -

Ук

7. Определяется логическая топология сети с наименьшим значением функции Т(С,М,У).

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

9. Отправляется один субпоток с источника на один суперузел.

10. Посылается один субпоток с суперузла на все дочерние узлы.

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

Такой вид функции (2) обусловлен сильным влиянием параметров С, М и У на сетевые характеристики, описанные в рекомендации У. 1541 МСЭ. При , использовании МВКС с небольшим количеством участников (3-6 человек) определяющим значением функции Т(С,М,У) будет являться первое слагаемое, так как остальные слагаемые равны 0. Для выполнения зависимостей, описанных ранее, количество узлов на втором уровне должно стремиться к максимальному значению.

Рис. 2. Блок-схема алгоритма множественных деревьев II

Уровень 0 Уровень 1 Уровень 2 Уровень 3 Уровень 4

Рис. 3. Передача информации через сеть с разбиением на субпотоки.

В третьей главе проводится сравнение разработанного алгоритма построения логической топологии сети на основе множественных деревьев для распределенной системы МВКС с известными алгоритмами «Найс» и «САКС».

Рассмотрим результаты компьютерного моделирования работы АМД для 5, 10, 15 и 20 узлов. Шаг изменения интервала значений весовых коэффициентов -

0.1. Интервал значений количества узлов в сети соответствует минимальному (5) и типичному (20) числу участников для использования АМД в многоточечной ВКС. Используя данные из матрицы смежности по сквозной задержке, количеству потерянных пакетов, полосе пропускания, и применяя АМД, строится топология сети. Разбиение потока на субпотоки происходит с помощью алгоритма МКВ. С учетом ограничений и заданным интервалом перестройки, возможно 72 комбинации весовых коэффициентов. В результате их анализа можно выделить три группы по количеству потерянных пакетов, сквозной задержке и размеру мультимедиа потока. Отберем значения весовых коэффициентов, соответствующих каждой группе, которые демонстрируют характерное поведение сети МВКС для каждой группы коэффициентов &'(/,/):

1. £,=0,3, К, =0,3, К, =0,4;

2. АГ, =0,3, =0,5, АГ3 =0,2;

3. А:, =0,8, £,=0,1, АГ3= 0,1

Полученные данные (рис. 4) показывают влияние весовых коэффициентов на сетевые характеристики для разного количества участников ВКС. Использование набора весовых коэффициентов № 1 (табл. 1) с наименьшим значением Т{С,М,У) для 5 участников позволяет сократить количество потерянных пакетов на 10% и 7%, при этом, уменьшая задержку сигнала на 26% и 46% по сравнению с алгоритмами «Найс» и «САКС». Увеличение количества участников ВКС сохраняет тенденцию улучшения работы системы с использованием АМД.

Таблица 1

Значение функции Т(С,М , К) для 3-х наборов весовых коэффициентов

Т(С,М,У) для 5 узлов Т(С,М,У) для 10 узлов Т(С,М,У) для 15 узлов Т(С,М,Г) для 20 узлов

АГ, =0.3, К, =0,3, К, =0.4 0.125 2.143 2,054 10,256

£,=0.3, К2 =0,5, К,=0,2 0,286 4,500 6,772 22.454

АГ, =0.8, Кг= 0,1, А:, = 0.1 0,125 2.091 3,147 14,688

Г> Ю 15 20

к,= оз к?=о.з

к3= 0.4

10 15 .........................1 1 .............8

20 1

К,= 0.3 Ка=0.5 К3=0.2

5 10 15 20;

К,-0.8

кг-°.1

К,» 0.1 а)

5.10 15

5 10 ; 15 го!

230150-

■,20

К2=0.3 К,= 0.4

120:

кг= 0.5 к.,= 0.2

20

; 15

: 10

К,= 0.8 Кг= 0,1 К,= 0.1

б)

15!

20!..

: 10

Найс

! 15 : 10;

20

САКС

10 1« 20

К,= 0.3 К2» 0.3 К,= 0 4

6 110;15 | 5

5;ю

15;20;

к,= о.з

к2= 0.5 К3= 0.2

К,= 0.8 К2= 0.1

к,» 0.1

В)

Г15

20 I

10

15 I

: 20

Рис. 4. Результаты работы системы ВКС: а) используемая полоса пропускания: б) сквозная задержка сигнала; в) количество потерянных пакетов

Рис. 5. Графы сети для 20 узлов при наборе весовых коэффициентов: а) А", =0,8, АГ2=0»1, Аз =0,1; б) К, =0,3, К2=0,5, £3 = 0,2; в) А, =0,3, А', =0,3, А3=0,4

При увеличении в топологии количества уровней и числа дочерних узлов на уровнях ниже второго, происходит сильный скачок сквозной задержки сигнала. Установлено, что особенно это заметно в случае использования АМД с набором весовых коэффициентов ЛГ, =0,3, К2= 0,5, £,=0,2. Такие результаты объясняются тем, что в этом примере единственный вклад в значение метрики 0(7,/) вносит полоса пропускания, а другие параметры равны 0. Для набора весовых коэффициентов № 1 с различным количеством узлов в топологии значение задержки сигнала уменьшается от 26% до 72% по сравнению с алгоритмами «Найс» и «САКС». Наибольшая разница в результатах между АМД (набор весовых коэффициентов № 1) и другими алгоритмами достигается для топологии сети с 15 узлами, где диапазон значений составляет от 63% до 72%.

Установлено, что одновременно с уменьшением количества потерянных пакетов и сквозной задержкой сигнала АМД позволяет передавать на 7-15% больший суммарный информационный поток по сравнению с алгоритмом «САКС» и на 3—1% — по сравнению с алгоритмом «Найс». В проведенном исследовании топология сети АМД набор весовых коэффициентов № 1 является наиболее эффективной, так как значение функции Т(С,М,У) достигает минимального значения для разного количества узлов, а сетевые характеристики стремятся к рекомендуемым.

0

1

со

3 I

I

о. с с

Ё а

1

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

Основные выводы и результаты работы

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

Номер передающего узла Номер передающего узла Номер передающего узла

а) б) в)

Рис. 6. Интенсивность нагрузки узлов связи при различных наборах весовых коэффициентов: а) ЛГ, =0,8, £, =0,1, £, =0.1; б) £,=0,3, £,=0,5. К,= 0,2; в) £,=0,3, £2=0,3, £3=0,4

2. Выведена формула, определяющая «идеальную» логическую топологию IP-сети в АМД на основе строения его деревьев для организации МВКС. Полученные результаты подтверждают выбор теоретического аппарата для определения эффективного строения топологии сети.

3. Разработана методика определения количества суперузлов для распределения информации в IP-сети на основе значений, полученных новой метрикой. Показано, что при значительном увеличении количества субпотоков и суперузлов (более 4) наблюдается резкое ухудшение сетевых характеристик в соответствии с рекомендациями МСЭ.

4. Результаты компьютерного моделирования показали, что одновременно с уменьшением количества потерянных пакетов и задержкой сигнала АМД позволяет передавать на 7-15% больший суммарный информационный поток по сравнению с алгоритмом ««САКС»» и на 3-7% - по сравнению с алгоритмом «Найс» в зависимости от набора весовых коэффициентов в предложенной метрике.

5. Предложенные алгоритмы могут быть использованы для организации работы систем МВКС на основе IP-сетей.

Список работ, опубликованных по теме диссертации

Публикации в изданиях из перечню ВАК

1. Тупицын, В.В. Построение сети видеоконференцсвязи по алгоритму Дейкстры на основе новой метрики / В.В. Тупицын, А.Н. Тараканов, A.JI. Приоров // Вестник компьютерных и информационных технологий. - М„ 2013. - С. 34-40.

2. Тупицын, В.В. Исследование масштабируемости систем многоточечной видеоконференцсвязи на основе алгоритмов множественных деревьев / В.В. Тупицын, А.Н. Тараканов, A.JI. Приоров // Проектирование и технология электронных средств. - Владимир. 2012. - С. 20-24

В остальных изданиях

3. Тупицын, В.В. Передача потокового видео по сети Radio Ethernet стандарта IEEE 802.11b при максимальной загрузке канала / В.В. Тупицын, В.Г. Медведев, A.JI. Приоров // 14-ая международная конференция «Радиоэлектроника, электротехника и энергетика». Сборник докладов. - М., 2007-С. 61-64.

4. Тупицын, В.В. Передача потокового видео по IP-сети при значительной загрузке канала с применением восстанавливающего алгоритма QoS / В.В. Тупицын, В.Г. Медведев, Е.В. Давыденко // 9-ая международная конференция «Цифровая обработка сигналов и ее применение». Сборник докладов. - М., 2007 - С. 74-76.

5. Тупицын, В.В. Внедрение технологии Triple-Play в локальную сеть Ethernet в режиме максимальной загрузки канала / В.В. Тупицын, В.Г. Медведев, A.JI. Приоров // 10-ая международная конференция «Цифровая обработка сигналов и ее применение». Сборник докладов. - М., 2008 - С. 81-83.

6. Тупицын, B.B. Имитационное моделирование сети мониторинга дорожного движения, построенной на основе технологии IEEE 802.15.4 ZigBee / B.B. Тупицын, А.Н. Ермаков, П.А. Савасин // 12-ая международная конференция «Цифровая обработка сигналов и ее применение». Сборник докладов. - М„ 2010-С. 111-113.

7. Тупицын, В.В. Анализ алгоритма множественных деревьев для топологии пиринговых сетей при организации многоточечных конференций // 9-ая Всероссийская научно-техническая конференция «Динамика нелинейных дискретных электротехнических и электронных систем». Материалы. - Чебоксары. 2011. - С. 55-57

8. Тупицын, В.В. Анализ алгоритма множественных деревьев и алгоритма NICE для топологии пиринговых сетей при организации многоточечных конференций. / В.В. Тупицын, А.Н. Тараканов, П.А. Савасин, А.Н. Ермаков, A.B. Абрамов, И.С. Ненахов // 4-ая научно-практическая конференция «Техника и технология Новые перспективы развития». Материалы. - М., 2011. -С. 97-100.

9. Тупицын, В.В. Анализ влияния параметров сети на построение топологии посредством алгоритма множественных деревьев. / В.В. Тупицын, П.А. Савасин // 8-ая Всероссийская научно-техническая конференция «Информационные технологии в электротехнике и электроэнергетике». Материалы. - Чебоксары. 2012. - С. 45^18.

10. Тупицын, В.В. Алгоритм построения множественных деревьев для пиринговых сетей / В.В. Тупицын, А.Н. Тараканов, П.А. Савасин, А.Н. Ермаков, A.B. Абрамов, И.С. Ненахов // 12-ая международная научно-практическая конференция «Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности». Сборник статей. — СпБ., 2012.-С. 170-173.

11. Тупицын, В.В. Использование алгоритма множественных деревьев для построения сети видеоконференцсвязи / В.В. Тупицын, А.Н. Тараканов, А.Л. Приоров // 13-ая всероссийская научно-практическая конференция «Проблемы развития и применения средств ПВО в современных условиях». Сборник докладов. — Ярославль: Филиал BKA им. А.Ф. Можайского. 2012 Филиал BKA им. А.Ф. Можайского. — 263-268

12. Тупицын, В.В. Организация системы видеоконференцсвязи с использованием алгоритма множественных деревьев / В.В. Тупицын, А.Н. Тараканов, П.А. Савасин, А.Н. Ермаков, A.B. Абрамов, И.С. Ненахов // 14-ая международная конференция «Цифровая обработка сигналов и ее применение». Сборник докладов. - М., 2012 - С. 95-96.

13. Тупицын, В.В. Программа для анализа работы телекоммуникационных сетей и прогнозирования качества обслуживания - Unitracer / В.В. Тупицын, А.Н. Тараканов, П.А. Савасин, И.А. Манов // Свидетельство о регистрации в Реестре программ для ЭВМ №2013614535 от 14.05.2013.

Тупицын Виталий Валерьевич

РАЗРАБОТКА И АНАЛИЗ АЛГОРИТМА ПОСТРОЕНИЯ ТОПОЛОГИИ СЕТИ МНОГОТОЧЕЧНОЙ ВИДЕОКОНФЕРЕНЦСВЯЗИ

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

Подписано в печать 18.11.2013 Формат 60><84 1/16. Тираж 100 экз. Напечатано ИП Платонова П.В. (печатный салон «Спринт Пресс») 150000, Ярославль, ул. Б. Октябрьская, 37 18

ЯРОСЛАВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

имени П.Г. ДЕМИДОВА

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

04201456448

Тупицын Виталий Валерьевич

РАЗРАБОТКА И АНАЛИЗ АЛГОРИТМА ПОСТРОЕНИЯ ТОПОЛОГИИ СЕТИ МНОГОТОЧЕЧНОЙ ВИДЕОКОНФЕРЕНЦСВЯЗИ

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

Диссертация

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

Научный руководитель кандидат технических наук, доцент Тараканов Алексей Николаевич

Владимир 2013

Содержание

Введение 6

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

1.1. Вводные замечания 13

1.2. Многоточечная видеоконференцсвязь 14

1.2.1. Виды видеоконференцсвязи 17

1.2.2. Видеоконференцсвязь с использованием сервера 20

1.3. Технологии передачи видеоданных 23

1.4.1. Многоадресное вещание по 1Р-сети 23

1.3.2. Внутридоменные протоколы многоадресного вещания 24

1.3.3. Междоменная маршрутизация пакетов 27

1.4. Распределенные сети 33

1.4.1. Классификация распределенных самоорганизующихся 35 сетей

1.4.2. Структурированные распределенные 38 самоорганизующиеся сети

1.5 Системы распределения информации в самоорганизующихся 39 распределенных сетях

1.5.1 Алгоритм «Зиг-Заг» 40

1.5.2 Алгоритм «НАЙС» 41

1.5.3 Алгоритм «САКС» 43

1.5. Краткие выводы 46

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

2.1. Вводные замечания 47

2.2. Основные требования к топологиям множественных деревьев

2.3. Процедура проверки связности графа 52

2.4. Новая метрика для определения стоимости связей между узлами в топологии сети

2.5. Критерий определения эффективной структуры сети для передачи данных в реальном времени

2.6. Алгоритм построения логической топологии 1Р-сети на ^ основе множественных деревьев

2.7. Краткие выводы ^

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

3.1. Вводные замечания ^

3.2. Определение числа субпотоков для многопутевой передачи ^ мультимедиа трафика реального времени

3.3. Оценка масштабируемости предлагаемого решения 72

3.4. Анализ интенсивности нагрузки на отдельные элементы сети 79

3.5. Определение набора весовых коэффициентов для построения эффективной топологии сети

3.6. Анализ вычислительной сложности предложенного алгоритма

3.7. Краткие выводы 92

Заключение 93

Список Литературы 95

Приложение 1 К°Д пРогРаммы, моделирующей сеть 108

1 многоточечной видеоконференцсвязи

П ж нии 2 Акты внедрения результатов диссертационной цд р работы

Перечень сокращений

Видеоконференцсвязь Многоточечная Видеоконференцсвязь

Международный Союз Электросвязи

Address Allocation Protocol - протокол распределения адресов

Autonomous System - автономная система

Border Gateway Protocol - протокол пограничного шлюза

Content Delivery Network - сеть доставки контента

Constant Bit Rate - постоянная битовая скорость

Distance Vector Multicast Routing Protocol - протокол дистанционно-векторной многоадресной маршрутизации

Enhanced Interior Gateway Routing Protocol - расширенная версия протокола IGRP

Internet Group Management Protocol - межсетевой протокол управления группами

Internet Protocol - интернет протокол Вещание видеоданных по IP протоколу Local Area Network - локальная сеть

Multicast Address Allocation Server - сервер распределения групповых адресов

Multicast Address-Set Claime - схема распределения мультикаст адресов

Multicast Border Gateway Protocol - протокол пограничного шлюза для многоадресных маршрутов

Multicast Backbone - специальная информационная магистральная сеть

Media control unit - сервер для организации ВКС

Multicast Source Discovery Protocol - протокол обнаружения источников многоадресных сообщений

Open System Interrupt - взаимодействие открытых систем

Open Shortest Path First - протокол динамической маршрутизации

Protocol Independent Multicast Sparse Mode - протокол маршрутизации многоадресных сообщений

Quality of Service - качество обслуживания

Routing Information Protocol - протокол маршрутной информации

Request for Comments - пронумерованная документация, содержащий технические документации и стандарты

Source Active - сообщение об активности

Scalable Adaptive Hierarchical Clustering - алгоритм с адаптивной иерархической кластеризацией Session Announcement Protocol - протокол анонсирования сеанса

Session Description Protocol - протокол описания сеанса Time to Live - время существования пакета данных

ВВЕДЕНИЕ

Актуальность темы исследования

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

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

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

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

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

t

с учетом характеристик всех каналов и устройств в сети. При проведении сессии ВКС крупного масштаба от 20 участников с использованием централизованного подхода вся нагрузка на обеспечение качественной связи ложится на MCU (Media Control Unit - сервер многоточечной ВКС), что

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

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

В настоящее время использование таких систем для проведения МВКС достаточно широко изучено. Первые теоретические работы опубликованы Коммаредди, Вангом, Кастро и др. [5-9] В последние годы наблюдается значительный рост активности разработок в этом направлении, в связи с увеличением пропускной способности каналов «последней мили», позволяющих участвовать в МВКС [20-31, XX]. Применение современных алгоритмов сжатия информации в совокупности с новейшими разработками в области передачи информации по различным каналам связи позволяет использовать данную услугу на широком множестве устройств и платформ.

Исследования, проведенные в данном направлении, показали, что наилучших результатов можно добиться при организации многоточечной ВКС на основе децентрализованных самоорганизующихся сетей и специальных алгоритмов построения топологии сети на прикладном уровне модели OSI («Найс,» «САКС», «Зиг-Заг»).

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

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

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

Таким образом, актуальной является задача разработки алгоритма построения логической топологии 1Р-сети с использованием новой метрики для организации МВКС на прикладном уровне.

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

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

1. Разработка новой метрики расчета топологии сети ВКС, состоящей из трех критериев и учитывающей Рекомендации Международного союза электросвязи (МСЭ).

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

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

4. Исследование сетевых характеристик получаемого решения и его масштабируемости.

Объектом исследования являются распределенные системы МВКС в ГР-сетях на прикладном уровне.

Предметом исследования является алгоритм построения логической топологии сети на основе множественных деревьев в распределенных системах МВКС.

Методы исследования

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

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

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

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

3. Разработан алгоритм построения логической топологии распределенной 1Р-сети на прикладном уровне для организации МВКС.

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

Практическая значимость

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

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

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

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

Результаты работы внедрены в соответствующие разработки предприятия ООО «Медиа-мир», г. Ярославль. Отдельные результаты диссертационной работы внедрены в учебный процесс ЯрГУ в рамках дисциплин «Системы коммутации» и «Сети связи».

Личный вклад автора

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

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

Апробация работы

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

10

- 12-ой, 14-ой Международной конференции «Цифровая обработка сигналов и ее применение». Москва, 2010, 2012.

- 21-ой Международной научно-технической конференции «Информационные средства и технологии». Москва, 2013.

- 12-ой Международной научно-практической конференции «Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности». Санкт-Петербург, 2012.

- 13-ой Всероссийской научно-практической конференции «Проблемы развития и применения средств ПВО в современных условиях». Ярославль, 2012.

- 1Х-ой Международной научно-технической конференции «Техника и технология: Новые перспективы развития». Москва, 2011.

Публикации по работе

По теме диссертации опубликовано 12 научных работ, из них 2 статьи в журналах, рекомендованных ВАК для публикации результатов диссертационных исследований, 10 докладов на научных конференциях, получено свидетельство о регистрации программы для ЭВМ.

Структура и объем работы

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

На защиту выносятся

1. Метрика, характеризующая канал связи на основе данных по количеству потерянных пакетов, задержке сигнала и ширине полосы пропускания в соответствии с Рекомендациями МСЭ.

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

11

3. Алгоритм построения логической топологии IP-сети на прикладном уровне модели OSI на основе множественных деревьев, с использованием предложенной методики и метрики для организации системы многоточечной ВКС.

Благодарности.

Автор выражает слова глубокой благодарности своему научному руководителю доценту Алексею Николаевичу Тараканову за помощь и поддержку на всех этапах выполнения данной работы. Отдельная благодарность В.Г. Медведеву, И.С. Ненахову, Ю.С. Корневу, A.B. Абрамову, работы которых оказали значительное влияние на формирование взглядов автора в данном научном направлении.

Особая благодарность профессору Юрию Александровичу Брюханову, доцентам Андрею Леонидовичу Приорову и Владимиру Вячеславовичу Хрящеву за постоянную поддержку во время обучения в аспирантуре и подготовки данной диссертации.

Особая признательность моим коллегам по кафедре В.А. Волохову, И.В. Апалькову, И.Н. Трапезникову, Ю.А. Лукашевичу, И.С. Мочалову, а также соавторам всех моих публикаций.

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

1. АНАЛИЗ СОВРЕМЕННЫХ ПРОБЛЕМ В СИСТЕМАХ МНОГОТОЧЕЧНОЙ ВИДЕОКОНФЕРЕНЦСВЯЗИ

1.1. Вводные замечания

На протяжении более двух десятилетий использование современных решений в области высоких технологий позволяет развиваться одному из самых перспективных направлений межличностных коммуникаций -видеоконференцсвязи (ВКС) [1-4]. В последнее время наблюдается настоящий переворот в данной области, связанный с появлением нового стандарта сжатия -Н.265, который должен стать достойной заменой кодеку Н.264 при потоковой передаче видео, а с его внедрением требования к пропускной способности каналов передачи данных снизятся практически вдвое. Кроме того на настоящий момент для видеосвязи характерно интеграция социальных сервисов и облачных решений.

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