Elárasztásos módszer

Az elárasztás (flooding) egy nagyon egyszerű eljárás, ami a hasznos sávszélességet nagyon leszűkíti, amelyen bizonyos technikákkal segíthetünk. A módszer lényege, hogy a csomópont a beérkező csomagokat minden kimenő vonalon elküldi, kivéve azt a vonalat, amelyről a csomag érkezett. Ez értelemszerűen rengeteg kettőzött csomagot eredményez a hálózatban, amely a hatékony működés szempontjából nem kívánatos. A kettőzött csomagok száma elméletileg végtelen, ezért ennek kiküszöbölése érdekében egyéb technikák alkalmazására is szükségünk van.

Az egyik módszer, hogy minden elküldött csomag fejlécében egy számlálót helyezünk el. Ennek értékét minden csomópontban csökkentjük egészen nulláig. Az ilyen állapotú csomagokat egyszerűen kidobjuk. Amennyiben ismerjük a hálózat topológiáját és a vonalak állapotát késleltetési szempontból, akkor a számlálóban a célállomásig vezető út hosszát kell beállítanunk. Sajnos az esetek többségében nincsenek pontos információin a vonalak állapotára vonatkozólag. Ilyenkor a legrosszabb esetet kell figyelembe venni és a számláló értékét erre beállítani. A legrosszabb eset (worst case) a hálózat teljes mérete.

Egy másik módszer alapján nyilvántartják azokat a csomagokat, amelyek már részt vettek elárasztásban. Ez biztosítja azt, hogy ne küldjünk el még egyszer ugyanazt a csomagot. A küldő IMP, amely gyakorlatilag bármelyik lehet, egy sorszámot helyez el a csomagban, amelyet a rá kapcsolódó hosztoktól kap meg. Minden IMP-nek szüksége van egy forráslistára, amelyben a már látott sorszámokat tartják nyílván. Amennyiben a beérkező csomag már szerepel a listában, az IMP nem küldi tovább, hanem eldobja. A módszer nagyon jók működik, de elsősorban nagy forgalom esetén a lista mérete folyamatosan növekedik. Ez a kezelés hatékonyságát nagy mértékben lerontja, mivel egy adott sorszámot nagyobb listában tovább tart megkeresni. Ennek kivédése érdekében bevezetnek egy számot, amelynek az értéke a arra a számra áll be, amely alatt minden sorszám szerepelt már. Tulajdonképpen ez alatt a szám alatt nincs szükség listára, amivel a teljes lista mérete lecsökkenthető.

Az elárasztásos módszernek kialakult kifinomultabb, de ezzel együtt bonyolultabb változata is. A cél a hasznos sávszélesség növelése és a kettőzött csomagok számának leszorítása. A megoldás a szelektív elárasztás (selective flooding) nevet kapta, amely használatakor az IMP-ek nem küldenek ki minden csomagot minden vonalra, hanem csak azokba, amelyek előre láthatólag megfelelők lesznek.

Mint látható, az elárasztásos módszer nagyon ritka esetekben használható eredményesen. Vannak az életnek olyan speciális területei, ahol viszont nagyon eredményesen ki lehet használni az elárasztás robosztusságát. A katonai terület tipikusan ilyen, mivel előfordulhat, hogy bármelyik kapcsolóelem kárt szenved, amelynek feladatát más útvonalon ilyenkor is el lehet látni.

Távolság alapú forgalomirányítás

Ez a megoldás dinamikus, ami azt jelenti, hogy a forgalom igazodni képes az aktuális forgalmi viszonyokhoz. Nyílván ez hatásos megoldás lehet, mivel mindig naprakész, de nem kell nagy képzelőerő, hogy rájöjjünk ennek biztosan erőforrásigénye lesz. Ez így igaz. A távolság alapú forgalomirányítás (distance vector routing) alapja, hogy minden kapcsolóelem egy táblázatot tart fenn, amelyben minden célponthoz eltárolják a hozzá vezető legrövidebb útvonalat, valamint azt, hogy melyik annak a vonalnak az azonosítója, amelyen keresztül elérhető a célpont. A megoldás nem használható semmire, ha a szomszédos csomópontok nem tudnak egymás táblázatairól semmit, éppen ezért egymás között megadott időközönként frissíteniük kell a táblázatokat.

A 67. ábrán egy hálózat felépítését vehetjük szemügyre. A vonalak késleltetése figyelembevételével az egyes kapcsolóelemek az alábbi táblázatokat tartják fenn.


67. ábra. A távolság alapú útvonalválasztás elve
 

A táblázat alapján képesek a kapcsolóelemek megkeresni a legoptimálisabb útvonalat. Első ránézésre bonyolultnak tűnhet a táblázatok felépítése. Minden tábla tartalmazza az elérhető kapcsolóelemek távolságát, valamint annak a kapcsolónak az azonosítóját, amelyen keresztül elérhető. Ez a megoldás rugalmas, de fontos, hogy a kapcsolóelemek egymás között frissítsék a táblázataikat, amelyekben lehetőség szerint mindig az aktuális értékeknek kell szerepelniük.

Van egy nagyon érdekes tulajdonsága ennek a módszernek. Az, hogy a kedvező változások a hálózatban gyorsabban terjednek, mint a kedvezőtlenek. Ennek az oka természetesen a felépítésben keresendő. Egy példán keresztül nézzük meg, hogy milyen módon történik a változások követése. Tekintsünk egy lineáris hálózatot, mint amilyen a 68. ábrán látható. Ennek minden tagja fenntart egy táblázatot, amelyben a távolságokat tartják nyílván.


68. ábra. A pozitív változások hatása a táblázatok tartalmára

Kezdetben tegyük fel, hogy nem működik a D jelzésű kapcsolóelem. A D elemre vonatkozólag minden kapcsolóelem végtelen értéket állít be, hiszen nem működik. A táblázatok frissítése minden esetben egy megadott ütemben történik, amelyet az órajel határoz meg. Ha bekapcsolódik a D kapcsoló az átvitelbe, akkor a következő cserekor a C jelzésű felismeri ezt és beállítja a távolságot 1-re. A többi még mit sem tud a D állapotváltozásáról. A következő periódusban már a B jelzésű is megkapja a D-re vonatkozó információt, és a távolságot beállítja 2-re. A harmadik cserekor a B kapcsolótól az A jelzésű is megkapja a D működését jelző információt, amelynek hatására beállítja a távolságot 3-ra. Általánosságban elmondhatjuk tehát, hogy egy hálózatban, ahol a leghosszabb út M hosszúságú, M csere után minden kapcsolóelem tudni fog a bekövetkezett kedvező változásról.


69. ábra. A negatív változások hatása a táblázatokra

Egészen más a helyzet akkor, ha meghibásodik egy kapcsolóállomás. Tekintsük ugyanazt a hálózatot, amelyben a távolságokat a D jelzésű kapcsolóelem irányába tárolják a kapcsolók táblázatai. Egy hirtelen bekövetkező hiba folytán a D kapcsoló meghibásodik. A következő frissítéskor a C természetesen nem kap semmiféle információt a D távolságára vonatkozólag, viszont a B kapcsolóelem ismer egy útvonalat, amely 2 távolságra van. Mivel ez kevesebb, mint a végtelen, a C ezt a távolságot (pontosabban eggyel nagyobbat, mivel a B-C távolság 1) fogja beállítani. A következő cserekor a B észreveszi, hogy mindkét szomszédjának távolsága D-től 3, ezért véletlenszerűen kiválasztja az egyiket közülük és a távolságot beállítja 4-re. A folyamat minden táblacserénél ismétlődik, míg a távolságok értéke közelít a végtelenhez. A lassúság oka, hogy soha sincs egyetlen kapcsolóelemnek sem több, mint eggyel nagyobb értéke, mint a szomszédainak a minimuma. Ebből az következik, hogy mindegyik fokozatosan közelít a végtelenhez. Megoldásként szolgálhat, ha a végtelent a leghosszabb út+1-re állítjuk be. Ezt a problémát a végtelenig számolás (count-to-infinity) problémájának nevezzük. Több módszer is ismeretes ennek kivédésére, de ezek mindegyike bonyolult és kevésbé használatos a gyakorlatban.

Kapcsolatállapot alapú forgalomirányítás

A távolságvektor alapú forgalomirányítás nagyon sokáig használatban volt egyszerű alkalmazhatósága miatt. Az egyik legfőbb problémája az, hogy nem veszi figyelembe a vonalak sávszélességét, a távolság a várakozási sorok hossza volt. Ez kezdetben azért nem okozott problémát, mivel minden vonal azonos sávszélességgel rendelkezett. Később egyes vonalakat kicseréltek nagyobb sávszélességet megengedő vonalakra, amelyet ez a rendszer már nem volt képes lekezelni. Persze lehetőség lett volna beépíteni a távolságok kiszámításába a sávszélességet is, azonban a túl lassú volt a közelítése az eljárásnak. Ennek az oka, hogy kidolgoztak egy másik eljárást, amelyet kapcsolatállapot alapú forgalomirányításnak (link state routing) neveznek. Nagyon kellemes módszer, az egyes változatait még a mai napig is széleskörűen használják. A működés lényege, hogy minden kapcsolóelem az alábbi 5 pont alapján végezze a feladatát:
 

  1. Kutassa fel a szomszédait, majd meg kell szereznie a hálózati címeiket.
    Amikor bekapcsolódik a kommunikációba egy kapcsolópont, akkor az első feladata, hogy megkeresse, hogy kik a szomszédai. Ezt egy speciális HELLO csomaggal teszi meg, amely során elvárja, hogy minden kapcsolódó pont visszaküldje az azonosítóját. Természetesen minden azonosítónak egyedinek kell lennie, különben a hálózat működése megbénul. Üzenetszórásos topológia esetében az egész adatátviteli közeget egy csomópontként fogjuk fel és ennek alapján rajzolhatjuk fel a hálózati gráfot.
  2. Minden szomszéd irányába meg kell mérnie a késleltetést, valamint ki kell számítania a költségeket.
    A késleltetés a kommunikáció szempontjából nagyon fontos, ennek alapján lehet kiválasztani a rendelkezésre álló útvonalak közül a legoptimálisabbat. Valószínűleg a leggyorsabb útvonal eredményezi a legkisebb költségű átvitelt, amely elsősorban kapcsolt vonalú hálózatoknál nem utolsó szempont. A módszer hasonlít a szomszédok felkutatásához. A kapcsolópont egy ECHO csomagot küld el a vonalon, amelyet a fogadónak azonnal, késleltetés nélkül vissza kell küldenie. A küldő méri az időt a küldéstől a beérkezésig, amelyet kettővel elosztva megkapja az adott vonal késleltetését. Természetesen ezt a mérés magadott időközönként célszerű elvégezni, mivel a vonal és a fogadó állapota időközben változhat. Abban az esetben viszont, ha ezt nagyon gyakran csináljuk, akkor a hasznos sávszélességet jelentősen lecsökkentjük. A késleltetési időt megmérhetjük úgy, hogy nem vesszük figyelembe a terhelést, valamint úgy is, hogy ezt is beleszámítjuk a mérésbe. utóbbi esetben a számlálót már akkor el kell indítani, amikor a csomagot beletesszük a küldési sorba. Ha a terhelést nem kívánjuk figyelembe venni, akkor a mérés akkor kell indítani, amikor a csomag a küldési sor elejére ért. Mindkét megoldás indokolt lehet, az adott alkalmazás dönti el. A terhelés figyelembevételével két azonos sávszélességű vonal közül a küldő a kevésbé terheltet fogja rövidebbnek értékelni. A teljesítmény ezzel a megoldással maximálisra növelhető. A módszernek van egy hátulütője is. Ha egy cél irányába több, azonos paraméterekkel rendelkező vonal is halad, akkor a kevésbé terheltet fogják a kapcsolóáramkörök előnyben részesíteni. Ennek a következménye, hogy minden csomag ezen a vonalon fog közlekedni, aminek az eredménye, hogy most ez a vonal lesz a terheltebb. A következő frissítésnél már a másik vonal kerül jobb pozícióba. Ez rendkívül bizonytalan forgalomirányítást okoz.
  3. Össze kell állítani egy csomagot, amelye tartalmazza az eddig beszerzett információkat.
    Miután megvannak a késleltetési eredmények, minden kapcsolónak össze kell állítania egy csomagot, amelyben az összes adatot elhelyezik. Minden csomagban azonosítani kell a küldőt, amit egy sorszám és egy, a csomópont korára utaló érték követ, amelyet a csomagok kezelésére használhatunk. Természetesen el kell tárolni a szomszédok eléréséhez tartozó késleltetéseket is. Ebben a lépésben felmerül egy fontos kérdés, nevezetesen az, hogy mikor állítsuk össze a csomagokat. A kedvezőtlenebb, de naprakészebb megoldás, hogy bizonyos időközönként. Ennél általában jobb, amikor valamilyen jelentősebb esemény bekövetkezésekor végezzük el ezt a műveletet.
  4. Ezeket a csomagokat el kell küldeni minden egyes kapcsolóelemnek.
    Ez a lépés nagyon kritikus a működés szempontjából. Amikor egy csomópont ilyen csomagot kap, használni kezdi, aminek a hatása, hogy megváltoztatja az útvonalakat. Ennek az eredménye, hogy az egyes csomópontok más és más topológiát használnak, ami hálózati problémákhoz vezet.
    A csomagokat alapvetően elárasztásos módszerrel küldik szét, annyi kiegészítéssel, hogy minden csomagot ellátnak egy sorszámmal, amelynek az értéke minden küldéskor eggyel növekszik. A kapcsolópontok nyilvántartanak minden forráspont-sorszám párost, amelyet képesek elérni. Amikor egy új csomagot kapnak, amelyben állapotinformációkat találnak, akkor összehasonlítják a listájukkal. Amennyiben ez már másodpéldány, eldobják, ellenkező esetben minden vonalra elküldik, kivéve azt, ahonnan érkezett. Természetesen előfordulhat olyan eset is, amikor az érkező csomag sorszáma alacsonyabb, mint a legmagasabb, már látott sorszám, akkor az ezt jelenti, hogy a csomag már elavult, tehát nem kerül továbbításra.
    Annak érdekében,hogy a sorszámok ne fordulhassanak át, 32 bites sorszámot kell alkalmazni. Egyéb hibák kivédésének jó módszere az életkor beépítése a csomagba. Ennek értéke másodpercenként eggyel csökken. Amennyiben eléri a nullát, akkor az attól a kapcsolóponttól érkező információkat eldobják.
    Amikor megérkezik egy csomag, nem küldik azonnal tovább, hanem egy pufferbe teszik. Amennyiben egy bizonyos időn belül újabb csomag érkezik ugyanattól a forrástól, akkor összehasonlítják. Amennyiben a sorszám azonos, akkor másodpéldányról van szó, tehát eldobják.
  5. Ennek alapján ki kell számítani az összes kapcsolóelemhez vezető legrövidebb út irányát, valamit késleltetését.
    Miután egy csomópont megkapta a kapcsolatállapot csomagok egy készletét, az azokban található információk alapján felépíti a hálózatot modellező gráfot. Ezek után a Dijkstra-algoritmus felhasználásával megkeresik a legrövidebb utat az összes többi kapcsolóponthoz. Az algoritmus eredményeit elmentik a forgalomirányító táblázatokba és folytatódhat a hálózat működése.
Hierarchikus forgalomirányítás

Az egyre növekvő hálózatok esetében a forgalomirányító táblázatok mérete is drasztikusan növekszik. Ez természetesen megnöveli az erőforrásigényt, amely jelentkezik a memória- és a processzorhasználatban, valamint a sávszélességben is. Ilyen esetekben már a lineáris szervezés nem célravezető, sokkal hatékonyabb, ha hierarchikus rendszereket használunk.

Ennek a lényege, hogy forgalomirányító csomópontokat tartományokra (regions) osztjuk fel. Minden forgalomirányító tudja, hogy milyen módon irányítsa a saját tartományában közlekedő csomagokat, de a többi tartomány szerkezeti felépítéséről mit sem tud. Ilyen módon működik a telefonhálózat is, amelyet a cikksorozat korábbi részében már megismerhettünk.

Adatszóró forgalomirányítás

Az adatszórás (broadcasting) abban az esetben használható eredményesen, amikor minden hosztnak el kell küldeni az üzeneteket. A módszer kicsit hasonlít az elárasztásos módszerhez, viszont itt nincsenek csomagkettőzések. Az üzenetszórás során minden irányban egyszerre történik meg a csomagok továbbítása.

Könnyen észrevehetjük,hogy ez a módszer nem túl hasznos pont-pont kapcsolat esetében, mivel ez erősen közelít az elárasztáshoz. Éppen ez az oka, hogy inkább üzenetszórásos topológiánál használható, amely teljes mértékben igazodik a forgalomirányítás eme változatához.

Az adatszóró forgalomirányítás egyik változata a többcélú forgalomirányítás (multidestination routing). Ennek használatakor minden csomagban megtalálható egy lista, amely a célállomások térképét tartalmazza. Amikor egy forgalomirányító csomóponthoz egy ilyen csomag érkezik, megvizsgálja, hogy melyek azok a csomópontok, amelyek irányába el kell ezt küldeni. Mint látjuk, ezzel ki lehet küszöbölni a felesleges csomagkettőzéseket.

Mint látjuk, meglehetősen sokféle forgalomirányítási algoritmussal találkozhatunk a hálózati réteg vizsgálata során. Ezek kialakulását az a törekvés vonta maga után, hogy egy adott célra minél alkalmasabb módszert használjunk. Ez rugalmasságot eredményez azáltal, hogy lehetővé teszi az optimális forgalomirányítás kiválasztását.

A következő részben még mindig a hálózati réteggel fogunk foglalkozni, ugyanis még egy fontos feladatáról, a torlódások kezeléséről még nem írtunk.