Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6This Lecture: Common ThreadLowermost Level: Basics, Physical Phenomena, and LifeComplexity of Networks1. Network StructureSlide 11A Scientist’s PerspectiveSlide 13Slide 14Another Scientific ViewpointBasics: The Log-Log PlotSlide 17Power law vs. Small WorldPower law + Small world2. Network DynamicsSlide 21Slide 22Self-Synchronizing FirefliesWhy the heart beats by itselfDiscussionA Level Up: The InternetSlide 27Slide 28Slide 29Main ResultSlide 31Slide 32Policy RoutingSlide 34Slide 35Slide 36Slide 37Another Level Up: ApplicationsStudy of GnutellaGnutella StructureSlide 41Slide 42Churn CharacteristicsSlide 44Slide 45Traffic VolumeSlide 47Slide 48Overlay-Network MatchSlide 50Another level Up: The Users, Humans, …SummarySlide 53Final Report GradingLast LectureCourse EvaluationsCS 525: Advanced Distributed SystemsSpring 08Structure of NetworksIndranil GuptaApril 24, 200819811981Countries=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”Lowermost Level: Basics, Physical Phenomena, and LifeComplexity of Networks•Structural: human population has 6 B nodes, there are millions of computers on the Internet…•Evolution: people make new friends all the time, ISP’s change hands all the time…•Diversity: some people are more popular, some friendships are more important…•Node Complexity: PCs have different CPUs, Windows is a complicated OS…•Emergent phenomena: simple end behavior complex system-wide behavior. If we understand the basics of climate change, why is the weather so unpredictable?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 nodesMost “natural evolved” networks are (probably) small world•Network of actors six degrees of Kevin Bacon•Network of humans Milgram’s experiment•Co-authorship network “Erdos Number”Another 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 vs. Small World•A lot of small world networks are power law graphs (Internet backbone, telephone call graph, protein networks)•Not all small world networks are power law (e.g., co-author networks)•Not all power law networks are small world•Preferential Model for network growth generates power law distributions [e.g., WWW]•Power law networks also called scale-freePower 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”2. Network Dynamics•Strogatz goes on to discuss dynamics of many “natural networks”•We’ll focus on dynamics w.r.t. the Internet and P2P networks in the papers [Akella et al] and [Ripeanu et al]•But let’s just touch a bit on oscillation dynamics in networks…•Networks of coupled dynamical systems•If each node is a dynamical system, and is affected by its neighbors, what behaviors emerge from the entire network?•E.g., Social networks, network of neurons in the brain, protein networks, …•An example of emergent behavior: self-synchronizationA group of oscillators canself-synchronizeSelf-Synchronizing Fireflies•Synchronizing Fireflies of Malaysia•Each firefly: •Is driven by an external stimulus so•Can show self-sync occurs when•For more details see [Strogatz’ non-linear dynamics textbook])sin(-A--AA Why the heart beats by itself•A few thousand sinoatrial cells•Each oscillating at its own frequency•Peskin’s model: when a cell fires, all other cells have a small jump in voltage •[Why does this self-synchronize?]–Think of two sinoatrial cells first•For more details, see [Strogatz’ book “Sync”]timevoltagefire! fire!fire!Discussion•Recall: where have we seen self-synchronization before in this course?•What is one problem where a self-synchronizing system could be used to design a distributed protocol?•Why is the co-authorship network different from the Internet if both follow an incremental / preferential construction?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
View Full Document
Unlocking...