A Practical Non-blocking Route Propagation Technology for Threaded BGP

This paper presents a non-blocking technology to accelerate the route propagation in TBGP (Threaded BGP). The scheme eliminates various contentions effectively, achieves con-current queue operations by SCLF lock-free algorithm, and also avoids the performance penalty by cache line thrashing. We first evaluate the average announcing time per thread and memory consumption for the lock-based scheme and newly-proposed scheme by analytical models, and then the experiments on dual quad-core Xeon server show that the non-blocking scheme greatly educes the runtime of route propagation with distinct parallelization. At the same time, the SCLF algorithm empowers faster queue operations, which is about 120 ns on average and much smaller than that of the lock-based queue algorithm.