Title :
Two-level tries: A general acceleration structure for parallel routing table accesses
Author :
Mingche, Lai ; Lei, Gao
Author_Institution :
Dept. of Comput., Nat. Univ. of Defense Technol., Changsha, China
Abstract :
The stringent performance requirement for the high efficiency of routing protocols on the Internet can be satisfied by exploiting the threaded border gateway protocol (TBGP) on multi- cores, but the state-of-the-art TBGP performance is restricted by a mass of contentions when racing to access the routing table. To this end, the highly-efficient parallel access approach appears to be a promising solution to achieve ultra-high route processing speed. This study proposes a general routing table structure consisting of two-level tries for fast parallel access, and it presents a heuristic-based divide-and-recombine algorithm to solve a mass of contentions, thereby accelerating the parallel route updates of multi-threading and boosting the TBGP performance. As a projected TBGP, this study also modifies the table operations such as insert and lookup, and validates their correctness according to the behaviors of the traditional routing table. Our evaluations on a dual quad-core Xeon server show that the parallel access contentions decrease sharply by 92.5% versus the traditional routing table, and the maximal update time of a thread is reduced by 56.8% on average with little overhead. The convergence time of update messages are improved by 49.7%.
Keywords :
Internet; internetworking; message passing; multi-threading; multiprocessing systems; parallel processing; routing protocols; table lookup; trees (mathematics); Internet; dual quad-core Xeon server; general acceleration structure; general routing table structure; heuristic-based divide-and-recombine algorithm; highly-efficient parallel access approach; multicores; multithreading; parallel access contentions; parallel route updates; parallel routing table accesses; routing protocols; state-of-the-art TBGP performance; stringent performance requirement; table insert; table lookup; threaded border gateway protocol; two-level tries; ultra-high route processing speed; update messages; Eigenvalues and eigenfunctions; Heuristic algorithms; Message systems; Partitioning algorithms; Peer to peer computing; Routing; Routing protocols; Multi-cores; route update; two-level tries;
Journal_Title :
Communications and Networks, Journal of
DOI :
10.1109/JCN.2011.6157461