A quantitative comparison of graph-based models for Internet topology

@article{citeulike:2660785, 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}, author = {Zegura, E. W. and Calvert, K. L. and Donahoo, M. J. }, booktitle = {Networking, IEEE/ACM Transactions on}, citeulike-article-id = {2660785}, doi = {http://dx.doi.org/10.1109/90.650138}, journal = {Networking, IEEE/ACM Transactions on}, keywords = {graph, internet, topology}, number = {6}, pages = {770--783}, posted-at = {2008-04-12 16:47:39}, priority = {2}, title = {A quantitative comparison of graph-based models for Internet topology}, url = {http://dx.doi.org/10.1109/90.650138}, volume = {5}, year = {1997} }

TY - JOUR ID - citeulike:2660785 L3 - citeulike-article-id:2660785 TI - A quantitative comparison of graph-based models for Internet topology T2 - Networking, IEEE/ACM Transactions on JF - Networking, IEEE/ACM Transactions on VL - 5 IS - 6 SP - 770 EP - 783 N2 - 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 KW - graph KW - internet KW - topology AU - Zegura, EW AU - Calvert, KL AU - Donahoo, MJ PY - 1997/// UR - http://dx.doi.org/10.1109/90.650138 ER -