Addressing Issues in Research on Packet Classification in Core Networks

Řešení problémů ve výzkumu klasifikace paketů v páteřních sítích

Ačkoliv se Internet od počátku 21. století znatelně proměnil, klasifikace paketů je stále jednou z nejběžnějších operací implementovaných v síťových zařízeních. Požadavky na její výkonnost však neustále narůstají, zvláště pak v oblasti páteřních sítí, kde musejí současné klasifikační algoritmy podporovat propustnost 100 Gb/s. Navíc dochází i k nárůstu počtu používaných klasifikačních pravidel a v souvislosti se zavedením 128bitových adres v protokolu IPv6 a klasifikace paketů založené na více než 5 položkách v protokolu OpenFlow se také zvyšuje počet bitů majících vliv na výsledek procesu klasifikace. Většina současného výzkumu v oblasti klasifikace paketů v páteřních sítích se proto zaměřuje na zvyšování výkonnosti klasifikačních algoritmů, které musejí držet krok s neustále narůstajícími požadavky. Výzkumníci se však také věnují měření výkonnostních parametrů nově vyvinutých klasifikačních algoritmů, respektive generování vhodných syntetických sad klasifikačních pravidel pro tato měření, protože reálné sady pravidel nejsou pro většinu oblastí, v nichž se klasifikace paketů používá, dostupné. Tato práce se zaměřuje na obě uvedené oblasti, protože je nutné nejen vyvíjet klasifikační algoritmy s vysokou výkonností, ale také ověřovat jejich výkonnostní parametry s využitím vhodných datových sad.

V oblasti výkonnosti klasifikačních algoritmů se tato práce věnuje především úloze vyhledávání shodných prefixů, která je součástí většiny jednodimenzionálních i vícedimenzionálních klasifikačních algoritmů. Jelikož softwarová implementace vyhledávání shodných prefixů nemůže dostát požadavkům na klasifikaci paketů v páteřních sítích, tato práce navrhuje implementaci dané úlohy pomocí zřetězené architektury určené pro FPGA čipy firmy Xilinx a využívající distribuovaných paměťových bloků dostupných na těchto čipech. Kromě toho je v této práci navržena i paměťově efektivní reprezentace sady prefixů založená na binárním prefixovém stromu (tzv. trie), která umožňuje uložit celou datovou strukturu potřebnou pro vyhledávání shodných prefixů do paměti na FPGA čipu. Navržená reprezentace prefixové sady je s ohledem na paměťové nároky efektivnější než reprezentace používané ve známých vícebitových trie Tree Bitmap a Shape Shifting Trie a v případě IPv4 prefixů také výrazně překonává reprezentaci používanou algoritmem Prefix Partitioning. Samotná architektura pro vyhledávání shodných prefixů pak sestává ze dvou zřetězených linek využívajících oba dva porty paměťových bloků dostupných na FPGA čipu, které jsou dohromady schopné provést téměř 255 milionů vyhledání za sekundu, což pro nejkratší rámce protokolu Ethernet znamená propustnost 170 Gb/s.

Pro podporu realistického měření výkonnostních parametrů klasifikačních algoritmů představuje tato práce nový volně dostupný generátor syntetických sad klasifikačních pravidel nazývaný ClassBench-ng, který umožňuje generování IPv4, IPv6 a OpenFlow 1.0.0 pravidel, jejichž statistické vlastnosti odpovídají rozložením popsaným ve vstupním souboru parametrů. Kromě generování syntetických klasifikačních pravidel podporuje tento nástroj také analýzu reálných pravidlových sad ve formátu ovs-ofctl, jejímž výstupem je odpovídající soubor parametrů, který může být později použit pro generování podobné syntetické sady pravidel. Výzkumníci mající přístup k reálným sadám klasifikačních pravidel tudíž mohou sdílet svá testovací data s ostatními členy výzkumné komunity prostřednictvím souborů parametrů vytvořených nástrojem ClassBench-ng, které popisují pouze statistické vlastnosti původních pravidlových sad, a tudíž zachovávají jejich anonymitu. S ohledem na přesnost generování syntetických sad klasifikačních pravidel dosahuje nástroj ClassBench-ng lepších průměrných výsledků než nástroje ClassBench a FRuG v případě IPv4 prefixů a než nástroj Non-random Generator v případě IPv6 prefixů. Generování syntetických sad OpenFlow pravidel je pak v tomto nástroji přesnější než v nástroji FRuG.

Klasifikace paketů, páteřní sítě, vyhledávání shodných prefixů, FPGA, OpenFlow, ClassBench-ng.

MATOUŠEK, Jiří. Addressing Issues in Research on Packet Classification in Core Networks. Brno, 2018. Disertační práce. Vysoké učení technické v Brně, Fakulta informačních technologií. 2019-04-12. Vedoucí práce Kořenek Jan. Dostupné z: https://www.fit.vut.cz/study/phd-thesis/642/