X. Chen and J. Shen (USA)
bit string, IP address, prefix matching, range, routing table
With the rapid expansion of the Internet, it is increas ingly important that the Internet provides adequate perfor mance. High speed packet forwarding is withheld by in creasing routing table sizes (due to increased number of hosts) and increasing address sizes in the routing table (due to the transition to IPv6). To improve packet forwarding rates, a bottleneck is IP address lookup in a routing ta ble. Many algorithms have been put forward to make IP address lookup faster. However, none of them discusses multiple IP address lookups in a routing table. In this pa per, we will present two efficient algorithms to address this issue. Our approach improves the IP lookup speed by re ducing the number of comparisons between IP addresses and the addresses in a routing table. It is proved that when 4m < n 8m, the second algorithm needs the least num ber of comparisons than all other existing algorithms. The comparison of the two algorithms is also conducted.
Important Links:
Go Back
