2.2 TRIE-BASED ALGORITHMS 29 Lookup Speed.The explosive growth of link bandwidth requires faster IP lookups.For example,links running at 10 Gbps can carry 31.25 million packets per second(mpps) (assuming minimum sized 40-byte IP packets). Storage Requirement.Small storage means fast memory access speed and low power consumption,which are important for cache-based software algorithms and SRAM (static RAM)-based hardware algorithms. Update Time.Currently,the Internet has a peak of a few hundred BGP(Border Gateway Protocol)updates per second.Thus,a certain algorithm should be able to perform 1k updates per second to avoid routing instabilities.These updates should interfere little with normal lookup operations. Scalability.It is expected that the size of forwarding tables will increase at a speed of 25k entries per year.Hence,there will be around 250k entries for the next five years. The ability of an algorithm to handle large forwarding tables is required. Flexibility in Implementation.Most current lookup algorithms can be implemented in either software or hardware.Some of them have the flexibility of being implemented in different ways,such as ASIC,a network processor,or a generic processor. 2.2 TRIE-BASED ALGORITHMS 2.2.1 Binary Trie A trie structure is a multi-way tree where each node contains zero or more pointers to point its child nodes,allowing the organization of prefixes on a digital basis by using the bits of prefixes to direct the branching.In the binary trie(or 1-bit trie)structure [5],each node contains two pointers,the 0-pointer and the 1-pointer. Data Structure.A node X at the level h of the trie represents the set of all addresses that begin with the sequence of h bits consisting of the string of bits labeling the path from the root to that node.Depending on the value of the (h+1)th bit,0 or 1,each pointer of the node X points to the corresponding subtree (if it exists),which represents the set of all route prefixes that have the same(h+1)bits as their first bits.An example data structure of each node (i.e.,the entry in a memory)is shown in Figure 2.6,including the next hop address (if it is a prefix node),a left pointer pointing to the left node location (with an address bit 0) and a right pointer pointing to the right node location (with an address bit 1). A prefix database is defined as a collection of all prefixes in a forwarding table.A prefix database example is shown in Figure 2.6 [6],where the prefixes are arranged in an ascending order of their lengths for easy illustration. To add a route prefix,say 10111*,simply follow the pointer to where 10111 would be in the trie.If no pointer exists for that prefix,it should be added.If the node for the prefix already exists,it needs to be marked with a label as being in the forwarding table(for example,Pi).The nodes in gray are prefix nodes.When deleting a route prefix that has no children,the node and the pointer pointing to it are deleted and the parent node is examined. If the parent node has another child or it is a gray node,it is left alone.Otherwise,that node is also deleted and its parent node is examined.The deletion process is repeated up to the trie until a node that has another child or a gray node is found.2.2 TRIE-BASED ALGORITHMS 29 Lookup Speed. The explosive growth of link bandwidth requires faster IP lookups. For example, links running at 10 Gbps can carry 31.25 million packets per second (mpps) (assuming minimum sized 40-byte IP packets). Storage Requirement. Small storage means fast memory access speed and low power consumption, which are important for cache-based software algorithms and SRAM (static RAM)-based hardware algorithms. Update Time. Currently, the Internet has a peak of a few hundred BGP (Border Gateway Protocol) updates per second. Thus, a certain algorithm should be able to perform 1k updates per second to avoid routing instabilities. These updates should interfere little with normal lookup operations. Scalability. It is expected that the size of forwarding tables will increase at a speed of 25k entries per year. Hence, there will be around 250 k entries for the next five years. The ability of an algorithm to handle large forwarding tables is required. Flexibility in Implementation. Most current lookup algorithms can be implemented in either software or hardware. Some of them have the flexibility of being implemented in different ways, such as ASIC, a network processor, or a generic processor. 2.2 TRIE-BASED ALGORITHMS 2.2.1 Binary Trie A trie structure is a multi-way tree where each node contains zero or more pointers to point its child nodes, allowing the organization of prefixes on a digital basis by using the bits of prefixes to direct the branching. In the binary trie (or 1-bit trie) structure [5], each node contains two pointers, the 0-pointer and the 1-pointer. Data Structure. A node X at the level h of the trie represents the set of all addresses that begin with the sequence of h bits consisting of the string of bits labeling the path from the root to that node. Depending on the value of the (h + 1)th bit, 0 or 1, each pointer of the node X points to the corresponding subtree (if it exists), which represents the set of all route prefixes that have the same (h + 1) bits as their first bits. An example data structure of each node (i.e., the entry in a memory) is shown in Figure 2.6, including the next hop address (if it is a prefix node), a left pointer pointing to the left node location (with an address bit 0) and a right pointer pointing to the right node location (with an address bit 1). A prefix database is defined as a collection of all prefixes in a forwarding table. A prefix database example is shown in Figure 2.6 [6], where the prefixes are arranged in an ascending order of their lengths for easy illustration. To add a route prefix, say 10111*, simply follow the pointer to where 10111 would be in the trie. If no pointer exists for that prefix, it should be added. If the node for the prefix already exists, it needs to be marked with a label as being in the forwarding table (for example, Pi). The nodes in gray are prefix nodes. When deleting a route prefix that has no children, the node and the pointer pointing to it are deleted and the parent node is examined. If the parent node has another child or it is a gray node, it is left alone. Otherwise, that node is also deleted and its parent node is examined. The deletion process is repeated up to the trie until a node that has another child or a gray node is found