LPR-Trie:A,Fast,IPv6,Routing,Lookup,Algorithm,with,Virtual,Nodes

Wenlong Chen,Diya Liu,Jiacheng Wang,Xiaolan Tang

The College of Information Engineering,Capital Normal University,Beijing 100048,China

*The corresponding author,email:tangxl@cnu.edu.cn

Abstract:The number of IPv6 routes in todays backbone routers has grown rapidly,which has put tremendous pressure on route lookup and storage.Based on the analysis of IPv6 address prefx length and distribution characteristics,this paper proposes an IPv6 route lookup architecture called LPR-Trie.The core idea of the algorithm is to utilize more spaces and accelerate routing lookup.Moreover,we put forward the concept of virtual nodes,and leverage the link between virtual nodes and ordinary nodes to accelerate routing lookup.We provide the longest prefx routing entry(LPR)calculation algorithm to achieve the longest prefx match.The experimental results show that the virtual node mechanism increases the search speed up to 244%,and the virtual nodes have better stability by setting an appropriate keep-alive time according to the characteristics of actual traffc.This paper shows that our design improves the routing lookup speed and have better memory utilization.

Keywords:IPv6;route lookup;longest prefx match;virtual node;Trie

WITH the continuous growth of the network scale,IPv4 protocol no longer meets the requirement of the Internet.Therefore,IPv6 emerged as the next generation IP protocol.Routing lookup is the process of searching the forwarding table for the destination address according to the longest prefx matching principle and selecting the path.The 128-bit IPv6 address format inevitably results in a very large routing table in the router.High-performance routing lookup algorithms have become the key to improving the router’s forwarding speed.

The routing table search algorithm is mainly evaluated by storage overhead and search speed[1].For the routing table with frequent update,the update performance is also required.As the network throughput increases,the routing table expands exponentially.This trend poses challenges to current routers by requiring higher throughput and larger routing tables.

Most current routing lookup algorithms are designed for IPv4 and cannot be directly applied to IPv6.The algorithms proposed in some related studies can be extended to IPv6,but no exhaustive research has been done.Therefore,we propose the LPR-Trie structure and corresponding search algorithm in accordance with the characteristics of IPv6 addresses and backbone network routing tables.By analyzing the number of routes for each prefx length,we store 64-bit prefx addresses in three layers which achieves high memory utilization.Compared to existing multi-bit Trie trees,we introduce the concept of virtual nodes.The virtual node,as a kind of temporary node,is created when relevant real-time packets come and is destroyed when its keep-alive time expires.Once the IP address matches a virtual node,the LPR algorithm is used to quickly match the corresponding longest prefx routing entries.Compared with ordinary nodes,the number of virtual nodes is small,and has little effect on the overall memory space consumption.

The contributions of our method are summarized as follows.

·We propose an IPv6 route lookup architecture called LPR-Trie and the corresponding lookup algorithm based on the characteristics of IPv6 addresses,which accelerate routing lookup with better memory utilization than existing studies.

·In LPR,a virtual node is created when an IP address cannot match the ordinary nodes,in order to increase the search speed for corresponding IP addresses.Meanwhile,the dynamic creation and deletion of virtual nodes improves the memory utilization.

·We compare our proposed method LPR with TSB[2]by using the current routing table from bgp.potaroo.net.Experimental results show that our search speed is 3.49 times that of TSB,and the memory size occupied by TSB is about 1.5 times that of LPR.

The rest of this article is organized as follows:we present existing methods for IPv6 route lookup in Section II.An overview of the architecture,LPR algorithm and lookup procedure are provided in Section III.In Section IV we introduce the routing update.The experiments and performance analysis are discussed in Section V.Finally,we summarize our work in Section VI.

In general,there are three kinds of algorithms for IP routing lookup:Trie-based,hash-based,and hardware-based methods.Each method has its own advantages and disadvantages.

Trie uses a tree-based data structure that determines the branch of the tree by the value of each bit in the prefx.In the Trie tree,the path from the root node to the node of the n-th layer represents the value of the frst n bits in the string.The traditional Trie tree has a large storage overhead and requires a large amount of memory access operations as the search depth increases.

Multi-branch Trie tree looks up multiple bits at each step,which effectively reduces the number of accesses.In[2],TSB is a three-stage algorithm for IPv6 routing table lookup that uses three data structures:tree,segment table,and route bucket.The frst stage is the root node 2001.The second stage is a segment table or another node linked to the node 2001.The segment table stores the value of 17-32 bits of the destination IPv6 address.The third stage is the routing bucket linked to the segment table or 8 child nodes of node 2001.In[3],the multi-branch Trie tree is combined with the Hash table to divide the IPv6 address space into fve levels:1-32 bits,1-16 bits,33-48 bits,49-64 bits,65-128 bits.The prefx information is stored in 5 hash tables and 3 multi-bit trees.The algorithm starts from frst 32 bits.Hash tables are used in[4]to store address prefx information starting with 0x20,0x24,0x26,0x28,0x2A.At the same time,the 6-5-4 Trie tree is used to store the address prefxes of the three intervals of 33-38,39-43,and 43-47.

For a multi-bit Trie tree,each step of the search process checks multiple bits,so it does not support an address prefx of any length.We need to use the prefx expansion method to convert the address prefx,which will increase the redundancy of the information.For the search method that uses the hash algorithm,we have to face the two problems of the choice of the hash function and the handling of hash conficts.When there are many prefxes in the forwarding table,it is diffcult to fnd a collision-free hash function.This article has carefully studied the characteristics of IPv6 address structure and routing table,and we propose an IPv6 route lookup architecture called LPR-Trie,which combines the Trie tree and the array.Because the array address space is continuous,the corresponding node can be located with one search,which improves routing lookup speed.

Degermark et al.[5]proposed the Lulea algorithm that is a bitmap compression of the Trie tree structure.The 32-layer IPv4 tree structure is divided into 3 layers according to the cutting method of(16-8-8).By cutting,the entire tree is organized into many tree branches.The Lulea algorithm frst uses leaf push to save the node information in the leaf nodes,and then constructs the corresponding bitmap by traversing all the leaf nodes.This algorithm uses a multi-level index table generated offine to achieve fast lookup.Although this algorithm reduces the storage overhead of the data structure,it causes update diffculties,and complex and ineffcient update operations also affects the search performance to a certain extent.Liu et al.[6]proposed a software routing lookup algorithm based on overlapping bitmap compression,which constructs an overlapping bitmap structure through hierarchical traversal,and puts the port information of the tree structure onto a linear forwarding port array(FPA).Instead of using leaf push technology,the hierarchical traversal of the tree is used to ensure the longest prefx match.The array of forwarding ports is divided into groups of equal length,and independent group structures are established for each group.Based on bitmap segmentation,two optimization algorithms,conditional optimization and general optimization,are proposed to further improve the update speed.

Hardware-based algorithms mainly use SRAM and FPGA chips to complete route lookup.Peng et al.[7]uses extended segment tables and extended offset tables to accommodate changes in memory capacity across different SRAM and FPGA chips.The algorithm divides the same prefx of the frst l bit into the same segment,and expands the prefx of less than 1 bit.The next hop address of the segment is then stored in the corresponding segment table or offset table.Hardware is relatively expensive and often requires multiple external memory chips.Due to the limitations of the hardware itself,the update performance and scalability are not very satisfying.

Virtual routers are also a promising way to lookup IP to provide network services.Each virtual router has a local forwarding information base(FIB).When multiple virtual routers run IP forwarding at the same time,a large amount of memory is needed to store multiple FIBs,which places higher requirements on the cache of general-purpose processors.Considering the commonality of IP prefxes between each FIB,Fu et al.[8]use the prefx conversion method to convert the network prefxes in all FIBs into the same prefx set.With the help of prefx conversion,the memory usage is reduced.Existing software routers often store IPv6 routes through binary trees or Hash linked lists,but when the number of IPv6 routing items increases to several k or tens of k,the storage space required is very large,and the search speed will also be signifcantly reduced.The work of this paper can better solve the above-mentioned problems.

Based on the analysis of characteristics of IPv6 prefx length and distribution,this paper proposes a routing lookup algorithm.It leverages LPR-Trie structure to reduce the number of memory accesses and achieve the lookup with the virtual nodes.In order to support rapid update,we develop the optimization methods.

3.1 LPR-Trie Architecture

We divide the frst 64 bits of the IP prefx into four tiers evenly:Root Tier(1-16 bits),Tier 1(17-32 bits),Tier 2(33-48 bits)and Tier 3(49-64 bits).Root tier stores the frst 16 bits in an array and other tiers are organized in an array or linked list.In Figure 1,the circles represent nodes.We use different colors to distinguish which layer the nodes belong to,and use solid lines and dashed lines to distinguish the types of nodes.Red circle represents the node in R array,green circles represent nodes in T1 array,and blue circles represent nodes in T2 array.Solid circles indicate ordinary nodes,and dotted circles mean virtual nodes.Because the whole structure are four layers and there is a link relationship between each layer,so we call the elements in the array“nodes”.

Root Tier:Root Tier is organized as an array:R array.The structure of R array elements is divided into three types:root node,list header and NULL.The size of the array element is 16 bits and the length is 216.In the current routing table,there are 52 kinds of values in the frst 16 bits of the destination address.Although the structure of the array requires 216spaces,each search for the frst 16 bits of the destination address requires only one memory operation.

When the number of routing prefxes starting with the element value is greater than a certain thresholdk,the element type is the root node.When the number is less than or equal tok,the element type is the list header.When there is no route starting with the element value,the element type is NULL.In this paper,we setkto 3.

The array element contains two kinds of pointers.One is the structure pointerPS,which points to the next level of array or linked list.The other is the prefx pointerPlen,which points to the prefx length table.The prefx length table is a table composed of all the lengths of the prefx that starts with the element value in the routing table at this level.

Tier 1:The second tier is organized in an array or linked list according to the element type of the R array

·If the element type of the R array is the root node,then Tier 1 is organized as T1 array that stores the 17-32 bits of the IP address.T1 array has the same size as the R array and elements in T1 array contain 2 types of information:fag and pointer.If the node value exists in the value of bits 17-32 in the routing table entry,the fag is set to beordinary,otherwise the fag is set to bevirtual.The pointer of the virtual node is calculated by LPR and points to an ordinary node.For the defnition and discussion of LPR calculation,see the introduction in section 3.2 below.

Figure 1.LPR-Trie structure.

The ordinary node contains two types of pointers:structure pointer and prefx pointer are the same as the pointer types in the R array,and virtual node does not have these two pointers,but an pointerPLPRto an ordinary node in the same layer through LPR calculation.

·If the element type of the R array is the list header,then Tier 1 is a linked list which stores the 17-64 bits of the IP address.For example,there are 3 routing entries whose frst 16 bits are“1234”,so the type of the element“1234”in R array is the list header and T1 tier stores the 3 entries in a list.

·The element type is NULL:When searching,it returns the next hop information of the default route.

Tier 2 and Tier 3:The third layer has a similar structure to the second layer.According to statistics,the prefx length of the routing table is mostly concentrated in 33-48.Therefore,the fourth layer is mainly lists linked with T2 array.When there are only a few routing entries in the lists,linear search generally meets the requirements.

The routing prefx is distributed in different array layers in steps of 16 bits:the R array is concerned with frst 16 bits of the routing prefx,and the T1 array is related to 17-32 bits.The T2 array represents the 33-48 bits.The 49-64 bits are placed in the list linked by the T2 array.

T1 array stores routes with same value of IP prefx(SV-RT)in the form of a pointer structure.The SVRTs stored in the T1-ND are routing entries with the frst 32 bits being a specifc value and the mask length from 17 to 32.SV(ND,len)is used to describe the node and prefxes linked to it where len=prefx length-TierNum*16.In Figure 1,node C has two SV-RTs,which are:2001:1240::/28 and 2001:1240::/24.They are represented as SV(C,12)and SV(C,8).

T2 array stores two kinds of routes.The frst type is SV-RT,which prefx length is between 33 and 48.The SV-RTs stored in node G in Figure 1 are:2001:1240:5800::/48,2001:1240:5800::/45 and 2001:1240:5800::/37.The second type is extending route(EX-RT).The frst 48 bits of these routes are the same and the mask length is greater than 48.The EX-RTs stored in the node G are:

2001:1240:5800::/62,2001:1240:5800::/56,

2001:1240:5800:1200::/56,

2001:1240:5800:3400::/56,

2001:1240:5800:5678::/64.

EX-RT are described in forms of EX(ND,len,value)where value is thevalueof 49-6bits.For example,for 2001:1240:5800:3400:/56,it matches node G,len=56-3*16=8 andvalue=0x3400.Therefore it is represented as EX(G,8,0X3400).

Note that SV-RT may exist in both T1 and T2 array,and EX-RT only appears in T2 array.Moreover,the prefx length of the Internet route is always greater than 16,so the R-ND does not store the route.If a route whose mask length is shorter than 16 appears in the future,it is supposed to be stored at R array in a similar way to the SV-RT in T1 array.

Virtual nodeOnly when the node contains at least 1 SV-RT or 1 EX-RT routing entry,the fag is set to be ordinary.Otherwise,the fag is set to be virtual.The virtual node itself does not contain routing,nor does it have descendant nodes.It is constructed for fast routing matching during message forwarding.Virtual node points to an ordinary node in the same tier by LPR algorithm to fnd the longest prefx matching entry,and see the subsequent LPR algorithm in details.

3.2 Routing Lookup and LPR Calculation

The output of route lookup algorithm is a routing entry stored in nodeM,which matches the destination IP address and has the longest prefx,denoted byLPR.

When a packet reaches a router,the forwarding engine searches for the routing entry in the routing tree based on the destination IP address(Dest)of the packet.

S1.According to the frst 16 bits of Dest,we search the R array.If the search fails,we return to the default route and the search ends.If the R array element structure type is the root node,continue to fnd the next layer according to the pointer type.If it is a linked list,directly search the linked list and return the result.

S2.According to the 17-32 bits,we search the T1 array.If the nodeMis marked as virtual,it directly returns LPR(M),and the search ends.If the element fag is ordinary,record max prefx value,and continue to fnd the next level of array according to thePS.

S3.Find the T2 array based on the 33-48 bits of the destination address.In the T2 array,if the fag is virtual,the LPR of the element is directly returned,and the search ends.If the element fag is ordinary,it means that the element contains at least one SV-RT or EX-RT.According to thePS,search for SV-RT or EX-RT.If both SV-RT and EX-RT are available,check EX-RT frst.If the match fails,then check SV-RT.If the search still fails,the LPR of the element is returned.

For the virtual node and the ordinary node without SV-RT,it needs to obtain the corresponding LPR and store the link relationship when constructing the LPRTrie.Moreover,the link relationship is also an important part of the maintenance of the routing tree.We give the details as following:

Algorithm 1Replace-1 describes the replacement of the last“1”(binary bit)with“0”.Details are illustrated in Algorithm 1.For a given binaryM=0x1234,this algorithm transforms it to 0x1230;ifM=0x0018,it is transformed to 0x0010.

Algorithm 2LPR calculation algorithm calculates the routing entry with the longest prefx that matches the destination IP address.For a nodeM,the algorithm continuously performs Replace-1 operations onMuntil it matches the same layer nodes which fag is ordinary,and then chooses a SV-RT satisfying the longest prefx matching(LPM)condition.If the LPR is not found in the sibling nodes,the node M points to the same LPR as its parent.Obviously,if the LPR of the parent node is NULL,the LPR corresponding to the nodeMis also NULL.

In the search process,the LPR of the ordinary element or the LPR of the virtual element may be returned.Specifc examples are given separately below:

Suppose the destination address is 2001:1240:5840:3400::0001.We frst fnd node I that stores the route whose frst 48 bits are 2001:1240:5840 and the minimum prefx length is 48.As node I only has no SV-RT and only one EX-RT:EX(I,8,0x1200),and the destination IP cannot match this EX-RT,it needs to return LPR(I).Take out the second-level array element value 0x5840,and get 0x5800 according to the Replace-1 operation of Algorithm 1,matching to node G=0x5800.G stores three SV-RTs of length 16,13,5,because it is the 10th bit of 0x5840 is replaced from 1 to 0,according to the longest prefx match,the routing prefx length of the third layer should be less than 10,and then SV(G,5)is obtained.

For node H=0x5806,the frst Replace-1 operation replaces the 15th bit from 1 to 0 and returns t=0x5804,whereas no corresponding node is found in the same layer.The next Replace-1 operation replaces the 14th bit from 1 to 0 and returnst2=0x5800,which matches node G.There are three SVRTs stored in G are 16,13 and 5.We choose the longest prefx route smaller than 14,that is,LPR(H)=SV(G,13).J=0x5860.The frst Replace-1 operation returns 0x5840,then the node I is matched in the same layer node,but there is no SV-RT in the node I,so the LPR of I should be returned,LPR(I)=SV(G,5).

3.3 Architecture Optimization

For a nodeMin then-th array,the routing entries whose frst 16*nbits are the same with M and the parent node of M and the mask length exceeds 16*nare called the government routing entry(GR-RT).GR-RT of nodes in R array or T1 array are the routing entry stored in all its child nodes,excluding the SV-RT.GRRT of nodes in T2 array are its EX-RTs.In Figure 1,the GR-RTs of node C are 11 routes stored in nodes F,G,and I.

Table 1.Number of T1 nodes with different KGR.

Table 2.Number of T2 nodes with different KEX.

The real routing table we downloaded from bgp.potaroo.net contains more than 70,000 routes.According to the data structure of this article,a root node represents the frst 16 bits of a routing prefx,and there are totally 52 root nodes.We counted and sorted the number of routes under each root node,that is,the number of routes beginning with different frst 16 bits.Then,for clear presentation and simple analysis,we selected the 7 root nodes with the largest numbers of routes to analyze the characteristics of routing entries.

Table 1 lists the number of T1 nodes for different GR-RT numbers under each root node.T1 nodes stores GR-RTs in a linked list where the number of routes does not exceeds the thresholdKGR.On the one hand,a large threshold causes a large number of memory accesses when traversing the linked list.On the other hand,excessive pointers to T2 array consume memory spaces signifcantly.As Table 1 shows,withKGR=3,only 18.99% of the T1 nodes point to the node array of 216.In other words,81.01% of the T1 nodes have no more than 3 routes in average.Table 2 describes the number of T2 nodes for different EX-RT numbers under each root node.Similarly,T2 nodes stores EX-RTs in a linked list where the number of routes is smaller than the thresholdKEX.In our LPR-Trie structure,when the number of EX-RT exceedsKEX,the T2 node points to the next array of nodes.Table II shows that an average of 16.41%of the T2 nodes are linked to a layer of node arrays.Properly setting thresholdsKEXandKEXcan achieve a balance between storage consumption and lookup effciency.

3.4 Security Considerations for Virtual Node Mechanism

With the concept of virtual node,the router becomes prone to a malicious DoS attack.To avoid the explosion of virtual nodes consuming enormous storage resources,we have the following considerations:

1.To reduce the attack hazard,we make use of the suppression mechanism.Many existing network processing mechanisms use a suppression mechanism to generate a limited number of control entries,such as the interface-MAC entry of the switch.Suppression is refected in two aspects:1)limit the number of virtual nodes generated per unit time;2)limit the total number of virtual nodes in the router system.These two values are determined jointly by various factors such as the hardware performance of the route system and the network environment.

2.The deployment of the real source address mechanism makes it easy to trace and block malicious nodes.The multi-level real source address mechanism studied by Tsinghua University has been widely deployed in Chinese universities and national institutions.Therefore,it is relatively easy for the network administrator to trace back.

3.The IPv6 routing lookup in this paper is designed for software routers and mainly deployed at the edge.The traffc entering the local area network from the external network does not generate the virtual nodes,while the traffc from the local area network to the external network does.Once a malicious behavior is discovered,it must be from the device of the subnet,hence it is easy to locate the attack point.

In addition,the above-mentioned suppression measures for virtual nodes help to detect network malicious behaviors early,block their spread,and provide certain support for the security of the whole network.

When the routing table is initialized,all possible areas are constructed according to the routing statistics.Let the route to be processed be described asrt:(prefix,masklen)whereprefixis the destination IP prefx and themasklenis the mask length.The route insertion process is as follows:

S1.If the routing entry is added as the default route,it is pointed to by the default route.It does not belong to any area and the LPR of all R nodes are updated.

S2.According to the 1-16 bits of theprefix,determine the routing storage area where it is located,and obtain R nodes.

S3.Take the value of 17-32 bits in the prefx asP1,and locate the child node according toP1.If there is no such node,change the type of this node from NULL to ordinary.

S4.If 16

S5.Take the value of 33-48 bits in the prefx asP2,and locate the child node of T1-ND according toP2.If there is no such node,change the type of this node from NULL to ordinary.

S6.If 32

S7.If 48

The route deletion process is similar to the route addition process.The routing area and the tree node are mainly located according toprefixandmasklen.After deleting a route,if the tree node or the subtree rooted at it is empty,delete the corresponding empty node and empty subtrie.Due to the addition or deletion of routes,LPR of some nodes may change and the consistency of the LPR shall be maintained according to Algorithm 2.

For evaluation,we downloaded the current routing table from bgp.potaroo.net and implemented the algorithm on the Linux platform.In order to adapt to the application environment of the edge router,the sizes of the selected routing tables TABLE-A and TABLE-B are 5k and 6k,respectively.The CPU confguration of the experiment is the Intel Core i7TM 6700 processor,and the software compilation environment is Visual C++2015.

Figure 2 shows that the distribution of routing items is characteristic.The routing items with a prefx length of 32 account for 17%,and the routing items with a length of 48 account for the most,accounting for 48%,and the prefx distribution is mainly concentrated in 32-48.According to this feature,we search in steps of 16 bits.

Figure 2.Prefix length distribution.

Figure 3.Number of routes per layer in each area.

Figure 3 further analyzes the number of routes with prefx lengths of 17-32,33-48,and 49-64 in each area.17-32 routes are stored in the T1 array in the form of SV-RT,33-48 routes are stored under the T2 array in the form of SV-RT,and routes longer than 48 are stored in the form of EX-RT.

5.1 Lookup Speed and Timing Analysis

Figure 4.The percent of lookup times for real time traffic on TABLE-A and TABLE-B.

We implement the LPR scheme described in Section III and compare it with TSB[2].TSB has three-stage for IPv6 routing table lookup.In the frst stage,2001 was used as the root node.Because the algorithm was proposed in the year of 2006,the frst 16 bits of the IPv6 addresses of traffc on the IPv6 network at that time only had 9 values,and most started with 2001.Part of the traffc can be matched in one search on the binary tree.The second stage uses two different data structures.Node 2001 links segment table,while the other 8 nodes link routing buckets.The segment table is composed of 17-32 bits of the routing prefx,and the length is 16 bits.The third stage is the routing bucket linked to the segment table.It is a collection of routing table entries.According to the number of routing table entries in the routing bucket,the routing buckets can be organized in different ways.

In Figure 4,the number of memory accesses are shown.For most routes,the longest prefx route can be matched by three searches,and the search process is R array→T1 array→SV-RT of T1,and the result is returned directly in SV-RT of T1.In particular,since the virtual node is being constructed,a pointer to the ordinary node of the same array has been established.When the virtual node is matched,the corresponding node can be found directly through the pointer,which reduces the number of searches.

Table 1 depicts lookup speed and memory requirements of LPR and TSB.The average numbers of searches of the LPR and TSB for TABLE-A are 3.54 and 6.81,respectively.For TSB,in the year of 2006,most routing prefxes start with 2001,and there are very few routing prefxes that start with other values,so that most of the traffc only needs to be matched once on the binary tree.Now,there are 52 values in the frst 16 bits.The routes beginning with 2001 arestill the most,but only account for 14%.Therefore,only using 2001 as the root node is not suitable for current traffc characteristics.Due to the fast growth of the routing table,the number of segment tables and the size of the routing bucket in TSB have increased signifcantly.In LPR,we store the frst 16-bit value in the R array,whose memory consumption is fxed,and the corresponding root node can be located in only one search because of the characteristic of the structure of array.

Table 3.Lookup speed and memory requirements of LPR and TSB.

The worst case of the LPR algorithm requires 8 searches,namely R array→T1 array→T2 array→EX-RT of T2→T2 array.When the destination address matches the EX-RT list of T2 array once,the routes are searched one by one,however the search fails,and T2 array are searched once again,returning the LPR under the node at the same layer.But only about 4.72%of the traffc needs to be searched 8 times.

In terms of memory consumption,although we use a three-level array structure,in fact most of the routes are stored in the form of SV-RT under the T1 array,and the T2 array is not developed.When the number of routes exceeds a lot,the linear search will greatly reduce the search speed.Therefore,we set the thresholdKGR,andKEX.Table 3 shows the size of memory consumption withKGR=3 andKEX=3.

5.2 Keep-Alive Time

For the different keep-alive time of virtual nodes,the number of visits and the destruction and reconstruction times of the virtual nodes in the keep-alive time are different.The experimental results show that when the input actual fow duration is 24h,the keep-alive timeτis set to 0,1h,2h and 3h,respectively.When the keep-alive time is set to a small value,the storage overhead of the virtual node is small,but it needs to be destroyed and re-established multiple times.Due to the local characteristics of traffc,as the keep-alive time increases,the number of new virtual nodes decreases signifcantly.The update of the virtual node is stable,and it occupies less memory.But overall,the virtual node has less impact on memory overhead.

Figure 5.The change of the number of virtual nodes with time.

Figure 6.The change of refresh times with different τ.

Table 4.Num of V-ND with different τ.

Table 5.Repeat times with different τ.

Figure 7.The lookup time with different keep-alive times of V-ND.

Figure 5 shows the number of virtual nodes that changes over time.For the same routing table,the number of virtual nodes is relatively stable as time goes on.Table 4 lists the average numbers of virtual nodes established in our structure with three keepalive times.The number of times the virtual node is refreshed indicates the number of times the virtual node is repeatedly accessed during the keep-alive time.Table 5 is the average refresh times,and the change of refresh times with differentτis shown in Figure 6.From Figure 6,we learn that only a few virtual nodes refresh frequently.

Figure 7 illustrates that during the real destination queries for 3 hours,as we prolong the keep-alive time,the lookup decrease continuously.Moreover,we hope that the addition and deletion of virtual nodes is not too frequent.The update time of each virtual node has a great infuence on the overall search time,so a longer keep-alive time is required.According to the performance of hardware devices,the locality of traffc and peoples access habits,we recommend setting the keep-alive time to two days as a reference.In Figure 8,the numbers of reconstructions of each virtual node vary according to differentτ.A largerτresults in a less create times for one virtual node.

Figure 8.The effect of different keep-alive times on the number of virtual node reconstructions.

In this paper we propose a LPR-Trie extended from multi-bit Trie,and corresponding routing lookup algorithm.Combining the characteristics of the IPv6 address and the backbone network routing tables,the LPR algorithm is very effcient for IPv6 routing tables whose most prefx lengths distribute in/48.This algorithm calculates the pointer of the virtual node,which points to the longest prefx matching routing entry to achieve fast routing matching.The use of virtual node signifcantly reduces the number of memory accesses and improves the search speed.Experimental results show that our search speed is 3.49 times that of TSB.Our average number of searches is 3.41,while TSB needs 6.81 searches on average.And the memory size occupied by TSB is about 1.5 times that of LPR.In addition,due to the locality of actual traffc,a reasonable setting of the keep-alive time of the virtual node makes the data structure more stable and have less impact on memory consumption.Experimental results show that the algorithm has better storage and search performance,and it has good scalability.

ACKNOWLEDGMENT

We gratefully acknowledge the support from the National Natural Science Foundation of China(61872252),National Key Research and Development Program of China(2018YFB1800403),the Beijing Natural Science Foundation(4202012)and the Science and Technology Project of Beijing Municipal Commission of Education in China(KM201810028017).