DOC PREVIEW
Berkeley COMPSCI 268 - Lecture Notes

This preview shows page 1-2-15-16-31-32 out of 32 pages.

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

Unformatted text preview:

CS 268: Computer NetworkingL-14 Network TopologySensor Networks• Structural generators• Power laws• HOT graphs• Graph generators• Assigned reading• On Power-Law Relationships of the InternetTopology• A First Principles Approach to Understandingthe Internet’s Router-level Topology2Outline• Motivation/Background• Power Laws• Optimization Models• Graph Generation3Why Study Topology?• Correctness of network protocols typicallyindependent of topology• Performance of networks criticallydependent on topology• e.g., convergence of route information• Internet impossible to replicate• Modeling of topology needed to generatetest topologies4Internet TopologiesAT&TSPRINTMCIAT&TMCI SPRINTRouter levelAutonomous System (AS) level5More on Topologies ...• Router level topologies reflect physical connectivitybetween nodes• Inferred from tools like traceroute or well known publicmeasurement projects like Mercator and Skitter• AS graph reflects a peering relationship between twoproviders/clients• Inferred from inter-domain routers that run BGP and public projectslike Oregon Route Views• Inferring both is difficult, and often inaccurate6Hub-and-Spoke Topology• Single hub node• Common in enterprise networks• Main location and satellite sites• Simple design and trivial routing• Problems• Single point of failure• Bandwidth limitations• High delay between sites• Costs to backhaul to hub7Simple Alternatives to Hub-and-Spoke• Dual Hub-and-Spoke• Higher reliability• Higher cost• Good building block• Levels of Hierarchy• Reduce backhaul cost• Aggregate the bandwidth• Shorter site-to-site delay…8Critical Evolution of the Internet• NSFNet• 1st Gen (1985): 56 kbps /LSI-11s, six SC centers• 2nd Gen (1988): T1/IBM RTs, SC sites + regional nets• 3rd Gen (1991): T3/RS6000; Migration to MCI PoPs• 1993: Commercialization plan; NSF phase out by 4/95;NCSA Mosaic• 1994-1995: Privatization of the NSFNet, ISPconnectivity, Network Access Point (NAP) Architecture• 1995- : vBNS, Internet2, Abilene• WWW, Netscape• Telecommunications Act of 1996• Massive mergers yielding giants like SBC, MCI-Worldcom-Sprint, AT&T-TCI, AOL-Time Warner, andnew service providers like QwestThe ARPANet• Paul Baran– RAND Corp, early 1960s– Communications networksthat would survive a majorenemy attack• ARPANet: Researchvehicle for “ResourceSharing ComputerNetworks”– 2 September 1969: UCLAfirst node on the ARPANet– December 1969: 4 nodesconnected by phone linesSRI940UCLASigma 7UCSBIBM 360UtahPDP 10IMPsBBN team that implementedthe interface message processorVarious Research and CommercialBackbonesQwest IP Backbone (Late 1999)Digex BackboneGTE Internetworking BackboneAbilene Internet2 Backbone15SOXSFGP/AMPATHU. FloridaU. So. FloridaMiss StateGigaPoPWiscRENSURFNetRutgers U.MANLANNorthernCrossroadsMid-AtlanticCrossroadsDrexel U.U. DelawarePSCNCNI/MCNCMAGPIUMD NGIXDARPABossNetGEANTSeattleSunnyvaleLos AngelesHoustonDenverKansasCityIndian-apolisAtlantaWash D.C.ChicagoNew YorkOARNETNorthern LightsIndiana GigaPoPMeritU. LouisvilleNYSERNetU. MemphisGreat PlainsOneNetArizona St.U. ArizonaQwest LabsUNMOregonGigaPoPFront RangeGigaPoPTexas TechTulane U.North TexasGigaPoPTexasGigaPoPLaNetUT AustinCENICUniNetWIDEAMES NGIXPacificNorthwestGigaPoPU. HawaiiPacificWaveESnetTransPAC/APANIowa St.Florida A&MUT-SWMed Ctr.NCSAMRENSINetWPIStarLightIntermountainGigaPoPAbilene BackbonePhysical Connectivity(as of December 16, 2003)0.1-0.5 Gbps0.5-1.0 Gbps1.0-5.0 Gbps5.0-10.0 Gbps16Metropolitan Area Exchanges/Network Access PointsTier 1 Connections: High speed FDDI switches + routers with huge routing tablesTier 2 Connections: regional connection pointsMAE does not provide peering, just connection b/w to co-located ISPsPoints-of-Presence (PoPs)• Inter-PoP links• Long distances• High bandwidth• Intra-PoP links• Short cables betweenracks or floors• Aggregated bandwidth• Links to othernetworks• Wide range of mediaand bandwidthIntra-PoPOther networksInter-PoP18Deciding Where to Locate Nodes and Links• Placing Points-of-Presence (PoPs)• Large population of potential customers• Other providers or exchange points• Cost and availability of real-estate• Mostly in major metropolitan areas• Placing links between PoPs• Already fiber in the ground• Needed to limit propagation delay• Needed to handle the traffic load19Trends in Topology ModelingObservation• Long-range links are expensive• Real networks are not random,but have obvious hierarchy• Internet topologies exhibitpower law degree distributions(Faloutsos et al., 1999)• Physical networks have hardtechnological (and economic)constraints.Modeling Approach• Random graph (Waxman88)• Structural models (GT-ITMCalvert/Zegura, 1996)• Degree-based models replicatepower-law degree sequences• Optimization-driven modelstopologies consistent with designtradeoffs of network engineers20Waxman Model (Waxman 1988)• Router level model• Nodes placed at random in2-d space with dimension L• Probability of edge (u,v):• ae-d/(bL), whered is Euclidean distance (u,v),a and b are constants• Models locality21vud(u,v)Real World Topologies• Real networks exhibit• Hierarchical structure• Specialized nodes (transit, stub, ...)• Connectivity requirements• Redundancy• Characteristics incorporated into theGeorgia Tech Internetwork TopologyModels (GT-ITM) simulator (E. Zegura,K.Calvert, M.J. Donahoo, 1995)22Transit-Stub Model (Zegura 1997)• Router level model• Transit domains• Placed in 2-d space• Populated with routers• Connected to each other• Stub domains• Placed in 2-d space• Populated with routers• Connected to transit domains• Models hierarchy23So… Are We Done?• No!• In 1999, Faloutsos, Faloutsos, Faloutsospublished a paper, demonstrating powerlaw relationships in Internet graphs• Specifically, the node degree distributionexhibited power lawsThat Changed Everything…..24Outline• Motivation/Background• Power Laws• Optimization Models• Graph Generation25Power Laws in AS Level Topology26A few nodes have lots of connectionsRank R(d)Degree dSource: Faloutsos et al. (1999)Power Laws and Internet Topology• Router-level graph & Autonomous System (AS) graph• Led to active research in degree-based network modelsMost nodes have few connectionsR(d) = P (D>d) x #nodesGT-ITM Abandoned ...• GT-ITM did not give power law degreegraphs• New topology


View Full Document

Berkeley COMPSCI 268 - Lecture Notes

Documents in this Course
Lecture 8

Lecture 8

33 pages

L-17 P2P

L-17 P2P

50 pages

Multicast

Multicast

54 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?