A Fast IP Lookup Algorithm Based On Pivot-pushing And Bloom Filter

With the rapid development of computer and communication technology,the scale of the network is expanding.Internet users put forward higher requirements regarding network bandwidth.The network bandwidth relies heavily on the speed of router routing and packet forwarding.The router searches the route based on the destination IP address of the packet to be forwarded and queries the next-hop pointer in the forwarding information base(FIB)according to the longest prefix matching rule.The memory and CPU resources of a router are limited,with the increasing number of FIB entries,the design of an efficient and accurate IP lookup algorithm became a necessity due to its vital role in improving the overall speed of the router."Longest prefix matching using bloom filters(referred to as PBF algorithm)" is an efficient algorithm that applies Bloom Filter and Trie-tree to IP lookup,but because Bloom Filter has "false positive",it must contrast the prefixes investigated by Bloom Filters(the prefixes are called "candidate prefixes")to the FIB on the off-chip and find the prefix with the longest length,which affects the efficiency of IP lookups,and while the number of FIB entries is increasing,the PBF algorithm's efficiency will be decreasing.In order to detect fewer candidate prefixes than PBF algorithm,reduce the number of unnecessary off-chip memory accesses caused by Bloom filter false positive and improve the speed of IP lookup,this paper proposes and implements a fast IP lookup algorithm based on pivot-pushing and Bloom Filter(referred to as PP&BF algorithm).The PP&BF algorithm performs a pivot-pushing operation on a layer of the original Trie-tree(assumed to be the p-layer)based on the FIB table,which is used to optimize the Trie-tree.When performing an IP lookup,the return value of the Bloom Filter constructed on the p-layer "hollow node"(the network prefix represented by the hollow node does not exist in the FIB table)can detect the range of the longest match prefix in the FIB table,select fewer candidate prefixes than PBF algorithm,reduce the number of unnecessary off-chip memory access and improve the speed of routing lookup.After the test and theoretical analysis to determine the optimal value of the parameter p,completing the comparative tests between PBF algorithm and the PP&BF algorithm proposed in this paper.The experimental results show that the query efficiency of PP&BF algorithm is better than that of PBF algorithm;Under the premise that the average number of off-chip access is less than 1.003,It was shown that the PP&BF algorithm can save more than 10% of the on-chip memory space compared with the PBF algorithm.