Routen-Hashing

29/05/2008 - 01:22 von Grünther Meyer | Report spam
Hat jemand Informationen darüber wie Router die einen hohen Paket
-Durchsatz erreichen müssen das Mapping IP-Adresse zu Interface effi-
zient durchführen? Wenn die Pràfixe der verschiedenen Routen jeweils
gleiche Lànge hàtten, dann könnte man diese ja einfach hashen, aber
da das nicht so ist muss man eine andere Lösung finden.
Ich hab mir mal gedacht, dass man das ganze über einen Trie-Suchbaum
([1]) realisieren könnte. Wenn man jede Ebene des Tries über acht Bit
der IPv4-Adresse indizieren würde, dann wàr man spàtestens nach vier
Lookups beim Ziel-Mapping; d.h. diese spezielle Art des Tries würde
eine vorzeitige Terminierung der Suche erlauben wenn ein Eintrag in
diesem in ein einzelnes Pràfix fallen würde. Natürlich kann es aber
auch andererseits passieren, dass man für ein Pràfix mehrere Eintràge
im Trie hàtte wenn die Lànge des Pràfix nicht glatt durch acht divi-
dierbar wàre. Weiter könnte man die Sache noch verfeinern indem man
die Tiefe der einzelnen Ebenen an die Verteilung der Pràfixe anpasst.


[1] http://de.wikipedia.org/wiki/Trie

BTW: Um unproduktiven Diskussionen vorzubeugen bitte ich mal in
diesem Thread nicht auf Antworten von Herrn Bosau zu antworten.
Der ist zwar nicht gnz ohne Ahnung, wàre aber in einem Kranken-
haus besser aufgehoben als hier.
 

Lesen sie die antworten

#1 Grünther Meyer
29/05/2008 - 01:28 | Warnen spam
Grünther Meyer schrieb:

Hat jemand Informationen darüber wie Router die einen hohen
Paket-Durchsatz erreichen müssen das Mapping IP-Adresse zu
Interface effizient durchführen? ...



Ach, ich glaub ich hàtte hàtte einfach mal nach "Trie Routing
-Table" googlen sollen. Das was für mich so nacheliegend aus-
sah ist wohl Standard.

Ähnliche fragen