An IPv6 routing lookup algorithm using weight-balanced tree based on prefix value for virtual router

Lingjiang Chen; Shuguang Zhou; Qiaoduo Zhang; Fenghua Li

doi:10.1117/12.2262546

7 October 2016 An IPv6 routing lookup algorithm using weight-balanced tree based on prefix value for virtual router

Lingjiang Chen, Shuguang Zhou, Qiaoduo Zhang, Fenghua Li

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.

Citation Download Citation

Lingjiang Chen, Shuguang Zhou, Qiaoduo Zhang, and 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); https://doi.org/10.1117/12.2262546

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available