[cisco] Re: how routing works, bit level

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 :)


On Wed, 29 Oct 2003, Claudiu C. wrote:

> > cum face un ruter (cisco in particular si/sau altul) selectia rutei din
> > tabela, dar la nivel de algoritm intern.
> > adica el are la dispozitie o adresa de retea si masca de retea, si adresa
> > destinatie, cum "scaneaza" tabela de rutare si ce operatii
> > (and,or,xor,if...) face ca sa decida.
> > apoi avand in vedere si cazul in care exista mai multe matchuri posibile
> > pentru adresa respectiva, dar se alege chea mai exacta.
> 
> Intre adresa de IP destinatie, cat si a lui, face AND cu netmask-ul.
> 
> Din tabela de routare are prioritate routa cu netmask-ul care da spre o retea 
> cu cea mai mica parte de host (Adica /27 e inaintea unui /26).
> 
> Algoritmii de selectie din tabela sunt, in cel mai probabil caz, bazat pe 
> tabele hash sau pe binary tree (gandeste-te ca in tabela de routare sunt mii 
> sau zeci de mii de route).
> 
> 1.1 -- 1.2 ------ 1.20 <> 2.30 ------ 2.2 -- 2.1
> 255.0                     255.0
> 
> Un router, cat si un host, procedeaza cam in felul asta:
> 
> calculeaza adresa de retea dupa "retzeta": IP AND NETMASK. In cazul de mai 
> sus, pentru este 1.0, respectiv 2.0
> 
> Presupunem ca 1.1 vrea sa trimita pachet catre 1.2
> 
> adresa destinatie AND netmask propriu = 1.0
> adresa proprie    AND netmask propriu = 1.0
> 
> adresele de retea sunt egale ? DA =>
> afla adresa MAC de la 1.2 si incapsuleaza pachetul intr-un frame si-l pune pe 
> ethernet.
> 
> Presupunem ca 1.1 vrea sa trimita pachet catre 2.2
> 
> adresa destinatie AND netmask propriu = 2.0
> adresa sursa      AND netmask propriu = 1.0
> 
> adresele de retea sunt egale ? NU =>
> afla adresa MAC de la 1.20 (care e configurat ca gateway pe 1.1) si trimte 
> frame catre el.
> 
> Router-ul nostru ia pachetul, se uita la adresa destinatie. De aici, ceea ce 
> presupun este cam asa (nu stiu daca e corect, nu am studiat code-ul):
> 
> - face AND intre IP destinatie si netmask-ul cu cel mai mare nr de biti de 
> retea (cu cele mai putine host-uri) pe care-l are in tabela.
> 
> - ii rezulta o adresa de retea pe care o cauta in tabela lui (de sus in jos, 
> dar nu cred ca merge secvential - si nu merge sigur secvential - ci prin 
> hash-uri sau prin binary trees). Daca nu gaseste, ia urmatoarea mask, samd 
> pana ii gaseste destinatie.
> 
> - daca nu ii gaseste destinatie, si are default gateway setat, il trimite mai 
> departe catre default.
> 
> In cazul nostru va gasi ca 2.0 se duce pe interfata cu 2.30, afla MAC si 
> arunca frame-ul pe ethernet de unde e "ridicat" de catre 2.1
> 

-- 
-------------------------
Dan Nae
Romanian Education Network
Bucharest NOC