2003 | OriginalPaper | Buchkapitel
The Bitmap Trie for Fast Prefix Lookup
verfasst von : Seunghyun Oh, Yangsun Lee
Erschienen in: Web and Communication Technologies and Internet-Related Social Issues — HSI 2003
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
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
This paper introduces a new data structure to perform forwarding lookups at Gigabit speed by condensing the forwarding table of backbone routers to fit into cache, eliminating slow memory accesses. The proposed structure bases on the conventional trie, which is good at partial string search. Each link in the proposed trie denotes some portion of IP address and a node also holds a pointer to a routing entry when the entry’s destination is equal to the concatenation of IP prefixes assigned over the link path down to the node. For reduction of the trie’s size, our trie encodes a set of child and routing entry pointers as a bit array where a single bit represents a pointer. So, we call this proposed structure bitmap trie. The experiments show that the bitmap trie compacts backbone routing table small enough for 512Kbyte L2 cache.