Transcript PPT - personal homepage server for the University of Michigan

On the Impact of Route Monitor Selection
Ying Zhang* Zheng Zhang#
Z. Morley Mao* Y. Charlie Hu# Bruce M. Maggs^
University of Michigan* Purdue University#
Carnegie Mellon and Akamai Technologies^
1
Internet route monitoring systems
 Monitor the Internet routing system
 Establish passive, default-free BGP sessions with many networks
 Collect real-time BGP updates and periodic table snapshots
 Discover dynamic changes (e.g., misconfigs, routing attacks)
 Example public systems: RouteViews and RIPE
“I can reach
141.213.15.0/24”
via AE
AS 7018
Route monitor
“I can reach
141.213.15.0/24”
via DE
AS 3561
AS 1239
Prefix
141.213.15.0/24
Internet
2
Limited coverage
 Coverage and representativeness
 Only monitor a subset of ASes in the Internet
 Only monitor at most one router in each AS
 Difficulties in obtaining full coverage
 Scalability and privacy concerns
Route monitor
“I can reach
141.213.15.0/24”
via CFG
“I can reach
141.213.15.0/24”
via CDG
AS 3561
AS 7018
AS 1239
AS 237
AS 105
Internet
3
Limited visibility on IP Hijacking detection
 The accuracy of detection depends on route monitor systems’ visibility
 Example problems caused by limited visibility
 IP prefix hijacking: ASG hijacks ASE’s prefix
 Missed The route monitor system does not cover polluted ASes
Prefix p’s origin AS
has changed to be G
Path[p] = AG
Path[p] = ABE
Route monitor
Prefix p’s origin AS is E
Path[p] = CE
Path[p] = CE
Path[p] = BE
Path[p] = DE
Path[p] = BE
Path[p] = DE
AS 3561
AS 7018
AS 1239
Prefix p
Path[p] = E
AS 237
Path[p] = FG
Path[p] = FGDE
AS 105
Path[p] = G
Path[p] = GDE
Hijack:
Path[p] = G
4
Motivation
 Many research studies rely on BGP data from public
route monitors:
 Network topology discovery, AS relationship inference, AS level
path prediction, etc.
 The limitation of coverage and representativeness of the
monitors is critical to their results.
 Obtaining full coverage is difficult in practice.
 Understanding limitation can assist improved route
monitor placement.
5
Outline
Motivation
Methodology
Discovery of static network properties
Discovery of dynamic network properties
Inference of network properties
6
Methodology
 Data collection
 Public BGP monitoring vantage points: RouteViews and RIPE
 Private peering vantage points: 200 distinct ASes
 Comparison across different combinations of vantage points
 Monitor selection schemes




Random: select monitor nodes randomly
Degree based: select the node with largest degree
Greedy: select the node with largest unobserved links
Address block based: select the node originating largest IP
addresses
7
Outline
Motivation
Methodology
Discovery of static network
properties
Discovery of dynamic network properties
Inference of network properties
8
Static network properties





Network topology discovery
IP prefix to origin AS mappings
Identifying stub AS and its providers
Multi-homed ASes
Observed AS paths
9
Network topology discovery
 The number of observed AS level links
 Greedy based selection performs best
10
Multi-homed ASes discovery
 Discover multi-homed ASes to understand edge network
resilience
 Greedy based scheme performs best: additional
discovered links help discover multi-homed stub ASes
11
Outline
Motivation
Methodology
Discovery of static network properties
Discovery of dynamic network
properties
Inference of network properties
12
Dynamic network properties
 Routing instability monitoring
 Number of routing updates observed
 IP prefix hijacking detection
 The visibility of inconsistent origin ASes across routing updates
13
Routing instability monitoring
 Fraction of BGP routing events observed by the set of
vantage points
 Huge difference between random and other three: core
networks are more likely to observe network instabilities
14
IP Prefix hijacking detection
 Detected hijacking: as long as one vantage point can
observe hijacked routes
 Greedy based scheme performs slightly better
With 10 vantage points deployed,
0.35% of all possible attackervictim pairs can evade detection
15
Outline
Motivation
Methodology
Discovery of static network properties
Discovery of dynamic network properties
Inference of network properties
16
Inference of network properties
AS relationship inference
Commonly used Gao’s degree-based
relationship inference [Gao00]
AS-level path prediction
AS-relationship based profit-driven AS path
inference [Mao05]
AS-relationship-independent path prediction
[Muhlbauer06]
17
AS relationship inference and path
prediction
 Accuracy: comparing the predicted paths with the
observed paths
 More vantage points may not increase the accuracy
18
AS relationship inference and path
prediction – further explanation
 More vantage points may not increase the accuracy
 It may be due to nature of the degree-based relationship inference
 We study the changes of the top degree node per path
 More vantage points do not consistently improve the estimation of
the top degree nodes
19
Conclusion
 Examined the route monitor placement impact
on various applications
 Evaluated four simple placement schemes
 Demonstrated the limitation of studies relying on
the existing monitoring system
 Future work: develop a better placement
technique.
20
Thank you!
Questions?
21
AS relationship-independent path
prediction
 Recent proposed path prediction algorithm not relying on
AS relationships
 Matched percentage of unobserved does not increase
with more monitors
22