Dynamic routing tables using simple balanced search trees

Yeim-Kuan Chang, Yung Chieh Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationInformation Networking
Subtitle of host publicationAdvances in Data Communications and Wireless Networks - International Conference, ICOIN 2006. Revised Selected Papers
PublisherSpringer Verlag
Pages389-398
Number of pages10
ISBN (Print)3540485635, 9783540485636
Publication statusPublished - 2006 Jan 1
EventInternational Conference on Information Networking, ICOIN 2006 - Sendai, Japan
Duration: 2006 Jan 162006 Jan 19

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3961 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherInternational Conference on Information Networking, ICOIN 2006
CountryJapan
CitySendai
Period06-01-1606-01-19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Dynamic routing tables using simple balanced search trees'. Together they form a unique fingerprint.

Cite this