Распределение с длинным или тяжелым хвостом — это распределение, которое присваивает относительно высокие вероятности областям, далеким от среднего или медианного значения. Более формальное математическое определение дано ниже. В контексте проектирования телетрафика было показано, что ряд представляющих интерес величин имеет распределение с длинным хвостом . Например, если мы рассмотрим размеры файлов, переданных с веб-сервера, то с хорошей степенью точности распределение будет с тяжелым хвостом, то есть передается большое количество небольших файлов, но, что особенно важно, количество переданных очень больших файлов остается основным компонентом загруженного объема.
Многие процессы технически зависят от дальнего действия, но не являются самоподобными . Различия между этими двумя явлениями незначительны. Тяжелый хвост относится к распределению вероятностей, а дальний диапазон зависит от свойства временного ряда, поэтому их следует использовать с осторожностью и проводить различие. Эти термины различны, хотя суперпозиции выборок из распределений с тяжелым хвостом объединяются, образуя дальний диапазон зависимых временных рядов.
Кроме того, существует броуновское движение , которое является самоподобным, но не зависит от дальнего действия.
Проектирование надежных и устойчивых сетей и сетевых сервисов становится все более сложной задачей в современном мире Интернета . Для достижения этой цели понимание характеристик интернет-трафика играет все более важную роль. Эмпирические исследования измеренных следов трафика привели к широкому признанию самоподобия в сетевом трафике. [1]
Самоподобный трафик Ethernet демонстрирует зависимости в широких временных масштабах. Это следует противопоставить телефонному трафику, который является пуассоновским в процессе прибытия и отправления. [2]
В случае многих временных рядов, если ряд усредняется, данные начинают выглядеть более гладкими. Однако, с самоподобными данными, мы сталкиваемся с пиковыми и всплесковыми следами, даже в больших масштабах. Такое поведение вызвано сильной зависимостью в данных: большие значения, как правило, попадают в кластеры и кластеры кластеров и т. д. Это может иметь далеко идущие последствия для производительности сети . [3]
Распределения с тяжелым хвостом наблюдались во многих природных явлениях, включая как физические, так и социологические явления. Мандельброт установил использование распределений с тяжелым хвостом для моделирования реальных фрактальных явлений, например фондовых рынков, землетрясений и погоды. [2] Трафик Ethernet, WWW , SS7 , TCP , FTP , TELNET и видео VBR (оцифрованное видео того типа, которое передается по сетям ATM ) является самоподобным. [4]
Самоподобие в пакетных сетях передачи данных может быть вызвано распределением размеров файлов, человеческим взаимодействием и/или динамикой Ethernet. [5] Самоподобные и зависящие от больших расстояний характеристики в компьютерных сетях представляют собой принципиально иной набор проблем для людей, занимающихся анализом и/или проектированием сетей, и многие из предыдущих предположений, на которых строились системы, больше недействительны при наличии самоподобия. [6]
Дальнодействующие и близзависимые процессы характеризуются своими функциями автоковариации .
В процессах с ближней зависимостью связь между значениями в разное время быстро уменьшается по мере увеличения разницы во времени.
В долгосрочных процессах корреляции в более длительных временных масштабах более значимы.
где ρ( k ) — автокорреляционная функция с задержкой k , α — параметр в интервале (0,1), а ~ означает асимптотически пропорциональную величину при стремлении k к бесконечности.
Можно показать, что такое масштабирование по степенному закону функции автокорреляции связано биусловно со степенным законом между дисперсией и средним значением при оценке последовательностей методом расширения бинов . Этот закон дисперсии к среднему значению является неотъемлемой чертой семейства статистических распределений, называемых моделями экспоненциальной дисперсии Твиди . Подобно тому, как центральная предельная теорема объясняет, как определенные типы случайных данных сходятся к форме нормального распределения, существует связанная теорема, теорема о сходимости Твиди , которая объясняет, как другие типы случайных данных будут сходиться к форме этих распределений Твиди и, следовательно, выражать как закон дисперсии к среднему значению, так и спад степенного закона в своих функциях автокорреляции.
Прежде чем математически представить распределение с тяжелым хвостом, ниже кратко рассматривается распределение Пуассона без памяти, используемое для моделирования традиционных телефонных сетей. Более подробную информацию см. в статье о распределении Пуассона .
Предполагая, что прибытия и вылеты происходят по чистой случайности, получаем следующее:
где a — количество поступивших вызовов, а — среднее количество поступивших вызовов за время T. По этой причине чисто случайный трафик также известен как пуассоновский трафик.
где d — количество отправленных вызовов, а — среднее количество отправленных вызовов за время T.
где h — среднее время удержания (MHT). [4]
Информацию по основам статистики и теории вероятностей можно найти в разделе внешних ссылок.
Распределения с тяжелым хвостом обладают свойствами, которые качественно отличаются от свойств обычно используемых (без памяти) распределений, таких как экспоненциальное распределение .
Параметр Херста H является мерой уровня самоподобия временного ряда, демонстрирующего долгосрочную зависимость, к которому можно применить распределение с тяжелым хвостом. H принимает значения от 0,5 до 1. Значение 0,5 указывает на то, что данные не коррелируют или имеют только краткосрочные корреляции. Чем ближе H к 1, тем больше степень постоянства или долгосрочная зависимость. [4]
Типичные значения параметра Херста, H :
Распределение называется распределением с тяжелым хвостом, если:
Это означает, что независимо от распределения для малых значений случайной величины, если асимптотическая форма распределения гиперболическая, оно имеет тяжелый хвост. Простейшее распределение с тяжелым хвостом — это распределение Парето , которое является гиперболическим во всем своем диапазоне. Дополнительные функции распределения для экспоненциального и Парето распределений показаны ниже. Слева показан график распределений, показанных на линейных осях, охватывающих большую область. [8] Справа показан график дополнительных функций распределения по меньшей области и с логарифмическим диапазоном. [5]
Если взять логарифм диапазона экспоненциального распределения, то результирующий график будет линейным. Напротив, график распределения с тяжелым хвостом все еще криволинейный. Эти характеристики можно четко увидеть на графике выше справа. Характерной чертой распределений с длинным хвостом является то, что если взять логарифм и диапазона, и домена, то хвост распределения с длинным хвостом будет приблизительно линейным на многих порядках величины. [9] На графике выше слева условие существования распределения с тяжелым хвостом, как было представлено ранее, не выполняется кривой, обозначенной как «Гамма-экспоненциальный хвост».
Функция массы вероятности распределения с тяжелым хвостом определяется по формуле:
и его кумулятивная функция распределения определяется выражением:
где k представляет собой наименьшее значение, которое может принимать случайная величина .
Читатели, заинтересованные в более строгой математической трактовке предмета, могут обратиться к разделу внешних ссылок.
В целом, существует три основные теории причин длиннохвостого трафика (см. обзор всех трех причин [10] ). Во-первых, это причина, основанная на прикладном уровне, которая предполагает, что длительность сеанса пользователя меняется с длиннохвостовым распределением из-за распределения размера файла. Если распределение размеров файлов имеет тяжелый хвост, то суперпозиция многих передач файлов в сетевой среде клиент/сервер будет зависеть от больших расстояний. Кроме того, этот причинный механизм надежен по отношению к изменениям сетевых ресурсов ( пропускной способности и емкости буфера ) и топологии сети . [11] В настоящее время это самое популярное объяснение в инженерной литературе и одно с наибольшим количеством эмпирических доказательств посредством наблюдаемых распределений размеров файлов.
Во-вторых, это причина транспортного уровня, которая предполагает, что обратная связь между несколькими потоками TCP из-за алгоритма предотвращения перегрузки TCP в ситуациях с умеренными и высокими потерями пакетов вызывает самоподобный трафик или, по крайней мере, позволяет ему распространяться. Однако считается, что это является существенным фактором только в относительно коротких временных масштабах, а не долгосрочной причиной самоподобного трафика.
Наконец, есть теоретическая причина на уровне канала, которая основана на физических симуляциях сетей коммутации пакетов в смоделированных топологиях. При критической скорости создания пакетов поток в сети становится перегруженным и демонстрирует шум 1/f и характеристики трафика с длинным хвостом. Однако были критические замечания по поводу таких моделей как нереалистичных, поскольку сетевой трафик имеет длинный хвост даже в неперегруженных регионах [12] и на всех уровнях трафика.
Моделирование показало, что зависимость на большом расстоянии может возникнуть в динамике длины очереди в заданном узле (сущности, которая передает трафик) в сети связи, даже когда источники трафика свободны от зависимости на большом расстоянии. Механизм этого, как полагают, связан с обратной связью от эффектов маршрутизации в моделировании. [13]
Моделирование трафика с длинным хвостом необходимо для того, чтобы сети могли быть подготовлены на основе точных предположений о трафике, который они переносят. Определение размеров и подготовка сетей, которые переносят трафик с длинным хвостом, обсуждаются в следующем разделе.
Поскольку (в отличие от традиционного телефонного трафика) пакетированный трафик демонстрирует самоподобные или фрактальные характеристики, обычные модели трафика не применяются к сетям, которые передают трафик с длинным хвостом. [4] Предыдущие аналитические работы, выполненные в исследованиях Интернета, принимали такие предположения, как экспоненциально распределенное поступление пакетов, и выводы, полученные при таких предположениях, могут быть вводящими в заблуждение или неверными при наличии распределений с тяжелым хвостом. [2]
Давно известно, что эффективное и точное моделирование различных явлений реального мира должно включать тот факт, что наблюдения, сделанные в разных масштабах, несут важную информацию. Проще говоря, представление данных в больших масштабах по их среднему значению часто полезно (например, средний доход или среднее количество клиентов в день), но может быть неуместным (например, в контексте буферизации или ожидания в очередях). [3]
С конвергенцией голоса и данных будущая многосервисная сеть будет основана на пакетированном трафике, и для разработки, проектирования и измерения будущих многосервисных сетей потребуются модели, которые точно отражают природу длинного хвоста трафика. [4] Мы ищем эквивалент модели Эрланга для сетей с коммутацией каналов. [5]
Не существует большого количества моделей с тяжелым хвостом и богатым набором сопутствующих методов подгонки данных. [14] Четкая модель для фрактального трафика еще не появилась, и нет определенного направления к четкой модели. [4] Выведение математических моделей, которые точно представляют трафик с длинным хвостом, является плодотворной областью исследований.
Гауссовские модели , даже зависимые от дальнего действия гауссовские модели, не способны точно моделировать текущий интернет-трафик. [15] Классические модели временных рядов, такие как пуассоновские и конечные марковские процессы, в значительной степени полагаются на предположение о независимости или, по крайней мере, слабой зависимости. [3] Однако пуассоновские и марковские процессы использовались с некоторым успехом. Нелинейные методы используются для создания моделей пакетного трафика, которые могут воспроизводить как краткосрочные, так и долгосрочные зависимые потоки. [13]
Для моделирования трафика с длинным хвостом было предложено несколько моделей. К ним относятся следующие:
Не существует единого мнения о том, какая из конкурирующих моделей является подходящей, [4] но процесс Пуассона-Парето-Взрыва (PPBP), который является процессом M/G/, возможно, является наиболее успешной моделью на сегодняшний день. Продемонстрировано, что он удовлетворяет основным требованиям простой, но точной модели трафика с длинным хвостом. [15]
Наконец, представлены результаты моделирования [4] с использованием -устойчивых стохастических процессов для моделирования трафика в широкополосных сетях. Моделирование сравнивается с различными эмпирическими данными (Ethernet, WWW, VBR Video).
В некоторых случаях увеличение параметра Херста может привести к снижению производительности сети. Степень, в которой «тяжелый хвост» ухудшает производительность сети, определяется тем, насколько хорошо контроль перегрузки способен преобразовывать исходный трафик в в среднем постоянный выходной поток, сохраняя при этом информацию. [17] Контроль перегрузки трафика с «тяжелым хвостом» обсуждается в следующем разделе.
Самоподобие трафика отрицательно влияет на основные показатели производительности, такие как размер очереди и скорость потери пакетов. Распределение длины очереди трафика с длинным хвостом затухает медленнее, чем с источниками Пуассона. Однако зависимость от дальнего действия ничего не говорит о его краткосрочных корреляциях, которые влияют на производительность в небольших буферах. [16] Для трафика с тяжелым хвостом чрезвычайно большие всплески происходят чаще, чем для трафика с легким хвостом. [18] Кроме того, агрегирование потоков трафика с длинным хвостом обычно усиливает самоподобие (« всплеск »), а не сглаживает его, усугубляя проблему. [1]
График выше справа, взятый из [4], представляет сравнение производительности очередей между потоками трафика с различной степенью самоподобия. Обратите внимание, как размер очереди увеличивается с ростом самоподобия данных для любого заданного использования канала, тем самым ухудшая производительность сети.
В современной сетевой среде с потоками трафика мультимедиа и других QoS- чувствительных потоков, составляющих растущую долю сетевого трафика, показатели производительности второго порядка в форме « джиттера », такие как вариация задержки и вариация потери пакетов , имеют значение для предоставления определяемого пользователем QoS. Ожидается, что самоподобная пульсация будет оказывать отрицательное влияние на показатели производительности второго порядка. [19]
Услуги на основе коммутации пакетов, такие как Интернет (и другие сети, использующие IP ) являются услугами с наилучшими усилиями, поэтому ухудшение производительности, хотя и нежелательно, может быть терпимо. Однако, поскольку соединение является контрактным, сети ATM должны поддерживать задержки и джиттер в согласованных пределах. [20]
Самоподобный трафик демонстрирует постоянную кластеризацию, что отрицательно влияет на производительность сети.
Многие аспекты качества обслуживания сети зависят от способности справляться с пиками трафика, которые могут привести к сбоям в работе сети, например:
Процессы Пуассона ведут себя хорошо, потому что они не имеют состояния , а пиковая загрузка не поддерживается, поэтому очереди не заполняются. При дальнем порядке пики длятся дольше и оказывают большее влияние: равновесие смещается на некоторое время. [7]
Из-за возросших требований, которые трафик long-tail предъявляет к сетевым ресурсам, сети должны быть тщательно подготовлены, чтобы гарантировать выполнение соглашений о качестве обслуживания и уровне обслуживания . В следующем подразделе рассматривается подготовка стандартных сетевых ресурсов, а в следующем подразделе рассматривается подготовка веб-серверов, которые переносят значительный объем трафика long-tail.
Для сетевых очередей с входами, зависящими от больших расстояний, резкое увеличение задержек в очередях при довольно низких уровнях использования и медленное уменьшение длины очередей означает, что постепенное улучшение производительности потерь требует значительного увеличения размера буфера. [21]
В то время как пропускная способность постепенно снижается по мере увеличения самоподобия, задержка в очереди увеличивается более радикально. Когда трафик самоподобен, мы обнаруживаем, что задержка в очереди растет пропорционально емкости буфера, присутствующей в системе. Взятые вместе, эти два наблюдения имеют потенциально ужасные последствия для положений QoS в сетях. Для достижения постоянного уровня пропускной способности или потери пакетов по мере увеличения самоподобия необходима чрезвычайно большая емкость буфера. Однако увеличение буферизации приводит к большим задержкам в очереди, и, таким образом, самоподобие значительно круче кривую компромисса между пропускной способностью/потерей пакетов и задержкой. [17]
ATM может использоваться в телекоммуникационных сетях для преодоления проблем измерения производительности второго порядка. Короткая фиксированная длина ячейки, используемая в ATM, уменьшает задержку и, что наиболее важно, джиттер для чувствительных к задержке услуг, таких как голос и видео. [22]
Сложность шаблонов рабочей нагрузки (например, паттерны пульсирующего прибытия) может существенно влиять на потребности в ресурсах, пропускную способность и задержку, с которой сталкиваются запросы пользователей, с точки зрения более высокого среднего времени ответа и более высокой дисперсии времени ответа . Без адаптивного, оптимального управления и контроля ресурсов соглашения об уровне обслуживания, основанные на времени ответа, невозможны. Требования к емкости на сайте увеличиваются, в то время как его способность обеспечивать приемлемые уровни производительности и доступности уменьшается. [18] Методы контроля и управления трафиком с длинным хвостом обсуждаются в следующем разделе.
Способность точно прогнозировать шаблоны запросов является важным требованием планирования мощности. Практическим следствием всплесков и тяжелых хвостов и коррелированных поступлений является сложность планирования мощности. [18]
Что касается SLA, тот же уровень обслуживания для распределений с тяжелым хвостом требует более мощного набора серверов по сравнению со случаем независимого трафика запросов с легким хвостом. Чтобы гарантировать хорошую производительность, необходимо сосредоточиться на длительности пикового трафика, поскольку именно огромные всплески запросов больше всего снижают производительность. Вот почему некоторым загруженным сайтам требуется больше запаса (резервной мощности) для обработки объемов; например, сайт онлайн-торговли с большим объемом резервирует резервную мощность в соотношении три к одному. [18]
Дополнительную информацию о влиянии долгосрочной зависимости на производительность сети можно найти в разделе внешних ссылок.
Учитывая повсеместность масштабно-инвариантной всплесковой активности, наблюдаемой в различных сетевых контекстах, поиск эффективного алгоритма управления трафиком, способного обнаруживать и управлять самоподобным трафиком, стал важной проблемой. Проблема управления самоподобным сетевым трафиком все еще находится в зачаточном состоянии. [23]
Управление трафиком для самоподобного трафика изучалось по двум направлениям: во-первых, как расширение анализа производительности в контексте предоставления ресурсов, а во-вторых, с точки зрения управления трафиком в нескольких временных масштабах, где корреляционная структура в больших временных масштабах активно используется для улучшения производительности сети. [24]
Подход к предоставлению ресурсов направлен на определение относительной полезности двух основных типов сетевых ресурсов — пропускной способности и емкости буфера — в отношении их ограничивающего воздействия на самоподобие и выступает за политику определения размеров ресурсов малого буфера/большой пропускной способности. В то время как предоставление ресурсов является по своей природе открытым циклом , управление трафиком с множественными временными масштабами использует структуру корреляции дальнего действия, присутствующую в самоподобном трафике. [24] Управление перегрузкой может осуществляться одновременно в нескольких временных масштабах, и путем совместного использования информации, извлеченной в разных временных масштабах, достигается значительный прирост производительности. [23]
Другой подход, принятый для управления длиннохвостовым трафиком, делает средства управления трафиком осведомленными о свойствах рабочей нагрузки. Например, когда TCP вызывается в HTTP в контексте взаимодействия веб-клиента/сервера, размер транспортируемого файла (который известен на сервере) передается или становится доступным для протоколов на транспортном уровне , включая выбор альтернативных протоколов, для более эффективной передачи данных. Для коротких файлов, которые составляют большую часть запросов на подключение в распределениях размеров файлов с тяжелым хвостом веб-серверов, сложный контроль обратной связи может быть обойден в пользу легких механизмов в духе оптимистичного контроля, что может привести к улучшению использования полосы пропускания. [19]
Было обнаружено, что самый простой способ контролировать пакетный трафик — это ограничить длину очередей. Длинные очереди в сети неизменно возникают на хостах (сущностях, которые могут передавать и получать пакеты). Поэтому контроль перегрузки может быть достигнут путем снижения скорости производства пакетов на хостах с длинными очередями. [13]
Зависимость от больших расстояний и ее использование для управления трафиком лучше всего подходят для потоков или соединений, чей срок службы или продолжительность соединения являются длительными. [19]
{{cite journal}}
: CS1 maint: multiple names: authors list (link)