Annons för rutt med delad horisont

Inom datornätverk är ruttannonsering med delad horisont en metod för att förhindra routingslingor i distans-vektor-routingprotokoll genom att förbjuda en router från att annonsera en rutt tillbaka till gränssnittet från vilket den lärdes.

Konceptet föreslogs 1974 av Torsten Cegrell och implementerades ursprungligen i det ARPANET -inspirerade svenska nätverket TIDAS.

Terminologi

Här är lite grundläggande terminologi:

Ruttförgiftning : om en nod N får reda på att dess rutt till en destination D inte går att nå, informera alla noder i nätverket om det genom att skicka ett meddelande till dem som säger att avståndet från N till D, som uppfattas av N, är oändligt.

Regel för delad horisont: om en nod N använder gränssnitt I för att sända till en given destination D, ska N inte skicka genom I ny information om D.

Omvänd regel för gift: om en nod N använder gränssnitt I för att sända till en given destination D, N skickar genom I informationen att dess kostnad att gå till D är oändlig.

Medan under delad horisont N inte sänder någon information genom I, under gift omvänd nod berättar N en vit lögn.

Exempel

I detta exempel dirigerar nätverksnod A paket till nod B för att nå nod C. Länkarna mellan noderna är distinkta punkt-till-punkt-länkar.

Enligt regeln om delad horisont annonserar nod A inte sin rutt för C (nämligen A till B till C ) tillbaka till B . På ytan verkar detta överflödigt eftersom B aldrig kommer att rutta via nod A eftersom rutten kostar mer än den direkta rutten från B till C . Men om länken mellan B och C går ner, och B hade fått en rutt från A till C , skulle B kunna sluta använda den vägen via A . A skulle skicka paketet direkt tillbaka till B och skapa en loop. Detta är Count to Infinity-problemet . Med regeln om delad horisont på plats kan det här specifika loopscenariot inte inträffa, vilket förbättrar konvergenstiden i komplexa, mycket redundanta miljöer.

Rutning med delad horisont med omvänd gift är en variant av ruttannonsering med delad horisont där en router aktivt annonserar rutter som oåtkomliga över gränssnittet över vilket de lärdes in genom att ställa in ruttmåttet till oändligt (16 för RIP ) . Effekten av ett sådant tillkännagivande är att de flesta slingrutter omedelbart tas bort innan de kan spridas genom nätverket.

Den största nackdelen med poison reverse är att det avsevärt kan öka storleken på routingmeddelanden i vissa ganska vanliga nätverkstopologier, men det möjliggör en förbättring av nätverkets totala effektivitet i händelse av fel. Delad horisont anger att om en närliggande router skickar en rutt till en router, kommer den mottagande routern inte att sprida denna rutt tillbaka till reklamroutern på samma gränssnitt.

Med ruttförgiftning, när en router upptäcker att en av dess anslutna rutter har misslyckats, kommer routern att förgifta rutten genom att tilldela den ett oändligt mått och göra reklam för det till grannar. När en router annonserar en förgiftad rutt till sina grannar bryter dess grannar regeln om delad horisont och skickar tillbaka till upphovsmannen samma förgiftade rutt, en så kallad giftomvändning. För att ge routern tillräckligt med tid för att sprida den förgiftade rutten och för att säkerställa att inga routningsslingor inträffar medan utbredningen sker, implementerar routrarna en nedhållningsmekanism.

Poison Reverse

Poison Reverse används ofta inom distans-vektor routing för att lösa problemet med räkning till oändlighet . I praktiken kan giftomvändning ses som ett alternativ till delad horisont. Med gift omvänd annonseras ruttannonser som skulle undertryckas av delad horisont istället med ett oändligt avstånd.

Grundidén med poison reverse är att se till att en väg inte går tillbaka till samma nod om en kostnad har ändrats inom nätverket. Ett exempel på detta skulle vara: Nod Z leder via nod Y till destination X. Om kostnaden mellan Y och X ökar kommer räkningen till oändlighetsproblemet att uppstå. För att undvika det implementerar vi giftomvänd. Så länge Z leder via nod Y för att komma till X, kommer Z att säga en vit lögn för Y: Z kommer att meddela Y en oändlig kostnad för destination X.

Siffrorna på kanterna är kostnaderna för länkarna.

Efter denna topologi bygger vi avståndsvektorerna för alla noder i nätverket:

Destination	till Z	till Y	till X
från Z	0	1	3
från Y	1	0	2
från X	3	2	0

De första, andra och tredje linjerna motsvarar nod Z, nod Y respektive nod X avståndsvektorer.

Följande matris innehåller uppskattningarna av avstånden från Z till alla andra noder i nätverket genom var och en av dess grannar.

Destination	via Z	via Y	via X
till Z	0	X	X
till Y	X	1	32
till X	X	3	30

Eftersom Z går via Y för att komma till X är reskostnaden från Z till X 3. Giftomvändningen slår in när en nod sänder sin avståndsvektor till sina grannar. Avståndsvektorerna som sänds av Z är:

Till Y: nod Z annonserar sin avståndsvektor och ersätter det sista elementet med ∞, dvs den skickar [0, 1, ∞]

Till X: nod Z annonserar sin avståndsvektor, utan några ersättningar, dvs den skickar [0, 1, 3]

Som vi ser i avståndsvektorn som sänds till nod Y har slutdestinationen X ett oändligt värde.

Omvänt bakåt löser räkningen-till-oändlighet-problemet, eftersom om länken mellan Y och X får sin kostnad ökad till, säg, 70, då kommer Y och Z inte att studsa mellan varandra och istället direkt försöka en annan väg. Alternativt, om balanserad omvändning inte används, när länken mellan Y och X har ökat sin kostnad, kommer Y att meddela nyheterna för Z. Innan Y tillkännager kan dock Y utnyttja det faktum att Z kan nå X med en kostnad på 3 till besluta att Y kan nå X med en kostnad på 4. Sedan uppdaterar Z sin kostnad att gå till X, genom Y, som 5. Därefter uppdaterar Y sin kostnad att gå till X, till Z, som 6 , och så vidare, nyttokostnaden att gå från Z till X når 30. Vid denna punkt, efter 30 iterationer, konvergerar algoritmen.

Poison reverse fungerar inte alltid. Till exempel:

Om länken mellan C och D skulle misslyckas kan nod C fortfarande försöka gå igenom B för att komma till destinationen. B var redan på väg genom A och kommer att fortsätta göra det. Nu kan A inte färdas genom B, på grund av giftomvändning, men vid denna tidpunkt kommer A så småningom att få ett meddelande från C som meddelar att C har en rutt med kostnad 7 till D, där c(C,B)+distans(B,D) )=3+(3+1)=7. Sedan kommer A att förlita sig på C för att dirigera till D. Sammanfattningsvis, efter fel på CD, kommer C att uppdatera, följt av A, B, C, A, B, C och så vidare. Därifrån har vi en slinga som vi inte kan lösa med gift omvänd.

Detta kan dock kompletteras med en implementering av ett distansvektorprotokoll som kallas RIP .

Genomföranden

Metoden med delad horisont är effektiv och enkel att implementera och används därför av de flesta distans-vektorprotokoll. Det används särskilt av:

VILA I FRID
IGRP
EIGRP
VPLS , som använder tekniken delad horisont för att undvika slingor i framplanet
Babel , som endast tillämpar delad horisont på trådbundna länkar

Se även

Split-horizon DNS , ett liknande koncept inom DNS som utför selektiv publicering av information
Ruttförgiftning
CISCO-certifiering

James F. Kurose, Keith W. Ross (2017). Computer Networking: A top-Down Approach, Seventh Edition . Harlow, England: Pearson. sid. 418. {{ citera bok }} : CS1 underhåll: använder författarens parameter ( länk )

externa länkar

"Split Horizon" och "Split Horizon with Poison Reverse" i Convergence in RIP Internetworks , från Microsoft TechNet.