Exploiting the Thread-Level Parallelism for BGP on Multi-core

With the developing technology of multi-core processors, exploiting the thread-level parallelism (TLP) of BGP will highly improve the performance required by core routers on Internet, to relax the problems of BGP route outburst updates and persistent route oscillations. The TLP approach for BGP based on min-cut partition algorithm which introduces thread-level speculation (TLS) and decomposes the BGP program into granularity balanced threads is proposed in this paper. Meanwhile, the speculation strategies and relative implementations, which ensure the commits of speculative threads in sequence and maintain the memory consistency, are presented for TLS of BGP to improve the parallelism. Experiments on sun fire T1000 server show that our algorithm can achieve pretty speedup, which can reach 1.51, 1.82, 2.59 and 2.92 when partitioning 32, 64, 256 and 512 threads and allowing 4, 8, 12 and 16 threads in parallel. And the response time of processing 1 K, 5 K, 10 K and 30 K packets on single session has decreased 16.9% and 25.2% averagely when partitioning 64 and 256 threads.