Gift granted by the Cisco Collaborative Research Initiative (CCRI)
Researchers: Fred Baker, Russ White, David Ward Marcelo Yannuzzi and Xavi Masip
Duration of the Project: from January 2009 to December 2009
Research goal: “Path State Vectors”
Although many arguments can be found in the literature stating that it is time to replace BGP, the practical and economical implications associated with its replacement are obstacles hard to overcome. The challenge nowadays is to find ways to improve different aspects of the inter-domain routing system that neither require the imminent replacement of BGP, nor the development of upward-compatible extensions tending to make BGP even more irreplaceable than it is today. In light of this, this research proposal aims at developing the concept of a Path-State Vector (PSV), as a promising and straightforward way to overlay some key functions out from BGP. In the PSV model that we conceive, the distribution of reachability information (i.e., the localizers) as well as the computation of loop-free paths are kept in the scope of BGP (the underlay), whereas the critical issues currently driving the replacement of BGP can be decoupled from the latter, and managed through one or more domain-level overlays. Unlike pure overlay networks, which simply circumvent BGP, the PSV model that we devise should feed from and assist BGP, as well as offer an effective coupling between BGP and the functions overlayed from the latter. To this end, we propose that PSVs build a graph overlay. Our previous research has shown that graphs inspired in link-state protocols cannot offer a unique and consistent view of the forwarding paths of an internetwork under the current export policies between domains. We have recently found how to build a suitable graph for a PSV, and more importantly, this graph does not violate the policy opaqueness required by ISPs, which provides new and promising research opportunities. As a starting point, this initiative proposes to focus on two objectives: (1) the design of a highly scalable PSV protocol; and (2) exploit the graph overlay in a PSV to remove the path exploration phenomenon from BGP, and therefore, drastically reduce the convergence time on the Internet.