[cisco] Re: how routing works, bit level

On Thursday 30 October 2003 16:45, you wrote:
> Suna foarte bine in teorie, dar in practica nu face asa (sau nu mai face),
> pentru ca dureaza prea mult. Exista o carte care se cheama IOS Software
> architecture, vezi la capitolul CEF. De fapt iti genereaza dinainte un
> arbore cu toate combinatiile posibile de ip-uri, pe care adauga pentru
> toate destinatiile pe care le cunoaste headerele de layer2(si 3?) pentru
> interfata pe care tre sa plece pachetul . Asa nu face decat sa
> caute intr-un arbore binar (era 4-way parca?), fara sa mai faca 100 de
> comparatii pe masca. Cum ai zis tu probabil ca face linuxul, si in plus
> mai tine si un cache. Devine mai complicat cand ai mai multe tabele de
> rutare :)

Well, problema cea mai mare e accesul la liste. Cel mai bun algoritm e cel cu 
hash tables, dar pentru intrari multe, nu prea da roade fara o functie buna 
de hash si fara o dimensiune mare a tabelei. Din aceasta cauza, se 
implementeaza mai bine pe algoritmi binary tree. Pe hash tables, in mod 
ideal, complexitatea e O(1) !. In cazul ideal un btree are O(log n). Insa cum 
ajunge ca adresele/retelele sa fie bagate in aceste tablele si cum le 
acceseaza, nu stiu.