An IPv6 address lookup algorithm based on recursive balanced multi-way range trees with efficient search and update

摘要: Internet routers forward packets based on the destination address of packet. A packet's is matched against prefixes stored in router forwarding table, and packet sent to output interface determined by Longest Matching Prefix (LMP). migration from IPv4 IPv6 has introduced more challenge IP lookup problem. Nowadays, there are some existing algorithms working well for addresses, however, none current schemes scales both update speed. As uses 128 bit whose time grows with length, such as patricia or multi- tries, become less attractive. In this paper, we propose a new scheme worst case search O(logN), where N number table. Since updates irrelevant promising IPv6. This novel data structure, called recursive balanced multi-way range trees, which able achieve optimal binary search, can also be updated logarithmic when prefix added deleted. Intensive experiments have been done evaluate proposed algorithm. The results show that our outperforms all terms Moreover, small storage requirement (2N nodes), suggests algorithm approach lookup.