Självlikhet i nätverksdataanalys

I datornätverk är självlikhet en egenskap hos nätverksdataöverföringsdynamiken . När man modellerar nätverksdatadynamik är de traditionella tidsseriemodellerna, såsom en autoregressiv glidande medelvärdesmodell inte lämpliga. Detta beror på att dessa modeller endast tillhandahåller ett ändligt antal parametrar i modellen och därmed interaktion i ett ändligt tidsfönster, men nätverksdata har vanligtvis en långdistansberoende tidsstruktur. En självliknande process är ett sätt att modellera nätverksdatadynamik med en så lång räckviddskorrelation. Den här artikeln definierar och beskriver nätverkets dataöverföringsdynamik i samband med en självliknande process. Processens egenskaper visas och metoder ges för att grafera och uppskatta parametrar som modellerar nätverksdatas självlikhet.

Definition

Antag att $X$ är en svagt stationär (2:a ordningens stationär) process med medelvärde ${\displaystyle \mu } ,$ varians $displaystyle \sigma ^{2}}$ \ och autokorrelationsfunktionen ${ \displaystyle \gamma (t)}$ . Antag att autokorrelationsfunktionen $\gamma (t)$ har formen $\gamma (t)\rightarrow t^{-\beta } L(t)$ som $t\to \infty$ , där $0<\beta <1$ och $L(t)$ är en långsam varierande funktion i oändligheten , det vill säga $\lim _{t\to \infty }{\frac {L(tx)}{L(t)} }=1$ för alla $x>0$ . Till exempel, $L(t)=const$ och $L(t)=\log(t)$ är långsamt varierande funktioner. Låt ${\displaystyle X_{k}^{(m)}={\frac {1}{m^ {H}}}(X_{km-m+1}+\cdot \cdot \cdot +X_{km})} , där k =$ 1 $k=1,2,3, \ldots }$ , betecknar en aggregerad punktserie över icke-överlappande block med storleken $m$ , för varje ${\displaystyle m} ett$ är positivt heltal .

Exakt självliknande process

• $X$ kallas en exakt självliknande process om det finns en självliknande parameter $H$ så att $X_{k}^{(m)}$ har samma fördelning som $X$ . Ett exempel på exakt självliknande process med $H$ är Fractional Gaussian Noise (FGN) med ${\frac {1}{2}}<H<1$ .

Definition: Fractional Gaussian Noise (FGN)

$X(t)=B_{H}(t+1)-B_{H}(t),~ \forall t\geq 1$ kallas det fraktionella gaussiska bruset, där $B_{H}(\cdot )$ är en fraktionell Brownsk rörelse .

exakt andra ordningens självliknande process

• $X$ kallas en exakt andra ordningens självliknande process om det finns en självliknande parameter $H$ så att $X_{k}^{(m)}$ har samma varians och autokorrelation som $X$ .

asymptotisk andra ordningens självliknande process

• $X$ kallas en asymptotisk andra ordningens självliknande process med självliknande parameter $H$ om $\gamma ^{(m)}(t)\to {\frac {1}{2}}[(t+1)^{2H}-2t^{ 2H}+(t-1)^{2H}]$ som $m\to \infty$ , $~\forall t=1,2, 3,\ldots$

Några relativa situationer av självliknande processer

Long-Range-Dependence (LRD)

Antag att $X(t)$ är en svagt stationär (2:a ordningens stationär) process med medelvärde $\mu$ och varians $\sigma ^{2}$ . Autokorrelationsfunktionen (ACF) för lag $\gamma (t)={\mathrm {cov} (X(h),X(h+t)) \over \sigma ^{2} }={E[(X(h)-\mu )(X(h+t)-\mu )] \över \sigma ^{2}}$$\displaystyle t}$ ges av

Definition:

En svagt stationär process sägs vara "Long-Range-Dependence" om $\sum _{t=0}^{\infty }|\gamma (t)|=\infty$

En process som uppfyller $\gamma (t)\rightarrow t^{-\beta }L(t)$ som $t\to \infty$ sägs ha långdistansberoende. Den spektrala täthetsfunktionen för långdistansberoende följer en kraftlag nära ursprunget. Motsvarande $\gamma (t)\rightarrow t^{-\beta }L(t)$ , $X$ har långdistansberoende om spektral densitetsfunktion för autokorrelationsfunktion, $f_{t}(w)=\summa _{t=0}^{\infty }\ gamma (t)e^{iwt}$ , har formen av $w^{-\gamma }L(w)$ som $w\to 0$ där $0<\gamma <1$ , $L$ varierar långsamt vid 0.

se också

Långsamt sönderfallande varianser

$X^{(m)}={\frac {1}{m}}(X_{1}+\cdot \cdot \ cdot +X_{m})$ När en autokorrelationsfunktion för en självliknande process uppfyller $\gamma (t)\rightarrow t^{-\beta }L( t)$ som $t\to \infty$ , det betyder att den även uppfyller $Var(X^{(m)})\ till am^{-\beta }$ som $m\to \infty$ , där $a$ är en finit positiv konstant oberoende av m, och 0<β<1.

Uppskattning av självlikhetsparametern "H"

R/S-analys

Antag att den underliggande processen $X$ är Fractional Gaussian Noise. Betrakta serierna $X_{(1)},\ldots ,X_{(n)}$ , och låt $Y_{(n)}=\summa _{i=1}^{n}X_{(i)}$ .

Provvariansen för $X_{(i)}$ är $S ^{2}(n)={\frac {1}{n}}\summa _{i=1}^{n}X_{(i)}^{2}-({\frac {1}{n }})^{2}Y_{n}^{2}$

Definition:R/S-statistik

${\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})]$

Om $X_{(i)}$ är FGN, då ${\frac {R}{S}}(n ))\till C_{H}\ gånger n^{H}}$${\displaystyle \ log {\frac {R}{S}}(n)=\log(C_{H})+H\log(n)+\epsilon _{n}} ,$ en regressionsmodell: där ${ \displaystyle \epsilon _{n}\thicksim N(0,\sigma ^{2})}$ I synnerhet för en tidsserie med längden $N$ dela upp tidsseriedata i $k$ grupper vardera av storlek ${\frac {N}{k}}$ , beräkna ${\frac {R}{S}}(n)$ för varje grupp. För varje n har vi alltså $k$ datapar ( $\log(n),\log {\frac {R}{S}} (n)$ ).Det finns $k$ punkter för varje $n$ , så vi kan anpassa en regressionsmodell för att uppskatta $H$ mer exakt. Om lutningen på regressionslinjen är mellan 0,5~1 är det en självliknande process.

Varians-tid plot

Varians av provmedelvärdet ges av $Var({\bar {X}}_{n})\to cn^{2H -2},~\forall c>0$ . För att uppskatta H, beräkna urvalsmedelvärden ${\bar {X}}_{1},{\bar {X}}_{2},\cdots ,{\bar {X}}_{m_{k}}$ för $m_{k}$ underserier av längden $k$ . Totalt medelvärde kan ges av ${\displaystyle {\bar {X}}(k)={\frac {1}{m_{ k}}}\summa _{i=1}^{m_{k}}{\bar {X}}_{i}(k)} ,$ sampelvarians $S^{2}(k)={\frac {1}{m_{k}-1}}\summa _{ i=1}^{m_{k}}({\bar {X}}_{i}(k)-{\bar {X}}(k))^{2}$ . Varians-tidsplotterna erhålls genom att plotta $\log S^{2}(k)$ mot $\log k$ och vi kan passa en enkel minsta kvadratlinje genom de resulterande punkterna i planet ignorerar de små värdena på k.

För stora värden på $k$ förväntas punkterna i diagrammet vara utspridda runt en rät linje med en negativ lutning $2H-2$ . För kortdistansberoende eller oberoende bland observationer är lutningen på den räta linjen lika med -1. Självlikhet kan härledas från värdena för den uppskattade lutningen som är asymptotiskt mellan –1 och 0, och en uppskattning av graden av självlikhet ges av ${\hat {H}}=1+{\frac {1}{2}}(lutning).$

Periodogrambaserad analys

Whittle's approximativa maximum likelihood estimator ( MLE ) används för att lösa Hurst's parameter via spektraldensiteten av $X$ . Det är inte bara ett verktyg för att visualisera Hursts parameter, utan också en metod för att göra några statistiska slutsatser om parametrarna via de asymptotiska egenskaperna hos MLE. I synnerhet följer ${\displaystyle X} en$ Gauss-process . Låt spektraldensiteten för $X$ , $f_{x}(w;\theta )=\sigma _{\epsilon }^{2}f_{x}(w;(1,\eta ))$ , där $\theta =(\sigma _{\epsilon }^{2},\eta )=(\sigma _{\epsilon }^{2},H,\theta _{ 3},\ldots ,\theta _{k}),H={\frac {\gamma +1}{2}}$ och $\theta _{3},\ ldots ,\theta _{k}$ konstruerar en autoregression (AR) modell med kort räckvidd, det vill säga ${\displaystyle X_{j}=\ summa _{i=1}^{k}\alpha _{i}X_{ji}+\epsilon _{j}} ,$ med $Var(\epsilon _ {j})=\sigma _{\epsilon }^{2}$ .

Således minimerar Whittle's estimator ${\hat {\eta }}$ av $\eta$ funktionen $Q(\eta )=\int _{-\pi }^{\pi }{\frac {I(w)}{f(w;(1,\eta ))}} \,dw$ , där $I(w)$ anger periodogrammet för X som $(2\pi n)^{-1}|\sum _{j=1}^{n}X_{j}e^{iwj}|^{2}$ och ${\hat {\sigma }}^{2}=\int _{-\pi }^{\pi }{\ frac {I(w)}{f(w;(1,{\hat {\eta }}))}}\,dw$ . Dessa integrationer kan bedömas av Riemann summa.

Sedan följer $\displaystyle n^{1/2}({\hat {\theta }}-\theta )}$$X_{j}$ en normalfördelning om kan uttryckas som en form av en modell med oändligt glidande medelvärde.

För att uppskatta $H$ måste man först beräkna detta periodogram. Eftersom $I_{n}(w)$ är en estimator av spektraltätheten, bör en serie med långdistansberoende ha ett periodogram, som är proportionellt mot $|\lambda |^{1-2H}$ nära origo. Periodogramdiagrammet erhålls genom att plotta $\log(I_{n}(w))$ mot $\log(w)$ . Att sedan anpassa en regressionsmodell av $\log(I_{n}(w))$ på $\log(w)$ bör ge en lutning av ${\hat {\beta }}$ . Lutningen för den monterade räta linjen är också uppskattningen av $1-2H$ . Således erhålls uppskattningen ${\displaystyle {\hat {H}}} .$

Obs: Det finns två vanliga problem när vi tillämpar periodogrammetoden. För det första, om data inte följer en gaussisk fördelning, kan transformation av data lösa denna typ av problem. För det andra är det provspektrum som avviker från den antagna spektrala tätheten ett annat. En aggregeringsmetod föreslås för att lösa detta problem. Om $X$ är en Gauss-process och spektraldensitetsfunktionen för $X$ uppfyller $w^{-\gamma }L(w)$ som $w\to \infty$ , funktionen, ${\displaystyle m^{-H}L^{-{\frac {1}{2}}}(m)\summa _{i=(j-1)m +1}^{m}k(X_{i}-E(|X_{i}|)),~j=1,2,\ldots ,[{\tfrac {n}{m}}]} ,$ konvergerar i distribution till FGN som $m\to \infty$ .

• P. Whittle, "Uppskattning och information i stationära tidsserier", Art. Matta. 2, 423-434, 1953.
• K. PARK, W. WILLINGER, Self-Similar Network Traffic and Performance Evaluation, WILEY,2000.
• WE Leland, W. Willinger, MS Taqqu, DV Wilson, "On the self-similar nature of Ethernet traffic", ACM SIGCOMM Computer Communication Review 25,202-213,1995.
• W. Willinger, MS Taqqu, WE Leland, DV Wilson, "Self-Similarity in High-Speed ​​Packet Traffic: Analysis and Modeling of Ethernet Traffic Measurements", Statistical Science 10,67-85,1995.