Självlikhet och skalning fenomen har dominerat Internet trafik analys under det senaste årtiondet. Med identifieringen av långdistansberoende (LRD) i nätverkstrafiken har forskarsamhället genomgått en mental förändring från Poisson och minneslösa processer till LRD och spruckna processer. Trots dess utbredda användning hindras dock LRD-analysen av svårigheten att faktiskt identifiera beroendet och göra en otvetydig uppskattning av dess parametrar. Författarna beskriver LRD-resultaten i nätverkstrafiken och undersöker den nuvarande bristen på noggrannhet och robusthet i LRD-uppskattningen. Dessutom lägger de fram färska bevis för att paketanländande verkar vara i överensstämmelse med Poissons antagande i Internetkärnan. Internet Measurement Long-Range Dependence T raffic modellering och analys är en grundläggande byggsten för Internetteknik och design. Vi kan inte kopiera Internet och studera det som helhet, så vi förlitar oss på noggrann analys av nätverksmätningar och deras omvandling till modeller för att hjälpa till att förklara Internets funktionalitet och förbättra dess prestanda. För ungefär 10 år sedan revolutionerade införandet av långdistansberoende (LRD) och självlikhet vår förståelse av nätverkstrafiken. (LRD innebär att beteendet hos en tidsberoende process visar statistiskt signifikanta korrelationer över stora tidsskalor; självlikhet beskriver det fenomen där beteendet hos en process bevaras oavsett skalning i rum eller tid.) Innan dess ansåg forskare att Poisson-processer (dvs. paketankomstprocessen är minneslös och interarrivaltider följer den exponentiella distributionen) är en lämplig representation för nätverkstrafik i verkliga system. 1 LRD flög i ansiktet på konventionell visdom genom att ange att nätverkstrafiken uppvisar långtidsminne (sitt beteende över vitt skilda tider korreleras). Detta påstående ifrågasatte giltigheten i Poissons antagande och flyttade samhällets fokus från att anta minneslöst och smidigt beteende till att anta ett långt minne och ett sprucket beteende. I den här artikeln ger vi en översikt över vad samhället har lärt sig av 10 år av LRD-forskning; vi identifierar också grottorna och begränsningarna i vår förmåga att upptäcka LRD. I synnerhet vill vi öka medvetenheten om två frågor: att identifiera och uppskatta LRD är långt ifrån enkelt, och att den storskaliga aggregering av Internets kärna kan ha förskjutit paket-nivå beteende till att vara en Poisson process. I slutändan kräver mätning och modellering av Internet att vi hela tiden förnyar modeller och metoder. Gott om bevis som samlats in under det senaste årtiondet tyder på förekomsten av LRD, självlikhet, och tung-tailed distributioner (vilket innebär stora värden kan existera med icke-försumbar sannolikhet) i olika aspekter av nätverkets beteende. Innan vi tittar på de stora framstegen inom LRD-forskningen måste vi först beskriva LRD och självlikhet i samband med tidsserieanalys. Låt X(t) vara en stokastisk process. I vissa fall kan X ta formen av en diskret tidsserie {X t }, t = 0, 1,..., N, antingen genom periodisk provtagning eller genom att beräkna dess värde över en serie fasta längdintervall. Vi säger att X(t) är stationär om dess gemensamma fördelning över en samling av gånger t 1,..., t N är invariant till tidsförskjutning. Således kan vi karakterisera beroendet mellan processens värden vid olika tidpunkter genom att utvärdera processens autokorreleringsfunktion (ACF), som är ρ(k). ACF mäter likheten mellan en serie X t och en skiftad version av sig själv X t+k :, där μ och σ är medelvärdet respektive standardavvikelser för X. Också av intresse är en tidsseries aggregerade process X k A stationär process X är långdistansberoende om dess autokorrelationer sönderfaller till noll så långsamt att deras summa inte konvergerar - det vill säga, k=1 ❌  på (k) och = ∞. Intuitivt är minnet inbyggt i processen eftersom beroendet av en LRD-processs vitt skilda värden är betydande, även vid stora tidsförskjutningar. En stokastisk process X är självlik om där jämlikhet hänvisar till jämlikhet i fördelningar, a är en skalfaktor, och självlikhet parameter H kallas Hurst exponenten. Intuitivt beskriver självlikhet det fenomen där vissa processegenskaper bevaras oavsett skalning i rum eller tid. Second-order self-similarity beskriver egenskapen att en tidsseries korrelationsstruktur (ACF) bevaras oberoende av tidsaggregation. Enkelt uttryckt är en andra ordningens självliknande tidsserie ACF densamma för antingen grova eller fina tidsskalor. En stationär process X t är andra ordningens självliknande 3 om och asymptotiskt exakt självliknande om andra ordningens självliknande processer kännetecknas av en hyperboliskt sönderfallande ACF och används i stor utsträckning för att modellera LRD-processer. Omvänt kännetecknar snabbt förfallande korrelationer kortdistansberoende. Av dessa definitioner kan vi dra slutsatsen att LRD karakteriserar en tidsserie om 0,5 < H < 1. Som H → 1, beroendet är starkare. För nätverksmätningsprocesser avser X antalet paket och bytes med efterföljande tidsintervall, vilket innebär att X beskriver volymen av bytes/paket som observeras i en länk varje gång intervall t. Leland och kollegors banbrytande arbete gav det första empiriska beviset på självliknande egenskaper i LAN-trafiken. 4 De gjorde en rigorös statistisk analys av Ethernet trafikmätningar och etablerade dess självliknande karaktär. De konstaterade särskilt att variabiliteten i Internettrafiken var invariant i den observerade tidsskalan - det vill säga, trafiken blev inte jämn med aggre- 5 De visade att paket interarrivaltider för Telnet och FTP-trafik beskrevs av tunga-tailed distributioner och kännetecknas av sprickighet, vilket indikerade att Poissonprocessen underskattade både sprickighet och variabilitet. Dessutom visade de att storskaliga korrelationer kännetecknade trafikspår i stort område, och drog följande slutsats: "Vi bör överge Poissonbaserade modellering av bredområdestrafik för alla utom användares ankomster." Dessa två banbrytande studier knuffade forskare bort från traditionella Poisson modellering och självständighetsantaganden, som förkastades som orealistiska och alltför förenklade. Den typ av trängsel som orsakas av självlika nättrafikmodeller har haft en betydande inverkan på köprestandan, vilket till stor del beror på variationer mellan olika tidsskalor. Ytterligare studier visade att Poisson-baserade modeller avsevärt underskattade prestandamått, vilket visar att självlikhet resulterade i prestandanedbrytning genom att drastiskt öka köande fördröjningar och paketförluster. Självlikviditetens ursprung i Internettrafiken beror huvudsakligen på omfattande distributioner av filstorlekar. 8, 9 Flera studier korrelerade Hurst exponenten med tung-tailed distributioner, vilket tyder på att extremt stora överföringsförfrågningar kunde inträffa med icke-försumbar sannolikhet. Förutom LRD, Internettrafiken presenterar komplexa skalning och multifractal egenskaper. Många simuleringar och empiriska studier illustrerar hur skalningsbeteendet och intensiteten i det observerade beroendet är relaterad till observationens omfattning. Specifikt finns löst kontra starkt beroende i mindre respektive större tidsskalor. Förändringspunkten förknippas vanligen med antingen tur-trip-tiden (RTT) eller påträngande "snabba" flöden med små interarrivaltider. Trots de överväldigande bevisen på LRD:s närvaro i Internettrafiken tyder några fynd på att Poissonmodeller och oberoende fortfarande kan tillämpas eftersom antalet källor ökar i snabba stamlänkar som medför ett stort antal distinkta flöden, vilket leder till stora volymer trafikmultiplexing. 12 I andra studier 13 påpekas dessutom att flera end-to-end nätverksegenskaper verkar stämma överens med självständighetsantagandena i närvaro av icke-stationaritet (dvs. när statistiska egenskaper varierar med tiden). Det dominerande sättet att kvantifiera LRD är genom Hurst exponenten, som är en skalar, men att beräkna denna exponent är inte enkelt. För det första kan det inte beräknas definitivt, bara uppskattat. För det andra, även om vi kan använda flera olika metoder för att uppskatta Hurst exponenten, de ofta producerar motstridiga resultat, och det är inte klart som ger den mest korrekta uppskattningen. Vi kan klassificera Hurst exponentskattningar i två allmänna kategorier: de som arbetar i tidsdomänen och de som arbetar i frekvens- eller waveletdomänen. På grund av utrymmesbegränsningar kan vi inte ge en fullständig beskrivning av alla tillgängliga estimatorer, men en översikt visas på annat håll. 14 Tidsdomänskattare undersöker maktlagens förhållande mellan en specifik statistisk egenskap i en tidsserie och tidsaggregationsblockets storlek m: LRD finns om den specifika egenskapen kontra m är en rak linje när den ritas i loggskala. Denna linje lutning är en uppskattning av Hurst exponenten, så tid-domänskattare innebär två presuppositioner för LRD att existera: statistiskt signifikanta bevis för att de relevanta punkterna verkligen representerar en rak linje, och att linjens lutning är sådan att 0,5 < H < 1 (Hurst exponent H beror på denna lutning). Dessa estimatorer använder flera metoder: R/S (omskalad intervallstatistik), absolut värde, varians och varians av restvärden. Naturligtvis, frekvens-och wavelet-domäner fungerar i frekvens-eller wavelet-domänen. På samma sätt som tid-domän metoder, de undersöker om en tidsserie spektrum eller energi följer power-law beteende. Dessa skattningar inkluderar periodogram, Whittle, och wavelet Abry-Veitch (AV) estimatorer. 15 Vi kan testa dessa skattningsmetoder förmåga genom att först undersöka deras noggrannhet på syntetiserade LRD-serien och sedan testa deras förmåga att diskriminera LRD beteende när det tillämpas på icke-LRD datamängder. I överensstämmelse med liknande resultat i tidigare studier, visar 14, 16 våra resultat att ingen konsekvent estimator är robust i varje fall: estimatorer kan dölja LRD eller rapportera det felaktigt. Dessutom har varje estimator olika styrkor och begränsningar. Vi använde programvarupaketet SELFIS (offentligt distribuerat på vår webbplats, www.cs.ucr.edu/ tkarag) för att utföra de experiment som beskrivs nedan. De mest använda självliknande processerna Arima-processer beskriver LRD-serien när 0 < d < 0,5, där H = d + 0,5. Vi testade varje estimator mot två olika typer av syntetiserade långminnesserier: fraktionerade ARIMA och fGn. 17 För varje Hurst värde mellan 0,5 och 1 (med ett steg på 0,1) genererade vi 100 fGn och 100 fraktionerade ARIMA syntetiserade datamängder på 64 Kbyte. Figur 1 rapporterar det uppskattade genomsnittliga Hurst-värdet för dessa datamängder för varje estimator samt de 95 procentiga konfidensintervallen för medelvärdet (dvs. det intervall av värden som har en hög sannolikhet att innehålla medelvärdet). Men dessa intervall är så nära genomsnittet att de knappt kan urskiljas. Även om det finns många estimatorer och generatorer, utvärderade vi de vanligaste och mest använda. Figur 1 visar betydande variation i det uppskattade Hurst exponentvärdet mellan de olika metoderna, särskilt som Hurst exponenten tenderar till 1, där intensiteten av långdistansberoende är större. Frekvens-domänskattningar verkar vara mer exakta. När det gäller fGn syntetiserade serier, Whittle och Periodogram estimators faller exakt ovanpå den optimala skattningslinjen. Whittleskattaren har på förhand en fördel av att tillämpas på en tidsserie vars underliggande struktur motsvarar de antaganden enligt vilka estimatorn härleddes. Den vågformade AV-skattningen överskattar alltid Hurst exponentens värde (vanligtvis med 0,05). Sammantaget, tids-domänskattare misslyckas med att rapportera rätt Hurst exponent värde, underskattar det med mer än 20 procent. (I figur 1, linjer som samlas under den optimala uppskattningslinjen representerar dessa estimatorer.) När vi använde fraktionerad ARIMA för att syntetisera tidsserien var skattningarna i allmänhet närmare den optimala skattningslinjen. Ingen av estimatorerna följde dock konsekvent den optimala linjen över alla Hurst-värden. För att studera skattningarnas känslighet undersökte vi effekterna av olika fenomen som är gemensamma för tidsserieanalyser, såsom periodicitet, buller och trend (där medeltalet för processen stadigt ökar eller minskar). Vår analys visade att förekomsten av sådana processer märkbart påverkar uppskattare. Dessutom misslyckas de flesta metoder med att skilja mellan LRD och sådana fenomen, och felaktigt rapportera LRD i deterministiska icke-LRD tidsserier. Vi undersökte fGn-serien plus vitt Gaussiskt brus. Därefter undersökte vi bullereffekten på LRD-data. Vi fann att alla estimatorer underskattar Hurst exponenten i närvaro av buller, men med undantag av Whittle och våget estimator, skillnaden är försumbar. Beroende på signal-brusförhållandet och fGn-seriens Hurst exponentvärde, kan dessa två estimatorer dock avsevärt underskatta Hurst exponenten - med mer än 20 procent i vissa fall. fGn-serien plus en cosinusfunktion. Vid undersökningen av periodicitetens effekt på LRD-data fann vi att alla uppskattningar påverkades av dess närvaro. Beroende på cosinusfunktionens amplitud tenderar tidsdomäner att underskatta Hurst exponenten. Å andra sidan överskattar frekvensbaserade metoder Hurst exponenten. När vi ökar cosinusfunktionens amplitud, tenderar uppskattningarna till 1. Trend. Definitionen av LRD förutsätter stationära tidsserier. För att studera effekten av icke-stationaritet på estimatorerna syntetiserade vi därför olika serier med olika sönderfallande eller ökande trender. Vi undersökte också kombinationer av tidigare kategorier (vita Gaussiska buller och cosinusfunktioner) med trend. I varje fall var Whittle uppskattningen konsekvent 0,99; Periodogram metodens uppskattningar för Hurst exponenten var större än 1, medan självlikviditet definieras endast för H < 1. Ingen annan metod gav statistiskt signifikanta uppskattningar.
Trots ett antal skattningar som rapporterats i litteraturen är den exakta uppskattningen av Hurst-parametern fortfarande ett svårt problem även i offline-förhållanden REF.
Long-range dependence ten years of Internet traffic modeling
{'venue': 'IEEE Internet Computing', 'journal': 'IEEE Internet Computing', 'mag_field_of_study': ['Computer Science']}