slozitost filtrovacich pravidel (Re: HTB a 2Mb linka)

Pavel Kankovsky peak na argo.troja.mff.cuni.cz
Čtvrtek Červen 17 14:54:26 CEST 2004


On Wed, 16 Jun 2004, Zdenek Kaminski wrote:

> > Jestli se tech 2000 pravidel muselo projit pro kazdy jednotlivy paket, tak
> > to urcite 100 Mbitu nezvladalo.
> 
> Nu, bylo to nakaskadovano samozrejme... Tusim, ze nejdelsi retezec, ktery 
> se prochazel, byl cca 8, nejkratsi pak 4? Uz je to davno...

Pri pruchodu pravidlem jsou prave dve ruzne moznosti, jak pokracovat. (*)
Cili pokud mame v sade pravidel pouze retezce delky max. 8, pak to
znamena, ze je tam pouze maximalne (2^l - 1) N dosazitelnych pravidel, kde
N je pocet ruznych vstupnich bodu a l delka nejdelsi cesty. No...hmm...to
by nevychazelo, protoze existuji maximalne tri ruzne zpusoby pruchodu
paketu (dovnitr na lokal, ven z lokalu a skrz), cili N je 3 a vysledek je
max. 765. To je vyznamne mene nez 2000.

A to zanedbavame mozna vnitrni omezeni na rozvetveni stromu, pokud by byla
pravidla ve vice po sobe sekvencne pouzitych chainech (napr. PREROUTING a
INPUT), a take ignorujeme tvrzeni, ze nektere cesty mely byt kratsi nez 8,
coz pocet moznosti jeste dale redukuje.

(*) Aspon pokud se nepouzije nejake nestandardni reseni typu "skoc na
chain jmenem bla-X.Y.Z.W, kde za X.Y.Z.W dosadis IP adresu cile".

Mimochodem, zkousel nekdo nejake reseni zefektivnujici slozite sady
pravidel? Zatim jsem nasel ippool/ipset (v patch-o-maticu netfilteru),
ktery umoznuje udrzovat mnoziny IP adres pouzit pritomnost adresy
v mnozine jako podminku pro pravidlo, coz se hodi, pokud potrebuju nejake
konkretni pravidlo aplikovat na ruzne adresy. A take to umi tu mnozinu
pruzne za chodu menit. Ale z toho provedeni mam trochu rozporuplne pocity.

Krome toho by se obcas hodilo neco jineho, totiz podle adresy (prip.
jineho udaje, napr. portu) se rychle rozvetvit na ruzne chainy. Da
se to nasimulovat nejakym vicemene binarnim stromem, ale furt je to
log_2 n kroku v kazde vetvi (ackoli nejakou hasovaci tabulkou by slo
dosahnout O(1)) a navic se tam musi vyrobit n/2 pomocnych "vyhybkovych
pravidel". Sice to jde udelat automaticky, ale stejne je v tom pak
zbytecny bordel.

--Pavel Kankovsky aka Peak  [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."



Další informace o konferenci Linux