Långsvanstrafik

En långsvansad eller tungsvansad sannolikhetsfördelning är en som tilldelar relativt höga sannolikheter till regioner långt från medelvärdet eller medianen. En mer formell matematisk definition ges nedan. I samband med teletrafikteknik har ett antal kvantiteter av intresse visat sig ha en långsvansad distribution . Om vi ​​till exempel tar hänsyn till storleken på filer som överförs från en webbserver, så är distributionen, med en god grad av noggrannhet, grovsvansad, det vill säga att det finns ett stort antal små filer som överförs men, av avgörande betydelse, antalet mycket stora filer som överförs är fortfarande en viktig del av den nedladdade volymen.

Många processer är tekniskt långdistansberoende men inte självlika . Skillnaderna mellan dessa två fenomen är subtila. Heavy-tailed hänvisar till en sannolikhetsfördelning och långdistansberoende hänvisar till en egenskap i en tidsserie och därför bör dessa användas med försiktighet och en distinktion bör göras. Termerna är distinkta även om överlagringar av prover från tungsvansfördelningar aggregerar för att bilda långdistansberoende tidsserier.

Dessutom finns det Brownsk rörelse som är självlik men inte långdistansberoende.

Översikt

Utformningen av robusta och pålitliga nätverk och nätverkstjänster har blivit en alltmer utmanande uppgift i dagens internetvärld . För att uppnå detta mål spelar förståelsen av Internettrafikens egenskaper en mer och mer avgörande roll. Empiriska studier av uppmätta trafikspår har lett till ett brett erkännande av självlikhet i nätverkstrafik.

Självliknande Ethernet- trafik uppvisar beroenden över en lång rad tidsskalor. Detta ska jämföras med telefontrafik som är Poisson i sin ankomst- och avgångsprocess.

Med många tidsserier om serien är medelvärde så börjar data se jämnare ut. Men med självliknande data konfronteras man med spår som är taggiga och sprängiga, även i stor skala. Sådant beteende orsakas av starkt beroende i data: stora värden tenderar att komma i kluster, och kluster av kluster etc. Detta kan få långtgående konsekvenser för nätverkets prestanda .

Heavy-tail distributioner har observerats i många naturfenomen inklusive både fysiska och sociologiska fenomen. Mandelbrot etablerade användningen av tunga svansfördelningar för att modellera verkliga fraktala fenomen, t.ex. aktiemarknader, jordbävningar och vädret. Ethernet-, WWW- , SS7- , TCP- , FTP- , TELNET- och VBR- video (digitaliserad video av den typ som sänds över ATM -nätverk) är självliknande.

Självlikhet i paketerade datanätverk kan orsakas av distributionen av filstorlekar, mänsklig interaktion och/eller Ethernet-dynamik. Självliknande och långdistansberoende egenskaper i datornätverk utgör en fundamentalt annorlunda uppsättning problem för människor som analyserar och/eller designar nätverk, och många av de tidigare antaganden som system har byggts på är inte längre giltiga i närvaro av självlikhet.

Kortdistansberoende vs långdistansberoende

Lång- och kortdistansberoende processer kännetecknas av sina autokovariansfunktioner .

I kortdistansberoende processer minskar kopplingen mellan värden vid olika tidpunkter snabbt när tidsskillnaden ökar.

• Summan av autokorrelationsfunktionen över alla fördröjningar är ändlig.
• När fördröjningen ökar försvinner autokorrelationsfunktionen för kortdistansberoende processer snabbt.

I långdistansprocesser är korrelationerna på längre tidsskalor mer signifikanta.

• Arean under autokorrelationsfunktionen summerad över alla fördröjningar är oändlig.
• Förfallet av autokorrelationsfunktionen antas ofta ha den specifika funktionella formen,

$\rho (k)\sim k^{-\alpha }$

där ρ( k ) är autokorrelationsfunktionen vid en fördröjning k , α är en parameter i intervallet (0,1) och ~ betyder asymptotiskt proportionellt mot när k närmar sig oändligheten.

Långtidsberoende som en konsekvens av matematisk konvergens

Sådan effektlagsskalning av autokorrelationsfunktionen kan visas vara bivillkorligt relaterad till ett potenslagsförhållande mellan variansen och medelvärdet, när den utvärderas från sekvenser med metoden att expandera bins . Denna varians för att betyda maktlag är en inneboende egenskap hos en familj av statistiska fördelningar som kallas Tweedies exponentiella spridningsmodeller . På samma sätt som den centrala gränssatsen förklarar hur vissa typer av slumpmässiga data konvergerar mot formen av en normalfördelning, finns det en relaterad sats, Tweedie-konvergenssatsen som förklarar hur andra typer av slumpmässiga data kommer att konvergera mot formen av dessa Tweedie-fördelningar, och uttrycker följaktligen både variansen till medelkraftlag och en potenslagsavklingning i deras autokorrelationsfunktioner.

Poissondistributionen och trafiken

Innan heavy-tail-distributionen introduceras matematiskt, kommer den minneslösa Poisson-distributionen, som används för att modellera traditionella telefoninät, kort att gå igenom nedan. För mer information, se artikeln om Poisson-distributionen .

Att anta rena slumpmässiga ankomster och rena slumpmässiga uppsägningar leder till följande:

• Antalet ankommande samtal under en given tid har en Poisson-fördelning, dvs.

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

där a är antalet samtalsankomster och $\mu$ är medelantalet samtalsankomster i tiden T . Av denna anledning kallas ren-slumpmässig trafik också som Poisson-trafik.

• Antalet samtalsavgångar under en given tid har också en Poisson-fördelning, dvs.

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

där d är antalet samtalsavgångar och $\lambda$ är medelantalet samtalsavgångar i tiden T .

• Intervallet, T , mellan samtalsankomster och -avgångar är intervall mellan oberoende, identiskt fördelade slumpmässiga händelser. Det kan visas att dessa intervall har en negativ exponentialfördelning, dvs.

$P[T\geq \ t]=e^{\frac {-t}{h}},$

där h är den genomsnittliga hålltiden (MHT).

Information om grunderna för statistik och sannolikhetsteori finns i avsnittet med externa länkar .

Den tunga svansfördelningen

Heavy-tail distributioner har egenskaper som skiljer sig kvalitativt från vanliga (minneslösa) distributioner som exponentialfördelningen .

Hurst -parametern H är ett mått på nivån av självlikhet för en tidsserie som uppvisar långdistansberoende, till vilken tungsvansfördelningen kan tillämpas. H tar på värden från 0,5 till 1. Ett värde på 0,5 indikerar att data är okorrelerade eller endast har korta korrelationer. Ju närmare H är 1, desto större är graden av persistens eller långdistansberoende.

Typiska värden för Hurst-parametern, H :

• Varje ren slumpmässig process har H = 0,5
• Fenomen med H > 0,5 har typiskt en komplex processstruktur.

En fördelning sägs vara tungsvansad om:

$P[X>x]\sim x^{-\alpha },\ {\text{as}}\ x\ till \infty ,0<\alpha <2$

Detta innebär att oavsett fördelningen för små värden av den slumpmässiga variabeln, om den asymptotiska formen på fördelningen är hyperbolisk, är den tungsvansad. Den enklaste tungsvansfördelningen är Pareto-fördelningen som är hyperbolisk över hela sitt område. Komplementära fördelningsfunktioner för exponential- och Pareto-fördelningarna visas nedan. Till vänster visas en graf över fördelningarna som visas på linjära axlar, som spänner över en stor domän. Till höger om den finns en graf över de komplementära fördelningsfunktionerna över en mindre domän och med ett logaritmiskt område.

Om logaritmen för intervallet för en exponentialfördelning tas, är den resulterande plotten linjär. Däremot är distributionen med tung svans fortfarande krökt. Dessa egenskaper kan tydligt ses på grafen ovan till höger. Ett kännetecken för långsvansfördelningar är att om logaritmen för både intervallet och domänen tas, är svansen på långsvansfördelningen ungefär linjär över många storleksordningar. I grafen ovan till vänster uppfylls inte villkoret för förekomsten av en tung svansfördelning, som tidigare presenterats, av kurvan märkt "Gamma-Exponential Tail".

Sannolikhetsmassfunktionen för en tungsvansfördelning ges av :

$p(x)=\alpha k^{\alpha }x^{-\alpha -1},\ \ alfa ,k>0,\ x\geq k$

och dess kumulativa fördelningsfunktion ges av:

$F(x)=P[X\leq \ x]=1-\left({\frac {k}{x} }\right)^{\alpha }$

där k representerar det minsta värde som den slumpmässiga variabeln kan ta.

Läsare som är intresserade av en mer rigorös matematisk behandling av ämnet hänvisas till avsnittet med externa länkar .

Vad orsakar långsvanstrafik?

Generellt finns det tre huvudteorier för orsakerna till långsvanstrafik (se en genomgång av alla tre orsakerna). För det första är en orsak baserad i applikationslagret som teoretiserar att användarsessionslängderna varierar med en long-tail-distribution på grund av filstorleksfördelningen. Om distributionen av filstorlekar är grovsvansad kommer överlagringen av många filöverföringar i en klient/server- nätverksmiljö att vara långdistansberoende. Dessutom är denna orsaksmekanism robust med avseende på förändringar i nätverksresurser ( bandbredd och buffertkapacitet ) och nätverkstopologi . Detta är för närvarande den mest populära förklaringen i ingenjörslitteraturen och den med flest empiriska bevis genom observerade filstorleksfördelningar.

För det andra är en transportlagerorsak som teoretiserar att återkopplingen mellan flera TCP-strömmar på grund av TCP:s algoritm för att undvika överbelastning i situationer med måttlig till hög paketförlust orsakar självliknande trafik eller åtminstone tillåter den att spridas. Detta tros dock endast vara en betydande faktor vid relativt korta tidsskalor och inte den långsiktiga orsaken till självliknande trafik.

Slutligen är en teoretiserad länklagerorsak som baseras på fysiksimuleringar av paketförmedlingsnätverk på simulerade topologier. Vid en kritisk paketskapningshastighet blir flödet i ett nätverk överbelastat och uppvisar 1/f-brus och långa trafikegenskaper. Det har förekommit kritik mot dessa typer av modeller, men som orealistiska eftersom nätverkstrafiken är långsvansad även i icke-överbelastade regioner och på alla trafiknivåer.

Simulering visade att långdistansberoende kunde uppstå i kölängdsdynamiken vid en given nod (en enhet som överför trafik) inom ett kommunikationsnät även när trafikkällorna är fria från långdistansberoende. Mekanismen för detta tros relatera till feedback från routingeffekter i simuleringen.

Modellering av långsvanstrafik

Modellering av långsvanstrafik är nödvändig så att nätverk kan tillhandahållas baserat på exakta antaganden om den trafik som de bär. Dimensionering och försörjning av nät som transporterar long tail-trafik diskuteras i nästa avsnitt.

Eftersom (till skillnad från traditionell telefonitrafik) paketerad trafik uppvisar självliknande eller fraktala egenskaper, är konventionella trafikmodeller inte tillämpliga på nät som bär långsvanstrafik. Tidigare analytiskt arbete utfört i internetstudier har antagit antaganden som exponentiellt distribuerade paketinter-ankomster, och slutsatser som dragits under sådana antaganden kan vara missvisande eller felaktiga i närvaro av tunga svansfördelningar.

Man har länge insett att effektiv och korrekt modellering av olika verkliga fenomen måste inkludera det faktum att observationer gjorda på olika skalor var och en bär viktig information. I de flesta enkla termer är det ofta användbart att representera data i stor skala med dess medelvärde (som en genomsnittlig inkomst eller ett genomsnittligt antal klienter per dag), men det kan vara olämpligt (t.ex. i samband med buffring eller väntande köer).

Med konvergensen av röst och data kommer det framtida multitjänstnätet att baseras på paketerad trafik, och modeller som exakt återspeglar karaktären hos långsvanstrafik kommer att krävas för att utveckla, designa och dimensionera framtida multitjänstnät. Vi söker en motsvarighet till Erlang -modellen för kretskopplade nätverk.

Det finns inte ett överflöd av tunga modeller med rika uppsättningar av tillhörande dataanpassningstekniker. En tydlig modell för fraktaltrafik har ännu inte vuxit fram och det finns inte heller någon bestämd riktning mot en tydlig modell. Att härleda matematiska modeller som korrekt representerar långsvanstrafik är ett fruktbart forskningsområde.

Gaussiska modeller , även långdistansberoende Gaussiska modeller, kan inte exakt modellera aktuell internettrafik. Klassiska modeller av tidsserier som Poisson och ändliga Markov-processer förlitar sig starkt på antagandet om oberoende , eller åtminstone svagt beroende. Poisson- och Markovrelaterade processer har dock använts med viss framgång. Icke-linjära metoder används för att producera pakettrafikmodeller som kan replikera både kort- och långdistansberoende strömmar.

Ett antal modeller har föreslagits för uppgiften att modellera långsvanstrafik. Dessa inkluderar följande:

• Bråkdel ARIMA
• fraktionell rörelse
• Itererade kaotiska kartor
• Oändliga Markov-modulerade processer
• Poisson Pareto Burst Processes (PPBP)
• Markov Modulated Poisson Processes (MMPP)
• Multifraktalmodeller
• Matrix modeller
• Wavelet modellering
• Tweedie-distributioner

Det finns ingen enighet om vilken av de konkurrerande modellerna som är lämplig, men Poisson Pareto Burst Process (PPBP), som är en M/G/ ${\displaystyle {\mathcal {1}}}-$ process, är kanske den mest framgångsrika modellen för att datum. Den har visat sig uppfylla de grundläggande kraven för en enkel, men exakt, modell av långsvanstrafik.

Slutligen presenteras resultat från simuleringar med $\alpha$ -stabila stokastiska processer för modellering av trafik i bredbandsnätverk. Simuleringarna jämförs med en mängd olika empiriska data (Ethernet, WWW, VBR Video).

Nätverksprestanda

I vissa fall kan en ökning av Hurst-parametern leda till en minskning av nätverkets prestanda. Omfattningen i vilken tunga svansar försämrar nätverkets prestanda bestäms av hur väl överbelastningskontroll kan forma källtrafiken till en genomsnittlig konstant utström samtidigt som information bevaras. Trängselkontroll av tungstjärtad trafik diskuteras i följande avsnitt.

Trafikens självlikhet påverkar negativt primära prestandamått som köstorlek och paketförlusthastighet. Kölängdsfördelningen av långsvanstrafik avtar långsammare än med Poisson-källor. Långtidsberoende antyder dock ingenting om dess kortsiktiga korrelationer som påverkar prestanda i små buffertar. För tungsvansad trafik uppstår extremt stora skurar oftare än vid lättsvansad trafik. Dessutom förstärker aggregering av strömmar av long-tail-trafik vanligtvis självlikheten (" burstiness ") snarare än att jämna ut den, vilket förvärrar problemet.

Grafen ovan till höger, hämtad från, presenterar en köprestandajämförelse mellan trafikströmmar av varierande grad av självlikhet. Notera hur köstorleken ökar med ökande självlikhet mellan data, för varje given kanalanvändning, vilket försämrar nätverkets prestanda.

I den moderna nätverksmiljön med multimedia och andra QoS- känsliga trafikströmmar som omfattar en växande del av nätverkstrafiken, är andra ordningens prestandamått i form av " jitter " såsom fördröjningsvariationer och paketförlustvariationer viktiga för provisioneringsanvändarspecificerade QoS. Självliknande utbrott förväntas ha en negativ inverkan på andra ordningens prestationsmått.

Paketväxlingsbaserade tjänster, såsom Internet (och andra nätverk som använder IP ) är tjänster som gör det bäst, så försämrad prestanda, även om den är oönskad, kan tolereras. Men eftersom anslutningen är kontrakterad måste ATM-nätverk hålla förseningar och jitter inom förhandlade gränser.

Självliknande trafik uppvisar ihållande klustring vilket har en negativ inverkan på nätverkets prestanda.

• Med Poisson-trafik (finns i konventionella telefoninät ) sker klustring på kort sikt men jämnar ut sig på lång sikt.
• Med long-tail-trafik kan det bursty-beteendet i sig vara bursty, vilket förvärrar klustringsfenomenen och försämrar nätverkets prestanda.

Många aspekter av nätverkets kvalitet på tjänsten beror på att hantera trafiktoppar som kan orsaka nätverksfel, som t.ex

• Cell-/paketförlust och köspill
• Överträdelse av fördröjningsgränser t.ex. i video
• Värsta fall vid statistisk multiplexering

Poisson-processer sköter sig väl eftersom de är tillståndslösa och toppbelastningen upprätthålls inte, så köerna fylls inte. Med ordning på lång räckvidd varar toppar längre och har större inverkan: jämvikten skiftar ett tag.

På grund av de ökade krav som långsvanstrafik ställer på nätverksresurser, måste nätverk vara noggrant försedda för att säkerställa att servicekvalitet och servicenivåavtal uppfylls. Följande underavsnitt handlar om tillhandahållande av standardnätverksresurser, och underavsnittet efter det tittar på provisionering av webbservrar som bär en betydande mängd long-tail-trafik.

Nätverksprovisionering för long-tail-trafik

För nätverksköer med långdistansberoende ingångar, innebär den kraftiga ökningen av köfördröjningar vid ganska låga utnyttjandenivåer och långsamt avtagande av kölängder att en inkrementell förbättring av förlustprestanda kräver en betydande ökning av buffertstorleken.

Medan genomströmningen minskar gradvis när självlikheten ökar, ökar köfördröjningen mer drastiskt. När trafiken är siglik, finner vi att köfördröjningen växer proportionellt mot buffertkapaciteten som finns i systemet. Sammantaget har dessa två observationer potentiellt allvarliga konsekvenser för QoS-bestämmelser i nätverk. För att uppnå en konstant nivå av genomströmning eller paketförlust när självlikheten ökar, behövs extremt stor buffertkapacitet. Ökad buffring leder dock till stora köfördröjningar och sålunda gör självlikhet avsevärt brantare avvägningskurvan mellan genomströmning/paketförlust och fördröjning.

ATM kan användas i telekommunikationsnätverk för att övervinna problem med andra ordningens prestandamått. Den korta cellen med fast längd som används i ATM minskar fördröjningen och framför allt jitter för fördröjningskänsliga tjänster som röst och video.

Webbplatsförsörjning för långsvanstrafik

Komplexiteter i arbetsbelastningsmönster (till exempel sprängfyllda ankomstmönster) kan avsevärt påverka resursbehov, genomströmning och fördröjningen av användarförfrågningar, i form av högre genomsnittliga svarstider och högre svarstidsvarians . Utan adaptiv, optimal hantering och kontroll av resurser är SLA baserade på svarstid omöjliga. Kapacitetskraven på platsen ökar samtidigt som dess förmåga att tillhandahålla acceptabla nivåer av prestanda och tillgänglighet minskar. Tekniker för att kontrollera och hantera long-tail-trafik diskuteras i följande avsnitt.

Förmågan att korrekt prognostisera förfrågningsmönster är ett viktigt krav för kapacitetsplanering. En praktisk konsekvens av bristningar och tungsvansade och korrelerade ankomster är svårigheter med kapacitetsplanering.

När det gäller SLA:er kräver samma servicenivå för distributioner med tunga svansar en mer kraftfull uppsättning servrar, jämfört med fallet med oberoende lättsvansad förfrågningstrafik. För att garantera bra prestanda måste fokus läggas på varaktigheten av topptrafik eftersom det är de enorma skurarna av förfrågningar som mest försämrar prestandan. Det är därför som vissa upptagna platser kräver mer huvudutrymme (reservkapacitet) för att hantera volymerna; till exempel reserverar en högvolym onlinehandelsplats reservkapacitet med ett förhållande på tre till ett.

Hänvisning till ytterligare information om effekten av långdistansberoende på nätverksprestanda finns i avsnittet med externa länkar .

Kontrollerar långsvanstrafik

Med tanke på den överallt där skalinvariant burstiness observeras över olika nätverkssammanhang, har det blivit ett viktigt problem att hitta en effektiv trafikkontrollalgoritm som kan detektera och hantera självliknande trafik. Problemet med att kontrollera självliknande nätverkstrafik är fortfarande i sin linda.

Trafikstyrning för självliknande trafik har utforskats på två fronter: dels som en förlängning av prestandaanalys i resursförsörjningssammanhang, och dels ur trafikkontrollperspektivet med flera tidsskalor där korrelationsstrukturen på stora tidsskalor aktivt utnyttjas för att förbättra nätverkets prestanda.

Resursförsörjningsmetoden försöker identifiera den relativa nyttan av de två huvudsakliga nätverksresurstyperna – bandbredd och buffertkapacitet – med avseende på deras minskande effekter på självlikhet, och förespråkar en dimensioneringspolicy för liten buffert/stor bandbredd. Medan resursförsörjning är öppen till sin natur, utnyttjar trafikkontroll i flera tidsskaliga den långdistanskorrelationsstruktur som finns i självliknande trafik. Överbelastningskontroll kan utövas samtidigt på flera tidsskalor, och genom att samarbeta med information som extraheras vid olika tidsskalor, uppnå betydande prestandavinster.

Ett annat tillvägagångssätt som används för att kontrollera långsvanstrafik gör trafikkontroller medvetna om arbetsbelastningsegenskaper. Till exempel, när TCP anropas i HTTP i samband med webbklient/serverinteraktioner, överförs eller görs tillgänglig storleken på filen som transporteras (vilket är känt på servern) för protokoll i transportlagret , inklusive val av alternativa protokoll, för effektivare datatransport. För korta filer, som utgör huvuddelen av anslutningsförfrågningar i grova filstorleksfördelningar av webbservrar, kan komplicerad återkopplingskontroll förbigås till förmån för lätta mekanismer i en anda av optimistisk kontroll, vilket kan resultera i förbättrat bandbreddsutnyttjande.

Det visade sig att det enklaste sättet att kontrollera pakettrafik är att begränsa köernas längd. Långa köer i nätverket uppstår undantagslöst hos värdar (enheter som kan sända och ta emot paket). Överbelastningskontroll kan därför uppnås genom att minska hastigheten på paketproduktionen hos värdar med långa köer.

Långdistansberoende och dess utnyttjande för trafikstyrning lämpar sig bäst för flöden eller förbindelser vars livslängd eller anslutningslängd är långvarig.

Se även

• Elefantflöde
• Trafikgenereringsmodell
• Tweedie-distributioner