Samopodobieństwo analizy danych sieciowych

W sieciach komputerowych samopodobieństwo jest cechą dynamiki przesyłu danych w sieci. Podczas modelowania dynamiki danych w sieci tradycyjne modele szeregów czasowych, takie jak autoregresyjny model średniej ruchomej, nie są odpowiednie. Dzieje się tak dlatego, że te modele zapewniają tylko skończoną liczbę parametrów w modelu, a tym samym interakcję w skończonym oknie czasowym, ale dane sieciowe mają zwykle zależny od dalekiego zasięgu struktura czasowa. Samopodobny proces jest jednym ze sposobów modelowania dynamiki danych sieciowych z korelacją o tak dużym zasięgu. W tym artykule zdefiniowano i opisano dynamikę transferu danych w sieci w kontekście procesu samopodobnego. Pokazano właściwości procesu oraz podano metody tworzenia wykresów i estymacji parametrów modelujących samopodobieństwo danych sieciowych.

Definicja

Załóżmy, $.$ będzie to $\displaystyle \gamma (t)}$ (stacjonarny drugiego rzędu $)$ ze $,$ wariancją i funkcją autokorelacji ${$ . że funkcja autokorelacji ma postać $gamma (t)$${\ Displaystyle \ gamma (t) \ strzałka w prawo t ^ {- \ beta} L (t)}$ jak ${\ Displaystyle t \ do \ infty}$ , gdzie ${\ displaystyle 0 <\ beta <1$$wolno$ jest zmieniającą funkcją w nieskończoności ,
${\ Displaystyle \ lim _ {t \ do \ infty} {\ Frac {L (tx)} {L (t)}} = 1}$ dla wszystkich ${\ Displaystyle x> 0}$ . Na przykład $\ Displaystyle L (t) = const}$ i ${\ Displaystyle L (t) = \ log (t)}$ są powoli różne funkcje. Pozwalać ${\ Displaystyle X_ {k} ^ {(m)} = {\ Frac {1} {m ^ { H}}} (X_ {km-m + 1} + \ cdot \ cdot \ cdot + X_ {km})}$ , gdzie ${\ Displaystyle k = 1,2,3, \ ldots }$ oznaczają zagregowaną serię punktów na nienakładających się blokach wielkości ${\ displaystyle m}$$dla$ każdego dodatnią liczbą całkowitą .

Dokładnie samopodobny proces

• ${\ displaystyle X}$ nazywany jest dokładnie samopodobnym procesem, jeśli istnieje samopodobny parametr taki, że ma $Displaystyle X_ {k} ^ {(m$$}}$ taka sama dystrybucja jak ${\ displaystyle X}$ . Przykładem dokładnie samopodobnego procesu z $szum$ ułamkowy gaussowski (FGN) z ${\ Displaystyle {\ Frac {1} {2} <H <1}$ .

Definicja: ułamkowy szum gaussowski (FGN)

$}$${\ Displaystyle X (t) = B_ {H} (t + 1) -B_ {H} (t) ~$$1$ nazywa się ułamkowym szumem gaussowskim, gdzie jest ułamkowym ruchem Browna

proces samopodobny dokładnie drugiego rzędu

• ${\ Displaystyle X} nazywany jest samopodobnym procesem dokładnie drugiego$$X_ {k} ^ {(m)} }$ , jeśli istnieje parametr samopodobny taki, że $Displaystyle$ ma taką samą wariancję i autokorelację jak ${\ displaystyle X}$ .

asymptotyczny proces samopodobny drugiego rzędu

• $}$$X$ nazywany jest asymptotycznym samopodobnym procesem rzędu z parametrem samopodobnym, jeśli ${\ Displaystyle \ gamma ^ {(m)} (t) \ do {\ Frac {1} {2}} [(t + 1) ^ {2H} -2t ^ {2H} + (t-1) ^ { 2H}]}$ jak ${\ Displaystyle m \ do \ infty}$ , ${\ Displaystyle ~ \ forall t = 1,2,3, \ ldots}$

Niektóre względne sytuacje procesów samopodobnych

Zależność dalekiego zasięgu (LRD)

Załóżmy $średnią$$słabo stacjonarny$$)$ drugiego rzędu i . Funkcja autokorelacji (ACF) opóźnienia $jest$ przez ${\ Displaystyle \ gamma (t) = {\ operatorname {cov} (X (h), X (h+t)) \over \sigma ^{2}}={E[(X(h)-\mu )(X(h+t)-\mu )] \over \sigma ^{2}}}$

Definicja:

Mówi się, że proces słabo stacjonarny jest „zależnością dalekiego zasięgu”, jeśli ${\ Displaystyle \ suma _ {t = 0} ^ {\ infty} |\ gamma (t) | = \ infty}$

Proces, który spełnia ${\ Displaystyle \ gamma (t) \ rightarrow t ^ {- \ beta} L (t)}$ jako ${\ Displaystyle t \ do \ infty Mówi się, że }$ ma zależność dalekiego zasięgu. Funkcja gęstości widmowej zależności dalekiego zasięgu jest zgodna z prawem potęgowym w pobliżu początku. Równoważnie ${\ Displaystyle \ gamma (t) \ rightarrow t ^ {- \ beta} L (t)}$ , ${\ Displaystyle X}$ ma zależność dalekiego zasięgu, jeśli funkcja gęstości widmowej funkcji autokorelacji $_$ _ postać ${\ Displaystyle w ^ {- \ gamma} L (w)}$ jak ${\ Displaystyle w \ do 0}$ gdzie ${\ Displaystyle 0 <\ gamma <1}$ , ${\ Displaystyle L}$ jest powoli zmienna w punkcie 0.

Zobacz także

Powoli zanikające różnice

${\ Displaystyle X ^ {(m)} = {\ Frac {1} {m}} (X_ {1} + \ cdot \ cdot \ cdot + X_ {m})}$ Gdy funkcja autokorelacji procesu samopodobnego spełnia ${\ Displaystyle \ gamma (t) \ strzałka w prawo t ^ {- \ beta} L ( t)}$ jako ${\ Displaystyle t \ do \ infty}$ , co oznacza, że ​​​​spełnia również ${\ Displaystyle Var (X ^ {(m)}) \ do am ^ {- \ beta }}$ as ${\ Displaystyle m \ do \ infty}$ , gdzie jest $stałą$ niezależną od m i 0 <β <1.

Szacowanie parametru samopodobieństwa „H”

Analiza R/S

$ułamkowy$ że podstawowym procesem jest szum gaussowski. Rozważ szereg $_$${\ Displaystyle Y_ {(n)} = \ suma _ {i = 1} ^ {n} X_ {(i)}}$ .

Wariancja próbki wynosi ${\ Displaystyle X_ {(i)}}$$S ^{2}(n)={\frac {1}{n}}\sum _{i=1}^{n}X_{(i)}^{2}-({\frac {1}{n }})^{2}Y_{n}^{2}}$ n

Definicja: statystyka R/S

${\ Displaystyle {\ Frac {R} {S}} (n) = {\ Frac {1} {S (n)}} [\ max _ {0 \ równoważnik t \ równoważnik n} (Y_ {t} - { \frac {t}{n}}Y_{n})-\min _{0\równoważnik t\równoważnik n}(Y_{t}-{\frac {t}{n}}Y_{n})]}$

${\ Displaystyle X_ {(i)}}$ ja FGN, to ${\ Displaystyle E ({\ Frac {R} {S}} (n ))\to C_{H}\times n^{H}}$ Rozważ dopasowanie modelu regresji :
${\ Displaystyle \ log {\ Frac {R} {S}} (n) = \ log (C_ {H}) + H \ log (n) + \ epsilon _ {n}},$ gdzie ${\ Displaystyle \ epsilon _ {n} \ gruby N (0, \ sigma ^ {2})}$ W szczególności dla szeregu czasowego o długości podzielić dane szeregów czasowych na ${\ Displaystyle N}$${\ Displaystyle k}$ grupuje każdą o rozmiarze ${\ Displaystyle {\ Frac {N} {k}}}$ , oblicz
${\ Displaystyle {\ Frac {R} {S}} (n)}$ dla każdej grupy. Zatem dla każdego n mamy pary danych ( $log$$} {S}} (n)}$ ). Istnieją $aby$ dla każdego $,$ więc możemy dopasować model regresji oszacować ${\ displaystyle H}$ dokładniej. Jeśli nachylenie linii regresji wynosi od 0,5 do 1, jest to proces samopodobny.

Wykres wariancji w czasie

Wariancja średniej próbki jest dana przez ${\ Displaystyle Var ({\ bar {X}} _ {n}) \ do cn ^ {2H -2},~\forall c>0}$ . Aby oszacować H, oblicz średnie próbki
${\ Displaystyle {\ bar {X}} _ {1}, {\ bar {X}} _ {2}, \ cdots, {\ bar {X}} _ {m_ {k}}} dla$ m $\ displaystyle m_ {k}}$ podseria długości ${\ displaystyle k}$ . Ogólną średnią można podać jako ${\ Displaystyle {\ bar {X}} (k) = {\ Frac {1} {m_ { k}}}\sum _{i=1}^{m_{k}}{\bar {X}}_{i}(k)} , wariancja$ próby
${\ Displaystyle S ^ {2} (k) = {\ Frac {1} {m_{k}-1}}\suma _{i=1}^{m_{k}}({\bar {X}}_{i}(k)-{\bar {X}}(k) )^{2}}$ . Wykresy wariancji-czasu uzyskuje się przez wykreślenie ${\ displaystyle \ log S ^ {2} (k)}$ przeciwko ${\ displaystyle \ log k}$ i możemy dopasować prostą linię najmniejszych kwadratów przez wynikowe punkty na płaszczyźnie, ignorując małe wartości k.

W przypadku dużych wartości $lub$$zasięgu$ punkty na wykresie będą rozproszone wokół linii prostej o ujemnym nachyleniu . między obserwacji, nachylenie linii prostej jest równe -1. Samopodobieństwo można wywnioskować z wartości oszacowanego nachylenia, które jest asymptotycznie między –1 a 0, a oszacowanie stopnia samopodobieństwa jest określone przez ${\ Displaystyle {\ kapelusz {H}} = 1 + {\ Frac {1} {2}} (nachylenie).}$

Analiza oparta na periodogramie

$rozwiązania$ estymator największej wiarygodności Whittle'a ( MLE ) jest stosowany do parametru Hursta za pomocą gęstości widmowej . Jest to nie tylko narzędzie do wizualizacji parametru Hursta, ale także metoda wnioskowania statystycznego o parametrach poprzez asymptotyczne właściwości MLE. $podąża$ szczególności za procesem Gaussa . gęstość $x$ , ${\ Displaystyle f_ {x} (w; \ teta) = \ sigma _ {\ epsilon} ^ {2} f_ {x} (w; ( 1,\eta ))}$ , gdzie ${\ Displaystyle \ teta = (\ sigma _ {\ epsilon} ^ {2}, \ eta) = (\ sigma _ {\ epsilon} ^ {2}, H, \ teta _ {3}, \ ldots \ theta _ {k}), H = {\ Frac {\ gamma + 1} {2}}}$ i ${\ Displaystyle \ theta _ {3}, \ ldots, \ theta _{k}}$ skonstruować model autoregresji (AR) szeregów czasowych krótkiego zasięgu, czyli ${\ Displaystyle X_ {j} = \ suma _ {i = 1} ^ {k} \ alfa _ {i} X_ {ji} + \ epsilon _ {j}}$ z ${\ Displaystyle Var (\ epsilon _ {j}) = \ sigma _ {\ epsilon} ^ {2}}$ .

$Zatem$$($ Whittle'a minimalizuje funkcję ${\ Displaystyle Q (\ eta) = \ int _ {- \ pi} ^ {\ pi} {\ Frac {ja (w)}} {f (w; (1, \ eta)}}} \,dw}$ , gdzie ${\ Displaystyle I (w)}$ oznacza periodogram X jako ${\ Displaystyle (2 \ pi n) ^ {- 1} | \ suma _ {j = 1} ^ {n} X_ {j} e ^ {iwj} | ^ {2}}$ i ${\ Displaystyle {\ kapelusz {\ sigma}} ^ {2} = \ int _ {- \ pi} ^ {\ pi} {\ Frac {I (w)}} {f (w; (1, {\ kapelusz {\ eta}})}} \, dw}$ . Całki te można ocenić za pomocą sumy Riemanna.

Wtedy ${\ Displaystyle n ^ {1/2} ({\ kapelusz {\ teta}} - \ teta)}$ asymptotycznie podąża za rozkładem normalnym, jeśli ${\ Displaystyle X_ {j} }$ można wyrazić jako postać nieskończonego modelu średniej ruchomej.

Aby oszacować $najpierw$ należy obliczyć ten periodogram. Ponieważ $,$ estymatorem gęstości widmowej, szereg z zależnością dalekiego zasięgu powinien mieć periodogram ${\ Displaystyle | \ lambda | ^ {1-2H}}$ blisko początku. Wykres periodogramu uzyskuje się przez wykreślenie
${\ Displaystyle \ log (I_ {n} (w))}$ przeciwko ${\ Displaystyle \ log (w)}$ . Następnie dopasowanie modelu regresji dziennika $\ Displaystyle \ log (I_ {n} (w))}$$\ Displaystyle \ log (w)}$ ⁡ ( nachylenie ${\ Displaystyle {\ kapelusz {\ beta}}}$ . Nachylenie dopasowanej linii prostej jest również oszacowaniem ${\ Displaystyle 1-2H}$ . W $sposób$ uzyskuje się .

Uwaga: Podczas stosowania metody periodogramu występują dwa typowe problemy. Po pierwsze, jeśli dane nie mają rozkładu Gaussa, transformacja danych może rozwiązać tego rodzaju problemy. Po drugie, widmo próbki, które odbiega od założonej gęstości widmowej, jest kolejnym widmem. Aby rozwiązać ten problem, proponuje się metodę agregacji. X ${\ Displaystyle X}$ jest procesem Gaussa, a funkcja gęstości widmowej $} L (w)}$ ) $\$ jak ${\ Displaystyle w \ do \ infty}$ , funkcja, ${\ Displaystyle m ^ {- H} L ^ {- {\ Frac {1} {2}}} (m) \ suma _ {i = (j-1) m + 1} ^ {m} k(X_{i}-E(|X_{i}|)),~j=1,2,\ldots ,[{\tfrac {n}{m}}]} , zbiega się w rozkładzie do FGN$ jako ${\ Displaystyle m \ do \ infty}$ .

• P. Whittle, „Estymacja i informacja w stacjonarnych szeregach czasowych”, art. Mata. 2, 423-434, 1953.
• K. PARK, W. WILLINGER, samopodobna ocena ruchu sieciowego i wydajności, WILEY,2000.
• WE Leland, W. Willinger, MS Taqqu, DV Wilson, „O samopodobnym charakterze ruchu Ethernet”, ACM SIGCOMM Computer Communication Review 25,202-213,1995.
• W. Willinger, MS Taqqu, WE Leland, DV Wilson, „Samopodobieństwo w ruchu pakietów o dużej prędkości: analiza i modelowanie pomiarów ruchu w sieci Ethernet”, Statistical Science 10,67-85,1995.