Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2005.11.010 Byline: Danny Dolev (a), Sugih Jamin (b), Osnat (Ossi) Mokryn (c), Yuval Shavitt (c) Keywords: Directed graph; AS relationships; Valley free routing Abstract: We investigate the resiliency of the Internet at the Autonomous System (AS) level to failures and attacks, under the real constraint of business agreements between the ASs. The agreements impose policies that govern routing in the AS level, and thus the resulting topology graph is directed, and thus the reachability between Ases is not transitive. We show, using partial views obtained from the Internet, that the Internet's resiliency to a deliberate attack is much smaller than previously found, and its reachability is also somewhat lower under random failures. We use different metrics to measure resiliency, and also investigate the effect of added backup connectivity on the resiliency. Author Affiliation: (a) School of Engineering and Computer Science, The Hebrew University, Jerusalem 91904, Israel (b) Department of EECS, University of Michigan, Michigan, United States (c) School of Electrical Engineering, Tel Aviv University, Ramat Aviv 69978, Israel Article History: Received 4 August 2004; Revised 26 June 2005; Accepted 7 November 2005 Article Note: (miscellaneous) Responsible Editor: J. Hou

The rich get richer principle, manifested by the Preferential attachment (PA) mechanism, is widely considered one of the major factors in the growth of real-world networks. PA stipulates that popular nodes are bound to be more attractive than less popular nodes; for example, highly cited papers are more likely to garner further citations. However, it overlooks the transient nature of popularity, which is often governed by trends. Here, we show that in a wide range of real-world networks the recent popularity of a node, i.e., the extent by which it accumulated links recently, significantly influences its attractiveness and ability to accumulate further links. We proceed to model this observation with a natural extension to PA, named Trending Preferential Attachment (TPA), in which edges become less influential as they age. TPA quantitatively parametrizes a fundamental network property, namely the network’s tendency to trends. Through TPA, we find that real-world networks tend to be moderately to highly trendy. Networks are characterized by different susceptibilities to trends, which determine their structure to a large extent. Trendy networks display complex structural traits, such as modular community structure and degree-assortativity, occurring regularly in real-world networks. In summary, this work addresses an inherent trait of complex networks, which greatly affects their growth and structure, and develops a unified model to address its interaction with preferential attachment. [ABSTRACT FROM AUTHOR]

This work presents a thorough investigation of the structure of multicast trees cut from the Internet and power-law topologies. Based on both generated topologies and real Internet data, we characterize the structure of such trees and show that they obey the rank-degree power law; that most high degree tree nodes are concentrated in a low diameter neighborhood; and that the sub-tree size also obeys a power law. Our most surprising empirical finding suggests that there is a linear ratio between the number of high degree network nodes, namely nodes whose tree degree is higher than some constant, and the number of leaf nodes in the multicast tree (clients). We also derive this ratio analytically. Based on this finding, we develop the Fast Algorithm, that estimates the number of clients, and show that it converges faster than one round trip delay from the root to a randomly selected client. [ABSTRACT FROM AUTHOR]