An Efficient Update Mechanism for GPU-based IP Lookup Engine using Threaded Segment Tree
Recently,the Graphics Processing Unit (GPU) has been proved to be an exciting new platform for high-performance software routers.On such a platform,designing efficient IP lookup engine is a challenging task,especially when taking into account the comprehensive performance under frequent updates.Existing solutions either fail in dealing with update overhead,or can not provide stable throughput.In this paper,we propose Threaded Segment Tree,a novel treelike structure,based on which we present a fast IP lookup engine with an efficient parallel update mechanism.In our mechanism,a list of threaded segments cover all route updates without intersecting,which minimizes the number of required global memory accesses on GPU for on-line updates and also promotes their parallelism.Besides,by assigning tasks to all working threads in a balance way,update performance is enhanced further.According to the experiment results on real-world data,our proposed mechanism reduces the memory accesses on GPU and the overall update overhead by at least 82:5% and 89:6% respectively.Moreover,it also ensures the lookup engine provides stable throughput with highly frequent updates,which only decreases by less than 1% even though update frequency increases to 100; 000 updates=s.
GPU IP lookup parallel update segment tree
Yanbiao Li Dafang Zhang Gaogang Xie Jintao Zheng Wei Zhao
College of Information Science and Engineering, Hunan University, Changsha, 410082, China Institute of Computing Technology, Chinese Academy of Sciences, Beijing, 100190, China
国内会议
张家界
英文
119-124
2013-07-01（万方平台首次上网日期，不代表论文的发表时间）