A fractional model of the border gateway protocol (BGP)

ABSTRACT

The Border Gateway Protocol (BGP) is the interdomain routing protocol used to exchange routing information between Autonomous Systems (ASes) in the internet today. While intradomain routing protocols such as RIP are basically distributed algorithms for solving shortest path problems, the graph theoretic problem that BGP is trying to solve is called the stable paths problem (SPP). Unfortunately, unlike shortest path problems, it has been shown that instances of SPP can fail to have a solution and so BGP can fail to converge.

We define a fractional version of SPP and show that all such instances of fractional SPP have solutions. We also show that while these solutions exist they are not necessarily half-integral.

REFERENCES

• 1: Ron Aharoni , Tamás Fleiner, On a lemma of Scarf, Journal of Combinatorial Theory Series B, v.87 n.1, p.72-80, January 2003 [doi>10.1016/S0095-8956(02)00028-X]
• 2: {GS62} D. Gale and L. Shapley. College admissions and stability of marriage. American Math Monthly, 69(1):9--15, 1962.
• 3: Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, The stable paths problem and interdomain routing, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 2002
• 4: Timothy G. Griffin , Gordon Wilfong, An analysis of BGP convergence properties, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.277-288, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 5: {Nas50} J. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36(1):48--49, 1950.
• 6: {RL95} Y. Rehkter and T. Li. A Border Gateway Protocol (BGP version 4). RFC 1771, 1995.
• 7: {Sca67} H. Scarf. The core of an n person game. Econo-metrica, 35(1):50--69, 1967.
• 8: Jimmy J. M. Tan, A necessary and sufficient condition for the existence of a complete stable matching, Journal of Algorithms, v.12 n.1, p.154-178, March 1991 [doi>10.1016/0196-6774(91)90028-W]
• 9: {VGE00} K. Varadhan, R. Govindan, and D. Estrin. Persistent route oscillations in inter-domain routing. Computer Networks, 32:1--16, 2000.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems; Graph algorithms

General Terms:
Algorithms, Design, Theory