Network Topology Measurement Yang Chen CS 8803 1

Network Topology Measurement Yang Chen CS 8803 1

Outline Big Picture ISP Topology Measurement Statistical Results Problems & Solutions 2

Heuristics for Internet Map Discovery R. Govindan and H. Tangmunarunkit INFOCOM 2000 3

Why do we need the topology? Understand the macroscopic properties of the Internet physical structure Network management Topology-aware algorithms Simulation and topology generation tools 4

On-going efforts CAIDA Skitter Router View 5

Fundamental: traceroute Prober sends packets with successively increased TTL. A router responds with ICMP time exceeded when the probe is with TTL 1 6

Fundamental: traceroute Geographic info can help on building up the topology. * Data from http://www.linkwan.com/vr/ 7

Fundamental: Tree map 1)Source routing 2)Multiple Vantage points 8

Address scan space BGP tables Route Table Database Informed Random Address Probing – A response from some IP address is considered as a sign that some prefix P of A must contain addressable nodes; – If P is an addressable prefix, the neighboring prefixes of P are also considered as possibly addressable. (128.8/16 and 128.10/16 are neighbors of 128.9/16) 9

Some results 150,000 interfaces and nearly 200,000 links Findings related to source route – Simulation demonstrated that In relatively sparse random networks, a few source route capable nodes ( 5%) are sufficient to discover 90% of the links. In fact, there are 8% routers support source route. – Source route discovered links do not skew the qualitative conclusion on the network statistics. 10

For example: degree distribution Similar observation on hop-pair distribution 11

Measuring ISP Topologies w ith Rocketfuel N.Spring, R. Mahajan and D. Wetherall ACM Sigcomm 2002 12

ISP network infrastructure Access Router Access Router Backbone Router Backbone Link 13

ISP topology measurement An old story: the blinds and the elephant ISP Traceroute 14

ISP topology measurement Traceroute Server 15

Focusing on one ISP – Directed probing Network * 192.9.9.0 * * * * * * * * blackrose.org Verio Sprint MCI LINX CERFnet IIJ PIPEX IAGnet * Next Hop 204.212.44.128 205.238.48.3 144.228.240.93 204.70.4.89 194.68.130.254 134.24.127.3 202.232.1.8 158.43.133.48 131.103.20.49 (Ann Arbor) (MAE-WEST) (Stockton) (San Francisco) (London) (San Diego) (Japan) (London) (Chicago) M/LP/Weight Path 0 234 266 237 3561 701 90 i 0 2914 1 90 i 0 1239 701 90 i 0 3561 1 90 i 0 5459 5413 1 90 i 0 1740 701 90 i 0 2497 701 90 i 0 1849 702 701 90 i 0 1225 2548 1 90 i 204.212.44.128 through AS234 205.238.48.3 through AS2914 144.228.240.93 through AS1239 204.70.4.89 through AS3561 194.68.130.254 through AS5459 134.24.127.3 through AS1740 202.232.1.8 through AS2497 158.43.133.48 through AS1849 131.103.20.49 through AS1225 BGP table source: RouteView project 16

Focusing on one ISP – Directed probing Traceroutes to dependent prefixes: All traceroutes to these pr efixes from any vantage point should transit the ISP. Depende nt prefixes can be readily identified from the BGP table. All A S-paths for the prefix would contain the number of the AS bein g mapped. Traceroutes from insiders: We call a traceroute server located in a dependent prefix an insider. Traceroutes from insiders to any prefix should transit the ISP. Traceroutes that are likely to transit the ISP based on some A S-path are called up/down traces. 17

Path/Query reduction Share Ingress Share egress Same next-hop AS number 18

Impacts of directed probing 1) Fraction of useful but pruned traces from 0.1 to 7% 2) Unnecessary traces around 6% over all the ISPs * Comparison based on Skitter data 19

Impacts of ingress reduction Overall, ingress reduction keeps only 12% of the traces chosen by directed probing. The number of vantage points that share an ingress by rank 20

Impacts of egress reduction Overall, egress reduction keeps only 18% of the Dependent prefix traces chosen by directed probing. The number of dependent prefixes that share an egress by rank 21

Impacts of next-hop reduction Overall, Next-hop AS reduction Reduces the number of traces to 5% of those chosen by directed probing. 22

POP sizes analysis 23

Power Law Complementary cumulative distribution function (CCDF) P(X x) Pareto Distribution x P( X x ) xmin k P( X x ) x k Power Law ln( y ) C ln( x ) 24

Router degree distribution 25

Peering structure 26

Difficulties in topology discovery Shared media Backup links Router Identification and annotation Alias resolution Completeness Validation Currently, none of them is completely solved! 27

POP hierarchy Naming convention, DNS information and neighbor inferring 28

Backbone topology AT&T Level 3 29

Alias Problem OR 30

Alias: is it a big deal? 31

Alias resolution Send a packet with unreachable port to certain interfaces which are possible alias. The corresponding ICMP port unreachable response will contain the source address. IP identifier 32

Completeness validation Comparison with Router Views Comparison with Skitter IP address space – Search prefixes of ISP’s address space for additional IP addresses Validation with ISPs – Is “Good” enough? 33

In Search of Path Diversity in ISP Networks P. Teixeira, K. Marzullo, S. Savag e and G. M. Voelker IMC 2003 34

Real metric instead of counting links Path diversity – Metric that reflects the number of routes available between two points in the network An extreme example 35

Real topology speaks Inter-PoP Path diversity in the Sprint Network Inter-PoP Path diversity inferred by Rocketfuel 36

Take a closer look 37

Inaccuracy introduced during probing Lack of vantage points – How many points are sufficient? Incomplete traceroutes – What can we do if ISP turns off traceroute fun ctionality? Changes in the path of a probe Incorrect DNS record 38

Inaccuracy from processing probed links Alias Resolution Adding reverse links Missed and added links in Rocketfuel PoP topology relative to the number of links in the Sprintreal topology 39

Questions? 40