Study Of Algorithms For Fast IP Lookups Based On Bloom Filters

In recent years, with the rapid development of Internet, communicating through Internet has been applied by more and more people, which make network services increasing sharply. Statistics show that network traffic, bandwidth of the Internet and router interface speed increases double every six months. And thus the number of packets, the backbone routers per second forward to the router, also increase, which has brought great challenges. In the working process of the router, route table lookup process is the most time-consuming step. Therefore, whether routing lookup algorithm is good or not has a direct impact on the performance of the router. So routing lookup algorithm is a hot research topic in recent years.Firstly, the related basic technology about IP lookups algorithms is studied.(1) For the Classless Inter-Domain Routing technology, the cause for emergency is discussed at first, and then the basic theory is introduced.(2) For IPv6technology, the advantages are analyzed firstly, and then the address structure is introduced.(3) In view of the Bloom filters, the basic principle of technology and performances indexes are studied in detail, and then the analysis for the typical modified Bloom filters is proposed.Secondly, a fast longest prefix match IP lookups algorithm based on Bloom filters is proposed. In this algorithm these are three parts, a first byte index table which is built by routing table, a group of Bloom filters used to store and query different prefixes information, and a group of routing index tables for packets forwarding, are involved. For the destination IP address, the first bytes information at first is extracted and all possible prefix lengths are found out. And then the prefix lengths in the corresponding Bloom filters are searched. According to the Matching results of Bloom filters, in the routing index table, the corresponding routing is selected for packet forwarding at last. Performance analyses are developed aim at time and space complexity. Numerical analysis and experimental results show that the algorithms are able to implement linear IP lookups, and time complexity performance has improved significantly than the previous algorithms.Finally, an IP lookups algorithm for global aggregated unicast IPv6address in backbone IPv6routers is proposed. This algorithm is based on Bloom filters and controllable prefix extension technology. According to the distribution characteristics of global aggregated unicast IPv6address, the IPv6prefix is expanded to24bits,32bits48bits and64bits respectively. A Bloom filter group which contains three Bloom filters is applied to store IPv6prefix of32bits,48bits and64bits, and meanwhile a direct index array is used to store prefix information of 24bits. For the destination IP address, firstly prefix information in Bloom filter group and direct index array are queried, and then the routing index table according the querying results is searched, and thus the packets are forwarded at last. Aiming at the time cost and the routing index table detect numbers per IP lookups, experimental analyses are carried on. Numerical analyses and experimental results show that the algorithm has the ability to obtain good time and space performance when the parameters of Bloom filter group are reasonable.