Presentation Transcript
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?