Sampling large Internet topologies for simulation purposes
Sampling large Internet topologies for simulation purposes
复制标题
DOI：
10.1016/j.comnet.2007.06.004
复制
发表时间：
2007-10
期刊：
影响因子：
--
通讯作者：
Vaishnavi Krishnamurthy;M. Faloutsos;M. Chrobak;Jun-hong Cui;Li Lao;A. Percus
中科院分区：
文献类型：
--
作者：
Vaishnavi Krishnamurthy;M. Faloutsos;M. Chrobak;Jun-hong Cui;Li Lao;A. Percus
在本文中，我们开发的方法来“采样”一个小的现实图从一个大的互联网拓扑结构。尽管最近的活动，建模和生成逼真的图形类似于互联网仍然是一个没有解决的问题。所有以前的工作都试图从零开始生长这样的图。我们解决的互补问题，缩小现有的拓扑结构。具体来说，这项工作有三个部分。首先，我们提出了一些约简方法，可以分为三类：（a）删除方法，（B）收缩方法，和（c）勘探方法。我们证明了其中一些保持初始图的关键属性。我们实现我们的方法，并表明，我们可以有效地减少多达70%的互联网图的节点，同时保持其重要的属性。其次，我们表明，我们的减少图相比，有利的建设为基础的发电机。最后，我们成功地验证了我们最好的方法的有效性，在实际的多播路由性能评估研究。除了它的实际应用，图抽样问题是独立的利益。
In this paper, we develop methods to “sample” a small realistic graph from a large Internet topology. Despite recent activity, modeling and generation of realistic graphs resembling the Internet is still not a resolved issue. All previous work has attempted to grow such graphs from scratch. We address the complementary problem of shrinking an existing topology. In more detail, this work has three parts. First, we propose a number of reduction methods that can be categorized into three classes: (a) deletion methods, (b) contraction methods, and (c) exploration methods. We prove that some of them maintain key properties of the initial graph. We implement our methods and show that we can effectively reduce the nodes of an Internet graph by as much as 70% while maintaining its important properties. Second, we show that our reduced graphs compare favorably against construction-based generators. Finally, we successfully validate the effectiveness of our best methods in an actual performance evaluation study of multicast routing. Apart from its practical applications, the problem of graph sampling is of independent interest.