|
Algoritmy pro vyhledání nejdelšího shodného prefixu
Skačan, Martin ; Puš, Viktor (oponent) ; Tobola, Jiří (vedoucí práce)
Tato práce se zabývá algoritmy pro vyhledání nejdelšího shodného prefixu (longest prefix match - LPM), což je klíčová operace při klasifikaci paketů a směrování v počítačových IP sítích. Je uvedena potřebná teorie a rozbor vybraných algoritmů - Trie, Tree Bitmap, Shape Shifting Tree a Multi-Match. Tyto metody byly detailně popsány a implementovány v programovacím jazyce Python. Nad implementovanými algoritmy byly provedeny testy a simulace pro určení jejich praktických paměťových nároků s cílem identifikovat nejvhodnější metodu pro množiny prefixů o velikosti desítek až tisíců pravidel.
|
|
Vyhledávání nejdelšího shodného prefixu ve vysokorychlostních sítích
Skačan, Martin ; Tobola, Jiří (oponent) ; Kořenek, Jan (vedoucí práce)
Tato práce se zabývá vyhledáváním nejdelšího shodného prefixu (LPM), což je časově kritická operace při směrování paketů. Pro dosažení propustnosti 100Gbps je nutná hardwarová implementace této operace a směrovací tabulka musí být uložena v paměti na čipu, která je omezena nízkou kapacitou. Současné LPM algoritmy vyžadují velké množství paměti pro uložení směrovacích tabulek protokolu IPv6, nebo je není možno jednoduše implementovat v HW. Proto jsem se zaměřil na analýzu směrovacích tabulek IPv6 a několika známých LPM algoritmů. Na základě této analýzy jsem navrhl nový algoritmus, který vyniká nízkou paměťovou složitostí pro IPv4/IPv6 vyhledávání. Navržený algoritmus má nejnižší paměťové nároky v porovnání s existujícími LPM algoritmy. Navíc je vhodný pro nasazení ve vysokorychlostních 100Gbps sítích, což bylo ukázáno s pomocí nové hardwarové architektury využívající zřetězené zpracování s propustností 140Gbps.
|
|
Algoritmy pro vyhledání nejdelšího shodného prefixu
Skačan, Martin ; Puš, Viktor (oponent) ; Tobola, Jiří (vedoucí práce)
Tato práce se zabývá algoritmy pro vyhledání nejdelšího shodného prefixu (longest prefix match - LPM), což je klíčová operace při klasifikaci paketů a směrování v počítačových IP sítích. Je uvedena potřebná teorie a rozbor vybraných algoritmů - Trie, Tree Bitmap, Shape Shifting Tree a Multi-Match. Tyto metody byly detailně popsány a implementovány v programovacím jazyce Python. Nad implementovanými algoritmy byly provedeny testy a simulace pro určení jejich praktických paměťových nároků s cílem identifikovat nejvhodnější metodu pro množiny prefixů o velikosti desítek až tisíců pravidel.
|
|
Vyhledávání nejdelšího shodného prefixu ve vysokorychlostních sítích
Skačan, Martin ; Tobola, Jiří (oponent) ; Kořenek, Jan (vedoucí práce)
Tato práce se zabývá vyhledáváním nejdelšího shodného prefixu (LPM), což je časově kritická operace při směrování paketů. Pro dosažení propustnosti 100Gbps je nutná hardwarová implementace této operace a směrovací tabulka musí být uložena v paměti na čipu, která je omezena nízkou kapacitou. Současné LPM algoritmy vyžadují velké množství paměti pro uložení směrovacích tabulek protokolu IPv6, nebo je není možno jednoduše implementovat v HW. Proto jsem se zaměřil na analýzu směrovacích tabulek IPv6 a několika známých LPM algoritmů. Na základě této analýzy jsem navrhl nový algoritmus, který vyniká nízkou paměťovou složitostí pro IPv4/IPv6 vyhledávání. Navržený algoritmus má nejnižší paměťové nároky v porovnání s existujícími LPM algoritmy. Navíc je vhodný pro nasazení ve vysokorychlostních 100Gbps sítích, což bylo ukázáno s pomocí nové hardwarové architektury využívající zřetězené zpracování s propustností 140Gbps.
|