Hardver által támogatott címkeresési algoritmusok tervezése és verifikálása

OData támogatás
Konzulens:
Horváth Dániel
Távközlési és Médiainformatikai Tanszék

A számítógépes hálózatok egyre több szerepet kapnak a mai mindennapi életben. Egyre több alkalmazás jelenik meg egyre több hálózati kapacitást igényelve. A hálózati eszközök gyakran használnak specializált hardver modulokat az adatok továbbítására. Ezek a modulok felgyorsíthatják a továbbítás folyamatát a szoftveres feldolgozáshoz képest, illetve csökkentik a csomagok késleltetését, az időt, amit a hálózati eszközben eltöltenek. Ezek a hardverek általában továbbítási táblákban keresnek információt egy adott csomag kimenő port-jára vonatkozóan. Ezek a továbbítási táblák különböző memóriákban lehetnek: TCAM, SD RAM illetve DDR RAM -okban. A címkeresés teljesítményét definiálhatjuk a szükséges memória hozzáférések számával. Ez a teljesítmény nagyban függ a használt keresési algoritmustól.

Ebben a dokumentumban szólni fogok a manapság használt hálózat típusokról. Beszélek a hozzáférési hálózat és gerinchálózat különbségeiről. Megemlítek különböző protokoll technológiákat, mint például az Ethernet, Internet Protokoll, illetve a Multiprotocol Label Switching. Bemutatok négy különböző címkeresési algoritmust: a Naiv algoritmust, a Bináris algoritmust, a Hash-vödrös algoritmust, illetve a Bloom Filter algoritmust. Utóbbi kettő a memóriát részekre osztó algoritmus, melyek hash függvényeket és „hash-vödröket” használnak. Ezután megtervezem az algoritmusokat egy adott környezetre Ethernet továbbítási protokollt használva. Bemutatom az implementációm körüli környezetet, és az ahhoz kapcsolódó interfészeket. Minden algoritmushoz definiálok egy címbejegyzés formátumot, valamint leírom az architektúrához módosított folyamatábrákat. A tervet implementálom SystemC nyelven. Szimulációkkal megmutatom, hogy a naiv algoritmus O(n), a bináris algoritmus O(log(n)), illetve a Hash alapú és a Bloom Filter pedig O(c) azaz konstans számú memória hozzáférést igényel. Megfigyeltem, hogy a Bloom filternek előnye, hogy jobban szétszórja a címbejegyzéseket a továbbítási táblában, így jobban támogatja az ütközés elkerülést. Hátrányát is vizsgáltam, miszerint a Bloom Filter több memória hozzáférést igényel címbejegyzések inkrementális beillesztése esetén.

Letölthető fájlok

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