Binary search on range of IPv6 prefix sets - Yu CUI; Zhi-hong TIAN; GHong-li ZHAN; Bin-xing FANG (Tongxin xuebao)
The general and special types of IPv6 routing algorithms were studied.Focusing on the imbalance problems in lookup and update process in routing algorithm,a novel method called BSRPS (binary search on range of prefix sets) was presented.By range-partition (K) and set-partition (M) on routing table (N),and self-recovery after updating,this method enhanced the lookup speed and reduced the impact of imbalance in updating.Time complexity in lookup and update process is O(log2N/K) and O(log2N/K+2M),and space complexity is O(K+2N) where N is the size of routing table.Experiment re-sults show that this method is efficient in lookup and reduces the impact of imbalance after updating effectively.