Lastbalanserad brytare

En belastningsbalanserad switch är en switcharkitektur som garanterar 100 % genomströmning utan någon central medling alls, till priset av att varje paket skickas över tvärbalken två gånger. Belastningsbalanserade switchar är ett föremål för forskning för stora routrar som skalas förbi punkten för praktisk central medling.

Introduktion

Internetroutrar byggs vanligtvis med linjekort anslutna med en switch . Routrar som stöder måttlig total bandbredd kan använda en buss som växel, men routrar med hög bandbredd använder vanligtvis någon form av gränsöverskridande sammankoppling. I en tvärbalk ansluts varje utgång till en ingång, så att information kan flöda genom varje utgång samtidigt. Tvärstaplar som används för paketväxling omkonfigureras vanligtvis tiotals miljoner gånger per sekund. Schemat för dessa konfigurationer bestäms av en central arbiter , till exempel en Wavefront arbiter , som svar på förfrågningar från linjekorten att skicka information till varandra.

Perfekt arbitrering skulle resultera i en genomströmning som endast begränsas av den maximala genomströmningen för varje ingång eller utgång av tvärstången. Till exempel, om all trafik som kommer in på linjekort A och B är avsedd för linjekort C, så begränsas den maximala trafik som kort A och B kan behandla tillsammans av C. Perfekt skiljedom har visat sig kräva enorma mängder beräkning, dvs. skalar upp mycket snabbare än antalet portar på tvärbalken. Praktiska system använder imperfekta skiljedomsheuristiker (som iSLIP) som kan beräknas inom rimlig tid.

En belastningsbalanserad växel är inte relaterad till en belastningsbalanseringsväxel, vilket hänvisar till en sorts router som används som en frontend till en gård av webbservrar för att sprida förfrågningar till en enda webbplats över många servrar.

Grundläggande arkitektur

Som visas i figuren till höger har en lastbalanserad switch N ingångslinjekort, vart och ett med hastighet R, vart och ett anslutet till N buffertar genom en länk med hastighet R/N. Dessa buffertar är i sin tur var och en ansluten till N utgångslinjekort, var och en med hastighet R, genom länkar med hastighet R/N. Buffertarna i mitten är uppdelade i N virtuella utdataköer.

Varje ingångslinjekort sprider sina paket jämnt till de N buffertarna, något som det tydligt kan göra utan konflikt. Varje buffert skriver dessa paket in i ett enda buffertlokalt minne med en kombinerad hastighet av R. Samtidigt skickar varje buffert paket i spetsen för varje virtuell utgångskö till varje utgångslinjekort, återigen med hastigheten R/N till varje kort. Utgångslinjekortet kan tydligt vidarebefordra dessa paket ut på linjen utan tvivel.

Varje buffert i en belastningsbalanserad växel fungerar som en växel med delat minne, och en belastningsbalanserad växel är i huvudsak ett sätt att skala upp en växel med delat minne, till bekostnad av ytterligare latens i samband med vidarebefordran av paket med hastighet R/N dubbelt.

Stanford-gruppen som undersöker lastbalanserade switchar koncentrerar sig på implementeringar där antalet buffertar är lika med antalet linjekort. En buffert är placerad på varje linjekort, och de två sammankopplingsmaskorna är i själva verket samma nät, vilket ger hastigheten 2R/N mellan varje par av linjekort. Men den grundläggande lastbalanserade switcharkitekturen kräver inte att buffertarna placeras på linjekorten, eller att det finns samma antal buffertar och linjekort.

En intressant egenskap hos en lastbalanserad omkopplare är att även om nät som kopplar linjekort till buffertar krävs för att ansluta varje linjekort till varje buffert, finns det inget krav på att nätet ska fungera som en icke-blockerande tvärstång, inte heller att anslutningarna vara lyhörd för alla trafikmönster. En sådan anslutning är mycket enklare än en centralt arbitrerad tvärbalk.

Hålla ordning på paketen

Om två paket som är avsedda för samma utdata anländer rygg mot rygg till ett linjekort, kommer de att spridas till två olika buffertar, som kan ha två olika beläggningar, och så kan paketen ordnas om när de levereras till produktion. Även om omordning är lagligt är det vanligtvis oönskat eftersom TCP inte fungerar bra med omordnade paket.

Genom att lägga till ännu mer latens och buffring kan den belastningsbalanserade switchen upprätthålla paketordning inom flöden med endast lokal information. En sådan algoritm är FOFF (Fully Ordered Frames First). FOFF har ytterligare fördelar att ta bort all sårbarhet för patologiska trafikmönster och tillhandahålla en mekanism för att implementera prioriteringar.

Genomföranden

Single chip-tvärstag plus lastbalanserande arbiter

Stanford Universitys Tiny Tera -projekt (se Abrizio ) introducerade en switcharkitektur som krävde minst två chipdesigner för själva switching-tyget (tvärbalksskivan och arbitern). Att uppgradera arbitern till att inkludera lastbalansering och kombinera dessa enheter kan ha tillförlitlighets-, kostnads- och genomströmningsfördelar.

En enda global router

Eftersom linjekorten i en lastbalanserad switch inte behöver vara fysiskt nära varandra, är en möjlig implementering att använda ett helt kontinent- eller globalt stamnätverk som sammankopplingsnät, och kärnroutrar som "linjekort" . En sådan implementering lider av att ha alla latenser ökade till dubbelt så hög sändningsfördröjning i värsta fall. Men det har ett antal spännande fördelar:

• Stora stamnätspaketnätverk har vanligtvis enorm överkapacitet (10x eller mer) för att hantera ofullständig kapacitetsplanering, överbelastning och andra problem. En belastningsbalanserad switch kan leverera 100 % genomströmning med en överkapacitet på bara 2x, mätt över hela systemet.
• Grunden för stora stamnät är vanligtvis optiska kanaler som inte kan bytas snabbt. Dessa mappar väl till konstanthastighets 2R/N-kanalerna i den lastbalanserade switchens mesh.
• Inga rutttabeller behöver ändras baserat på global trafikstockningsinformation, eftersom det inte finns någon global trafikstockning.
• Omdirigering i fallet med ett nodfel kräver att de optiska kanalernas konfiguration ändras. Men omdirigeringen kan förberäknas (det finns bara ett ändligt antal noder som kan misslyckas), och omdirigeringen orsakar ingen överbelastning som då skulle kräva ytterligare rutttabellsändringar.

externa länkar

• Optimal lastbalansering I. Keslassy, ​​C. Chang, N. McKeown och D. Lee
• Skala internetroutrar med optik I. Keslassy, ​​S. Chuang, K. Yu, D. Miller, M. Horowitz, O. Solgaard och N. McKeown