ABSTRACT
In the Internet, there are two fundamentally important access patterns: Independently skewed access patterns and bursty access patterns. In a tree data structure, if a recently accessed leaf node is moved up to the root, the next access time should be shorter than the last. In the data structure-trie, the accessed time of each node depends on the level in which it is, and the average time for all nodes is related to the distribution of the levels of all nodes and the frequency with which all nodes are accessed. When a routing table tree can be represented as a set of tables, a route lookup can be cast as a table lookup, where a single table is indexed by the destination address to yield the routing entry. If the internet protocol address space precludes a single table, then it will produce a large table. Such large memories are impractical, expensive, and slow.
