AS alliance: cooperatively improving resilience of intra-alliance communication

ABSTRACT

The current interdomain routing protocol, BGP, is not resilient to a path failure due to its single-path and slowly-converging route calculation. This paper proposes a novel approach to improve the resilience of the interdomain communication by enabling a set of ASes to form an alliance for themselves. The alliance members cooperatively discover a set of disjoint paths using not only the best routes advertised via BGP but also the ones unadvertised. Since such a set of disjoint paths are unlikely to share a link or an AS failure, a member AS can provide a pair of the other members with a transit to circumvent the failure. We evaluate how many disjoint paths we could discover from both advertised and hidden (unadvertised) routes by analyzing publicly available BGP route data. Our feasibility study indicates that an alliance of ASes can establish a set of disjoint paths between arbitrary pair of its alliance members to improve the resilience of interdomain routing among the members.

REFERENCES

• 1: The CAIDA AS relationships dataset. http://www.caida.org/data/active/as-relationships/.
• 2: PlanetLab. http://www.planet-lab.org.
• 3: RIPE routing information service (RIS). http://www.ripe.net/projects/ris/index.html.
• 4: Route views project. http://www.routeviews.org.
• 5: Aditya Akella , Jeffrey Pang , Bruce Maggs , Srinivasan Seshan , Anees Shaikh, A comparison of overlay routing and multihoming route control, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 6: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 7: I. Avramopoulos, M. Suchara, and J. Rexford. How small groups can secure interdomain routing. http://www.cs.prinston.edu/research/techreps/TR-808-07.
• 8: Xenofontas Dimitropoulos , Dmitri Krioukov , Marina Fomenkov , Bradley Huffaker , Young Hyun , kc claffy , George Riley, AS relationships: inference and validation, ACM SIGCOMM Computer Communication Review, v.37 n.1, January 2007 [doi>10.1145/1198255.1198259]
• 9: Krishna P. Gummadi , Harsha V. Madhyastha , Steven D. Gribble , Henry M. Levy , David Wetherall, Improving the reliability of internet paths with one-hop source routing, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.13-13, December 06-08, 2004, San Francisco, CA
• 10: S. H. Khor and A. Nakao. AI-RON-E: Prophecy of one-hop source routers. In Proc. of IEEE GLOBECOM, 2008.
• 11: Nishant Kumar , Girish Saraph, End-to-End QoS in Interdomain Routing, Proceedings of the International conference on Networking and Services, p.82, July 16-18, 2006 [doi>10.1109/ICNS.2006.45]
• 12: N. Kushman, S. Kandula, D. Katabi, and B. Maggs. R-BGP: Staying connected in a connected world. In 4th USENIX Symposium on NSDI, April 2007.
• 13: Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.175-187, August 28-September 01, 2000, Stockholm, Sweden
• 14: Z. Morley Mao , Lili Qiu , Jia Wang , Yin Zhang, On AS-level path inference, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 15: Y. Rekhter, T. Li, and S. Hares. A border gateway protocol 4 (BGP-4). RFC 4271, January 2006.
• 16: Hu Xiangjiang , Zhu Peidong , Gong Zhenghu, Translator Trust for the Internet Inter-domain Routing, Proceedings of the Future Generation Communication and Networking, p.453-458, December 06-08, 2007 [doi>10.1109/FGCN.2007.221]
• 17: Wen Xu , Jennifer Rexford, MIRO: multi-path interdomain routing, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking

General Terms:
Design, Experimentation

Keywords:
AS alliance, disjoint path, interdomain routing, multipath routing