A forgalomirányítás (routing) feladata a a csomagok hatékony (gyors) eljuttatása az egyik csomópontból a másikba, illetve a csomagok útjának a kijelölése a forrástól a célállomásig.
A hálózatot célszerű gráfként modellezni, ahol a csomópontok a csomagtovábbító IMP-k, és a csomópontokat összekötő élek az IMP-k közötti információs adattovábbító csatornák. A csomagok a hálózati vonalakon keresztül jutnak egy IMP-be, majd az valamilyen irányba továbbküldi a csomagokat. Mivel az ilyen hálózati csomópontok irányítási, továbbküldési kapacitása véges, elképzelhető a csomagok sorban állása a bemenő oldalon.
A forgalomirányítási szemléletünket nagyon jól segíti az olyan analógia, ahol a hálózatot a közúti hálózat, míg a csomagokat az autók képviselik. A csomópontok pedig természetesen az útkereszteződések.
Vonalkapcsolt hálózatoknál az útvonal kijelölése a hívás felépítésének fázisában történik. Csomagkapcsolt hálózatokban az útvonal kijelölése vagy minden csomagra egyedileg történik, vagy kialakít egy olyan útvonalat amelyen egy sorozat csomag megy át. Ezért a csomópontoknak ún. routing táblákat kell tartalmaznia, amiben a vele kapcsolatban álló csomópontokra vonatkozó adatok (pl. távolság) be van jegyezve
A forgalomirányítás összetettségét alapvetően meghatározza a hálózat topológiája. Például egy csillaghálózatban, mivel a csillag központjában lévő csomóponton keresztül történik az adatátvitel, kizárólag ennek kell rendelkeznie a forgalomirányításhoz szükséges minden információval.
Egy másik ilyen szempontból egyszerű elrendezés a két irányú kommunikáció miatt duplán kialakított gyűrű, hiszen csomópontból csak két irányba lehet elküldeni a csomagokat, bár a két lehetséges út közül az egyik általában rövidebb a másiknál. Ezért vagy minden csomópont egy routing táblát tartalmaz, amiben az összes többire vonatkozó távolság be van jegyezve, vagy a csomópontok számozási rendszere olyan, hogy a címe alapján a távolság meghatározható. Egy gyűrű esetén egyirányú pont-pont kapcsolat van, tehát a forgalomirányítás a másik pontba való küldésre egyszerűsődik.
Általában is elmondható, hogy szabályos elrendezések esetében általában könnyebb az optimális forgalomirányítási algoritmus kidolgozása. A legtöbb valóságos hálózat lényegesen bonyolultabb topológiájú, szabálytalan szövevényes és sokszor állandóan változó szerkezettel rendelkezik.
A forgalomirányító algoritmusok osztályozásának alapjául a következő négy irányítási főfunkciót tekinthetjük:
vezérlésmód; (Hogyan?)
döntésfolyamat; (Milyen esetben?)
információ-karbantartó folyamat; (Hálózati forgalmi ismeretek frissítése.)
továbbító eljárás (Hogyan jut el a vezérlési információ a csomópontokhoz?)
Ezek feladata a forgalomirányítási információk áramlásának szabályozása, a kerülő utak választékának kialakítása, az irányítási információk felújítása valamennyi csomópontban és az útvonalválasztás az adatcsomagok részére.
A forgalomirányítási algoritmusoknak két osztálya van:
Adaptív (alkalmazkodó): A hálózati forgalomhoz alkalmazkodik.
Determinisztikus (előre meghatározott): Az útvonal-választási döntéseket nem befolyásolják a pillanatnyi forgalom mért vagy becsült értékei.
Ezek alapján alapvetően négy lehetséges vezérlésmód különböztethető meg:
determinisztikus forgalomirányítás: Olyan rögzített eljárás, amelyet a változó feltételek nem befolyásolnak.
elszigetelt adaptív forgalomirányítás: Minden csomópont hoz irányítási döntéseket, de csak helyi információk alapján.
elosztott adaptív forgalomirányítás: A csomópontok információt cserélnek azért, hogy az irányítási döntéseket a helyi és a kapott információkra együtt alapozhassák.
központosított adaptív forgalomirányítás: A csomópontok a helyi forgalmi információikat egy közös irányító központnak jelentik, amely erre válaszul forgalomirányítási utasításokat ad ki az egyes csomópontok részére.
Az említetteken kívül bevezethető még egy további forgalomirányítás-típus is, amelyet deltairányításnak neveznek. Ennél az eljárásnál a központi irányító egység munkáját a forgalomirányítási döntésekhez kizárólag abban az esetben használják fel, ha ezek a helyi információkra nem alapozhatók.
A legrövidebb út meghatározása
Nyilvánvaló hogy a forgalomirányítás során két pont között meg kell találni a legoptimálisabb útvonalat, amely még egyéb csomópontokat tartalmaz. Az optimális útvonal nem feltétlenül jelenti a fizikailag legrövidebb útvonalat, mivel számos egyéb tényező is befolyásolhatja az optimális választást: lehet például mértéknek a csomópont-átlépések számát tekinteni, lehet azt az időt, hogy mennyi idő alatt jut el a csomag, vagy a vonalhasználat költségeit. Az objektív mérték megállapításához lehet olyan teszteket futtatni az adott szakaszokon, amely magadja az átlagos sorbaállási és átviteli késleltetési időt, és ezt tekinti a mértéknek. Általánosan egy adott szakasz mértékét a távolság, az adatátviteli sebesség, az átlagos forgalom, a kommunikációs költség, az átlagos sorhossz vagy más egyéb tényezők alapján határozzák meg.
forgalomirányitás
Matematikailag a probléma a gráfelmélet segítségével tárgyalható, ahol a csomópontok az egyes IMP-k, és a csomópontokat összekötő éleket jellemezzük az előbb említett mértékekkel. A feladat a gráf két csomópontja közötti olyan élekből álló útvonal meghatározása (shortest path), amelyre az érintett élek mértékeinek összege minimális. Az ismertetett módszer Dijsktrá-tól (1959) származik.
Minden csomópontot címkével látunk el, amely zárójel első tagjaként tartalmazza az adott csomópont legrövidebb távolságát a forráscsomóponttól. Ez induláskor minden csomópontra végtelen. A zárójelben lévő második tag annak a csomópontnak a neve, amelyen keresztül valósul meg ez a legrövidebb út.
Az algoritmus működése során utakat talál, és úgy változnak a címkék is a legjobb utat tükrözve. Egy címke ideiglenes vagy állandó lehet. Amikor az algoritmus felfedezi, hogy egy adott címke a forrástól a címkéhez tartozó csomópontig vezető legrövidebb utat jelzi, akkor a címkét állandóvá teszi, és ezután már nem változtatja.
Nézzük a febti ábrát! A csomópontokat vonalak kötik össze, ahol a ráírt számok mértéket, például távolságokat jelenthetnek. A feladat az A és D pontok közötti legrövidebbi út megtalálása. Induláskor az A csomópontot állandóvá tesszük (önmagától ő van legközelebb...), és ezt a hozzátartozó kis kör befeketítésével jeleztük az ábrán. A vizsgált csomópontot aktuális csomópontnak nevezzük.
Ezután sorban egymás után megvizsgáljuk az A aktuális csomópont szomszédos csomópontjait (itt a B és G), és az A-tól való távolságukat a zárójelbe elsőként beírjuk. Minden A-val szomszédos csomópont megvizsgálása után az összes frissen címkézett csomópont megvizsgálása következik, melynek során azt a csomópontot tesszük állandóvá, amelyik a legkisebb értékű címkével rendelkezik. Ez a csomópont lesz egyben a következő munkacsomópont is.
A példában ez a B pont. Most tehát, a B-től indulunk, és ennek szomszédait vizsgáljuk. B-nek két szomszédja van: E és C. E pont B-től 2 egységre van, és mivel B pont A-tól való távolsága 2, ezért E pont (4,B) címkét, C pont (9,B) címkét kap. (C pont A-tól való távolsága 9, és B ponton keresztül vezet. Mivel E címkéje kisebb (4), ezért E lesz állandóvá téve, és most E szomszédjait vizsgáljuk.
Ez a G és F pont. F pont (6,E), G pont (5,E) címkéjű lesz, ezért G lesz állandó. Ennek szomszédjai: A, E, H. Ezek közül A és E már állandó címkéjű, H címkéje (9,G) lesz. Ezek közül a legkisebb már rögzített, ezért E következő legkisebb szomszédját, F-et kell vizsgálni, az lesz állandó.
F szomszédjai: E, C, és H pont. F távolsága ezeken keresztül A-tól rendre 6, 12 és 9, ezért F a (6,E) címkével lesz állandó.
Az állandó F szomszédjai közül H távolsága A-tól 8, C-nek 12, ezért H(8,F) lesz állandó. Ennek a végpont a szomszédja, ezért D(10,H) lesz a címkéje.
Azaz A és D közötti legrövidebb út 10 egység, és ez az A-B-E-F-H-D útvonal.
Determinisztikus forgalomirányítás
Vannak olyan forgalomirányító módszerek, amelyeknél nincs szükség semmilyen forgalomirányítási táblára, a hálózati topológia ismeretére, minden csomópont autonóm módon, azonos algoritmus alapján dolgozik.
A véletlen forgalomirányító eljárás alapján működő rendszerben a továbbítandó csomagot a csomópont egy ún. véletlen folyamat segítségével kiválasztott az érkező vonaltól eltérő más vonalon küldi tovább. Mivel a hálózat által ilyen módon szállított csomagok véletlen bolyonganak, ésszerűnek látszik, ha a csomagokhoz hozzárendeljük a mozgásuk során bejárt szakaszok számát és töröljük azokat a csomagokat, amelyek lépésszáma elér egy előre meghatározott értéket. Ez az eljárás nem garantálja a csomagok kézbesítését, de nagyon egyszerűen realizálható, és nem túl bonyolult hálózatokban jól működhet.
Az elárasztásos forgalomirányító eljárás sem igényel semmi ismeretet a hálózatról. A csomópontok, mikor egy csomagot továbbítanak, a bejövő csomagot minden vonalra kiküldenek, kivéve ahonnan érkezett. A lépések száma itt is korlátozva van. Jelentős érdeme a módszernek, hogy a csomag legalább egy példányban mindenképp a legrövidebb úton ér célba. Ez azonban jelentősen terheli a rendszert, mivel nagyszámú másolat (redundancia) van, és sok felesleges továbbítás történik. Az algoritmus rendkívül megbízható, és még megsérült rendszer esetén is működőképes. Érhető, hogy katonai alkalmazások esetén előtérbe kerülhet a módszer, mert erősen sérült hálózatban (sok csomópontot kilőnek) is nagy a valószínűsége egy üzenet célba jutásának.
Adaptív forgalomirányítás
A probléma a hálózat elosztott jellegéből ered. Mikor a csomópontok irányítási döntéseket hoznak, olyan eseményeket kell figyelembe venniük, amelyek a hálózat távoli részében történtek, és amelyekről vagy egyáltalán nem rendelkeznek semmiféle információval, vagy a meglevő információjuk már időszerűtlen.
A közúthálózatban az autóvezető a forgalmi információhoz rádión jut hozzá; ideálisan szervezett úthálózatban, amelyben fejlett forgalmi információs rendszer működik az autós ki tudja kerülni az akadályokat, mert kerülő utakat választhat. Ez azért lehetséges, mert a forgalmi információkat külön rendszeren gyorsabban továbbítják, mint ahogyan maguk a járművek haladnak. Az irányító központ veszi a rádión érkező forgalmi jelentéseket, amelyeket a megfigyelőpontokról küldenek, és ezek alapján tanácsokat ad a közlekedők részére
A csomaghálózatokban a forgalomirányítási információ ugyanazon a közegen és ugyanolyan sebességgel halad, mint a felhasználói információ. Nem volna értelme a csomagkapcsolt hálózatban az irányítási és egyéb vezérlő információkat egy külön, nagy adatátviteli sebességű rendszerben, a felhasználói forgalmat pedig kis sebességű vonalakon továbbítani.
A csomaghálózat szempontjából is jó lenne az egész hálózatra kiterjedő forgalomirányítási információ azonnali elérhetősége. Bár a gyakorlatban ez megvalósíthatatlan, a szimulációs modellezés módszerével mégis analizálták az ilyen módon működő hálózat elméleti teljesítőképességét. A szimuláció során minden egyes csomópont úgy hozta meg irányítási döntését, hogy ehhez a hálózat többi részéről is teljes körű és közvetlen áttekintése volt. Az irányító algoritmus — ismerve az összes többi csomóponton a sorok hosszát és minden egyes vonalon az áthaladó csomagok számát — az irányítás alatt álló csomagja részére azt a következő, optimális adatátviteli vonalat választotta ki, amelyen az áthaladva minimális késleltetési idővel érkezhetett célba. Ennek a szimulációs kísérletnek teljesen váratlanul az volt az eredménye, hogy itt az átlagos késleltetési idők nem voltak lényegesen kisebbek, mint a rögzített forgalomirányító eljárásnál, amelynél a forgalomirányítási táblákat a legrövidebb utakra állították be.
Ennek az lehetett az oka, hogy bár a forgalomirányítás a pillanatnyilag lehető legpontosabb információn alapult, az időközben megváltozott forgalom miatt a döntés pillanatában optimális útvonal a kérdéses csomag célba érkezése előtt már nem volt optimálist. Még az is előfordulhat ennél a módszernél, hogy több csomópont egyszerre fedez fel egy gyengén terhelt hálózatrészt, és ezért valamennyi ide tereli a forgalmat és abban erős torlódást okoz. Ez szabályozástechnikai analógiával egy lengő rendszernek felel meg. Az ideális algoritmus sem tudja előre figyelembe venni a jövőben bekövetkező eseményeket. A szimuláció jól jellemzi a különböző, ténylegesen működő forgalomirányító algoritmusok egyik lehetséges nagy hátrányát; azt a tényt, hogy a hálózat egy bizonyos részéről a hálózat többi részei esetleg úgy értesülnek, hogy az pillanatnyilag alig van terhelve és tartalékkapacitással rendelkezik. Ha ezek a részek ugyanakkor éppen torlódással küszködnek, valamennyien egyszerre fognak arra törekedni, hogy ebbe az alig terhelt zónába tereljék a forgalmat, amivel ott még súlyosabb torlódást idézhetnek elő. A valóságos hálózatokban alkalmazott adaptív forgalomirányító eljárásoknak vagy a helyileg rendelkezésre álló információt (izolált adaptív irányítás), vagy a hálózatban terjesztett információt kell felhasználniuk.
Központi adaptív forgalomirányítás
A fentebb említett forgalomirányító algoritmusok vagy a helyileg rendelkezésre álló, vagy a szomszédos csomópontok között cserélt információt használták.
A központosított adaptív forgalomirányításban minden egyes csomópont helyzetjelentést állít össze, és abban a folyó sorhosszakat, a hálózat elemeinek meghibásodásait, stb. elküldi a hálózat forgalomirányító központjába (RCC = Routing Controll Center). A központ ezek alapján átfogó képet alakít ki a hálózatról, és valamennyi forgalmi áramlat részére meg tudja határozni a legkedvezőbb útvonalat. Ezeket a legjobb utakat a hálózat csomópontjai forgalomirányítási táblák formájában kapják meg.
A központnak szóló helyzetjelentéseket és a csomópontoknak szóló új irányítási táblákat szabályos időközözönként (szinkron üzemmódban) vagy csak jelentős változás hatására (aszinkron üzemmódban) küldik. Ha a szinkron üzemmódot választják, akkor az irányító algoritmus működtetése érdekében a hálózatban áramoltatott vezérlő információ fantasztikus mennyiségűvé válhat. Különösen, ha a hálózat maga nagy, akkor a túlzott mértékű irányítási funkció jelentős többletterhelést okoz. Aszinkron üzemmódban viszont csak elfogadható mennyiségű vezérlő információ áramlik a hálózatban.
Azt várhatnánk, hogy a hálózat forgalomirányító központja az optimális utak kiválasztásához a lehető legjobban hasznosítja a hálózat kapacitását. Az elkerülhetetlen időkülönbségek miatt a csomópontokból elinduló állapotjelentések eleve késve érkeznek meg a központba és a távoli csomópontokból ez a késés már jelentős lehet. Megfordítva, miután a központ elvégezte a forgalomirányító funkció által igényelt tekintélyes idejű számításokat, további időhátrány származhat abból, hogy a csomópontok késve kapják a módosított forgalomirányítási táblákat. Így azután a központ olyan információk alapján dolgozik, amely részben már elavultak, és a csomópontok részére is olyan utasításokat ad ki, amelyek még inkább elavultak, amikor célba érnek.
Elszigetelt forgalomirányítás
Ilyenkor a forgalomirányítási döntéseket a helyi körülmények alapján hozza a csomópont. Egyszerű algoritmus az ún. forró krumpli algoritmus. Ennek az a lényege, hogy a beérkezett abba kimeneti sorba rakja, amely a legrövidebb, legrövidebb ideig "égeti a kezét", gyorsan megszabadul tőle. Lényeges, hogy nem foglalkozik az irányokkal.
Érdekes kiterjesztése az algoritmusnak, amikor ennél a döntésnél az irányokhoz tartozó mértékeket is figyelembe veszi.
Ez azt jelenti, hogy nem küldi automatikusan a legrövidebb sorba, hanem figyelembe veszi a kiválasztott sor mértékét is.
forró krumpli algoritmus
Az ábrán látható X jelű csomópont felől érkező csomag az eredeti algoritmus szerint B felé lenne elküldve. A módosított algoritmus szerint ez már nem biztos, hiszen a mértéke (jósága) csak 0.6, ezért talán jobb lehet az A irányt választani. A korrekt döntéshez kell egy a sorhosszt jellemző mérőszámot is választani (1-ha üres a sor, 0 — ha nagyon sok csomag van előtte) és így pl. a két szám szorzatának nagysága alapján hozni meg az irányra vonatkozó döntést.
Egy másik lehetséges algoritmus a fordított tanulás módszere. A hálózatban minden csomópont egy csomagot indít el, amely tartalmaz egy számlálót és az elindító azonosítóját. A számláló értéke minden csomóponton történő áthaladáskor nő eggyel. Amikor egy csomópont (IMP) egy ilyen csomagot vesz, akkor ezt elolvasva tudja, hogy a csomagot küldő hány csomópontnyi távolságra van tőle.
Természetesen az optimális út keresése érdekében, ha ugyanarra a távoli csomópontra egy kedvezőbb értéket kap (van rövidebb út is), akkor az előzőt eldobva ezt jegyzi meg magának. Ha azonban meghibásodás következik be, vagy az optimális útvonal valamelyik része túlterhelődik, akkor ezt az algoritmus nem veszi észre. Ezért célszerű időnként "mindent felejteni", törölni a feljegyzéseket, hogy az ilyen változó körülményekre is működjön az algoritmus.
Elosztott adaptív forgalomirányítás
A megvalósított hálózatokban mindeddig legnépszerűbb az elosztott adaptív forgalomirányító eljárás.
Az algoritmus fő célkitűzése az adatforgalom részére a legkisebb késleltetéssel járó útvonalak keresése. E célból minden egyes csomópontban egy táblázatot hozunk létre, amely minden egyes célállomáshoz megadja a legkisebb késleltetésű útvonalat, s ezzel együtt a továbbításhoz szükséges idő legjobb becsült értékét. A hálózat működésének kezdetén a késleltetések a hálózat topológiája alapján becsült értékek, később azonban, mihelyt a csomagok célba értek, a becsült késleltetési időket felváltják a hálózatban ténylegesen mért továbbítási idők. Az eredeti algoritmus szerint a késleltetési táblák adatait a szomszédos csomópontok rendszeresen megküldik egymásnak. Amikor a késleltetési táblákat megküldték, a csomópontok áttérnek a késéseket újraszámító fázisba, amelyben a saját sorhosszaikat és a szomszédos csomópontok által küldött késleltetési értékeket figyelembe veszik.
A szomszédos csomópontok között a késleltetési táblák cseréje természetesen sok vezérlőcsomag továbbításával történik, ami jelentős többletterhelést ró a hálózatra. Ha a táblákat túl gyakran, pl. 2/3 másodpercenként tartják karban, a hálózati mérések azt mutatják, hogy a kis adatátviteli sebességű vonalak kapacitásának 50 százalékát a késleltetési táblák továbbításával járó forgalom foglalja le, és a lefoglalt kapacitás még a nagyobb sebességű vonalak esetén is észlelhető — bár kisebb — mértékű. A továbbított információról kimutatható, hogy az átvitt késleltetési táblák igen gyakran ugyanazt vagy majdnem ugyanazt az információt tartalmazzák, mint az őket megelőzők.
A táblák ilyen, szinkron karbantartása helyett az aszinkron karbantartás a célravezetőbb. Ez utóbbi azt jelenti, hogy a csomópontoknak csak akkor kell továbbítaniuk a késleltetési táblákat, ha számottevő változást észlelnek a forgalom intenzitásában, vagy a hálózat elemeinek működési körülményeiben. A késleltetési táblák újraszámítására csak akkor kerül sor, ha jelentősebb helyi változás történt, vagy ha módosított késleltetési tábla érkezik valamelyik szomszédos csomóponttól.
A hálózatot célszerű gráfként modellezni, ahol a csomópontok a csomagtovábbító IMP-k, és a csomópontokat összekötő élek az IMP-k közötti információs adattovábbító csatornák. A csomagok a hálózati vonalakon keresztül jutnak egy IMP-be, majd az valamilyen irányba továbbküldi a csomagokat. Mivel az ilyen hálózati csomópontok irányítási, továbbküldési kapacitása véges, elképzelhető a csomagok sorban állása a bemenő oldalon.
A forgalomirányítási szemléletünket nagyon jól segíti az olyan analógia, ahol a hálózatot a közúti hálózat, míg a csomagokat az autók képviselik. A csomópontok pedig természetesen az útkereszteződések.
Vonalkapcsolt hálózatoknál az útvonal kijelölése a hívás felépítésének fázisában történik. Csomagkapcsolt hálózatokban az útvonal kijelölése vagy minden csomagra egyedileg történik, vagy kialakít egy olyan útvonalat amelyen egy sorozat csomag megy át. Ezért a csomópontoknak ún. routing táblákat kell tartalmaznia, amiben a vele kapcsolatban álló csomópontokra vonatkozó adatok (pl. távolság) be van jegyezve
A forgalomirányítás összetettségét alapvetően meghatározza a hálózat topológiája. Például egy csillaghálózatban, mivel a csillag központjában lévő csomóponton keresztül történik az adatátvitel, kizárólag ennek kell rendelkeznie a forgalomirányításhoz szükséges minden információval.
Egy másik ilyen szempontból egyszerű elrendezés a két irányú kommunikáció miatt duplán kialakított gyűrű, hiszen csomópontból csak két irányba lehet elküldeni a csomagokat, bár a két lehetséges út közül az egyik általában rövidebb a másiknál. Ezért vagy minden csomópont egy routing táblát tartalmaz, amiben az összes többire vonatkozó távolság be van jegyezve, vagy a csomópontok számozási rendszere olyan, hogy a címe alapján a távolság meghatározható. Egy gyűrű esetén egyirányú pont-pont kapcsolat van, tehát a forgalomirányítás a másik pontba való küldésre egyszerűsődik.
Általában is elmondható, hogy szabályos elrendezések esetében általában könnyebb az optimális forgalomirányítási algoritmus kidolgozása. A legtöbb valóságos hálózat lényegesen bonyolultabb topológiájú, szabálytalan szövevényes és sokszor állandóan változó szerkezettel rendelkezik.
A forgalomirányító algoritmusok osztályozásának alapjául a következő négy irányítási főfunkciót tekinthetjük:
vezérlésmód; (Hogyan?)
döntésfolyamat; (Milyen esetben?)
információ-karbantartó folyamat; (Hálózati forgalmi ismeretek frissítése.)
továbbító eljárás (Hogyan jut el a vezérlési információ a csomópontokhoz?)
Ezek feladata a forgalomirányítási információk áramlásának szabályozása, a kerülő utak választékának kialakítása, az irányítási információk felújítása valamennyi csomópontban és az útvonalválasztás az adatcsomagok részére.
A forgalomirányítási algoritmusoknak két osztálya van:
Adaptív (alkalmazkodó): A hálózati forgalomhoz alkalmazkodik.
Determinisztikus (előre meghatározott): Az útvonal-választási döntéseket nem befolyásolják a pillanatnyi forgalom mért vagy becsült értékei.
Ezek alapján alapvetően négy lehetséges vezérlésmód különböztethető meg:
determinisztikus forgalomirányítás: Olyan rögzített eljárás, amelyet a változó feltételek nem befolyásolnak.
elszigetelt adaptív forgalomirányítás: Minden csomópont hoz irányítási döntéseket, de csak helyi információk alapján.
elosztott adaptív forgalomirányítás: A csomópontok információt cserélnek azért, hogy az irányítási döntéseket a helyi és a kapott információkra együtt alapozhassák.
központosított adaptív forgalomirányítás: A csomópontok a helyi forgalmi információikat egy közös irányító központnak jelentik, amely erre válaszul forgalomirányítási utasításokat ad ki az egyes csomópontok részére.
Az említetteken kívül bevezethető még egy további forgalomirányítás-típus is, amelyet deltairányításnak neveznek. Ennél az eljárásnál a központi irányító egység munkáját a forgalomirányítási döntésekhez kizárólag abban az esetben használják fel, ha ezek a helyi információkra nem alapozhatók.
A legrövidebb út meghatározása
Nyilvánvaló hogy a forgalomirányítás során két pont között meg kell találni a legoptimálisabb útvonalat, amely még egyéb csomópontokat tartalmaz. Az optimális útvonal nem feltétlenül jelenti a fizikailag legrövidebb útvonalat, mivel számos egyéb tényező is befolyásolhatja az optimális választást: lehet például mértéknek a csomópont-átlépések számát tekinteni, lehet azt az időt, hogy mennyi idő alatt jut el a csomag, vagy a vonalhasználat költségeit. Az objektív mérték megállapításához lehet olyan teszteket futtatni az adott szakaszokon, amely magadja az átlagos sorbaállási és átviteli késleltetési időt, és ezt tekinti a mértéknek. Általánosan egy adott szakasz mértékét a távolság, az adatátviteli sebesség, az átlagos forgalom, a kommunikációs költség, az átlagos sorhossz vagy más egyéb tényezők alapján határozzák meg.
forgalomirányitás
Matematikailag a probléma a gráfelmélet segítségével tárgyalható, ahol a csomópontok az egyes IMP-k, és a csomópontokat összekötő éleket jellemezzük az előbb említett mértékekkel. A feladat a gráf két csomópontja közötti olyan élekből álló útvonal meghatározása (shortest path), amelyre az érintett élek mértékeinek összege minimális. Az ismertetett módszer Dijsktrá-tól (1959) származik.
Minden csomópontot címkével látunk el, amely zárójel első tagjaként tartalmazza az adott csomópont legrövidebb távolságát a forráscsomóponttól. Ez induláskor minden csomópontra végtelen. A zárójelben lévő második tag annak a csomópontnak a neve, amelyen keresztül valósul meg ez a legrövidebb út.
Az algoritmus működése során utakat talál, és úgy változnak a címkék is a legjobb utat tükrözve. Egy címke ideiglenes vagy állandó lehet. Amikor az algoritmus felfedezi, hogy egy adott címke a forrástól a címkéhez tartozó csomópontig vezető legrövidebb utat jelzi, akkor a címkét állandóvá teszi, és ezután már nem változtatja.
Nézzük a febti ábrát! A csomópontokat vonalak kötik össze, ahol a ráírt számok mértéket, például távolságokat jelenthetnek. A feladat az A és D pontok közötti legrövidebbi út megtalálása. Induláskor az A csomópontot állandóvá tesszük (önmagától ő van legközelebb...), és ezt a hozzátartozó kis kör befeketítésével jeleztük az ábrán. A vizsgált csomópontot aktuális csomópontnak nevezzük.
Ezután sorban egymás után megvizsgáljuk az A aktuális csomópont szomszédos csomópontjait (itt a B és G), és az A-tól való távolságukat a zárójelbe elsőként beírjuk. Minden A-val szomszédos csomópont megvizsgálása után az összes frissen címkézett csomópont megvizsgálása következik, melynek során azt a csomópontot tesszük állandóvá, amelyik a legkisebb értékű címkével rendelkezik. Ez a csomópont lesz egyben a következő munkacsomópont is.
A példában ez a B pont. Most tehát, a B-től indulunk, és ennek szomszédait vizsgáljuk. B-nek két szomszédja van: E és C. E pont B-től 2 egységre van, és mivel B pont A-tól való távolsága 2, ezért E pont (4,B) címkét, C pont (9,B) címkét kap. (C pont A-tól való távolsága 9, és B ponton keresztül vezet. Mivel E címkéje kisebb (4), ezért E lesz állandóvá téve, és most E szomszédjait vizsgáljuk.
Ez a G és F pont. F pont (6,E), G pont (5,E) címkéjű lesz, ezért G lesz állandó. Ennek szomszédjai: A, E, H. Ezek közül A és E már állandó címkéjű, H címkéje (9,G) lesz. Ezek közül a legkisebb már rögzített, ezért E következő legkisebb szomszédját, F-et kell vizsgálni, az lesz állandó.
F szomszédjai: E, C, és H pont. F távolsága ezeken keresztül A-tól rendre 6, 12 és 9, ezért F a (6,E) címkével lesz állandó.
Az állandó F szomszédjai közül H távolsága A-tól 8, C-nek 12, ezért H(8,F) lesz állandó. Ennek a végpont a szomszédja, ezért D(10,H) lesz a címkéje.
Azaz A és D közötti legrövidebb út 10 egység, és ez az A-B-E-F-H-D útvonal.
Determinisztikus forgalomirányítás
Vannak olyan forgalomirányító módszerek, amelyeknél nincs szükség semmilyen forgalomirányítási táblára, a hálózati topológia ismeretére, minden csomópont autonóm módon, azonos algoritmus alapján dolgozik.
A véletlen forgalomirányító eljárás alapján működő rendszerben a továbbítandó csomagot a csomópont egy ún. véletlen folyamat segítségével kiválasztott az érkező vonaltól eltérő más vonalon küldi tovább. Mivel a hálózat által ilyen módon szállított csomagok véletlen bolyonganak, ésszerűnek látszik, ha a csomagokhoz hozzárendeljük a mozgásuk során bejárt szakaszok számát és töröljük azokat a csomagokat, amelyek lépésszáma elér egy előre meghatározott értéket. Ez az eljárás nem garantálja a csomagok kézbesítését, de nagyon egyszerűen realizálható, és nem túl bonyolult hálózatokban jól működhet.
Az elárasztásos forgalomirányító eljárás sem igényel semmi ismeretet a hálózatról. A csomópontok, mikor egy csomagot továbbítanak, a bejövő csomagot minden vonalra kiküldenek, kivéve ahonnan érkezett. A lépések száma itt is korlátozva van. Jelentős érdeme a módszernek, hogy a csomag legalább egy példányban mindenképp a legrövidebb úton ér célba. Ez azonban jelentősen terheli a rendszert, mivel nagyszámú másolat (redundancia) van, és sok felesleges továbbítás történik. Az algoritmus rendkívül megbízható, és még megsérült rendszer esetén is működőképes. Érhető, hogy katonai alkalmazások esetén előtérbe kerülhet a módszer, mert erősen sérült hálózatban (sok csomópontot kilőnek) is nagy a valószínűsége egy üzenet célba jutásának.
Adaptív forgalomirányítás
A probléma a hálózat elosztott jellegéből ered. Mikor a csomópontok irányítási döntéseket hoznak, olyan eseményeket kell figyelembe venniük, amelyek a hálózat távoli részében történtek, és amelyekről vagy egyáltalán nem rendelkeznek semmiféle információval, vagy a meglevő információjuk már időszerűtlen.
A közúthálózatban az autóvezető a forgalmi információhoz rádión jut hozzá; ideálisan szervezett úthálózatban, amelyben fejlett forgalmi információs rendszer működik az autós ki tudja kerülni az akadályokat, mert kerülő utakat választhat. Ez azért lehetséges, mert a forgalmi információkat külön rendszeren gyorsabban továbbítják, mint ahogyan maguk a járművek haladnak. Az irányító központ veszi a rádión érkező forgalmi jelentéseket, amelyeket a megfigyelőpontokról küldenek, és ezek alapján tanácsokat ad a közlekedők részére
A csomaghálózatokban a forgalomirányítási információ ugyanazon a közegen és ugyanolyan sebességgel halad, mint a felhasználói információ. Nem volna értelme a csomagkapcsolt hálózatban az irányítási és egyéb vezérlő információkat egy külön, nagy adatátviteli sebességű rendszerben, a felhasználói forgalmat pedig kis sebességű vonalakon továbbítani.
A csomaghálózat szempontjából is jó lenne az egész hálózatra kiterjedő forgalomirányítási információ azonnali elérhetősége. Bár a gyakorlatban ez megvalósíthatatlan, a szimulációs modellezés módszerével mégis analizálták az ilyen módon működő hálózat elméleti teljesítőképességét. A szimuláció során minden egyes csomópont úgy hozta meg irányítási döntését, hogy ehhez a hálózat többi részéről is teljes körű és közvetlen áttekintése volt. Az irányító algoritmus — ismerve az összes többi csomóponton a sorok hosszát és minden egyes vonalon az áthaladó csomagok számát — az irányítás alatt álló csomagja részére azt a következő, optimális adatátviteli vonalat választotta ki, amelyen az áthaladva minimális késleltetési idővel érkezhetett célba. Ennek a szimulációs kísérletnek teljesen váratlanul az volt az eredménye, hogy itt az átlagos késleltetési idők nem voltak lényegesen kisebbek, mint a rögzített forgalomirányító eljárásnál, amelynél a forgalomirányítási táblákat a legrövidebb utakra állították be.
Ennek az lehetett az oka, hogy bár a forgalomirányítás a pillanatnyilag lehető legpontosabb információn alapult, az időközben megváltozott forgalom miatt a döntés pillanatában optimális útvonal a kérdéses csomag célba érkezése előtt már nem volt optimálist. Még az is előfordulhat ennél a módszernél, hogy több csomópont egyszerre fedez fel egy gyengén terhelt hálózatrészt, és ezért valamennyi ide tereli a forgalmat és abban erős torlódást okoz. Ez szabályozástechnikai analógiával egy lengő rendszernek felel meg. Az ideális algoritmus sem tudja előre figyelembe venni a jövőben bekövetkező eseményeket. A szimuláció jól jellemzi a különböző, ténylegesen működő forgalomirányító algoritmusok egyik lehetséges nagy hátrányát; azt a tényt, hogy a hálózat egy bizonyos részéről a hálózat többi részei esetleg úgy értesülnek, hogy az pillanatnyilag alig van terhelve és tartalékkapacitással rendelkezik. Ha ezek a részek ugyanakkor éppen torlódással küszködnek, valamennyien egyszerre fognak arra törekedni, hogy ebbe az alig terhelt zónába tereljék a forgalmat, amivel ott még súlyosabb torlódást idézhetnek elő. A valóságos hálózatokban alkalmazott adaptív forgalomirányító eljárásoknak vagy a helyileg rendelkezésre álló információt (izolált adaptív irányítás), vagy a hálózatban terjesztett információt kell felhasználniuk.
Központi adaptív forgalomirányítás
A fentebb említett forgalomirányító algoritmusok vagy a helyileg rendelkezésre álló, vagy a szomszédos csomópontok között cserélt információt használták.
A központosított adaptív forgalomirányításban minden egyes csomópont helyzetjelentést állít össze, és abban a folyó sorhosszakat, a hálózat elemeinek meghibásodásait, stb. elküldi a hálózat forgalomirányító központjába (RCC = Routing Controll Center). A központ ezek alapján átfogó képet alakít ki a hálózatról, és valamennyi forgalmi áramlat részére meg tudja határozni a legkedvezőbb útvonalat. Ezeket a legjobb utakat a hálózat csomópontjai forgalomirányítási táblák formájában kapják meg.
A központnak szóló helyzetjelentéseket és a csomópontoknak szóló új irányítási táblákat szabályos időközözönként (szinkron üzemmódban) vagy csak jelentős változás hatására (aszinkron üzemmódban) küldik. Ha a szinkron üzemmódot választják, akkor az irányító algoritmus működtetése érdekében a hálózatban áramoltatott vezérlő információ fantasztikus mennyiségűvé válhat. Különösen, ha a hálózat maga nagy, akkor a túlzott mértékű irányítási funkció jelentős többletterhelést okoz. Aszinkron üzemmódban viszont csak elfogadható mennyiségű vezérlő információ áramlik a hálózatban.
Azt várhatnánk, hogy a hálózat forgalomirányító központja az optimális utak kiválasztásához a lehető legjobban hasznosítja a hálózat kapacitását. Az elkerülhetetlen időkülönbségek miatt a csomópontokból elinduló állapotjelentések eleve késve érkeznek meg a központba és a távoli csomópontokból ez a késés már jelentős lehet. Megfordítva, miután a központ elvégezte a forgalomirányító funkció által igényelt tekintélyes idejű számításokat, további időhátrány származhat abból, hogy a csomópontok késve kapják a módosított forgalomirányítási táblákat. Így azután a központ olyan információk alapján dolgozik, amely részben már elavultak, és a csomópontok részére is olyan utasításokat ad ki, amelyek még inkább elavultak, amikor célba érnek.
Elszigetelt forgalomirányítás
Ilyenkor a forgalomirányítási döntéseket a helyi körülmények alapján hozza a csomópont. Egyszerű algoritmus az ún. forró krumpli algoritmus. Ennek az a lényege, hogy a beérkezett abba kimeneti sorba rakja, amely a legrövidebb, legrövidebb ideig "égeti a kezét", gyorsan megszabadul tőle. Lényeges, hogy nem foglalkozik az irányokkal.
Érdekes kiterjesztése az algoritmusnak, amikor ennél a döntésnél az irányokhoz tartozó mértékeket is figyelembe veszi.
Ez azt jelenti, hogy nem küldi automatikusan a legrövidebb sorba, hanem figyelembe veszi a kiválasztott sor mértékét is.
forró krumpli algoritmus
Az ábrán látható X jelű csomópont felől érkező csomag az eredeti algoritmus szerint B felé lenne elküldve. A módosított algoritmus szerint ez már nem biztos, hiszen a mértéke (jósága) csak 0.6, ezért talán jobb lehet az A irányt választani. A korrekt döntéshez kell egy a sorhosszt jellemző mérőszámot is választani (1-ha üres a sor, 0 — ha nagyon sok csomag van előtte) és így pl. a két szám szorzatának nagysága alapján hozni meg az irányra vonatkozó döntést.
Egy másik lehetséges algoritmus a fordított tanulás módszere. A hálózatban minden csomópont egy csomagot indít el, amely tartalmaz egy számlálót és az elindító azonosítóját. A számláló értéke minden csomóponton történő áthaladáskor nő eggyel. Amikor egy csomópont (IMP) egy ilyen csomagot vesz, akkor ezt elolvasva tudja, hogy a csomagot küldő hány csomópontnyi távolságra van tőle.
Természetesen az optimális út keresése érdekében, ha ugyanarra a távoli csomópontra egy kedvezőbb értéket kap (van rövidebb út is), akkor az előzőt eldobva ezt jegyzi meg magának. Ha azonban meghibásodás következik be, vagy az optimális útvonal valamelyik része túlterhelődik, akkor ezt az algoritmus nem veszi észre. Ezért célszerű időnként "mindent felejteni", törölni a feljegyzéseket, hogy az ilyen változó körülményekre is működjön az algoritmus.
Elosztott adaptív forgalomirányítás
A megvalósított hálózatokban mindeddig legnépszerűbb az elosztott adaptív forgalomirányító eljárás.
Az algoritmus fő célkitűzése az adatforgalom részére a legkisebb késleltetéssel járó útvonalak keresése. E célból minden egyes csomópontban egy táblázatot hozunk létre, amely minden egyes célállomáshoz megadja a legkisebb késleltetésű útvonalat, s ezzel együtt a továbbításhoz szükséges idő legjobb becsült értékét. A hálózat működésének kezdetén a késleltetések a hálózat topológiája alapján becsült értékek, később azonban, mihelyt a csomagok célba értek, a becsült késleltetési időket felváltják a hálózatban ténylegesen mért továbbítási idők. Az eredeti algoritmus szerint a késleltetési táblák adatait a szomszédos csomópontok rendszeresen megküldik egymásnak. Amikor a késleltetési táblákat megküldték, a csomópontok áttérnek a késéseket újraszámító fázisba, amelyben a saját sorhosszaikat és a szomszédos csomópontok által küldött késleltetési értékeket figyelembe veszik.
A szomszédos csomópontok között a késleltetési táblák cseréje természetesen sok vezérlőcsomag továbbításával történik, ami jelentős többletterhelést ró a hálózatra. Ha a táblákat túl gyakran, pl. 2/3 másodpercenként tartják karban, a hálózati mérések azt mutatják, hogy a kis adatátviteli sebességű vonalak kapacitásának 50 százalékát a késleltetési táblák továbbításával járó forgalom foglalja le, és a lefoglalt kapacitás még a nagyobb sebességű vonalak esetén is észlelhető — bár kisebb — mértékű. A továbbított információról kimutatható, hogy az átvitt késleltetési táblák igen gyakran ugyanazt vagy majdnem ugyanazt az információt tartalmazzák, mint az őket megelőzők.
A táblák ilyen, szinkron karbantartása helyett az aszinkron karbantartás a célravezetőbb. Ez utóbbi azt jelenti, hogy a csomópontoknak csak akkor kell továbbítaniuk a késleltetési táblákat, ha számottevő változást észlelnek a forgalom intenzitásában, vagy a hálózat elemeinek működési körülményeiben. A késleltetési táblák újraszámítására csak akkor kerül sor, ha jelentősebb helyi változás történt, vagy ha módosított késleltetési tábla érkezik valamelyik szomszédos csomóponttól.
Nincsenek megjegyzések:
Megjegyzés küldése