Gyors IP forgalomtovábbítás tömörített prefix fákkal

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

Az internet folyamatos terjedésének köszönhetően az elmúlt években az IP útválasztók forgalomtovábbítási tábláinak (FIB, Forwarding Information Base) mérete, dinamikája és terhelése jelentősen megnőtt. A növekedés mellett ehhez hozzájárul a mobilkommunikáció rohamos terjedése, illetve az IPv6 térhódítása is. A modern IP útvonalválasztókban leggyakrabban használt FIB adatstruktúra a prefix fa, mely másodpercenként több millió komplex lekérdezési, illetve módosítási műveletet képes támogatni, azonban a memóriaigénye is jelentős. Jelen munkában bemutatok néhányat a prefix fa tömörítését célzó algoritmusok közül, különös figyelmet fordítva a prefix fa hajtogatásra. Ezen algoritmusnak szüksége van egy segéd-adatszerkezetre, melynek megvalósítására is bemutatok néhány már létező megoldást, és egy új szervezési elvű módszert is ismertetek.

A forgalomtovábbítási tábla tömörítése azonban csak az első lépés egy, a gyakorlatban is használható megoldás felé, ugyanis az útvonalválasztókban tárolt

FIB-hez rengeteg frissítés érkezik, tehát az adatszerkezet dinamikus, így betömörített állapotában is támogatnia kell a frissítés, törlés műveleteit. Erre a feladatra algoritmust mutatok be.

A különböző tömörítési módszerek hatékonyságának mérése céljából szimulációs környezetet készítettem. Ennek bemutatása után rátérek a segítségével

elvégzett teljesítményvizsgálatra. Az analízis során olyan kérdésekre kerestem a választ, mint hogy az egyes tömörítési algoritmusok milyen hatékonyságot érnek el különböző helyzetekben, vagy hogy mennyi időt vesz igénybe a tömörítés. Ezenfelül megvizsgáltam az említett segéd-adatszerkezet méretét és a kezeléséhez szükséges időt is. Végül dinamikus környezetben végeztem méréseket, amely során azt az eredményt találtam, hogy a prefix fa hajtogatáshoz szerkesztett frissítő algoritmus a gyakorlatban is megállná a helyét.

Letölthető fájlok

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