Share Email Print

Proceedings Paper

An IPv6 routing lookup algorithm using weight-balanced tree based on prefix value for virtual router
Author(s): Lingjiang Chen; Shuguang Zhou; Qiaoduo Zhang; Fenghua Li
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 7 October 2016
PDF: 6 pages
Proc. SPIE 9902, Fourth International Conference on Wireless and Optical Communications, 99020Z (7 October 2016); doi: 10.1117/12.2262546
Show Author Affiliations
Lingjiang Chen, Institute of Information Engineering (China)
Shuguang Zhou, Institute of Information Engineering (China)
Qiaoduo Zhang, Institute of Information Engineering (China)
Fenghua Li, Institute of Information Engineering (China)

Published in SPIE Proceedings Vol. 9902:
Fourth International Conference on Wireless and Optical Communications
Maode Ma, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?