Trie-based Observations on the Routing Tables

Trie is a data structure that is widely used in the algorithms for routing table lookup. Usually, the structure and characteristics of the routing table are first examined, and then the efficient and effective trie-based algorithms are designed to speed up the time-critical path of packet processing in routers. This paper, on the contrary, uses a binary trie to make observations on the backbone BGP routing tables of both IPv4 and IPv6. Following some new terms and definitions, we use the statistical features of the trie to reveal the characteristics of the routing tables, such as route redundancy, route hierarchy etc. Particularly, some of the most significant evaluation metrics of the routing table lookup algorithms, such as worst case and average case memory access times per lookup for both successful and unsuccessful lookups, are concluded using different types of nodes in the trie