2006 | OriginalPaper | Buchkapitel
Dynamic Routing Tables Using Simple Balanced Search Trees
verfasst von : Yeim-Kuan Chang, Yung-Chieh Lin
Erschienen in: Information Networking. Advances in Data Communications and Wireless Networks
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Various schemes for high-performance IP address lookups have been proposed recently. Pre-computations are usually used by the special designed IP address lookup algorithms to improve the lookup speed and reduce the memory requirement. However, the disadvantage of the pre-computation based schemes is when a single prefix is added or deleted, the entire data structure may need to be rebuilt. Rebuilding the entire data structure seriously affects the lookup performance of a backbone router, and thus is not suitable for dynamic routing tables. In this paper, we develop a new dynamic routing table algorithm. The proposed data structure consists of a collection of balanced binary search trees. The search, insertion, and deletion operations can be finished in
O
(log
N
) time, where
N
is the number of prefixes in a routing table. Comparing with the best existing dynamic routing table algorithm, PBOB (Prefix Binary tree On Binary tree), our experiment results using the real routing tables show that the proposed scheme performs better than PBOB in terms of the lookup speed, insertion time, deletion time, and memory requirement.