Trängsel i nätverket - Network congestion

Trängsel i nätverk i datanätverk och köteori är den minskade servicekvaliteten som uppstår när en nätverksnod eller länk bär mer data än den kan hantera. Typiska effekter inkluderar köfördröjning , paketförlust eller blockering av nya anslutningar. En konsekvens av trängsel är att en ökad ökning av erbjuden last antingen bara leder till en liten ökning eller till och med en minskning av nätverkets genomströmning .

Nätverksprotokoll som använder aggressiva vidarebefordran för att kompensera för paketförlust på grund av trängsel kan öka trängseln, även efter att den initiala belastningen har reducerats till en nivå som normalt inte skulle ha orsakat nätstopp. Sådana nätverk uppvisar två stabila tillstånd under samma belastningsnivå. Det stabila tillståndet med låg genomströmning kallas kongestiv kollaps .

Nätverk använder överbelastningskontroll och teknik för att undvika trängsel för att undvika kollaps. Dessa inkluderar: exponentiell backoff i protokoll som CSMA/CA i 802.11 och liknande CSMA/CD i det ursprungliga Ethernet , fönsterreduktion i TCP och rättvis kö i enheter som routrar och nätverksväxlar . Andra tekniker som hanterar trängsel inkluderar prioritetsscheman som överför vissa paket med högre prioritet framför andra och den uttryckliga fördelningen av nätverksresurser till specifika flöden genom användning av antagningskontroll .

Nätverkskapacitet

Nätverksresurser är begränsade, inklusive routerns bearbetningstid och länkgenomströmning . Resurstvister kan förekomma i nätverk under ett antal vanliga omständigheter. Ett trådlöst LAN fylls enkelt av en enda persondator. Även på snabba datanätverk kan ryggraden lätt överbelastas av några servrar och klient -datorer. Denial-of-service-attacker från botnät kan fylla även de största nätverkslänkar för Internet-ryggrad , vilket genererar storskalig nätstopp. I telefonnät kan en massanropshändelse överväldiga digitala telefonkretsar.

Congestiv kollaps

Congestiv kollaps (eller trängselkollaps) är det tillstånd där trängsel förhindrar eller begränsar användbar kommunikation. Trängselkollaps inträffar i allmänhet vid kvävningspunkter i nätverket, där inkommande trafik överstiger utgående bandbredd. Anslutningspunkter mellan ett lokalt nätverk och ett brett nätverk är vanliga kvävningspunkter. När ett nätverk befinner sig i detta tillstånd, sätter det sig i ett stabilt tillstånd där trafikbehovet är högt men lite användbar genomströmning är tillgänglig, under vilken paketfördröjning och förlust uppstår och servicekvaliteten är extremt dålig.

Congestiv kollaps identifierades som ett möjligt problem 1984. Det observerades första gången på det tidiga internet i oktober 1986, när NSFnet fas-I-ryggrad minskade tre storleksordningar från dess kapacitet på 32 kbit/s till 40 bit/s, vilket fortsatte tills slutnoder började implementera Van Jacobson och Sally Floyds överbelastningskontroll mellan 1987 och 1988. När fler paket skickades än vad som kunde hanteras av mellanrouter slängde de mellanliggande routrarna många paket och väntade sig att slutpunkterna i nätverket skulle sända om information. Tidiga TCP -implementeringar hade emellertid dåligt vidaresändningsbeteende. När denna paketförlust inträffade skickade slutpunkterna extra paket som upprepade den förlorade informationen, vilket fördubblade den inkommande hastigheten.

Trängselkontroll

Trängselkontroll modulerar trafikinträde i ett telekommunikationsnät för att undvika överbelastning som orsakas av överabonnemang. Detta uppnås vanligtvis genom att minska pakethastigheten. Medan trängselkontroll hindrar avsändare från att överväldiga nätverket , hindrar flödeskontroll avsändaren från att överväldiga mottagaren .

Teori om trängselkontroll

Teorin om överbelastningskontroll var banbrytande av Frank Kelly , som tillämpade mikroekonomisk teori och konvex optimeringsteori för att beskriva hur individer som kontrollerar sina egna priser kan interagera för att uppnå en optimal nätverksövergripande prisallokering. Exempel på optimal räntefördelning är max-min rättvis tilldelning och Kellys förslag om proportionellt rättvis tilldelning, även om många andra är möjliga.

Låt vara flödeshastigheten , var länkens kapacitet och var 1 om flödet använder länk och 0 annars. Låt , och vara motsvarande vektorer och matris. Låt oss vara en ökande, strikt konkav funktion , kallad verktyget , som mäter hur stor nytta en användare får genom att sända i takt . Den optimala räntefördelningen uppfyller då ${\ displaystyle x_ {i}}$${\ displaystyle i}$${\ displaystyle c_ {l}}$${\ displaystyle l}$${\ displaystyle r_ {li}}$${\ displaystyle i}$${\ displaystyle l}$${\ displaystyle x}$${\ displaystyle c}$${\ displaystyle R}$${\ displaystyle U (x)}$${\ displaystyle x}$

${\ displaystyle \ max \ limit _ {x} \ sum _ {i} U (x_ {i})}$

Så att ${\ displaystyle Rx \ leq c}$

Den Lagrange dubbla om detta problem frikopplar, så att varje flöde sätter sin egen takt, baserat enbart på ett pris signaleras av nätverket. Varje länk kapacitet innebär en begränsning, som ger upphov till en lagrangemultiplikator , . Summan av dessa multiplikatorer är det pris som flödet svarar på. ${\ displaystyle p_ {l}}$${\ displaystyle y_ {i} = \ sum _ {l} p_ {l} r_ {li},}$

Trängselkontroll blir sedan en distribuerad optimeringsalgoritm. Många nuvarande algoritmer för överbelastningskontroll kan modelleras i detta ramverk, antingen som förlustsannolikhet eller köfördröjning vid länk . En stor svaghet är att den tilldelar samma pris till alla flöden, medan glidande fönsters flödeskontroll orsakar spränghet som får olika flöden att observera olika förluster eller fördröjningar vid en given länk. ${\ displaystyle p_ {l}}$${\ displaystyle l}$

Klassificering av algoritmer för överbelastningskontroll

Bland sätten att klassificera algoritmer för överbelastningskontroll är:

• Efter typ och mängd feedback från nätverket: Förlust; dröjsmål; enstaka eller flera bitars tydliga signaler
• Genom inkrementell distribution: Endast avsändare behöver ändras; avsändare och mottagare behöver ändras; bara routern behöver ändras; avsändare, mottagare och routrar behöver ändras.
• Enligt prestanda: produktnät med hög bandbreddfördröjning; förlorande länkar; rättvisa; fördel med korta flöden; länkar med variabel ränta
• Enligt rättvisekriterium: Max-min rättvisa; proportionellt rättvis; kontrollerad fördröjning

Begränsning

Mekanismer har uppfunnits för att förhindra överbelastning av nätverket eller för att hantera en nätverkskollaps:

• Nätverksschemaläggare  - aktiv köhantering som ordnar om eller selektivt tappar nätverkspaket i närvaro av trängsel
• Explicit Congestion Notification  - en förlängning till IP- och TCP -kommunikationsprotokoll som lägger till en flödeskontrollmekanism
• TCP -överbelastningskontroll  - olika implementeringar av ansträngningar för att hantera nätstopp

Det korrekta slutpunktsbeteendet är vanligtvis att upprepa tappad information, men gradvis sakta upprepningshastigheten. Förutsatt att alla slutpunkter gör detta, ökar trängseln och nätverket återupptar normalt beteende. Andra strategier som långsam start säkerställer att nya anslutningar inte överväldigar routern innan detektering av överbelastning startar.

Vanliga mekanismer för att undvika trafikstockningar inkluderar rättvis kö och andra schemaläggningsalgoritmer och slumpmässig tidig upptäckt (RED) där paket slumpmässigt släpps när överbelastning detekteras. Detta utlöser proaktivt slutpunkterna till långsam överföring innan trängselkollaps inträffar.

Vissa end-to-end-protokoll är utformade att fungera bra under överbelastade förhållanden; TCP är ett välkänt exempel. De första TCP -implementeringarna för att hantera trängsel beskrevs 1984, men Van Jacobsons införande av en öppen källkodslösning i Berkeley Standard Distribution UNIX (" BSD ") 1988 gav först bra beteende.

UDP kontrollerar inte trängsel. Protokoll byggda ovanpå UDP måste hantera trängsel oberoende. Protokoll som sänder med en fast hastighet, oberoende av trängsel, kan vara problematiska. Strömningsprotokoll i realtid, inklusive många Voice over IP- protokoll, har den här egenskapen. Sålunda måste särskilda åtgärder, såsom servicekvalitet, vidtas för att förhindra att paket tappas i närvaro av trängsel.

Praktisk undvikande av överbelastning av nätverk

Anslutningsorienterade protokoll , till exempel det allmänt använda TCP- protokollet, övervakar paketförlust eller köfördröjning för att justera överföringshastigheten. Olika processer för att undvika trafikstockningar stöder olika avvägningar.

Undvikande av överbelastning av TCP/IP

Den TCP undvikande trängsel algoritm är den primära grunden för stockningskontroll på Internet.

Problem uppstår när samtidiga TCP-flöden upplever svansdroppar , särskilt när bufferbloat finns. Denna fördröjda paketförlust stör TCP: s automatiska överbelastning. Alla flöden som upplever denna paketförlust börjar en TCP -omskolning i samma ögonblick - detta kallas TCP global synkronisering .

Aktiv köhantering

Aktiv köhantering (AQM) är omordning eller släppning av nätverkspaket inuti en överföringsbuffert som är associerad med en nätverksgränssnittskontroller (NIC). Denna uppgift utförs av nätverksschemaläggaren .

Slumpmässig tidig upptäckt

En lösning är att använda slumpmässig tidig upptäckt (RED) på nätverksutrustningens utgångskö. På nätverksmaskinvaruportar med mer än en utgångskö kan vägd slumpmässig tidig upptäckt (WRED) användas.

RÖD indirekt signalerar TCP -sändare och mottagare genom att tappa några paket, t.ex. när den genomsnittliga kölängden är mer än en tröskel (t.ex. 50%) och raderar linjärt eller kubiskt fler paket, upp till t.ex. 100%, när kön fylls ytterligare.

Robust slumpmässig tidig upptäckt

Den robusta algoritmen för slumpmässig tidig upptäckt (RRED) föreslogs för att förbättra TCP-genomströmningen mot denial-of-service-attacker (DoS) -attacker, särskilt low-rate denial-of-service (LDoS) -attacker. Experiment bekräftade att RED-liknande algoritmer var sårbara under LDoS-attacker på grund av den oscillerande TCP-köstorleken som orsakades av attackerna.

Flödesbaserad WRED

Vissa nätverksutrustningar är utrustade med portar som kan följa och mäta varje flöde och därigenom kunna signalera ett för stort bandbreddsflöde enligt viss servicekvalitet. En policy kan sedan dela bandbredden mellan alla flöden med vissa kriterier.

Explicit Trafikmeddelande

Ett annat tillvägagångssätt är att använda Explicit Congestion Notification (ECN). ECN används endast när två värdar signalerar att de vill använda det. Med denna metod används en protokollbit för att signalera uttrycklig trängsel. Detta är bättre än den indirekta överbelastningsmeddelandet som signaleras av paketförlust av RED/WRED -algoritmerna, men det kräver stöd av båda värdarna.

När en router får ett paket som är märkt som ECN-kompatibelt och routern förutser överbelastning sätter den ECN-flaggan och meddelar avsändaren om överbelastning. Avsändaren bör svara genom att minska sin överföringsbandbredd, t.ex. genom att sänka sin sändningshastighet genom att minska TCP -fönsterstorleken eller på annat sätt.

Formning av TCP -fönster

Undvikande av trängsel kan uppnås effektivt genom att minska trafiken. När en applikation begär en stor fil, grafik eller webbsida, brukar det annonsera ett fönster på mellan 32K och 64K. Detta resulterar i att servern skickar ett fullständigt datafönster (förutsatt att filen är större än fönstret). När många applikationer samtidigt begär nedladdning kan dessa data skapa en överbelastningspunkt hos en uppströmsleverantör. Genom att minska fönsterannonsen skickar fjärrservrarna mindre data, vilket minskar trängseln.

Bakåt ECN

Backward ECN (BECN) är en annan föreslagen mekanism för överbelastning av överbelastning. Den använder ICMP -källkyldningsmeddelanden som en IP -signalmekanism för att implementera en grundläggande ECN -mekanism för IP -nätverk, vilket håller trafikmeddelanden på IP -nivå och kräver ingen förhandling mellan nätverksslutpunkter. Effektiva överbelastningsmeddelanden kan spridas till transportlagerprotokoll, till exempel TCP och UDP, för lämpliga justeringar.

Biverkningar av undvikande av kongestiv kollaps

Radiolänkar

Protokollen som undviker kongestiv kollaps antar generellt att dataförlust orsakas av trängsel. På trådbundna nätverk är fel under överföringen sällsynta. WiFi , 3G och andra nätverk med ett radiolager är mottagliga för dataförlust på grund av störningar och kan uppleva dålig genomströmning i vissa fall. TCP-anslutningarna som körs över ett radiobaserat fysiskt lager ser dataförlusten och tenderar att felaktigt tro att trängsel uppstår.

Kortlivade förbindelser

Slow-start-protokollet fungerar dåligt för korta anslutningar. Äldre webbläsare skapade många kortlivade anslutningar och öppnade och stängde anslutningen för varje fil. Detta höll de flesta anslutningarna i långsamt startläge. Initial prestanda kan vara dålig, och många anslutningar kommer aldrig ur den långsamma startregimen, vilket väsentligt ökar latensen. För att undvika detta problem öppnar moderna webbläsare antingen flera anslutningar samtidigt eller återanvänder en anslutning för alla filer som begärs från en viss server.

Antagningskontroll

Antagningskontroll är alla system som kräver att enheterna får tillstånd innan nya nätverksanslutningar upprättas. Om den nya anslutningen riskerar att skapa trängsel kan tillstånd nekas. Exempel inkluderar Contention-Free Transmission Opportunities (CFTXOPs) i ITU-T G.hn- standarden för hemnätverk över äldre ledningar, Resource Reservation Protocol för IP-nätverk och Stream Reservation Protocol för Ethernet .

Se även

• Bandbreddshantering  - Process för att mäta och styra kommunikationen på en nätverkslänk, för att undvika att fylla länken till kapacitet eller överfylla länken
• Kaskadfel  - Systemisk risk för fel
• Choke exchange  - telefonväxel utformad för att hantera många samtidiga samtalsförsök
• Erlang (enhet)  - Lastmått inom telekommunikation
• Sorcerer's Apprentice Syndrome  - Nätverksprotokollfel i originalversionerna av TFTP
• Teletrafikteknik  - Tillämpning av trafikkonstruktionsteori för telekommunikation
• Thrashing  - Dator utbyter ständigt data mellan minne och lagring och lämnar liten kapacitet för produktiv behandling
• Trafikformning  - teknik för bandbreddshantering
• Pålitlighet (datornätverk)

Referenser

externa länkar

• Floyd, S. och K. Fall, Främja användningen av End-to-End Congestion Control på Internet (IEEE/ACM Transactions on Networking, augusti 1999)
• Sally Floyd, On the Evolution of End-to-end Congestion Control in the Internet: An Idiosyncratic View (IMA Workshop on Scaling Phenomena in Communication Networks, oktober 1999) ( pdf- format )
• Linjär term: Kö
• Pierre-Francois Quet, Sriram Chellappan, Arjan Durresi, Mukundan Sridharan, Hitay Ozbay, Raj Jain, "Riktlinjer för optimering av multi-level ECN, med hjälp av vätskeflödesbaserad TCP-modell"
• Sally Floyd, Ratul Mahajan, David Wetherall: RED-PD: RED with Preferential Dropping
• En generisk enkel RÖD simulator för utbildningsändamål av Mehmet Suzen
• Tillvägagångssätt för överbelastningskontroll i paketnätverk
• Papper i trängselkontroll
• Slumpmässig tidig upptäcktshemsida
• Hemsida för aviserad trängsel
• TFRC: s hemsida
• AIMD-FC-hemsida
• permanent död länk ] TCP -trängselkontrollsimulering: Snabb återhämtning
• Nya publikationer i lågfrekventa denial-of-service-attacker (DoS)