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.