Ruting - Routing

Ruting er prosessen med å velge en bane for trafikk i et nettverk eller mellom eller på tvers av flere nettverk. I grove trekk utføres ruting i mange typer nettverk, inkludert kretsomkoblede nettverk , for eksempel det offentlige koblede telefonnettet (PSTN) og datanettverk , for eksempel Internett .

I pakkebyttenettverk er ruting beslutningen på høyere nivå som leder nettverkspakker fra kilden til destinasjonen gjennom mellomliggende nettverksnoder ved hjelp av spesifikke pakkeoverføringsmekanismer. Videresending av pakker er overføring av nettverkspakker fra ett nettverksgrensesnitt til et annet. Mellomliggende noder er vanligvis nettverksmaskinvareenheter som rutere , gateways , brannmurer eller svitsjer . Datamaskiner for generelle formål videresender også pakker og utfører ruting, selv om de ikke har noen spesielt optimalisert maskinvare for oppgaven.

Rutingprosessen dirigerer vanligvis videresending på grunnlag av rutetabeller . Rutetabeller holder oversikt over rutene til forskjellige nettverksdestinasjoner. Rutingstabeller kan spesifiseres av en administrator, læres ved å observere nettverkstrafikk eller bygges ved hjelp av rutingprotokoller .

Ruting, i en smalere forstand av begrepet, refererer ofte til IP -ruting og står i kontrast med bro . IP -ruting forutsetter at nettverksadresser er strukturert og at lignende adresser innebærer nærhet i nettverket. Strukturerte adresser lar en enkelt rutetabelloppføring representere ruten til en gruppe enheter. I store nettverk overgår strukturert adressering (ruting, i smal forstand) ustrukturert adressering (broing). Ruting har blitt den dominerende formen for adressering på Internett. Bro er fremdeles mye brukt i lokalnett .

Leveringsordninger

Rutingordninger
Unicast

Unicast.svg

Kringkaste

Broadcast.svg

Multicast

Multicast.svg

Anycast

Anycast-BM.svg

Rutingskjemaer er forskjellige i hvordan de leverer meldinger:

  • Unicast leverer en melding til en enkelt spesifikk node ved å bruke en en-til-en- tilknytning mellom avsender og destinasjon: hver destinasjonsadresse identifiserer et enkelt mottakerendepunkt på en unik måte.
  • Broadcast leverer en melding til alle noder i nettverket ved å bruke en en-til-alle- tilknytning; et enkelt datagram (eller en pakke ) fra en sender sendes til alle de muligens flere endepunktene som er knyttet til kringkastingsadressen . Nettverket gjentak automatisk datagrammer som er nødvendig for å nå alle mottakere innenfor rammen av sendingen, som vanligvis er et helt nettverk subnett .
  • Multicast leverer en melding til en gruppe noder som har uttrykt interesse for å motta meldingen ved hjelp av en en-til-mange-av-mange eller mange-til-mange-av-mange- foreninger; datagrammer dirigeres samtidig i en enkelt overføring til mange mottakere. Multicast skiller seg fra kringkasting ved at destinasjonsadressen angir et delsett, ikke nødvendigvis alle, av de tilgjengelige nodene.
  • Anycast leverer en melding til en ut av en gruppe noder, vanligvis den som er nærmest kilden ved å bruke en en-til-en-av-mange- tilknytning der datagrammer dirigeres til et enkelt medlem av en gruppe potensielle mottakere som alle er identifisert med samme destinasjonsadresse. Rutingsalgoritmen velger den eneste mottakeren fra gruppen basert på hvilken som er den nærmeste i henhold til noen avstand eller kostnadsmål.

Unicast er den dominerende formen for levering av meldinger på Internett. Denne artikkelen fokuserer på unicast -rutingalgoritmer.

Topologi distribusjon

Med statisk ruting kan små nettverk bruke manuelt konfigurerte rutetabeller. Større nettverk har komplekse topologier som kan endre seg raskt, noe som gjør den manuelle konstruksjonen av rutetabeller umulig. Likevel bruker det meste av det offentlige koblede telefonnettet (PSTN) forhåndsberegnede rutetabeller, med tilbakebetalingsruter hvis den mest direkte ruten blir blokkert (se ruting i PSTN ).

Dynamisk ruting forsøker å løse dette problemet ved å konstruere rutingstabeller automatisk, basert på informasjon som bæres av rutingprotokoller , slik at nettverket kan handle nesten autonomt for å unngå nettverksfeil og blokkeringer. Dynamisk ruting dominerer Internett. Eksempler på dynamiske routingsprotokoller og algoritmer inkluderer Routing Information Protocol (RIP), Open Shortest Path First (OSPF) og Enhanced Interior Gateway Routing Protocol (EIGRP).

Avstandsvektoralgoritmer

Avstandsvektoralgoritmer bruker Bellman – Ford -algoritmen . Denne tilnærmingen tildeler et kostnadstall til hver av koblingene mellom hver node i nettverket. Noder sender informasjon fra punkt A til punkt B via banen som resulterer i den laveste totale kostnaden (dvs. summen av kostnadene for koblingene mellom nodene som brukes).

Når en node først starter, vet den bare om sine nærmeste naboer og de direkte kostnadene som er forbundet med å nå dem. (Denne informasjonen - listen over destinasjoner, den totale kostnaden for hver og neste hopp for å sende data for å komme dit - utgjør rutetabellen eller avstandstabellen .) Hver node sender regelmessig til hver nabo -node sin egen nåværende vurdering av den totale kostnaden for å komme til alle destinasjonene den vet om. Nabo -nodene undersøker denne informasjonen og sammenligner den med det de allerede vet; alt som representerer en forbedring av det de allerede har, legger de inn i sitt eget bord. Over tid oppdager alle nodene i nettverket det beste neste hoppet og totalkostnaden for alle destinasjoner.

Når en nettverksnode går ned, vil alle noder som brukte den som sitt neste hopp, forkaste oppføringen og formidle den oppdaterte rutinginformasjonen til alle tilstøtende noder, som igjen gjentar prosessen. Etter hvert mottar alle nodene i nettverket oppdateringene og oppdager nye stier til alle destinasjonene som ikke involverer ned -noden.

Link-state-algoritmer

Når du bruker koblingstilstandsalgoritmer, er et grafisk kart over nettverket de grunnleggende dataene som brukes for hver node. For å produsere kartet, oversvømmer hver node hele nettverket med informasjon om de andre nodene den kan koble seg til. Hver node samler deretter denne informasjonen uavhengig til et kart. Ved å bruke dette kartet, bestemmer hver ruter uavhengig den billigste banen fra seg selv til hver annen node ved å bruke en standard korteste banealgoritme, for eksempel Dijkstras algoritme . Resultatet er en tregraf som er forankret på den nåværende noden, slik at banen gjennom treet fra roten til en hvilken som helst annen node er den billigste banen til den noden. Dette treet tjener deretter til å konstruere rutetabellen, som spesifiserer det beste neste hoppet å komme fra den nåværende noden til en hvilken som helst annen node.

Optimalisert algoritme for ruting av lenketilstand

En koblingstilstandsruteringsalgoritme optimalisert for ad hoc-nettverk for mobil er den optimaliserte Link State Routing Protocol (OLSR). OLSR er proaktiv; den bruker Hello- og Topology Control (TC) -meldinger for å oppdage og spre informasjon om lenketilstand via det mobile ad hoc-nettverket. Ved hjelp av Hello-meldinger oppdager hver node 2-hop naboinformasjon og velger et sett flerpunktsreléer (MPR). MPR skiller OLSR fra andre koblingstilstands routingprotokoller.

Sti-vektor-protokoll

Avstandsvektor og koblingstilstandsruting er begge rute-protokoller innenfor domenet. De brukes inne i et autonomt system , men ikke mellom autonome systemer. Begge disse rutingprotokollene blir umulige i store nettverk og kan ikke brukes i ruting mellom domener . Avstandsvektoruting er utsatt for ustabilitet hvis det er mer enn noen få hopp i domenet. Koblingstilstandsruting trenger betydelige ressurser for å beregne rutetabeller. Det skaper også tung trafikk på grunn av flom.

Sti-vektor ruting brukes for ruting mellom domener. Det ligner på avstandsvektoruting. Path-vector routing forutsetter at en node (det kan være mange) i hvert autonome system handler på vegne av hele det autonome systemet. Denne noden kalles høyttalernoden. Høyttalernoden oppretter et rutingtabell og annonserer det til nabohøyttalernoder i nærliggende autonome systemer. Ideen er den samme som avstandsvektorruting bortsett fra at bare høyttalernoder i hvert autonome system kan kommunisere med hverandre. Høyttalernoden annonserer banen, ikke den metriske, til nodene i det autonome systemet eller andre autonome systemer.

Sti-vektor-rutingsalgoritmen ligner avstandsvektoralgoritmen i den forstand at hver grense-ruter annonserer destinasjonene den kan nå til naboruteren. I stedet for annonseringsnettverk når det gjelder en destinasjon og avstanden til den destinasjonen, blir nettverk imidlertid annonsert som destinasjonsadresser og banebeskrivelser for å nå disse destinasjonene. Banen, uttrykt i form av domenene (eller konføderasjonene) som er krysset så langt, bæres i et spesielt baneattributt som registrerer sekvensen av dirigeringsdomener som tilgjengelighetsinformasjonen har passert. En rute er definert som en sammenkobling mellom en destinasjon og attributtene til banen til den destinasjonen, og dermed navnet, banen-vektorruting; Ruterne mottar en vektor som inneholder stier til et sett med destinasjoner.

Valg av bane

Sti -valg innebærer å bruke en rutemåling på flere ruter for å velge (eller forutsi) den beste ruten. De fleste rutingalgoritmer bruker bare én nettverksbane om gangen. Ruting med flere baner og spesielt flerkjørte rutingsteknikker til like mye kostnad muliggjør bruk av flere alternative stier.

I datanettverk beregnes beregningen av en rutingalgoritme, og kan dekke informasjon som båndbredde , nettverksforsinkelse , hoppetall , banekostnad, belastning, maksimal overføringsenhet , pålitelighet og kommunikasjonskostnad. Rutingtabellen lagrer bare de best mulige ruter, mens lenketilstand eller topologiske databaser også kan lagre all annen informasjon.

Ved overlappende eller like ruter, vurderer algoritmer følgende elementer i prioritert rekkefølge for å bestemme hvilke ruter som skal installeres i rutetabellen:

  1. Prefikslengde : En matchende rutetabelloppføring med en lengre nettverksmaske er alltid å foretrekke ettersom den spesifiserer destinasjonen mer nøyaktig.
  2. Metrisk : Når du sammenligner ruter som er lært via den samme rutingsprotokollen, foretrekkes en lavere beregning. Beregninger kan ikke sammenlignes mellom ruter som er lært fra forskjellige rutingsprotokoller.
  3. Administrativ avstand : Når du sammenligner rutetabelloppføringer fra forskjellige kilder, for eksempel forskjellige rutingsprotokoller og statisk konfigurasjon, indikerer en lavere administrativ avstand en mer pålitelig kilde og dermed en foretrukket rute.

Fordi en rutingberegning er spesifikk for en gitt rutingprotokoll, må ruter med flere protokoller bruke en ekstern heuristikk for å velge mellom ruter som er lært fra forskjellige rutingsprotokoller. Cisco -rutere tilskriver for eksempel en verdi kjent som den administrative avstanden til hver rute, der mindre administrative avstander indikerer ruter som er lært av en protokoll som antas å være mer pålitelig.

En lokal administrator kan konfigurere vertsspesifikke ruter som gir mer kontroll over nettverksbruk, tillater testing og bedre generell sikkerhet. Dette er nyttig for feilsøking av nettverkstilkoblinger eller rutetabeller.

I noen små systemer bestemmer en enkelt sentral enhet på forhånd hele banen til hver pakke. I noen andre små systemer bestemmer hvilken kantinnretning som injiserer en pakke i nettverket på forhånd hele banen til den aktuelle pakken. I begge tilfeller må ruteplanleggingsenheten vite mye informasjon om hvilke enheter som er koblet til nettverket og hvordan de er koblet til hverandre. Når den har denne informasjonen, kan den bruke en algoritme som A* søkealgoritme for å finne den beste banen.

I høyhastighetssystemer sendes det så mange pakker hvert sekund at det er umulig for en enkelt enhet å beregne hele banen for hver pakke. Tidlige høyhastighetssystemer behandlet dette med kretsbytte ved å sette opp en bane en gang for den første pakken mellom en kilde og en destinasjon; senere pakker mellom den samme kilden og den samme destinasjonen fortsetter å følge den samme banen uten å regne på nytt til kretsen rives ned . Senere injiserer høyhastighetssystemer pakker i nettverket uten at noen enhet noen gang har beregnet en fullstendig bane for pakker.

I store systemer er det så mange tilkoblinger mellom enheter, og disse tilkoblingene endres så ofte, at det er umulig for en enhet å vite hvordan alle enhetene er koblet til hverandre, langt mindre beregne en fullstendig vei gjennom dem. Slike systemer bruker vanligvis next-hop- ruting.

De fleste systemer bruker en deterministisk dynamisk rutingalgoritme . Når en enhet velger en vei til en bestemt sluttdestinasjon, velger den enheten alltid den samme veien til den destinasjonen til den mottar informasjon som får den til å tro at en annen vei er bedre.

Noen få rutingalgoritmer bruker ikke en deterministisk algoritme for å finne den beste koblingen for en pakke å komme fra den opprinnelige kilden til den endelige destinasjonen. I stedet, for å unngå overbelastningspunkter i pakkesystemer, bruker noen få algoritmer en randomisert algoritme - Valiant's paradigme - som ruter en vei til et tilfeldig plukket mellomliggende reisemål, og derfra til den sanne endelige destinasjonen. I mange tidlige telefonbrytere ble en randomizer ofte brukt til å velge starten på en bane gjennom et flertrinns koblingsstoff .

Avhengig av applikasjonen som banevalg utføres for, kan forskjellige beregninger brukes. For eksempel, for webforespørsler kan man bruke minst ventetidbaner for å minimere lastetid for nettsider, eller for masseoverføringer av data kan man velge den minst brukte banen for å balansere belastning på tvers av nettverket og øke gjennomstrømningen. Et populært stevalgsmål er å redusere den gjennomsnittlige fullføringstiden for trafikkstrømmer og det totale nettverksbåndbreddeforbruket. Nylig ble det foreslått en veivalg -beregning som beregner det totale antallet byte som er planlagt på kantene per bane som seleksjonsberegning. En empirisk analyse av flere veivalgberegninger, inkludert dette nye forslaget, er gjort tilgjengelig.

Flere agenter

I noen nettverk er ruting komplisert av det faktum at ingen enkelt enhet er ansvarlig for å velge stier; i stedet er flere enheter involvert i å velge baner eller deler av en enkelt bane. Komplikasjoner eller ineffektivitet kan oppstå hvis disse enhetene velger veier for å optimalisere sine egne mål, noe som kan komme i konflikt med målene til andre deltakere.

Et klassisk eksempel er trafikk i et veisystem, der hver sjåfør velger en bane som minimerer reisetiden. Med slik ruting kan likevektsrutene være lengre enn optimal for alle sjåfører. Spesielt viser Braess paradoks at det å legge til en ny vei kan forlenge reisetiden for alle sjåfører.

I en enkeltagentmodell som for eksempel brukes til å dirigere automatiserte guidede kjøretøyer (AGV) på en terminal, tas det forbehold for hvert kjøretøy for å forhindre samtidig bruk av den samme delen av en infrastruktur. Denne tilnærmingen kalles også kontekstbevisst ruting.

Internett er delt inn i autonome systemer (AS) som internettleverandører (ISPer), som hver kontrollerer ruter som involverer nettverket. Ruting skjer på flere nivåer. Først velges baner på AS-nivå via BGP- protokollen som produserer en sekvens av ASer som pakker flyter gjennom. Hvert AS kan ha flere veier, som tilbys av nærliggende AS -er, og velge mellom. Disse rutingbeslutningene korrelerer ofte med forretningsforbindelser med disse nærliggende AS -ene, som kan være uten sammenheng med banekvalitet eller latens. For det andre, når en bane på AS-nivå er valgt, er det ofte flere tilsvarende baner på ruternivå å velge mellom. Dette skyldes delvis at to Internett -leverandører kan være tilkoblet via flere tilkoblinger. Ved valg av banen på ett ruternivå er det vanlig praksis for hver ISP å bruke hotpotet-ruting : sende trafikk langs stien som minimerer avstanden gjennom ISPs eget nettverk-selv om den banen forlenger den totale avstanden til destinasjonen.

For eksempel vurdere to ISPer, A og B . Hver har en tilstedeværelse i New York , forbundet med en rask kobling med latensms - og hver har en tilstedeværelse i London forbundet med en 5 ms -kobling. Anta at begge Internett-leverandørene har trans-atlantiske koblinger som kobler sine to nettverk, men A 's kobling har latens 100 ms og B har latens 120 ms. Når du dirigerer en melding fra en kilde i A 's London -nettverk til en destinasjon i Bs New York -nettverk, kan A velge å umiddelbart sende meldingen til B i London. Dette sparer A for arbeidet med å sende den langs en dyr transatlantisk forbindelse, men får meldingen til å oppleve latens 125 ms når den andre ruten ville vært 20 ms raskere.

En måleundersøkelse fra 2003 av internettruter fant at mer enn 30% av banene mellom par av naboprogrammere har oppblåst latens på grunn av ruting av varme poteter, og 5% av banene er forsinket med minst 12 ms. Inflasjon på grunn av AS-nivåbanevalg, selv om den var betydelig, ble hovedsakelig tilskrevet BGPs mangel på en mekanisme for direkte optimalisering for latens, i stedet for egoistisk rutingspolicy. Det ble også antydet at Internett-leverandører ville være villige til å samarbeide for å redusere ventetid i stedet for å bruke hotpotet-ruting, hvis en passende mekanisme var på plass. En slik mekanisme ble senere publisert av de samme forfatterne, først for to Internett -leverandører og deretter for den globale saken.

Ruteanalyse

Som Internett og IP-nettverk har blitt virksomhetskritiske forretningsverktøy, har det vært økt interesse i teknikker og metoder for å overvåke ruting holdning av nettverk. Feil ruting eller rutingproblemer forårsaker uønsket ytelsesforringelse, flapp eller nedetid. Overvåking av ruting i et nettverk oppnås ved hjelp av ruteanalyseverktøy og -teknikker.

Sentralisert ruting

I nettverk der en logisk sentralisert kontroll er tilgjengelig over videresendingstilstanden, for eksempel ved bruk av programvaredefinert nettverk , kan rutingsteknikker brukes som tar sikte på å optimalisere globale og nettverksdekkende ytelsesberegninger. Dette har blitt brukt av store internettselskaper som driver mange datasentre på forskjellige geografiske steder vedlagt ved bruk av private optiske lenker, eksempler på dette inkluderer Microsofts Global WAN, Facebooks Express Backbone og Googles B4. Globale ytelsesmålinger for å optimalisere inkluderer maksimering av nettverksutnyttelse, minimering av fullføringstider for trafikkflyt og maksimering av trafikk levert før bestemte frister. Minimering av gjennomføringstidene for strømning over privat WAN, spesielt, har ikke fått mye oppmerksomhet fra forskningsmiljøet. Imidlertid, med det økende antallet bedrifter som driver globalt distribuerte datasentre som er tilkoblet ved hjelp av private inter-datasenternettverk, vil det sannsynligvis se økende forskningsinnsats i dette området. Et helt nylig arbeid med å redusere fullføringstidene for strømmer over privat WAN diskuterer modelleringsruting som et grafoptimaliseringsproblem ved å skyve alle køene til sluttpunktene. Forfattere foreslår også en heurist for å løse problemet effektivt samtidig som det ofrer ubetydelig ytelse.

Se også

Referanser

Videre lesning

Eksterne linker