ITR/SI: On Topologies, Power Laws, and Hierarchies

最近的工作指出了现实世界网络的度分布中存在幂定律。回想起来，这些发现虽然被广泛宣传，但或许并不令人惊讶；现实世界现象中各种大小概念的幂定律已经众所周知几十年了。然而，这些发现引发了人们对互联网结构和宏观特性的广泛兴趣。这种兴趣是及时的；最近的工作还表明，网络拓扑属性可能会影响协议性能。生成真实的拓扑是理解拓扑对协议性能影响的先决条件。我们最近在拓扑生成方面的工作推动了这项研究，并受到结构生成器和基于连通性的生成器之间的二分性的影响，结构生成器显式地体现了构造拓扑时的层次性，而基于连通性的生成器往往生成具有幂率度分布的拓扑。我们对这个更大的问题的初步研究揭示了几个有趣的结果：真实的网络由基于连通性的生成器很好地建模，并且这些生成器产生的图具有连续的层次结构。在这项工作的基础上，我们提出的研究将试图增加我们对真实网络结构及其对协议性能影响的基本理解。从概念上讲，我们提出的研究包括三个相互关联的部分：理解真实网络中的层次结构，设计基于高度优化容错的拓扑构造结构模型，以及更密切地研究拓扑对协议性能的影响。直到最近，网络的结构及其对协议的影响还很少受到关注。就更广泛的影响而言，这项工作有可能在拓扑建模领域取得根本性进展。在更广泛的意义上，它可能会开发出一些方法，这些方法可以用来理解导致其他真实世界网络发展的物理过程，例如网络拓扑和社交网络。

Recent work has pointed out the existence of power-laws in the degree distribution of real-worldnetworks. In retrospect, these findings while widely publicized are perhaps not surprising; power-lawsfor various notions of size in real-world phenomena have been known for several decades.Nevertheless, these findings have sparked extensive interest in the structure and macroscopic propertiesof the Internet. Such interest is timely; recent work has also revealed that network topology propertiesmay impact protocol performance Generating realistic topologies is a prerequisite for understanding the impact of topology on pro-tocolperformance. Our recent work on topology generation motivates the proposed research and isdriven by the perceived dichotomy between structural generators those that explicity embody somenotion of hierarchy in constructing topologies and connectivity-based generators those that at-temptto generate topologies with power-law degree distributions. Our preliminary research on this larger question reveals several interesting results: that real net-worksare well-modeled by connectivity-based generators, and that these generators result in graphswith a continuum of levels of hierarchy. Continuing on from this work, our proposed research will at-temptto increase our fundamental understanding of the structure of real networks, and their impact onprotocol performance. Conceptually, our proposed research has three interrelated parts: understand-inghierarchy in real networks, devising structural models for topology construction based on HighlyOptimized Tolerance, and examining more closely the impact of topology on protocol performance. The structure of networks, and their impact on protocols, has received little attention until recently.In terms of broader impact, this work has the potential for making fundamental progress in the areasof topology modeling. In a larger sense, it may develop methods that can be used to understand thephysical processes that lead to the development of other real-world networks, such as the Web topologyand social networks.