IP Address Lookup in an IP Router Based On a Reorganized Binary Prefixes Value Tree (RBPVT)

IP address lookup to route data packets is an important function in a router and improving this function improves the overall performance of the router. From the data structures used for the prefixes representation, there are the trees that represent prefixes with their binary values. However, this data structure requires an improvement because of the longest prefix function search complexity. Our approach is used to improve the routing information search time in the prefixes values binary tree by periodically reorganizing the tree according to the use of prefixes; the most recently used prefixes are stored in the higher levels of the reorganized binary prefixes value tree (RBPVT) which improves the data packets routing time. The tests and evaluation of the access memory number of the longest prefix match search algorithm shows that the IP address lookup algorithm based on our RBPVT tree improves the performance of the IP routers in terms of average memory access number.