Slide 1Slide 2Slide 3Slide 4Slide 5This Lecture: Common Thread1. Network StructureSlide 8A Scientist’s PerspectiveSlide 10Another Scientific ViewpointBasics: The Log-Log PlotSlide 13Power law + Small worldA Level Up: The InternetSlide 16Slide 17Slide 18Main ResultSlide 20Slide 21Policy RoutingSlide 23Slide 24Slide 25DiscussionAnother Level Up: ApplicationsStudy of GnutellaGnutella StructureSlide 30Slide 31Churn CharacteristicsSlide 33Slide 34Traffic VolumeSlide 36Slide 37Overlay-Network MatchSlide 39Another level Up: The Users, Humans, …SummarySlide 42CS 525: Advanced Distributed SystemsSpring 08Structure of Networks (Continued)Indranil GuptaApril 24 and 29, 20081981Countries=nodesTreaties=edgesGraph or Network1992The Internet (Internet Mapping Project, color coded by ISPs)PCs=nodesConnected=edgesFood Web of Little Rock Lake,WIElectric Power GridMetabolic reaction networkThis Lecture: Common ThreadNetworks–Structure of,–Dynamics within,•We’ll study networks at three different “levels”1. Network Structure•“Six degrees of Kevin Bacon”•Milgram’s experiment in 1970•Watts and Strogatz Model•Kleinberg’s algorithmic results•Recent work on mapping Internet, WWW, p2p overlays, electric power grid, protein networks, co-authorship among scientists•These networks have “evolved naturally”Ring graphFully Connected graphRandom graphPower Law GraphA Scientist’s Perspective•Two important metrics–Clustering Coefficient: CC•Pr(A-B edge, given an A-C edge and a C-B edge)–Path Length of shortest path•Ring graph: high CC, long paths•Random graph: low CC, short paths•Small World Networks: high CC, short pathsRing graphRandom GraphClustering CoefficientPath LengthSmall World NetworksConvert more and more edges to point to random nodesAnother Scientific ViewpointThat was about “nature of neighbors”; what about number of neighbors?Degree distribution – what is the probability of a given node having k edges (neighbors, friends, …)•Regular graph: all nodes same degree•Gaussian•Random graph: Exponential•Power law:kcke.log (number of nodes)log (node degree=k)Basics: The Log-Log PlotPower lawExponentialHeavy tailed1 10 100 10001 100 10000 1000000Number of nodes with degree k is ~ kWWW is a power law graph NCSTRL co-author graphs is power law, with exponential cutoffElectric Power Grid graphis exponentialSocial network of Utah Mormons is Gaussian4.21.2 Power law + Small worldMost nodes have small degree, but a few nodes have high degreeAttacks on small world networks•Killing a large number of randomly chosen nodes does not disconnect graph•Killing a few high-degree nodes will disconnect graph“A few (of the many thousand) nutrients are very important to your body”“The Electric Grid is very vulnerable to terrorists”A Level Up: The Internet•[Faloutsos et al] showed that the Internet backbone follows a power law distribution•[One kind of Dynamism over such a network?]•[Faloutsos et al] showed that the Internet backbone follows a power law distribution•[One kind of Dynamism over such a network?]•Routing [Akella et al] What is the stress on Internet routers due to–Shortest path routing (“efficient”)–Policy based routing (BGP)AS’sThe Internet is growingHow does the stress scale?Internet is a multi-level topologyAt the highest level, it consists of AS’sAS’s consist of subnets, then LANS, …AS-AS routing is done by BGPMain Result•Take a power law network (node has degree k with probability )•Shortest path routing, with ties broken by higher degree•With uniform traffic model for all pairs of end nodes, maximum edge congestion grows as [Theorem 1])(11nOkLog-log plot againPower-law and Tree network topologies give superlinear congestionExponential Network has sublinear congestion[why?]+ Shortest-path routing has worse max edge congestion than with uniform trafficClout Traffic Model: well-connected nodes generate more trafficPolicy Routing•Due to ISP to ISP financial contracts, AS to AS edges are either–Customer-provider edges, or–Peering edges•Policy routing prefers customer provider traffic•Gives “valley free” paths: most edges are customer provider+ Policy routing also gives superlinear growth, but is better than shortest path routingClout Traffic Model: well-connected nodes generate more trafficSynthetic GraphsReal GraphsPolicy-based and Shortest Path Routing give similar edge congestion for the uniform traffic modelA Solution: Add redundant edges between selective node pairsCongestion varies linearly withnDiscussion•Metrics: max edge congestion (why not average?)–Instability from single source could spread•Think “Electric Power Grid failures”•Think “self-synchronizing routers”•Why is Shortest Path Routing always worse than Policy Routing?–Shortest Path Routing is supposed to be “efficient”–Outrageous Opinion: Should the design of Internet be left to non-technicians?Another Level Up: ApplicationsStudy of Gnutella•[Ripeanu et al]•Gnutella–Peer to peer Overlay–Users download songs from other users, upload their own songs–Each computer host = “peer”–Completely decentralizedGnutella StructurePPPPPPServents (“Peers”)PConnected in an overlay graphStore their ownfilesAlso store “peer pointers”Queries flooded out, ttl-restrictedStudy of Gnutella•6 month period 10/00-5/01–Before revision of Gnutella protocol (late 2001)•Characteristics–System Size–Network Traffic–Node Connectivity95% of nodes in largest connected componentQuick Growth over time (exponential?)SpikesChurn Characteristics•40% of nodes logged in for less than 4 hours•25% nodes alive for more than 24 hours55% ping-pong messages (membership)36% query messagesSubsequent improvements reduced these to 8%, 92%95% of nodes less than 7 hops away[Implication of ttl=7 for query messages? ]Traffic Volume•170 K connexns for 50 K node Gnutella•6 KBps per connexn 1 GBps total 330 TB/month•1.7% of total traffic in Internet Backbone•Recall: [3/00] 25% UWisc traffic from NapsterAverage degree of node is scale-independentOn average 3.4 edges / nodeNot power lawBut Heavy-tailedOverlay-Network Match•Does the Gnutella Overlay reflect the underlying Internet structure?•Entropy technique in paper–Nodes identified with their domain
View Full Document
Unlocking...