A hálózati réteg fő feladata, hogy a csomagokat a forrásgéptől a célgépig irányítsa. A legtöbb hálózatban a csomagoknak ehhez több útválasztón kell keresztülhaladni, több ugrást kell megtenni. Az egyetlen figyelemre méltó kivétel az adatszóró hálózatok esete, de az útválasztás itt is téma lehet, ha a forrás és a cél nem ugyanazon hálózaton van. Azok az algoritmusok, amelyek az útvonal meghatározását szolgálják, és azok az adatstruktúrák, amelyeket az algoritmusok használnak, a hálózati réteg tervezésének egyik legfontosabb területét alkotják.
Az útválasztó algoritmus (routing algorithm) a hálózati réteg szoftverének azon része, amely azért a döntésért felelős, hogy egy bejövő csomag melyik kimeneti vonalon kerüljön továbbításra. Ha a hálózat belül datagramokat használ, ezt a döntést újra meg újra meg kell hozni minden beérkező adatcsomagra, mivel lehet, hogy a legjobb útvonal a legutóbbi meghatározás óta változott. Ha a hálózat belül virtuális áramköröket használ, akkor útválasztó döntéseket csak új virtuális áramkör felépítésekor kell meghozni. Ezután az adatcsomagok már csak az előzőleg kialakított útvonalat követik. Ezt az utóbbi esetet néha viszony-útválasztásnak (session routing) is nevezik, mivel az útvonal érvényben marad a teljes felhasználói viszony (mint például a VPN-en keresztüli bejelentkezés) alatt.
Néha célszerű megkülönböztetnünk az útválasztást, azaz a választandó útvonalról való döntést és a továbbítást, ami a csomag beérkezésekor történik. Képzeljük azt, hogy az útválasztó két folyamatot tartalmaz. Az egyik kezeli a beérkező csomagokat: mindegyik számára kikeres egy kimeneti vonalat az útválasztó táblázatokból. Ez a folyamat a továbbítás (forwarding). A másik folyamat az útválasztó táblázatok feltöltéséért és karbantartásáért felelős – itt kerülnek be a képbe az útválasztó algoritmusok.
Függetlenül attól, hogy az útvonalakat minden egyes csomagra egymástól függetlenül választják ki vagy csak új összeköttetés létrejöttekor, vannak bizonyos tulajdonságok, amelyek kívánatosak egy útválasztó algoritmus esetében. Ezek a következők: helyesség, egyszerűség, robusztusság, stabilitás, igazságosság, optimalitás és hatékonyság. A helyesség és az egyszerűség magától értetődő, a robusztusság azonban elsőre talán kevésbé nyilvánvaló. Amikor egy nagyobb hálózatot üzembe helyeznek, elvárják, hogy az évekig rendszerszintű hibáktól mentesen működjön. Ez alatt az idő alatt mindenféle hardver- és szoftverhiba adódik. Hosztok, útválasztók és vonalak többször is tönkremennek és megjavulnak, és a topológia is sokszor fog változni. Az útválasztó algoritmusnak képesnek kell lennie arra, hogy megbirkózzon a topológiában és a forgalomban bekövetkező változásokkal anélkül, hogy az összes hoszton futó összes munkát meg kellene szakítani. Képzeljük el, hogy mekkora probléma lenne az, ha a hálózatot mindig újra kellene indítani, ahányszor csak valamelyik útválasztó összeomlik.
A stabilitás szintén az útválasztó algoritmus fontos célja. Léteznek algoritmusok, amelyek soha nem közelítik meg az egyensúlyi állapotot (egy fix útvonalhalmazt), bármilyen hosszan fussanak is. Egy stabil algoritmus eléri az egyensúlyt, és meg is őrzi azt. Ennek gyorsan kell történnie, mivel a kommunikáció megszakadhat, mire az útválasztó algoritmus elérné az egyensúlyi állapotot.
Az igazságosság és hatékonyság ugyancsak nyilvánvalónak tűnik – bizonyára senkinek nem lenne kifogása ellenük –, de amint látható, ezek gyakran egymásnak ellentmondó célok. Erre a konfliktusra látható egy egyszerű példa az 5.5. ábrán. Tegyük fel, hogy elegendő forgalom van A és A', B és B', illetve C és C' között ahhoz, hogy telítődjenek a vízszintes adatkapcsolatok. A teljes adatfolyam maximalizálása érdekében az X és X' közti forgalmat teljesen be kellene szüntetni. Sajnos elképzelhető, hogy X és X' ezt nem így látja. Ezért kompromisszumot kell kötni a globális hatékonyság és az egyes összeköttetések azonos elbírálása között.
Mielőtt megpróbálnánk kompromisszumot keresni az igazságosság és hatékonyság között, el kell határoznunk, mit is akarunk optimalizálni. A hálózati forgalom hatékony küldésénél az egyik nyilvánvaló jelölt az átlagos csomagkésleltetés minimalizálása, de ugyanígy a teljes hálózati átbocsátóképesség maximalizálása is. Ez a két cél is ütközik, mivel ha bármely sorbanállási rendszert a teljesítőképessége határán működtetünk, az hosszú sorbanállási késleltetést von maga után. Kompromisszumként sok hálózatban a csomagok által megtett utat, illetve az ugrások számát próbálják meg minimalizálni, mivel ez csökkenti a csomagonként felhasznált sávszélességet, és ezáltal az átbocsátóképesség is javul.
Az útválasztó algoritmusok két nagy osztályba sorolhatók: adaptív és nem adaptív algoritmusok. A nem adaptív algoritmusok (nonadaptive algorithms) döntéseikben nem támaszkodnak mérésekre vagy becslésekre az aktuális forgalomról és topológiáról. Ehelyett az I-től J-ig használandó útvonalat (minden I-re és J-re) előre, offline módon számolják ki, és a hálózat indításakor letöltik az útválasztókba. Ezt az eljárást néha statikus útválasztásnak (static routing) is szokták nevezni. Mivel a statikus útválasztás nem reagál a hibákra, főként olyan helyzetekben hasznos, ahol az útválasztás egyértelmű. Például az 5.3. ábrán látható F útválasztó a hálózatra küldött csomagokat a célcímtől függetlenül az E útválasztónak küldi.
Ezzel ellentétben az adaptív algoritmusok (adaptive algorithms) úgy változtatják útválasztó döntéseiket, hogy azok tükrözzék a topológiában és néha a forgalomban is történt változásokat. Ezek a dinamikus útválasztó algoritmusok abban különböznek egymástól, hogy honnan kapják az információt (például helyileg, a szomszédos útválasztóktól vagy az összes útválasztótól), mikor változtatják meg az útvonalakat (például amikor a topológia változik, vagy minden 
másodpercben, amikor a terhelés változik), és milyen metrikát használnak az optimalizáláshoz (például a távolságot, az ugrások számát vagy a becsült áthaladási időt).
A következő szakaszokban különböző útválasztó algoritmusokat fogunk tárgyalni. Az algoritmusok egy csomagnak a forrástól a cél felé történő küldésén kívül kézbesítési modelleket is magukban foglalnak. Bizonyos esetekben a cél az, hogy a csomagot több címzettnek, az összes címzettnek vagy egy adott címzettnek küldjük. Az itt leírt összes algoritmus a topológia alapján hoz döntést. A forgalomalapú döntések leírását az 5.3. alfejezet tartalmazza.
Mielőtt beleásnánk magukat az egyes algoritmusokba, segítségünkre lehet, hogy az optimális útvonalakról egy általános megállapítás tehető, a hálózat topológiájától és a forgalomtól függetlenül. Ez a megállapítás az optimalitási elv (optimality principle) néven ismeretes [Bellman, 1957]. Az állítás szerint, ha a J útválasztó az I útválasztótól K útválasztó felé vezető optimális útvonalon helyezkedik el, akkor a J-től K-ig vezető útvonal ugyanerre esik. Hogy ezt belássuk, nevezzük az útvonal I-től J-ig tartó részét 
-nek és az útvonal másik részét 
-nek. Ha létezne egy 
-nél jobb, J-től K-ig tartó útvonal, ezt összefűzhetnénk 
-gyel, hogy az I-től K-ig tartó útvonalon is javítsunk. Ez viszont ellentmond állításunknak, miszerint 
optimális.
Az optimalitási elv egyenes következményeként beláthatjuk, hogy az összes forrásból egy adott célba tartó optimális útvonalak egy fát alkotnak, amelynek gyökere a cél. Az ilyen fákat nyelőfának (sink tree) nevezzük. Egy ilyen látható az 5.6. ábrán, ahol a távolság mértéke az ugrások száma. Vegyük észre, hogy a nyelőfa nem feltétlenül egyedi; más fák is létezhetnek ugyanolyan úthosszakkal. Minden útválasztó algoritmus célja a nyelőfák felderítése és használata az összes útválasztó számára.
Vegyük figyelembe, hogy a nyelőfa nem feltétlenül egyedi, létezhetnek azonos úthosszal más fák is. Ha megengedjük, hogy az összes lehetséges útvonal kiválasztható legyen, akkor a fa egy általánosabb adatszerkezetté válik, amelyet irányított aciklikus gráfnak, DAG-nak (Directed Acycle Graph – irányított aciklikus gráf) hívunk. A DAG nem tartalmaz hurkokat. Az egyszerűség kedvéért a nyelőfát, mint egy kényelmes jelölést mindkét típusra alkalmazzuk. Mindkét eset azon a műszaki feltételezésen alapul, hogy az útvonalak nem zavarják egymást, azaz az egyik útvonalon lévő forgalmi dugó nem okozza a másik útvonal eltérülését.
Mivel a nyelőfa valóban fa, nem tartalmaz hurkot, ezért minden csomag véges és korlátos számú ugráson belül kézbesítésre kerül. A gyakorlatban az élet nem ilyen könnyű. Adatkapcsolatok és útválasztók tönkremehetnek és megjavulhatnak működés közben, ezért különböző útválasztóknak különböző elképzeléseik lehetnek a pillanatnyi topológiáról. Szintén csendben elmentünk azon kérdés mellett, hogy vajon az útválasztóknak egyénileg kell-e beszerezni az információt, amelyre a nyelőfaszámítás épül, vagy ezt az információt valami más módszerrel gyűjtik össze. Ezekre a kérdésekre hamarosan visszatérünk. Mindazonáltal az optimalitási elv és a nyelőfa egy mérőszámot adnak, amelyhez más útválasztó algoritmusokat viszonyíthatunk.
Kezdjük az útválasztó algoritmusok tanulmányozását egy egyszerű módszerrel, amely kiszámítja az optimális útvonalakat, és a hálózat teljes képét megadja. Azt szeretnénk, hogy az osztott útválasztó algoritmus még akkor is megtalálja ezeket az útvonalakat, ha nem minden útválasztó ismeri a hálózat összes részletét.
Az ötlet az, hogy építsük fel a hálózat egy gráfját, ahol minden útválasztó egy csomópontnak, és minden él egy kommunikációs vonalnak (vagy adatkapcsolatnak) felel meg. Két adott útválasztó közötti útvonal kiválasztásához az algoritmus egyszerűen a köztük levő legrövidebb utat keresi meg a gráfban.
A legrövidebb út (shortest path) fogalma némi magyarázatra szorul. Egy út hosszát mérhetjük például a megtett ugrások számával. Ezzel a mértékkel az 5.7. ábrán szereplő ABC és ABE út ugyanolyan hosszú. Egy másik mérték lehet a földrajzi távolság kilométerekben, amikor is ABC nyilvánvalóan sokkal hosszabb, mint ABE (feltéve, hogy az ábra léptékhelyes).
5.7. ábra - Az első hat lépés az A-tól D felé vezető legrövidebb út kiszámításában. A nyilak a munkacsomópontot jelzik
Ám az ugrások száma és a földrajzi távolság mellett sok egyéb mérték lehetséges. Például mindegyik él súlya lehetne egy szabványos tesztcsomagra vonatkozó átlagos sorbanállási és átviteli késleltetés, amelyet óránkénti próbafuttatásokkal mérnénk. Ezzel az élsúlyozással a legrövidebb út a leggyorsabb út lesz, a legkevesebb kilométerű vagy legkevesebb élből álló helyett.
A legáltalánosabb esetben az élsúlyok a távolság, a sávszélesség, az átlagos forgalom, a kommunikációs költség, az átlagos sorhosszúság, a mért késleltetés és más értékek függvényeként számíthatók ki. A súlyozó függvény változtatásakor az algoritmus a „legrövidebb” utat a számos feltétel közül valamelyik vagy ezek kombinációja szerint számolná ki.
Számos algoritmus ismert egy gráf két csomópontja közti legrövidebb út kiszámítására. Az alábbi Dijkstrától [1959] származik, és a hálózatban a forráscsomópont és az összes többi csomópont mint nyelőcsomópont közötti legrövidebb utakat határozza meg. Minden csomópontot felcímkézünk (zárójelben) a forráscsomóponttól való legrövidebb ismert út mentén mért távolságával. A távolságértékek nem lehetnek negatív értékek, mivel olyan valós mennyiségeken alapulnak, mint amilyen a sávszélesség vagy a késleltetés. Kezdetben nem ismertek ilyen utak, ezért minden csomópont címkéje végtelen. Ahogy az algoritmus halad előre és találja meg az utakat, a címkék módosulhatnak, jelezve az egyre jobb utakat. Egy címke lehet ideiglenes vagy állandó. Kezdetben minden címke ideiglenes. Amikor kiderül, hogy a címke a legrövidebb lehetséges utat jelzi, állandóvá tesszük, és ezek után már nem módosítjuk.
A címkéző algoritmus bemutatásához nézzük az 5.7.(a) ábrán szereplő, irányítatlan, súlyozott gráfot, ahol a súlyok például távolságot jeleznek. Az A-tól D-ig vezető legrövidebb utat akarjuk megtalálni. Azzal kezdjük, hogy az A csomópontot állandónak jelöljük meg, amit a kör besötétítésével jelzünk. Ezután sorban végigvizsgáljuk az A-val (a munkacsomóponttal) szomszédos csomópontokat, és újracímkézzük az A-tól való távolságukkal. Amikor ezeket a csomópontokat újracímkéztük, akkor azzal a csomóponttal is felcímkézzük ezeket, amelyiktől a vizsgálatot végeztük, hogy később rekonstruálhassuk a végső utat. Ha több legrövidebb útvonal létezik A és D között, és az összeset meg akarjuk találni, akkor az összes megvizsgált csomópontot fel kell jegyezni, amely egy adott csomópontot azonos hosszúságú úttal tud elérni.
Miután A minden szomszédját megvizsgáltuk, az egész gráfban levő ideiglenesen felcímkézett csomópontok közül a legkisebb címkéjűt állandóvá tesszük, amint az az 5.7.(b) ábrán látszik. Ez lesz az új munkacsomópont.
Most B-től kezdjük, és az összes szomszédját megvizsgáljuk. Ha B címkéjének és a B és a vizsgálandó csomópont közti él súlyának összege kisebb, mint a vizsgálandó csomópont címkéje, akkor rövidebb utat találtunk, és a csomópontot újracímkézzük.
Miután a munkacsomópont összes szomszédját megvizsgáltuk, és ha lehetett, az ideiglenes címkéket újra cseréltük, az egész gráfból kikeressük a legkisebb értékű ideiglenes címkéjű csomópontot. Ezt állandóvá tesszük, és ez lesz a következő körben a munkacsomópont. Az 5.7. ábrán az algoritmus első hat lépése látható.
Hogy lássuk, miért működik az algoritmus, nézzük az 5.7.(c) ábrát. Ezen a ponton éppen E-t tettük állandóvá. Tegyük fel, hogy volna ABE-nél rövidebb út, mondjuk AXYZE. Két lehetőség van: vagy már állandóvá tettük a Z csomópontot, vagy még nem. Ha igen, akkor az E-t már megvizsgáltuk (abban a körben, ami előtt Z-t állandóvá tettük), tehát az AXYZE nem kerülte el a figyelmünket és így nem lehet a legrövidebb út.
Most nézzük azt az esetet, amikor Z még mindig ideiglenesen van felcímkézve. Z címkéje vagy nagyobb, vagy egyenlő E-ével, amikor is AXYZE nem lehet ABE-nél rövidebb út, vagy E-énél kisebb, amikor is Z, és nem E lesz előbb állandó, lehetővé téve, hogy E-t Z-ből vizsgálhassuk.
Ezt az algoritmust az 5.8. ábrán adjuk meg. Az n és dist globális változók írják le a gráfot; ezek még a shortest_path eljárás meghívása előtt inicializálásra kerülnek. A program és a fentebb leírt algoritmus között az egyetlen különbség, hogy az 5.8. ábrán a legrövidebb utat a végcsomóponttól, t-től számítjuk, a forráscsomópont, s helyett.
Mivel egy irányítatlan gráfban a t-től s-ig vezető legrövidebb út ugyanaz, mint az s-től t-ig vezető, nem számít, melyik végén kezdjük (hacsak nincs több legrövidebb út, amikor is a keresés megfordítása egy másikat derítene fel). A visszafelé keresésnek az az oka, hogy minden csomópontot a megelőző, és nem a következő csomóponttal címkéztünk fel. Amikor a végső utat a kimeneti változóba, a path-ba másoljuk, az útvonal megfordul. A két visszafordítás kioltja egymást, és a válasz a helyes sorrendben kerül kiadásra.
Az útválasztó algoritmus megvalósításakor minden útválasztónak helyi ismeretek alapján kell döntéseket hoznia, nem pedig a hálózat teljes képe alapján. Egy egyszerű helyi módszer az elárasztás (flooding), amelyben minden bejövő csomagot minden kimenő vonalon kiküldünk, kivéve azon, amelyiken beérkezett.
Az elárasztás nyilván nagyszámú kettőzött csomagot eredményez, valójában végtelen számút, hacsak nem teszünk intézkedéseket a folyamat visszafogására. Ilyen intézkedés, hogy legyen minden csomag fejrészében egy ugrásszámláló, amely minden ugráskor csökken eggyel, és ha eléri a nullát, a csomagot eldobjuk. Ideális esetben az ugrásszámláló kezdeti értékének a forrástól a célig vezető út hosszát kell beállítani. Ha a küldő nem tudja, milyen hosszú az út, beállíthatja a legrosszabb esetre, nevezetesen a hálózat teljes átmérőjére.
Az ugrásszámlálót alkalmazó elárasztás exponenciálisan megtöbbszörözheti a csomagokat az ugrásszám növekedésével, mert az útválasztók megduplázzák azokat a csomagokat, amelyeket már láttak. Az elárasztás gátak közé szorításának másik módja az, ha nyilvántartjuk, mely csomagokkal végeztük már el az elárasztást, így elkerülve, hogy másodszor is kiküldjük azokat. E cél elérésének egyik módja az, hogy a forrásútválasztó minden csomagba elhelyez egy sorszámot, amelyet a hosztjaitól kap. Ezek után minden útválasztónak szüksége van forrásútválasztónként egy listára, amely megmondja, mely sorszámokat látott már ebből a forrásból. Ha a beérkező csomag rajta van a listán, az útválasztó nem küldi tovább szomszédjainak.
A lista korlát nélküli növekedésének meggátolása érdekében minden listát ki kell egészíteni egy számlálóval, k-val, amelynek az a jelentése, hogy k-ig minden sorszám előfordult már. Amikor a csomag megérkezik, a sorszám és a k értékének összehasonlításával egyszerűen ellenőrizhető, hogy az másodpéldány-e. Ha igen, el kell dobni. Ráadásul az egész k alatti listára nincs is szükség, mivel k hatékonyan magába foglalja azt.
Az elárasztás sok csomag elküldésénél nem praktikus, de van néhány fontos alkalmazási helye. Először is, ez biztosítja, hogy egy csomag a hálózat összes csomópontjához eljusson. Ez azonban pazarlás lehet, ha egyetlen címzettnek van szüksége a csomagra, de adatszórásnál hatékony módszer. Vezeték nélküli hálózatokban egy állomás által továbbított összes üzenetet az adott állomással azonos vételkörzetben található összes állomás veheti, ami lényegében elárasztásnak tekinthető, és néhány algoritmus ki is használja ezt a tulajdonságot.
Másodszor az elárasztás rendkívül robusztus. Még nagyszámú útválasztó kiesése esetén (például háborús zónában lévő katonai hálózatban) is talál útvonalat – már amennyiben legalább egy létezik – a csomag célba juttatásához. Az elárasztáshoz nem szükséges túl sok előzetes beállítás. Ez azt jelenti, hogy használható más hatékonyabb, de több beállítást igénylő útválasztó algoritmus alapjaként. Az útválasztónak csak a szomszédjait kell ismernie. Az elárasztás mértékként is használható más útválasztó algoritmusok összehasonlításához. Az elárasztás mindig a legrövidebb utat választja, mert az összes lehetséges utat egyszerre választja. Ebből következően nincs olyan algoritmus, amely rövidebb késleltetést tudna produkálni (ha az elárasztási folyamatból adódó többletterhet elhanyagoljuk).
A számítógép-hálózatok általában dinamikus algoritmust használnak, ami lényegesen összetettebb, mint az elárasztás, de sokkal hatékonyabb is, mivel megtalálja a legrövidebb utat az aktuális topológiában. Két dinamikus algoritmus is igen népszerű: a távolságvektor-alapú és a kapcsolatállapot-alapú útválasztás. Ebben a szakaszban az előbbit, a következőben pedig az utóbbit fogjuk tanulmányozni.
A távolságvektor-alapú útválasztás (distance vector routing) alapja, hogy minden útválasztónak egy táblázatot (vagyis egy vektort) kell karbantartania, amelyben minden célhoz szerepel a legrövidebb ismert távolság, és annak a vonalnak az azonosítója, amelyiken a célhoz lehet eljutni. A táblázatokat a szomszédokkal való információcsere útján frissítik. Végül minden útválasztó tudni fogja a legjobb adatkapcsolatot minden célcím megtalálásához.
A távolságvektor-alapú útválasztó algoritmust néha máshogy is nevezik, mint például elosztott Bellman–Ford útválasztó algoritmus – az algoritmust kifejlesztő kutatók után [Bellman,1957; Ford és Fulkerson,1962]. Ez volt az ARPANET eredeti útválasztó algoritmusa és ezt használták az interneten is RIP néven.
A távolságvektor-alapú útválasztó algoritmusban minden útválasztó karbantart egy táblázatot, amelyet a hálózatban levő összes útválasztó szerint indexelnek, és amely mindegyikhez tartalmaz egy bejegyzést. Ez a bejegyzés két részből áll: az adott célhoz előnyben részesített kimeneti vonalból és a becsült távolságból. A távolság mérhető az ugrások számával vagy egyéb mértékkel (például késleltetéssel), amelyet a legrövidebb utak kiszámításánál megbeszéltünk.
Feltételezzük, hogy az útválasztó tudja a szomszédjaitól való „távolságát”. Ha a mérték az ugrások száma, akkor a távolság csak egy ugrás. Ha a mérték a sorhossz, akkor az útválasztó egyszerűen megvizsgál minden sort. Ha a mérték a késleltetés, az útválasztó ezt közvetlenül mérheti különleges ECHO csomagokkal, amelyeket a vevő csak időbélyeggel lát el és visszaküld, amilyen gyorsan csak tudja.
Példának okáért tételezzük fel, hogy a mérték a késleltetés, és az útválasztó ismeri az összes szomszédja felé a késleltetést. T ms-onként minden útválasztó minden szomszédjának listát küld az összes cél felé becsült késleltetéseiről. És minden szomszédjától kap egy hasonló listát. Képzeljük el, hogy épp most érkezett egy táblázat az X szomszédtól, amely tartalmazza 
-t, vagyis X becslését arról, hogy mennyi időbe telik az i útválasztóig eljutni. Ha az útválasztó tudja, hogy a késleltetés X felé m ms, akkor azt is tudja, hogy az i útválasztót X-en keresztül 
ms idő alatt tudja elérni. Ezt a számolást minden szomszédra elvégezve, egy útválasztó megtudhatja, melyik becslés tűnik a legjobbnak, és a következőkben ezt a becslést és a hozzá tartozó vonalat használja az új útválasztó táblázatban. Vegyük észre, hogy a régi útválasztó táblázatot nem használják a számításhoz.
Ezt a frissítési folyamatot illusztrálja az 5.9. ábra. Az (a) rész egy hálózatot ábrázol. A (b) rész első négy oszlopa a J útválasztó szomszédjaitól kapott késleltetési vektorokat mutatja. A állítása szerint B felé 12, C felé 25, D felé 40 ms-os késleltetése van. Tegyük fel, hogy J a szomszédjai, A, I, H és K felé a késleltetéseket sorrendben 8, 10, 12 és 6 ms-ra méri vagy becsüli.
5.9. ábra - (a) Egy hálózat. (b) J-hez érkező késleltetési vektorok A, I, H, K felől, és J új útválasztó táblázata
Gondoljuk el, hogyan számítja ki J a G felé vezető új útvonalat. Tudja, hogy el tud jutni A-ba 8 ms alatt, és A állítása szerint képes 18 ms alatt eljutni G-be, tehát J tudja, hogy 26 ms-os késleltetéssel kell számolnia, ha a G felé tartó csomagokat A-nak továbbítja. Hasonlóan, a G felé I-n, H-n és K-n keresztül tapasztalható késleltetés sorrendben 41-nek (31 + 10), 18-nak (6 + 12), és 37-nek (31 + 6) adódik. Ezen értékek közül a 18 a legjobb, így bejegyzi az útválasztó táblázatába, hogy G-ig a késleltetés 18 ms, és a használandó útvonal H-n keresztül vezet. Ugyanezt a számolást kell elvégezni az összes többi célra is. Az új útválasztó táblázat az ábra utolsó oszlopában látható.
A hálózatban a lehetséges útvonalak közül a legjobb út beállítását konvergenciának nevezik. A távolságvektor-alapú útválasztás nagyon hasznos, mivel ez egy olyan egyszerű módszer, amellyel az útválasztók együttesen tudják kiszámítani a legrövidebb utat, a gyakorlatban azonban egy komoly hátránya is van: jóllehet konvergál a helyes megoldáshoz, de ezt esetleg nagyon lassan teszi. Pontosabban, gyorsan reagál a jó hírre, de nagyon kényelmesen a rossz hírre.
Hogy lássuk, milyen gyorsan terjed a jó hír, vegyük az 5.10. ábra öt csomópontból álló (lineáris) hálózatát, ahol a késleltetés mértéke az ugrások száma. Tegyük fel, hogy A kezdetben nem működik, és ezt az összes többi útválasztó tudja. Más szavakkal, mind végtelent írtak be az A felé érvényes késleltetéshez.
Amikor A megjavul, a többi útválasztó ezt a vektorcserékből tudja meg. Az egyszerűség kedvéért feltételezzük, hogy létezik valahol egy hatalmas gong, amelynek periodikus ütéseire az útválasztók egyszerre cserélik ki vektoraikat. Az első csere idején B megtudja, hogy bal oldali szomszédjának nulla késleltetése van A-ig. B most bejegyzi az útválasztó táblázatába, hogy A egy ugrásnyira van balra. Az összes többi útválasztó még mindig azt gondolja, hogy A nem működik. Az ekkor érvényes útválasztó táblázatok A-ra vonatkozó bejegyzéseit láthatjuk az 5.10.(a) ábra második sorában. A következő cserekor C megtudja, hogy B-nek van egy 1 hosszú útja A felé, tehát frissíti az útválasztó táblázatát, hogy az egy 2 hosszú utat jelezzen, de D és E csak később tudja meg a jó hírt. Világos, hogy a jó hír egy ugrás/csere sebességgel terjed. Egy olyan hálózatban, ahol a leghosszabb út N ugrás hosszú, N csere múlva mindenki tudni fog az újjáéledt adatkapcsolatokról és útválasztókról.
Most vegyük az 5.10.(b) ábrán látható szituációt, ahol kezdetben minden adatkapcsolat és útválasztó működik. A B, C, D és E útválasztók távolsága A-tól sorrendben 1, 2, 3 és 4. Hirtelen A elromlik, vagy más esetben, az A és B közti vonal megszakad (ami B felől nézve gyakorlatilag ugyanaz).
Az első vektorcserénél B nem hall semmit A felől. Szerencsére C azt mondja: „Ne aggódj. Van egy A-hoz vezető 2 hosszú utam.” B nem tudhatja, hogy C útja magán B-n vezet keresztül. Amennyit B tud, aszerint C-nek akár tíz kimenő adatkapcsolata is lehet független A-hoz vezető utakkal, amelyek mind 2 hosszúak. Ennek eredményeként B most azt gondolja, hogy elérheti A-t C-n keresztül, egy 3 hosszú úttal. D és E nem frissítik az A-ra vonatkozó bejegyzéseiket az első cserekor.
A második cserekor C észreveszi, hogy mindkét szomszédja azt állítja, hogy az A-hoz vezető út 3 hosszú. Kiválaszt közülük egyet véletlenszerűen, és az A-hoz tartozó új távolságot 4-re állítja, mint ahogy az 5.10.(b) ábra harmadik sorában látszik. A sorozatos cserék idézik elő az 5.10.(b) ábra maradék részén mutatott történést.
Ebből az ábrából nyilvánvaló, miért terjed lassan a rossz hír: soha nincs egyik útválasztónak sem több mint eggyel magasabb értéke, mint a szomszédjainak a minimuma. Fokozatosan mindegyik útválasztó felküzdi magát a végtelenig, de az ehhez szükséges cserék száma a végtelen ábrázolásához használt számtól függ. Ennél az oknál fogva okos gondolat a végtelent a leghosszabb útvonalnál 1-gyel hosszabbra állítani.
Nem teljesen meglepő, hogy ez a probléma a végtelenig számolás (count-to-infinity) problémájaként ismert. Történt már néhány kísérlet a probléma megoldására, például annak megakadályozásával, hogy az útválasztók hirdessék a legjobb útvonalaikat azon szomszédjaik felé, akiktől hallották azokat, a megosztott láthatár tiltott visszaúttal (split horizon with poisoned reverse) szabályainak megfelelően, ahogy azt az RFC 1058 bemutatja. A jól csengő nevek ellenére ezek közül a heurisztikus módszerek közül egyik sem működik jól a gyakorlatban. A probléma lényege az, hogy ha X elmondja Y-nak, hogy van egy valahová vezető útja, Y-nak sehogy sem áll módjában megtudnia, hogy vajon ő maga rajta van-e ezen az úton.
Távolságvektor-alapú útválasztást használt az ARPANET 1979-ig, amikor is ezt felváltotta a kapcsolatállapot-alapú útválasztás. Az elsődleges probléma, amely ehhez a váltáshoz vezetett, hogy az algoritmus egyensúlyba kerülése túl sokáig tartott a hálózati topológia változása után (a végtelenig számolás problémája miatt). Következésképpen ezt egy teljesen új algoritmus váltotta fel, amelyet kapcsolatállapot-alapú útválasztásnak (link state routing) neveznek. Manapság a kapcsolatállapot-alapú útválasztás különböző változatait (IS-IS és OSPF) széles körben használják nagy hálózatokban és az interneten.
A kapcsolatállapot-alapú útválasztás mögötti ötlet egyszerű, és öt részből tehető össze. Minden útválasztónak a következőket kell tennie:
Felkutatni a szomszédjait és megtudni a hálózati címeiket.
Beállítani a távolság vagy a költség értékét a minden szomszédjáig mért késleltetés alapján.
Összeállítani egy csomagot, amely a most megtudottakat tartalmazza.
Elküldeni ezt a csomagot az összes többi útválasztónak.
Kiszámítani az összes többi útválasztóhoz vezető legrövidebb utat.
Lényegében a teljes topológia eljut az összes útválasztóhoz. Ezután a Dijkstra-algoritmust futtatják az útválasztók, hogy megtalálják a legrövidebb utat az összes többi útválasztóhoz. A következőkben mind az öt lépést részletesebben is megvizsgáljuk.
Amikor egy útválasztó beindul, az első feladata, hogy megtudja, kik a szomszédai. Ezt a célt úgy éri el, hogy egy speciális hello csomagot küld ki minden hozzá kapcsolódó kétpontos vonalon. A másik végen levő útválasztótól elvárja, hogy küldjön vissza egy választ, amelyben közli azonosítóját. Ezeknek a neveknek globálisan egyedieknek kell lenniük, mert amikor később egy távoli útválasztó azt hallja, hogy három útválasztó az F-hez csatlakozik, el kell döntenie, hogy mind a három ugyanaz az F vagy sem.
Amikor két vagy több útválasztót üzenetszórásos adatkapcsolat köt össze (például kapcsoló, gyűrű vagy klasszikus Ethernet), a helyzet kicsivel bonyolultabb. Az 5.11.(a) ábra egy üzenetszórásos LAN-t mutat, amelyhez három útválasztó: A, C és F kapcsolódik közvetlenül. Mindegyik útválasztóhoz egy vagy több további útválasztó kapcsolódik, amint azt az ábra mutatja.
Az üzenetszórásos LAN minden csatlakoztatott útválasztópár között kapcsolatot létesít. A LAN több kétpontos típusú adatkapcsolatként történő modellezése azonban növeli a topológia méretét és üzenetek elvesztéséhez vezet. Jobb módszer, ha a LAN-t magát egy csomópontnak tekintjük, amint azt az 5.11.(b) ábra mutatja. Itt egy új, mesterséges csomópontot vezettünk be, az N-t, amihez A, C és F kapcsolódik. Kiválasztunk a LAN-on egy kijelölt útválasztót (designated router), amely az N szerepét fogja játszani az útválasztó protokollban. A tényt, hogy lehetséges A-tól C-ig eljutni a LAN-on, itt az ANC út mutatja.
A kapcsolatállapot-alapú útválasztó algoritmus megköveteli, hogy minden adatkapcsolat rendelkezzen a legrövidebb út megtalálására vonatkozó távolság vagy költség mérőszámmal. A szomszédok elérésének költsége beállítható automatikusan, vagy azt beállíthatja a hálózat operátora. Általános választási lehetőség az adatkapcsolat költségének beállítására, hogy a költség fordítottan arányos az adatkapcsolat sávszélességével. Például az 1 Gb/s-os Ethernet költsége 1, a 100 Mb/s-os Etherneté pedig 10. Ez a nagyobb kapacitású utakat jobb választásnak tekinti.
Ha a hálózat földrajzilag kiterjedt, akkor az adatkapcsolatok késleltetését is figyelembe lehet venni a költség kiszámításánál, így a rövidebb adatkapcsolaton lévő útvonalak jobb választásnak bizonyulnak. A késleltetés meghatározásának legközvetlenebb módja egy speciális echo csomag kiküldése a vonalon, amelyet a másik oldalnak azonnal vissza kell küldenie. A körülfordulási idő megmérésével és kettővel osztásával a küldő útválasztó elfogadható becslést kaphat a késleltetés mértékéről.
Az információcseréhez szükséges adatok összegyűjtése után a következő lépés, hogy minden útválasztó összeállít egy csomagot, amely az összes adatot tartalmazza. A csomag a feladó azonosítójával kezdődik, amit egy sorszám és egy korérték (ezt később tárgyaljuk), végül pedig a szomszédok listája követ. Minden szomszédhoz megadják a feléje tapasztalható költséget is. Az 5.12.(a) ábrán egy példahálózatot mutat a vonali költségek feltüntetésével. Az 5.12.(b) ábrán mind a hat útválasztóhoz láthatók a megfelelő kapcsolatállapot-csomagok.
A kapcsolatállapot-csomagok összeállítása egyszerű. A nehézséget annak eldöntése jelenti, hogy mikor állítsuk össze azokat. Az egyik lehetőség, hogy periodikusan, vagyis szabályos időközönként. Egy másik lehetőség, hogy amikor valami jelentős esemény történt, mint például egy vonal vagy szomszéd meghibásodott, megjavult vagy megváltoztatta a tulajdonságait.
Az algoritmus legtrükkösebb része a kapcsolatállapot-csomagok szétosztása. Minden útválasztónak az összes kapcsolatállapot-csomagot gyorsan és megbízhatóan meg kell kapnia. Ha a különböző útválasztók esetleg a topológia más-más változatait használják, akkor az általuk kiszámított utak inkonzisztensek lehetnek, előfordulhatnak például hurkok, elérhetetlen gépek és egyéb problémák.
Először leírjuk az alapvető szétosztó algoritmust, majd később pár finomítást is adunk. Az alapötlet az, hogy az elárasztást használjuk a kapcsolatállapot-csomagok szétosztására. Hogy az elárasztást kézben tartsák, minden csomag tartalmaz egy sorszámot, amely minden egyes csomagküldésnél eggyel növekedik. Az útválasztók számon tartanak minden (forrásútválasztó, sorszám) párt, amit csak látnak. Amikor egy új kapcsolatállapot-csomag érkezik, összevetik a már látott csomagok listájával. Ha új, eddig nem látott csomag érkezett, akkor továbbítják minden vonalon, kivéve azon, amelyiken érkezett. Ha másodpéldány, eldobják. Ha egy csomag olyan sorszámmal érkezik, amely kisebb, mint a legnagyobb már látott sorszám, akkor az útválasztó elavult csomagnak tekinti, és nem továbbítja, hiszen az útválasztó rendelkezik már ennél frissebb információval is.
Ennek az algoritmusnak van néhány problémája, de ezek kezelhetők. Először is, ha a sorszámok átfordulnak, zűrzavar fog eluralkodni. Itt az a megoldás, hogy 32 bites sorszámokat kell használni. Másodpercenként egy kapcsolatállapot-csomag elküldését feltételezve, az átfordulás 137 év múlva következne be, így ezt a lehetőséget figyelmen kívül hagyhatjuk.
Másodszor, ha egy útválasztó valamikor összeomlik, elfelejti, melyik sorszámnál tartott. Ha újra 0-ról kezdi, a következő általa küldött csomagot másodpéldánynak fogják tekinteni, és nem továbbítják.
Harmadszor, ha egy sorszám megsérül, és 65 540 érkezik meg 4 helyett (egy 1 bites hiba), az 5-től 65 540-ig tartó csomagokat elavultként visszautasítja, mivel a jelenlegi sorszámot 65 540-nek hiszi.
Mindezekre a problémákra az a megoldás, hogy minden csomagba a sorszáma után a csomag életkorát is bele kell tenni, és ezt másodpercenként eggyel csökkenteni kell. Amikor az életkor eléri a nullát, az attól az útválasztótól származó információt eldobják. Rendszerint, mondjuk 10 másodpercenként érkezik egy új csomag, tehát az útválasztó információja csak akkor válik használhatatlanná, ha egy útválasztó meghibásodott (vagy ha hat egymás után következő csomag elveszett, de ez valószínűtlen). Az életkor mező értékét minden útválasztó csökkenti is a kezdeti elárasztási folyamat során, így biztosítva azt, hogy egyetlen csomag sem veszhet el, és hogy nem élhet közelebbről meg nem határozott ideig (egy nulla életkorú csomag eldobásra kerül).
A robusztusabbá tételhez néhány finomításra van szükség. Amikor egy kapcsolatállapot-csomag beérkezik az útválasztóhoz elárasztásra, nem kerül bele rögtön az adásra várakozó csomagok sorába. Ehelyett egy ideiglenes tárolóterületre kerül, hogy ott egy keveset várakozzon. Ha egy másik kapcsolatállapot-csomag is beérkezik ugyanattól a forrástól, mielőtt az előző továbbítódna, az elküldés előtt az útválasztó összehasonlítja a sorszámukat. Ha egyenlők, a másodpéldányt eldobja kerül. Ha különböznek, a régebbi példány kerül eldobásra. Az útválasztók közti vonalakon bekövetkező hibák kivédésére minden kapcsolatállapot-csomagot nyugtáznak.
Az 5.13. ábrán látható a B útválasztó által az 5.12.(a) ábra hálózatához használt adatstruktúra. Minden sor megfelel egy nemrég érkezett, de még nem teljesen feldolgozott kapcsolatállapot-csomagnak. A táblázat rögzíti, honnan indult a csomag, a sorszámát, a korát és az adatokat. Ezen kívül B mindhárom adatkapcsolatához (az A, C, illetve F felé vezetőkhöz) vannak küldési és nyugtázási jelzőbitek. A küldési jelzőbitek azt jelentik, hogy a csomagot a jelzett adatkapcsolaton tovább kell küldeni. A nyugtázási jelzőbitek azt jelentik, hogy ott a csomagot nyugtázni kell.
Az 5.13. ábrán az A kapcsolatállapot-csomagja közvetlenül érkezett, így el kell küldeni C-nek és F-nek, és nyugtázni A-nak, ahogy a jelzőbitek mutatják. Hasonlóan az F-től érkezett csomagot továbbítani kell A-nak és C-nek, és nyugtázni F-nek.
A harmadik, E-től érkezett csomaggal azonban más a helyzet. Ez kétszer is megjött, egyszer EAB-n és egyszer EFB-n keresztül. Következésképpen csak C felé kell elküldeni, de A és F felé is nyugtázni kell, ahogy a jelzőbitek mutatják.
Ha egy másodpéldány érkezik, amíg az eredeti még mindig a pufferben van, a jelzőbiteket át kell állítani. Például ha egy másolat érkezik F felől C állapotáról, mielőtt a táblázat negyedik bejegyzését továbbították volna, a hat jelzőbitet 100011-re kell változtatni, hogy jelezve, hogy a csomagot nyugtázni kell F felé, de elküldeni nem.
Amint az útválasztó összegyűjtötte a kapcsolatállapot-csomagok teljes készletét, megszerkesztheti a hálózat teljes gráfját, mivel minden adatkapcsolat látható. Valójában minden adatkapcsolat kétszer szerepel, egyszer-egyszer mindkét irányban. A különböző irányokhoz eltérő költség tartozhat. Elképzelhető, hogy a legrövidebb útvonal kiszámítás az A-B irányhoz más útvonalat talál, mint a B-A irányhoz.
Most helyileg lefuttatja a Dijkstra-algoritmust, hogy megszerkessze a legrövidebb utat minden lehetséges célhoz. Ennek az algoritmusnak az eredményei mutatják meg az útválasztónak, hogy az egyes célok eléréséhez melyik adatkapcsolatot használja. Ezek az adatok bekerülnek az útválasztó táblába, és ezután visszatérhet a normális működés.
A távolságvektor-alapú útválasztáshoz viszonyítva a kapcsolatállapot-alapú útválasztás több memóriát és számítást igényel. Egy olyan hálózatban, amely n útválasztóból áll, és mindegyik útválasztónak k szomszédja van, a bejövő adat tárolásához szükséges memória mérete kn-nel arányos, ami legalább akkora, mint az összes célt tartalmazó útválasztó tábla. A számítási idő még a leghatékonyabb adatszerkezetek esetén is gyorsabban nő mint kn, és ez nagy hálózatoknál gondot jelenthet. Mindezek ellenére a kapcsolatállapot-alapú útválasztás sok gyakorlati helyzetben jól működik, mivel a lassú egyensúlyba hozás (konvergencia) itt nem jelent problémát.
A kapcsolatállapot-alapú útválasztást széles körben használják a jelenlegi hálózatokban, ezért helyénvaló pár szót szólni az ezeket használó példa-protokollokról. Számos szolgáltató használja az IS-IS (Intermediate System to Intermediate System Intradomain Routing Protocol – közbenső rendszertől közbenső rendszerig történő körzeten belüli útválasztó protokoll) kapcsolatállapot-alapú protokollt [Oran, 1990], amelyet a DECnet számára terveztek, és amelyet később átvett az ISO is az OSI-protokollhoz. Azóta módosították, hogy más protokollokat is kezeljen, különösen az IP-t. Az OSPF (Open Shortest Path First – nyílt hozzáférésű, a legrövidebb utat előrevevő protokoll) a másik fontos kapcsolatállapot-alapú protokoll. Ezt az IETF fejlesztette ki évekkel az IS-IS után, az IS-IS számos újítását átörökítve. Ezek közül az újítások közül említhetnénk például a kapcsolatállapot-frissítések elárasztásának önstabilizáló eljárását, a kijelölt útválasztó koncepcióját egy LAN-on, valamint az utak kettéosztásának és többfajta mérték használatának számítási és támogatási módszerét. Ennek következtében csak nagyon kicsi a különbség az OSPF és az IS-IS között. A legfontosabb eltérés az, hogy az IS-IS egyszerre több hálózati rétegbeli protokollról tud információit szállítani (például IP, IPX és AppleTalk), és ez előnyös nagy, többprotokollos környezetekben, míg az OSPF ezzel a képességgel nem rendelkezik. Az OSPF-et az 5.6.6. szakaszban ismertetjük.
Az útválasztó algoritmusokkal kapcsolatos általános véleménnyel is szolgálunk. A kapcsolatállapot-alapú, a távolságvektor-alapú és egyéb algoritmusok az összes útválasztóra építenek az útvonalak kiszámításánál. A hardver- és szoftverproblémák még kisszámú útválasztó esetén is nagy pusztítást okozhatnak a hálózatban. Ha például egy útválasztó egy olyan adatkapcsolatot tételez fel, amely már nem létezik, vagy elfelejtkezik egy létező adatkapcsolatról, akkor a hálózati gráf helytelen lesz. Ha egy útválasztó nem tud csomagokat továbbítani, vagy elrontja a csomagokat küldés közben, akkor az útvonal nem az elvárt módon fog működni. Végül hibás működéshez vezet az is, ha elfogy a memória vagy helytelen az útválasztási számítás. Ahogy a hálózat növekszik, és több tíz- vagy akár több százezer csomópontot tartalmaz, az egyes útválasztók meghibásodásának valószínűsége már nem elhanyagolható. A fő szempont az, hogy megpróbáljuk minimalizálni a kárt, amikor az elkerülhetetlenül bekövetkezik. Ezekkel a problémákkal és lehetséges megoldásaikkal részletesen Perlman [1988] foglalkozik.
Ahogy a hálózat mérete nő, az útválasztók útválasztó táblázatai is arányosan nőnek. Az egyre növekvő táblázatok nemcsak az útválasztók memóriáját fogyasztják, hanem több CPU-időre van szükség a táblázatok átvizsgálásához, és nagyobb sávszélesség szükséges ahhoz, hogy elküldjék az ezekről szóló állapotjelentéseket. Egyszer csak a hálózat akkorára nő, hogy már nem lehetséges minden egyes útválasztóban minden más útválasztó számára egy bejegyzést fenntartani, ezért az útválasztást hierarchikusan kell elvégezni, ahogy azt a telefonhálózatban is teszik.
Amikor hierarchikus útválasztást használnak, az útválasztókat úgynevezett tartományokra (regions) osztják. Minden útválasztó tudja, hogyan irányítsa a saját tartományán belüli célok felé a csomagokat, de nem tud semmit a többi tartomány belső szerkezetéről. Amikor különböző hálózatokat kapcsolunk össze, természetes, hogy mindegyiket különálló tartománynak tekintjük, és így az egyik hálózaton belüli útválasztóknak nem kell tudniuk semmit a többi hálózat topológiájáról.
Hatalmas hálózatok esetén lehet, hogy nem elég a kétszintű hierarchia. Szükség lehet arra, hogy a tartományokat kerületekbe, a kerületeket zónákba, a zónákat csoportokba szervezzük és így tovább, amíg csak ki nem fogyunk az egyesítésekre használt nevekből. A többszintű hierarchiára példaként nézzük meg, hogyan irányíthatnak egy csomagot a kaliforniai Berkeleyből a kenyai Malindibe. A Berkeleyben lévő útválasztó ismerné a Kalifornián belüli részletes topológiát, de minden, az államból kifelé tartó forgalmat a Los Angeles-i útválasztóhoz küldene. A Los Angeles-i útválasztó képes lenne a többi belföldi útválasztóhoz irányítani a forgalmat, de a külföldi forgalmat New Yorkba küldené. A New York-i útválasztó úgy lenne programozva, hogy minden forgalmat a célország külföldi forgalomért felelős útválasztójához küldjön, mondjuk Nairobiba. Végül a csomag lefelé haladna a kenyai fán belül, amíg el nem érné Malindit.
Az 5.14. ábra egy mennyiségi példát hoz az útválasztásra egy kétszintű hierarchiában, öt tartománnyal. Az 1A teljes útválasztó táblázata 17 bejegyzést tartalmaz, ahogy az az 5.14.(b) ábrán látható. Amikor az útválasztást hierarchikusan végezzük, mint az 5.14.(c) ábrán, akkor, mint előzőleg, vannak a helyi útválasztókra vonatkozó bejegyzések, de a többi tartományt egy-egy csomópontba sűrítettük össze. Így a 2. tartomány felé tartó összes forgalom az 1B–2A vonalon keresztül halad, de a távoli forgalom többi része az 1C–3B vonalat használja. A hierarchikus útválasztás a táblázat méretét 17 bejegyzésről 7-re csökkentette. Ahogy a tartományok számának tartományonkénti útválasztók számához viszonyított aránya nő, úgy növekszik a megtakarítás a táblázathelyekben.
Sajnos ez a helymegtakarítás nincs ingyen. Ezért büntetést kell fizetni, mégpedig a megnövekedett úthossz formájában. Például az 1A és 5C közti legjobb út a 2-es tartományon át vezet, de a hierarchikus útválasztásnál minden, az 5-ös tartomány felé tartó forgalom a 3-as tartományon keresztül zajlik, mert az 5-ös tartományon belül a legtöbb célhoz ez a jobb.
Amikor egy egyedülálló hálózat nagyon nagyra nő, felmerül egy érdekes kérdés: hány szintje legyen a hierarchiának? Vegyünk például egy 720 útválasztóból álló hálózatot. Ha nincs hierarchia, minden útválasztónak 720 táblázatbejegyzésre van szüksége. Ha a hálózatot felosztjuk 24 tartományra, amelyek közül mindegyikben 30 útválasztó van, minden útválasztónak 30 helyi és 23 távoli bejegyzésre van szüksége, ez összesen 53 bejegyzés. Ha háromszintű hierarchiát választunk nyolc kerülettel, amelyek közül mindegyik 9, tíz útválasztós tartományból áll, minden útválasztónak 10 bejegyzésre van szüksége a helyi útválasztókhoz, 8 bejegyzésre a saját kerületen belüli tartományokhoz, és 7 bejegyzésre a távoli kerületekhez, ez összesen 25 bejegyzés. Kamoun és Kleinrock [1979] felfedezték, hogy egy N útválasztóból álló hálózathoz a szintek optimális száma ln N, amely e ln N bejegyzést igényel útválasztónként. Azt is megmutatták, hogy a hierarchikus útválasztás által okozott tényleges átlagos úthossznövekedés elegendően kicsi, úgyhogy rendszerint elfogadható.
Néhány alkalmazásban a hosztoknak üzeneteket kell küldeniük néhány másik hosztnak vagy az összes többi hosztnak. Például egy olyan szolgáltatás, amely időjárás-jelentést, tőzsdei híreket vagy élő rádióműsort oszt szét, a legjobban úgy működhet, hogy adatszórással minden géphez adatokat küld, és az érdeklődők elolvashatják azokat. Egy csomag mindenhová történő egyidejű elküldését adatszórásnak (broadcasting) nevezzük. Különböző módszereket javasoltak ennek megvalósítására.
Az egyik adatszóró eljárás, amely nem igényel semmi különleges képességet a hálózattól, úgy működik, hogy a forrás egyszerűen külön csomagot küld minden egyes rendeltetési helyre. Ez a megoldás nemcsak sávszélesség-pazarló és lassú, hanem azt is megköveteli a forrástól, hogy rendelkezzen a rendeltetési helyek teljes listájával. Ez a legszélesebb körben alkalmazható, de a gyakorlatban a legkevésbé kívánatos eljárás.
Ennek továbbfejlesztése a többcélú útválasztás (multidestination routing). Itt minden csomag tartalmaz vagy egy listát a rendeltetési helyekről, vagy egy bittérképet, amely a kívánt rendeltetési helyeket jelzi. Amikor egy csomag megérkezik egy útválasztóhoz, az útválasztó megnézi a rendeltetési helyek listáját, hogy eldöntse, mely kimeneti vonalakra lesz szüksége. (Akkor van kimeneti vonalra szüksége, ha az az út a legjobb út legalább egy rendeltetési hely felé.) Az útválasztó előállítja a csomag egy új másolatát minden használandó kimeneti vonal számára, és csak azokat a célcímeket teszi bele, amelyeknek azt a vonalat kell használniuk. Ezzel a rendeltetési helyek halmazát felosztja a kimenő vonalak közt. Elegendő számú ugrás megtétele után minden csomag csak egy címet fog tartalmazni, és normális csomagként kezelhető. A többcélú útválasztás olyan, mint a külön-külön címzett csomagok esete, kivéve azt az esetet, amikor több csomagnak is ugyanazt az útvonalat kell követnie. Ilyenkor az egyik fizeti a teljes viteldíjat, a többi ingyen utazik. A hálózati sávszélesség így hatékonyabban kihasználható. Ebben a sémában a forrásnak továbbra is ismernie kell az összes célt, és az útválasztónak ugyanakkora erőfeszítésbe kerül meghatároznia azt, hogy hova kell küldeni egy többcélú csomagot, mintha több különböző csomagot küldene.
Ennél jobb adatszóró technikát is láttunk már: az elárasztást. Ha a megvalósításnál forrásonkénti sorszámozást alkalmazunk, akkor az elárasztás hatékonyan használja a vonalakat az útválasztók döntési szabályával, amely viszonylag egyszerű. Jóllehet az elárasztás nem megfelelő a szokásos kétpontos kommunikációhoz, de adatszórás esetén érdemes megfontolni az alkalmazását. Az is kiderül azonban, hogy ennél jobb megoldást is találhatunk, ha már egyszer kiszámítottuk a közönséges csomagok legrövidebb útvonalát.
A visszairányú továbbítás (reverse path forwarding) alapjául szolgáló ötlet elegáns és figyelemre méltóan egyszerű, ha már egyszer megmutatták [Dalal és Metcalfe, 1978]. Amikor egy adatszórásos csomag megérkezik egy útválasztóhoz, az útválasztó ellenőrzi, hogy azon az adatkapcsolaton kapta-e meg, amelyen rendszerint ő szokott az adatszórás forrásához csomagot küldeni. Ha igen, akkor nagy esély van rá, hogy az adatszórásos csomag a legjobb utat követte a szomszédos útválasztótól, és ezért ez az első másolat, amely megérkezett a tekintett útválasztóhoz. Ha ez az eset, az útválasztó másolatot továbbít minden adatkapcsolatra, kivéve arra, amelyiken érkezett. Viszont, ha az adatszórásos csomag más adatkapcsolaton érkezett, mint amit a forrás eléréséhez előnyben részesített, a csomagot eldobja, mint valószínű másodpéldányt.
A visszairányú továbbítás algoritmusára az 5.15. ábrán láthatunk példát. Az (a) rész a hálózatot, a (b) rész a hálózat I útválasztójának nyelőfáját, a (c) rész pedig a visszairányú algoritmus működését szemlélteti. Az első ugrás során I csomagokat küld F-nek, H-nak, J-nek és N-nek, ahogy azt a fa második sora mutatja. Ezen csomagok közül mindegyik az I felé vezető előnyben részesített úton érkezett (feltételezve, hogy az előnyben részesített utak egybeesnek a nyelőfával); ezt jelzi a betűk körüli kör. A második ugrás során nyolc csomag keletkezik: minden olyan útválasztó, amely az első ugrás során megkapta a csomagot, létrehoz kettőt. Amint látjuk, mind a nyolc még meg nem látogatott útválasztóhoz érkezik, és öt közülük az előnyben részesített vonalon. Abból a hat csomagból, amelyik a harmadik ugrás során keletkezik, csak három érkezik az előnyben részesített úton (C-hez, E-hez és K-hoz); a többi másodpéldány. Öt ugrás és 24 csomag után az adatszórás befejeződik, ezzel szemben a nyelőfa pontos követésekor négy ugrásra és 14 csomagra lett volna szükség.
5.15. ábra - Visszairányú továbbítás. (a) Hálózat. (b) Nyelőfa. (c) A visszairányú továbbítás által felépített fa
A visszairányú továbbítás legfontosabb előnye, hogy hatékony és könnyen megvalósítható. Az adatszórásos csomagot minden adatkapcsolaton csak egyszer küldi ki csakúgy, mint az elárasztásnál, de csak azt követeli meg, hogy az útválasztó tudja: az egyes célok hogyan érhetők el, azt nem, hogy megjegyezze a sorszámokat (vagy egyéb módszert használjon az elárasztás megakadályozására), vagy hogy felsorolja a csomagban az összes célt.
Az utolsó adatszórásos algoritmus javítja a visszairányú továbbítás működését. Explicit módon használja a nyelőfát – vagy egyéb más megszokott feszítőfát – az adatszórást kezdeményező útválasztóhoz. A feszítőfa részhalmaza annak a hálózatnak, amely tartalmazza az összes útválasztót, de nem tartalmaz hurkot. A nyelőfák maguk is feszítőfák. Ha minden útválasztó tudja, hogy melyik vonal tartozik a feszítőfához, akkor le tudja másolni a bejövő adatszórásos csomagot a feszítőfa vonalaira, annak a kivételével, amelyen a csomag érkezett. Ez a sávszélesség tökéletes kihasználását biztosítja azáltal, hogy csak a feladat elvégzéséhez elengedhetetlenül szükséges, minimális mennyiségű csomagot generálja. Ha az 5.15. ábra (b) részében lévő nyelőfa kerül felhasználásra feszítőfaként, akkor az adatszórásos csomag a minimális 14 csomaggal kerül továbbküldésre. Az egyetlen probléma, hogy minden útválasztónak ismernie kell néhány feszítőfát a módszer alkalmazásához. Bizonyos esetekben ezek az adatok rendelkezésre állnak (kapcsolatállapot-alapú útválasztás esetén az összes útválasztó ismeri a teljes topológiát, így ki tudnak számítani egy feszítőfát), de néha nem.
Néhány alkalmazás – például egy többszereplős játék vagy egy sportesemény élő videoközvetítése, amelyet több helyszínen néznek –, több vevőnek küld csomagokat. Hacsak a csoport nem nagyon kicsi, nagyon drága különálló csomagot küldeni minden címzettnek. Másrészről a csomag adatszórásos küldése nagyon pazarló, ha a csoport mondjuk, egy millió csomópontból álló hálózat 1000 számítógépét foglalja magában, mivel a címzettek nagy része nem kíváncsi az üzenetre (vagy ami még rosszabb, lehet, hogy érdekli őket, de nem volna szabad látniuk azt). Ezért szükség van arra, hogy az üzeneteket egy jól meghatározott csoportnak tudjuk küldeni, amelynek tagszáma relatíve nagy, de a teljes hálózathoz képest elenyésző.
Az ilyen csoportnak történő üzenetküldést többesküldésnek (multicasting), a hozzá tartozó útválasztó algoritmust pedig többesküldéses útválasztásnak (multicast routing) nevezzük. Az összes többesküldéses séma megköveteli csoportok létrehozását és megsemmisítését, valamint a csoport tagjainak azonosítását. Hogy hogyan valósulnak meg ezek a feladatok, azzal az útválasztó algoritmus nem foglalkozik. Feltételezzük, hogy minden csoportot egy többesküldéses cím azonosít, valamint azt, hogy az útválasztók tudják, hogy melyik csoporthoz tartoznak. A csoporttagsággal újra foglalkozni fogunk az internet hálózati rétegének bemutatásakor, az 5.6. fejezetben.
A többesküldéses útválasztó séma a már tanulmányozott adatszórásos útválasztásra épül, amelyben a csomagok a feszítőfák mentén kerülnek kiküldésre, hogy a csomagokat csak a csoport tagjai kapják meg, a sávszélesség hatékony kihasználása mellett. A legjobb feszítőfa kiválasztása azonban attól függ, hogy vajon a csoport sűrű, a hálózat nagy részén szétszóródó vevőkkel, vagy ritka, a hálózat nagy részén olyan vevőkkel, amelyek nem tartoznak a csoporthoz. Ebben a fejezetben mindkét esetet tárgyaljuk.
Ha a csoport sűrű, akkor az adatszórás jó kiindulás, mivel hatékonyan eljuttatja a csomagot a hálózat minden részébe. De néhány olyan útválasztóhoz is elkerül a csomag, amely nem tagja a csoportnak, és ez pazarlás. Erre a megoldás Deering és Cheriton [1990] felfedezése szerint az, hogy az adatszórásos feszítőfát csonkolni kell azoknak az adatkapcsolatoknak az eltávolításával, amelyek nem a csoport tagjaihoz vezetnek. Ennek eredménye egy hatékony többesküldéses feszítőfa.
Az 5.16.(a) ábrán például egy hálózat látható két csoporttal, 1-gyel és 2-vel. Néhány útválasztó olyan hosztokhoz csatlakozik, amelyek legalább az egyik csoporthoz tartoznak, ahogy az az ábrán látható. A legbaloldalibb útválasztó feszítőfája látható az 5.16.(b) ábrán. Ez a fa használható adatszóráshoz, de többesküldéshez túlzás, ahogy a következő részben látható csonkolt verziók mutatják. Az 5.16.(c) ábrán az összes olyan adatkapcsolat eltávolításra került, amely nem az 1-es csoport tagját képező hoszthoz vezet. A csomagok csak ennek a feszítőfának a mentén kerülnek továbbításra, amely hatékonyabb, mint az adatszórási fa, mivel 10 adatkapcsolat helyett csak 7-et tartalmaz. Az 5.16.(d) ábra a 2-es csoport többesküldéses feszítőfáját mutatja csonkolás után. Ez szintén hatékony, mert csak öt adatkapcsolatot tartalmaz. Ez azt is mutatja, hogy a különböző többesküldéses csoportokhoz különböző feszítőfák tartoznak.
5.16. ábra - (a) Egy hálózat. (b) A legbaloldalibb útválasztó feszítőfája. (c) Többesküldéses fa az 1-es csoporthoz. (d) Többesküldéses fa a 2-es csoporthoz
A feszítőfa csonkolásának különféle módjai vannak. A legegyszerűbbet akkor használhatjuk, amikor kapcsolatállapot-alapú útválasztást használunk, és minden útválasztó ismeri a teljes topológiát, beleértve azt is, hogy mely hosztok mely csoportokhoz tartoznak. Minden útválasztó felépítheti a saját csonkolt feszítőfáját az adott csoport minden küldőjéhez a nyelőfa szokásos módon történő létrehozásával, majd eltávolítva azokat az adatkapcsolatokat, amelyek nem a csoporttagokat és a nyelő csomópontot kötik össze. Az MOSPF (Multicast OSPF – többesküldéses OSPF) példa az olyan kapcsolatállapot-alapú protokollra, amely ezt az elérést használja [Moy, 1994].
A távolságvektor-alapú útválasztásnál más csonkolási stratégiát követhetünk. Az alapalgoritmus a visszairányú továbbítás. Viszont, amikor egy olyan útválasztó kap többesküldéses üzenetet, amelynek nincs abban a csoportban érdekelt hosztja és nincs más útválasztókhoz adatkapcsolata, prune üzenettel válaszol, utasítva azt a szomszédját, amelyik az üzenetet küldte, hogy ennek a csoportnak szóló többesküldéseket ne küldjön többet. Amikor egy útválasztó, amelynek nincs csoporttag a hosztjai között, minden vonalán ilyen üzeneteket kapott, ő is prune üzenettel válaszolhat. Ily módon a feszítőfa rekurzívan csonkolásra kerül. A DVMRP (Distance Vector Multicast Routing Protocol – távolságvektor-alapú többesküldéses útválasztó protokoll) például egy ilyen módon működő többesküldéses útválasztó protokoll [Waitzman és mások, 1988].
A csonkolás hatékony feszítőfákat eredményez, amelyek csak a csoporttagok eléréséhez ténylegesen szükséges adatkapcsolatokat használják. Egy lehetséges hátrány, hogy az útválasztókra sok munka hárul, különösen nagy hálózatok esetén. Tegyük fel, hogy a hálózatban n csoport van, valamennyi átlagosan m taggal. Minden útválasztón, minden csoporthoz m csonkolt feszítőfát kell tárolni, ez összesen mn fa. Az 5.16.(c) ábra például a legbaloldalibb útválasztó 1-es csoporthoz tartozó feszítőfáját mutatja. A legjobboldalibb útválasztó 1-es csoporthoz tartozó feszítőfája (nem látható) nagyon különbözik ettől, mivel a csomagok közvetlenül a csoporttagokhoz kerülnek elküldésre, nem a gráf bal oldali részén keresztül. Ez azt jelenti, hogy az útválasztóknak az 1-es csoporthoz címzett csomagokat más irányba kell küldeniük attól függően, hogy melyik csomópont küld a csoportnak. Amikor sok nagy csoport van számos küldővel, tekintélyes méretű tár kell az összes fa tárolásához.
Egy alternatív kialakítás magalapú fákat (core-based trees) használ a csoport feszítőfájának kiszámításához [Ballardie és mások, 1993]. Az összes útválasztó megegyezik egy gyökérben (ezt magnak vagy találkozási pontnak hívják), és kialakításra kerül a fa oly módon, hogy minden tag csomagot küld a gyökér felé. A fa ezen csomagok által bejárt útvonalak uniója. Az 5.17(a) ábra az 1-es csoport magalapú fáját mutatja be. Ehhez a csoporthoz való küldéshez a küldő csomagot küld a magnak. Amikor a csomag eléri a magot, továbbításra kerül lefelé a fában. Ezt az 5.17(b) ábra mutatja a hálózat legjobboldalibb küldőjére. A teljesítőképesség optimalizálásaként a csoporthoz küldött csomagoknak nem kell eljutniuk a magig többesküldésük előtt. Amint a csomag eléri a fát, továbbítható felfelé a gyökér felé, valamint lefelé az összes többi ágon. Ez vonatkozik az 5.17(b) ábra tetején lévő küldőre.
Osztott fa nem optimális az összes forráshoz. Az 5.17(b) ábrán például a jobb oldalon lévő küldőtől érkező csomag a jobb felső csoporttagot a három ugrásra lévő magon keresztül éri el, nem közvetlenül. A hatékonyság mértéke attól függ, hogy hol található a mag és a küldő. Általában érdemes a magot a küldők közepére tenni. Ha csak egyetlen küldő van – mint például egy videofolyam esetén, amely egy csoporthoz kerül továbbításra –, akkor optimális megoldásként a küldőt kell magnak választani.
Vegyük figyelembe azt is, hogy az osztott fák jelentős megtakarítást jelentenek a tárolási költség, a küldött üzenetek mennyisége és a számítási igény szempontjából. Minden útválasztónak csoportonként csak egyetlen fát kell tárolnia m fa helyett. Azok az útválasztók, amelyek nem részei a fának, semmit nem tesznek a csoport támogatása érdekében. Emiatt az osztott fa módszer, a magalapú fához hasonlóan, többesküldéshez kerül felhasználásra ritka csoportok esetén az interneten, az olyan népszerű protokollok részeként, mint amilyen például a PIM (Protocol Independent Multicast – protokollfüggetlen többesküldés) [Fenner és mások, 2006].
Eddig olyan továbbítási modelleket mutattunk be, amelyekben egyetlen forrás küld adatokat egyetlen címzettnek (ezt nevezik egyesküldésnek), az összes címzettnek (adatszórás) vagy a címzettek egy adott csoportjának (többesküldés). Bizonyos esetekben azonban hasznos lehet egy másik továbbítási modell, a bárkinek küldés (anycast) modell alkalmazása. Bárkinek küldés esetén a csomag a csoport legközelebbi tagjának kerül kézbesítésre [Partridge és mások, 1993]. Azokat a sémákat, amelyekkel az ilyen útvonalak megtalálhatók, bárkinek küldéses útválasztásnak hívjuk.
Miért lehet érdemes bárkinek küldést használni? Bizonyos esetekben a csomópontok olyan szolgáltatást nyújtanak, mint például a pontos idő vagy a tartalomelosztás, ahol csak a megfelelő információ biztosítása számít, az nem érdekes, hogy melyik csomópont kapja az információt. Tetszőleges csomópont kaphatja. A bárkinek küldés például használható az interneten a DNS részeként, ahogy az a 7. fejezetben látható.
Szerencsére a bárkinek küldéshez nem kell új útválasztási sémát kitalálni, mivel a normál távolságvektor-alapú és kapcsolatállapot-alapú útválasztás elő tudja állítani a bárkinek küldés útvonalait. Tételezzük fel, hogy az 1-es csoport tagjai felé kívánunk bárkinek küldést alkalmazni. Az összes csoporttag „1”-es címet kap, nem kapnak különböző címeket. A távolságvektor-alapú útválasztás a vektorokat a szokásos módon kiosztja, és a csomópontok kiválasztják a legrövidebb útvonalat az 1-es célhoz. Ennek eredményeképpen a csomópontok az 1-es cél legközelebbi példányához küldik a csomagot. Az útvonalakat az 5.18(a) ábra mutatja. Ez az eljárás azért működik, mert az útválasztó protokoll nem tudja, hogy az 1-es cél több példánnyal rendelkezik. Az 1-es csomópont összes példányát egyetlen csomópontnak tekinti, ahogy azt az 5.18(b)ábrán látható topológia mutatja.
5.18. ábra - (a) Bárkinek küldéses útvonalak az 1-es csoporthoz. (b) Az útválasztó protokoll által látott topológia
Ez az eljárás kapcsolatállapot-alapú útválasztás esetén is működik, azzal kiegészítve, hogy az útválasztó protokollnak nem kell megtalálni azt a látszólag rövid útvonalat, amely átmegy az 1-es csomóponton. Ez a hipertéren átmenő ugrásokat okozna, mivel az 1-es csomópont példányai valóban olyan csomópontok, amelyek a hálózat különböző részein találhatók. A kapcsolatállapot-alapú protokollok azonban már különbséget tesznek az útválasztók és a hosztok között. Eddig ezt a tényt nem említettük, mivel a leíráshoz nem volt rá szükség.
Manapság több millió ember használ számítógépet utazás közben, a mozgó autókban lévő vezeték nélkül eszközöket használó, teljesen mobil helyzetektől kezdve olyan nomád helyzetekig, ahol a hordozható számítógépet különböző helyeken használják. A mozgó hoszt (mobile host) kifejezést mindkét kategóriára alkalmazzuk, a mozdulatlan (stationary) hosztoktól való megkülönböztetés érdekében. Egyre nagyobb igény mutatkozik arra, hogy a felhasználók, bárhol is vannak a világon, ugyanolyan könnyen tudják elérni a hálózatot, mintha otthon lennének. Ezek a mozgó hosztok újabb bonyodalmat jelentenek: ahhoz, hogy egy csomagot egy mozgó hoszthoz lehessen irányítani, a hálózatnak először meg kell találnia azt a hosztot.
Az általunk elképzelt világmodellben minden hoszt rendelkezik állandó lakhellyel (home location), amely sosem változik. Minden hosztnak van egy állandó lakcíme is, amelynek segítségével meghatározható a lakhely, hasonlóan, ahogy az 1-212-5551212 telefonszámból kiolvasható az Egyesült Államok (1-es országkód) és Manhattan (212). A mozgó hosztokat tartalmazó rendszerek útválasztási célja, hogy lehetővé tegyük a mozgó felhasználók számára csomagok küldését a lakcímükre, és hogy a csomagok hatékonyan érjék el őket, bárhol is legyenek. Természetesen a trükk az, hogy meg kell őket találni.
Ennek a modellnek a bemutatása következik. Egy eltérő modell lehetne, amelyik újra meg újra kiszámítja az útvonalat, amint a mozgó hoszt helyet változtat, és a topológia változik. Ezután egyszerűen használhatnánk e szakasz korábbi részében leírt útválasztási sémát. Az egyre növekvő számú mozgó hoszt miatt azonban ez a modell azt okozná, hogy a teljes hálózat vég nélkül új útvonalakat számítana ki. Az otthoni cím használata nagymértékben csökkenti ezt a terhet.
Másik alternatíva a mobilitás biztosítása a hálózati réteg felett, ami manapság jellemzően történik laptopoknál. Amikor új internetes helyre viszik, a laptopok új hálózati címet igényelnek. Nincs összefüggés a régi és új hálózati cím között. A hálózat nem tudja, hogy ez a két cím ugyanahhoz a laptophoz tartozik. Ebben a modellben a laptop használható webböngészésre, de más hosztok nem tudnak felé csomagot küldeni (például bejövő hívás esetén) magasabb rétegbeli helymeghatározási szolgáltatás kialakítása nélkül (például újra be kell jelentkezni a Skype-ba). Továbbá az összeköttetések nem tarthatók fenn, mialatt a hoszt mozgásban van. Ehelyett új összeköttetést kell elindítani. A hálózati rétegbeli mobilitással ezek a problémák megoldhatók.
Az interneten és a mobilhálózatokban a mobil útválasztásnál alkalmazott alapgondolat az, hogy a mozgó hosztok megmondják az otthoni hosztnak, hogy hol vannak. Ezt a hosztot, amely a mozgó hoszt nevében jár el, otthoni ügynöknek (home agent) hívjuk. Ha ez az ügynök tudja, hogy jelenleg hol található a mozgó hoszt, akkor csomagokat továbbíthat felé, így a csomagok kézbesítésre kerülnek.
Az 5.19. ábra a mobil útválasztást mutatja be működés közben. Az északnyugati Seattle városban lévő feladó csomagot kíván küldeni egy hosztnak, amely általános esetben az USA átellenes oldalán, New Yorkban található. Minket az az eset érdekel, amikor a mozgó hoszt nem otthon van, hanem ideiglenesen San Diegóban.
A San Diegóban lévő mozgó hosztnak helyi hálózati címet kell kérnie ahhoz, hogy használni tudja a hálózatot. Ez a szokásos módon zajlik. A fejezet későbbi részében mutatjuk be, hogy ez hogyan működik az interneten. A helyi címet c/o címnek (care-of address – továbbítási cím) hívjuk. Ha a mozgó hoszt megkapta ezt a címet, akkor meg tudja mondani ezt a címet az otthoni ügynöknek (1. lépés). Ez az üzenet látható az 5.19. ábrán szaggatott vonallal, ami azt jelzi, hogy ez egy vezérlőüzenet, nem adatüzenet.
Következő lépésként a feladó adatcsomagot küld a mozgó hoszt felé az állandó cím felhasználásával (2. lépés). Ezt a csomagot a hálózat a hoszt lakhelyére küldi, mivel ehhez tartozik az otthoni cím. New Yorkban az otthoni ügynök elfogadja ezt a csomagot, mivel a mozgó hoszt távol van az otthonától. Ezután beágyazza vagy becsomagolja a csomagot egy új fejrésszel, majd elküldi ezt a csomagot a továbbítási címre (3. lépés). Ezt a mechanizmust alagút típusú átvitelnek (tunneling) hívjuk. Ez nagyon fontos az interneten, így ezzel részletesebben is foglalkozunk.
Amikor a becsomagolt csomag megérkezik a c/o továbbítási címre, akkor a mozgó hoszt kibontja azt, és megkapja a feladó csomagját. A mozgó hoszt ezután a válaszcsomagot közvetlenül a feladónak küldi (4. lépés). A teljes útvonal meghatározását háromszögező útválasztásnak (triangle routing) hívják, mivel hosszadalmas lehet, ha az új hely távol van az otthoni helytől. A 4. lépés részeként a feladó megismerheti az aktuális c/o továbbítási címet. A további csomagok közvetlenül a mozgó hoszthoz küldhetők a c/o címre történő, alagút típusú továbbítással (5. lépés), az otthoni cím kihagyásával. Ha a kapcsolat valamilyen okból megszakad a mozgó hoszt mozgása közben, akkor az otthoni cím továbbra is használható a mozgó hoszt eléréséhez.
Fontos megjegyezni, hogy a leírásból kihagytuk a biztonságot. Általában amikor egy hoszt vagy útválasztó „Mostantól Stefani leveleit küldje nekem” formátumú üzenetet kap, akkor számos kérdés merülhet fel azzal kapcsolatban, hogy ki a másik fél, és hogy jó ötlet-e neki küldeni. Az üzenetek tartalmaznak biztonsági információt, úgy hogy az érvényességük titkosító protokollokkal ellenőrizhető, amelyet a 8. fejezetben tanulmányozunk.
Számos különböző mobil útválasztás létezik. A fenti séma IPv6-mobilitáson kerül modellezésre. Ezt használják az interneten [Johnson és mások, 2004], valamint az IP-alapú mobilhálózatok – mint például az UMTS – részeként. A küldőt az egyszerűség kedvéért mozdulatlan csomópontnak mutattuk, de a kialakítás lehetővé teszi, hogy mindkét csomópont mozgó hoszt legyen. Ennek egy változata az, amikor a hoszt egy mobilhálózat része, például amikor egy számítógép egy repülőn van. Az alapséma kiterjesztései támogatják a mobilhálózatokat anélkül, hogy a hosztoknak bármit tenniük kellene [Devarapalli és mások, 2005].
Néhány séma idegen ügynököt (foreign agent) vagy távoli ügynököt használ az otthoni ügynökhöz hasonlóan, de idegen helyen, vagy a VLR-hez (Visitor Location Register – látogató-elhelyezkedési regiszter) hasonló mobilhálózatokban. Az újabb sémákban azonban az idegen ügynökre nincs szükség. A mozgó hosztok saját idegen ügynökükként is működnek. A mozgó hoszt ideiglenes helyének ismerete mindkét esetben kis számú hosztra korlátozódik (például a mozgó ügynök, otthoni ügynök és a küldők), így nagy hálózatokban nem minden útválasztónak kell újból kiszámítania az útvonalakat. A mobil útválasztással kapcsolatos további információt Perkins [1998, 2002], valamint Snoeren és Balakrishnan [2000] munkája tartalmaz.
A hálózattervezők által tipikusan használt világmodellt az 5.18. ábra mutatja. Van egy WAN-unk, amely útválasztókból és hosztokból áll. A WAN-hoz LAN-ok, MAN-ok és olyan vezeték nélküli cellák kapcsolódnak, amelyeket a 2. fejezetben tanulmányoztunk.
Azt már láttuk, hogyan történik az útválasztás, ha a hosztok mozognak, de az útválasztók helyhez kötöttek. Ennél is szélsőségesebb eset az, ha az útválasztók maguk is mozognak. Néhány a lehetőségek közül: válságstáb egy földrengés sújtotta területen, katonai járművek egy harctéren, hajóflotta a tengeren, hordozható számítógéppel rendelkező felhasználók csoportja egy olyan helyen, ahol nincs 802.11.
Az ilyen esetekben minden csomópont egy útválasztóból és egy hosztból áll, általában ugyanazon a számítógépen belül. Az olyan csomópontokból álló hálózatot, amelyben a csomópontok véletlenül éppen egymás közelében tartózkodnak, ad hoc hálózatnak vagy MANET-nek (Mobile Ad hoc NETworks) hívjuk. Tekintsük át röviden most ezeket! További információért lásd Perkins [2001] munkáját.
Az ad hoc hálózatokat az különbözteti meg a vezetékes hálózatoktól, hogy ezeknél a rögzített topológiákra, rögzített és ismert szomszédokra, valamint az IP-címek és fizikai elhelyezkedés közötti rögzített adatkapcsolatra vonatkozó jól bevált szabályainkat egyszeriben kidobhatjuk az ablakon. Az útválasztók itt jöhetnek-mehetnek, és egyik pillanatról a másikra új helyeken bukkanhatnak fel. Ha az útválasztónak egy vezetékes hálózatban van érvényes útvonala valamely címzett irányába, az az útvonal a végtelenségig érvényes marad (eltekintve egy esetleges rendszerhibától). Ad hoc hálózatban a topológia állandóan változásban lehet, így az egyes utak kívánatossága, sőt érvényessége is spontán, minden előzetes figyelmeztetés nélkül megváltozhat. Mondani sem kell, hogy e körülmények miatt az ad hoc hálózatok útválasztása teljesen eltér a fix, telepített hálózatokétól.
Számos javaslat született már az ad hoc hálózatok útválasztó algoritmusaira. Bár az ad hoc hálózatok használata kevésbé gyakori, mint a mobilhálózatoké, tisztázatlan, hogy ezek közül a protokollok közül melyik a leghasznosabb. Az egyik legnépszerűbb útválasztó algoritmus az AODV-(Ad hoc On-demand Distance Vector – ad hoc igény szerinti távolságvektor) algoritmus [Perkins és Royer, 1999]. Ez a távolságvektor-alapú algoritmus távoli rokona, amit hozzáigazítottak a mobilkörnyezet sajátosságaihoz: a csomópontok sávszélessége jellemzően korlátozott és szűkös az akkumulátor-kapacitás. Tekintsük át, hogy ez hogyan térképezi fel és tartja karban az útvonalakat.
Ad hoc igény szerinti távolságvektor (AODV) esetén a címzett felé vezető útvonalak igény szerint kerülnek feltérképezésre, azaz csak akkor, ha valaki csomagot kíván küldeni a címzett felé. Így több munka takarítható meg, mint amennyit az útvonal használata előtti topológia módosítása vonna maga után. Az ad hoc hálózat topológiája bármelyik pillanatban leírható a csatlakoztatott csomópontok gráfjával. Két csomópont akkor van összekötve (azaz él köti össze őket a gráfban), ha rádiós úton közvetlenül kommunikálni tudnak egymással. Alapszintű, de a célnak megfelelő modell, hogy minden csomópont kommunikálni tud az összes többi csomóponttal, amely a hatótávolságon (lefedettségi körön) belül van. A valós hálózatok ennél összetettebbek. Megtalálhatók benne épületek, hegyek és egyéb, a kommunikációt blokkoló akadályok, és előfordulhat, hogy A tud kommunikálni B-vel, de B nem tud A-val, mivel a két készülék közül az egyik nagyobb teljesítményű adóval rendelkezhet, mint a másik. Az egyszerűség kedvéért azonban tegyük fel, hogy minden kapcsolat szimmetrikus.
Az algoritmus ismertetéséhez tekintsük meg az 5.20. ábrán látható, újonnan kialakított ad hoc hálózatot, ahol az A csomópont egy folyamata csomagot szeretne küldeni az I csomópontba. Az AODV-algoritmus minden csomópontban karbantart egy távolságvektor-alapú táblázatot minden csomóponthoz, címzettekre vonatkozó kulccsal, például arról, hogy melyik csomópontnak kell küldeni a csomagokat az adott címzett eléréséhez. Először az A végignézi a táblázatát, de nem talál benne I-re vonatkozó bejegyzést. Ekkor magának kell felfedeznie az I-be vezető útvonalat. Az utakat tehát csak akkor térképezik fel, amikor szükség van rájuk – ezen tulajdonsága miatt mondjuk az algoritmust „igény szerinti”-nek (on demand).
5.20. ábra - (a) A adáskörzete. (b) Miután B és D megkapták A üzenetét. (c) Miután C, F és G is megkapta A üzenetét. (d) Miután E, H és I is megkapta A üzenetét. A sötétített csomópontok az új vevők. A szaggatott nyilak a lehetséges visszairányú útvonalakat, a folytonos nyilak a feltárt útvonalakat jelzik
Annak érdekében, hogy A megtalálja I-t, egy speciális route request (útvonalkérelem) csomagot állít össze és ezt elárasztással (lásd 5.2.3. szakasz) minden hatósugarában lévő állomásnak elkezdi sugározni. A csomag A-ból eléri B-t és D-t, ahogy azt az 5.20.(a) ábra mutatja. Minden csomópont továbbsugározza a kérést, és eléri az F-et, G-t és C-t (5.20.(c) ábra), illetve a H-t, E-t és I-t (5.20.(d) ábra). A forráson beállított sorszámot használják arra, hogy megakadályozza a csomagok kettőződését az elárasztás során. Például a D eldobja a B felől jövő csomagot az 5.20.(c) ábrán, mivel az már továbbította a kérést.
Végül a kérés eléri az I csomópontot, amely route reply (útvonalválasz) csomagot állít össze. Ezt a csomagot közvetlenül a címzetthez küldik a kérés által bejárt útvonalon visszafelé. Ahhoz, hogy ez működjön, minden köztes csomópontnak meg kell jegyeznie a csomópontot, amelyiktől a kérést kapta. Az 5.20.(b)–(d) ábrán lévő nyilak mutatják a tárolt fordított útvonal-információt. A válasz továbbítása során minden köztes csomópont növeli az ugrásszámlálót. Ez megmondja a csomópontoknak, hogy milyen messze vannak a címzettől. A válaszok megmondják az összes köztes csomópontnak, hogy melyik szomszédot használják a címzett eléréséhez: ez az a csomópont, amelyiktől a választ kapták. A köztes G és D csomópont a válasz feldolgozása közben beteszi a legjobb útvonalat az útválasztó táblázatba. Amikor a válasz eléri az A csomópontot, új ADGI útvonal áll elő.
Nagyméretű hálózatban az algoritmus sok csomagot generál, még közeli célok esetén is. A többletterhelés csökkentése érdekében az adatszórás hatóköre korlátozott az IP-csomag Élettartam mezője alapján. Ezt a mezőt a küldő inicializálja, ennek az értéke minden ugrásnál csökken. Ha eléri a nullát, a csomagot eldobják, ahelyett hogy továbbadnák. Az útfelfedezési folyamat ezután a következőképp változik. A címzett keresésekor a feladó a route request csomag Élettartamát 1-re állítja. Ha belátható időn belül nem érkezik válasz, egy újabb kérelem kerül elküldésre, 2-es Élettartam értékkel. Az ezt követő kísérletekben pedig 3, 4, 5 stb. kerül az Élettartam mezőbe. A feladó így először lokálisan, később pedig egyre nagyobb sugarú körökben kísérelheti meg a keresést.
Mivel a csomópontok mozoghatnak, illetve ki is kapcsolhatják őket, a topológia váratlanul megváltozhat. Az 5.20. ábrán lévő példánkban, ha G-t kikapcsolják, A nem fogja észrevenni, hogy az I-hez eddig használt útvonala (ADGI) már nem érvényes. Az algoritmusnak ezzel is meg kell birkóznia. Ennek érdekében minden csomópont periodikusan szétküld egy Hello üzenetet. Erre minden szomszédnak válaszolnia kell. Ha valahonnan nem jött üzenet, a feladó tudja, hogy az adott szomszédja elhagyta az adáskörzetét és már nincs vele kapcsolatban. Hasonlóképpen, abból, hogy megpróbál elküldeni egy csomagot egy szomszédnak, és az nem válaszol, megtudhatja, hogy a szomszédja többé nem elérhető.
Ezzel az információval megszabadulhatunk azoktól az utaktól, amelyek már nem működnek. Minden csomópont (ezek közül az egyik legyen N) minden lehetséges címzetthez nyilvántartja azokat az aktív szomszédjait, amelyek az elmúlt 
másodperc során csomagot továbbítottak neki az adott címzetthez. Ha bármely szomszédja elérhetetlenné válik, N megvizsgálja az útválasztó táblázatában, hogy mely címzettekhez vezet út az imént távozott szomszédon keresztül. Minden ilyen útvonal esetében közölni kell az aktív szomszédokkal, hogy az N-en át vezető útvonaluk immár érvénytelen és törölni kell az útválasztó táblázatból. Példánkban a D törli a G-hez és I-hez tartozó bejegyzéseket az útválasztó táblázatból, és értesíti A-t, amely törli az I-hez tartozó bejegyzést. Általános esetben az aktív szomszédok értesítik a saját aktív szomszédjaikat, és így tovább, míg rekurzív módon az összes, az imént távozott csomóponttól függő útvonal ki nem kerül az összes útválasztó táblázatból.
Ezen a ponton az érvénytelen útvonalak törlésre kerültek a hálózatról, és a leírt felfedezési módszerrel a feladók megkereshetik az új, érvényes útvonalakat. Idézzük fel, hogy a távolságvektor-alapú protokolloknál a topológia változása után fellép a végtelenségig számolás problémája és lassú a konvergencia is, amelyben összekeverednek a régi, érvénytelen útvonalak az új, érvényes útvonalakkal.
A gyors konvergencia biztosítása érdekében az útvonalak tartalmaznak egy sorszámot, amelyet a címzett szabályoz. A címzett sorszám egy logikai órához hasonlatos. A címzett ezt növeli minden egyes friss route reply üzenet küldésekor. A feladók úgy kérnek friss útvonalat, hogy az utolsó használt útvonal sorszámát berakják a címzett route request üzenetbe, amely az éppen törölt útvonal sorszáma lesz, vagy kezdeti értékként 0. A kérés addig kerül továbbításra, amíg magasabb sorszámú útvonalat nem talál. A köztes csomópontok eltárolják a magasabb sorszámú útvonalakat, vagy a legkevesebb ugrást az aktuális sorszámhoz.
Az igény szerinti protokollok szellemében a köztes csomópontok csak a használatban lévő útvonalakat tartalmazzák. Az adattovábbítások során megszerzett útvonal-információ rövid késleltetés után lejár. Azáltal, hogy csak a használt útvonalak kerülnek felfedezésre és tárolásra, sávszélesség takarítható meg és növelhető az akkumulátor-élettartam a normál távolságvektor-alapú protokollhoz képest, amely rendszeres időközönként továbbítja a frissítéseket.
Eddig csak egyetlen útvonalat tételeztünk fel az A és I között. További erőforrások megtakarítása érdekében az útvonal felfedezése és karbantartása megoszlik, ha az útvonalak átfedik egymást. Ha például a B is csomagokat kíván küldeni az I-nek, akkor útvonal-felfedezést hajt végre. Ebben az esetben azonban a kérés először eléri a D-t, amely már rendelkezik útvonallal az I felé. A D csomópont ezután elő tud állítani egy választ, hogy megmondja B-nek az útvonalat anélkül, hogy további munkára lenne szükség.
Számos más ad hoc útválasztási séma létezik. Egy másik, jól ismert igény szerinti séma a DSR (Dynamic Source Routing – dinamikus forrás útválasztás) [Johnson és mások, 2001]. Más típusú, földrajzi alapú stratégia a GPRS (Greedy Perimeter Stateless Routing – önző határfelületi állapot nélküli útválasztás) [Karp és Kung, 2000]. Ha minden csomópont tudja a földrajzi helyét, akkor a címzett felé történő továbbítás folytatható útvonal-kiszámítás nélkül azáltal, hogy a megfelelő irányban kerül továbbításra és vissza, a zsákutcák elkerülése érdekében. Az, hogy melyik protokoll nyer, az ad hoc hálózatok típusától függ, ami a gyakorlatban nagyon hasznos.