Mint már tudjuk, a hálózati réteg feladata, hogy a csomagokat eljuttassa a célhosztig. Ez egyszerű, vagy üzenetszórásos topológiával rendelkező hálózatok esetén nem túl bonyolult feladat, vagy nincs is rá szükség. Egészen más a helyzet akkor, ha a két hoszt között több lehetséges útvonal is kialakítható. Értelemszerűen meg kell találni ilyen esetekben az optimális útvonalat. Ennek a feladatnak a végrehajtása is a hálózati rétegre tartózik. A gyakorlatban többféle módszer alakult ki, a továbbiakban ezekből tekintünk át néhányat.

A csomagok továbbítása az alhálózatban elhelyezkedő IMP-ek között zajlik. Minden IMP-nek el kell döntenie, hogy a bemenetén érkező üzenetet, vagy csomagot melyik kimeneten küldi tovább. Ezt a folyamatot nevezzük forgalomirányításnak (routing). Abban az esetben, ha datagram típusú hálózattal dolgozunk, akkor az üzenet minden egyes csomagjával meg kell a forgalomirányítás algoritmusát ismételni, mivel a vonalak terheltsége az alhálózaton belül minden időpillanatban változhat. A virtuális áramkörök használatakor ez a feladat egy kissé leegyszerűsödik, mivel új forgalomirányítási döntést csak abban az esetben kell hozni, ha a virtuális áramkörök változnak, vagyis újak jönnek létre, illetve a régiek bontásra kerülnek.

Amikor a forgalomirányítás algoritmusát kell meghatározni, az alábbi szempontokat kell figyelembe venni:

  • Az algoritmus legyen egyszerű, ami elősegíti a megoldás nagyobb sebességét is. Minél bonyolultabb egy megoldás, valószínűleg annál nagyobb lesz az erőforrásigénye.
  • Fontos, hogy a megoldás robosztus legyen, mivel a hibákra való érzékenység a hálózatok működését alapvetően meghatározza.
  • Ugyanilyen fontos a stabilitás is, ami szintén az egész alhálózatra kihatással van.
  • A forgalomirányító algoritmust úgy kell felépíteni, hogy csak annyira legyen bonyolult, amennyire okvetlenül szükséges az adott feladat ellátása érdekében.
  • Rugalmasság követelményét is megfogalmazhatjuk, ugyanis a hálózat tervezésekor sok évre kell gondolni. Közben a hálózatban hibák fordulnak elő, amelyek lehetnek akár hardveres-, akár szoftveres hibák is. A javítás során megváltozik a hardverkiépítés, adott esetben a hálózati topológia is. Ha minden ilyen esetben újra kellene terveznünk a hálózatot, akkor az a elveszítené a működésképességét.
A forgalomirányító algoritmusok két nagy csoportba sorolhatók a működési elvük szerint: Adaptív algoritmusok (Adaptive algorithms) figyelembe veszik a működésük során bekövetkező változásokat. Ennek megfelelően alkalmazkodnak a mindenkori forgalmi és terheltségi viszonyokhoz. A megoldás előnye, hogy rugalmas, viszont nagy az erőforrásigénye, mint ahogy majd a későbbiekben láthatjuk. A megoldást nevezik dinamikus forgalomirányításnak is.

Nem adaptív algoritmusok (Non-adaptive algorithms) egyszerű eljárásokat alkalmaznak, az aktuális forgalmi viszonyokat működés közben nem veszik figyelembe. A hálózat felépítésekor az IMP-ekben egy off-line módon kiszámított forgalmi helyzet kerül letöltésre. Az egyszerűség előnye mellett természetesen a rugalmatlanságából adódó hátrányt is meg kell említeni. Másik elterjedt elnevezése a statikus vagy determinisztikus forgalomirányítás.

Mielőtt megnéznénk, hogy milyen algoritmusok alakultak ki az évek folyamán, amelyeket a gyakorlatban is használnak, fontos néhány fogalomnak a tisztázása. A hálózat működésénél az optimális felépítésre kell törekednünk. De mit is jelent az,hogy optimális? Milyen paraméternek kell optimálisnak lennie? Hogyan lehet a hálózatokat ezek figyelembevételével felépíteni? Hogyan lehet modellezni az ilyen rendszerek működését? Mennyi kérdés merülhet fel egy ilyen egyszerű szóval kapcsolatban, ezért egy kicsit részletesebben is nézzük meg ennek a jelentését.

Most még célszerű, ha az optimalitást a hálózat felépítésétől függetlenül, mivel a konkrét megvalósításokat majd a későbbiekben tekintjük át. Az optimalitási elv (optimality principle) azt jelenti, hogy hogy ha az A és C IMP közötti optimális útvonalon helyezkedik el a B jelzésű IMP, akkor az A-B és a B-C útvonal szinté erre az útra esik. Ennek az állításnak a bebizonyítása nem bonyolult. Tegyük fel, hogy találunk egy útvonalat B és C között, amely jobb, mint az A-B-C útvonal. Ez az eset nem fordulhat elő, mivel akkor az A-B-C útvonal már nem lenne optimális.

Könnyel belátható, hogy az IMP-ek között egy célhoz tartozó optimális útvonalak felrajzolva fa-szerkezetet fognak alkotni, ahol a csúcspontok az IMP-ek, míg az ágak a vonalak. Ennek a fának a gyökere a cél IMP vagy hoszt. Ez ilyen elven felépített fákat nyelőfáknak (silk tree) nevezik.

59. ábra. Egy alhálózat és egy nyelőfa felépítése

Ha szemügyre vesszük az ábrát, felmerülhet a kérdés, hogy csak ez az egyetlen optimális útvonal van az A IMP és a többi kapcsolópont között? Természetesen a válasz: NEM. Több ilyen útvonal is kialakítható, a konkrét forgalomirányító algoritmusoknak pont az a feladata, hogy ezeket felderítsék.

Ez nem tartalmazhat hurkot,aminek az következménye, hogy minden üzenet vagy csomag véges számú kapcsolóelem érintésével célba juttatható elméletileg. Azért csak elméletileg, mivel az útvonalban résztvevő IMP-ek meghibásodhatnak, majd újak jöhetnek létre. Az sem elhanyagolható szempont, hogy az egyes IMP-ek milyenmódon juthatnak hozzá azokhoz az információkhoz, amelyek alapján kiszámíthatják a saját nyelőfájukat, mert ugye minden egyes csomópontnak saját nyelőfája van az útvonalak kialakításához.

Most már elkezdhetjük a forgalomirányítási módszereket áttanulmányozni. Először nézzük végig a determinisztikus algoritmusokat, majd folytatjuk az adaptív eljárások ismertetésével.

Legrövidebb út módszere

Az egyik legalapvetőbb forgalomirányítási modell a legrövidebb út módszere. Ezt több eljárásban felhasználják, az egyszerűsége és a hatékonysága miatt. Sajnos a működés megértéséhez egy kissé a matematika vizeire kell eveznünk, mivel az a módszer teljes egészében matematikai úton levezethető.

Az alhálózatot alkotó IMP-eket és vonalakat egy gráfnak képzeljük el. Rögtön bele is ütköztünk az első fogalomba, amit nem ismerünk. Az IMP-ek egy halmaz elemei, amelyek a gráf csúcspontjait jelölik. A csúcspontok között elhelyezkedő vonalak lesznek a gráf élei. Az éleket szokás E, míg a csúcspontokat V betűvel jelölni, utána zárójelben felsoroljuk, hogy mely csúcsok között helyezkednek el, illetve hogyan jelöljük őket. Sokkal egyszerűbb lesz, ha egy példán keresztül tekintjük át az eddig elmondottakat.

Legyenek a csúcspontok

V = {A, B, C, D, E}

Az élek pedig

E = {(A, B), (B, C), (C, D), (D, E), (A, E), (C, E), (A, C)}

Vegyük fel az A, B, C, D és E pontokat, ezek lesznek a gráf csúcspontjai. Ez látható a 60. ábrán.

60. ábra. A gráf csúcspontjai

Most kezdjük összekötögetni a csúcsokat az "E"-ben meghatározott módon, tehát az A-B, az B-C, a C-D, a D-E az A-E, a C-E és az A-C csomópontok közé kell egy vonalat húznunk. Ezzel el is készítettük a gráfunkat. Ezt láthatjuk a 61. ábrán. Ha nem lenne megfelelő a csúcspontok elhelyezkedése, akkor nyugodtan át is rajzolhatjuk a könnyebb olvashatóság szempontjából, az a végeredményen nem változtat.

61. ábra. A gráf csúcspontjainak összekötése

A gráfok egy speciális fajtája az irányított gráf. Ilyen is előfordulhat elméletileg a számítógép-hálózatoknál, de nem túlzottan jellemző, ehhez szimplex vonalakra lenne szükség. Az irányított gráfoknál az éleknek megfelelő párok rendezettek, a két csúcs közötti él csak egyik irányban járható. Az előbbi példánál maradva az élek felírása némileg változik:

E = {[A, B], [B, C], [C, D], [D, E], [A, E], [C, E], [A, C]}

Az ilyen elven felépített irányított gráfot ugyanúgy rajzolhatjuk fel, azonban az éleket nyilak jelentik., mint ahogy a 62. ábrán is látható.

62. ábra. Az irányított gráf csúcspontjainak összekötése

Előfordulhat, hogy olyan éleket kell figyelembe vennünk, amelyek kezdőpontja megegyezik az előző él végpontjával. Az ilyen élek együttesét nevezzük pályának, vagy útnak. Példaként az A-ból E-be tartó út irányítatlan gráf esetében az A-E útvonal, míg irányított gráfnál az A-B-C-E útvonal. A pályának egy speciális változata a körpálya, amikor a pálya kezdő és végpontja pontosan megegyezik.

Van még két módszer, amit alkalmazhatunk a gráfok felírásához:

  • Szomszédsági listás
  • Minden egyes csúcs esetén egy listára felfűzzük a szomszédait. Ritka gráfok esetén tömör felírásmódot tesz lehetővé. A ritka gráf azt jelenti,hogy az E sokkal kisebb, mint V*V. Fontos feladat annak az eldöntése, hogy két pont között vezet-e él. Maga a megoldás nem túlzottan hatékony. Egy speciális megjelenési formája, amikor a csúcspontok és az élek nem egyforma szinten vannak, hanem fontossági sorrend (súlyozás) kerül kialakításra, azok a súlyozott gráfok, amelyeknél a listában a szomszédok mellé kell tenni a súlyt is.
    Irányítatlan gráf esetén a listák összhossza 2E, irányított esetben E.

  • Szomszédsági mátrix
  • Ez a felírás nem túlzottan egyszerű, még mélyebben kell a matematikába elmélyednünk. Írjunk fel egy mátrixot, aminek annyi sora és annyi oszlopa van, amennyi a gráfban található csúcspontok száma. A szomszédsági mátrixot A-val szokás jelölni. A mátrixnak az i, j eleme akkor 1, ha az i-dik csúcspontból él vezet a j-edik csúcsba. Ezt szemlélteti a 63. ábra.

63. ábra. Szomszédsági mátrix

Tetszőleges csúcspárról hatékonyan eldönthető, hogy eleme-e az élhalmaznak. Hatékony, ha E megközelíti V*V-t, egyébként viszont tárpazarló. Nagy méretű gráfok esetén gyakorlatilag használhatatlan. Egyszerű, nem súlyozott gráfok esetén a mátrix elemei lehetnek bitek.

Két pont közötti út meghatározása

A csomagoknak az alhálózaton belül csomópontokon kell keresztülhaladniuk. Ahhoz, hogy ezek a csomópontok a megfelelő útvonalon továbbítsák a csomagot, szükség van olyan információkra, amelyek megadják, hogy egy csomópontból el lehet-e jutni egy másikba. Ennek az eldöntése nem is olyan egyszerű feladat.

Tekintsük a G (V, E) gráfot (aminek V csúcspontjai és E élei vannak). Legyen ennek a gráfnak két pontja, az {x, y}, ahol azt kell eldöntenünk, hogy közöttük van-e járható út, vagyis el tudunk-e jutni az x-ből y-ba. Ennek az algoritmusa a következő:

  1. Ha az x és az y között van él, akkor biztosan van járható út is, tehát megtaláltuk, amit keresünk.
  2. Ha nincs, a második körben megnézzük, hogy van-e a gráfnak olyan u pontja, hogy {x, u} és {u, y} eleme E-nek. Ha van, megtaláltuk a keresett útvonalat.
  3. Ha nincs, akkor a harmadik körben megnézzük minden u,v pontpárra, hogy igaz-e, hogy {x, i}, {u, v}, {v, y} eleme E-nek. Ha van, megleltük azt az útvonalat, amelyen keresztül eljuthatunk az x-ből y-ba.
Ha nem találtunk ebből a három lépésből útvonalat, akkor a harmadik lépést ismételjük addig, amíg meg nem találjuk a kereset útvonalat, van el nem fogynak a gráf csúcspontjai. n pontú gráf esetén az algoritmus max. n-1 körből áll. Ha n-1 kör után sem találtunk utat x és y között, akkor azok különböző komponensben vannak, egyébként meg megtaláltuk a keresett útvonalat. A megoldás amilyen egyszerű, annyira nem szerencsés az alkalmazása az esetek többségében. Meglehetősen erőforrás-igényes az alábbi megoldás. Egy n csúcspontból álló gráf esetén maximálisan (n-1)! számítási műveletre van szükség, vagyis (n-1) faktoriális. Például egy 5 elemű gráf esetében 1*2*3*4*5 = 120 műveletre van szükség a legrosszabb esetben. Egy 20 kapcsolópontot tartalmazó hálózatban ez már 2,43*1018, ami már hatalmas szám, pedig ez még nem is nagy hálózat!

Ennél gyorsabb módszer a szélességi keresés. Ebben az esetben nem azt keressük, hogy x és y egy komponensben van-e, hanem megjelöljük x teljes komponensét, és megnézzük, hogy y benne van-e. Akkor vannak egy komponensben, ha az egyikből el lehet jutni a másikba.

  • Először vesszük a kiindulópont szomszédjait, és bejelöljük őket.
  • Második körben vesszük az 1. lépésben bejelölt pontokat, és bejelöljük a bejelöletlen szomszédjaikat.
  • Harmadik körben vesszük az előző lépésben bejelölt pontokat, és bejelöljük a bejelöletlen szomszédjaikat.
  • Ezt a lépést ismételjük meg, amíg végig nem érünk a teljes gráfon.
Az algoritmus lépésszáma <= Szumma d(V) = 2*E <= n2. Ez nyilvánvalóan gyorsabb algoritmus az előzőnél, mert a lépésszámát felülről becsültük n egy polinomjával. Általában gyors egy algoritmus, ha n polinomjaként becsülhető a lépésszáma. A legrövidebb utak problémája Amikor egy csomagot szeretnénk elküldeni egy másik hosztnak, akkor értelem szerűen megpróbálunk a lehető legnagyobb sebességet elérni. Ennek egyenes következménye, hogy a csomagot a lehető legrövidebb útvonalon (shortest path) kell elküldeni. De mi is a legrövidebb út? Többféle szempontot vehetünk figyelembe: meghatározhatjuk az érintet kapcsolóelemek számát, az útvonalak késleltetési idejét, vagy a tényleges távolságot. Mindhárom esetben a modellünkből indulunk ki, amelyben matematikai úton meghatározhatjuk a távolságokat, valamint a legrövidebb útvonalat.

A legrövidebb útvonal keresésének változatai az alábbiak lehetnek matematikai szempontból:

  1. Egy adott csúcsból induló utak megkeresése (nem tudunk olyan algoritmusról, amely a két pont közötti távolság kérdését aszimptotikusan gyorsabban dönti el, mint az összes csúcsra vonatkozót).
  2. Egy adott csúcsba érkező legrövidebb utak (ez egyszerűen az élek megfordításával visszavezethető az előző feladatra).
  3. Az összes csúcspár közötti legrövidebb utak problémája.
A megoldáshoz a gráfunkat ki kell egészíteni az élekre vonatkozó súlyokkal. Ezeket általános esetben a hálózatunkban 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 határozza meg. Egy csúcspontból egy másikba tartó legrövidebb útvonal kiszámítására az egyik leggyakrabban alkalmazott módszer Dijkstrától származik, aki 1969-ben vetette papírra az eljárást. A gráf minden csúcspontját felcímkézzük a forráscsomóponttól való legrövidebb út mentén mért távolságával. Az eljárás kezdetén ezek az utak még nem ismertek, ezért minden utat végtelennek feltételezünk. Ahogy az algoritmus végzi feladatát és halad előre a gráfban, úgy kerülnek meghatározásra az utak. A címkék lehetnek állandók és ideiglenesek egyaránt. Természetesen az algoritmus kezdetén minden címke ideiglenes, csak akkor változtatjuk meg állandóra, ha bebizonyosodik, hogy nincs nála jobb útvonal. Az eljárást a 64. ábrán mutatjuk be.

64. ábra. A Dijkstra algoritmus működése

Nézzük tehát, hogyan is működik ez az algoritmus.

  • Az első ábrán látható a kiindulási állapot. Az A csúcstól keressük az optimális távolságot. Első lépésben megállapítjuk az A-ból kiinduló élek távolságát, majd ennek értékét felírjuk az A-hoz kapcsolódó csúcspontok után zárójelben, majd annak a csúcsnak az azonosítóját, amelyből kiindultunk.
  • A következő lépésben az előzőleg legrövidebb útvonallal kapcsolódó csúcspontot vesszük kiindulásként, ami a példánkban a B (2, A) csúcspont. Ettől mérjük meg a kiinduló élek hosszát. Mivel itt csak egy él jöhet számításba, ennek lesz a legoptimálisabb a távolsága. A C (4, B) jelölés azt jelenti, hogy az A-C távolság 4, míg a távolságnál a B csúcsból indultunk ki. Ennek akkor lesz jelentősége, amikor fel akarjuk használni az útvonalat, ugyanis fontos azoknak a csúcspontoknak az ismerete, amelyeken keresztül a csomagokat továbbíthatjuk.
  • Most már a C (4, B) lesz a kiindulási csúcs, amelyből két él fut ki, tehát ezeknek kell a távolságát meghatároznunk.
Ezeket a lépéseket mindaddig ismételjük, amíg az összes útvonalat fel nem térképezzük. Abban az esetben, ha van rövidebb útvonal,mint amit a kiindulási pontból meghatároztunk, akkor az éleket átszámozzuk. Megjegyezzük, hogy az eljárás nem használható olyan gráfokban, melyek negatív éleket tartalmaznak. Ennek bizonyításától eltekintünk, az ilyen gráfokra a Bellman-Ford által meghatározott algoritmust használhatjuk. Az Dijkstra eljárás pszeudokódja az alábbi módon adható meg:

DIJKSTRA(s)
        INICIALIZÁL(s)
        S=üres
        Q=V
        while Q nem üres
                u=KIVESZ-MIN(Q)
                S=S U {u}
                for u minden v szomszédjára
                        KÖZELÍT(u,v)

Floyd-Warshall algoritmus

Előfordulhat, hogy minden pontból minden pontba meg kell állapítanunk a legrövidebb útvonalakat. Természetesen erre is használható a Dijkstra-algoritmus, minden csomópontra lefuttatva. Most nézzünk meg egy másik módszert, ami egy, az előzőtől eltérő modell használ.

Tekintsük meg a 65. ábrán felrajzolt gráfot.

65. ábra. Mintagráf a Floyd-Warshall algoritmus bemutatásához

Az ábráról leolvashatók az élek súlyai. Ezekből írjuk fel a gráfhoz tartozó súlymátrixot:

A nullák helyére írjunk végtelent:

Ennek megfelelően az útmátrix:

vezessünk be egy új mátrixszorzást:

ahol az Ak mátrixok sorozata k=1..m-ig, ahol az m az A mátrix mérete (m*m), vagyis a példában m = 4és A0 = A.

A kapott Am eredménymátrix a legrövidebb utakat adja.

Az első menetben k=1-re kapott mátrix:

A megfelelő útmátrix:

A végeredményt k=4-re kapjuk, vagyis a legrövidebb utak hossza:

Ebből az útmátrix:

Az algoritmust bemutatjuk 66. ábrán struktogram formájában is:

66. ábra a Floyd-Warshall algoritmus struktogramja