RIP - Routing Information Protocol

Del 2
Av Michael Seemann

Första delen av denna artikel om Routing Information Protocol (RIP) beskrev hur routrar använder distansvektoralgoritmen och metrik för att finna den bästa vägen till slutdestinationen. Här kan du läsa hur RIP förebygger instabilitet i systemet; det gäller att undvika att loopar och konflikter uppstår.

Plötsliga topologiska förändringar (t ex när en länk går ner) i ett system med routrar hör inte till ovanligheterna. Sådana situationer skulle kunna leda till att datapaket började cirkulera runt mellan routrarna istället för att transporteras till sin slutdestination. Distansvektoralgoritmen som RIP baseras på ger ingen lösning på detta problem. RIP inkluderar därför några smarta funktioner som ser till att undvika loopar och andra konflikter, och framför allt ser till att routingtabellerna i systemet uppdateras tillräckligt snabbt.

Att förebygga instabilitet
Distansvektoralgoritmen innebär att varje enskild router i ett system kan avgöra den optimala vägen för ett datapaket uteslutande baserad på information från sina närmaste routergrannar. Varje router lagrar relevant information i sin routingtabell som normalt uppdateras var 30:e sekund. Detta är emellertid inte tillräckligt för att göra systemet praktiskt användbart. Algoritmen garanterar endast att routingtabellerna kommer att bli korrekta i sinom tid, vilket i vissa situationer kan innebära oacceptabelt lång tid.

Nätverk som inte kan nås tilldelas metrikvärdet 16
För att hantera situationer där nätverk blir onåbara specificerar RIP-protokollet att metrikvärdet 16 skall representera "oändligheten". Detta värde är valt som en kompromiss mellan största möjliga antal hopp i systemet och att det inte får ta för lång tid att lösa upp konflikter. När ett nätverk blir onåbart kommer de närmast angränsande routrarna efter en time-out att sätta metriken i sina routingtabeller till 16. De övriga routrarna i systemet kommer därefter successivt att anpassa sina tabeller. Routrar som ligger ett hopp ifrån de närmast angränsande routrarna kommer att beräkna metriken till 17, de som ligger två hopp bort kommer att sätta metriken till 18 och så vidare. Eftersom dessa tal är högre än max-värdet 16, sätts alla till 16. Så småningom kommer hela routersystemet ha flaggat nätverket som onåbart genom att ha uppdaterat metrikvärdet till 16 i de respektive routingtabellerna.

Den centrala frågan är här hur lång tid det tar innan hela systemet har uppdaterat sina routingtabeller. Problematiken kan illustreras med följande exempel. Observera att exemplet är ägnat att belysa varför vissa egenskaper krävs av protokollet, varför exempelsituationen inte uppstår vid en korrekt implementering av RIP.

Varje router har information i sin routingtabell om den mest effektiva rutten till respektive nätverk. Ovan visas hur rutter och metrik för respektive router utvecklar sig över tiden. I förenklingens namn visas endast rutterna till nätverk N, och alla routrar antas sända sina uppdateringsmeddelanden samtidigt.

Mellan tidpunkt 1 och 2 i tabellen havererar länken mellan router Rb och Rd. Alla rutter till nätverk N måste då justeras för att istället använda vägen via router Rc och Rd. Det kommer dock ta tid innan samtliga routrar uppfattat den förändrade situationen.

Förändringarna börjar vid tidpunkt 2 då router Rb efter en 180 sekunders time-out upptäckt att rutten till Rd inte längre kan användas. Router Ra och Rc tror fortfarande att de kan nå router Rd via Rb. Följaktligen fortsätter de att sända felaktiga uppdateringsmeddelanden med metriken 3.

Vid tidpunkt 3 tror Rb att den kan nå Rd via Rc, vilket den ännu inte kan. Rutten via Rc är vid denna tidpunkt ej framkomlig eftersom både Ra och Rc tror att det finns en rutt via den andre. Ra och Rc blir med andra ord involverade i en loop där de lurar varandra. Var gång de sänder felaktiga meddelanden till varandra kommer dock metriken att ökas med 1, tills den når oändligheten (16) eller en bättre rutt aviseras av en annan granne. Med tiden blir sålunda systemet korrekt uppdaterat, men frågan är efter hur många iterationer? Av detta skäl kallas problemet "räkna till oändligheten".

Det är nu lätt att förstå varför man valt ett så lågt värde som möjligt för oändligheten. Om ett nätverk blir helt onåbart, är det önskvärt att räkningen till oändligheten avslutas så snart som möjligt. Oändligheten måste dock vara större än systemets längsta rutt. Oändligheten är med andra ord en kompromiss mellan systemets maximala storlek och tiden det tar att uppdatera alla routrar när problemet med att räkna till oändligheten inträffar. När RIP specificerades utgick man ifrån att protokollet inte skulle vara tillämpligt för system vars diameter överstiger 15 hopp.

Att "räkna till oändligheten" får ses som en sista utväg för att lösa problem, eftersom det tar sin tid. Det finns dock metoder som påskyndar processen. RIP använder sig av "delad horisont med spärrad återgång" och "triggade uppdateringar".

Delad horisont
Problemet som beskrivs ovan orsakas delvis av det faktum att router Ra och Rc är engagerade i en process där de lurar varandra. Båda tror att de kan nå router Rd via den andre. Detta kan förhindras genom att vara restriktiv med var uppdateringsmeddelanden sänds. Det är i synnerhet aldrig vettigt för en router att hävda att den kan nå ett visst mål till de grannar från vilken den ursprungligen fått information om målet. "Delad horisont" är en mekanism som undviker problem förorsakade av att rutter sänds tillbaka till den router från vilken rutten meddelats. "Delad horisont" utelämnar helt enkelt de rutter som den lärt sig från en grannrouter, när uppdateringar sänds till samma granne. "Delad horisont med spärrad återgång" innebär att sådana rutter inkluderas i uppdateringsmeddelandena, men att metriken sätts till oändligheten (16).

Om router Ra tror att den kan nå Rd via Rc, skall Ra:s meddelanden till Rc indikera att Rd är onåbar. Om rutten via Rc är riktig, har Rc antingen en direktanslutning till Rd, eller via en annan router. Rc:s rutt kan då inte gå tillbaka till Ra, eftersom det skulle innebära en loop. Genom att Ra berättar för Rc att Rd är onåbar, skyddas Rc mot möjligheten att tro att det finns en giltig rutt via Ra. Detta är uppenbart för en punkt-till-punkt-förbindelse. Situationen blir dock annorlunda om Ra och Rc vore anslutna via ett broadcastnät såsom Ethernet, där det även finns andra routrar anslutna. Om Ra har en rutt via Rc, måste den då indikera att Rd är onåbar när den meddelar sig med andra routrar inom samma nätverk. De övriga routrarna inom nätverket kan ju själva nå Rc, och behöver därför inte Ra för att nå Rc. Om Ra:s bästa rutt verkligen går via Rc, behöver inga andra routrar på samma nätverk veta att Ra kan nå Rd. Detta är positivt, eftersom samma uppdateringsmeddelande som används av Rc kan användas av alla övriga routrar på samma nätverk. Med andra ord kan uppdateringsmeddelandena sändas via broadcast.

"Delad horisont med spärrad återgång" är i allmänhet säkrare än bara "delad horisont". Om två routrar har rutter som går genom varandra, bryts loopen ögonblickligen när en rutt med metriken 16 annonseras. I annat fall skulle den felaktiga rutten inte elimineras förrän en time-out inträffade. Delad horisont med spärrad återgång har dock en nackdel; den ökar storleken på uppdateringsmeddelandena. I system med stora backbonenät kan detta leda till mycket stora uppdateringsmeddelanden där merparten av rutterna annonseras som onåbara. Spärrad återgång är fördelaktigt i system där topologiska förändringar ofta inträffar. I mer stabila system kan overheaden minskas om RIP implementeras så att man vid konfiguration kan välja mellan "delad horisont" och "delad horisont med spärrad återgång". En ännu mer sofistikerad lösning kan använda sig av "delad horisont med spärrad återgång" under en viss tid efter förändringar i rutterna, för att sedan automatiskt övergå till bara "delad horisont".

Triggade uppdateringar
"Delad horisont med spärrad återgång" förhindrar att loopar mellan två routrar uppstår. Det är dock möjligt med situationer där tre routrar lurar varandra, exempelvis där Ra tror att den har en rutt via Rb, Rb tror att den kan gå via Rc, och Rc genom Ra. Delad horisont kan inte förhindra denna typ av loop. Den stannar inte förrän metriken når oändligheten (16), och det berörda nätverket därmed deklareras onåbart. Metoden som används för att påskynda upplösningen av sådana loopar kallas "triggade uppdateringar". Det innebär att så snart en router ändrar metriken för en rutt, måste den sända uppdateringsmeddelanden snarast, utan att invänta tiden för nästa reguljära uppdateringsmeddelande (som sker var 30:e sekund).

När en router mottar en uppdatering från sin granne kommer den att räkna om metriken baserad på den nya informationen. Om resultatet blir att metriken ändras (oavsett om den ökar eller minskar), måste routern snarast sända triggade uppdateringar till samtliga sina grannar, vilka i sin tur sänder triggade uppdateringar till sina grannar. Resultatet blir en kaskad av triggade uppdateringar genom hela systemet.

I en ideal värld där systemet kunde göras så att det satt helt stilla medan kaskaden av triggade uppdateringar fortplantade sig, skulle situationer där "räkna till oändligheten" krävdes aldrig inträffa. Ogiltiga rutter skulle elimineras ögonblickligen, vilket i sin tur innebär att inga loopar skulle uppstå. Tyvärr är inte verkligheten så väl inrättad. Medan triggade uppdateringar sänds, kan reguljära uppdateringar komma samtidigt. Routrar som ännu inte mottagit den triggade uppdateringen kommer fortfarande att sända ut information baserad på den rutt som inte längre existerar. Det är fullt möjligt att en router som just mottagit en triggad uppdatering direkt efter mottar en reguljär uppdatering från en router som ännu ej nåtts av kaskaden. Detta medför att den felaktiga rutten återskapas. Om triggade uppdateringar sker tillräckligt snabbt minskar sannolikheten att sådana situationer uppstår. Om de trots allt gör det kommer de att lösas upp med tiden genom att räkna till oändligheten.

Stabiliteten hos timers
Som tidigare nämnts sänder routrar sina reguljära uppdateringsmeddelanden var 30:e sekund. I system med många routrar tenderar de att synkronisera sig med varandra så att de alla sänder sina uppdateringar samtidigt. Detta fenomen uppstår när routrarnas timers påverkas av lasten i systemet. Sådan synkronisering är inte önskvärd då den kan leda till onödiga kollisioner i nätverken. RIP föreskriver därför att routertillverkare skall förebygga problemet genom att antingen se till att timern inte påverkas av routerns belastning, eller genom att addera ett litet slumptal till timern varje gång den återställs till 30 sekunder.

Det finns ytterligare två timers som är knutna till varje rutt i routingtabellen. Den ena kallas time-out vilket innebär att en rutt markeras som ogiltig (metriken sätts till 16) om den inte uppdaterats inom 180 sekunder. När en rutt väl markerats som ogiltig startas en 120-sekunders garbage collection timer. Syftet med denna timer är att hålla kvar rutten i tabellen länge nog för att grannarna skall kunna upplysas om att rutten är ogiltig. Först när denna timer räknats ner till noll elimineras rutten helt från tabellen.

Faktaruta: Distansvektoralgoritmen
RIP är en tillämpning av en distansvektoralgoritm (Bellman-Ford algoritmen), vilket innebär att beslut om vägval baseras på avståndet, eller den mest ekonomiska vägen till slutdestinationen. Algoritmen bevisar matematiskt att det är möjligt för en enskild router att avgöra den optimala vägen uteslutande baserat på information från sina närmaste grannar. Varje router som deltar i routingprotokollet använder denna information för att bygga upp en routingtabell med adressinformation till samtliga destinationer inom systemet. Av routingtabellen framgår även adressen till nästa router på vägen till det aktuella målet. Om en router mottar information från två eller flera andra routrar om en och samma slutdestination, väljer den enligt algoritmen ut den väg som innebär lägst metrik. Om två olika vägar till samma mål har samma metrik väljs den väg som först annonserats.

Faktaruta: Metrik
Metrik är ett tal mellan 1 och 15 som speglar avståndet till slutdestinationen. Avstånd är i detta sammanhang ett generaliserat begrepp, som kan innebära tidsfaktorn för att leverera data, kostnaden i pengar etc. I praktiken motsvarar dock metriken oftast antal hopp (antal routrar på vägen) till slutdestinationen. Även själva slutdestinationen räknas som ett hopp. Ett nätverk som kan nås via en enda router motsvaras följaktligen av två hopp. Man måste dock vara medveten om att användningen av en hopp-räknare för att kalkylera den kortaste distansen inte alltid ger ett optimalt resultat. Exempelvis är en väg med 3 hopp som passerar via Ethernet väsentligt snabbare och mer ekonomisk än en väg med två hopp som går via en långsam modemförbindelse. För att kompensera för sådana tekniska skillnader kan man i många routrar justera upp hopp-räknaren vid behov.