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.