Разработка и исследование метода балансировки трафика в пакетных сетях связи тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат наук Дорт-Гольц, Антон Александрович

• Дорт-Гольц, Антон Александрович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Дорт-Гольц, Антон Александрович

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. АНАЛИЗ МЕТОДОВ БАЛАНСИРОВКИ СЕТЕВОГО

ТРАФИКА

1.1. Анализ свойств трафика и его влияния на состояние современных пакетных сетей связи

1.2. Механизмы балансировки сетевого трафика

1.3. Наложенные сети

1.3.1. Самоорганизующиеся наложенные сети

1.3.2. Методы балансировки трафика на основе наложенных

сетей

1.4. Цель и задачи исследования

Выводы по главе 1

ГЛАВА 2. РАЗРАБОТКА МЕТОДА БАЛАНСИРОВКИ ТРАФИКА НА

ОСНОВЕ НАЛОЖЕННОЙ СЕТИ

2.1. Механизм наложенной балансировочной сети

2.2. Построение наложенной балансировочной сети

2.2.1. Управление наложенной сетью

2.2.2. Контроль состояния наложенной балансировочной сети

2.2.3. Балансировка транзитного трафика

2.2.4. Отказоустойчивость наложенной балансировочной сети

2.3. Модель оценки возможностей наложенной балансировочной сети

2.3.1. Стратегия балансировки трафика

2.3.2. Параметры наложенной балансировочной сети

2.3.3. Свойства полносвязного графа

2.4. Балансировка трафика наложенной сетью

2.4.1. Контроль входящей нагрузки

2.4.2. Оценка эффективности передачи трафика наложенной балансировочной сетыо

2.4.3. Распределение нагрузки в наложенной балансировочной сети

2.4.4. Распределение потоков в наложенной балансировочной сети

2.4.5. Механизм сглаживания осцилляций маршрутов

Выводы по главе 2

ГЛАВА 3. АНАЛИЗ МЕТОДОВ КРАТКОСРОЧНОГО

ПРОГНОЗИРОВАНИЯ СЕТЕВОГО ТРАФИКА

3.1. Задача краткосрочного прогнозирования временных рядов

3.2. Автоматизированные методы краткосрочного прогнозирования временных рядов

3.2.1. Основные модели краткосрочного прогнозирования

3.2.2. Постановка задачи определения эффективности методов краткосрочного прогнозирования

3.3. Статистический анализ временных рядов интенсивности сетевого трафика

3.4. Анализ эффективности автоматизированных методов краткосрочного прогнозирования

3.4.1. Экспериментальная оценка точности прогнозирования

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

Выводы по главе 3

ГЛАВА 4. ИССЛЕДОВАНИЕ РАБОТЫ НАЛОЖЕННОЙ

БАЛАНСИРОВОЧНОЙ СЕТИ

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

4.1.1. Процесс моделирования работы наложенной

балансировочной сети

4.1.2. Визуализация результатов моделирования

4.2. Исследование работы наложенной балансировочной сети в

условиях статических нагрузок

4.2.1. Исследование влияния количества узлов в балансировочном оверлее на эффективность передачи трафика

4.2.2. Исследование эффективности работы балансировочной сети

в условиях реальных статических нагрузок

4.3. Исследование работы наложенной балансировочной сети в

условиях динамических нагрузок

4.3.1. Исследование поведения наложенной балансировочной сети

в условиях медленно меняющейся нагрузки

4.3.2. Исследование поведения наложенной балансировочной сети

при взрывном характере нагрузки

4.4. Исследование влияния внутренних параметров на работу

наложенной балансировочной сети

4.4.1. Исследование влияния длительности интервала обмена сообщениями UPDATE на функционирование сети LBO

4.4.2. Исследование влияния чувствительности процедуры исключения осцилляций на работу сети LBO

4.4.3. Исследование влияния ошибок, вносимых прогнозированием 130 Выводы по главе 4

ЗАКЛЮЧЕНИЕ

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

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

Приложение А. Временные ряды образцов реального сетевого трафика

Приложение Б. Коды программного симулятора

Приложение В. Акты о внедрении

Введение диссертации (часть автореферата) на тему «Разработка и исследование метода балансировки трафика в пакетных сетях связи»

ВВЕДЕНИЕ

Актуальность работы. Свершившийся переход к концепции построения сетей связи следующего поколения (NGN) утвердил принцип коммутации пакетов в качестве базового для передачи данных различных типов и работы с любым пользовательским трафиком. Эволюционные процессы, происходящие в сетях связи, неизбежно отражаются на объёмах, а также внутренней структуре трафика. Согласно многочисленным исследованиям суммарный объём данных, передаваемых глобальной сетыо, показывает устойчивый экспоненциальный рост со второй половины 90-х годов прошлого века, при этом прогнозы экспертов и аналитиков единодушны: в ближайшие годы данная тенденция сохранится. Наряду с увеличением объёмов данных, поведение трафика современной глобальной сети обнаруживает такую негативную особенность, как нестабильность нагрузки, характеризующуюся возможностью появления резких непредсказуемых скачков интенсивности передачи. Существует множество причин, вызывающих подобную нестабильность. Ярким примером могут служить различные проявления стихийной организации и скоординированных действий множества пользователей, вызванные вирусным характером распространения популярной информации. Лавинообразный процесс вовлечения новых пользователей, новые способы коллективной коммуникации, базирующиеся на широком применении социальных сервисов, массовые онлайн-трансляции, прогнозируемый взрыв М2М-трафика - всё это заставляет говорить о новом характере возникающих нагрузок.

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

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

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

Степень разработанности темы. На данный момент существует довольно большое количество работ, посвященных вопросам организации эффективного распределения нагрузки в сетях связи. Исследования в этой области проводили многие известные отечественные и зарубежные ученые, в числе которых Вишневский В.М., Гайдамака Ю.В., Гольдштейн Б.С., Дымарский Я.С., Канаев А.К., Крутякова Н.П., Кучерявый А.Е., Самуйлов К.Е., Степанов С.Н., Шнепс-Шнеппе М.А., Яновский Г.Г., Fortz В., Kleinrock L., Medhi D., Pioro M., Thorup M. и многие другие.

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

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

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

- разработка математической модели оценки возможностей по распределению и передаче трафика наложенной балансировочной сетью;

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

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

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

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

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

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

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

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

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

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

Полученные в диссертационной работе результаты использованы ОАО «НИИ Масштаб» при подготовке технического проекта ОКР «Мост-СНГ», а также в учебном процессе кафедры сетей связи и передачи данных Санкт-Петербургского государственного университета телекоммуникаций им. проф. М.А. Бонч-Бруевича (СПбГУТ) при чтении лекций и проведении практических занятий по курсам «Маршрутизация в IP-сетях» и «Сетевые технологии, Интернет и NGN» для магистров.

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

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

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

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

- научно обоснованные рекомендации по функционированию наложенной балансировочной сети.

Степень достоверности и апробация результатов. Достоверность результатов подтверждается корректным использованием математических методов исследования и результатами имитационного моделирования. Основные результаты, полученные в диссертационной работе, докладывались и обсуждались на следующих всероссийских и международных конференциях: 16th International Conference on Advanced Communications Technology (ICACT, PyeongChang, South Korea, 2014), 14th International Conference on Next Generation Wired/Wireless Advanced Networks and Systems (NEW2AN, St.-Petersburg, Russia,

2014), на 69-й и 68-й конференциях СПбНТОРЭС им. А. С. Попова. (Санкт-Петербург, 2014, 2013), а также на II Международной научно-технической и научно-методической конференции «Актуальные проблемы

инфотелекоммуникаций в науке и образовании» СПбГУТ (Санкт-Петербург, 2013).

Публикации. Основные положения диссертации изложены в 5 докладах на научно-технических конференциях и 6 научных статьях. Всего по теме диссертации опубликовано 11 печатных работ, из них 3 статьи в изданиях, рекомендованных ВАК Министерства образования и науки Российской Федерации.

Структура и объём диссертации. Диссертация состоит из введения, четырех глав, заключения, списка сокращений и условных обозначений, списка литературы и двух приложений. Работа содержит 148 страниц, 66 рисунков, 13 таблиц.

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

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

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

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

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

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

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

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

ГЛАВА 1. АНАЛИЗ МЕТОДОВ БАЛАНСИРОВКИ СЕТЕВОГО ТРАФИКА

1.1. Анализ свойств трафика и его влияния на состояние современных

пакетных сетей связи

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

На данный момент происходит очередная смена парадигм в вопросах построения сетей связи общего пользования (ССОП). Принято считать, что переход существующих ССОП к концепции сетей связи следующего поколения (Next Generation Networks, NGN) в настоящее время в значительной степени завершён. Основной отличительной чертой данной концепции является эволюция и конвергенция всех сетей, независимо от их назначения, приводящие их к единому знаменателю - принципу построения на базе коммутации пакетов. Действительно, как показывает практика, в подавляющем большинстве случаев современные сети строятся на пакетных технологиях, таких как Ethernet, MPLS, IP. Переход к концепции NGN привел к формированию двух классов операторов: собственно операторов связи, предоставляющих возможность передачи данных, и поставщиков услуг, являющихся в свою очередь клиентами первых. Данный подход значительно отличается от принятого ранее, когда предоставление услуги (например, телефонии) и её доставка обеспечивались единой технологией. В то же время такое разделение ускорило конвергенцию в сетях связи, добиваясь, с одной

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

Дальнейшее развитие сетей связи приводит к необходимости следования новой универсальной концепции Интернета Вещей (Internet of Things, IoT) [18], в рамках которой любой конечный пользователь - человек, устройство или даже приложение - рассматривается в качестве абстрактной «интернет-вещи». Особенностью предлагаемой концепции IoT является способность новой глобальной сети функционировать в условиях количества пользователей, значительно превышающего текущее. Согласно прогнозам международного исследовательского форума [121] количество вещей в глобальной сети достигнет 7 триллионов единиц к 2020 году, другие исследователи [132] дают оценку верхней границы насыщения IoT в 100 триллионов, причем до 2025-2030 годов рост сети будет близок к экспоненциальному. Другой отличительной особенностью можно назвать изменение подхода к построению сетей: новая глобальная сеть базируется на принципах самоорганизации [19]. В данном случае самоорганизация является необходимостью в условиях гетерогенной среды, динамично меняющей свое поведение. Скопления мобильных устройств, сенсоров, разнообразных датчиков генерируют плохо предсказуемый трафик, делая нецелесообразным, а зачастую и невозможным, планирование и централизованное управление такими сетями.

Развитие сетей связи в рамках обозначенных концепций неизбежно отражается на объёмах и структуре трафика. Согласно опубликованным результатам исследований [25] суммарный трафик глобальной сети показывает устойчивый экспоненциальный рост со второй половины 90-х годов XX века. В настоящее время эта тенденция сохраняется, что подтверждают прогнозы развития сетей на ближайшее время [47] (см. рис. 1.1).

140

120

1°о

m a"

f 80 a. н a.

:S 60

3 x a.

re

| 40

>, и

20

I tM

2013 2014 2015 2016 2017 2018

■ Трафик Internet Q Корпоративный + IPTV ■ Мобильный трафик

Рис. 1.1 - Прогноз интенсивности передаваемого 1Р-трафика

Структурный состав передаваемого трафика также будет претерпевать дальнейшие изменения (см. рис. 1.2). Если на начальных этапах перехода к концепции NGN доминировал трафик данных, то теперь наиболее значительную нагрузку создает видео-трафик, доля которого согласно прогнозам должна вырасти до 76% от общего количества передаваемого IP-трафика к 2018 году. Также отмечается тенденция роста доли интернет-трафика, доставляемого пользователям системами CDN (Content Delivery Networks). При этом интенсивность локального трафика, передаваемого в рамках городских сетей (Metro-only) в два раза превышает таковую для магистрального трафика (Long-Haul), а в дальнейшем этот разрыв будет увеличиваться. Таким образом, можно дополнительно отметить тенденцию к локализации сетевого трафика.

Наряду с указанными тенденциями, все более значительной становится нестационарность передаваемой нагрузки. Наблюдается корреляция между временем суток, возрастом, интернет-грамотностью, кругом интересов пользователей с одной стороны и интенсивностью генерируемого ими трафика с другой [24].

90

2013 2014 2015 2016 2017 2018

■ Internet-видео □ Web, email и данные Ифайлообмен ЯТрафик онлайн-игр

Рис. 1.2 - Прогноз структуры пользовательского трафика

Одним из примеров такой нестационарности может служить известный эффект flash-crowd, возникающий при вирусном распространении информации о некотором популярном ресурсе/контенте. Результатом этого эффекта является временный и практически непредсказуемый всплеск интенсивности передаваемого сетевого трафика. Схожие результаты дают запуск онлайн-трансляций, выход крупного обновления популярного программного продукта, широкое использование Р2Р-сервисов и многие другие подобные примеры скоординированных действий большого количества участников сетевого обмена. Подобная координация вызывает резкий рост интенсивности передаваемого трафика и может быть как стихийной, например, в случае вирусного распространения информации в социальных сетях или перераспределения BGP-маршрутов, так и прогнозируемой, примерами которой могут служить просмотр онлайн-трансляций спортивных соревнований, массовое срабатывание множества узлов сенсорной сети при регистрации некоторого природного явления и т. п. На тенденцию увеличения неравномерности нагрузки также указывают прогнозы [47]: интенсивность трафика передаваемого в час наибольшей нагрузки (ЧНН) будет расти относительно средней интенсивности (см. рис. 1.3).

Трафик, Гбит/сек

1|200--— ЧНН

■ средний

2013 2014 2015 2016 2017 2018

Рис. 1.3 - Прогноз роста неравномерности нагрузок в глобальной сети [47]

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

Как известно, традиционные протоколы маршрутизации выбирают путь прохождения данных по сети, оптимальный с точки зрения минимизации выбранной метрики. Такой подход позволяет передавать трафик наилучшим образом с точки зрения количества пройденных сетевых узлов, доступной полосы пропускания, задержек и т.п. Однако ему присущи определенные недостатки. Многие исследователи [35, 129] находят, что использование существующей сетевой инфраструктуры является крайне неоднородным. Так, проведенный в работе [35] анализ интенсивности трафика относительно географического расположения показывает, что в глобальной сети трафик является сильно локализованным, а ранговое распределение подчиняется экспоненциально убывающему закону. На фоне постоянного экспоненциального роста объема передаваемого трафика [47] и вытекающей отсюда необходимости наращивать возможности оборудования такая ситуация выглядит как неэкономное и нерациональное использование существующей инфраструктуры. Тогда как основная нагрузка сосредоточена на некоторых путях, остальная часть сети

используется довольно слабо. Топология современной глобальной сети по результатам многочисленных исследований относится к классу small-world графов [28]. Особенностью таких графов является малая средняя длина пути в графе, а также степенное вероятностное распределение количества ребер случайной вершины. Например, для физической топологии Internet средняя длина пути составляет около 11 проходимых маршрутизаторов, а среднее количество ребер, инцидентных случайной вершине, (/с)«2,66. При этом некоторые

исследователи отмечают тенденцию к уменьшению средней длины пути и общему повышению связности сети [82]. Приведенные факты свидетельствуют, что в глобальной сети существует множество потенциальных маршрутов, позволяющих достигнуть пункта назначения, большинство из которых никогда не будут использованы из-за жестких условий, накладываемых маршрутизацией по кратчайшим путям. Более того, исследования показывают, что составные маршруты в Internet, получаемые на основе метрик нескольких различных протоколов, зачастую не оптимальны. Результаты работы [115] позволяют утверждать, что для 30-80% всех маршрутов, проходящих через глобальную сеть, могут быть найдены альтернативные пути, лучшие по показателям пропускной способности, задержек и потерь. Еще одной топологической особенностью современной глобальной сети является довольно высокий коэффициент кластеризации, показывающий вероятность того, что некоторый случайно выбранный узел окажется связанным с географически близким ему узлом. Например, в исследовании [28] указан коэффициент кластеризации с е (0,2;0,3) (для случайных графов с =¿0,001). Практически это означает, что наиболее плотно между собой связаны соседние узлы, что позволяет предполагать наличие множества путей альтернативных кратчайшему, особенно при маршрутизации в локальных сегментах.

Другим важным вопросом является пропускная способность. Традиционно наименее производительным участком в сети считалась «последняя миля», однако с увеличением возможностей сетей доступа все более актуальной становится проблема возникновения узких мест на других уровнях. В работе [71] отмечается,

что 20-30% соединений, проходящих через глобальную сеть, постоянно маршрутизируются через перегруженные участки, при этом определение конкретного канала связи, на котором происходит перегрузка, достаточно затруднительно. Также наблюдается явная корреляция перегрузки и текущего уровня использования канала, тогда как подобной зависимости в отношении пропускной способности соответствующего канала, а также использования ресурсов маршрутизатора не выявлено. Статистические исследования [27] показывают, что перегруженные каналы равномерно распределены по всей глобальной сети, при этом вероятности возникновения узкого места внутри сегмента провайдера, способного обеспечить инжиниринг трафика, и в каналах между сетями различных провайдеров, где применение таких методов практически исключено, приблизительно равны. Также отмечается, что доля каналов с недостаточной пропускной способностью зависит от положения сетевого сегмента в иерархии, увеличиваясь от 34% у провайдеров Т1ег-1 до 54% у провайдеров Т1ег-4.

На данный момент доминирующим является эмпирический подход, предполагающий экстенсивное наращивание пропускных способностей. Методики, используемые в настоящее время для расчета требуемой пропускной способности канала на уровне агрегации, основываются на статистических профилях трафика, причем для обеспечения должного качества обслуживания в условиях фрактальных эффектов пакетного трафика [12,22,23] вводится эмпирический понижающий коэффициент («0,3), предполагающий работу на недогруженных каналах [21]. Высоконагруженные и критичные участки сетей могут иметь избыточность, значительно превышающую указанную цифру. Так результаты исследования [38] позволяют утверждать, что при существующих методиках планирования сети, использование пропускной способности внутренних каналов современного центра обработки данных при самом худшем сценарии не превысит 25%, тогда как загрузка каналов реальным трафиком в среднем не будет превышать 5%. Оценки создаваемых нагрузок с помощью традиционных методик характерны для расчета сетей, генерирующих

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

Список литературы диссертационного исследования кандидат наук Дорт-Гольц, Антон Александрович, 2014 год

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

1. Алберг, Д. Теория сплайнов и ее приложения: Пер. с англ. / Д. Алберг, Э. Нильсон, Д. Уолш, Ю.Н. Субботин, С.Б. Стечкин. - Мир, 1972.

2. Андерсон, Т. Статистический анализ временных рядов: Т. 1 / Т. Андерсон. -Мир, 1976.

3. Вадзинский, Р.Н. Справочник по вероятностным распределениям / Р.Н. Вадзинский. - Наука СПб, 2001.

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

5. Гольдштейн, Б.С. Сети связи / Б.С. Гольдштейн. - СПб.: БХВ-Петербург, 2010.

6. Гребенников, А. Моделирование сетевого трафика и прогнозирование с помощью модели AR1MA / А. Гребенников, Ю. Крюков, Д. Чернягин. - 2011.

7. Гребешков, А.Ю. Управление сетями электросвязи по стандарту TMN / А.Ю. Гребешков. - М.: Радио и связь, 2004.

8. Грешилов, A.A. Математические методы построения прогнозов / A.A. Грешилов, В.А. Стакун, A.A. Стакун. - М.: Радио и связь, 1997.

9. Дорт-Гольц, А. А. Анализ функционирования наложенных сетей в сетях операторов // Электросвязь. - 2013. - №3. - С. 22-26.

10. Дорт-Гольц, А. А. Анализ протоколов наложенных пиринговых сетей // II МНТНПК «Актуальные проблемы инфотелекоммуникаций в науке и образовании». СПб.: СПбГУТ. - 2013. -С.113-118.

11. Дорт-Гольц, А. А. Анализ трафика анонимных сетей // Материалы 68 НТК СПбНТОРЭС, СПб. - 2013. - С. 98-101.

12. Дорт-Гольц, А. А. Базовые модели сетевых устройств агрегации трафика / Дорт-Гольц А. А., Симонина О. А. // Информационные технологии и телекоммуникации. - 2013. -№2. - С. 13-19.

13. Дымарский, Я.С. Управление сетями связи: принципы, протоколы, прикладные задачи / Я.С. Дымарский, Н.П. Крутякова, Г.Г. Яновский. -Мобильные коммуникации, 2003.

14. Зуховицкий, С.И. Линейное и выпуклое программирование: Справочное руководство / С.И. Зуховицкий, Л.И. Авдеева. - Наука, 1964.

15. Кендалл, М. Многомерный статистический анализ и временные ряды: Пер. с англ. / М. Кендалл, А. Стьюарт, Э.Л. Прейсман, В.И. Ротарь, Ю.В. Прохоров, А.Н. Колмогоров. - Наука. Гл. ред. физ.-мат. лит., 1976.

16. Кормен, Т. Алгоритмы. Построение и анализ:[пер. с англ.] / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. - Издательский дом Вильяме, 2009.

17. Кох, Р. Эволюция и конвергенция в электросвязи / Р. Кох, Г.Г. Яновский. - М.: Радио и связь, 2001.

18. Кучерявый, А.Е. Самоорганизующиеся сети / А.Е. Кучерявый, A.B. Прокопьев, Е.А. Кучерявый. - СПб.: Любавич, 2011.

19. Кучерявый, А.Е. Интернет Вещей / А.Е. Кучерявый // Электросвязь. — 2013. — № 1.

20. Олифер, В.Г. Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 3-е изд / В.Г. Олифер, H.A. Олифер, 2006. - 958 с.

21. Семенов, Ю.В. Проектирование сетей связи следующего поколения / Ю.В. Семенов. - СПб.: Наука и техника, 2005.

22. Симонина, O.A. Модели расчета показателей QoS в сетях следующего поколения: дисс. на соиск. уч. степ. канд. техн. наук. : 05.12.13 / Симонина Ольга Александровна. - СПб, СПбГУТ, 2005.

23. Степанов, С.Н. Основы телетрафика мультисервисных сетей / С.Н. Степанов. - М.: Эко-трендз, 2010.

24. Шелухин, О.И. Фрактальные процессы в телекоммуникациях / О.И. Шелухин, A.M. Тенякшев, A.B. Осин. - М.: Радиотехника, 2003.

25. Яновский, Г.Г. Современные проблемы науки в области телекоммуникаций (Эволюция и конвергенция) / Г.Г. Яновский. - СПб: СПбГУТ им. МА Бонч-Бруевича, 2008.

26. Aberer, K. P-Grid: a self-organizing structured P2P system / K. Aberer, P. Cudré-Mauroux, A. Datta, Z. Despotovic, M. Hauswirth, M. Punceva, R. Schmidt // ACM SIGMOD Record. - 2003. - T. 32, № 3. _ c. 29-33.

27. Akella, A. An empirical evaluation of wide-area internet bottlenecks / A. Akella, S. Seshan, A. Shaikh // Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement. - ACM, 2003. - C. 101-114.

28. Albert, R. Statistical mechanics of complex networks / R. Albert, A.-L. Barabâsi // Reviews of modern physics. - 2002. - T. 74, № 1. - C. 47.

29. Andersen, D. Resilient overlay networks: T. 35 / D. Andersen, H. Balakrishnan, F. Kaashoek, R. Morris. - ACM, 2001.

30. Awduche, D. RFC 2702: Requirements for Traffic Engineering Over MPLS / D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, J. McManus // Internet Engineering Task Force (IETF).- 1999.

31. Awduche, D. Overview and principles of Internet traffic engineering / D. Awduche, A. Chiu, A. Elwalid, I. Widjaja, X. Xiao. - RFC 3272, may, 2002.

32. Awduche, D. MPLS and traffic engineering in IP networks / D.O. Awduche // Communications Magazine, IEEE. - 1999. - T. 37, № 12. - C. 42-^7.

33. Awduche, D. RSVP-TE: extensions to RS VP for LSP tunnels / D. Awduche, L. Berger, D. Gan, T. Li, V. Srinivasan, G. SwallowRFC 3209, December, 2001.

34. Bartels, R. The rank version of von Neumann's ratio test for randomness / R. Bartels // Journal of the American Statistical Association. - 1982. - T. 77, № 377. - C. 40-46.

35. Barthélémy, M. Spatial structure of the internet traffic / M. Barthélémy, B. Gondran, E. Guichard // Physica A: statistical mechanics and its applications. - 2003. - T. 319. -C. 633-642.

36. Baset, S.A. An analysis of the skype peer-to-peer internet telephony protocol / S.A. Baset, H. Schulzrinne // arXiv preprint cs/0412017. - 2004.

37. Ben-Ameur W. Routing strategies for IP networks / W. Ben-Ameur, N. Michel, B. Liau, E. Gourdin // Telektronikk. - 2001. - T. 97, № 2/3. - C. 145-158.

38. Benson, T. Network traffic characteristics of data centers in the wild / T. Benson, A. Akella, D.A. Maitz. - ACM, 2010. - C. 267-280.

39. Boutaba, R. DORA: Efficient routing for MPLS traffic engineering / R. Boutaba, W. Szeto, Y. Iraqi // Journal of Network and Systems Management. - 2002. - T. 10, № 3. -C. 309-325.

40. Boyle, J. Applicability statement for traffic engineering with MPLS / J. Boyle, V. Gill, A. Hannan, D. Cooper, D. Awduche, B. Christian, W.S. Lai. - RFC 3346, 2002.

41. Brownlee, N. Understanding Internet traffic streams: dragonflies and tortoises / N. Brownlee, K. Claffy // Communications Magazine, IEEE. - 2002. - T. 40, № 10. - C. 110-117.

42. Castro, M. SCRIBE: A large-scale and decentralized application-level multicast infrastructure / M. Castro, P. Druschel, A.-M. Kermarrec, A.I. Rowstron // Selected Areas in Communications, IEEE Journal on. - 2002. - T. 20, № 8. - C. 1489-1499.

43. Castro, M. SplitStream: high-bandwidth multicast in cooperative environments / M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, A. Singh: T. 37. -ACM, 2003.-C. 298-313.

44. Chen, Y. Machine-to-machine communications: Architectures, standards and applications / Y. Chen, J. Wan, F. Li - 2012.

45. Chun, B. Planetlab: an overlay testbed for broad-coverage services / B. Chun, D. Culler, T. Roscoe, A. Bavier, L. Peterson, M. Wawrzoniak, M. Bowman // ACM SIGCOMM Computer Communication Review. - 2003. - T. 33, № 3. - C. 3-12.

46. Cidon, I. Analysis of multi-path routing / I. Cidon, R. Rom, Y. Shavitt // IEEE/ACM Transactions on Networking (TON). - 1999. - T. 7, № 6. - C. 885-896.

47. Cisco visual networking index: Forecast and methodology, 2013-2018, Cisco systems, S. Jose, CA, Jun. 2014, www.cisco.com.

48. Clarke, I. Freenet: A distributed anonymous information storage and retrieval system /1. Clarke, O. Sandberg, B. Wiley, T.W. HongSpringer, 2001. - C. 46-66.

49. Clegg, R. A practical guide to measuring the Hurst parameter / R.G. Clegg // arXiv preprint math/0610756. - 2006.

50. Davie, B. MPLS: technology and applications / B. Davie, Y. Rekhter. - Morgan Kaufmann Publishers Inc., 2000.

51. Elwalid, A. MATE: MPLS adaptive traffic engineering / A. Elwalid, C. Jin, S. Low, I. Widjaja: T. 3. - IEEE, 2001. - C. 1300-1309.

52. Fildes, R. Generalising about univariate forecasting methods: further empirical evidence / R. Fildes, M. Hibon, S. Makridakis, N. Meade // International Journal of Forecasting. - 1998. - T. 14, № 3. - C. 339-358.

53. Ford, L.R. Flows in networks: T. 1962 / L.R. Ford, D.R. Fulkerson. - Princeton University Press, 1962.

54. Frost, V.S. Traffic modeling for telecommunications networks / V.S. Frost, B. Melamed // Communications Magazine, IEEE. - 1994. - T. 32, № 3. - C. 70-81.

55. Fuller, W.A. Introduction to statistical time series: T. 428 / W.A. Fuller. - John Wiley & Sons, 2009.

56. Gabrielyan, E. Reliable multi-path routing schemes for real-time streaming / E. Gabrielyan, R.D. Hersch. - IEEE, 2006. - C. 65-65.

57. Gabrielyan, E. Fault-Tolerant Streaming with FEC through Capillary Multi-Path Routing / E. Gabrielyan: T. 3. - IEEE, 2006. - C. 1497-1501.

58. Gallager, R.G. A minimum delay routing algorithm using distributed computation / R.G. Gallager // Communications, IEEE Transactions on. - 1977. - T. 25, № 1. - C. 73-85.

59. Garcia-Luna-Aceves, J.J. EIGRP-a fast routing protocol based on distance vectors / R. Albrightson, J.J. Garcia-Luna-Aceves, J. Boyle: T. 941994. - C. 136-147.

60. Garcia-Luna-Aceves, J.J. MPATH: a loop-free multipath routing algorithm / S. Vutukury, J.J. Garcia-Luna-Aceves // Microprocessors and Microsystems. - 2000. - T. 24, № 6.-C. 319-327.

61. Garcia-Luna-Aceves, J.J. MDVA: A distance-vector multipath routing protocol / S. Vutukury, J.J. Garcia-Luna-Aceves: T. 1. - IEEE, 2001. - C. 557-564.

62. Gardner Jr., E.S. Exponential smoothing: The state of the art-Part II / E.S. Gardner Jr. // International Journal of Forecasting. - 2006. - T. 22, № 4. - C. 637-666.

63. Gerber, A. Traffic types and growth in backbone networks / A. Gerber, R. Doverspike. - Optical Society of America, 2011.

64. Gojmerac, I. Adaptive multipath routing for dynamic traffic engineering / I. Gojmerac, T. Ziegler, F. Ricciato, P. Reichl: T. 6. - IEEE, 2003. --C. 3058-3062.

65. Grebennikov, A. A prediction method of network traffic using time series models / A. Grebennikov, Y. Krukov, D. Chernyagin. - 2011.

66. Guang, S. Network Traffic Prediction Based on The Wavelet Analysis and Hopfield Neural Network / S. Guang // International Journal of Future Computer and Communication. - 2013. - T. 2, № 2. - C. 101-105.

67. Hamra, A.A. Understanding the properties of the bittorrent overlay / A.A. Hamra, A. Legout, C. Barakat // arXiv preprint arXiv:0707.1820. - 2007.

68. Harvey, A. State space and unobserved component models / A. Harvey, S.J. Koopman, N. Shephard. - Cambridge University Press, Cambridge, UK, 2004.

69. He, J. Toward internet-wide multipath routing / J. He, J. Rexford // Network, IEEE. -2008. -T. 22, № 2. - C. 16-21.

70. Hopps, C.E. Analysis of an equal-cost multi-path algorithm / C.E. Hopps -2000.

71. Hu, N. A measurement study of internet bottlenecks / N. Hu, L. Li, Z.M. Mao, P. Steenkiste, J. Wang: T. 3IEEE, 2005. - C. 1689-1700.

72. ITU-T Recommendation M3010. Principles for a telecommunication management network. - 2000.

73. ITU-T Recommendation M.3020. TMN interface specification methodology. -2000.

74. ITU-T Recommendation M.3200. TMN management services and telecommunications managed areas: overview. - 1997.

75. ITU-T Recommendation M.3400. TMN management functions. - 2000.

76. Kalekar, P.S. Time series forecasting using Holt-Winters exponential smoothing / P.S. Kalekar // Kanwal Rekhi School of Information Technology. - 2004. - T. 4329008. -C. 1-13.

77. Kandula, S. Walking the tightrope: Responsive yet stable traffic engineering / S. Kandula, D. Katabi, B. Davie, A. Charny: T. 35. - ACM, 2005. - C. 253-264.

78. Katz, D. Traffic engineering (TE) extensions to OSPF version 2 / D. Katz, K. Kompella, D. Yeung. - RFC 3630, September, 2003.

79. Katz, D. Bidirectional forwarding detection / D. Katz, D. Ward - 2010.

80. Knoke, J.D. Testing for randomness against autocorrelation: Alternative tests / J.D. Knoke // Biometrika. - 1977. - T. 64, № 3. - C. 523-529.

81. Kompella, K. IS-IS Extensions in Support of Generalized Multi-Protocol Label Switching (GMPLS) / K. Kompella, Y. Rekhter - 2008.

82. Krioukov, D. On compact routing for the Internet / D. Krioukov, K. Fall, A. Brady, others // ACM SIGCOMM Computer Communication Review. - 2007. - T. 37, № 3. -C. 41-52.

83. Krishnamurthy B. Early measurements of a cluster-based architecture for P2P systems / B. Krishnamurthy, J. Wang, Y. Xie. - ACM, 2001. - C. 105-109.

84. Kubiatowicz, J. Oceanstore: An architecture for global-scale persistent storage / J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, others // ACM Sigplan Notices. - 2000. - T. 35, № 11.-C. 190-201.

85. Labovitz, C. Delayed Internet routing convergence / C. Labovitz, A. Ahuja, A. Bose, F. Jahanian // ACM SIGCOMM Computer Communication Review. - 2000. - T. 30, № 4. - C. 175-187.

86. Lakhina, A. Structural analysis of network traffic flows: T. 32 / A. Lakhina, K. Papagiannaki, M. Crovella, C. Diot, E.D. Kolaczyk, N. Taft. - ACM, 2004.

87. Lee, G. A survey of multipath routing for traffic engineering / G. Lee, J. Choi // Information and Communications University, Korea. - 2002.

88. Li, B. An empirical study of the coolstreaming+ system / B. Li, S. Xie, G.Y. Keung, J. Liu, I. Stoica, H. Zhang, X. Zhang // Selected Areas in Communications, IEEE Journal on. - 2007. - T. 25, № 9. - C. 1627-1639.

89. Liang, J. The FastTrack overlay: A measurement study / J. Liang, R. Kumar, K.W. Ross // Computer Networks. - 2006. - T. 50, № 6. - C. 842-858.

90. Lichtwald, G. Improving convergence time of routing protocols / G. Lichtwald, U. Walter, M. Zitterbart. - 2004. - C. 640-647.

91. Lin, D. Dynamics of random early detection / D. Lin, R. Morris // ACM SIGCOMM Computer Communication Review: T. 27ACM, 1997. — C. 127-137.

92. Lua, E.K. A survey and comparison of peer-to-peer overlay network schemes. / E.K. Lua, J. Crowcroft, M. Pias, R. Sharma, S. Lim, others // IEEE Communications Surveys and Tutorials. - 2005. - T. 7, № 1-4. - C. 72-93.

93. Makhoul, J. Linear prediction: A tutorial review / J. Makhoul // Proceedings of the IEEE. - 1975. - T. 63, № 4. - C. 561-580.

94. Malkhi, D. Viceroy: A scalable and dynamic emulation of the butterfly / D. Malkhi, M. Naor, D. Ratajczak. - ACM, 2002. - C. 183-192.

95. Malkin, G. RFC 2453: Rip version 2 / G. Malkin // RFC. - 1998. - T. 2453.

96. Maymounkov, P. Kademlia: A peer-to-peer information system based on the XOR metric / P. Maymounkov, D. Mazieres // Peer-to-Peer Systems. - Springer, 2002. - C. 53-65.

97. McCoy, D. Shining light in dark places: Understanding the Tor network / D. McCoy, K. Bauer, D. Grunwald, T. Kohno, D. Sicker. - Springer, 2008. - C. 63-76.

98. McKeown, N. Software-defined networking / N. McKeown // INFOCOM keynote talk. - 2009.

99. Medhi, D. Network routing: algorithms, protocols, and architectures / D. Medhi. -Morgan Kaufmann, 2010.

100. Mendonca, M. A Survey of software-defined networking: past, present, and future of programmable networks / M. Mendonca, B.A.A. Nunes, X.-N. Nguyen, K. Obraczka, T. Turletti // hal-00825087. - 2013.

101. Mérindol, P. Improving load balancing with multipath routing / P. Mérindol, J.-J. Pansiot, S. Cateloin. - IEEE, 2008. - C. 1-8.

102. Moy, J. OSPF Version 2, RFC 2328 / J. Moy, others // Ascend Communications Inc.-1998.

103. Nehra, N. Load balancing in heterogeneous P2P systems using mobile agents / N. Nehra, R.B. Patel, V.K. Bhat // International Journal of Applied Science, Engineering and Technology. - 2006. - T. 2, № 3. - C. 108-113.

104. Oran, D. OSI IS-IS Intra-domain Routing Protocol (RFC 1142) / D. Oran // Digital Equipment Corp. - 1990.

105. Palakurthi, H.S. Study of multipath routing for QoS provisioning / H.S. Palakurthi // EECS. - 2001.

106. Pioro, M.. Routing, flow, and capacity design in communication and computer networks / M. Pioro, D. Medhi // Elsevier - 2004. - 765 c.

107. Postel, J. RFC 791: Internet protocol / J. Postel -1981.

108. Psenak, P. Multi-topology (MT) routing in OSPF / P. Psenak, S. Mirtorabi, A. Roy, L. Nguyen, P. Pillay-Esnault. - RFC 4915, June, 2007.

109. Ratnasamy S. A Scalable Content-Addressable Network / S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker- 2001.

110. Rekhter, Y. RFC 4271: Border gateway protocol 4 / Y. Rekhter, T. Li, S. Hares. -Technical report, IBM, Cisco Systems, 2006.

111. Ripeanu, M. Peer-to-peer architecture case study: Gnutella network / M. Ripeanu. -IEEE, 2001.-C. 99-100.

112. Rosen E. RFC 4364 BGP / E. Rosen, Y. Rekhter // MPLS IP Virtual Private Networks (VPNs), IETF February. - 2006.

113. Rowstron, A. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems / A. Rowstron, P. Druschel. - Springer, 2001. - C. 329-350.

114. Rutka, G. Network Traffic Prediction using ARIMA and Neural Networks Models / G. Rutka // Electronics and Electrical Engineering. - 2008. - T. 4. - C. 47-52.

115. Savage, S. The end-to-end effects of Internet path selection / S. Savage, A. Collins, E. Hoffman, J. Snell, T. Anderson: T. 29. - ACM, 1999. - C. 289-299.

116. Schollmeier, G. Improving the resilience in IP networks / G. Schollmeier, J. Charzinski, A. Kirstadter, C. Reichert, K.J. Schrodi, Y. Glickman, C. Winkler. - IEEE, 2003.-C. 91-96.

117. Semenov, Y. The Distributed Service Network architecture approach for Russian networks planning / Y. Semenov, V. Pyattaev, C. Chung. - IEEE, 2012. - C. 611-614.

118. Shen, X. Handbook of peer-to-peer networking: T. 1 / X. Shen, H. Yu, J. Buford, M. Akon. - Springer, 2010.

119. Shields, C. A protocol for anonymous communication over the Internet / C. Shields, B.N. Levine. - ACM, 2000. - C. 33-42.

120. Shu, Y. Traffic prediction using FARIMA models / Y. Shu, Z. Jin, L. Zhang, L. Wang, O.W. Yang: T. 2. - IEEE, 1999. - C. 891-895.

121. Sorensen, L.T. User scenarios 2020: a worldwide wireless future / L.T. Sorensen, K.E. Skouby, D. Dietterle, A. Jhunjhunwala, X. Fu, X. Wang // WWRF Outlook. -2009. - № 4.

122. Srinivasan, C. Multiprotocol label switching (MPLS) traffic engineering (TE) management information base (MIB) / C. Srinivasan, A. Viswanathan, T. Nadeau // Internet Engineering Task Force, RFC. - 2004. - T. 3812.

123. Stoica, I. Chord: A scalable peer-to-peer lookup service for internet applications / I. Stoica, R. Morris, D. Karger, M.F. Kaashoek, H. Balakrishnan // ACM SIGCOMM Computer Communication Review. - 2001. - T. 31, № 4. - C. 149-160.

124. Tarkoma, S. Overlay Networks: Toward Information Networking. / S. Tarkoma. - Auerbach Publications, 2010.

125. Taylor, J.W. Smooth transition exponential smoothing / J.W. Taylor // Journal of Forecasting. - 2004. - T. 23, № 6. - C. 385-404.

126. Thaler, D. Multipath issues in unicast and multicast next-hop selection / D. Thaler, C. Hopps. - RFC 2991, November, 2000.

127. Trotter, G. Terminology for Forwarding Information Base (FIB) based Router Performance / G. Trotter - 2001.

128. Tuncer, D. Towards decentralized and adaptive network resource management / D. Tuncer, M. Charalambides, G. Pavlou, N. Wang. - IEEE, 2011. - C. 1-6.

129. Tune, P. Internet traffic matrices: A primer / P. Tune, M. Roughan // Recent Advances in Networking. - 2013. - T. 1.

130. Villamizar, C. Ospf optimized multipath (ospf-omp) / C. Villamizar // Work in Progress. - 1999.

131. Vutukury, S. A traffic engineering approach based on minimum-delay routing / S. Vutukury, J.J. Garcia-Luna-Aceves. - IEEE, 2000. - C. 42-47.

132. Waldner, J.-B. Nanocomputers and swarm intelligence: T. 12 / J.-B. Waldner. -John Wiley & Sons, 2010.

133. Wang, C. Peer-to-peer overlay networks: A survey / C. Wang, B. Li // Department of Computer Science, The Hong Kong University of Science and Technology.-2003.

134. Wang, N. An overview of routing optimization for internet traffic engineering / N. Wang, K. Ho, G. Pavlou, M. Howarth // Communications Surveys & Tutorials, IEEE. - 2008. - T. 10, № 1. - C. 36-56.

135. Wang, Z. Analysis of shortest-path routing algorithms in a dynamic network environment / Z. Wang, J. Crowcrofit // ACM SIGCOMM Computer Communication Review. - 1992. -T. 22, № 2. - C. 63-71.

136. Xue, F. Modeling and predicting long-range dependent traffic with FARIMA processes / F. Xue, T.T. Lee. - 1999.

137. Yasukawa, S. An analysis of scaling issues in MPLS-TE core networks / S. Yasukawa, A. Farrel, others - 2009.

138. Zantout, B. I2P data communication system / B. Zantout, R. Haraty. - 2011. - C. 401-409.

139. Zhang, Y. Understanding the End-to-End Performance Impact of RED in a Heterogeneous Environment / Y. Zhang, L. Qiu. - Cornell University, 2000.

140. Zhao, B.Y. Brocade: Landmark routing on overlay networks / B.Y. Zhao, Y. Duan, L. Huang, A.D. Joseph, J.D. Kubiatowicz // Peer-to-Peer Systems. - Springer, 2002.-C. 34-44.

141. Zhao, B.Y. Tapestry: A resilient global-scale overlay for service deployment / B.Y. Zhao, L. Huang, J. Stribling, S.C. Rhea, A.D. Joseph, J.D. Kubiatowicz // Selected Areas in Communications, IEEE Journal on. - 2004. - T. 22, № 1. - C. 41-53.

Приложение А. Временные ряды образцов реального сетевого трафика

Графики временных рядов интенсивности реального сетевого трафика, использовавшихся для оценки эффективности методов краткосрочного предсказания (см. главу 3).

;е7 Интенсивность трафика (файл "5атр1еяЛгасе 4 ')

100 150

Время сек

100 <50

Время сек

Интенсивность трафика (файл "5атр^/№асе-5")

100 150

Время, сек

Интенсивность трафика (файл "аатр^Лгасоб")

100 150

Нр«.мя сек

100 150

Время, сек

Интенсивность трафика, бай г'сек

ё

Интенсивность трафика, баиг/сек

Приложение Б. Программный код симулятора

#!/usr/bin/python # -*- coding: utf-8 -*-

from _future_ import division

import csv, sys

import numpy as np

import cPickle as pkl

import matplotlib.pyplot as pit

from scipy import interpolate

from scipy.optimize import fmin_tnc

font = {'family': 'Times New Roman', 'weight': 'normal', 'size': '14.0' pit.rc('font', **font) class Node(object) :

"""Class defines LBO-nodes"""

def _init_(self, network, num_nodes, node_id, b_thresh):

# Link to the network object containing current node self.network = network

# Current node ID self.node_id = node_id

# Total number of nodes in overlay self.num_nodes = num_nodes

# Neighbour links bandwidths - !¡Currently unused!!

# self.band_capacity = np.zeros(num_nodes)

# Neighbour links capacity threshold values self.band_threshold = b_thresh

# Node activity flag self.isActive = 1

self.nodes_activity = np.ones(num_nodes)

# Traffic loads

# Intensity of received incoming traffic self.load_IN_recv_p = np.zeros(num_nodes) self. load_IN__recv_np = np. zeros (num_nodes)

# Acceptable current incoming traffic load self.load_IN_max_p = np.zeros(num_nodes) self. load_IN__max_np = np.zeros(num_nodes) self. load__IN__max_p = self. band_threshold

# Incoming traffic load passed into node self.load_IN_passed_p = np.zeros(num_nodes) self.load_IN_passed_np = np.zeros(num_nodes)

# Intensity of dropped incoming traffic self. load_IN__dropped_p = np. zeros (num_nodes) self.load_IN_dropped_np = np.zeros(num_nodes) self.load_OUT_p = np.zeros(num_nodes)

self.load_OUT_np = np.zeros([num_nodes, num_nodes])

# Load averaged by update period self.load_IN_recv_p_averaged = []

# Theoretically calculated values (ideal case) self.load_IN_passed_p_theor = np.zeros(num_nodes) self.load_IN_passed_np_theor = np.zeros(num_nodes) self. load_IN_dropped_p_theor = np. zeros (num_nodes) self.load_IN_dropped_np_theor = np. zeros (num__nodes)

# Loads in similar mesh-network (used for statistics) self. load_IN__passed_p_mesh = np. zeros (num_nodes) self.load_IN_passed_np_mesh = np.zeros(num__nodes) self.load_IN_dropped_p_mesh = np.zeros(num_nodes) self.load_IN_dropped_np_mesh = np.zeros(num_nodes)

# Flows

# Total number of nonpriority incoming traffic flows (on current node) self.flow_IN_np = np.zeros(num_nodes)

# Expactation of single nonpriority traffic flow intensity self.flow_np_intensity_expected = np.zeros(num_nodes) self.flow_OUT_rough = np.zeros([num_nodes, num_nodes]) self.flow_OUT_precise = np.zeros([num_nodes, num_nodes])

# Number of flows to be remapped. Finalized precise estimation self.fl ow OUT change — np.zeros([num nodes, num nodes])

# Flow control parameters

# Parameters for oscillation avoidance procedure self.flow_OA_parameter_a_abs = 20

self.flow_OA_parameter_b_abs = 30 self.flow_OA_parameter_a_rel = 0.1 self.flow_OA_parameter_b_rel = 0.2 self.flow_0A_num_flow_threshold = 50 self. f low_OA_num_flow_threshold__sum = 80

# Forecasts parameters

self.load_IN_recv_p_forecast = np.zeros(num_nodes)

self.load_IN_recv_p_predicted = []

self.alpha_vector = np.repeat(0.2, num_nodes)

# Channel resources

# Matrix of residual channel resources

self.chan_resource = np.zeros([num_nodes, num_nodes])

def expSmoothing(self, alpha, x_current, s_previous): '''N-N model, used for forecasts'''

s_current = alpha * x_current + (1 - alpha) * s_previous return s_current

def squaredError(self, alpha, x_current, x_previous, predicted): sse = 0; data_length = len(x_current)

assert(data_length == len(x_previous) == len(predicted)) for i in xrange(data_length):

sse += pow((x_current[i] - self.expSmoothing(alpha, x_previous[i], predicted[i])), 2)

return sse / data_length

def forecast(self, time_pointer, update_cycle_number, optimizeAlpha, useActual=False) :

'''Forecasting incoming traffic loads for the next period''1

# Average incoming priority traffic intensity for previous period if update_cycle_number != 0:

self.load_IN_recv_p_averaged.append(np.mean(self.network.currentLoad(self.no de_id, slice(time_pointer - self.network.update_period, time_pointer))[0], axis=0))

else:

self.load_IN_recv_p_averaged.append(self.network.currentLoad(self.node_id,

0) [0] )

# Alpha vector optimization procedure if optimizeAlpha and time_pointer != 0:

# Boundaries for alpha value bounds = [(0, 1)] for i in xrange(self.num_nodes): if i != self.node_id:

if update_cycle_number <= self.network.forecast_parameter_optimization_interval:

av_t_start = 1

else:

av__t_start = update_cycle_number -self.network.forecast_parameter_optimization_interval

# Data for optimization x_current =

np.matrix(self.load_IN_recv_p_averaged[slice(av_t_start, update_cycle_number+l)])[:,i]

x_previous =

np.matrix(self.load__IN_recv_p_averaged [slice(av_t_start-l, update_cycle_number)])[:,i]

predicted =

np.matrix(self.load_IN_recv_p_predicted[slice(av_t_start-l, update_cycle_number)]) [:, i]

# Alpha parameter optimization

self.alpha_vector[i] = fmin_tnc{self.squaredError, self.alpha_vector[i], bounds=bounds, approx_grad=True, args=(x_current, x_previous, predicted), xtol=0.001, disp=0)[0]

# Forecasting procedure if useActual:

for i in xrange(self.num_nodes):

self. load__IN_recv_p_forecast [i] = np.mean(self.network.currentLoad(self.node_id, slice(time_pointer, time_pointer+self.network.update_period)) [0] [:,i]) else:

# Make forecast if update__cycle_number == 0:

# At first time use measured current values for i in xrange(self,num_nodes):

if i ! = self.node_id:

self.load_IN_recv_p_forecast[i] = self.network.currentLoad{self.node_id, time_pointer)[0][i]

else:

# After that - predict traffic for i in xrange(self.num_nodes):

if i != self.node_id:

self.load_IN_recv_p_forecast[i] = self.expSmoothing(self.alpha_vector[i], self.load_IN_recv_p_averaged[-1][i], self.load_IN_recv_p_forecast[i])

# Save current forecast

self. load_IN__recv__p_predicted. append (self. load_IN_recv_p_forecast)

def chanResource(self):

''' Calculate residual channel resources ' ' ' for i in xrange(self.num_nodes): if i != self.node_id:

# Filtering function if res < 0:

res = 0

self.chan_resource[self.node_id, i] = res

def getLoad(self, time_pointer):

'1'Method sets array of current priority and nonpriority incoming traffic loads'''

self. load_IN_recv__p, self.load_IN_recv_np = self.network.currentLoad(self.node_id, time_pointer)

def getFlow(self, time_pointer):

'11 Method sets array of current numbers of nonpriority incoming traffic flows''1

aq = "Contact author, pis!"

return aq

def shapeLoad(self):

'''Calculates current passed and dropped traffic loads for priority and nonpriority traffic11'

if self.isActive:

self.load_IN_max_p = self.band_threshold for i in xrange(self.num_nodes): if i != self.node_id:

# Incoming traffic load passed into node self.load_IN_passed_p[i] =

min(self.load_IN_recv_p[i] , self.load_IN_max_p[i])

self.load_IN_passed_np[i] = self. load__IN_max_np [i] )

# Incoming traffic load dropped

self.load_IN_dropped_p[i] = self.load_IN_recv_p[i] self.load_IN_dropped_np[i] = self.load_IN_recv_np[

# Similar mesh-network self.load_IN_passed_p_mesh[i] =

min (self. load__IN_recv_p [i] , self . band_threshold [i] )

self.load_IN_dropped_p_mesh[i] = self. load_IN_recv_p [i] - self. load__IN_passed__p_mesh [i]

self.load_IN_dropped_np_mesh[i] = self. load_IN_recv__np [i] - self.load_IN_passed_np_mesh[i]

# Expectation of single nonpriority traffic flow

intensity

if self.flow_IN_np[i] != 0:

self.flow_np_intensity_expected[i] = self.load_IN_passed_np[i] / self.flow_IN_np[i]

else:

self.flow_np_intensity_expected[i] = 0

min(self.load_IN_recv_np[i] ,

self.load_IN_passed_p[i] - self. load_IN_passed__np [i]

else:

self.load_IN_max_p = np.zeros(self.num_nodes) self.load_IN_passed_p = np.zeros(self,num_nodes) self.load_IN_passed_np = np.zeros(self.num_nodes) self.load_IN_passed_p_mesh = np.zeros(self.num_nodes) self.load_IN_passed_np_mesh = np.zeros(self.num_nodes) self.load_IN_dropped_p_mesh = self.load_IN_recv_p self.load_IN_dropped_np_mesh = self.load_IN_recv_np

def getUpdate(self):

'''Get whole network channel resources forecasts and nodes activity

mask'''

self.chan_resource = self.network.sendUpdates()

def sendUpdate(self):

'''Send channel resources forecast to virtual centralized storage + current node activity'''

if self.isActive:

# Send calculated channel resources forecast self.network.getUpdates(self.node_id,

self.chan_resource[self.node_id], self.isActive) else:

# Send zero-vector

self.network.getUpdates(self.node_id, np.zero(self.num_nodes),

self.isActive)

def nodeStat(self, statobject, time_pointer):

statdata = diet(passed_p_LBO=self.load_IN_passed_p, passed_np_LBO=self.load_IN_passed_np, dropped_p_LBO=self.load_IN_dropped_p, dropped_np_LBO=self.load_IN_dropped_np, \ passed_p_LBO_theor=self.load_IN_passed_p_theor, passed_np_LBO_theor=self.load_IN_passed_np_theor, dropped_p_LBO_theor=self.load_IN_dropped_p_theor, dropped_np_LBO_theor=self.load_IN_dropped_np_theor, \ passed_p_mesh=self.load_IN_passed_p_mesh, passed_np_mesh=self.load_IN_passed_np_mesh, dropped_p_mesh=self.load_IN_dropped_jp_mesh, dropped_np_mesh=self.load_IN_dropped_np_mesh, \ flow_IN=self.flow_IN_np, flow_OUT=self.flow_OUT_precise, flow_change=self.flow_OUT_change,

flow_expect=self.flow_np_intensity_expected, bw=self.band_threshold, \ alpha_vector=self.alpha_vector, recv_p_forecast=self.load_IN_recv_p_forecast, recv_p_averaged=self.load_IN_recv_p_averaged[-1])

# Send current node statistics into global statistics storage statobject.getNodeStat(self.node_id, time_pointer, **statdata)

def flowControl(self):

'1' Managing currently appeared and vanished flows ''1

# Skip offline nodes if self.isActive:

for j in xrange(self.num_nodes): if j != self,node_id:

# Load distribution parts for current direction (to

j-th node)

flow_OUT_part = self.flow_OUT_precise[j] / np.sum(self.flow_OUT_precise[j])

# Round-robin for probabilistic path selection round_robin = np.cumsum(flow_OUT_part)

# Number of incoming flows alteration flow_diff = self.flow_IN_np[j] -

np. sum(self. flow__OUT_precise [ j ] )

if flow_diff == 0:

# No changes in number of flows pass

elif flow_diff > 0:

# Some new flows appeared

res = [np.searchsorted(round_robin, i) for i in np.random.uniform(0.0, 1.0, abs(flow_diff))]

for i in res:

# Check "out of bounds" if i >= self.num_nodes:

i = self.num_nodes - 1 self.flow_OUT_precise[j, i] += 1 elif flow_diff < 0:

# Some flows vanished

res = [np.searchsorted(round_robin, i) for i in np.random.uniform(0.0, 1.0, abs(flow_diff))]

for i in res:

# Check "out of bounds" if i >= self.num_nodes:

i = self.num nodes - 1

# Check for empty paths

if self.flow_OUT_precise[j, i] ==0:

# Flow vanished from the most

loaded path

self.flow_OUT_precise[np.argmax(self.flow_OUT_precise[j])] -= 1

else:

self.flow_OUT_precise[j, i] -= 1

else:

print "FlowControl operation error on node:

{}".format(self.node_id)

exit(1)

def loadBalance(self):

1 ' ' Calculate nonpriority traffic load distribution ' ' 1

# Fill priority traffic distribution vector

# (no priority traffic flows distribution) self.load_OUT_p = self.load_IN_passed_p

# Fill nonpriority traffic distribution table for j in xrange(self.num_nodes):

if j != self.node_id:

# Clear accumulators f_res_alt_sum, extra_load =0, 0

# Maximum nonpriority traffic load through current node self.load_IN_max_np[j] = self.chan_resource[self.node_id,

j] / 2 + f_res_alt_sum

# Shortest path

extra__load = self. load_IN_passed_np [ j ] -self.chan_resource[self.node_id, j] /2

if extra_load < 0:

self.load_OUT_np[j , j] = self.load_IN_passed_np[j]

else:

self.load_OUT_np[j , j] = self.chan_resource[self.node_id, j] /2

# Roundabout paths

for k in xrange(self.num_nodes):

if k != self.node_id and k != j: if extra_load > 0:

self.load_OUT_np[j, k] = extra_load * min(self.chan_resource[self.node_id, k] / 2, self.chan_resource[k, j] / (2 * self. num_nodes - 4)) / f_res_alt__sum

else:

self.load_OUT_np[j, k] = 0

def flowMap(self) :

' ' 1 Calculate nonpriority traffic flows distribution ' '' for j in xrange(self.num_nodes): if j != self.node_id:

for k in xrange(self.num_nodes): if k != self.node_id:

self.flow_OUT_rough[j, k] = round(self.flow_IN_np[j] * self.load_OUT_np[j , k] / self.load_IN_passed_np[j])

def oscillationAvoidance(self):

''' Procedure of path oscillation avoidance for nonpriority traffic

flows '''

# Clear array with flow changes

self.flow_OUT_change = np.zeros([self.num_nodes, self.num_nodes])

# Oscillation avoidance

for j in xrange(self.num_nodes): if j != self.node_id:

# Check if there is a summary change if np.sum(self.flow_OUT_precise[j]) <

self.flow_OA_num_flow_threshold_sum:

# Absolute approach (for small number of flows)

if abs(np.sum(self.flow_OUT_rough[3]) -np.sum(self.flow_OUT_precise[3])) > self.flow_OA_parameter_b_abs:

# Remap flows and calculate flow changes self.flow_OUT_change[3] =

self.flow_OUT_rough[3] - self.flow_OUT_precise[3]

self. flow_OUT_preci.se [3 ] =

self.flow_OUT_rough[3 ]

continue

else:

# Relative change (for high amount of flows) if abs(np.sum(self.flow_OUT_rough[3]) / np.sum(self.flow_OUT_precise[3]) - 1) > self.flow_OA_parameter_b_rel:

# Remap flows and calculate flow changes self.flow_OUT_change[3] =

self.flow_OUT_rough[3 ] - self. f low_OUT_jpreci.se [3 ]

self.flow_OUT_precise[3] =

self.flow_OUT_rough[3 ]

continue

# Check if there is a single change for k m xrange(self.num_nodes): if k '= self.node_id:

if self.flow_OUT_precise[3, k] <

self.flow_OA_num_flow_threshold:

# Absolute approach (for small number o

flows)

if abs (self . f low_OUT__rough [3 , k] -self.flow_OUT_precise[3, k]) > self.flow_OA_parameter_a_abs:

# Remap flows and calculate flow

changes

self.flow_OUT_change[3] = self.flow_OUT_rough[3] - self.flow_OUT_precise[3]

self.flow_OUT_precise[3] =

self.flow_OUT_rough[3 ]

break

else:

# Relative change (for high amount of

flows)

if abs(self.flow_0UT_rough[3, k] / self.flow_OUT_precise[3 , k] - 1) > self.flow_OA__parameter_a_rel:

# Remap flows and calculate flow

changes

self.flow_OUT_change[3] = self.flow_OUT_rough[3] - self.flow_OUT_precise[3]

self.flow_OUT_precise[3] =

self.flow_OUT_rough[3]

break

def mitializeNodeState(self):

''' Set some initial node's parameters ''' self.getLoad(O) self.getFlow(O)