Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

There are different types of links between the domains that compose Internet. Relationships introduced by these types impose a hierarchical structure on the global network. This structure may influence the functioning of the different mechanisms used in the network, notably inter-domain routing protocols. In order to validate a new inter-domain protocol it is necessary to have a model of hierarchical networks.

To the best of our knowledge, there is no random topology generator which is well adapted to represent the Internet hierarchy. We try to induce this hierarchy into random topologies generated by BRITE. The obtained results show that the hierarchy inducted in topologies generated with the extended model of Barabási and Albert (BA2) is very close to the real one.

The implementation of the proposed solution, the SHIIP program, is available on Internet under a public-domain license.

REFERENCES

• 1: Zihui Ge, Daniel R. Figueiredo, Sharad Jaiswal, and Lixin Gao, "The hierarchical structure of the logical Internet graph," in Proc. of SPIE ITCOM'01, Colorado, USA, July 2001, vol. 4526, pp. 208--222.
• 2: Lakshminarayanan Subramanian, Sharad Agarwal, Jennifer Rexford, and Randy H. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in Proc. of IEEE INFOCOM'02, New York, USA, June 2002, vol. 2, pp. 618--627.
• 3: Joan Feigenbaum , Christos Papadimitriou , Rahul Sami , Scott Shenker, A BGP-based mechanism for lowest-cost routing, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571856]
• 4: Dominique Barth, Loubna Echabbi, Chahinez Hamlaoui, and Sandrine Vial, "An economic and algorithmic model for qos provisioning bgp interdomain network," in Proceedings of the EuroNGI Workshop on QoS and Traffic Control, 2005.
• 5: C. Jin, Q. Chen, and S. Jamin, "Inet: Internet topology generator," Tech. Rep. CSE-TR443-00, Department of EECS, University of Michigan, 2000.
• 6: William Aiello , Fan Chung , Linyuan Lu, A random graph model for massive graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.171-180, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335326]
• 7: Bernard M. Waxman, "Routing of multipoint connections," Selected Areas in Communications, IEEE Journal on, vol. 6, no. 9, pp. 1617--1622, 1988.
• 8: Albert-Laszlo Barabási and Reka Albert, "Emergence of scaling in random networks," Science, vol. 286, no. 5439, pp. 509--512, 1999.
• 9: Reka Albert and Albert-Laszlo Barabási, "Topology of evolving networks: local events and universality," Physical Review Letters, vol. 85, pp. 5234, 2000.
• 10: T. Bu and D. Towsley, "On distinguishing between Internet power law topology generators," in Proc. of INFOCOM'02, New York, USA, June 2002, vol. 2, pp. 638--647.
• 11: M. Doar, "A better model for generating test networks," in Proc. of Globecom'96, London, Great Britain, 1996, pp. 86--93.
• 12: Ellen W. Zegura, Kenneth L. Calvert, and Samrat Bhattacharjee, "How to model an internetwork," in Proc. of IEEE Infocom, San Francisco, USA, March 1996, vol. 2, pp. 594--602.
• 13: Hongsuda Tangmunarunkit , Ramesh Govindan , Sugih Jamin , Scott Shenker , Walter Willinger, Network topology generators: degree-based vs. structural, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 14: Lixin Gao, On inferring autonomous system relationships in the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.733-745, December 2001 [doi>10.1109/90.974527]
• 15: Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: An Approach to Universal Topology Generation, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.346, August 15-18, 2001
• 16: Marc-Antoine Weisser and Joanna Tomasik, "Inferring inter-domain relationships in randomly generated network models," in Proc. of EuroNGI Workshop, Torino, Italy, June 2006.
• 17: Hyunseok Chang , Ramesh Govindan , Sugih Jamin , Scott J. Shenker , Walter Willinger, Towards capturing representative AS-level Internet topologies, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.44 n.6, p.737-755, 22 April 2004 [doi>10.1016/j.comnet.2003.03.001]
• 18: Hongsuda Tangmunarunkit , John Doyle , Ramesh Govindan , Walter Willinger , Sugih Jamin , Scott Shenker, Does AS size determine degree in as topology?, ACM SIGCOMM Computer Communication Review, v.31 n.5, p.7-8, October 2001 [doi>10.1145/1037107.1037108]

INDEX TERMS

Keywords:
inter-domain hierarchy, random topology generator