A routing az a folyamat, ami során egy hálózati protokoll (3. réteg) egy csomagja a kapcsológépek (router-ek) sorozatán keresztül a feladótól eljut a címzettig. Ehhez szükséges, hogy a router-ek kommunikáljanak egymással, hogy eldönthessék, hogy egy adott végcél felé melyik irányba kell továbbítani a csomagot. A hálózati protokollt hívjuk route-olt protokollnak (IP, IPX, AppleTalk, stb.), a router-ek egymás közötti kommunikációját bonyolító protokollt pedig routing protokollnak. A routing protokoll a kommunikáció módjainak lerögzítése mellett meghatározza az útvonalkiválasztás mikéntjét is. Maga az útvonalkiválasztás a routing problémakörének legérdekesebb kérdése.
Bár a kapcsolatorientált hálózati protokollok (például X.25 vagy az ATM P-NNI) is tartalmaznak routing elemeket, hiszen a kapcsolat felépítésekor ki kell jelölni az útvonalat, mégis a fogalom elsôsorban a csomagkapcsolt hálózatokra vonatkozik. Egyébként a hívásfelépítéskor történô útvonalkiválasztás során ugyanazokkal a megoldandó feladatokkal nézünk szembe, mint egy csomagkapcsolt hálózatban, fejtegetésünket ezért elsôsorban a csomagkapcsolt hálózatok (ezen belül is az Internet) szem elôtt tatásával folytatjuk.
Egy ilyen csomagkapcsolt hálózatot router-ekkel összekapcsolt link-ek halmazának tekintünk, ahol a link-en belüli kommunikáció kizárólag a link-en keresztül, a hálózati protokollt nem érintô módon, linkspecifikusan zajlik. A link-ek közötti kommunikáció viszont a router-ek segítségével a 3. rétegben történik. A route-olás szempontjából egy több szegmensbôl álló Ethernet hálózat egyetlen link, hiszen benne teljes az Ethernet konnektivitás és a router-eknek nem is kell tudniuk arról, hogy mindez hogyan valósul meg.
A router minden link-jéhez egy interface-en keresztül kapcsolódik. A csomagok kapcsolása mindig egy táblázat alapján történik, mely <cél, kimenô interface> párokból áll. A beérkezett csomagot ennek a táblázatnak a segítségével, a cél alapján többnyire egy gyors, berendezésorientált áramkör kapcsolja a kimenetre. A routing protokollok feladata, hogy ezt a táblázatot elôállítsák. A protokollokat általában a router egy a csomagkapcsolástól elkülönített részében egy általános célú processzor futtatja. Innentôl kezdve magával a csomagkapcsolással nem, csak a táblázat elôállításával foglalkozunk.
A hálózat topológiája egy gráf, melyben a pontok router-ek és link-ek (amelyek a rájuk kapcsolt állomásokat összefoglalóan jelentik), az élek pedig azt fejezik ki, hogy a router kapcsolódik az adott link-re. Ebben a gráfban kell a csomag útját meghatározni. Ha több út is lehetséges, akkor a több út közül a valamilyen szempontból legjobbat kell kiválasztani. A kiválasztás szempontjai lehetnek:
A fenti szempontok valamilyen kombinációjaként adódik az útvonal.
Az is lehetséges és sokszor szükséges, hogy a több útvonal között megosszuk a forgalmat, tehát nem egyiket vagy másikat részesítjük elônyben, hanem mindkettôt használjuk valamilyen mértékben (load balancing).
Egy olyan berendezés, amelyik a fenti szempontok mindegyikét, különösen az utolsókat képes szem elôtt tartani és ezek alapján utat választani, meglehetôsen bonyolult és igen sok konfigurációt igényel, ami mind a beruházási, mind az üzemeltetési költségeit növeli.
A nagy csomagkapcsolt hálózatokban (az Internetben) igen sok célpont felé kell utat ismerni. Ez meglehetôsen nagyméretû táblázatokat eredményez, ami megdrágítja a router-eket. Célszerû az egy csoportban lévô hálózatokat összefogni és egy egységként kezelni, így az ilyen csoporton belüli route-olást egyszerûbb berendezésekkel is megoldhatjuk. Ez nagy nyereség, hisz a forgalom nagy része általában lokális. Olyan területen ráadásul, melynek adminisztrációja egységes, nincs is szükség a politikai szempontok figyelembevételére, így a belsô router-ek még egyszerûbbek lehetnek.
Éppen ezért a jelenlegi Internet autonóm rendszerekbôl (Autonomous System, AS) áll. Egy autonóm rendszer több hálózatot is magában foglalhat, de a belsô adminisztrációja egységes és belsô route-olási kérdésekben kifelé koherens képet mutat. Ezen felül összefüggônek kell lennie. Az AS-en belüli routing protokollokat az Interior Gateway Protocol (IGP), míg az AS-ek között route-olást végzôeket az Exterior Gateway Protocol (EGP) gyûjtônévvel illeti az Internet közösség. Maga az EGP elnevezés -elég szerencsétlenül- egy konkrét protokollt is jelöl. A gateway kifejezés onnan származik, hogy a router-eket az eredeti Internet terminológiában gateway-nek nevezték.
Az EGP protokollok erôsen koncentrálnak a politikai kérdésekre és tág teret hagynak az adminisztrátoroknak az útvonalkiválasztás mikéntjének befolyásolásában, míg az IGP protokollok inkább az automatikus útvonalválasztásra összpontosítanak és a manuális konfiguráció minimalizálására törekszenek, hogy birtoklásuk olcsóbb legyen.
A routing protokollok algoritmusai számos kategóriába oszthatóak:
A routing feladata igen közel áll a bridge-k feladatához. A beérkezô csomagról/keretrôl intelligensen el kell dönteni, hogy merre továbbítsuk, ehhez táblázatokat és a kapcsolás elvégzésére külön berendezéseket használunk. A source-routed bridging nagyjából a source routing-hez, a transzparens bridging pedig a hop-by-hop routing-hez hasonlít, ily módon is erôsítve a hasonlóságot. Vajon mi akkor a lényeges különbség? Az a tény, hogy a bridge-k a 2. rétegben, a router-ek pedig a 3. rétegben mûködnek, meglehetôsen teoretikus érv csupán.
A két módszer között az alapvetô különbség a bridging protokollok hiánya. Transzparens bridging esetén a bridge-k közötti kommunikáció csupán a hurkok elkerülésére szorítkozik, de azt, hogy melyik célpont merre található, a hálózat figyelésével derítik ki a bridge-k, nem pedig egymástól tudják meg, mint a router-ek. Ehhez természetesen az ismeretlen címzettû csomagokkal el kell árasztani a hálózatot, ami tetemes forgalmat okoz. A router-ek esetében ilyen árasztás nincs, vagy a default router kezeli a problémát, vagy a csomagot eldobjuk, mondván, hogy a címzett nem létezik, különben benne lenne a táblázatunkban. A source route bridging esetén pedig a felderítô keretek árasztásával rakunk nagy terhet a hálózatra és a végberendezésektôl is többet követelünk.
A bridging ráadásul lapos, azaz, minden bridge mindenkirôl, minden egyes állomásról tud, hiszen a MAC címtér is struktúrálatlan. Ez korlátozza a bridge-kbôl fölépíthetô hálózat méretét a bridge-k korlátos memóriája miatt. A router-ek viszont többnyire egy struktúrált hálózati címmel dolgoznak és elég minden hálózat fele utat ismerni, a hálózaton belüli postázás már lokális probléma. Ha pedig úgy döntünk, hogy nem minden hálózat, hanem példának okáért csak a mi AS-ünk hálózatairól kell tudnia minden router-nek, a külsô hálózatokról pedig csak egynek, akkor azt az egyet default router-nek kinevezve minden célpont felé képesek vagyunk továbbítani a csomagokat.
A bridging elônye viszont, hogy olcsó, egyszerû, gyors és szinte nem kell konfigurálni. A bridging protokollok hiánya egyszerûbb berendezést és kevés adminisztrációt igényel. Egy bridge vagy swicth szinte a bekapcsolás és a hálózatra való csatlakoztatás után azonnal mûködõképes és kezdi tanulni a címeket. Egy router esetén viszont egy sereg dolgot be kell állítani.
Egy brigde-kbôl felépített hálózat számára mindegy, hogy milyen hálózati protokollt használunk, akár egyszerre többet is. Így sokkal több alkalmazást használhatunk, hiszen egész más alkalmazások futnak IPX, IP vagy DECNet fölött. Router-ek alkalmazása esetén a router-nek minden hálózati protokollt ismernie kell és képesnek kell lennie ezek routing protokolljait is futtatni.
Az alábbiakban néhány, elsôsorban az Internetben, az IP route-olására használt IGP protokollt tekintünk át. Ezek a protokollok elsôsorban egy AS-en belül mûködnek, de nem kell azt képzelnünk, hogy egy AS-en belül csak egy protokoll szerint kommunikáló router-ek lehetségesek. Viszont ha csak egyetlen protokollt használunk, megspóroljuk a különbözô protokollok együttmûködésének megoldását.
A distance-vector protokollokat gyakran emlegetik úgy, mint „Bellman-Ford" protokollok, mert alapjukat az R. E. Bellman által kidolgozott legrövidebb út kiszámítását végzô [3], valamit a Ford és Fulkerson által elôször leírt elosztott algoritmus [4] képezi. Mûködésük a következô.
A szomszédos router-ek periodikusan küldenek egymásnak frissítô üzeneteket, melyekben leírják, hogy melyik célponthoz mekkora költségû utat ismernek. Ezekben az üzenetekben minden általuk ismert célpontot felsorolnak és az üzenetet minden link-re elküldik, amelyhez kapcsolódnak. Az üzenet hallgatói hozzáadják az útvonalak költségeihez a közbeesô link költségét, majd megvizsgálják, hogy a hirdetett célpontokhoz ôk olcsóbb utat ismernek-e. Ha nem, vagyis olcsóbb a hallott utat használni, mint az eddig ismertet, akkor módosítják táblázataikat és ettôl kezdve a hirdetô router felé továbbítják a megadott célba igyekvô csomagokat. Ha viszont az eddig ismert út jobb, figyelmen kívül hagyják az imént hallottat.
A router-ek egészen addig fokozatosan csökkentgetik útvonalaik költségét, amíg hallanak olcsóbb utat. Ez a folyamat addig tart, amíg a létezô legolcsóbb utak ki nem alakulnak a hálózatban, nincs közbeesô állapotban való megrekedés. Ha a hálózat topológiája nem változik, a kialakult táblázatok optimális utakat kínálnak. A hálózat topológiája azonban gyakran változik (meghibásodás miatt kiesnek vonalak vagy router-ek), ami miatt elôfordulhat, hogy egy célpontba az eddigieknél csak drágábban lehet eljutni, mert az olcsóbb úton hiba történt.
Ha attól a router-tôl, mely felé eddig a csomagjainkat küldtük, nagyobb költségû hirdetményt hallunk, mint ami a mi táblázatunkban szerepel, az azt jelenti, hogy az általunk is használt út valamilyen okból drágább lett, ekkor a mi táblázatunkban is növeljük az út költségét és ezt mi is terjeszteni kezdjük. A drágább utat tehát csak attól vagyunk hajlandóak elfogadni, aki felé csomagjainkat továbbítjuk. Gyakran ez a drágább út végtelen költségû, ami azt jelzi, hogy ebben az irányban az adott célpont már elérhetetlen. Ha valamilyen másik irányba viszont elérhetô, akkor egy onnan érkezô olcsóbb utat tartalmazó hirdetmény hatására majd csökkentjük a végtelen költségû bejegyzésünket és a továbbítás irányát a hirdetôre állítjuk.
A módszer igazán egyszerû és tetszetôs. Azonban nem tökéletes.
Számos probléma adódhat abból, hogy a router-ek topológiaváltozás esetén nem egyidôben változtatják táblázataikat, hanem a kommunikációval eltöltött idô miatt késleltetve. Ezen problémák egyike a végtelenig számolás (counting to infinity). Ha egy célpont (a fenti ábrán X) elérhetôsége megszûnik, az A router ezt úgy jelzi, hogy táblázatában végtelenre költségûre állítja az X célponthoz tartozó bejegyzést, ami eddig például 5 lehetett. Ám mielôtt ezt B router-rel közölhetné kaphat B-tôl egy olyan üzenetet, hogy az ismer egy 6 költségû utat. (A-n keresztül, de ez nincs benne a hirdetményben). Erre A átírja bejegyzését, hogy az X hálózat B fele található, az út költsége 7, és ezt terjeszteni is fogja. B, mikor meghallja, hogy A már 7 költségû utat ismer, átírja a saját bejegyzését 8-ra, a drágítás indokolt, hiszen ô A felé továbbítja a csomagjait. Ennek hatásaként A 9-re módosít, B 10-re, A 11-re és így tovább. A végeredmény az lesz, hogy mindkét router a végtelenségig emeli a költséget. Ennek a folyamatnak a lerövidítése érdekében a végtelen értékét célszerû kicsire választani.
A számlálás akkor is megindulhat, ha az X hálózat felé az út költsége nem végtelenre, hanem például 5-rôl 12-re nô. Ekkor a számolás 12-ig zajlik, hiszen mikor odáig elérnek, A nem számol tovább, hisz X felôl hallani fog egy 12 költségû utat. A számolás ideje alatt azonban hurok keletkezik, a csomagokat A és B egymásnak küldözgeti, amíg azok élettartama le nem jár. Ez hatalmas torlódást okoz és számos csomag célba sem ér.
Az egymásraállítódás és a végtelenig számolás ellen a split horizon módszerrel védekezhetünk. Ez azt jelenti, hogy ha egy router megismer egy utat, amit A-tól hallott, akkor azt az utat A-val már nem közli. Így a fenti példában B sohasem fogja A-val közölni, hogy ismer utat X-be és így A terjesztheti a végtelen költségû útját, amibôl B kitalálhatja, hogy X már nem elérhetô. Kicsit tovább javít a helyzeten, ha B nemcsak hogy nem terjeszti A-nak a tôle megtudott útvonalat, de minden az ugyanazon a link-en levô router-nek (jelen esetben D-nek) végtelen költségû utat terjeszt, nem pedig a sajátját(split horizon with poisoned reverse). Így ezek a router-ek (azaz D) nem B-re, hanem A-ra fognak figyelni, arra, akin keresztül az út valójában vezet és nem történik meg az, hogy D, mivel B hirdetményét (6 költségû) elôbb hallotta, mint A-ét (5 költségû) egy kis ideig B-nek küldi csomagjait, hogy az aztán A-nak továbbítsa. Ez a módszer található a RIP-ben.
Ezzel azonban csak 2 router között akadályozzuk meg a végtelenig számolást, egy körben nem. A fenti ábrán C a B-n keresztül küldi a csomagokat X-be, mert az az út olcsóbb, mint a közvetlen A-ba vivô. Az elôbbi esetet tekintve, ha A 5 költségû útja megváltozik végtelenre, akkor még mielôtt a B ezt megtudná és közölhetné a C-vel, C küldhet egy üzenetet A-ba, hogy ismer egy 7 költségû utat X-be. Erre A átírja táblázatában 10-re az X-hez tartozó bejegyzést és C fele irányítja csomagjait. Mikor B errôl A-tól tudomást szerez, ô továbbra is A fele küldi csomagjait, de útjának költségét 11-re állítja. Ezt C-nek hirdetve C költsége 12-re módosul és a kör bezárult, a számolás nem két router között, hanem körben, de megindult a végtelen felé és igazából X-be senki nem képes eljuttatni csomagokat. A hurokba került csomagok pedig ismét torlódást okoznak. A torlódásban pedig a routing protokollok üzeneteit is nehezebb átadni, ami a számolást lassítja.
A problémán tovább úgy segíthetünk, ha minden router-tôl megköveteljük, hogy egy út megváltozása esetén azonnal terjessze a megváltozott utat és ne várja meg a következô frissítô üzenetet (triggered update). Így, ha egy célpont elérhetetlenné válik, minden odavezetô út mentén, a hibától távolodva sugarasan szétterjed az elérhetetlenséget jelzô információ és elméletileg nem alakulhatnak ki ilyen hurkok. (Azaz ha X elérhetetlenné válik, A ezt azonnal közli B-vel, aki azonnal közli C-vel.) A végtelen költségû utat ugyanis csak azok a router-ek kötelesek saját táblázatukba beírni, akik valóban használják is az adott utat (csak a továbbítás irányából érkezô nagyobb költséget kénytelen felhasználni egy router, ha máshonnan hall egy nagyobb költségû útról, azt figyelmen kívül hagyhatja). Így az X-be tartó csomagok haladási útvonalain visszafelé, hurokmentesen szétterjed az elérhetetlenségrôl szóló információ (példánkban az A, B, C sorrendben). A valóságban azonban rendszeresen küldött frissítô üzenetek becsúszhatnak (ha C éppen akkor küldi rendszeres frissítô üzenetét, mikor a végtelen út terjedése éppen B-nél tart) és a körben való végtelenig számlálás elkerülhetetlen. Azonban az azonnali terjesztés miatt maga a számlálás is meglehetôsen hamar lezajlik.
5.3.1.2. Routing Information Protocol (RIP)
5.3.1.5. Interior Gateway Routing Protocol (IGRP) és (EIGRP)
5.3.1.7. Open Shortest Path First (OSPF)
5.3.2.1. Exterior Gateway Protocol (EGP)
5.3.2.2. Classless Inter-Domain Routing (CIDR)
5.3.2.3. Border Gateway Protocol (BGP)