1 15-744: Computer Networking L-14 Network Topology Sensor Networks • Structural generators • Power laws • HOT graphs • Graph generators • Assigned reading • On Power-Law Relationships of the Internet Topology • A First Principles Approach to Understanding the Internet’s Router-level Topology 2 Outline • Motivation/Background • Power Laws • Optimization Models • Graph Generation 3 Why study topology? • Correctness of network protocols typically independent of topology • Performance of networks critically dependent on topology • e.g., convergence of route information • Internet impossible to replicate • Modeling of topology needed to generate test topologies 42 Internet topologies AT&T SPRINT MCI AT&T MCI SPRINT Router level Autonomous System (AS) level 5 More on topologies.. • Router level topologies reflect physical connectivity between nodes • Inferred from tools like traceroute or well known public measurement projects like Mercator and Skitter • AS graph reflects a peering relationship between two providers/clients • Inferred from inter-domain routers that run BGP and publlic projects like Oregon Route Views • Inferring both is difficult, and often inaccurate 6 Hub-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 hub 7 Simple 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 … 83 Abilene Internet2 Backbone 9 SOX SFGP/ AMPATH U. Florida U. So. Florida Miss State GigaPoP WiscREN SURFNet Rutgers U. MANLAN Northern Crossroads Mid-Atlantic Crossroads Drexel U. U. Delaware PSC NCNI/MCNC MAGPI UMD NGIX DARPA BossNet GEANT Seattle Sunnyvale Los Angeles Houston Denver Kansas City Indian- apolis Atlanta Wash D.C. Chicago New York OARNET Northern Lights Indiana GigaPoP Merit U. Louisville NYSERNet U. Memphis Great Plains OneNet Arizona St. U. Arizona Qwest Labs UNM Oregon GigaPoP Front Range GigaPoP Texas Tech Tulane U. North Texas GigaPoP Texas GigaPoP LaNet UT Austin CENIC UniNet WIDE AMES NGIX Pacific Northwest GigaPoP U. Hawaii Pacific Wave ESnet TransPAC/APAN Iowa St. Florida A&M UT-SW Med Ctr. NCSA MREN SINet WPI StarLight Intermountain GigaPoP Abilene Backbone Physical Connectivity (as of December 16, 2003) 0.1-0.5 Gbps 0.5-1.0 Gbps 1.0-5.0 Gbps 5.0-10.0 Gbps 10 Points-of-Presence (PoPs) • Inter-PoP links • Long distances • High bandwidth • Intra-PoP links • Short cables between racks or floors • Aggregated bandwidth • Links to other networks • Wide range of media and bandwidth Intra-PoP Other networks Inter-PoP 11 Deciding 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 load 124 Trends in Topology Modeling Observation • Long-range links are expensive • Real networks are not random, but have obvious hierarchy • Internet topologies exhibit power law degree distributions (Faloutsos et al., 1999) • Physical networks have hard technological (and economic) constraints. Modeling Approach • Random graph (Waxman88) • Structural models (GT-ITM Calvert/Zegura, 1996) • Degree-based models replicate power-law degree sequences • Optimization-driven models topologies consistent with design tradeoffs of network engineers 13 Waxman model (Waxman 1988) • Router level model • Nodes placed at random in 2-d space with dimension L • Probability of edge (u,v): • ae^{-d/(bL)}, where d is Euclidean distance (u,v), a and b are constants • Models locality 14 v u d(u,v) Real world topologies • Real networks exhibit • Hierarchical structure • Specialized nodes (transit, stub..) • Connectivity requirements • Redundancy • Characteristics incorporated into the Georgia Tech Internetwork Topology Models (GT-ITM) simulator (E. Zegura, K.Calvert and M.J. Donahoo, 1995) 15 Transit-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 hierarchy 165 So…are we done? • No! • In 1999, Faloutsos, Faloutsos and Faloutsos published a paper, demonstrating power law relationships in Internet graphs • Specifically, the node degree distribution exhibited power laws That Changed Everything….. 17 Outline • Motivation/Background • Power Laws • Optimization Models • Graph Generation 18 Power laws in AS level topology 19 A few nodes have lots of connections Rank R(d) Degree d Source: Faloutsos et al. (1999) Power Laws and Internet Topology • Router-level graph & Autonomous System (AS) graph • Led to active research in degree-based network models Most nodes have few connections R(d) = P (D>d) x #nodes6 GT-ITM abandoned.. • GT-ITM did not give power law degree graphs • New topology generators and explanation for power law degrees were sought • Focus of generators to match degree distribution of observed graph 21 Inet (Jin 2000) • Generate degree sequence • Build spanning tree over nodes with degree larger than 1, using preferential connectivity • randomly select node u not in tree • join u to existing node v with probability d(v)/Σd(w) • Connect degree 1 nodes using preferential connectivity • Add remaining edges using preferential connectivity 22 Power law random graph (PLRG) • Operations • assign degrees to nodes drawn from power law distribution • create kv copies of node v; kv degree of v. • randomly match nodes in pool • aggregate edges may be
View Full Document
Unlocking...