Research And Design Of Routing Lookup Algorithm Based On IPv6

The data transmission speed in the link has reached 400Gbps with the rapid development of Internet technologies,which leads to a great increase in the throughput of the routers and workloads of searching for the best export.What limits current data throughput of the Internet is routers' speed of transmitting datagram,namely,the rate of route forwarding.It is the key in the process of route forwarding is routing lookup.Therefore,it is necessary to design a suitable routing lookup algorithm.Compared with IPv4,the address length of IPv6 is longer,which means that the number of IPv6 routing table items will be more,and the search algorithm based on the IPv4 prefix length cannot be directly extended to IPv6.This paper launches around the routing lookup algorithm based on IPv6,a routing lookup algorithm that is suitable for the current routing table and a routing lookup algorithm that is suitable for the large-scale IPv6 routing table are given.The main work are as followed:1.Unicast address of IPv6 is analyzed in this chapter,as well as the distribution characteristics of current backbone router routing table.Then an IPv6 routing lookup algorithm based on B-tree and Bloom Filter(BTBF)is proposed.Two-three tree is used in BTBF to find the prefix 16bits value.Then,according to the mapping of an array in two-three tree node,the next lookup is forwarded to the Bloom Filter.Finally,the Bloom Filter is adopted to count the array's values,and the next hop is extracted through mapping.Simulation results show that compared with other tree-based and Bloom Filter based algorithms,BTBF can effectively reduce search time and storage occupation,and maintain stable search performance even if the number of routing entries changes greatly.2.Since that binary-based Trie data structure is difficult to find in large-scale IPv6 routing table,the prefix interval is introduced to adapt to the construction of large-scale dynamic IPv6 routing table data structure.An IPv6 routing lookup algorithm combining segment table and B-tree is proposed.The prefix items in the routing table are firstly divided into a prefix Index?(P)and a suffix Suffix?(P).Meanwhile,Indexa(P)is stored in the segment table,and link it to B-tree.Then,look for the suffix Su)fix?(P)in the B-tree.This strategy effectively reduces the amount of nodes in B-tree searching process,decreases search depth and improves search efficiency.Experimental results show that this algorithm is superior to other Trie-Tree searching algorithms based on prefix intervals in searching time,and can meet the large-scale routing table search performance.We carry on the exploration and improve the routing lookup algorithm and a lot of excellent thought integrated into the algorithm.