Interesting People mailing list archives
more on Internet topology
From: David Farber <dave () farber net>
Date: Sun, 10 May 2009 07:51:20 -0400
Begin forwarded message: From: Rodney Van Meter <rdv () sfc wide ad jp> Date: May 10, 2009 7:09:24 AM EDT To: David Farber <dave () farber net> Subject: more on Internet topology Dave,This might not be the forum to discuss the technical details, but I got several requests for more information about the Internet topology after my IP message last week. So, for IP if you want to flog this, and not if you don't...
I definitely owe a debt to Joe Touch and John Heidemann on this topic, as well as other ISI and ex-ISI folks.
I am co-teaching Jun Murai's class for master's students. "Internet Evolution and Possibilities" or "History and Future Possibility of the Internet" is the way we translated the class title from the Japanese, but "The Evolving Internet" would be more elegant in English. One of the that we topics that introduce is measurement/study of the Internet topology. http://gc.sfc.keio.ac.jp/cgi/class/class_top.cgi?2008_25894+e will get you into the right ballpark for the 2008-9 version of the class. The next-to-last lecture is about topology. Apologies, but the website is 90+% in Japanese. The actual slides are about 70% English, and the lecture itself is 90% in English. Click the TV icon in the upper left for video. One of the stimuli for this topic is the recent appearance of an article (in Japanese) in the March 2008 IPSJ (Info. Proc. Soc. Japan) Magazine, titled, "How Do We Construct Networks Robust Against Both Random Failure and External Attacks?" by Toshihiro TANIZAWA (Kochi National College of Technology). Unfortunately, Tanizawa (who is a physicist), has some interesting points, but seems to be behind on the literature, so I'm going to try to correct that in class. Here's what I think I know: 1) The AS-level topology (as well as that of individual networks), can more or less be described as a "scale-free" graph. (It's not exact, but a reasonable approximation, but read on...) 2) Starting almost a decade ago, some physicists from Notre Dame, including Barabasi, started a shtick about how many kinds of networks, including the Internet, are "robust yet fragile", since they are scale-free: delete a random node and the net is fine, but target a central hub, and the network goes down in flames. Barabasi & co. have published in _Nature_, _Science_ and _Reviews of Modern Physics_ and have collected thousands of citations for their work. 3) Some actual Internet researchers, including John Doyle from Caltech and Ramesh Govindan from the University of Southern California, responded, saying, "Hang on, you don't understand the Internet. It's both better and worse than you imagine." Doyle & co. pointed out that the analysis by Barabasi & collaborators is (a) based on an incomplete model of how the Internet works, and (b) not a mathematically complete description, anyway: 1) Scale-free (SF) is actually an incomplete specification of the interesting characteristics of a graph; there are many kinds of scale-free networks. In the real Internet, high-degree nodes tend to be toward the edge, not central hubs, as Barabasi et al. assumed. Barabasi's particular preferred form of SF is preferential attachment (PA-SF). 2) Looking at AS-level topology in the abstract ignores facts about how ASes really operate. (Note that Barabasi focuses primarily on the router-level topology, rather than AS-level, but the points can actually be made about the router-level topo, too.) a) Each "node" is really a network, possibly with multiple edges connecting to any given neighbor, and it's kind of hard to imagine a whole "node" (AS) being taken out of the Internet (still vulnerable to a failure of the IGP, in theory). b) L3 topology and L2 topology may be different, and may include redundancy that means that failures are rarer than might otherwise be believed. 3) Economic and other factors drive growth and organizational behavior that means that the network is actually remarkably robust. a) It's not physically possible to build the highest-performance router that would be required by some of the Barabasi PA-SF networks, forcing a less centralized design than they imagine. b) Internet traffic has particular characteristics, and the network is *designed* (rather than randomly grown) to meet those characteristics; the performance of the real Internet far exceeds what the Barabasi PA-SF nets could handle. c) The Internet's deliberate separation of layered functionality contributes to a virtual connectivity that is largely independent of the physical connectivity. 4) The most serious risks to the Internet are not to individual "nodes" (ASes), but rather stem from the near-monocropping of Internet infrastructure and end nodes, and the vulnerability of the system to human error (and political/economic considerations): a) The chances of a bug in a Cisco (or possibly Juniper) routing protocol implementation. b) Known vulnerabilities, such as the lack of secure BGP (see also YouTube/Pakistan, the Czech Republic SupraNet incident, and the 2008 Cogent/Sprint spat for other ways in which routing can go wrong) and secure higher-level protocols (c.f. Kaminsky's DNS cache poisoning). c) "Fail on" errors, as Doyle calls them: DDoS attacks and other malware. Students will be asked to read a total of three papers to prepare for the lecture: * *ONE* of these two papers: - Doyle et al., Proc. Nat. Academy of Science, 102(41), 2005 - Willinger et al., Notices of the AMS, 56(5), 2009 * *TWO* of these other seven papers (free choice): - Heidemann et al., IMC 2008 - Tanizawa, IPSJ 49(3), 2008 (日本語) - Albert et al., Nature, 406, 2000 - Baran, Trans. on Communications, 12(1), 1964 - Xie et al., SIGCOMM 2007 - Gao, Trans. on Networking, 9(6), 2001 - Mahadevan et al., SIGCOMM 2006 @article{albert2000eaa, title={{Error and attack tolerance of complex networks}}, author={Albert, R. and Jeong, H. and Barabasi, A.L.}, journal={Nature}, volume={406}, number={6794}, pages={378--382}, year={2000}, comment={One of the suspect Internet topology papers.} } @article{baran1964dcn, title={{On Distributed Communications Networks}}, author={Baran, P.}, journal={Communications, IEEE Transactions on}, volume={12}, number={1}, pages={1--9}, year={1964}, comment={Classic paper saying 3-4x the minimum number of links is enough for a network to be survivable.} } @article{JohnCDoyle10112005,author = {Doyle, John C. and Alderson, David L. and Li, Lun and Low, Steven and Roughan, Matthew and Shalunov, Stanislav and Tanaka, Reiko and Willinger, Walter},
title = {{The "robust yet fragile" nature of the Internet}}, journal = {Proceedings of the National Academy of Sciences}, volume = {102}, number = {41}, pages = {14497-14502}, doi = {10.1073/pnas.0501426102}, year = {2005}, abstract = {The search for unifying properties of complex networks is popular, challenging, and important. For modeling approaches that focus on robustness and fragility as unifying concepts, the Internet is an especially attractive case study, mainly because its applications are ubiquitous and pervasive, and widely available expositions exist at every level of detail. Nevertheless, alternative approaches to modeling the Internet often make extremely different assumptions and derive opposite conclusions about fundamental properties of one and the same system. Fortunately, a detailed understanding of Internet technology combined with a unique ability to measure the network means that these differences can be understood thoroughly and resolved unambiguously. This article aims to make recent results of this process accessible beyond Internet specialists to the broader scientific community and to clarify several sources of basic methodological differences that are relevant beyond either the Internet or the two specific approaches focused on here (i.e., scale-free networks and highly optimized tolerance networks). }, URL = {http://www.pnas.org/cgi/content/abstract/102/41/14497}, eprint = {http://www.pnas.org/cgi/reprint/102/41/14497.pdf},comment = {The "response" to the article that Internet researchers didn't like.}
} @article{gao2001ias,title={{On inferring autonomous system relationships in the Internet}},
author={Gao, L.}, journal={IEEE/ACM Transactions On Networking}, volume={9}, number={6}, pages={733--745}, year={2001} } @inproceedings{heidemann2008cas, title={{Census and survey of the visible Internet}},author={Heidemann, J. and Govindan, R. and Papadopoulos, C. and Bartlett, G. and Bannister, J.}, booktitle={Proceedings of the 8th ACM SIGCOMM conference on Internet measurement},
pages={169--182}, year={2008}, organization={ACM New York, NY, USA} } @InProceedings{mahadevan:_degree_correl, author = {Priya Mahadevan and Dmitri Krioukov and Kevin Fall and Amin Vahdat}, title = {Systematic Topology Analysis and Generation Using Degree Correlations}, crossref = {sigcomm06},comment = {Fascinating article on ways to generate synthetic topologies
like the Internet. Good summary of prior work: spectrum, distance distribution, betweenness, node degree distribution, likelihood, assortativity coefficient, clustering. They introduce dK graphs. (topology generator)} } @Article{tanizawa08:_construct_networks, author = {Toshihiro Tanizawa}, title = {How Do We Construct Networks Robust Against Both Random Failure and External Attacks?}, journal = {IPSJ Magazine}, year = 2008, volume = 49, number = 3, pages = {50--57}, month = mar, note = {in Japanese}, comment = {Cites Barabasi, but not Doyle.} } @article{willinger2009mmi, title={Mathematics and the {Internet}: A Source of Enormous Confusion and Great Potential}, author={Walter Willinger and David Alderson and John C. Doyle}, journal={Notices of the American Mathematical Society}, volume={56}, number={5}, pages={586--599}, year={2009}, comment={Good paper. Everything by these guys seems to be good.} } @inproceedings{xie2007dia, title={{How dynamic are IP addresses?}},author={Xie, Y. and Yu, F. and Achan, K. and Gillum, E. and Goldszmidt, M. and Wobber, T.}, booktitle={Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications},
pages={301--312}, year={2007}, organization={ACM Press New York, NY, USA} } ===== Related resources: http://dir.yahoo.com/Computers_and_Internet/Internet/Maps/ --Rod ------------------------------------------- Archives: https://www.listbox.com/member/archive/247/=now RSS Feed: https://www.listbox.com/member/archive/rss/247/ Powered by Listbox: http://www.listbox.com
Current thread:
- more on Internet topology David Farber (May 10)