Самоподобие анализа сетевых данных

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

Определение

Предполагать $X$ быть слабостационарным (стационарным 2-го порядка) процессом со средним $\mu$, дисперсия $\sigma ^{2}$и автокорреляционная функция $\gamma (t)$.Предположим, что автокорреляционная функция $\gamma (t)$ имеет форму $\gamma (t)\rightarrow t^{-\beta }L(t)$ как $t\to \infty$, где $0<\beta <1$и $L(t)$ — медленно меняющаяся функция на бесконечности , т.е. $\lim _{t\to \infty }{\frac {L(tx)}{L(t)}}=1$ для всех $x>0$.Например, $L(t)=const$ и $L(t)=\log(t)$ являются медленно меняющимися функциями.
Позволять $X_{k}^{(m)}={\frac {1}{m^{H}}}(X_{km-m+1}+\cdot \cdot \cdot +X_{km})$,где $k=1,2,3,\ldots$, обозначают агрегированную серию точек по непересекающимся блокам размера $m$, для каждого $m$ является положительным целым числом .

Точно самоподобный процесс

• $X$ называется точно самоподобным процессом, если существует самоподобный параметр $H$ такой, что $X_{k}^{(m)}$ имеет то же распределение, что и $X$. Пример точно самоподобного процесса с $H$ это дробный гауссовский шум (FGN) с ${\frac {1}{2}}<H<1$.

Определение: дробный гауссов шум (FGN).

$X(t)=B_{H}(t+1)-B_{H}(t),~\forall t\geq 1$ называется дробным гауссовским шумом, где $B_{H}(\cdot )$ является дробным броуновским движением .

точно самоподобный процесс второго порядка

• $X$ называется самоподобным процессом ровно второго порядка, если существует самоподобный параметр $H$ такой, что $X_{k}^{(m)}$ имеет ту же дисперсию и автокорреляцию, что и $X$.

асимптотический самоподобный процесс второго порядка

• $X$ называется асимптотическим самоподобным процессом второго порядка с самоподобным параметром $H$ если $\gamma ^{(m)}(t)\to {\frac {1}{2}}[(t+1)^{2H}-2t^{2H}+(t-1)^{2H}]$ как $m\to \infty$, $~\forall t=1,2,3,\ldots$

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

Дальнодействующая зависимость (LRD)

Предполагать $X(t)$ — слабостационарный (стационарный процесс 2-го порядка) со средним $\mu$ и дисперсия $\sigma ^{2}$. Автокорреляционная функция (ACF) задержки $t$ дается $\gamma (t)={\mathrm {cov} (X(h),X(h+t)) \over \sigma ^{2}}={E[(X(h)-\mu )(X(h+t)-\mu )] \over \sigma ^{2}}$

Определение:

Слабо стационарный процесс называется «дальнобойной зависимостью», если $\sum _{t=0}^{\infty }|\gamma (t)|=\infty$

Процесс, который удовлетворяет $\gamma (t)\rightarrow t^{-\beta }L(t)$ как $t\to \infty$ Говорят, что он имеет долгосрочную зависимость. Функция спектральной плотности дальнодействующей зависимости подчиняется степенному закону вблизи начала координат. Эквивалентно $\gamma (t)\rightarrow t^{-\beta }L(t)$, $X$ имеет дальнодействующую зависимость, если функция спектральной плотности автокорреляционной функции, $f_{t}(w)=\sum _{t=0}^{\infty }\gamma (t)e^{iwt}$, имеет вид $w^{-\gamma }L(w)$ как $w\to 0$ где $0<\gamma <1$, $L$ медленно меняется на 0.

также см.

Медленно убывающая дисперсия

$X^{(m)}={\frac {1}{m}}(X_{1}+\cdot \cdot \cdot +X_{m})$
Когда автокорреляционная функция самоподобного процесса удовлетворяет условию $\gamma (t)\rightarrow t^{-\beta }L(t)$ как $t\to \infty$, это означает, что оно также удовлетворяет $Var(X^{(m)})\to am^{-\beta }$ как $m\to \infty$, где $a$ — конечная положительная константа, не зависящая от m, и 0<β<1.

Оценка параметра самоподобия «H»

R/S-анализ

Предположим, что основной процесс $X$ это дробный гауссовский шум. Рассмотрим серию $X_{(1)},\ldots ,X_{(n)}$, и пусть $Y_{(n)}=\sum _{i=1}^{n}X_{(i)}$.

Выборочная дисперсия $X_{(i)}$ является $S^{2}(n)={\frac {1}{n}}\sum _{i=1}^{n}X_{(i)}^{2}-({\frac {1}{n}})^{2}Y_{n}^{2}$

Определение: статистика R/S.

${\frac {R}{S}}(n)={\frac {1}{S(n)}}[\max _{0\leq t\leq n}(Y_{t}-{\frac {t}{n}}Y_{n})-\min _{0\leq t\leq n}(Y_{t}-{\frac {t}{n}}Y_{n})]$

Если $X_{(i)}$ это FGN, тогда $E({\frac {R}{S}}(n))\to C_{H}\times n^{H}$
Рассмотрите возможность установки регрессионной модели: $\log {\frac {R}{S}}(n)=\log(C_{H})+H\log(n)+\epsilon _{n}$, где $\epsilon _{n}\thicksim N(0,\sigma ^{2})$
В частности, для временного ряда длиной $N$ разделить данные временного ряда на $k$ группирует каждую по размеру ${\frac {N}{k}}$, вычислить ${\frac {R}{S}}(n)$ для каждой группы.
Таким образом, для каждого n мы имеем $k$ пары данных ( $\log(n),\log {\frac {R}{S}}(n)$).Есть $k$ баллы за каждый $n$, поэтому мы можем использовать регрессионную модель для оценки $H$ точнее. Если наклон линии регрессии находится в пределах 0,5–1, это самоподобный процесс.

График изменения времени

Дисперсия выборочного среднего определяется выражением $Var({\bar {X}}_{n})\to cn^{2H-2},~\forall c>0$.
Для оценки H рассчитайте выборочные средние значения. ${\bar {X}}_{1},{\bar {X}}_{2},\cdots ,{\bar {X}}_{m_{k}}$ для $m_{k}$ подсерия длины $k$.
Общее среднее значение можно определить по формуле ${\bar {X}}(k)={\frac {1}{m_{k}}}\sum _{i=1}^{m_{k}}{\bar {X}}_{i}(k)$, выборочная дисперсия $S^{2}(k)={\frac {1}{m_{k}-1}}\sum _{i=1}^{m_{k}}({\bar {X}}_{i}(k)-{\bar {X}}(k))^{2}$.
Графики зависимости времени от времени получаются путем построения графика $\log S^{2}(k)$ против $\log k$ и мы можем провести простую линию наименьших квадратов через полученные точки на плоскости, игнорируя малые значения k.

Для больших значений $k$, ожидается, что точки на графике будут разбросаны вокруг прямой линии с отрицательным наклоном. $2H-2$.Для ближней зависимости или независимости наблюдений наклон прямой равен -1.
О самоподобии можно судить по значениям предполагаемого наклона, который асимптотически находится между –1 и 0, а оценка степени самоподобия дается выражением ${\hat {H}}=1+{\frac {1}{2}}(slope).$

Анализ на основе периодограммы

Приблизительная оценка максимального правдоподобия Уиттла ( MLE ) применяется для решения параметра Херста через плотность спектральную $X$. Это не только инструмент для визуализации параметра Херста, но и метод, позволяющий сделать некоторые статистические выводы о параметрах с помощью асимптотических свойств MLE. В частности, $X$ следует гауссовскому процессу . Пусть спектральная плотность $X$, $f_{x}(w;\theta )=\sigma _{\epsilon }^{2}f_{x}(w;(1,\eta ))$, где $\theta =(\sigma _{\epsilon }^{2},\eta )=(\sigma _{\epsilon }^{2},H,\theta _{3},\ldots ,\theta _{k}),H={\frac {\gamma +1}{2}}$, и $\theta _{3},\ldots ,\theta _{k}$ построить модель авторегрессии временных рядов с коротким диапазоном (AR), то есть $X_{j}=\sum _{i=1}^{k}\alpha _{i}X_{j-i}+\epsilon _{j}$,с $Var(\epsilon _{j})=\sigma _{\epsilon }^{2}$.

Таким образом, оценка Уиттла ${\hat {\eta }}$ из $\eta$ сводит к минимумуфункция $Q(\eta )=\int _{-\pi }^{\pi }{\frac {I(w)}{f(w;(1,\eta ))}}\,dw$, где $I(w)$ обозначает периодограмму X как $(2\pi n)^{-1}|\sum _{j=1}^{n}X_{j}e^{iwj}|^{2}$ и ${\hat {\sigma }}^{2}=\int _{-\pi }^{\pi }{\frac {I(w)}{f(w;(1,{\hat {\eta }}))}}\,dw$. Эти интегрирования можно оценить суммой Римана.

Затем $n^{1/2}({\hat {\theta }}-\theta )$ асимптотически следует нормальному распределению, если $X_{j}$ может быть выражен как форма модели бесконечного скользящего среднего.

Чтобы оценить $H$, сначала нужно вычислить эту периодограмму. С $I_{n}(w)$ является оценкой спектральной плотности, ряд с дальнодействующей зависимостью должен иметь периодограмму, пропорциональную $|\lambda |^{1-2H}$ близко к источнику. График периодограммы получается путем построения графика $\log(I_{n}(w))$ против $\log(w)$.
Затем подготавливаем регрессионную модель $\log(I_{n}(w))$ на $\log(w)$ должен давать наклон ${\hat {\beta }}$. Наклон подобранной прямой также является оценкой $1-2H$. Таким образом, оценка ${\hat {H}}$ получается.

Примечание:
При применении метода периодограммы возникают две распространенные проблемы. Во-первых, если данные не соответствуют распределению Гаусса, преобразование данных может решить проблемы такого рода. Во-вторых, спектр образца, который отклоняется от предполагаемой спектральной плотности, является другим. Для решения этой проблемы предлагается метод агрегирования. Если $X$ является гауссовским процессом, а функция спектральной плотности $X$ удовлетворяет $w^{-\gamma }L(w)$ как $w\to \infty$, функция, $m^{-H}L^{-{\frac {1}{2}}}(m)\sum _{i=(j-1)m+1}^{m}k(X_{i}-E(|X_{i}|)),~j=1,2,\ldots ,[{\tfrac {n}{m}}]$, сходится по распределению к FGN как $m\to \infty$.

Ссылки

• П. Уиттл, «Оценка и информация в стационарных временных рядах», Ст. Мат. 2, 423–434, 1953.
• К. ПАРК, В. ВИЛЛИНГЕР, Самоподобная оценка сетевого трафика и производительности, WILEY, 2000.
• У. Е. Леланд, В. Виллинджер, М. С. Такку, Д. В. Уилсон, «О самоподобной природе трафика Ethernet», ACM SIGCOMM Computer Communication Review 25,202-213,1995.
• В. Виллингер, М. С. Такку, В. Е. Леланд, Д. В. Уилсон, «Самоподобие в высокоскоростном пакетном трафике: анализ и моделирование измерений трафика Ethernet», Statistical Science 10,67-85, 1995.