TY - GEN
T1 - Using forgetful routing to control BGP table size
AU - Karpilovsky, Elliott
AU - Rexford, Jennifer L.
PY - 2006
Y1 - 2006
N2 - Running the Border Gateway Protocol (BGP), the Internet's interdomain routing protocol, consumes a large amount of memory. A BGP-speaking router typically stores one or more routes, each with multiple attributes, for more than 170,000 address blocks, and growing. When the router does not have enough memory to store a new route, it may crash or enter into other unspecified behavior, causing serious dis- ruptions for the data traffic. In this paper, we propose a new mechanism for routers to handle memory limitations with- out modifying the underlying routing protocol and without negatively affecting convergence delay. Upon running out of memory, the router simply discards information about some alternate routes, and requests a quot;refresh" from its neighbors later if necessary. We present an optimal offline algorithm for deciding which alternate routes to evict, and explore the trade-off between memory size and refresh overhead using a large BGP message trace. Based on these promising re- sults, we design and evaluate efficient online algorithms that achieve most of the performance benefits. We believe that our scheme can significantly improve the scalability and ro- bustness of IP routers in the future.
AB - Running the Border Gateway Protocol (BGP), the Internet's interdomain routing protocol, consumes a large amount of memory. A BGP-speaking router typically stores one or more routes, each with multiple attributes, for more than 170,000 address blocks, and growing. When the router does not have enough memory to store a new route, it may crash or enter into other unspecified behavior, causing serious dis- ruptions for the data traffic. In this paper, we propose a new mechanism for routers to handle memory limitations with- out modifying the underlying routing protocol and without negatively affecting convergence delay. Upon running out of memory, the router simply discards information about some alternate routes, and requests a quot;refresh" from its neighbors later if necessary. We present an optimal offline algorithm for deciding which alternate routes to evict, and explore the trade-off between memory size and refresh overhead using a large BGP message trace. Based on these promising re- sults, we design and evaluate efficient online algorithms that achieve most of the performance benefits. We believe that our scheme can significantly improve the scalability and ro- bustness of IP routers in the future.
KW - Communication networks
KW - Performance optimization
KW - Workload characterization
UR - http://www.scopus.com/inward/record.url?scp=77953817772&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77953817772&partnerID=8YFLogxK
U2 - 10.1145/1368436.1368439
DO - 10.1145/1368436.1368439
M3 - Conference contribution
AN - SCOPUS:77953817772
SN - 1595934561
SN - 9781595934567
T3 - Proceedings of CoNEXT'06 - 2nd Conference on Future Networking Technologies
BT - Proceedings of CoNEXT'06 - 2nd Conference on Future Networking Technologies
T2 - 2nd Conference on Future Networking Technologies, CoNEXT'06
Y2 - 4 December 2006 through 7 December 2006
ER -