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 decomposesthe 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 insequence 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 canreach 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 1K, 5K, 10K and 30K packets on single sessionhas decreased 16.9% and 25.2% averagely when partitioning 64 and 256 threads.