DOC PREVIEW
CMU CS 15744 - Network Topology

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 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 10 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 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Network TopologyJulian ShunOn Power-Law Relationships of the Internet Topology (Faloutsos 1999)• Observes that Internet graphs can be described by “power laws” (P[X > x] = kax-aL(x) )• Introduces power-law exponents to characterize Internet graphs• Comments– Limited data• Especially linear fit to measure hop-plot exponents (Fig. 7 and 8)– How well have power laws held up since 1999?– Explanatory power of power-law exponents?– Other metrics?Data• Power Laws and the AS-Level Internet Topology (Siganos, Faloutsos, 2003)– Use much more data, obtained from Route Views– Shows that power laws continue to hold for AS topology over 5 year interval– Variation of power-law exponents less than 10%5-year intervals of exponentsData• Measuring ISP Topologies with Rocketfuel(Spring, Mahajan and Wetherall, 2002)– Obtains much more router-level data, and show that the topologies mostly obey a power law• Faloutsos’ 1999 paper won "Test of Time" award at SIGCOMM 2010A First-Principles Approach to Understanding the Internet’s Router-level Topology (Li et.al. 2004)• Argues that previous metrics do not accurately model real Internet graphs• Introduces metrics based on first principles, such as throughput, router utilization, end user bandwidth distribution, likelihood metric• Comments– Does not use real Internet data in evaluation– Does not incorporate robustness into model– Applicable to AS-level topology?– Other metrics?DataApplicability to AS-level topology• Too many factors, such as political and economical ones, to consider• AS graph, Web graph, P2P networks left for future workOther metrics• Distance distribution d(x) – the number of pairs of nodes distance x, divided by the total number of pairs (Shenker et.al. 2002)• Betweenness – weighted sum of # of shortest paths passing through a node or link (related to router utilization) (HOT paper and Shenker et.al. 2002)• Clustering C(k) – how close neighbors of the average k-degree node are to forming a clique (Bu and Towsley2002)• dK-distribution – describes the correlation of degrees of d connected nodes (Vahdat et. Al. 2006)Why is this important?• Gain more insight into structure of Internet• Create graph generators that produce “Internet-like” graphs for testing• Open question: How can we model the time evolution of Internet


View Full Document

CMU CS 15744 - Network Topology

Documents in this Course
Lecture

Lecture

25 pages

Lecture

Lecture

10 pages

Lecture

Lecture

10 pages

Lecture

Lecture

45 pages

Lecture

Lecture

48 pages

Lecture

Lecture

19 pages

Lecture

Lecture

97 pages

Lecture

Lecture

39 pages

Lecture

Lecture

49 pages

Lecture

Lecture

33 pages

Lecture

Lecture

21 pages

Lecture

Lecture

52 pages

Problem

Problem

9 pages

Lecture

Lecture

6 pages

03-BGP

03-BGP

13 pages

Lecture

Lecture

42 pages

lecture

lecture

54 pages

lecture

lecture

21 pages

Lecture

Lecture

18 pages

Lecture

Lecture

18 pages

Lecture

Lecture

58 pages

lecture

lecture

17 pages

lecture

lecture

46 pages

Lecture

Lecture

72 pages

Lecture

Lecture

44 pages

Lecture

Lecture

13 pages

Lecture

Lecture

22 pages

Lecture

Lecture

48 pages

lecture

lecture

73 pages

17-DNS

17-DNS

52 pages

Lecture

Lecture

10 pages

lecture

lecture

53 pages

lecture

lecture

51 pages

Wireless

Wireless

27 pages

lecture

lecture

14 pages

lecture

lecture

18 pages

Lecture

Lecture

16 pages

Lecture

Lecture

14 pages

lecture

lecture

16 pages

Lecture

Lecture

16 pages

Lecture

Lecture

37 pages

Lecture

Lecture

44 pages

Lecture

Lecture

11 pages

Lecture

Lecture

61 pages

Multicast

Multicast

61 pages

Lecture

Lecture

19 pages

Lecture

Lecture

8 pages

Lecture

Lecture

81 pages

Lecture

Lecture

9 pages

Lecture

Lecture

6 pages

Lecture

Lecture

63 pages

Lecture

Lecture

13 pages

Lecture

Lecture

63 pages

Lecture

Lecture

50 pages

lecture

lecture

35 pages

Lecture

Lecture

47 pages

Lecture

Lecture

29 pages

Lecture

Lecture

92 pages

Load more
Download Network Topology
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 Network Topology 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 Network Topology 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?