New Directions and Half-Baked Ideas in Topology Modeling: New Directions and Half-Baked Ideas in Topology Modeling Ellen W. Zegura College of Computing Georgia Tech


Outline: Outline A very little bit of background Thoughts on: Alternative Internet models Scaling Application-driven topology modeling


Networking background: Networking background access networks hosts/endsystems routers domains/autonomous systems exchange point stub domains transit domains border routers peering lowly worm


Topo modeling: state-of-the-art: Topo modeling: state-of-the-art Graph representation Router-level modeling vertices are routers edges are one-hop IP connectivity Domain- (AS-) level modeling vertices are domains (ASes) edges are peering relationships Mostly undirected and unlabeled graphs


Alternative Internet models: Alternative Internet models Intermediate AS/router level model explicit representation for 'important' routers (border routers and exchange points) Hybrid real/synthetic model Fluid-flow topology model what might this mean? alternatives to graph-based models?


1: Intermediate AS/router level: 1: Intermediate AS/router level exchange point stub domains transit domains border routers one super-vertex per domain one vertex per exchange point and border router explicit representation of border routers endpoints of edges are border routers or exchange points


2: Hybrid real/synthetic model: 2: Hybrid real/synthetic model Create database of real data for autonomous system topology Use synthetic model for high-level structure Populate synthetic model using real data stub domains transit domains transit stub


III: “Fluid-flow” topology model: III: 'Fluid-flow' topology model What does this mean? alternatives to graph-based models Example: ASes occupy 2-d space; overlapping ASes can exchange traffic


Scaling: Scaling Problem: what are the smallest topology models that capture the interesting properties? One approach: canonical topologies with a size parameter (Too) simple examples: ring, star, trees, parking lot, …


Possible models: Possible models Domain star: One router per stub domain One transit domain One transit router per stub domain (or per k stub domains)


Possible models: Possible models Domain single bottleneck: bottleneck between xit domains different distances between stub domains


What else?: What else? More transit domains Hierarchy in transit domains More multihoming (stub domain connected to more than one transit domain) Routing rules? Closer look at needs of applications


Application-driven models: Application-driven models Rather than designing general models, let’s think about what particular problems need Examples: BGP analysis peer-to-peer (or overlay) system design


BGP analysis: BGP analysis BGP – interdomain routing protocol external BGP – between domains internal BGP – within a domain BGP problems: stability (do the routes oscillate?) convergence time what are the modeling needs? topology plus peering policies for stability: worst case topologies for convergence: typical topologies?


Peer-to-peer/overlay networks: Peer-to-peer/overlay networks Endsystems in base network are overlay network nodes; paths in base network are overlay network links Overlay problems: quality of overlay (length of overlay paths, load on base links,…) what are the modeling needs? AS-level alone is sufficient? intermediate AS/router-level is better?


More questions: More questions What topology models are appropriate for wireless/ad-hoc/sensor networks? What additional information is useful besides basic topology? Can a focus on the use of models lead to improved ability to evaluate the quality of models? How much do you need to know about today’s Internet to design decent models?