Содержание к диссертации
Введение
ГЛАВА 1. Анализ методов балансировки сетевого трафика ... 12
1.1. Анализ свойств трафика и его влияния на состояние современных пакетных сетей связи 12
1.2. Механизмы балансировки сетевого трафика 19
1.3. Наложенные сети 25
1.3.1. Самоорганизующиеся наложенные сети 27
1.3.2. Методы балансировки трафика на основе наложенных сетей 32
1.4. Цель и задачи исследования 34
Выводы по главе 1 36
ГЛАВА 2. Разработка метода балансировки трафика на основе наложенной сети 37
2.1. Механизм наложенной балансировочной сети 39
2.2. Построение наложенной балансировочной сети 40
2.2.1. Управление наложенной сетью 40
2.2.2. Контроль состояния наложенной балансировочной сети 44
2.2.3. Балансировка транзитного трафика 45
2.2.4. Отказоустойчивость наложенной балансировочной сети 50
2.3. Модель оценки возможностей наложенной балансировочной сети 52
2.3.1. Стратегия балансировки трафика 52
2.3.2. Параметры наложенной балансировочной сети 55
2.3.3. Свойства полносвязного графа 57
2.4. Балансировка трафика наложенной сетью 58
2.4.1. Контроль входящей нагрузки 58
2.4.2. Оценка эффективности передачи трафика наложенной балансировочной сетью 62
2.4.3. Распределение нагрузки в наложенной балансировочной сети 64
2.4.4. Распределение потоков в наложенной балансировочной сети. 66
2.4.5. Механизм сглаживания осцилляций маршрутов 69
Выводы по главе 2 73
ГЛАВА 3. Анализ методов краткосрочного прогнозирования сетевого трафика 74
3.1. Задача краткосрочного прогнозирования временных рядов 74
3.2. Автоматизированные методы краткосрочного прогнозирования временных рядов 76
3.2.1. Основные модели краткосрочного прогнозирования 76
3.2.2. Постановка задачи определения эффективности методов краткосрочного прогнозирования 82
3.3. Статистический анализ временных рядов интенсивности сетевого трафика 84
3.4. Анализ эффективности автоматизированных методов краткосрочного прогнозирования 88
3.4.1. Экспериментальная оценка точности прогнозирования 88
3.4.2. Результаты экспериментальной оценки эффективности методов краткосрочного прогнозирования для предсказания интенсивности сетевого трафика 100
Выводы по главе 3 101
ГЛАВА 4. Исследование работы наложенной балансировочной сети 102
4.1. Разработка симулятора наложенной балансировочной сети 102
4.1.1. Процесс моделирования работы наложенной балансировочной сети 102
4.1.2. Визуализация результатов моделирования 106
4.2. Исследование работы наложенной балансировочной сети в условиях статических нагрузок 107
4.2.1. Исследование влияния количества узлов в балансировочном оверлее на эффективность передачи трафика 108
4.2.2. Исследование эффективности работы балансировочной сети в условиях реальных статических нагрузок 110
4.3. Исследование работы наложенной балансировочной сети в условиях динамических нагрузок 114
4.3.1. Исследование поведения наложенной балансировочной сети в условиях медленно меняющейся нагрузки 115
4.3.2. Исследование поведения наложенной балансировочной сети при взрывном характере нагрузки 118
4.4. Исследование влияния внутренних параметров на работу наложенной балансировочной сети 124
4.4.1. Исследование влияния длительности интервала обмена сообщениями UPDATE на функционирование сети LBO 125
4.4.2. Исследование влияния чувствительности процедуры исключения осцилляций на работу сети LBO 128
4.4.3. Исследование влияния ошибок, вносимых прогнозированием 130
Выводы по главе 4 133
Заключение 134
Список сокращений и условных обозначений 136
Список литературы .
- Механизмы балансировки сетевого трафика
- Контроль состояния наложенной балансировочной сети
- Автоматизированные методы краткосрочного прогнозирования временных рядов
- Исследование работы наложенной балансировочной сети в условиях статических нагрузок
Механизмы балансировки сетевого трафика
Отмеченные тенденции в изменении состава глобального трафика делают такие эффекты все более ощутимыми для транспортной инфраструктуры сети, что в совокупности с экспоненциальным ростом объемов передаваемого трафика приводит к необходимости переосмысления старых подходов к построению сетей.
Как известно, традиционные протоколы маршрутизации выбирают путь прохождения данных по сети, оптимальный с точки зрения минимизации выбранной метрики. Такой подход позволяет передавать трафик наилучшим образом с точки зрения количества пройденных сетевых узлов, доступной полосы пропускания, задержек и т.п. Однако ему присущи определенные недостатки. Многие исследователи [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 до 54% у провайдеров Tier-4.
На данный момент доминирующим является эмпирический подход, предполагающий экстенсивное наращивание пропускных способностей. Методики, используемые в настоящее время для расчета требуемой пропускной способности канала на уровне агрегации, основываются на статистических профилях трафика, причем для обеспечения должного качества обслуживания в условиях фрактальных эффектов пакетного трафика [12,22,23] вводится эмпирический понижающий коэффициент («0,3), предполагающий работу на недогруженных каналах [21]. Высоконагруженные и критичные участки сетей могут иметь избыточность, значительно превышающую указанную цифру. Так результаты исследования [38] позволяют утверждать, что при существующих методиках планирования сети, использование пропускной способности внутренних каналов современного центра обработки данных при самом худшем сценарии не превысит 25%, тогда как загрузка каналов реальным трафиком в среднем не будет превышать 5%. Оценки создаваемых нагрузок с помощью традиционных методик характерны для расчета сетей, генерирующих предсказуемый агрегированный трафик. Такой трафик может успешно описываться с помощью статистических профилей (суточных, недельных), отклонения от которых незначительны. С учетом отмеченной растущей нестационарности пользовательского трафика подобный подход дат неудовлетворительные результаты, заставляющие искать выход в области применения механизмов динамического управления сетями связи.
Контроль состояния наложенной балансировочной сети
Каждый узел получает уникальный идентификатор, однозначно указывающий на его место в сети относительно других узлов. Жесткая структура позволяет гарантировать нахождение конкретного узла по его идентификатору, при этом сложность поиска растет, как правило, не быстрее логарифма количества узлов в сети. Размер таблиц маршрутизации узлов структурированной сети чаще всего также пропорционален логарифму общего числа участников [10]. Следует отметить, что структурированные сети в силу особенностей архитектуры сильнее подвержены влиянию динамики популяции узлов. Отключение действующего узла или подключение нового вызывает выполнение ряда процедур, затрагивающих некоторую часть узлов сети и связанных с перестроением таблиц маршрутизации. Данный факт несколько ограничивает применение структурированных архитектур в условиях высокой динамики популяции [118]. Примерами структурированных сетей являются протоколы CAN [109], Chord [123], Tapestry [141], Pastry [113], Kademlia [96], Viceroy [94], распределенная система хранения данных OceanStore [84], исследовательский комплекс PlanetLab [45], масштабируемые многоадресные CDN-системы SplitStream [43], Scribe [42] и многие другие. Помимо рассмотренных типов организации сетей существуют также гибридные варианты, совмещающие подходы структурированных и неструктурированных архитектур. Примером такой слабоструктурированной сети является сеть Freenet [48], поиск узла в которой осуществляется способом, близким к методу случайных блужданий, однако направление поиска задается близостью идентификаторов соседних узлов к искомому.
В отдельную группу самоорганизующихся наложенных сетей следует выделить анонимные сети [118]. Рассматривая такие сети с точки зрения генерируемого ими трафика можно выделить следующую особенность, отличающую их от всех других наложенных сетей: для повышения безопасности анонимные сети намеренно выбирают субоптимальные маршруты при передаче данных [11]. Это означает, что некоторый узел после нахождения требуемого ресурса, обменивается данными с последним через цепочку других узлов наложенной сети, при этом путь прохождения таких данных с точки зрения физической сети является неоптимальным. Важно подчеркнуть данный подход, как иллюстрирующий возможности организации произвольной схемы маршрутизации трафика на базе наложенной сети. Примерами самоорганизующихся анонимных сетей являются Freenet [48], Hordes [119], TOR [97], I2P [138] и другие.
Степень централизации. Как уже было отмечено выше, самоорганизующиеся сети могут отличаться различной степенью централизации управления. Можно выделить три группы: централизованные, сети с частичной централизацией и полностью децентрализованные сети. Архитектура централизованной сети содержит набор серверов, обеспечивающих поиск данных в сети, а также хранящих адреса узлов-участников. Все запросы узлов обрабатываются на центральных серверах, после чего узел-инициатор получает информацию об искомых данных и адреса узлов, готовых их представить. Такая схема является наиболее простой в реализации, эффективной с точки зрения поиска ресурсов и объемов служебного трафика. Однако в то же время степень самоорганизации сети значительно снижается за счет присутствия центральных элементов, являющихся потенциальными точками отказа. Примером типичной централизованных сетей является Napster [118].
Полностью децентрализованные сети лишены недостатков, связанных с возможностью потери работоспособности в результате отказа некоторых узлов. Информация об участниках децентрализованного оверлея, данные, а также сетевой функционал распределены по всем узлам, так что отключение части узлов не отразится на работе сети, при этом наибольшей отказоустойчивостью обладают неструктурированные децентрализованные сети [118]. В качестве примеров полностью децентрализованных сетей можно указать Gnutella, FastTrack, P-Grid [26] и другие.
Комбинированное решение, представляющее собой децентрализованный оверлей, содержащий ряд элементов централизации (вспомогательных серверов), получило название частично децентрализованной архитектуры. Такие сети обладают не только высокой отказоустойчивостью, но также позволяют производить быстрый и эффективный поиск узлов и данных с помощью группы центральных серверов, обменивающихся актуальной информацией. Примерами частично децентрализованных сетей являются Overnet/eDonkey [92], BitTorrent, а также (до недавних пор) P2P-VoIP система Skype.
Топология сети. Топология самоорганизующейся сети может быть либо одноранговой (плоской), либо подразделяться на несколько логических уровней (обычно, не более двух), образуя иерархическую структуру. В одноранговой наложенной сети все узлы являются равноправными, и за счет полносвязности оверлея любая пара узлов может обмениваться данными напрямую. Примерами одноранговых сетей являются Gnutella v0.4, Freenet, CAN, Chord, Kademlia и другие.
В случае создания многоуровневой сети некоторые участники на основании объективных показателей (таких как производительность, пропускная способность и т. п.) получают особый статус «суперузла». Все остальные узлы многоуровневой сети могут обмениваться данными только через свои родительские суперузлы, выступающие в роли транзитных. При этом суперузлы, как правило, объединяются в плоскую полносвязную логическую топологию. В качестве примеров иерархических наложенных сетей можно указать FastTrack/KaZaA, Gnutella v0.6, Skype, CAP [83], Brocade [140] и другие.
Автоматизированные методы краткосрочного прогнозирования временных рядов
По результатам проведенных экспериментов можно сделать выводы о возможности применения простых методов предсказания при решении задачи автоматизированного прогнозирования интенсивности сетевого трафика. Точность наилучших из исследованных методов находится на границе хорошего и удовлетворительного прогнозов, что дает возможность использовать данные методы в реальных системах управления трафиком.
Методом, обеспечивающим наивысшую точность прогнозирования поведения интенсивности сетевого трафика со средней процентной ошибкой предсказания в районе 20-25%, является простое экспоненциальное сглаживание (модель N-N) с адаптивным выбором коэффициента сглаживания и интервалом оценки порядка 10-15 точек временного ряда. Замечено, что точность также ощутимо зависит от гладкости исходных данных, указанное значение точности достигается при использовании временного ряда с шагом 21 секунда (максимальный шаг среди представленных). Основной рекомендацией в данном случае будет предварительная подготовка временного ряда с максимально возможным шагом усреднения. Также можно отметить, что для снижения вычислительной сложности процедуры, оправданным является применение интервальной модели N-N, позволяющей использовать рассчитанное значение коэффициента сглаживания для ближайших 10-15 прогнозов с
1. Рассмотрены методы краткосрочного прогнозирования, позволяющие осуществить полностью автоматизированное предсказание поведения сетевого трафика.
2. Проведен статистический анализ временных рядов, представляющих процессы изменения интенсивности реального сетевого трафика. Обнаружено, что интенсивность сетевого трафика может быть описана логнормальным и вейбулловским распределениями, а сам процесс предположительно является самоподобным и персистентным с показателем Хрста #є(о,7;0,8). Показано, что стационарность процесса зависит от применяемого временного шага сглаживания. Предложено использовать для предсказаний модели, не учитывающие сезонность процесса, в связи с отсутствием ярко выраженных циклических компонент.
3. Проведена экспериментальная оценка эффективности методов краткосрочного прогнозирования для предсказания поведения интенсивности сетевого трафика. Показано, что методом, обеспечивающим наивысшую точность прогнозирования поведения интенсивности сетевого трафика со средней процентной ошибкой предсказания в районе 20-25%, является простое экспоненциальное сглаживание (модель N-N) с адаптивным выбором коэффициента сглаживания и интервалом оценки порядка 10-15 точек временного ряда.
Для оценки эффективности функционирования предложенной концепции наложенной балансировочной сети был разработан высокоуровневый симулятор, позволяющий проанализировать поведение сети, а также е основные параметры в различных условиях. Как правило, наложенная балансировочная сеть имеет дело с агрегированными потоками трафика, характеризующимися высокой интенсивностью передачи относительно размеров отдельных пакетов. Такая структура трафика позволяет рассматривать его в виде потока, подобного потоку жидкости, избегая необходимости учитывать отдельные пакеты, что значительно упрощает процесс моделирования [54]. Данное допущение позволило разработать симулятор наложенной балансировочной сети, оперирующий потоковым представлением трафика при расчетах.
В первую очередь, в процессе инициализации создается объект, способный хранить основные параметры моделируемой балансировочной сети. Затем из специального файла загружаются сведения о пороговых пропускных способностях каналов наложенной сети, соединяющих соседние узлы между собой. Далее создается необходимое количество объектов, выполняющих функции узлов LBO, после чего из файлов, содержащих информацию об интенсивности поступающего в балансировочную сеть трафика (как приоритетного, так и неприоритетного) на все доступные направления, данные выгружаются в память симулятора. Все загруженные данные должны быть преобразованы к виду, удобному для дальнейшего использования в процессе моделирования, для чего однородные данные собираются в единые многомерные массивы, а также осуществляется приведение всех сведений о входящем трафике к единой временной шкале.
Необходимость введения процедуры нормализации определяется тем, что файлы, содержащие данные о зависимости интенсивности трафика, входящего на некоторый узел, от времени представляют собой таблицы, записи в которых могут быть сделаны в различном временном масштабе, могут иметь различный временной шаг между соседними значениями и т.д. Процедура нормализации позволяет автоматически устранить подобные несоответствия, а также дает возможность выбора произвольного временного шага, независимо от заданного в исходных данных. В ходе нормализации формируется единый массив модельного времени, представляющий собой пересечение всех исходных временных массивов и имеющий заданный шаг. После того, как общая временная шкала сформирована, все исходные данные с помощью сплайн-интерполяции [1] значений преобразуются для использования в едином времени.
Когда все необходимые объекты созданы, а исходные данные преобразованы для дальнейшего использования, симулятор переходит ко второму этапу работы. На данном этапе производится собственно численное моделирование работы балансировочной сети в заданных условиях. Как можно заметить из рисунка 4.3, второй этап является наиболее сложным и ресурсоемким в процессе работы симулятора. В сущности, весь второй этап является расчтом поведения каждого узла моделируемой сети в каждый данный момент единого модельного времени.
Временная диаграмма реальной последовательности событий в наложенной балансировочной сети была представлена на рисунке 2.4 (см. п. 2.2.3). Для уменьшения вычислительной сложности моделирования в симуляторе принят ряд допущений: обмен данными прогнозов между узлами осуществляется синхронно и централизованно в начале каждого периода длительностью tUPDAT E , нагрузка в каналах определяется с помощью прямого запроса объекта балансировочной сети.
Исследование работы наложенной балансировочной сети в условиях статических нагрузок
В данном эксперименте изучается влияние значений пороговых параметров процедуры исключения осцилляций (см. п. 2.4.5) на частоту переноса потоков и оптимальность распределения нагрузки в наложенной балансировочной сети.
Постановка эксперимента. Начальные условия данного эксперимента полностью аналогичны предыдущему: в тестовой сети из 4 узлов имитируется перегрузка направления от узла №0 к узлу №1, при этом характер неприоритетной нагрузки остается стабильным, а входящий приоритетный трафик на перегруженном направлении изменяется (см. рис. 4.11 и 4.17). Здесь, также как и в предыдущем эксперименте, рассматриваются случаи колебания интенсивности только для приоритетного трафика, как наиболее ощутимо влияющего на распределение нагрузки в сети.
Результаты эксперимента. В рамках проведения данного эксперимента тестируются 6 наборов параметров процедуры исключения осцилляций, представленных в таблице 4.9. Для упрощения рассматривается минимальный набор параметров
Как видно из таблицы 4.9, все значения параметров возрастают пропорционально номеру соответствующего набора, уменьшая, таким образом, чувствительность процедуры исключения осцилляций. Результаты, полученные для заданных наборов параметров, представлены на рисунках 4.28 и 4.29.
Как можно заметить, увеличение значений параметров в некоторый момент (набор №4) дат довольно ощутимое падение частоты переноса потоков (см. рис. 4.28). Такое поведение является следствием снижения чувствительности процедуры исключения осцилляций и приводит к росту неоптимальности распределения нагрузки. Неоптимальное распределение нагрузки, в свою очередь, ведет к кратковременной передаче на перегруженных каналах трафика с суммарной интенсивностью, превышающей установленную пороговую. Данный эффект характеризуется максимальным пиковым значением загрузки каналов превышающим 100% (относительно заданного порогового значения) и, в силу кратковременности и локальности, практически не сказывается на средней загрузке каналов сети (см. рис. 4.29).
Зависимость частоты переноса Рис. 4.29 – Зависимость загрузки каналов потоков от применяемых параметров между узлами от применяемых параметров процедуры исключения осцилляций процедуры исключения осцилляций Выводы. Как показывают результаты проведенного эксперимента, выбор параметров задающих чувствительность процедуры исключения осцилляций продиктован компромиссом между частотой переноса потоков в сети и оптимальностью распределения нагрузки. Таким образом, можно заключить, что соответствующий выбор является задачей минимизации негативных последствий частой перебалансировки и кратковременных превышений пороговой загрузки каналов сети.
Исследование влияния ошибок, вносимых прогнозированием В данном эксперименте оценивается влияние ошибок прогнозирования интенсивности входящего трафика на возможности передачи неприоритетной нагрузки и показатели функционирования наложенной балансировочной сети.
Постановка эксперимента. Условия проведения эксперимента аналогичны представленным в п. 4.3.1. и 4.3.2., с тем отличием, что анализируются только сценарии изменения приоритетного входящего трафика: медленного и взрывного характера (см. рис. 4.11 и 4.17). Каждый сценарий тестируется дважды – в первом случае сеть работает с применением прогнозирования, а во втором, опираясь на заранее известные данные входящего трафика, что позволяет оценить влияние ошибки, вносимой прогнозированием, на показатели функционирования наложенной балансировочной сети. В данном эксперименте значения параметров сглаживания пересчитываются каждые 20 секунд (2xtUPDAm), а оптимизация коэффициентов производится на участке 30 секунд (3xtUPDATE).
Результаты эксперимента. Пример неточной оценки интенсивности входящего приоритетного трафика, вызванной ошибками прогнозирования, приведен на рисунке 4.30. Полученные в результате проведения эксперимента показатели функционирования сети приведены в таблице 4.10.
Можно видеть, что использование прогнозирования незначительно ухудшает возможности передачи сетью неприоритетного трафика, а также снижает частоту переноса потоков, что особенно заметно в случае кратких всплесков приоритетной нагрузки. В то же время ошибки прогнозирования приводят к искажению плана распределения нагрузки в сети, в свою очередь ведущему к неоптимальному распределению потоков и кратковременному превышению порогового значения суммарной интенсивности передачи трафика по перегруженному каналу.
Отличия в распределении нагрузки в случае использования точных реальных и спрогнозированных данных проиллюстрированы на рисунке 4.31. На нижнем графике явно выделяется момент возникновения краткосрочной перегрузки на направлении от узла №0 к узлу №1 (около 30-й секунды), приходящийся на пик входной нагрузки. Инерционность подсистем прогнозирования и балансировки нагрузки не позволяет среагировать мгновенно и перевести избыточный трафик на обходные пути, в результате чего суммарная интенсивность нагрузки в канале кратковременно превышает заданное пороговое значение. приоритетного трафика узлом №0 наложенной балансировочной сети Выводы. Результаты проведенного эксперимента наглядно демонстрируют неизбежное отклонение плана распределения нагрузки в сети от идеального, вызываемое преимущественно ошибками и инерционностью системы прогнозирования. Основным негативным следствием такого отклонения является вероятность кратковременного превышения заданной пороговой нагрузки перегруженных каналов. (в экспериментах: до 14,6% допустимой пропускной способности канала). В то же время следует отметить, что неточность распределения незначительно отражается на возможностях передачи трафика наложенной балансировочной сетью, не вызывая ощутимого снижения производительности сети на рассмотренных сценариях. Так применение прогнозирования снизило интенсивность переданной в эксперименте нагрузки на 0,03%, в случае медленного, и на 0,18% – взрывного характера изменения интенсивности входящего приоритетного трафика. При этом инерционность предсказаний позволила уменьшить частоту переноса потоков на 7% и 24% для медленного и взрывного характера входящей нагрузки, соответственно.
