Topology Modeling: First-Principles ApproachChallengesTrends in Topology ModelingSlide 4Degree-Based Models of TopologyFeatures of Degree-Based ModelsLi et al.Router Technology ConstraintAggregate Router FeasibilityVariability in End-User BandwidthsSlide 11Slide 12Metrics for Comparison: Network PerformanceStructure Determines PerformanceLikelihood-Related MetricSlide 16Topology Modeling: First-Principles ApproachAditya AkellaSupplemental Slides03/30/2007•Evaluate performance of protocols•Protect Internet•Resource provisioning•Understand large scale networksWhy Topology ModelingChallenges•Large Size•Real topologies are not publicly available•Incredible variability in many aspectsTrends in Topology ModelingObservationModeling Approach•Real networks are not random, but have obvious hierarchy.•Structural models (GT-ITM Calvert/Zegura, 1996)•Long-range links are expensive•Random graph models (Waxman, 1988)•Internet topologies exhibit power law degree distributions (Faloutsos et al., 1999)•Degree-based models replicate power-law degree sequencesA 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 #nodesDegree-Based Models of Topology•Expected Degree Sequence–Based on random graph models that skew probability distribution to produce power laws in expectation–Examples: Power Law Random Graph (PLRG), Generalized Random Graph (GRG)•Preferential Attachment–Growth by sequentially adding new nodes–New nodes connect preferentially to nodes having more connections–Examples: Inet, GPL, AB, BA, BRITE, CMU power-law generatorFeatures of Degree-Based Models•Degree sequence follows a power law (by construction)•High-degree nodes correspond to highly connected central “hubs”, which are crucial to the system•Achilles’ heel: robust to random failure, fragile to specific attack Preferential Attachment Expected Degree SequenceLi et al.•Consider the explicit design of the Internet–Annotated network graphs (capacity, bandwidth)–Technological and economic limitations–Network performance•Seek a theory for Internet topology that is explanatory and not merely descriptive.–Explain high variability in network connectivity–Ability to match large scale statistics (e.g. power laws) is only secondary evidence100101102Degree10-1100101102103Bandwidth (Gbps)15 x 10 GE15 x 3 x 1 GE 15 x 4 x OC12 15 x 8 FETechnology constraintTotal Bandwidth Bandwidth per Degree Router Technology ConstraintCisco 12416 GSR, circa 2002high BW low degreehigh degree low BW0.010.111010010001000010000010000001 10 100 1000 10000degreeTotal Router BW (Mbps)cisco 12416cisco 12410cisco 12406cisco 12404cisco 7500cisco 7200linksys 4-port routeruBR7246 cmts(cable)cisco 6260 dslam(DSL)cisco AS5850(dialup)approximateaggregatefeasible regionAggregate Router Feasibilitycore technologiesedge technologiesolder/cheaper technologiesRank (number of users)Connection Speed (Mbps)1e-11e-211e11e21e31e41e21 1e41e61e8Dial-up~56KbpsBroadbandCable/DSL~500KbpsEthernet10-100MbpsEthernet1-10Gbpsmost users have low speed connectionsa few users have very high speed connectionshigh performancecomputingacademic and corporateresidential and small businessVariability in End-User BandwidthsHeuristically Optimal TopologyHostsEdgesCoresMesh-like core of fast, low degree routersHigh degree nodes are at the edges.SOXSFGP/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 GbpsMetrics for Comparison: Network PerformanceGiven realistic technology constraints on routers, how well is the network able to carry traffic?Step 1: Constrain to be feasibleAbstracted Technologically Feasible Region110100100010000100000100000010 100 1000degreeBandwidth (Mbps)kBxtsBBxijrkjikijji jijiij ,..maxmax :,, ,Step 3: Compute max flow BiBjxijStep 2: Compute traffic demand jiijBBx PA PLRG/GRGHOTStructure Determines PerformanceP(g) = 1.19 x 1010P(g) = 1.64 x 1010 P(g) = 1.13 x 1012Likelihood-Related Metric•Easily computed for any graph•Depends on the structure of the graph, not the generation mechanism•Measures how “hub-like” the network core isjconnectedjiiddgL,)(Define the metric(di = degree of node i)For graphs resulting from probabilistic construction (e.g. PLRG/GRG), LogLikelihood (LLH)  L(g)Interpretation: How likely is a particular graph (having given node degree distribution) to be constructed?Lmaxl(g) = 1P(g) = 1.08 x 1010 P(g) Perfomance (bps)PAPLRG/GRGHOTAbilene-inspired Sub-optimal0 0.2 0.4 0.6 0.8 1 101010111012 l(g) = Relative