WikiDer > Самоподобный процесс - Википедия

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

Обзор

Проектирование устойчивых и надежных сетей и сетевых сервисов становится все более сложной задачей в современном мире. Интернет Мир. Для достижения этой цели понимание характеристик интернет-трафика играет все более важную роль. Эмпирические исследования измеренных трассировок трафика привели к широкому признанию самоподобия сетевого трафика.^[1]

Самоподобный Ethernet трафик имеет зависимости в большом диапазоне временных масштабов. Это должно контрастировать с телефонным трафиком, который Пуассон в процессе его прибытия и отправления.^[2]

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

Распределения с тяжелыми хвостами наблюдались во многих природных явлениях, включая физические и социологические. Мандельброт установили использование распределений с тяжелыми хвостами для моделирования реальных фрактал явления, например Фондовые рынки, землетрясения, климат и погода.^{[нужна цитата]}Ethernet, WWW, SS7, TCP, FTP, ТЕЛНЕТ и VBR видео (оцифрованное видео того типа, которое передается по Банкомат сетей) трафик самоподобен.

Самоподобие в сетях с пакетной передачей данных может быть вызвано распределением размеров файлов, человеческим взаимодействием и / или динамикой Ethernet. Самоподобные и зависимые на большом расстоянии характеристики в компьютерных сетях представляют собой принципиально иной набор проблем для людей, занимающихся анализом и / или проектированием сетей, и многие из предыдущих предположений, на которых были построены системы, больше не действительны при наличии самоподобие.^[3]

Распределение Пуассона

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

Предполагая, что прибытие по чистой случайности или прерывание по чистой случайности приводит к следующему:

• Количество поступивших вызовов в данный момент времени имеет распределение Пуассона, то есть:

${ displaystyle P (a) = left ({ frac { mu ^ {a}} {a!}} right) e ^ {- mu},}$

куда а количество поступивших звонков по времени Т, и ${ displaystyle mu}$ среднее количество поступивших вызовов за время Т. По этой причине случайный трафик также известен как трафик Пуассона.

• Количество отправлений вызовов в заданное время также имеет распределение Пуассона, то есть:

${ Displaystyle P (d) = left ({ frac { lambda ^ {d}} {d!}} right) e ^ {- lambda},}$

куда d количество вызовов по времени Т и ${ displaystyle lambda}$ среднее количество вызовов за время Т.

• Интервалы, Т, между поступлением и отправлением вызова - это интервалы между независимыми, одинаково распределенными случайными событиями. Можно показать, что эти интервалы имеют отрицательное экспоненциальное распределение, то есть:

${ Displaystyle Р [Т GEQ т] = е ^ {- т / ч}, ,}$

куда час среднее время выдержки (MHT).^{[нужна цитата]}

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

Говорят, что распределение имеет тяжелый хвост, если

${ displaystyle lim _ {x to infty} e ^ { lambda x} Pr [X> x] = infty quad { mbox {для всех}} lambda> 0. ,}$

Одним из простых примеров распределения с тяжелым хвостом является Распределение Парето.

Моделирование автомодельного трафика

Поскольку (в отличие от традиционного телефонного трафика) пакетный трафик демонстрирует самоподобные или фрактальные характеристики, традиционные модели трафика не применимы к сетям, которые несут самоподобный трафик.^{[нужна цитата]}

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

Предыдущая аналитическая работа, проведенная в Интернет-исследованиях, основывалась на предположениях, таких как экспоненциально распределенные взаимные прибытия пакетов, и выводы, сделанные на основе таких предположений, могут вводить в заблуждение или быть неверными при наличии распределений с тяжелыми хвостами.^[2]

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

Автомодельные случайные процессы, моделируемые Распределения твиди

Лиланд и другие предоставили математический аппарат для описания автомодельных случайных процессов.^[4] Для последовательности чисел

${ Displaystyle Y = (Y_ {i}: я = 0,1,2, ..., N)}$

со средним

${ displaystyle { hat { mu}} = { text {E}} (Y_ {i})}$,

отклонения

${ displaystyle y_ {i} = Y_ {i} - { hat { mu}}}$,

отклонение

${ displaystyle { hat { sigma}} ^ {2} = { text {E}} (y_ {i} ^ {2})}$,

и автокорреляционная функция

${ displaystyle r (k) = { text {E}} (y_ {i}, y_ {i + k}) / { text {E}} (y_ {i} ^ {2})}$

с запаздыванием k, если автокорреляция этой последовательности имеет дальнобойное поведение

${ Displaystyle г (к) сим к ^ {- d} L (к)}$

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

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

${ Displaystyle Y_ {я} ^ {(м)} = (Y_ {им-м + 1} + ... + Y_ {им}) / м}$.

Дисперсия, определенная из этой последовательности, будет масштабироваться по мере изменения размера ячейки, так что

${ displaystyle { text {var}} [Y ^ {(m)}] = { hat { sigma}} ^ {2} m ^ {- d}}$

тогда и только тогда, когда автокорреляция имеет предельный вид^[5]

${ Displaystyle lim _ {к к infty} r (k) / k ^ {- d} = (2-d) (1-d) / 2}$.

Также можно построить набор соответствующих аддитивных последовательностей

${ Displaystyle Z_ {я} ^ {(м)} = mY_ {я} ^ {(м)}}$,

на основе расширяющихся бункеров,

${ Displaystyle Z_ {я} ^ {(м)} = (Y_ {им-м + 1} + ... + Y_ {им})}$.

Если автокорреляционная функция демонстрирует такое же поведение, аддитивные последовательности будут подчиняться соотношению

${ displaystyle { text {var}} [Z_ {i} ^ {(m)}] = m ^ {2} { text {var}} [Y ^ {(m)}] = ({ hat { sigma}} ^ {2} / { hat { mu}} ^ {2-d}) { text {E}} [Z_ {i} ^ {(m)}] ^ {2-d}}$

С ${ displaystyle { hat { mu}}}$ и ${ Displaystyle { шляпа { sigma}} ^ {2}}$ константы, это соотношение составляет отклонение от среднего сила закона (Закон Тейлора), с п=2-d.^[6]

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

Эти распределения Tweedie характеризуются присущей масштабная инвариантность и поэтому для любого случайная переменная Y который подчиняется распределению Tweedie, отклонение var (Y) относится к иметь в виду E (Y) по степенному закону,

${ displaystyle { text {var}} , (Y) = a [{ text {E}} , (Y)] ^ {p},}$

куда а и п положительные константы. Показатель п для среднего степенного закона дисперсии, связанной с некоторыми автомодельными случайными процессами, находится в диапазоне от 1 до 2 и, таким образом, может частично моделироваться Составной твиди Пуассон – гамма-распределение.^[6]

Аддитивная форма гамма-модели Пуассона соединения Твиди имеет кумулянтная производящая функция (CGF),

${ Displaystyle K_ {p} ^ {*} (s; theta, lambda) = lambda kappa _ {p} ( theta) [(1 + s / theta) ^ { alpha} -1] }$,

куда

${ displaystyle kappa _ {p} ( theta) = { dfrac { alpha -1} { alpha}} left ({ dfrac { theta} { alpha -1}} right) ^ { alpha}}$,

это кумулянт функция α показатель Твиди

${ Displaystyle альфа = { dfrac {p-2} {p-1}}}$,

s - переменная производящей функции, θ это канонический параметр и λ - индексный параметр.

Первая и вторая производные от CGF, с s = 0, дает среднее значение и дисперсию соответственно. Таким образом, можно подтвердить, что для аддитивных моделей дисперсия относится к среднему по степенному закону,

${ Displaystyle mathrm {var} (Z) propto mathrm {E} (Z) ^ {p}}$.

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

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

Теорема Твиди о сходимости может быть использована для объяснения происхождения отклонение от среднего степенного закона, 1 / f шум и мультифрактальность, особенности, связанные с автомодельными процессами.^[6]

Производительность сети

Производительность сети постепенно снижается с увеличением самоподобия. Чем больше самоподобный трафик, тем больше размер очереди. Распределение длин очереди самоподобного трафика затухает медленнее, чем с источниками Пуассона. Однако дальнодействующая зависимость ничего не говорит о его краткосрочных корреляциях, которые влияют на производительность в небольших буферах. Кроме того, агрегирование потоков самоподобного трафика обычно усиливает самоподобие («прерывистость»), а не сглаживает его, усугубляя проблему.^{[нужна цитата]}

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

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

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

• Потеря ячеек / пакетов и переполнение очереди
• Нарушение границ задержки, например в видео
• Худшие случаи в статистике мультиплексирование

Пуассоновские процессы хорошо себя ведут, потому что они без гражданства, а пиковая загрузка не выдерживается, поэтому очереди не заполняются. В случае дальнего порядка пики длятся дольше и имеют большее влияние: на некоторое время смещается равновесие.^[8]

Смотрите также

• Длиннохвостый трафик

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

внешняя ссылка

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