SpliTable: Toward Routing Scalability through Distributed BGP Routing Tables

Akeo MASUDA  Cristel PELSSER  Kohei SHIOMOTO  

Publication
IEICE TRANSACTIONS on Communications   Vol.E94-B   No.1   pp.64-76
Publication Date: 2011/01/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E94.B.64
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (IEICE/IEEE Joint Special Section on Autonomous Decentralized Systems Technologies and Their Application to Networked Systems)
Category: Scalability & Timeliness
Keyword: 
scalable routing,  BGP,  DHT,  

Full Text: PDF(927.1KB)
>>Buy this Article


Summary: 
The Internet has grown extremely fast in the last two decades. The number of routes to be supported by the routers has become very large. Moreover, the number of messages exchanged to distribute the routes has increased even faster. In this paper, we propose SpliTable, a scalable way to support the Internet routes in a Service Provider network. In our proposal, BGP route selection is done by distributed servers on behalf of the routers. They are called route selection servers. The selected routes are then stored in distributed routing tables. Each router maintains only its share of Internet routes, not the routes for each Internet prefix as it is the case today. We adapted the concept of Distributed Hash Tables (DHT) for that purpose. We show analytically that our proposal is more scalable in the number of routes supported in each router than current iBGP route distribution solutions. Moreover, the number of control messages exchanged with our proposal is bounded contrary to current sparse iBGP route distribution solutions which may never converge. We confirm these findings in an evaluation of a prototype implementation.