Egy hatékony IP forgalomtovábbítási mechanizmus Linux alapú implementációja

OData támogatás
Konzulens:
Dr. Rétvári Gábor Ferenc
Távközlési és Médiainformatikai Tanszék

A számítógép-hálózatok adatforgalma adatcsomagok formájában kerül továbbításra, amelyek fejlécében azok forrás és célcíme is megtalálható. A gerinchálózati eszközök útvonal választási táblák segítségével végzik az adatok továbbítását a csomagokban található forrástól azok célállomásáig. Minden eszközben, amely ebben a továbbításban érintett, egy útválasztási tábla tartalmazza az összes információt, amely a forrás- és célcímek összerendeléséhez szükséges. A táblát Forwarding Information Base-nek (FIB-nek) nevezik és mérete meghaladhatja az ötszázezer bejegyzést is egy napjainkban használt gerinchálózati eszközben. Minden egyes beérkező IP csomagra egy FIB lekérdezés készül, ami akár másodpercenként 20 milliószor is megtörténhet. Ez az adatszerkezet van használatban a legtöbb internetszolgáltató eszközeiben és szoftver router-ek esetében, főleg azoknál, amelyek Linux operációs rendszert futtatnak.

Ezen feladat teljesítésére nem egyszerű megfelelően gyors és hatékony adatszerkezetet találni, az irodalomban már 1968-ban foglalkoztak a kérdéskörrel. Azóta számos indítványt és megvalósítást készítettek, kezdve a fákhoz hasonló Bináris Leaf-Pushed Trie-okkal, Hash-elési Eljárásokon, Szint- és Útvonal-Tömörített algoritmusokon és Részfák Hajtogatásán át. Diplomamunkám ezek bemutatásán és elkészítésén túl részletekbe bocsátkozóan foglalkozik a Linux Kernel hálózati részének felépítésével, az abban történő útvonal-választási algoritmus működésével.

Munkámban olyan adatszerkezetek általános sorba rendezésére alkalmas módok megtervezését és megalkotását végeztem el, amelyek képesek egy vagy több szabadon választott FIB adatszerkezet tömörített tárolására. A keresési műveleteket is ezeken a tömörített adatszerkezeten valósítottam meg, lookup függvények létrehozásával. Ezeken az adatszerkezeteken végzett teljesítmény-elemzés segítségével a különböző adatszerkezeteket egymással és az eredeti Linux implementációval is összehasonlítottam. A méréseket egy erőteljes Linux Operációs Rendszert futtató szoftveres útvonalválasztón végeztem és az adatszerkezetek tárolási-, valamint számítási hatékonyságát vizsgáltam, amelyeket a memóriahasználat mellett a processzor utasítási ciklusainak és gyorsítótár-hibáinak mérésével végeztem.

A teljesítmény-értékelés alapján a vizsgált algoritmusok és sorba rendezési formák használatát, különösképpen a Multibit Trie Folding Linux-ban történő alkalmazását javaslom. Az elért teljesítmény-növekedés már jelenlegi formájában is kiemelkedő és további fejlesztéssel még nagyobb teljesítmény érhető el.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.