A quantitative comparison of graph-based models for internet topology

Ellen W. Zegura, Kenneth L. Calvert, Michael J. Donahoo

Research output: Contribution to journalReview articlepeer-review

367 Scopus citations

Abstract

Graphs are commonly used to model the topological structure of internetworks in order to study problems ranging from routing to resource reservation. A variety of graphs are found in the literature, including fixed topologies such as rings or stars, well-known" topologies such as the ARPAnet, and randomly generated topologies. While many researchers rely upon graphs for analytic and simulation studies, there has been little analysis of the implications of using a particular model or how the graph generation method may affect the results of such studies. Further, the selection of one generation method over another is often arbitrary, since the differences and similarities between methods are not well understood. This paper considers the problem of generating and selecting graphs that reflect the properties of real internetworks. We review generation methods in common use and also propose several new methods. We consider a set of metrics that characterize the graphs produced by a method, and we quantify similarities and differences among several generation methods with respect to these metrics. We also consider the effect of the graph model in the context of a specific problem, namely multicast routing.

Original languageEnglish
Pages (from-to)770-783
Number of pages14
JournalIEEE/ACM Transactions on Networking
Volume5
Issue number6
DOIs
StatePublished - 1997

Keywords

  • Internetworking
  • Multicast
  • Network modeling
  • Scalability

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'A quantitative comparison of graph-based models for internet topology'. Together they form a unique fingerprint.

Cite this