Faster Rebuilding Of Multi-bit Trie For Virtual Routers

Virtual Router, as a logical unit, refers to the function simulation of physical router in thesoftware layer and hardware layer. Each virtual router has both routing table and addressforwarding table which are independent logically, so that different address space of virtualprivate network can be reused. And the isolation of the internal routing and transmitting canbe ensured. Although it can speed up the process of looking up and transmitting, it hasaggravated the problem of frequent routing update that has originally existed. On the otherhand, routing lookup (or IP lookup) is the core function of routing transmitting and datapacket filtering. And its performance directly affects the total rate of the router throughput,but it usually has a bad influence on the function of lookup by frequent updates. The currentrouting update method generally includes two parts, one is on-line update and the other isoff-line update. The paper considers the search way and routing table’s organization by themulti-bit trie structure. So, it is the key to develop the update efficiency how to speed up theprocess of rebuilding and decrease the influence on the lookup.This paper proposes the faster rebuilding of Multi-bit Trie for Virtual Routers: throughmining the rule of correspondence among the memory block, we map the information ofreal-time updates from the uni-bit trie to the multi-bit trie. By this way we needn’t reread thedata and expand the prefixes, and it greatly speeds up the update process. The experimentalresults show that: for the IPv4and IPv6routing table, this method improves the updateefficiency of at least45.2%and23.1%.Based on the above, the paper also presents a new on-line update mode: in the process ofconstructing a multi-bit trie, disposing each block memory on-line in the free time as soon asit is completed, by which way to quicken the update process. The experimental results showthat: for the IPv4and IPv6routing table, this method improves the efficiency of updating atleast34%and44%.For summarized, this paper puts forward a new method to improve the update efficiencyof router, which has a certain theoretical significance and application value.