The number of IPv6 routes in todays back-bone routers has grown rapidly,which has put tremen-dous pressure on route lookup and storage.Based on the analysis of IPv6 address prefix length and distribu-tion 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 con-cept of virtual nodes,and leverage the link between virtual nodes and ordinary nodes to accelerate rout-ing lookup.We provide the longest prefix routing en-try(LPR)calculation algorithm to achieve the longest prefix 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 traffic.This paper shows that our design improves the routing lookup speed and have better memory utilization.

Wenlong Chen;Diya Liu;Jiacheng Wang;Xiaolan Tang

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

中国通信（英文版）

[1]Wenlong Chen;Diya Liu;Jiacheng Wang;Xiaolan Tang-.LPR-Trie:A Fast IPv6 Routing Lookup Algorithm with Virtual Nodes)[J].中国通信（英文版）,2022(10):1-11

Lookup,todays

LPR,Trie,Fast,IPv6,Routing,Algorithm,Virtual,Nodes,number,routes,back,bone,routers,has,grown,rapidly,which,put,tremen,dous,pressure,lookup,storage,Based,analysis,address,prefix,length,distribu,characteristics,this,paper,proposes,architecture,called,core,idea,algorithm,utilize,more,spaces,accelerate,routing,Moreover,forward,con,cept,virtual,nodes,leverage,link,between,ordinary,We,provide,longest,try,calculation,achieve,match,experimental,results,that,mechanism,increases,search,speed,have,better,stability,by,setting,appropriate,keep,alive,according,actual,traffic,This,shows,our,design,improves,memory,utilization

0.557608