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
• A very little bit of background
• Thoughts on:
– Alternative Internet models
– Scaling
– Application-driven topology modeling
Networking background
transit domains
domains/autonomous systems
exchange point
border routers
peering
hosts/endsystems
routers
stub domains
access networks
lowly worm
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
1. Intermediate AS/router level model
–
explicit representation for “important” routers
(border routers and exchange points)
2. Hybrid real/synthetic model
3. Fluid-flow topology model
–
–
what might this mean?
alternatives to graph-based models?
1: Intermediate AS/router level
transit domains
exchange point
border routers
stub domains
• 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
transit domains
transit
stub
stub domains
• Create database of real data for autonomous
system topology
• Use synthetic model for high-level structure
• Populate synthetic model using real data
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
• 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
Domain star:
• One router per
stub domain
• One transit
domain
• One transit
router per stub
domain (or per
k stub domains)
Possible models
Domain single bottleneck:
• bottleneck between xit domains
• different distances between stub domains
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
• 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 – 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
• 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
• 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?