CAIDA : ~amogh : rtr

High degree router analysis

The Internet Topology Data Kit (ITDK) consists of a router-level graph of the Internet obtained from Ark-based measurements. We find that the router-level graph has some routers with very large degrees (links to other routers), with . Our goal is to determine the cause of these high degree routers. We also study "link clouds" -- structures that have more than one router on a single link.

Router stats

midar-iffinder-kapar dataset: 32,604,620 routers total.
midar-iffinder dataset: 33,303,031 routers total.

We classify routers into the following types:
1) The router has some identified interfaces ("I' router).
2) The router does not have any identified interfaces ("U" router).

midar-iffinder-kapar dataset: 9,078,230 (28%) of routers have 0 identified interfaces.
midar-iffinder dataset: 9,380,103 (28.2%) of routers have 0 identified interfaces.

For a high degree router r, we split its degree into the following components:
1) Number of links from r to I routers due to r's presence in link clouds.
2) Number of links from r to U routers due to r's presence in link clouds.
2) Number of links from r to I routers due to point-to-point links.
3) Number of links from r to U routers due to point-to-point links.

For each router, we then find the maximum degree component, i.e., the component of its degree (from the 4 listed above) that contributes the most to that router's total degree.

dataset	degree greater than	total	cloud-I	%	cloud-U	%	point_I	%	point-U	%
midar-iffinder-kapar	10000	141	60	42	6	4.2	20	14	55	39
midar-iffinder	10000	178	116	65.1	3	1.6	17	9.5	42	23.5
midar-iffinder-kapar	5000	386	128	33	17	4	87	22	154	40
midar-iffinder	5000	423	196	46.3	21	4.9	69	16.3	137	32.3
midar-iffinder-kapar	1000	2536	459	13	225	6.3	1852	52	1007	28
midar-iffinder	1000	3976	1013	25.4	240	6.0	1674	42.1	1049	26.3

In all three cases, a significant fraction of the links for high degree routers are due to point-point links to routers that have no identified interfaces. A significant fraction of the high degree router links are due to clouds.

midar-iffinder-kapar	midar-iffinder

For each high degree router, we then determine the contribution of the max-degree component towards the total degree. In particular, we find that when the max degree component for a router is "deg point-U" (meaning that the max number of links of this router are point to point links that connect it with routers that have no identified interface), the correlation with line y=x is strong. This indicates that for such routers, most of their high degree is accounted for by the "deg-point-U" component.

For each high degree router, we determine the set of identified interfaces on that router, and find the AS that is found most frequently on that router. We then count the most frequently appearing AS for routers with degree greater than 10000, 5000 and 1000. We repeat this analysis using both the midar-iffinder-kapar and midar-iffinder datasets.

Degree > 10000

Degree > 5000

Degree > 1000

In each of the cases, we find some ASes that appear frequently in the set of interfaces of high degree routers. In particular, Global Crossing (3549) and ATT (7132) appear in this list, and are known to have an MPLS network. In the trace analysis, we study some examples of high degree router that belong to these ASes, and show that they produce signatures in the traces that are typical of MPLS networks.

Link stats

dataset	total links	invalid (<2 routers)	%	point-point (2 routers)	%	cloud (>2 routers)	%	U-U links	%
midar-iffinder-kapar	32970780	62643	0.1	32036696	97.1	871441	2.6	3521447	10.6
midar-iffinder	33448073	64265	0.1	32568006	97.3	815802	2.4	3627330	10.8

Trace analysis

We look at examples of high degree routers from the midar-iffinder-kapar datasets whose degrees are dominated by each of the 4 degree components mentioned above. We then isolate the traces in which these routers appear and look for possible reasons why these routers became high degree routers. We process the raw traces to the following format for each hop:
ip_address:router:AS:[H], where the "H" indicates that this hop belonged to a high degree router

Example 1: Router N28276, max degree component cloud-I (51,326 out of 65,463 links, max. number of interfaces from address space of AS3549)

We find router N28276 in traces of the form:
192.107.171.130:N5200125:681 192.107.171.142:N3383168:681 192.107.171.49:N26950:681 130.217.2.6:N69162:681 203.167.234.85:N98310:4768 218.101.61.193:N242019:4768 203.98.50.1:N260157:9901 203.98.50.251:N30081:9901 203.167.233.10:N780:4768 202.84.142.129:N256215:4637 202.84.251.238:N244216:4637 134.159.62.134:N28276:4637:H 67.17.110.2:N254810:3549:H 64.211.192.74:N423:3549 203.117.34.2:N423:38861 203.117.35.42:N5606672:38861 0.0.0.0:-1:-1 0.0.0.0:-1:-1 0.0.0.0:-1:-1 0.0.0.0:-1:-1 0.0.0.0:-1:-1

The sequence of hops
134.159.62.134:N28276:4637:H 67.17.110.2:N254810:3549:H 64.211.192.74:N423:3549
fits the signature of an MPLS network. The trace has only 2 hops on 3549's address space, and the routers containing the first and second hops appear as high degree routers. AS3549 (Global Crossing) advertises an MPLS network.

We use this observation to determine a signature for high-degree routers that are created due to MPLS. Let A(R) be the AS that accounts for the majority of interfaces on a router R. We then look at traces in which the router R appears, and count the total number of hops in A(R)'s address space. The conjecture is that if a high-degree router is due to MPLS, then it should have just 2 or 3 hops in A(R)'s address space. We use the threshold of 3 hops in A's address space as the signature of a high-degree router due to MPLS.

The following table shows, for each router which had a maximum degree component of cloud-I, the fraction of traces that matched the MPLS signature defined above.

Router	Fraction of traces
N685	0.563194
N724	0.794542
N279573	0.823812
N273305	0.840812
N293780	0.881266
N21583	0.883481
N121505	0.887631
N16220	0.900281
N16947	0.901151
N251632	0.907891
N22638	0.912951
N28276	0.918381
N279244	0.96214
N243740	0.97621
N154072	0.98064
N9364	0.98359
N254810	0.9845
N338411	0.99022
N298809	0.99963

Example 2: Router N175098, max degree component point-I (32,551 out of 32,718 links)

205.189.33.78:N5682499:6327_6509 205.189.33.1:N242038:6327_6509 205.189.32.226:N12198:6509 62.40.124.221:N45115:20965:H 62.40.112.138:N5362:20965 62.40.125.126:N5723:20965 193.1.236.2:N75348:1213 193.1.196.225:N175098:1213:H 87.46.227.207:N19069783:1213
205.189.33.78:N5682499:6327_6509 205.189.33.1:N242038:6327_6509 205.189.32.226:N12198:6509 62.40.124.221:N45115:20965:H 62.40.112.138:N5362:20965 62.40.125.126:N5723:20965 193.1.236.2:N75348:1213 193.1.196.225:N175098:1213:H 87.47.37.189:N19071887:1213
205.189.33.78:N5682499:6327_6509 205.189.33.1:N242038:6327_6509 205.189.32.226:N12198:6509 62.40.124.221:N45115:20965:H 62.40.112.138:N5362:20965 62.40.125.126:N5723:20965 193.1.236.2:N75348:1213 193.1.196.225:N175098:1213:H 87.47.31.136:N19071701:1213
205.189.33.78:N5682499:6327_6509 205.189.33.1:N242038:6327_6509 205.189.32.226:N12198:6509 62.40.124.221:N45115:20965:H 62.40.112.138:N5362:20965 62.40.125.126:N5723:20965 193.1.236.2:N75348:1213 193.1.196.225:N175098:1213:H 87.46.21.2:N19063210:1213
205.189.33.78:N5682499:6327_6509 205.189.33.1:N242038:6327_6509 205.189.32.226:N12198:6509 62.40.124.221:N45115:20965:H 62.40.112.138:N5362:20965 62.40.125.126:N5723:20965 193.1.236.2:N75348:1213 193.1.196.225:N175098:1213:H 87.46.5.92:N19062718:1213
205.189.33.78:N5682499:6327_6509 205.189.33.1:N242038:6327_6509 205.189.32.226:N12198:6509 62.40.124.221:N45115:20965:H 62.40.112.138:N5362:20965 62.40.125.126:N5723:20965 193.1.236.2:N75348:1213 193.1.196.225:N175098:1213:H 87.45.205.16:N19060945:1213
205.189.33.78:N5682499:6327_6509 205.189.33.1:N242038:6327_6509 205.189.32.226:N12198:6509 62.40.124.221:N45115:20965:H 62.40.112.138:N5362:20965 62.40.125.126:N5723:20965 193.1.236.2:N75348:1213 193.1.196.225:N175098:1213:H 87.44.50.58:N19047926:1213
205.189.33.78:N5682499:6327_6509 205.189.33.1:N242038:6327_6509 205.189.32.226:N12198:6509 62.40.124.221:N45115:20965:H 62.40.112.138:N5362:20965 62.40.125.126:N5723:20965 193.1.236.2:N75348:1213 193.1.196.225:N175098:1213:H 87.47.245.34:N19078489:1213

Each next hop router N19069783, N190719887, N19071701, N19063210, N19062718, N19060945, N19047926, N19078489 has a single interface assigned to it.

This particular high-degree router is the artifact of a honeypot in AS1213 (HEAnet). We use this observation to find a signature that may be characteristic of high-degree routers caused by honeypots or similar. The high-degree router appears as the last-but-one hop on each trace. For each high-degree router with a dominant degree component due to point-I links, we find the position of the high-degree router in each trace in which it appears. We count the fraction of traces for which the high degree router appears as the last-but-one hop in a trace. The table below shows, for each high degree router with a dominant point-I degree, the fraction of traces in which it appears as the last-but-one hop.

Router	Fraction of traces
N175098	0.235137
N292451	0.647666
N101126	0.690408
N128996	0.712701
N26944	0.779531
N213601	0.903907
N179161	0.947087
N4105386	0.969935
N120989	0.977021
N31553	0.987236
N164175	0.998159
N134403	0.998165
N75497	0.998422
N184628	0.99848
N188124	0.998881
N206848	0.998993
N184680	0.999194
N184627	0.999394
N4205050	1
N5324130	1

Example 3: Router N293383, max degree component cloud-U (10,940 out of 14,359 links)

Legitimate traces through 213.248.89.86:N293383 such as the following trace will show a few identified next hop interfaces. This will lead to a small number of legitimate router links from N293383. One such trace is shown below

84.88.81.122:N322:13041 84.88.81.121:N2113197:13041 84.88.19.149:N14043:13041 130.206.202.29:N26946:766 130.206.250.25:N11906:766 130.206.250.2:N98306:766 213.248.81.25:N245837:1299 80.91.248.128:N101773:1299 80.91.249.44:N101724:1299 80.91.251.214:N8514:1299 213.248.89.86:N293383:1299:H 213.25.5.206:N56520:5617 83.1.81.166:N105506:5617 0.0.0.0:-1:-1 0.0.0.0:-1:-1 0.0.0.0:-1:-1 0.0.0.0:-1:-1 0.0.0.0:-1:-1

In some cases, however, the high degree router is followed by non-responsive hops. If the non-responsive hops appear at the end of the trace, then they do not lead to spurious links from the router, as all trailing non-responsive hops are removed in the trace pre-processing. One such trace is shown below.

150.183.95.135:N4233263:1237 150.183.95.1:N69664:1237 134.75.20.7:N69663:1237 211.168.150.93:N243049:3786 203.233.53.145:N98475:3786 203.255.234.106:N947:3786 203.255.234.38:N2113:3786 12.116.52.13:N254616:7018 12.122.137.210:N99169:7018 12.122.3.122:N245575:7018 12.122.128.105:N99151:7018 193.251.250.81:N148752:-1 193.251.132.58:N98881:5511 193.251.131.185:N28506:5511 193.251.243.118:N244235:-1:H 193.251.250.162:N293383:-1:H 0.0.0.0:-1:-1 0.0.0.0:-1:-1 0.0.0.0:-1:-1 0.0.0.0:-1:-1 0.0.0.0:-1:-1

192.107.171.130:N5200125:681 192.107.171.142:N3383168:681 192.107.171.49:N26950:681 130.217.2.6:N69162:681 203.167.234.85:N98310:4768 218.101.61.193:N242019:4768 203.98.50.1:N260157:9901 203.98.50.251:N30081:9901 203.167.233.10:N780:4768 202.84.142.94:N256215:4637 202.84.143.62:N4601:4637 202.84.251.101:N261431:4637 134.159.62.130:N242118:4637 193.251.241.14:N8:-1:H 193.251.240.101:N8:5511:H 193.251.131.133:N244235:5511:H 193.251.250.162:N293383:-1:H 0.0.0.0:-1:-1 213.25.5.222:N89755:5617 83.12.1.169:N17738675:5617 0.0.0.0:-1:-1 0.0.0.0:-1:-1 0.0.0.0:-1:-1 0.0.0.0:-1:-1 0.0.0.0:-1:-1

N293383:193.251.250.162 is followed by non-responsive hops. Each instance where N293383 is followed by a non-responding hop can produce a cloud-U link. The number of such links depends on the number of responding hops that follow the non-responding hop. If there is a single non-responding hop, then the number of cloud-I links could be as large as the product of the out-degree of the high-degree router and the out-degree of the non-responding hop(s).
What happens with multiple non-responding hops between the high-degree router and the first responding hop?

Example 4: Router N336682, max degree component point-U (76,681 out of 86,706 links)

129.186.1.240:N4120309:2698 129.186.6.251:N105724:2698 129.186.254.131:N5206498:2698 192.245.179.52:N3569:2698 4.53.34.13:N10317:3356 4.69.135.233:N249491:3356 4.69.135.230:N242106:3356 4.69.145.204:N50310:3356 192.205.35.141:N338411:7018:H 12.122.139.22:N34540:7018 12.122.100.5:N245642:7018 12.90.228.10:N336682:7018:H 0.0.0.0:-1:-1 201.134.131.209:N29689443:8151 0.0.0.0:-1:-1 0.0.0.0:-1:-1 0.0.0.0:-1:-1 0.0.0.0:-1:-1 0.0.0.0:-1:-1

The router after N336682 does not respond. These links from N336682 to the routers containing the unresponsive hop are determined as being point-to-point links.

For high-degree routers where the degree is dominated by point-U or cloud-U links, we have the following signature. The high degree router is separated from responding hops by one (or more) non-responding hops. For each high-degree router with maximum degree component point-U or cloud-U, we count the number of traces which show this pattern. The table below shows that for several routers, only a small fraction of traces follow this pattern. Need to investigate these cases

Router	Fraction of traces
N338740	0.0149591
N258356	0.0172972
N257614	0.0176257
N250620	0.0294364
N45115	0.0709572
N255869	0.0812647
N101032	0.0898571
N336517	0.115847
N3189	0.118138
N24708	0.122139
N12530	0.128097
N105372	0.136015
N244235	0.144494
N269202	0.160935
N298377	0.162571
N249163	0.179696
N15932	0.219674
N336683	0.223188
N8	0.225857
N26870	0.232801
N284276	0.233387
N28224	0.242425
N1866767	0.249275
N1866766	0.25121
N31548	0.255057
N20522	0.270435
N336682	0.273291
N20520	0.286663
N5904822	0.296634
N368	0.300834
N103497	0.311099
N26869	0.312277
N6996	0.333713
N525	0.350359
N8689	0.354847
N69000	0.371237
N31624	0.404798
N107463	0.406213
N524	0.440116
N69003	0.443866
N97861	0.455611
N59742	0.559243
N186795	0.569182
N26865	0.569941
N1467781	0.588025
N77437	0.652435
N105371	0.661594
N55054	0.695684
N102092	0.717331
N69005	0.718694
N77439	0.739473
N267	0.802864
N1534	0.943745
N244234	0.963488
N1321	0.964721

Link cloud analysis

Next, we look in the traces and identify link clouds, try to infer why that link cloud was created.

Link L100251: N242631:149.6.80.181 N27096926:149.6.80.182 N242194

We study the particular link cloud between routers N242631, N27096926, and N242194. The algorithm inferred that interfaces 149.6.80.181 (on router N242631) and 149.6.80.182 (on router N27096926) were part of the link cloud.

Almost every trace through N242631 has either N242631 before N242194, or in the reverse direction with N242194 before N242631. The interfaces 149.6.80.181 and 149.6.80.182 that are part of the link cloud do not appear in such traces. Examples of these traces:

snip..130.117.2.57:N242633:174: 130.117.0.78:N242650:174: 130.117.50.17:N242194:174 130.117.1.74:N242631:174: 149.6.3.6:N71531:174...snip

snip..80.91.249.135:N23464:1299: 80.91.249.130:N90770:1299: 213.248.70.238:N242631:1299 130.117.3.226:N242194:174: 130.117.2.165:N243486:174...snip

Legitimate traces in which the interfaces 149.6.80.181 and 149.6.80.182 are seen are of the form:
snip...154.54.29.158:N248425:174: 154.54.25.142:N242525:174: 130.117.0.45:N242194:174 149.6.80.181:N242631:174
snip...146.97.35.182:N90770:786: 195.66.224.185:N242194:5459 130.117.1.74:N242631:174 149.6.80.182:N27096926:174...
(these traces look truncated, and may have ended before the loop. see loop traces below).

Due to their IP addresses, the algorithm infers 149.6.80.181 and 149.6.80.182 as two endpoints of a link between routers 242631 and 27096926. Also, as router 242194 is at the other end of a link with 242631:149.6.80.181, this structure is inferred as a link cloud.

However, we find frequent instances of loops involving these routers, for example traces of the form:
snip.. 130.117.1.74:N242631:174 149.6.80.182:N27096926:174 149.6.80.181:N242631:174 149.6.80.182:N27096926:174 ..snip

The loop traces are the only instances where 149.6.80.181 and 149.6.80.182 appear in the same trace. These interfaces are seen as successive hops in this trace.
Are loop traces removed completely? Or are the non-loop portions retained?