2, Brno

´ I´ NEJDELSˇ IHO ´ ˇ OPTIMALIZACE VYHLEDAN PREFIXU SI´TOV E´ ˇ ASTE ´ ˇ E´ DYNAMICKE ˇ IM ´ C ´ ADRESY S VYUZIT CN REKONFIGURACE FPGA Jiˇr´ı Matouˇsek V´ypoˇcetn´ı technika a informatika, 1. roˇcn´ık, prezenˇcn´ı studium ˇ Skolitel: Zdenˇek Kot´asek Fakulta informaˇcn´ıch technologi´ı, Vysok´e uˇcen´ı technick´e v Brnˇe Boˇzetˇechova 1/2, 612 66 Brno [email protected] ˇ anek se zab´yv´a optimalizac´ı rychlosti operace vyhled´an´ı nejdelˇs´ıho shodn´eho Abstrakt. Cl´ prefixu pomoc´ı algoritmu Tree Bitmap. Optimalizace jsou navrhov´any tak, aby v maxim´aln´ı moˇzn´e m´ıˇre vyuˇz´ıvaly prostˇredk˚u souˇcasn´ych FPGA cˇ ip˚u. Kromˇe nahrazen´ı extern´ı pamˇeti pomoc´ı Block RAM pamˇeti um´ıstˇen´e pˇr´ımo v FPGA je navrˇzeno tak´e rozdˇelen´ı jednotliv´ych krok˚u algoritmu do samostatn´ych stupˇnu˚ zˇretˇezen´e linky. Pro v´ysledn´e ˇreˇsen´ı je uveden n´avrh hardwarov´e architektury a jsou nast´ınˇeny vlastnosti takto optimalizovan´eho algoritmu. V cˇ l´anku je tak´e obsaˇzena kapitola o smˇeˇrov´an´ı moj´ı disetaˇcn´ı pr´ace. Kl´ıcˇ ov´a slova. LPM, Tree Bitmap, FPGA

´ 1 Uvod Poˇcet zaˇr´ızen´ı pˇripojen´ych k Internetu nar˚ust´a kaˇzd´ym dnem a bˇehem nˇekolika m´alo let se oˇcek´av´a u´ pln´e vyˇcerp´an´ı adresov´eho prostoru protokolu IPv4 (Internet Protocol version 4) [1]. S poˇctem pˇridˇelen´ych IPv4 adres nar˚ust´a tak´e poˇcet z´aznam˚u ve smˇerovac´ıch tabulk´ach router˚u. Nav´ıc doch´az´ı ke zrychlov´an´ı komunikace a napˇr´ıklad pro technologii Ethernet jsou jiˇz standardizov´any pˇrenosov´e rychlosti 40 Gb/s a 100 Gb/s [2]. Oba tyto trendy se nepˇr´ıznivˇe projevuj´ı v poˇzadavc´ıch na vlastnosti router˚u pˇredevˇs´ım v p´ateˇrn´ıch s´ıt´ıch. Nejn´aroˇcnˇejˇs´ı operac´ı v routeru je pˇritom vyhled´an´ı nejdelˇs´ıho shodn´eho prefixu (Longest Prefix Match, LPM) dan´e IP adresy a z´aznam˚u ve smˇerovac´ı tabulce. V p´ateˇrn´ıch routerech je nutn´e nasadit k prov´adˇen´ı t´eto operace specializovan´e hardwarov´e ˇreˇsen´ı, nejˇcastˇeji v podobˇe implementace algoritmu Tree Bitmap [3]. Aˇckoliv je tento algoritmus optimalizov´an tak, aby bˇehem jednoho v´ypoˇcetn´ıho kroku pˇristupoval do pamˇeti pouze jedenkr´at, pro v´ypoˇcet LPM v datab´azi s dlouh´ymi prefixy je typicky potˇreba prov´est nˇekolik v´ypoˇcetn´ıch krok˚u algoritmu. A pr´avˇe pˇr´ıstup do extern´ı pamˇeti je pˇri nasazen´ı hardwarov´eho ˇreˇsen´ı cˇ asovˇe a energeticky nejn´aroˇcnˇejˇs´ı. Hardwarovou implementaci algoritmu lze kromˇe ASIC (Application Specific Integrated Circuit) cˇ ipu prov´est tak´e s vyuˇzit´ım technologie FPGA (Field Programmable Gate Array). V´yhodou FPGA cˇ ip˚u jsou integrovan´e pamˇet’ov´e bloky, kter´e lze vyuˇz´ıt jako intern´ı pamˇet’ a dos´ahnout tak pˇri implementaci algoritmu Tree Bitmap u´ pln´e eliminace extern´ı pamˇeti. Algoritmus lze d´ale urychlit zaveden´ım zˇretˇezen´eho zpracov´an´ı, kter´e je umoˇznˇeno d´ıky distribuovan´e povaze pamˇeti na cˇ ipu FPGA. Pˇri statick´em rozdˇelen´ı pamˇeti mezi jednotliv´e stupnˇe zˇretˇezen´e linky by vˇsak pro pokryt´ı nejhorˇs´ıho moˇzn´eho

pˇr´ıpadu doch´azelo ke znaˇcn´emu pl´ytv´an´ı omezen´ymi pamˇet’ov´ymi zdroji, a proto je vhodn´e zajistit dynamick´e pˇridˇelov´an´ı pamˇeti pomoc´ı cˇ a´ steˇcn´e dynamick´e rekonfigurace FPGA cˇ ipu.

2

Algoritmy LPM

Vstupem LPM algoritmu je dan´a hodnota a sada prefix˚u, typicky r˚uznˇe dlouh´ych. V´ystupem algoritmu je pak nejdelˇs´ı z prefix˚u obsaˇzen´y ve specifikovan´e hodnotˇe. Nejtypiˇctˇejˇs´ı vyuˇzit´ı operace LPM v oblasti poˇc´ıtaˇcov´ych s´ıt´ı pˇredstavuje proces smˇerov´an´ı prov´adˇen´y na routerech. V tomto pˇr´ıpadˇe je vstupn´ı hodnotou c´ılov´a IP adresa paketu a sada prefix˚u je uspoˇra´ d´ana do tzv. smˇerovac´ı tabulky, ve kter´e jednotliv´e z´aznamy obsahuj´ı kromˇe prefix˚u IP adres tak´e informace pro dalˇs´ı smˇerov´an´ı paketu k c´ılov´emu zaˇr´ızen´ı. Pro vz´ajemn´e porovn´an´ı algoritm˚u implementuj´ıc´ıch operaci LPM budeme obdobnˇe jako v [3] pouˇz´ıvat tˇri z´akladn´ı ukazatele: rychlost vyhled´an´ı nejdelˇs´ıho shodn´eho prefixu, pamˇet’ov´e n´aroky vyhled´avac´ıch struktur a rychlost aktualizace vyhled´avac´ıch struktur.

2.1

Algoritmus vyuˇz´ıvaj´ıc´ı jednobitovou trie“ ”

Tento algoritmus lze povaˇzovat za z´aklad vˇsech dalˇs´ıch uveden´ych algoritm˚u. Jejich spoleˇcn´ym znakem je vyuˇzit´ı stromov´e datov´e struktury naz´yvan´e v kontextu LPM algoritm˚u trie (nˇekdy t´ezˇ prefixov´y strom), kter´a slouˇz´ı k vyhled´av´an´ı nejdelˇs´ıho shodn´eho prefixu. Kromˇe zak´odov´an´ı prohled´avan´e mnoˇziny prefix˚u pˇr´ımo do struktury trie lze na obr´azku 1 pozorovat tak´e korespondenci t´eto datov´e struktury s bin´arn´ım stromem, pˇriˇcemˇz jednotliv´e bity vstupn´ı hodnoty urˇcuj´ı, zda bude pr˚uchod stromem pokraˇcovat v lev´em nebo prav´em podstromu aktu´aln´ıho uzlu. Bin´arn´ı k´od vstupn´ı hodnoty tedy ud´av´a cestu stromem a posledn´ı prefix na t´eto cestˇe ve smˇeru od koˇrene k list˚um je hledan´ym nejdelˇs´ım shodn´ym prefixem.

Obr´azek 1: Reprezentace uk´azkov´e mnoˇziny prefix˚u jednobitovou trie“ ” Implementace operace LPM vyuˇz´ıvaj´ıc´ı jednobitovou trie“ vynikaj´ı pˇredevˇs´ım rychlost´ı aktualizac´ı. ” Pˇri pouˇzit´ı kompresn´ıch metod je i pamˇet’ov´a n´aroˇcnost algoritm˚u n´ızk´a. Z´asadn´ım probl´emem tohoto pˇr´ıstupu je vˇsak rychlost vyhled´av´an´ı, protoˇze v nejhorˇs´ım pˇr´ıpadˇe odpov´ıd´a poˇcet krok˚u algoritmu poˇctu bit˚u vstupn´ıho slova.

2.2

Algoritmus Lulea

Z´akladn´ım rozd´ılem algoritmu Lulea [4] oproti pˇr´ıstupu s jednobitovou trie“ je zpracov´an´ı nˇekolika ” bit˚u vstupn´ıho slova v jedin´em kroku. Oznaˇcme poˇcet bit˚u zpracov´avan´ych v jedin´em kroku jako SL (z anglick´eho term´ınu stride length). Vyhled´avac´ı datov´a struktura je pot´e tvoˇrena 2SL -arn´ım stromem, jehoˇz uzly obsahuj´ı kromˇe informac´ı o sadˇe prefix˚u tak´e informace usnadˇnuj´ıc´ı vyhled´an´ı nejdelˇs´ıho shodn´eho prefixu v t´eto datov´e struktuˇre.

Reprezentace uzlu stromu v algoritmu Lulea je navrˇzena tak, aby jej´ı pamˇet’ov´e n´aroky byly co nejmenˇs´ı. Za t´ımto u´ cˇ elem je vyuˇzita tzv. technika leaf pushing“, pˇri kter´e se v uzlu stromu zachov´av´a ” nam´ısto oddˇelen´ych informac´ı o prefixech a ukazatel´ıch na dalˇs´ı uzly stromu jen v´ybˇer z tˇechto informac´ı (pro kaˇzdou kombinaci hodnot zpracov´avan´ych bit˚u bud’ jen ukazatel nebo informace o prefixu), pˇriˇcemˇz zb´yvaj´ıc´ı hodnoty jsou ve stromu odsouv´any na voln´e pozice smˇerem k jeho list˚um. Pˇri vyuˇzit´ı t´eto techniky lze sn´ızˇ it pamˇet’ov´e n´aroky algoritmu pˇribliˇznˇe na polovinu. Algoritmus Lulea umoˇznˇ uje d´ıky zpracov´an´ı v´ıce bit˚u vstupn´ıho slova najednou rychlejˇs´ı vyhled´an´ı nejdelˇs´ıho shodn´eho prefixu. Jak jiˇz bylo naznaˇceno v´ysˇe, struktura uzlu vyhled´avac´ı datov´e struktury je pro tento algoritmus optimalizovan´a na co nejmenˇs´ı spotˇrebu pamˇeti, takˇze i v tomto ukazateli vykazuje Lulea dobr´e v´ysledky. Probl´emov´ym parametrem je vˇsak rychlost aktualizace stromu, pˇri kter´e m˚uzˇ e b´yt v nejhorˇs´ım pˇr´ıpadˇe ovlivnˇena aˇz polovina vˇsech jeho uzl˚u, coˇz zp˚usobuje technika leaf pushing“. ”

2.3

Algoritmus Tree Bitmap

C´ılem n´avrhu algoritmu Tree Bitmap [3] bylo zachovat co nejv´ıce z pozitivn´ıch vlastnost´ı Lulea algoritmu a z´aroveˇn vylepˇsit algoritmus z pohledu cˇ asu potˇrebn´eho k proveden´ı aktualizace vyhled´avac´ı stromov´e datov´e struktury. Nam´ısto techniky leaf pushing“ se tak v uzlech stromu algoritmu Tree Bitmap ” objevuje dalˇs´ı bitmapa, kter´a spoleˇcnˇe s jedn´ım odkazem na zaˇca´ tek pole synovsk´ych uzl˚u umoˇznˇ uje uchov´avat v uzlu stromu jak informace o prefixech, tak informace o odkazech na potomky. Aˇckoliv je celkov´a pamˇet’ov´a n´aroˇcnost tohoto algoritmu v porovn´an´ı s algoritmem Lulea ponˇekud horˇs´ı, uzly stromu maj´ı u Tree Bitmap menˇs´ı velikost a tato velikost je konstantn´ı. D´ıky tomu je moˇzn´e naˇc´ıst cel´y uzel z extern´ı pamˇeti v jedin´em kroku a i pro stejnou hodnotu SL tak dosahovat rychlejˇs´ıho vyhled´an´ı nejdelˇs´ıho shodn´eho prefixu, neˇz u algoritmu Lulea. Algoritmus Tree Bitmap tedy dosahuje oproti algoritmu Lulea v´yrazn´eho vylepˇsen´ı cˇ asu potˇrebn´eho pro aktualizaci trie a d´ıky zmenˇsen´ı poˇctu pˇr´ıstup˚u do pamˇeti tak´e urychlen´ı vyhled´an´ı nejdelˇs´ıho spoleˇcn´eho prefixu. Cenou za tato vylepˇsen´ı je vyˇssˇ´ı pamˇet’ov´a sloˇzitost algoritmu. Celkovˇe vˇsak dosahuje algoritmus Tree Bitmap vyv´azˇ en´eho v´ykonu ve vˇsech tˇrech sledovan´ych ukazatel´ıch a je v souˇcasnosti jedn´ım z nejpouˇz´ıvanˇejˇs´ıch.

3

Optimalizace LPM algoritmu Tree Bitmap

Poˇcet pˇr´ıstup˚u algoritmu Tree Bitmap do pamˇeti je v nejhorˇs´ım pˇr´ıpadˇe d´an vztahem 

d´elka vstupn´ıho slova +1 SL 

(1)

V cˇ l´anku [3], kde je algoritmus Tree Bitmap pˇredstaven, nav´ıc autoˇri zmiˇnuj´ı, zˇ e sami nenastavuj´ı parametr SL na hodnotu vˇetˇs´ı neˇz 8 a pro 32bitovou IPv4 adresu tedy m˚uzˇ e b´yt potˇreba pˇristoupit do pamˇeti aˇz pˇetkr´at. Nahrazen´ım extern´ı pamˇeti pomoc´ı pamˇeti na cˇ ipu FPGA lze tud´ızˇ dos´ahnout jednak dalˇs´ıho urychlen´ı operace LPM a nav´ıc tak´e energetick´e u´ spory. Zda je v˚ubec moˇzn´e pˇresunout veˇsker´e vyhled´avac´ı datov´e struktury algoritmu Tree Bitmap z extern´ı pamˇeti do pamˇeti na cˇ ipu FPGA ukazuj´ı tabulky 1 a 2. V prvn´ı z nich jsou uvedeny hodnoty dostupn´e pamˇeti na nˇekter´ych rodin´ach FPGA cˇ ip˚u firmy Xilinx, jak je uv´ad´ı v´yrobce v [7] a [8]. Kromˇe celkov´e dostupn´e pamˇeti obsahuje tabulka tak´e informaci o tom, do kolika Block RAM blok˚u je dostupn´a pamˇet’ rozdˇelena (kaˇzd´y blok obsahuje 36 Kb pamˇeti). Rozsah hodnot na jednotliv´ych ˇra´ dc´ıch pak ud´av´a rozsah pˇr´ısluˇsn´ych parametr˚u pro r˚uzn´e varianty cˇ ip˚u dan´e rodiny. Hlavn´ı n´apln´ı druh´e tabulky jsou pamˇet’ov´e n´aroky na reprezentaci dvou re´alnˇe pouˇz´ıvan´ych prefixov´ych sad datov´ymi strukturami algoritmu Tree Bitmap pˇri cˇ tyˇrech r˚uzn´ych hodnot´ach parametru SL. Tyto hodnoty byly pro potˇreby tohoto cˇ l´anku zmˇeˇreny pomoc´ı n´astroje Netbench [6] a u kaˇzd´e prefixov´e sady je uveden tak´e u´ daj o jej´ı velikosti. Jak je z hodnot v tabulk´ach 1 a 2 patrn´e, pˇri vhodn´e volbˇe

Tabulka 1: Pˇrehled dostupn´e Block RAM pamˇeti v r˚uzn´ych rodin´ach FPGA firmy Xilinx (viz [7, 8]) Rodina FPGA Dostupn´a pamˇet’ [Kb] Block RAM bloku˚ Virtex-5 LXT 936-11 664 26-324 Virtex-5 LX 1 152-10 368 32-288 Virtex-5 FXT 2 448-16 416 68-456 Virtex-5 SXT 3 024-18 576 84-516 Virtex-5 TXT 8 208-11 664 228-324 Virtex-6 LXT 5 616-25 920 156-720 Virtex-6 HXT 18 144-32 832 504-912 Virtex-6 SXT 25 344-38 304 704-1 064

Tabulka 2: Pamˇet’ov´e n´aroky reprezentace prefixov´ych sad v algoritmu Tree Bitmap Pamˇet’ov´a n´aroˇcnost [Kb] Prefixov´a sada Poˇcet prefixu˚ SL=3 SL=4 SL=5 SL=8 1 IPv4-space 231 712 9 047,470 10 318,393 5 933,388 56 648,033 AS2.02 416 703 33 276,393 38 330,674 32 042,546 197 934,766

parametru SL je moˇzn´e v intern´ı pamˇeti FPGA reprezentovat i prefixovou sadu obsahuj´ıc´ı v´ıce neˇz 416 tis´ıc poloˇzek. Kromˇe pˇresunu vyhled´avac´ıch datov´ych struktur do intern´ı pamˇeti na cˇ ipu FPGA je moˇzn´e rychlost vyhled´an´ı nejdelˇs´ıho shodn´eho prefixu zv´ysˇit jeˇstˇe zaveden´ım zˇretˇezen´eho zpracov´an´ı, kdy je kaˇzd´y krok algoritmu Tree Bitmap, vˇcetnˇe z´avˇereˇcn´eho pˇr´ıstupu do pamˇeti pro smˇerovac´ı informaci pˇr´ısluˇsej´ıc´ı nejdelˇs´ımu shodn´emu prefixu, prov´adˇen samostatnou v´ypoˇcetn´ı jednotkou v oddˇelen´em stupni zˇretˇezen´e linky. Toto rozˇs´ıˇren´ı je umoˇznˇeno distribuovanou povahou intern´ı pamˇeti FPGA cˇ ipu, takˇze kaˇzd´emu z v´ypoˇcetn´ıch stupˇnu˚ zˇretˇezen´e linky m˚uzˇ e b´yt pˇridˇelena samostatn´a pamˇet’. Pˇr´ıstup do pamˇet’ov´eho bloku je pak povolen jen odpov´ıdaj´ıc´ımu v´ypoˇcetn´ımu stupni algoritmu Tree Bitmap a jednotce v posledn´ım stupni linky, kter´a zajiˇst’uje vyˇcten´ı smˇerovac´ı informace pˇr´ısluˇsej´ıc´ı nejdelˇs´ımu shodn´emu prefixu. Tento dvojit´y pˇr´ıstup lze zajistit d´ıky dvˇema vstupnˇe-v´ystupn´ım port˚um kaˇzd´eho z Block RAM blok˚u. Sch´ema na obr´azku 2 zn´azorˇnuje hardwarovou realizaci algoritmu Tree Bitmap s aplikovan´ymi v´ysˇe popsan´ymi vylepˇsen´ımi. Bloky TBM i“ a pamˇet’ i“ pro i ∈ 1, 2, ..., n spoleˇcnˇe tvoˇr´ı vˇzdy jeden stupeˇn ” ” zˇretˇezen´e linky a posledn´ı stupeˇn obsahuje pouze blok vyˇcten´ı smˇerovac´ı informace“. ”

Obr´azek 2: Sch´ema hardwarov´e realizace optimalizovan´eho Tree Bitmap algoritmu

Souˇca´ st´ı sch´ematu na obr´azku 2 nen´ı ˇradiˇc cˇ a´ steˇcn´e dynamick´e rekonfigurace a konfiguraˇcn´ı rozhran´ı ´ ICAP (Internal Configuration Access Port), aˇckoliv se s jejich vyuˇzit´ım poˇc´ıt´a. Ukolem tˇechto jednotek je zajistit s vyuˇzit´ım cˇ a´ steˇcn´e dynamick´e rekonfigurace pr˚ubˇezˇ nou adaptaci kapacity pamˇet’ov´ych blok˚u pˇriˇrazen´ych jednotliv´ym stupˇnum zˇretˇezen´e linky podle aktu´aln´ıch potˇreb algoritmu. Pokud bychom totiˇz urˇcovali velikost jednotliv´ych pamˇet’ov´ych blok˚u staticky, doch´azelo by k pl´ytv´an´ı s jiˇz tak omezen´ym mnoˇzstv´ım pamˇeti na cˇ ipu FPGA. Pamˇet’ovou rezervu bychom totiˇz museli zajistit pro kaˇzd´y blok zvl´asˇt’, nam´ısto spoleˇcn´e pamˇet’ov´e rezervy v pˇr´ıpadˇe vyuˇzit´ı jedn´e pamˇeti pro vˇsechny cˇ a´ sti algoritmu.

3.1

Vlastnosti optimalizovan´eho algoritmu

Popsan´e optimalizace hardwarov´e implementace algoritmu Tree Bitmap s vyuˇzit´ım technologie FPGA byly navrˇzeny s c´ılem urychlit operaci LPM. Optimalizovan´y algoritmus je teoreticky schopn´y dos´ahnout v kaˇzd´em taktu vyhled´an´ı nejdelˇs´ıho shodn´eho prefixu pro jin´e vstupn´ı slovo. Pamˇet’ov´a n´aroˇcnost p˚uvodn´ıho algoritmu z˚ustala zachov´ana, pˇriˇcemˇz k zabr´anˇen´ı pl´ytv´an´ı s pamˇet´ı rozdˇelenou do jednotliv´ych stupˇnu˚ zˇretˇezen´e linky je vyuˇzita cˇ a´ steˇcn´a dynamick´a rekonfigurace FPGA. Navrˇzen´e optimalizace rychlosti operace LPM se pozitivnˇe projevuj´ı tak´e v rychlosti prov´adˇen´ı aktualizac´ı vyhled´avac´ıch datov´ych struktur. Aˇckoliv m˚uzˇ e b´yt aktualizace zdrˇzena proveden´ım cˇ a´ steˇcn´e dynamick´e rekonfigurace, eliminuje se toto zdrˇzen´ı v´yrazn´ym zrychlen´ım pˇr´ıstupu k aktualizovan´e pamˇeti. D´ıky zˇretˇezen´emu zpracov´an´ı nav´ıc m˚uzˇ e prob´ıhat aktualizace datov´ych struktur paralelnˇe s vyhled´av´an´ım nejdelˇs´ıho shodn´eho prefixu.

3.2

Vyuˇzitelnost optimalizovan´eho algoritmu

Jelikoˇz prozat´ım nebyla provedena hardwarov´a implementace navrˇzen´ych optimalizac´ı Tree Bitmap algoritmu, je tˇreba jeˇstˇe vyˇckat na experiment´aln´ı ovˇeˇren´ı vlastnost´ı popsan´ych v pˇredchoz´ı podkapitole. Pokud by se vˇsak popisovan´e vlastnosti potvrdily, mohla by optimalizovan´a hardwarov´a implementace algoritmu Tree Bitmap nal´ezt d´ıky podporovan´e rychlosti prov´adˇen´ı operace LPM uplatnˇen´ı v p´ateˇrn´ıch smˇerovaˇc´ıch zajiˇst’uj´ıc´ıch smˇerov´an´ı pˇri pˇrenosov´ych rychlostech v ˇra´ du des´ıtek aˇz stovek Gb/s. Nev´yhodou ˇreˇsen´ı je omezen´e mnoˇzstv´ı pamˇeti dostupn´e na cˇ ipu FPGA, kter´e nav´ıc nelze pro konkr´etn´ı cˇ ip nijak navyˇsovat. V nejnovˇejˇs´ıch FPGA firmy Xilinx (viz [9]) je vˇsak opˇet mnoˇzstv´ı dostupn´e intern´ı pamˇeti vˇetˇs´ı, neˇz u rodin popsan´ych v tabulce 1.

Smˇerˇ ov´an´ı disertaˇcn´ı pr´ace

4

T´ematem moj´ı disertaˇcn´ı pr´ace je vyuˇzit´ı rekonfigurovateln´ych obvod˚u v oblasti poˇc´ıtaˇcov´ych s´ıt´ı. V r´amci tohoto t´ematu bych se chtˇel zab´yvat pˇredevˇs´ım pouˇzit´ım cˇ a´ steˇcn´e dynamick´e rekonfigurace FPGA pro adaptivn´ı akceleraci v´ypoˇcetnˇe n´aroˇcn´ych operac´ı z oblasti poˇc´ıtaˇcov´ych s´ıt´ı (LPM, vyhled´av´an´ı vzor˚u, klasifikace paket˚u, anal´yza hlaviˇcek paket˚u) v z´avislosti na zat´ızˇ en´ı v´ypoˇcetn´ı jednotky (typicky obecn´y procesor) prov´adˇej´ıc´ı danou operaci. V r´amci disertace tedy bude nutn´e ˇreˇsit pˇredevˇs´ım u´ lohy z oblasti pl´anov´an´ı a mapov´an´ı s´ıt’ov´ych operac´ı do FPGA. Postupy navrhovan´e v r´amci disertace by mˇely b´yt prakticky ovˇeˇrov´any pˇri v´yvoji API (Application Programming Interface), kter´e by uˇzivateli umoˇznˇ ovalo starat se pouze o softwarovou cˇ a´ st s´ıt’ov´e aplikace, pˇriˇcemˇz vybran´e operace by byly v pˇr´ıpadˇe potˇreby akcelerov´any v rekonfigurovateln´em hardware a tato akcelerace by prob´ıhala plnˇe v reˇzii API, transparentnˇe v˚ucˇ i uˇzivateli. C´ılovou platformou pro uvaˇzovan´e API tedy mus´ı b´yt syst´em s obecn´ym procesorem a rekonfigurovatelnou logikou, pˇriˇcemˇz aktu´alnˇe se jako nejvhodnˇejˇs´ı jev´ı platforma Xilinx Zynq-7000 EPP [5]. 1 2

z´ısk´ano z http://bgp.potaroo.net/ipv4-stats/prefixes.txt z´ısk´ano z http://bgp.potaroo.net/as2.0/bgptable.txt

5

Z´avˇer

Tento cˇ l´anek se zab´yv´a urychlen´ım operace vyhled´an´ı nejdelˇs´ıho shodn´eho prefixu, pˇriˇcemˇz je vych´azeno z algoritmu Tree Bitmap a k jeho urychlen´ı jsou vyuˇz´ıv´any prostˇredky poskytovan´e souˇcasn´ymi FPGA cˇ ipy. Prvn´ı navrˇzenou optimalizac´ı algoritmu je eliminace extern´ı pamˇeti a jej´ı nahrazen´ı pamˇet´ı typu Block RAM, kter´a je pˇr´ımo souˇca´ st´ı FPGA cˇ ipu. Vedlejˇs´ım efektem eliminace extern´ı pamˇeti je i energetick´a u´ spora. Druh´a optimalizace spoˇc´ıv´a v rozdˇelen´ı jednotliv´ych krok˚u algoritmu do samostatn´ych stupˇnu˚ zˇretˇezen´e linky. Takov´a optimalizace pˇritom vyˇzaduje vlastn´ı pamˇet’ov´y blok pro kaˇzd´y krok v´ypoˇctu. Tento poˇzadavek je vyˇreˇsen d´ıky distribuovan´e povaze Block RAM pamˇeti. Myˇslenky vztahuj´ıc´ı se k optimalizaci algoritmu Tree Bitmap jsou v cˇ l´anku doplnˇeny tak´e n´avrhem hardwarov´e architektury takto optimalizovan´eho algoritmu a jsou pops´any pˇredpokl´adan´e vlastnosti v´ysledn´eho ˇreˇsen´ı. Jelikoˇz vˇsak navrˇzen´a architektura nebyla prozat´ım implementov´ana, nelze tyto pˇredpoklady podloˇzit experiment´aln´ımi v´ysledky. Implementov´an´ı optimalizovan´e verze algoritmu a experiment´aln´ı ovˇeˇren´ı jeho vlastnost´ı je tak jasn´ym c´ılem pro budouc´ı pr´aci na tomto t´ematu. Pˇredposledn´ı kapitola je vˇenov´ana popisu smˇeˇrov´an´ı moj´ı disertaˇcn´ı pr´ace, pˇriˇcemˇz hlavn´ı t´ema tohoto cˇ l´anku pˇredstavuje prvn´ı krok na cestˇe k c´ıli vytyˇcen´emu v r´amci disertace.

Podˇekov´an´ı Tato pr´ace byla podpoˇrena Evropsk´ym fondem region´aln´ıho rozvoje (ERDF) v r´amci projektu Centra excelence IT4Innovations (CZ.1.05/1.1.00/02.0070) a cˇ a´ steˇcnˇe tak´e grantem FIT-S-11-1 – Pokroˇcil´e bezpeˇcn´e, spolehliv´e a adaptivn´ı IT.

Reference [1] INTEC Inc.: IPv4 Exhaustion Counter (English) [online]. September 2011. Available at URL: http://inetcore.com/project/ipv4ec/index_en.html (June 2012). [2] IEEE Computer Society: Part 3: Carrier Sense Multiple Access with Collision Detection (CSMA/CD) Access Method and Physical Layer Specifications; Amendment 4: Media Access Control Parameters, Physical Layers, and Management Parameters for 40 Gb/s and 100 Gb/s Operation. IEEE std 802.3ba-2010, June 2010. ISBN 978-0-7381-6322-2. [3] W. Eatherton, G. Varghese, and Z. Dittia: Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates. ACM SIGCOMM Computer Communications Review, 34(2): 97–122, 2004. [4] M. Degermark, A. Brodnik, S. Carlsson, and S. Pink: Small Forwarding Tables for Fast Routing Lookups. In Proceedings of the ACM SIGCOMM ’97, September 1997, pp. 3–14. [5] Xilinx, Inc.: Xilinx Zynq-7000 Extensible Processing Platform [online]. June 2012. Available at URL: http://www.xilinx.com/products/silicon-devices/epp/zynq-7000/ (June 2012). [6] V. Puˇs, J. Tobola, J. Kaˇstil, V. Koˇsaˇr, and J. Koˇrenek: Netbench - the Framework for Evaluation of Packet Processing Algorithms. In Proceedings of the 7th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, 2011, pp. 95–96. ISBN 978-0-7695-4521-9. [7] Xilinx, Inc.: Virtex-5 Family Overview. DS100 (v5.0), February 2009. [8] Xilinx, Inc.: Virtex-6 Family Overview. DS150 (v2.4), January 2012. [9] Xilinx, Inc.: 7 Series FPGAs Overview. DS180 (v1.11), May 2012.