Tato pr´ace vznikla za podpory projektu TeamIt, jenˇz je spolufinancov´an Evropsk´ym soci´aln´ım fondem a ˇ e republiky prostˇrednictv´ım grantu ESF CZ.1.07/2.3.00/09.0067. st´atn´ım rozpoˇctem Cesk´
´n´ı konkurenceschopny ´ch vy ´zkumny ´ch ty ´m˚ Budova u pro IT
V´yzkumn´a skupina ANT at FIT:
Hardwarov´a akcelerace klasifikace paket˚ u Technick´a zpr´ava 10.kvˇetna 2010
ˇ ´ICH TECHNOLOGI´I VUT V BRNE ˇ FAKULTA INFORMACN Boˇzetˇechova 2, 612 66 Brno tel.: +420 541 141 144, +420 541 212 219, fax: +420 541 141 170, 270 http://www.fit.vutbr.cz, http://teamit.fit.vutbr.cz
´ Uvod
1
Klasifikace paket˚ u je u ´loha, na kterou lze pohl´ıˇzet jako na geometrick´y, anebo kombinatorick´y matematick´y probl´em. Z´aroveˇ n vˇsak praktick´e ˇreˇsen´ı t´eto u ´lohy m´a velk´y dopad v mnoha aplikac´ıch poˇc´ıtaˇcov´ych s´ıt´ı. V souˇcasnosti existuje mnoho pˇr´ıstup˚ u ke klasifikaci paket˚ u, avˇsak kaˇzd´y z nich m´a nˇekter´e nev´yhody. Nˇekter´a ˇreˇsen´ı jsou vhodn´a pouze pro softwarovou implementaci, novˇejˇs´ı pr´ace vˇsak jiˇz pˇredpokl´adaj´ı vyuˇzit´ı specializovan´ych technick´ych prostˇredk˚ u pro dosaˇzen´ı vysok´eho v´ykonu. Zat´ımco pouˇzit´ı software nebo hardware je sp´ıˇse implementaˇcn´ı ot´azkou, mnohem d˚ uleˇzitejˇs´ı je anal´yza algoritm˚ u z teoretick´eho pohledu. Pˇri pr´aci s klasifikaˇcn´ımi algoritmy je d˚ uleˇzit´a pˇredevˇs´ım ˇcasov´a a prostorov´a sloˇzitost. Z d˚ uvod˚ u popsan´ych d´ale dˇel´ıme ˇcasovou sloˇzitost popsan´ych algoritm˚ u na sloˇzitost vyhled´an´ı, a sloˇzitost vytvoˇren´ı datov´ych struktur.
2
Teoretick´ y rozbor
2.1
Model klasifikace
Klasifikaˇcn´ı algoritmus m´a k dispozici mnoˇzinu pravidel uspoˇr´adanou podle priority. Vstupem algoritmu jsou hodnoty z hlaviˇcky paketu. Klasifikaˇcn´ı algoritmus mus´ı prov´est hled´an´ı, jehoˇz v´ysledkem je pravidlo, kter´e odpov´ıd´a dan´emu paketu. Pokud paketu odpov´ıd´a v´ıce pravidel, potom je z nich vybr´ano pravidlo s nejvyˇsˇs´ı prioritou. V´ystupem klasifikace je ˇc´ıslo v´ysledn´eho pravidla.
2.2
Klasifikaˇ cn´ı pravidla
Pravidlo pohl´ıˇz´ı na nˇekolik pol´ı z hlaviˇcky paketu a pro kaˇzd´e pole urˇcuje podm´ınku. Podm´ınka m˚ uˇze b´yt: • Rozsah: Je urˇcen souvisl´y rozsah hodnot, kter´e vyhovuje pravidlu. Takov´e podm´ınky se pouˇz´ıvaj´ı napˇr´ıklad pro ˇc´ısla TCP/UDP port˚ u. • Prefix: Je zad´ano pouze nˇekolik vyˇsˇs´ıch bit˚ u datov´eho slova, niˇzˇs´ı bity mohou m´ıt libovolnou hodnotu. Takov´e podm´ınky se ˇcasto vyuˇz´ıvaj´ı pˇri definic´ıch skupiny IP adres. Potom prefix odpov´ıd´a adrese s´ıtˇe, zat´ımco adresa poˇc´ıtaˇce je libovoln´a a podm´ınka tak vyhovuje IP adrese libovoln´eho poˇc´ıtaˇce dan´e s´ıtˇe. Jde o speci´aln´ı pˇr´ıpad rozsahu. • Hodnota: Pole mus´ı m´ıt pˇresnˇe definovanou hodnotu. Jde o speci´aln´ı pˇr´ıpad prefixu nebo rozsahu. • Libovoln´ a: Pole m˚ uˇze m´ıt libovolnou hodnotu. Jde o speci´aln´ı pˇr´ıpad prefixu nebo rozsahu. Aˇckoliv rozsah je nejobecnˇejˇs´ı podm´ınka, ˇcasto se podm´ınky reprezentuj´ı pomoc´ı prefix˚ u. Kaˇzd´y rozsah lze pˇrev´est na nˇekolik prefix˚ u, ilustrace je na obr´azku 1. Poˇcet prefix˚ u, kter´e mohou pˇri t´eto operaci vzniknout, je v nejhorˇs´ım pˇr´ıpadˇe 2N − 2, kde N je poˇcet bit˚ u dan´eho pole1 [6]. Pˇresnou hodnotu v podm´ınce pravidla lze ch´apat jako prefix maxim´aln´ı d´elky (ˇz´adn´e bity nejsou voliteln´e). Podobnˇe podm´ınku povoluj´ıc´ı libovolnou hodnotu lze ch´apat jako prefix nulov´e d´elky (vˇsechny bity jsou voliteln´e). Pokud hodnoty pol´ı konkr´etn´ıho paketu splˇ nuj´ı vˇsechny definovan´e podm´ınky nˇejak´eho pravidla, vyhovuje paket dan´emu pravidlu a tedy patˇr´ı do dan´e tˇr´ıdy. Takto by paket mohl z´aroveˇ n patˇrit do nˇekolika tˇr´ıd, proto pravidla definuj´ı nav´ıc prioritu. Potom je jako v´ysledek klasifikace vybr´ano platn´e pravidlo s nejvyˇsˇs´ı prioritou. Nyn´ı lze pravidlo definovat form´alnˇe: Pravidlo je (n + 1)-tice R : (p, a1 , a2 , . . . , aN ), kde p ∈ N je priorita a ax jsou prefixy. N je poˇcet dimenz´ı. Znaˇ cen´ı: Je-li tˇreba pravidla ˇc´ıslovat, budeme pouˇz´ıvat doln´ı index (R1 , R2 , . . .). K oznaˇcen´ı priority a jednotliv´ych prefix˚ u dan´eho pravidla pouˇzijeme teˇckovou notaci, takˇze prefix a1 pravidla R2 lze napsat jako R2 .a1 . 1 Nejhorˇ s´ım
pˇr´ıpadem je rozsah h1, 2N − 2i
1
Obr´azek 1: Pˇrevod rozsahu h3, 9i na tˇri prefixy: 0011, 01**, 100*
Klasifik´ ator je mnoˇzina pravidel takov´a, ˇze kaˇzd´a dvˇe pravidla maj´ı rozd´ılnou prioritu. K = {R; Ri .p = Rj .p ⇒ i = j}
(1)
Protoˇze priorita je pˇrirozen´e ˇc´ıslo a ˇz´adn´a dvˇe pravidla v klasifik´atoru nemaj´ı stejnou prioritu, existuje u ´pln´e uspoˇr´ad´an´ı pravidel podle priority.
2.3
Geometrick´ y pohled na klasifikaci
Na klasifikaci lze pohl´ıˇzet jako na geometrick´y probl´em. Kaˇzd´e pole, kter´e klasifikujeme, definuje jednu dimenzi. Kaˇzd´y paket je potom jeden bod ve v´ıcedimenzion´aln´ım diskr´etn´ım prostoru. Pravidla jsou body, nebo (protoˇze mohou definovat rozsahy) v´ıcerozmˇern´e pravo´ uhl´e objekty v tomto prostoru a mohou se ´ libovolnˇe pˇrekr´yvat. Ukolem klasifikaˇcn´ıho algoritmu je potom nal´ezt vˇsechny objekty, kter´e obsahuj´ı zadan´y bod, a vybrat z nich ten s nejvyˇsˇs´ı prioritou. Obr´azek 2 ilustruje geometrick´y pohled na klasifikaci podle dvou pol´ı. V praxi se vˇsak pouˇz´ıv´a v´ıce dimenz´ı, ˇcasto pˇet (zdrojov´a IP adresa, c´ılov´a IP adresa, zdrojov´y port, c´ılov´y port, protokol).
Obr´azek 2: Ilustrace geometrick´eho pohledu na klasifikaci podle dvou pol´ı. Zat´ımco dan´ y paket jednoznaˇcnˇe urˇcuje jeden bod v prostoru, pravidla mohou m´ıt podobu obd´eln´ıku (obecnˇe v´ıcerozmˇern´eho kv´adru), u ´seˇcky nebo bodu.
2.4
Kombinatorick´ y probl´ em na klasifikaci
Jin´y pohled n´am poskytuje u ´vaha nad syst´emem prefix˚ u v jednotliv´ych dimenz´ıch. Pokud z klasifik´atoru vybereme vˇsechny prefixy v jedn´e dimenzi, dostaneme mnoˇzinu prefix˚ u, obecnˇe r˚ uzn´e d´elky. Takov´ych mnoˇzin lze vytvoˇrit tolik, kolik je klasifikaˇcn´ıch pol´ı (dimenz´ı). Je zˇrejm´e, ˇze nˇekter´e prefixy mohou b´yt cel´e obsaˇzeny v jin´ych, kratˇs´ıch prefixech. Jin´ymi slovy, prefix a m˚ uˇze b´yt speci´aln´ım pˇr´ıpadem nˇekolika prefix˚ u A = {b, c, ...}, kde kaˇzd´y prefix z A je kratˇs´ı neˇz prefix a, a ˇz´adn´e dva prefixy z A nemaj´ı 2
stejnou d´elku. Naopak prefix c m˚ uˇze b´yt obecnˇejˇs´ım pˇr´ıpadem nˇekolika prefix˚ u C = {a, b, ...}, kde kaˇzd´y prefix z B je delˇs´ı neˇz prefix c. Prefixy z B mohou m´ıt stejnou d´elku. Na z´akladˇe tohoto vztahu vznik´a relace ˇc´asteˇcn´eho uspoˇr´ad´an´ı, kterou lze pˇrehlednˇe vyj´adˇrit stromov´ym diagramem (obr. 3). Doplnˇen´ım c
d
b
a
ˇ ri prefixy v relaci ˇc´asteˇcn´eho uspoˇr´ad´an´ı. Prefix a je speci´aln´ım pˇr´ıpadem prefix˚ Obr´azek 3: Ctyˇ ub a c. Prefix c je obecnˇejˇs´ım pˇr´ıpadem vˇsech ostatn´ıch prefix˚ u. myˇslen´ych prefix˚ u lze z´ıskat bin´arn´ı strom (obr. 4). Pro zobrazen´ı pravidla je nutn´e doplnit do obr´azku * 1
0 0*
1*
0 1 101
Obr´azek 4: Konkr´etn´ı pˇr´ıklad prefix˚ u z pˇredchoz´ıho obr´azku, doplnˇen´ y do podoby bin´arn´ıho stromu. Pouˇz´ıv´ame pˇr´ım´ y z´apis bin´arn´ıch ˇc´ısel, hvˇezdiˇcka oznaˇcuje libovoln´e zbyl´e bity. bin´arn´ı stromy pro vˇsechny dimenze (obr. 5). Pravidlo je potom spojnice jdouc´ı pr´avˇe jedn´ım uzlem v kaˇzd´em bin´arn´ım stromˇe. Pro pˇrehlednost jsou v tab. 1 pravidla vyps´ana. Pole 1
Pole 2 R1 1 0
0
1
R2
0
0 0
1
R3
Obr´azek 5: Dva bin´arn´ı stromy a tˇri pravidla R1, R2, R3. V t´eto interpretaci probl´emu je u ´kolem klasifikaˇcn´ıho algoritmu nejprve vyhledat odpov´ıdaj´ıc´ı prefixy ve vˇsech dimenz´ıch. V kaˇzd´e dimenzi m˚ uˇze paketu odpov´ıdat hned nˇekolik prefix˚ u, v´ysledkem prvn´ıho kroku tedy nen´ı N prefix˚ u, ale N mnoˇzin prefix˚ u. V dalˇs´ım kroku je tˇreba vytvoˇrit kart´ezsk´y souˇcin tˇechto mnoˇzin a zjistit, kter´e prvky kart´ezsk´eho souˇcinu odpov´ıdaj´ı nˇekter´emu pravidlu. Prvky tohoto kart´ezsk´eho souˇcinu maj´ı totiˇz tvar pravidla (aˇz na chybˇej´ıc´ı prioritu). V´ysledkem algoritmu bude pravidlo s nejvyˇsˇs´ı prioritou. 3
Pravidlo
Pole 1
Pole 2
R1
1*
*
R2
1*
00*
R3
101*
100*
Tabulka 1: Pravidla z obr. 5
2.5
Poˇ zadavky na klasifikaˇ cn´ı algoritmus
Klasifikaˇcn´ı algoritmus mus´ı splˇ novat jist´e vlastnosti, aby byl vhodn´y pro praktick´e pouˇzit´ı v s´ıt’ov´ych zaˇr´ızen´ıch: • Rychlost: Klasifikaˇcn´ı algoritmus mus´ı pracovat v re´aln´em ˇcase, tak, aby nesniˇzoval pˇrenosovou rychlost s´ıtˇe. Nejhorˇs´ım pˇr´ıpadem je pˇrenos nejkratˇs´ıch paket˚ u, protoˇze v takov´e situaci se pˇren´aˇs´ı nejv´ıc paket˚ u za jednotku ˇcasu. Tabulka 2 ukazuje poˇcet pˇrenesen´ych paket˚ u za sekundu pro typick´e pˇrenosov´e rychlosti souˇcasn´ych nebo budouc´ıch s´ıt´ı. Pˇri v´ypoˇctu je uvaˇzov´ana s´ıt’ typu Ethernet, kde m´a nejkratˇs´ı r´amec (odpov´ıd´a paketu na s´ıt’ov´e vrstvˇe) velikost 64 B, ale ke kaˇzd´emu r´amci je nutno pˇripoˇc´ıst 8 B preambuli a 12 B mezir´amcovou mezeru. Vˇetˇsina literatury uv´ad´ı sloˇzitost klasifikaˇcn´ıho algoritmu jako nejhorˇs´ı poˇcet pˇr´ıstup˚ u do pamˇeti. Takov´a metrika je nez´avisl´a na pouˇzit´e technologii. Pochopitelnˇe existuj´ı i dalˇs´ı krit´eria rychlosti, napˇr´ıklad re´aln´a propustnost v paketech za sekundu, nebo latence v´ypoˇctu. • Pamˇ et’ov´ e poˇ zadavky: Velikost spotˇrebovan´e pamˇeti je d˚ uleˇzit´a, protoˇze ovlivˇ nuje cenu cel´eho ˇ ˇreˇsen´ı. Casto se ud´av´a v bajtech na pravidlo. Velikost pamˇeti m´a tak´e vliv na rychlost ˇreˇsen´ı. Obecnˇe totiˇz plat´ı, ˇze menˇs´ı pamˇeti jsou rychlejˇs´ı neˇz pamˇeti s vˇetˇs´ı kapacitou. Napˇr´ıklad pouˇzit´ı blokov´ych pamˇet´ı uvnitˇr ˇcipu je rychlejˇs´ı neˇz vyuˇzit´ı extern´ı statick´e pamˇeti. • Plocha na ˇ cipu: V pˇr´ıpadˇe hardwarov´e implementace algoritmu je d˚ uleˇzit´ym ukazatelem zabran´a plocha FPGA nebo ASIC ˇcipu. • Poˇ cet a vlastnosti pravidel: D˚ uleˇzit´ym parametrem ˇreˇsen´ı je tak´e maxim´aln´ı poˇcet pravidel, kter´a lze nahr´at do syst´emu. Kromˇe mnoˇzstv´ı pravidel je velice ˇz´adouc´ı zkoumat jejich vlastnosti. Pˇredevˇs´ım je tˇreba se zamˇeˇrit na poˇcet unik´atn´ıch hodnot pro jednotliv´a pole v pravidlech. Ukazuje se, ˇze mnoˇzstv´ı unik´atn´ıch prefix˚ u v jednotliv´ych pol´ıch je vˇetˇsinou mnohem niˇzˇs´ı neˇz poˇcet pravidel [16, 15]. T´eto skuteˇcnosti s v´yhodou vyuˇz´ıvaj´ı pokroˇcil´e algoritmy klasifikace paket˚ u.
Rychlost s´ıtˇ e [Gbit/s]
Paketov´ a rychlost [paket˚ u/s]
Doba zpracov´ an´ı paketu [ns/paket]
1
1 488 095
672
10
14 880 952
67,2
40
59 523 809
16,8
100
148 809 523
6,72
Tabulka 2: Poˇcet pˇrenesen´ ych paket˚ u d´elky 64 B pro r˚ uzn´e s´ıt’ov´e rychlosti.
3
Souˇ casn´ e pˇ r´ıstupy ke klasifikaci paket˚ u
Pˇredchoz´ı kapitola uvedla probl´em klasifikace paket˚ u a vymezila podm´ınky, kter´e mus´ı algoritmus ˇreˇs´ıc´ı popsan´y probl´em splˇ novat. V t´eto ˇc´asti pr´ace je uvedeno nˇekolik z´akladn´ıch metod pro klasifikaci paket˚ u. 4
Prvn´ı dva uveden´e algoritmy jsou pouze teoretickou moˇznost´ı, po nich n´asleduj´ı jiˇz propracovanˇejˇs´ı metody. Jsou vybr´any algoritmy urˇcuj´ıc´ı smˇery, kter´ymi se nejˇcastˇeji inspiruj´ı dalˇs´ı navazuj´ıc´ı pr´ace.
3.1
Naivn´ı pˇ r´ıstupy ke klasifikaci
Snad nejjednoduˇsˇs´ı pˇr´ıstup je line´arn´ı prohled´an´ı mnoˇziny pravidel. Staˇc´ı uloˇzit vˇsechna pravidla do jedn´e tabulky a kaˇzd´y paket postupnˇe porovnat se vˇsemi pravidly. Je zˇrejm´e, ˇze takov´y algoritmus m´a line´arn´ı ˇcasovou sloˇzitost s poˇctem pravidel a je tedy nevhodn´y z pohledu rychlosti. Pokud by mnoˇzina pravidel obsahovala tis´ıc prvk˚ u, bylo by nutn´e udˇelat tis´ıc pˇr´ıstup˚ u do pamˇeti pro klasifikaci kaˇzd´eho paketu. Tento algoritmus m´a vˇsak nejmenˇs´ı n´aroky na pamˇet’. Opaˇcn´ym extr´emem je algoritmus, kter´y vˇsechna rozhoduj´ıc´ı pole z hlaviˇcky paketu spoj´ı za sebe do jednoho datov´eho slova a vznikl´e slovo pak pouˇzije jako adresu do pamˇeti. Na dan´e adrese v pamˇeti je pak uloˇzeno pˇr´ımo ˇc´ıslo v´ysledn´eho pravidla. Mus´ıme tak vlastnˇe m´ıt pamˇet’ s ˇc´ıslem pravidla pro kaˇzd´y moˇzn´y paket. Pro klasifikaci paketu pak staˇc´ı jedin´y pˇr´ıstup do pamˇeti. Z toho d˚ uvodu je takov´y algoritmus teoreticky nejrychlejˇs´ı moˇzn´y. Jeho pouˇzit´ı je vˇsak nere´aln´e z d˚ uvodu pamˇet’ov´e n´aroˇcnosti. Napˇr´ıklad: Spoj´ıme-li dvˇe IPv4 adresy, dvˇe ˇc´ısla port˚ u a jedno ˇc´ıslo protokolu do jednoho datov´eho slova, dostaneme adresu ˇsirokou 2 · 32 + 2 · 16 + 8 = 104 bit˚ u. Pamˇet’ by tedy musela obsahovat 2104 poloˇzek, coˇz je za souˇcasn´eho stavu poˇc´ıtaˇcov´e techniky prakticky nemoˇzn´e.
3.2
TCAM
Asociativn´ı pamˇet’ je zvl´aˇstn´ım typem pamˇeti, kter´a podporuje vyhled´av´an´ı podle obsahu. Vstupem je hledan´e slovo a v´ystupem je adresa, na kter´e se slovo nach´az´ı. Pamˇet’ m´a u kaˇzd´eho slova kompar´atory, kter´e vyhodnocuj´ı shodu hledan´eho slova s uloˇzen´ym. Tern´arn´ı varianta asociativn´ıch pamˇet´ı (TCAM) pracuje kromˇe jedniˇcek a nul jeˇstˇe s tˇret´ım stavem, naz´yvan´ym don’t care a oznaˇcovan´ym X. Je-li v pamˇeti na nˇejak´e bitov´e pozici tato hodnota, nen´ı pˇri vyhled´av´an´ı br´an na dan´y bit zˇretel, takˇze m˚ uˇze b´yt na vstupu nula nebo jedniˇcka a v obou pˇr´ıpadech se bit povaˇzuje za shodn´y. T´ım je pˇr´ımo podporov´ano hled´an´ı prefix˚ u. Do horn´ı ˇc´asti datov´eho slova se uloˇz´ı poˇzadovan´e bity, zat´ımco spodn´ı ˇc´ast slova se nastav´ı na don’t care. Pˇrevedeme-li rozsahy v definici pravidel na prefixy, m˚ uˇzeme do TCAM ukl´adat pˇr´ımo pravidla, a pot´e je vyhled´avat jedin´ym pˇr´ıstupem. Z uveden´eho by se mohlo zd´at, ˇze TCAM podporuje klasifikaci paket˚ u v konstantn´ı ˇcasov´e a line´arn´ı prostorov´e sloˇzitosti. Jednak nˇeco takov´eho nen´ı z definice sloˇzitosti moˇzn´e (prostorov´a sloˇzitost nem˚ uˇze nikdy pˇres´ahnout ˇcasovou), nav´ıc je nutn´e povaˇzovat paraleln´ı vyhled´av´an´ı v TCAM za v´ıcep´askov´y Turing˚ uv stroj (kaˇzd´a p´aska pro jedno pravidlo). Ten po pˇreveden´ı na jednop´askov´y z´ısk´a line´arn´ı ˇcasovou i prostorovou sloˇzitost s poˇctem pravidel. TCAM maj´ı omezenou kapacitu, pomˇernˇe velk´y pˇr´ıkon a tak´e vysokou poˇrizovac´ı cenu. I pˇres zn´am´e nev´yhody jsou pamˇeti TCAM ˇcasto pouˇz´ıv´any v komerˇcn´ıch zaˇr´ızen´ıch [12, 5]. Uveden´e nev´yhody zp˚ usobuj´ı, ˇze st´ale existuje snaha nach´azet a zkoumat algoritmy, kter´e pouˇz´ıvaj´ı pamˇeti s n´ahodn´ym pˇr´ıstupem.
3.3
BitVector algoritmus
Algoritmus BitVector [8] pohl´ıˇz´ı na klasifikaci jako na geometrick´y probl´em. Algoritmus nejprve prom´ıtne v kaˇzd´e dimenzi vˇsechny rozsahy na ˇc´ıselnou osu. T´ım na ose vznikne maxim´alnˇe 2n + 1 nepˇrekr´yvaj´ıc´ıch se interval˚ u, kde n je poˇcet r˚ uzn´ych rozsah˚ u v t´eto dimenzi. Kaˇzd´emu intervalu je pˇriˇrazen vektor, kter´y obsahuje jeden bit pro kaˇzd´e pravidlo klasifik´atoru. Bity vektoru jsou nastaveny na jedniˇcku pr´avˇe kdyˇz se v t´eto dimenzi dan´e pravidlo pˇrekr´yv´a s intervalem (obr´azek 6). Klasifikace paket˚ u potom spoˇc´ıv´a ve vyhled´an´ı intervalu pro danou hodnotu pole paketu (lze prov´est bin´arn´ım hled´an´ım – logaritmick´a ˇcasov´a sloˇzitost) ve vˇsech pol´ıch nez´avisle. Pro kaˇzd´e pole tak z´ısk´ame jeden vektor. Pokud nad tˇemito vektory provedeme bitov´y souˇcin, z˚ ustanou ve v´ysledku jedniˇcky pouze pro ta pravidla, kter´a byla splnˇena ve vˇsech dimenz´ıch. Struktura algoritmu je naznaˇcena na obr´azku 7. Byly navrˇzeny nˇekter´e u ´pravy tohoto algoritmu (napˇr´ıklad Aggregated Bit Vector [1], nebo BV-TCAM [13]), kter´e dosahuj´ı lepˇs´ıch v´ysledk˚ u jak pamˇet’ov´e, tak ˇcasov´e n´aroˇcnosti.
5
Obr´azek 6: V´ ypoˇcet vektor˚ u pro dvˇe dimenze. Tˇri pravidla vytvoˇrila 7 interval˚ u na vodorovn´e ose a 5 interval˚ u na svisl´e ose. Ke kaˇzd´emu intervalu je pˇriˇrazen vektor tˇr´ı bit˚ u, protoˇze klasifik´ator obsahuje tˇri pravidla.
Obr´azek 7: Sch´ema klasifikace algoritmem BitVector. Po vyhled´an´ı intervalu v kaˇzd´e dimenzi je proveden bitov´ y souˇcin vˇsech vektor˚ u a ve v´ ysledn´em vektoru je nalezeno pravidlo s nejvyˇsˇs´ı prioritou.
Nicm´enˇe pr´avˇe poˇcet pˇr´ıstup˚ u do pamˇeti je slabinou algoritm˚ u zaloˇzen´ych na Bit Vector. Pro vˇetˇs´ı poˇcet pravidel roste d´elka vektoru tak, ˇze je nutn´e pˇristoupit nˇekolikr´at do pamˇeti pro naˇcten´ı cel´eho vektoru. Tento fakt je pˇr´ıˇcinou niˇzˇs´ı rychlosti algoritmu.
3.4
RFC algoritmus
Recursive Flow Classification (popsan´y v [6]) vych´az´ı z naivn´ıho pˇr´ıstupu s velikou tabulkou pro vˇsechny moˇzn´e pakety. Rozd´ıl je v tom, ˇze RFC postupuje rekurzivnˇe. Pole z hlaviˇcky paketu jsou rozdˇelena na slova se vhodnou datovou ˇs´ıˇrkou (napˇr. 16 bit˚ u), a vznikl´a slova jsou pouˇzita jako adresy do tabulek. Tabulky jsou pˇredvyplnˇeny hodnotami tak, aby pakety patˇr´ıc´ı do r˚ uzn´ych pravidel d´avaly odliˇsn´e hodnoty (rozklad na tˇr´ıdy ekvivalence). Nˇekolik v´ystup˚ u tˇechto tabulek je spojeno line´arn´ı kombinac´ı a pouˇzito jako adresa do dalˇs´ı tabulky.
6
Line´arn´ı kombinace je n´asoben´ı konstantou a souˇcet, pˇriˇcemˇz konstanty jsou voleny tak, aby pro r˚ uzn´e vstupy byl vˇzdy r˚ uzn´y v´ysledek. Napˇr´ıklad pro line´arn´ı kombinaci dvou hodnot je jedna hodnota nejprve vyn´asobena poˇctem prvk˚ u druh´e mnoˇziny a potom jsou obˇe hodnoty seˇcteny. Takto je vybudov´ana hierarchick´a struktura, kter´a postupnˇe sniˇzuje poˇcet bit˚ u, kter´ymi adresujeme, aˇz na konci je tabulka obsahuj´ıc´ı samotn´a pravidla. Sch´ema v´ypoˇctu je na obr´azku 8. Tento algoritmus
Obr´azek 8: Sch´ema klasifikace algoritmem RFC. Na prvn´ı u ´rovni jsou adresy do tabulek pˇr´ımo hodnoty pol´ı z hlaviˇcky paketu, d´ale jsou v´ ysledky kombinov´any a pouˇzity jako adresy dalˇs´ıch tabulek. Posledn´ı tabulka obsahuje pravidla. poskytuje velice dobr´e v´ysledky z pohledu v´ykonnosti, ale jeho slabinou je pamˇet’ov´a n´aroˇcnost, kter´a je mnohokr´at vˇetˇs´ı neˇz u ostatn´ıch metod [12].
7
3.5
Rozhodovac´ı stromy
Hierarchical Intelligent Cuttings (Hi-Cuts) [6] je algoritmus vych´azej´ıc´ı z geometrick´e repre- zentace klasifikace. Spoˇc´ıv´a v konstrukci rozhodovac´ıho stromu. Pˇri pr˚ uchodu stromem je v kaˇzd´em uzlu prostor paket˚ u dˇelen rovnobˇeˇzn´ymi plochami na v´ıce oblast´ı. Dalˇs´ı postup stromem je zvolen takov´y, aby klasifikovan´y paket leˇzel v dan´e oblasti. Takto je nakonec prostor omezen tak, ˇze dost´av´ame pouze oblast obsahuj´ıc´ı spr´avn´a pravidla. Aby algoritmus ˇsetˇril pamˇet’, je nˇekolik posledn´ıch stupˇ n˚ u stromu nahrazeno line´arn´ım prohled´an´ım. Pro konstrukci rozhodovac´ıho stromu je navrˇzena heuristika. Obr´azek 9 ukazuje pˇr´ıklad jednoduch´eho rozhodovac´ıho stromu.
Obr´azek 9: Rozhodovac´ı strom algoritmu Hi-Cuts. Uzly obsahuj´ı informaci o vˇetven´ı stromu (ve kter´e dimenzi, na kolik ˇc´ast´ı) a ukazatele na n´asleduj´ıc´ı uzly nebo listy. Listy obsahuj´ı nˇekolik pravidel.
Obr´azek 10: Plocha rozdˇelen´a podle rozhodovac´ıho stromu z obr´azku 9. Prvn´ı dˇelen´ı je ve vodorovn´e ose na ˇctyˇri ˇc´asti, d´ale je jedna ˇc´ast rozdˇelena svisle na dvˇe ˇc´asti. Nˇekter´a pravidla mohou zasahovat do v´ıce ˇc´ast´ı, potom se objev´ı ve v´ıce listech stromu. Hypercuts [12] je modifikac´ı pˇredchoz´ıho algoritmu tak, aby bylo moˇzn´e v jednom uzlu stromu dˇelit 8
prostor podle v´ıce neˇz jedn´e dimenze. T´ım je dosaˇzeno menˇs´ı hloubky stromu a tedy urychlen´ı algoritmu. Experiment´aln´ı v´ysledky ukazuj´ı tak´e na menˇs´ı pamˇet’ovou n´aroˇcnost.
3.6
Algoritmy zaloˇ zen´ e na dekompozici probl´ emu
Dekompoziˇcn´ı algoritmy ˇreˇs´ı klasifikaci ve dvou z´akladn´ıch kroc´ıch, kter´e odpov´ıdaj´ı kombinatorick´emu pohledu na klasifikaci, uveden´emu v ˇc´asti 2.4. V prvn´ım kroku je vyhled´an nejdelˇs´ı shodn´y prefix pro kaˇzd´e pole. To znamen´a, ˇze ze vˇsech prefix˚ u pro jednotliv´e pole dan´eho klasifik´atoru je nalezen ten nejspecifiˇctˇejˇs´ı, kter´y odpov´ıd´a hodnotˇe v hlaviˇcce konkr´etn´ıho paketu. Protoˇze v´ysledky prvn´ıho kroku neidentifikuj´ı jednoznaˇcnˇe pravidlo, n´asleduje proces hled´an´ı odpov´ıdaj´ıc´ıho pravidla. V´ysledkem druh´eho kroku je jiˇz ˇc´ıslo nalezen´eho pravidla. Ve druh´em kroku je nutn´e vyˇreˇsit probl´em tzv. pseudopravidel. V t´eto ˇc´asti je nejprve vysvˇetleno nˇekolik souvisej´ıc´ıch pojm˚ u, a pak jsou uvedeny nˇekter´e d˚ uleˇzit´e algoritmy ze t´eto skupiny. Vyhled´ an´ı nejdelˇ s´ıho shodn´ eho prefixu Algoritmus vyhled´an´ı nejdelˇs´ıho prefixu (Longest Prefix Match - LPM) m´a na vstupu mnoˇzinu prefix˚ u r˚ uzn´e d´elky a jednu konkr´etn´ı hodnotu. V´ystupem algoritmu je ze vˇsech prefix˚ u, kter´e odpov´ıdaj´ı dan´e hodnotˇe ten nejdelˇs´ı, tedy nejspecifiˇctˇejˇs´ı. Klasick´y algoritmus vyhled´an´ı nejdelˇs´ıho prefixu se naz´yv´a trie z anglick´eho retrieval, nˇekdy tak´e oznaˇcovan´y prefixov´y strom. Je zde vyuˇzita stromov´a datov´a struktura, kter´a obsahuje uloˇzen´a slova pˇr´ımo ve sv´e konstrukci. Kaˇzd´y uzel stromu obsahuje dva (v pˇr´ıpadˇe bin´arn´ı trie) ukazatele na dalˇs´ı uzly. V pr˚ ubˇehu v´ypoˇctu se zpracov´avaj´ı postupnˇe bity hledan´eho slova od nejv´yznamnˇejˇs´ıho k nejm´enˇe v´yznamn´emu. V kaˇzd´em kroku v´ypoˇctu se podle tohoto bitu rozhoduje, zda se bude postupovat lev´ym nebo prav´ym podstromem. V kaˇzd´em uzlu je oznaˇceno, zda zat´ım zpracovan´e bity tvoˇr´ı platn´y prefix. Pokud ano, je zde tak´e uloˇzeno ˇc´ıslo tohoto prefixu pro identifikaci. Pˇri pr˚ uchodu stromem je zapamatov´an posledn´ı platn´y prefix a na konci je pˇred´an jako v´ysledek. V´ypoˇcet je ukonˇcen, kdyˇz s danou hodnotou bitu jiˇz nen´ı moˇzn´e postupovat d´ale stromem (potˇrebn´y podstrom neexistuje), nebo jsou jiˇz zpracov´any ˇ vˇsechny vstupn´ı bity. Casov´ a sloˇzitost vyhled´an´ı je line´arn´ı s poˇctem bit˚ u datov´eho slova. Jednoduch´y pˇr´ıklad struktury trie je na obr´azku 11.
Obr´azek 11: Trie pro pˇetibitov´e pole. Jsou zde uloˇzeny 4 prefixy: 10*, 1010*, 10101, 111*. Existuje ˇrada modifikac´ı trie, z´akladn´ı z nich je zv´yˇsen´ı arity uzl˚ u. V kaˇzd´em kroku se potom rozhoduje podle v´ıce neˇz jednoho bitu a uzel se m˚ uˇze tedy vˇetvit do v´ıce neˇz dvou podstrom˚ u.
9
Pseudopravidla Pojem pseudopravidlo, zaveden´y v [5], oznaˇcuje pravidla, kter´a je nutn´e pˇridat do mnoˇziny pravidel tak, aby kaˇzd´a platn´a kombinace v´ysledk˚ u LPM byla pokryta. Vznik pseudopravidel demonstrujme na pˇr´ıkladˇe klasifikace podle dvou pol´ı. Tabulka 3 obsahuje tˇri jednoduch´a pravidla. Pravidlo
Pole 1
Pole 2
Pseudopravidlo
Pole 1
Pole 2
Pravidlo
R1
1*
*
P1
1*
100*
R1
R2
1*
00*
P2
101*
00*
R2
R3
101*
100*
P3
101*
*
R1
Tabulka 3: P˚ uvodn´ı pravidla
Tabulka 4: Pˇridan´a pseudopravidla
Obr´azek 12: Reprezentace pravidel a pseudopravidel (ˇc´arkovanˇe) pomoc´ı dvou trie. Pseudopravidla jsou specifiˇctˇejˇs´ımi pˇr´ıpady pravidel. Na obr´azku 12 jsou potom naznaˇceny trie pro LPM v obou dimenz´ıch. Vyplnˇen´e uzly znaˇc´ı platn´e prefixy. Barevn´ymi ˇcarami jsou oznaˇceny kombinace vstup˚ u, kter´e byly definov´any v p˚ uvodn´ı mnoˇzinˇe ˇ arkovanˇe jsou vyznaˇcena pseudopravidla. Jde o doplnˇen´ı mnoˇziny pravidel tak, aby i specifiˇctˇejˇs´ı pravidel. C´ v´ysledky LPM mˇely smysl a bylo z nich moˇzn´e snadno urˇcit spr´avn´e pravidlo. Tabulka 4 obsahuje pseudopravidla pro tento pˇr´ıklad. Na pseudopravidla lze pohl´ıˇzet tak´e jako na zp˚ usob, jak se vyhnout vyhodnocov´an´ı kart´ezsk´eho souˇcinu popsan´emu v ˇc´asti 2.4. D´ıky operaci LPM nem´a vyhled´an´ı v jednotliv´ych dimenz´ıch za v´ysledky mnoˇziny ˇ adn´y kart´ezsk´y souˇcin tedy nevznik´a. A d´ıky pˇrid´an´ı prefix˚ u, ale jen ty nejspecifiˇctˇejˇs´ı (tedy nejpˇresnˇejˇs´ı). Z´ pseudopravidel je kaˇzd´a takov´a kombinace v´ysledk˚ u platn´a a odkazuje na spr´avn´e ˇc´ıslo pravidla. Pˇ r´ıklad: Pokud by operace LPM vr´atily v´ysledek (1*, 100*), potom spr´avn´ym v´ysledkem klasifikace je pravidlo R1, protoˇze 100* je speci´aln´ı pˇr´ıpad obecnˇejˇs´ı hodnoty *. Nicm´enˇe v p˚ uvodn´ı mnoˇzinˇe pravidel se kombinace (1*, 100*) v˚ ubec nevyskytuje. Proto je nutn´e pˇridat pseudopravidlo P1, kter´e uvedenou kombinaci oˇsetˇruje. Pseudopravidlo v sobˇe obsahuje informaci, ˇze spr´avn´ym v´ysledkem klasifikace je pravidlo R1. Generovan´a pseudopravidla pˇripom´ınaj´ı kart´ezsk´y souˇcin, jelikoˇz je nutn´e pro kaˇzd´e pravidlo pokr´yt vˇsechny specifiˇctˇejˇs´ı prefixy ve vˇsech pol´ıch. Vzhledem k charakteru kart´ezsk´eho souˇcinu m˚ uˇze r˚ ust poˇcet pseudopravidel exponenci´alnˇe s poˇctem pravidel. V re´aln´ych klasifik´atorech sice nemus´ı doch´azet k tak v´yrazn´emu n´ar˚ ustu, ale pˇresto experiment´aln´ı v´ysledky ukazuj´ı na ˇr´adov´e zvˇetˇsen´ı potˇrebn´e pamˇeti [5].
10
Naivn´ı algoritmus kart´ ezsk´ eho souˇ cinu Pakety lze klasifikovat tak, ˇze se nejprve nalezne LPM pro kaˇzd´e pole a v´ysledky se spoj´ı do jednoho datov´eho slova [14]. Toto slovo je vstupem hashovac´ı funkce. V´ystupem je potom adresa do tabulky, ve kter´e jsou uloˇzena jak pravidla, tak pseudopravidla. Jsou-li vhodnˇe oˇsetˇreny kolize hashovac´ı funkce, je ˇcasov´a sloˇzitost takov´eho dohled´an´ı konstantn´ı. Nev´yhodou popsan´eho algoritmu je pamˇet’ov´a n´aroˇcnost, protoˇze n´ar˚ ust poˇctu pseudopravidel m˚ uˇze b´yt exponenci´aln´ı. DCFL V Distributed Crossproducting of Field Labels [15] je operace LPM modifikov´ana tak, aby v´ysledkem nebyl pouze jedin´y, nejdelˇs´ı prefix. Nam´ısto toho je v´ysledkem mnoˇzina vˇsech prefix˚ u, na kter´e algoritmus po cestˇe stromem narazil (tedy obecnˇejˇs´ı prefixy). V dalˇs´ım kroku je nutn´e zkusit vˇsechny kombinace v´ysledk˚ u a zjistit, zda nˇekter´a z nich odpov´ıd´a nˇekter´emu pravidlu. Jak uˇz bylo uvedeno, takov´a operace je kart´ezsk´y souˇcin nˇekolika mnoˇzin a m´a exponenci´aln´ı ˇcasovou sloˇzitost. DCFL popsan´y probl´em ˇreˇs´ı tak, ˇze kombinace prefix˚ u vyhodnocuje distribuovanˇe. Kart´ezsk´y souˇcin se prov´ad´ı vˇzdy pouze na dvou mnoˇzin´ach - zkoum´a se, zda se v nˇekter´em pravidle vyskytla kombinace dan´ych dvou prefix˚ u. Pro dotazy jsou pouˇzita pole Bloomov´ych filtr˚ u [2]. Z kart´ezsk´eho souˇcinu mohou b´yt nˇekter´e kombinace zam´ıtnuty, protoˇze neodpov´ıdaj´ı ˇz´adn´emu pravidlu. Ostatn´ı, nezam´ıtnut´e kombinace proch´azej´ı do dalˇs´ıch stupˇ n˚ u, kter´e pracuj´ı na stejn´em principu. Takto je vytvoˇrena stromov´a struktura, naznaˇcen´a na obr´azku 13. V´ysledkem posledn´ıho stupnˇe je mnoˇzina pravidel odpov´ıdaj´ıc´ıch dan´emu paketu.
Obr´azek 13: Sch´ema algoritmu DCFL pro klasifikaci podle 4 pol´ı. Po vyhled´ an´ı vˇsech prefix˚ u pro kaˇzd´e pole jsou zkoum´any vˇsechny kombinace prefix˚ u. Ze sch´ematu v´ypoˇctu je vidˇet, ˇze algoritmus je vhodn´y pro paraleln´ı prov´adˇen´ı, protoˇze jednotliv´e operace LPM mohou bˇeˇzet paralelnˇe, podobnˇe jako vyhodnocov´an´ı kart´ezsk´ych souˇcin˚ u. Slabinou algoritmu je postupn´e vyhodnocov´an´ı kart´ezsk´eho souˇcinu. Jsou-li v´ysledky LPM napˇr. dvˇe mnoˇziny ˇctyˇrech prefix˚ u, potom kart´ezsk´y souˇcin obsahuje 16 poloˇzek, pˇriˇcemˇz pro kaˇzdou z nich mus´ıme ovˇeˇrit jej´ı pˇr´ıtomnost v mnoˇzinˇe. I kdyˇz takov´e ovˇeˇrov´an´ı lze prov´adˇet s konstantn´ı ˇcasovou sloˇzitost´ı, je nutn´e znaˇcnˇe paraleln´ı vykon´av´an´ı nˇekolika tˇechto operac´ı nar´az. Nav´ıc pouˇzit´ı Bloomov´ych filtr˚ u pˇrin´aˇs´ı moˇznost chyby, kterou je nutn´e v pozdˇejˇs´ıch f´az´ıch v´ypoˇctu eliminovat. Pˇr´ıpadn´a anal´yza ˇcasov´e sloˇzitosti mus´ı poˇc´ıtat s nejhorˇs´ım pˇr´ıpadem ve vˇsech ˇc´astech v´ypoˇctu, pˇriˇcemˇz nejhorˇs´ı pˇr´ıpad se m˚ uˇze znaˇcnˇe odliˇsovat od typick´eho.
11
MSCA Velmi d˚ uleˇzit´y Multi-Subset Crossproduct Algorithm, popsan´y v [5], vych´az´ı z pozorov´an´ı, ˇze mnoˇzinu pravidel lze rozdˇelit do nˇekolika podmnoˇzin tak, aby vznikalo pouze velmi m´alo pseudopravidel. Experiment´aln´ı v´ysledky ukazuj´ı, ˇze poˇcet pravidel se d´ıky tomu zvˇetˇs´ı pouze 1,2 aˇz 2 kr´at. Je-li mnoˇzina pravidel rozdˇelena do v´ıce podmnoˇzin, je tˇreba pro kaˇzdou podmnoˇzinu prov´adˇet oddˇelen´e vyhled´an´ı nejdelˇs´ıho shodn´eho prefixu. Tomu se algoritmus vyhne tak, ˇze jako v´ysledek operace LPM uloˇz´ı v´ysledek pro kaˇzdou podmnoˇzinu. Tak´e je nutn´e pro kaˇzdou podmnoˇzinu oddˇelenˇe prov´adˇet hashov´an´ı a pˇr´ıstup do pamˇeti, abychom zjistili, zda bylo nalezeno platn´e pravidlo. Tomu se vˇsak lze vyhnout pouˇzit´ım Bloomov´ych filtr˚ u. Cel´e sch´ema v´ypoˇctu je na obr´azku 14.
Obr´azek 14: Sch´ema algoritmu zaloˇzen´eho na rozdˇelen´ı mnoˇziny pravidel do podmnoˇzin. (Zobrazena klasifikace podle dvou pol´ı, tˇri podmnoˇziny pravidel) Tak´e algoritmus MSCA je, podobnˇe jako DCFL, velice v´yhodn´y z pohledu rychlosti i vyuˇzit´e pamˇeti. Za slabinu bychom zde mohli povaˇzovat vyuˇzit´ı Bloomov´ych filtr˚ u, kter´e pˇripouˇstˇej´ı chybu typu false positive, tedy chybn´a detekce pˇr´ıtomnosti slova v mnoˇzinˇe. Tyto chyby jsou sice n´aslednˇe odstranˇeny kontrolou obsahu hlavn´ı pamˇeti, ale zp˚ usobuj´ı zvyˇsov´an´ı poˇctu pˇr´ıstup˚ u do pamˇeti, a tedy v nev´yhodn´e situaci mohou degradovat v´ykon algoritmu. Tento algoritmus je vˇsak zaj´ımav´y z toho d˚ uvodu, ˇze pˇrin´aˇs´ı dva zp˚ usoby, jak sniˇzovat mnoˇzstv´ı pseudopravidel. Prvn´ım zp˚ usobem je samotn´e rozdˇelen´ı klasifik´atoru na podmnoˇziny. Druhou optimalizac´ı je pouˇzit´ı mal´e TCAM (ˇr´adovˇe na jednotky ˇci des´ıtky pravidel), kam se uloˇz´ı ta pravidla, kter´a zp˚ usobovala nejvˇetˇs´ı n´ar˚ ust poˇctu pseudopravidel. Pozorov´an´ım bylo totiˇz zjiˇstˇeno, ˇze nejvˇetˇs´ı poˇcet pseudopravidel je zp˚ usoben jenom mal´ym mnoˇzstv´ym pravidel. Pokud se tedy nˇekolik tˇechto pravidel odstran´ı z klasifik´atoru, a jejich vliv se zajist´ı jinak (napˇr. malou TCAM), poˇcet pseudopravidel je v´yraznˇe omezen. Nˇekter´e zp˚ usoby identifikace pravidel, kter´a generuj´ı nejv´ıce pseudopravidel, jsou pops´any v [7]. PHCA Perfect Hashing Crossproduct Algorithm [10] se zamˇeˇruje na odstranˇen´ı nutnosti ukl´adat pseudopravidla, jak se to dˇeje v naivn´ım algoritmu kart´ezsk´eho souˇcinu a v MSCA. Sch´ema algoritmu je naznaˇceno na obr. 15. Pˇredem je zkonstruov´ana hashovac´ı funkce na m´ıru tak, aby vˇsechny kombinace v´ysledk˚ u LPM mapovala pˇr´ımo na spr´avn´e ˇc´ıslo pravidla. Je k tomu vyuˇzit algoritmus konstrukce perfektn´ı (tedy bezkolizn´ı) hashovac´ı funkce [3]. Jej´ı vyˇc´ıslen´ı spoˇc´ıv´a ve vyˇc´ıslen´ı dvou r˚ uzn´ych bˇeˇzn´ych hashovac´ıch funkc´ı f 1 a f 2, dvou pˇr´ıstupech do tabulky, a jednom aritmetick´em souˇctu. Tabulka je pˇredem vypoˇctena na z´akladˇe kl´ıˇc˚ u a poˇzadovan´ych v´ysledk˚ u hashovac´ı funkce. Hashovac´ı funkce vˇsak v tomto pˇr´ıpadˇe zkonstruov´ana z´amˇernˇe tak, aby obsahovala velk´e mnoˇzstv´ı koliz´ı. To je z toho d˚ uvodu, ˇze poˇcet pseudopravidel je v´yraznˇe vyˇsˇs´ı neˇz poˇcet pravidel. Kolize hashovac´ı funkce tedy slouˇz´ı k tomu, aby se vˇsechna pseudopravidla mapovala pr´avˇe na pravidlo kter´emu odpov´ıdaj´ı. V´yjimkou jsou pakety neodpov´ıdaj´ıc´ı ˇz´adn´emu pravidlu. Pro nˇe nen´ı v´ysledek hashovac´ı funkce oˇsetˇren, ale hashovac´ı funkce pˇresto vˇzdy vr´at´ı nˇejak´y v´ysledek, tedy vˇzdy oznaˇc´ı nˇekter´e pravidlo. Tuto potenci´aln´ı chybu lze odstranit prost´ym porovn´an´ım paketu proti oznaˇcen´emu pravidlu. 12
Obr´azek 15: Sch´ema algoritmu PHCA. Z´avˇereˇcn´e porovn´an´ı paketu proti vybran´emu pravidlu nen´ı zobrazeno.
Dalˇ s´ı optimalizace Algoritmus popsan´y v [11] se d´ale zab´yv´a sniˇzov´an´ım poˇctu pseudopravidel. Vych´az´ı z pozorov´an´ı, ˇze pravidla ˇcasto nedefinuj´ı podm´ınku pro vˇsechna pole z hlaviˇcky paketu. Pˇresnˇeji: Definuj´ı podm´ınku jako libovolnou hodnotu. Pseudopravidla takov´eho pravidla potom mus´ı pokr´yt vˇsechny specifick´e prefixy v dan´em poli. Situace pro dvˇe dimenze (zdrojovou a c´ılovou IP adresu) je naznaˇcena na obr. 16.
Obr´azek 16: Vznik velk´eho mnoˇzstv´ı pseudopravidel z jednoho obecn´eho pravidla Je navrˇzen zobecˇ nuj´ıc´ı v´ypoˇcetn´ı krok, jak´ysi filtr, kter´y zpracov´av´a v´ysledky LPM. Tento krok je vloˇzen jako mezikrok do nˇekter´eho existuj´ıc´ıho algoritmu (obr. 17). Zobecˇ nuj´ıc´ı krok na z´akladˇe definovan´ych zobecˇ nuj´ıc´ıch pravidel nahrazuje specifick´e v´ysledky hodnotou ANY. Tato hodnota reprezentuje libovoln´y prefix, je tedy nejobecnˇejˇs´ı a nejm´enˇe pˇresn´a. Nahrazen´ım doch´az´ı ke ztr´atˇe urˇcit´e informace. Existuj´ı proto omezen´ı na to, kdy lze takov´e nahrazen´ı prov´est, aby bylo st´ale moˇzn´e paket spr´avnˇe klasifikovat. Ve v´ysledku se na v´ystupu zobecˇ nuj´ıc´ıho kroku m˚ uˇze objevit m´enˇe r˚ uzn´ych kombinac´ı neˇz na vstupu, a t´ım doch´az´ı ke zmenˇsen´ı poˇctu pseudopravidel. N´asleduje krok kter´y nˇejak´ym zp˚ usobem mapuje pseudopravidla na pravidla (PHCA, nebo jin´y algoritmus). Protoˇze vˇsak na vstupu tohoto kroku je m´enˇe moˇzn´ych kombinac´ı neˇz bez pouˇzit´ı optimalizace, doch´az´ı v tomto kroku k u ´spoˇre pamˇeti.
13
Obr´azek 17: Vloˇzen´ı zobecˇ nuj´ıc´ıho kroku do v´ ypoˇctu.
4
Shrnut´ı
V tomto technick´em reportu byly pˇredstaveny nˇekter´e z´akladn´ı pˇr´ıstupy ke klasifikaci paket˚ u. Zkoum´ameli vlastnosti uveden´ych algoritm˚ u, zjist´ıme ˇze algoritmy zaloˇzen´e na kart´ezsk´em souˇcinu pol´ı (naivn´ı, DCFL, MSCA a PHCA) se nejv´ıce bl´ıˇz´ı ke konstantn´ı ˇcasov´e sloˇzitosti. Napˇr´ıklad algoritmus PHCA obsahuje tˇri z´akladn´ı kroky: • Operace LPM. Je-li implementov´ana jako stromov´y algoritmus podobn´y trie, m´a sloˇzitost line´arn´ı s poˇctem bit˚ u vstupn´ıho slova. Nicm´enˇe tento poˇcet je konstantn´ı a pˇredem zn´am´y, takˇze lze LPM povaˇzovat za operaci s konstantn´ı sloˇzitost´ı. Nav´ıc existuj´ı algoritmy (napˇr. [4]), kter´e slibuj´ı skuteˇcnˇe konstantn´ı sloˇzitost operace LPM. • Zkonstruovan´a hashovac´ı funkce. Jej´ı vyˇc´ıslen´ı je velice snadn´e, jde o vyˇc´ıslen´ı dvou bˇeˇzn´ych hashovac´ıch funkc´ı, dva pˇr´ıstupy do pamˇeti, a prost´y aritmetick´y souˇcet. Vˇsechny ˇc´asti tohoto kroku maj´ı konstantn´ı ˇcasovou sloˇzitost. • Kontrola. V tomto kroku je nutn´e porovnat paket proti jednomu pravidlu. Jde o trivi´aln´ı operaci s konstantn´ı ˇcasovou sloˇzitost´ı. Protoˇze vˇsechny kroky algoritmu maj´ı konstantn´ı sloˇzitost, lze tvrdit ˇze algoritmus PHCA m´a konstantn´ı ˇcasovou sloˇzitost vyhled´an´ı. Pro uloˇzen´ı vˇsech potˇrebn´ych dat je vˇsak potˇreba pamˇet’, kter´a roste exponenci´alnˇe s poˇctem pravidel (pseudopravidla!). Abychom tedy dodrˇzeli definici sloˇzitosti, je nutn´e uv´est, ˇze ˇcasov´a sloˇzitost vytvoˇren´ı potˇrebn´ych datov´ych struktur je exponenci´aln´ı. Exponenci´aln´ı prostorov´a sloˇzitost je hlavn´ı nev´yhodou tˇechto algoritm˚ u. Bylo nav´ıc dok´az´ano, ˇze je-li ˇcasov´a sloˇzitost vyhled´an´ı konstantn´ı, nem˚ uˇze b´yt prostorov´a sloˇzitost niˇzˇs´ı neˇz exponenci´aln´ı [9]. Protoˇze prostorov´a sloˇzitost m´a tyto sv´e teoretick´e limity, zamˇeˇruje se v´yzkum na moˇznosti praktick´eho sn´ıˇzen´ı potˇrebn´e pamˇeti. Jde o r˚ uzn´e optimalizace st´avaj´ıc´ıch algoritm˚ u, zaloˇzen´e na zkoum´an´ı struktury typick´ych klasifik´ator˚ u. Existuj´ıc´ı optimalizace algoritm˚ u jsou shrnuty v tabulce 5.
Reference [1] Florin Baboescu and George Varghese. Scalable packet classification. In SIGCOMM ’01: Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, pages 199–210, New York, NY, USA, 2001. ACM. [2] Burton Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970.
14
Optimalizace
Vliv na rychlost
Pˇ ridan´ e n´ aroky na pamˇ et’
Rozdˇelen´ı na podmnoˇziny
M˚ uˇze vy´ ustit v n´asobn´ y pˇr´ıstup do tabulky pravidel
Delˇs´ı v´ ysledky LPM, Bloomovy filtry pro kaˇzdou podmnoˇzinu
Mal´a TCAM
Vyhled´an´ı v TCAM prob´ıh´a paralelnˇe s hlavn´ım v´ ypoˇctem
TCAM na pravidla (dlouh´e datov´e slovo)
Zobecˇ nuj´ıc´ı filtr
Vloˇzen´ y krok v pipeline
Nˇekolik mal´ ych CAM na porovn´an´ı v´ ysledku LPM (kr´atk´e datov´e slovo)
Tabulka 5: Zn´am´e pˇr´ıstupy ke sniˇzov´an´ı velikosti potˇrebn´e pamˇeti klasifikaˇcn´ıch algoritm˚ u [3] Zbigniew J. Czech, George Havas, and Bohdan S. Majewski. An optimal algorithm for generating minimal perfect hash functions. Information Processing Letters, 43(5):257–264, 1992. [4] Sarang Dharmapurikar, Praveen Krishnamurthy, and David E. Taylor. Longest prefix matching using bloom filters. In SIGCOMM ’03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, pages 201–212, New York, NY, USA, 2003. ACM. [5] Sarang Dharmapurikar, Haoyu Song, Jonathan Turner, and John Lockwood. Fast packet classification using bloom filters. In ANCS ’06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems, pages 61–70, New York, NY, USA, 2006. ACM. [6] Pankaj Gupta. Algorithms for Routing Lookups and Packet Classification. PhD thesis, Stanford University, 2000. [7] Michal Kajan. Optimalizace klasifikaˇcn´ıch algoritm˚ u zaloˇzen´ych na kart´ezsk´em souˇcinu. diplomov´a pr´ace, FIT VUT, Brno, 2008. [8] T. V. Lakshman and D. Stiliadis. High-speed policy-based packet forwarding using efficient multidimensional range matching. SIGCOMM Comput. Commun. Rev., 28(4):203–214, 1998. [9] Mark H. Overmars and A. Frank van der Stappen. Range searching and point location among fat objects. J. Algorithms, 21(3):629–656, 1996. [10] Viktor Puˇs. Klasifikace paket˚ u s vyuˇzit´ım technologie fpga. diplomov´a pr´ace, FIT VUT, Brno, 2007. [11] Viktor Puˇs, Jan Koˇrenek, and Juraj Blaho. Memory optimization for packet classification algorithms. In ANCS ’09: Proceedings of the 5th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, New York, NY, USA, 2009. ACM. [12] Sumeet Singh, Florin Baboescu, George Varghese, and Jia Wang. Packet classification using multidimensional cutting. In SIGCOMM ’03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, pages 213–224, New York, NY, USA, 2003. ACM. [13] Haoyu Song and John W. Lockwood. Efficient packet classification for network intrusion detection using fpga. In FPGA ’05: Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, pages 238–245, New York, NY, USA, 2005. ACM. [14] V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel. Fast and scalable layer four switching. SIGCOMM Comput. Commun. Rev., 28(4):191–202, 1998.
15
[15] D. Taylor and J. Turner. Scalable packet classification using distributed crossproducting of field labels. In IEEE INFOCOM 2005, 24th Annual Joint Conference of the IEEE Computer and Communications Societies., pages 269–280, July 2005. [16] David E. Taylor. Survey and Taxonomy of Packet Classification Techniques. Washington University in Saint Louis, 2004.
16
