“Grådig” routing kan forbedre internetrouting

For at datapakker kan nå fra punkt A til punkt B (f.eks. fra en pc til en web-server), skal pakkerne routes; der skal bestemmes en sti, som denne pakke skal tage, en beslutning der normalt ville kræve, at routeren i teorien har viden om alle IP’er i verden – sådan fungerer routing i dag.

Nu er to forskere dog kommet frem med en påstand om, at “grådig” routing dramatisk kan forbedre routningshastigheden. Normalt vil den korteste afstand mellem to punkter kræve kendskab til den overordnede struktur af netværket, men det har forskerne fundet ud af, ikke er nødvendigt.

Idéen er, at i stedet for at slå op i lange lister over ip-adresser, så vælges den hurtigste vej ved kun at kigge på den underliggende afstand mellem nabo-routere og destinationen. Det kan lade sig gøre, fordi internettet er så komplekst som det er. Der eksisterer et sammenfald mellem højt rangerende routere og afstanden mod destinationen.

Idéen om grådig routning, som kan læses i nærmere detalje ved at følge linket til kilden, vil kunne mindske den interne kommunikation mellem routere, der sker, når de konstant holder hinanden opdateret om, hvordan internettet ser ud fra deres “synspunkt”.

Dmitri Krioukov skrev:

Routing in the Internet today requires global topological awareness for all routers, which involves enormous and ever-growing inter-router communication overhead. […] With greedy routing, global topology knowledge is not needed, so that this overhead would be removed, and routing would scale and work much better.