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

Az elmúlt években az IP útválasztók forgalomtovábbítási tábláinak (FIB) mérete, dinamikája, és terhelése jelentősen megnőtt. Ennek oka világhálózat növekedése, a mobilkommunikáció rohamos terjedése, illetve az IPv6 térhódítása. A modern IP eszközökben legelterjedtebben használt FIB adatstruktúra a prefix fa, mely másodpercenként több millió komplex lekérdezést illetve módosítási műveletet képes támogatni, azonban a memóriaigénye is jelentős. Ennek csökkentésére célszerű megoldás lehet a közös részfák egyedi tárolásán alapuló tömörített prefix fák használata. A tömörített prefix fa tipikusan jóval kevesebb memóriát igényel, mint az eredeti prefix fa, azonban szükségessé tesz egy nagy méretű járulékos adatstruktúrát is a közös részfák azonosításához.

TDK dolgozatom első felében megvizsgálom a tömörített prefix fákon alapuló FIB-ek gyakorlati alkalmazhatóságát, elsősorban a memóriaigényre, a lekérdezések kiszolgálásának gyorsaságára, illetve az adatstruktúra előállításának erőforrásigényére koncentrálva. Ismertetem a leggyakoribb FIB-szervezési módszereket (prefix fák, hash struktúrák, stb.) és összehasonlítom ezek elméleti és gyakorlati tulajdonságait. Bemutatom továbbá az általam tervezett szimulációs környezetet, melynek segítségével lehetővé válik a gyakorlatban elterjedten használt FIB adatstruktúrák és a tömörített prefix fák teljesítménybeli összevetése.

Munkám második felében a tömörített prefix fák előállításához elengedhetetlen járulékos adastruktúrákat vizsgálom, mely a közös részfák azonosításához szükséges. Javaslatot teszek ezen adatsrtuktúra több lehetséges megvalósítására (tömbök, ring buffer-ek, stb.) és összevetem a javasolt adatstruktúrák lekérdezésének és módosításának elméleti sebességét és memóriaigényét. Elméleti vizsgálódásaimat a szimulátoron szerzett gyakorlati eredményekkel támasztom alá.

Dolgozatom végén összegzem munkám tapasztalatait és felvetem a továbblépés lehetőségeit.

szerző

• 
  Mihálka Bence
  mérnökinformatikus
  nappali

konzulens

• 
  Dr. Rétvári Gábor
  tudományos főmunkatárs, Távközlési és Médiainformatikai Tanszék

helyezés