Avstånd-vektor routingprotokoll
Ett distans-vektor routingprotokoll i datanätverk bestämmer den bästa rutten för datapaket baserat på avstånd. Avstånd-vektor routingprotokoll mäter avståndet med antalet routrar ett paket måste passera; en router räknas som ett hopp. Vissa distans-vektorprotokoll tar också hänsyn till nätverkslatens och andra faktorer som påverkar trafiken på en given rutt. För att bestämma den bästa rutten över ett nätverk utbyter routrar som använder ett distans-vektorprotokoll information med varandra, vanligtvis routingtabeller plus hoppräkningar för destinationsnätverk och eventuellt annan trafikinformation. Avståndsvektors routingprotokoll kräver också att en router regelbundet informerar sina grannar om nätverkstopologiändringar .
Avståndsvektors routingprotokoll använder Bellman–Ford-algoritmen för att beräkna den bästa rutten. Ett annat sätt att beräkna den bästa rutten över ett nätverk är baserat på länkkostnad, och implementeras genom länk-tillståndsruttprotokoll .
Termen avståndsvektor hänvisar till det faktum att protokollet manipulerar vektorer ( matriser ) av avstånd till andra noder i nätverket. Avståndsvektoralgoritmen var den ursprungliga ARPANET- routningsalgoritmen och implementerades mer allmänt i lokala nätverk med Routing Information Protocol ( RIP).
Översikt
Avståndsvektors routingprotokoll använder Bellman–Ford-algoritmen . I dessa protokoll har inte varje router information om hela nätverkstopologin . Den annonserar sitt avståndsvärde (DV) beräknat till andra routrar och tar emot liknande annonser från andra routrar om inte ändringar görs i det lokala nätverket eller av grannar (routrar). Med hjälp av dessa routingannonser fyller varje router sin routingtabell. I nästa reklamcykel annonserar en router uppdaterad information från sin routingtabell. Denna process fortsätter tills routingtabellerna för varje router konvergerar till stabila värden.
Vissa av dessa protokoll har nackdelen av långsam konvergens.
Exempel på distans-vektor routingprotokoll:
- Routing Information Protocol (RIP)
- Routing Information Protocol version 2 (RIPv2)
- Routing Information Protocol Next Generation (RIPng), en förlängning av RIP version 2 med stöd för IPv6
- Interior Gateway Routing Protocol (IGRP)
- EIGRP ( Enhanced Interior Gateway Routing Protocol )
Metodik
Routrar som använder distans-vektorprotokoll bestämmer avståndet mellan sig själva och en destination. Den bästa vägen för Internet Protocol- paket som bär data över ett datanätverk mäts i termer av antalet routrar (hopp) ett paket måste passera för att nå sitt destinationsnätverk. Vissa distans-vektorprotokoll tar dessutom hänsyn till annan trafikinformation, såsom nätverkslatens . För att fastställa den bästa rutten utbyter routrar regelbundet information med närliggande routrar, vanligtvis deras routingtabell , hoppräkning för ett destinationsnätverk och eventuellt annan trafikrelaterad information. Routrar som implementerar distans-vektorprotokoll förlitar sig enbart på informationen som tillhandahålls av andra routrar och bedömer inte nätverkstopologin .
Avståndsvektorprotokoll uppdaterar routningstabellerna för routrar och bestämmer vägen på vilken ett paket kommer att skickas av nästa hopp, vilket är utgångsgränssnittet för routern och IP-adressen för gränssnittet för den mottagande routern. Avstånd är ett mått på kostnaden för att nå en viss nod. Den billigaste rutten mellan två noder är rutten med minsta avstånd.
Uppdateringar utförs med jämna mellanrum i ett distans-vektorprotokoll där hela eller delar av en routers routingtabell skickas till alla dess grannar som är konfigurerade att använda samma distans-vektor routingprotokoll. När en router väl har denna information kan den ändra sin egen routingtabell för att återspegla ändringarna och sedan informera sina grannar om ändringarna. Denna process har beskrivits som "routing för rykte" eftersom routrar förlitar sig på informationen de får från andra routrar och inte kan avgöra om informationen faktiskt är giltig och sann. Det finns ett antal funktioner som kan användas för att hjälpa till med instabilitet och felaktig ruttinformation.
Utveckling av distans-vektor routing
Det äldsta routingprotokollet , och det äldsta distans-vektorprotokollet, är version 1 av Routing Information Protocol (RIPv1). RIPv1 standardiserades formellt 1988. Den etablerar den kortaste vägen över ett nätverk enbart på basis av hopp, det vill säga antalet routrar som måste passeras för att nå destinationsnätverket. RIP är ett inre gateway-protokoll , så det kan användas i lokala nätverk (LAN) på inre routrar eller gränsroutrar. Routrar med RIPv1-implementering utbyter sina routningstabeller med angränsande routrar genom att sända ett RIPv1-paket var 30:e sekund till alla anslutna nätverk. RIPv1 lämpar sig inte för stora nätverk då den begränsar antalet hopp till 15. Denna hoppgräns infördes för att undvika routingslingor, men innebär också att nätverk som är anslutna via fler än 15 routrar inte går att nå.
Avståndsvektorprotokollet designat för användning i WAN ( Wide Area Networks) är Border Gateway Protocol (BGP). BGP är ett externt gateway-protokoll och därför implementerat på gräns- och exteriörroutrar på Internet . Den utbyter information mellan routrar genom en TCP-session (Transmission Control Protocol) . Routrar med BGP-implementering bestämmer den kortaste vägen över ett nätverk baserat på en rad andra faktorer än hopp. BGP kan också konfigureras av administratörer så att vissa rutter föredras eller undviks. BGP används av internetleverantörer (ISP) och telekommunikationsföretag.
Bland distans-vektorprotokollen som har beskrivits som en hybrid, eftersom den använder routingmetoder förknippade med länktillståndsroutingprotokoll , finns det proprietära Enhanced Interior Gateway Routing Protocol (EIGRP). Det utvecklades av Cisco på 1980-talet och designades för att erbjuda bättre konvergens och orsaka mindre nätverkstrafik mellan routrar än routingprotokollet för länktillstånd Open Shortest Path First (OSPF).
Ett annat exempel på ett distans-vektor routingprotokoll är Babel .
Räkna till oändlighet problem
Bellman –Ford-algoritmen förhindrar inte att routingslingor inträffar och lider av problemet med räkning till oändlighet . Kärnan i problemet med räkning till oändlighet är att om A säger till B att den har en väg någonstans, finns det inget sätt för B att veta om vägen har B som en del av sig. För att se problemet, föreställ dig ett subnät anslutet som A–B–C–D–E–F, och låt måttet mellan routrarna vara "antal hopp". Anta nu att A är offline. I vektoruppdateringsprocessen märker B att rutten till A, som var avstånd 1, ligger nere – B tar inte emot vektoruppdateringen från A. Problemet är att B också får en uppdatering från C och C fortfarande inte medveten om det faktum att A är nere – så det säger till B att A bara är två hopp från C (C till B till A). Eftersom B inte vet att vägen från C till A går genom sig själv (B), uppdaterar den sin tabell med det nya värdet "B till A = 2 + 1". Senare vidarebefordrar B uppdateringen till C och på grund av att A är nåbar genom B (Från C:s synvinkel), bestämmer C sig för att uppdatera sin tabell till "C till A = 3 + 1". Detta fortplantar sig långsamt genom nätverket tills det blir oändligt (i vilket fall algoritmen korrigerar sig själv, på grund av avslappningsegenskapen hos Bellman-Ford).
Lösningar och lösningar
RIP använder den delade horisonten med giftomvänd teknik för att minska risken för att bilda slingor och använder ett maximalt antal hopp för att motverka "räkning till oändlighet"-problemet. Dessa åtgärder undviker bildandet av routingslingor i vissa, men inte alla, fall. Tillägget av en hålltid (vägra ruttuppdateringar i några minuter efter en ruttåterdragning) undviker slingbildning i praktiskt taget alla fall, men orsakar en signifikant ökning av konvergenstider.
På senare tid har ett antal loop-fria avståndsvektorprotokoll utvecklats - anmärkningsvärda exempel är EIGRP , DSDV och Babel . Dessa undviker slingbildning i alla fall, men lider av ökad komplexitet, och deras utbyggnad har bromsats upp av framgången med länktillståndsroutningsprotokoll som OSPF .
Exempel
I detta nätverk har vi 4 routrar A, B, C och D:
Vi markerar den aktuella tiden (eller iterationen) i algoritmen med T, och börjar (vid tiden 0, eller T=0) med att skapa avståndsmatriser för varje router till dess närmaste grannar. När vi bygger rutttabellerna nedan markeras den kortaste vägen i grönt och en ny kortaste vägen är markerad i gult. Grå kolumner indikerar noder som inte är grannar till den aktuella noden och anses därför inte vara en giltig riktning i dess tabell. Rött indikerar ogiltiga poster i tabellen eftersom de refererar till avstånd från en nod till sig själv, eller via sig själv.
| T=0 |
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Vid det här laget har alla routrar (A,B,C,D) nya "kortaste vägar" för sin DV (listan över avstånd som är från dem till en annan router via en granne). De sänder var och en denna nya DV till alla sina grannar: A till B och C, B till C och A, C till A, B och D och D till C. När var och en av dessa grannar får denna information, räknar de nu om kortaste vägen med den. Till exempel: A tar emot en DV från C som talar om för A att det finns en väg via C till D, med ett avstånd (eller kostnad) på 5. Eftersom den nuvarande "kortaste vägen" till C är 23, så vet A att den har en väg till D som kostar 23+5=28. Eftersom det inte finns några andra kortare vägar som A känner till, sätter den detta som sin nuvarande uppskattning för den kortaste vägen från sig själv (A) till D, via C. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| T=1 |
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Återigen, alla routrar har under den senaste iterationen (vid T=1) fått nya "kortaste vägar", så de sänder alla sina DV till sina grannar; Detta uppmanar varje granne att räkna om sina kortaste avstånd igen. Till exempel: A tar emot en DV från B som talar om för A att det finns en väg via B till D, med ett avstånd (eller kostnad) på 7. Eftersom den nuvarande "kortaste vägen" till B är 3, så vet A att den har en väg till D som kostar 7+3=10. Denna väg till D av längd 10 (via B) är kortare än den befintliga "kortaste vägen" till D av längd 28 (via C), så den blir den nya "kortaste vägen" till D. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| T=2 |
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Den här gången är det bara routrarna A och D som har nya kortaste vägar för sina DV:er. Så de sänder sina nya DV till sina grannar: A sänder till B och C, och D sänder till C. Detta gör att var och en av grannarna som tar emot de nya DV:erna beräknar om sina kortaste vägar. Men eftersom informationen från DV:erna inte ger några kortare vägar än de redan har i sina routingtabeller, så finns det inga ändringar i routingtabellerna. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| T=3 |
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Ingen av routrarna har några nya kortaste vägar att sända. Därför får ingen av routrarna någon ny information som kan ändra deras routningstabeller. Algoritmen stannar. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
- G. Malkin (november 1998). RIP version 2 . Nätverksarbetsgrupp. doi : 10.17487/RFC2453 . STD 53. RFC 2453 . Internet standard. Föråldrade RFC 1723 och 1388 . Uppdaterad av RFC 4822 .
- "A Path-Finding Algorithm for Loop-Free Routing , JJ Garcia-Luna-Aceves och S. Murthy, IEEE/ACM Transactions on Networking, februari 1997
- "Detection of Invalid Routing Announcements in the RIP Protocol", D. Pei, D. Massey och L. Zhang, IEEE Global Communications Conference (Globecom), december 2003
Vidare läsning
- Avsnittet "Link-State Versus Distance Vector" i kapitlet "Routing Basics" i Cisco "Internetworking Technology Handbook"
- Avsnitt 5.2 "Routingalgoritmer" i kapitel "5 NÄTVERKSLAGET" från "Datornätverk" 4:e. Upplaga av Andrew S. Tanenbaum