DOC PREVIEW
U of I CS 525 - Lecture notes

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1CS 525 Advanced Topics in Distributed SystemsSpring 07Indranil GuptaConcluding LectureJanuary 16, 2007 – May 1, 2007Agenda for today• Structure of Networks• Conclusion of Course Material• Course Evaluations1981 1981Countries=nodesTreaties=edgesGraph or Network1992The Internet (Internet Mapping Project, color coded by ISPs)PCs=nodesConnected=edges2Food 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: protein networks contain millions, 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 Graph3A 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 Coefficient (CC)Path 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’sexperiment• 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−=α4Power 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]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?]• 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 BGP5Main Result• Take a power law network (node has degree k with probability )• Use 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])(11α+nOα−k+ Shortest-path routing has worse max edge congestion than with uniform traffic1e+111e+121e+131e+141e+151e+164000 10000 50000Max. edge congestionNumber of nodesMax. link congestionΘ(n4)Θ(n6)Clout 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 superlineargrowth, but is better than shortest path routing1e+081e+091e+104000 10000 50000Max. edge congestionNumber of nodesPolicy routingΘ(n2)Θ(n3)Θ(n4)Clout Traffic Model: well-connected nodes generate more trafficDiscussion• 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: Applications6Study 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– Overlay characteristics– Network traffic95% of nodes less than 7 hops away[Implication of ttl=7 for query messages? ]Average degree of node is


View Full Document

U of I CS 525 - Lecture notes

Documents in this Course
Epidemics

Epidemics

12 pages

LECTURE

LECTURE

7 pages

LECTURE

LECTURE

39 pages

LECTURE

LECTURE

41 pages

P2P Apps

P2P Apps

49 pages

Lecture

Lecture

48 pages

Epidemics

Epidemics

69 pages

GRIFFIN

GRIFFIN

25 pages

Load more
Download Lecture notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?