How to Generate Random Topologies with Internet-like Characteristics

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

The exponential growth of the number of Internet hosts has been well documented in the trade press. The research community, however, has not seen many systematic empirical studies of how the Internet topology evolves over time and in space. Most recently, the authors of [FFF99] report on several power-law relationships observed on Autonomous Systems' (AS) connectivity degree, degree frequencies, and the neighborhood size within any given hop count from an AS. This pioneering work represents a first important step toward a better understanding of the dynamic nature of the actual Internet topology. The need for realistic random topologies in simulations has long been recognized by researchers working on routing and multicast protocols, e.g. [BE90, ZGLA91, WE94]; more recently, the need for realistic random topologies has also been voiced by researchers studying traffic dynamics and protocol behavior [MS94, FGHW99, F+00]. In recognition of this, several topology generators have been proposed in the literature. The most recent one, proposed in [J+00] and called Inet, takes advantage of the power-law relationships reported in [FFF99] in its construction of random topologies. The preliminary work conducted as part of this research and reported in this proposal shows exponential growth over time in frequency of every outdegree, the outdegree of every rank, and the neighborhood size within any given hop count from an AS. The preliminary results also show that only the random topologies generated by the Inet model have the power-law relationships similar to those of the Internet. Unfortunately, these random topologies do not exhibit the exponential growth observed of the Internet. A new Inet topology generator, called New Inet,was constructed to generate topologies exhibiting both the power law relationships and exponential growth rates over time. The research proposed here consists of three parts: 1. To investigate whether or not proposed topology models are in fact capturing the essence of certain underlying network design mechanisms or engineering constraints that result in random topologies that perforce exhibit many of the empirically observed phenomena. To this end the PIs focus on two particular approaches concerning the emergence of scaling phenomena associated with Internet-like graph structures in the context of the models of Barabasi and Albert [BAJ99, BA99] and of Carlson and Doyle [CD99a, CD99b]. 2. An in-depth analysis of the properties of connectivity graphs at the intra-AS level. In particular, the Pis are interested in large ASs spanning wide geographic area. 3. To determine if trees constructed from a given graph can serve as a "fingerprint" of the graph from which various properties of the graph can be derived; and to model policy routing on the Internet as such trees. In particular, the PIs want to check whether these tree structures exhibit scaling laws that have been found ubiquitous in the context of river networks such as the Horton-Strahler laws [Hor45, Str57]. The PIs propose to continue studying AS-level connectivity data made available by the National Laboratory for Applied Network Research (NLANR) for better understanding of how ASs connect to each other, how this connectivity changes over time, and how each individual AS can be modeled in long-running simulations. Additionally, the PIs also propose to model router-level connectivity within ASs. For this, the PIs have access to intra-AS connectivity information from the AT&T WorldNet backbone. Funding for two graduate student research assistants was requested in this proposal. Both students will spend their academic year at the University of Michigan under the supervision of the PI, Sugih Jamin. They will help the PIs carry out research on studying AS-level connectivity, intra-AS connectivity, source-rooted trees constructed from traceroute data, and improve the New Inet random topology generator. During summers, one or both of the students will visit AT&T Labs-Research in Florham Park under the supervision of the co-PI, Walter Willinger, to collect and study data on AT&T WorldNet backbone. To improve the collaboration, the PI and co-PI may also visit each other'ssite during the project.