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

University Of Southern California, Los Angeles CA

Investigators

Abstract

Recent work has pointed out the existence of power-laws in the degree distribution of real-world networks. In retrospect, these findings while widely publicized are perhaps not surprising; power-laws for 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 properties of the Internet. Such interest is timely; recent work has also revealed that network topology properties may impact protocol performance Generating realistic topologies is a prerequisite for understanding the impact of topology on pro-tocol performance. Our recent work on topology generation motivates the proposed research and is driven by the perceived dichotomy between structural generators those that explicity embody some notion of hierarchy in constructing topologies and connectivity-based generators those that at-tempt to generate topologies with power-law degree distributions. Our preliminary research on this larger question reveals several interesting results: that real net-works are well-modeled by connectivity-based generators, and that these generators result in graphs with a continuum of levels of hierarchy. Continuing on from this work, our proposed research will at-tempt to increase our fundamental understanding of the structure of real networks, and their impact on protocol performance. Conceptually, our proposed research has three interrelated parts: understand-ing hierarchy in real networks, devising structural models for topology construction based on Highly Optimized 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 areas of topology modeling. In a larger sense, it may develop methods that can be used to understand the physical processes that lead to the development of other real-world networks, such as the Web topology and social networks.