more on Internet topology

[David Farber <dave () farber net>]

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