7 October 2016 An IPv6 routing lookup algorithm using weight-balanced tree based on prefix value for virtual router
Author Affiliations +
Proceedings Volume 9902, Fourth International Conference on Wireless and Optical Communications; 99020Z (2016) https://doi.org/10.1117/12.2262546
Event: Fourth International Conference on Wireless and Optical Communications, 2016, Beijing, China
Abstract
Virtual router enables the coexistence of different networks on the same physical facility and has lately attracted a great deal of attention from researchers. As the number of IPv6 addresses is rapidly increasing in virtual routers, designing an efficient IPv6 routing lookup algorithm is of great importance. In this paper, we present an IPv6 lookup algorithm called weight-balanced tree (WBT). WBT merges Forwarding Information Bases (FIBs) of virtual routers into one spanning tree, and compresses the space cost. WBT’s average time complexity and the worst case time complexity of lookup and update process are both O(logN) and space complexity is O(cN) where N is the size of routing table and c is a constant. Experiments show that WBT helps reduce more than 80% Static Random Access Memory (SRAM) cost in comparison to those separation schemes. WBT also achieves the least average search depth comparing with other homogeneous algorithms.
© (2016) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Lingjiang Chen, Lingjiang Chen, Shuguang Zhou, Shuguang Zhou, Qiaoduo Zhang, Qiaoduo Zhang, Fenghua Li, Fenghua Li, } "An IPv6 routing lookup algorithm using weight-balanced tree based on prefix value for virtual router", Proc. SPIE 9902, Fourth International Conference on Wireless and Optical Communications, 99020Z (7 October 2016); doi: 10.1117/12.2262546; https://doi.org/10.1117/12.2262546
PROCEEDINGS
6 PAGES


SHARE
Back to Top