Skip to Content
[CAIDA - Cooperative Association for Internet Data Analysis logo]
The Cooperative Association for Internet Data Analysis > ~amogh : rtr_graph : high_deg.xml
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-kapar10000 141 60 42 6 4.2 20 14 55 39
midar-iffinder10000 178 116 65.1 3 1.6 17 9.5 42 23.5
midar-iffinder-kapar5000 386 128 33 17 4 87 22 154 40
midar-iffinder5000 423 196 46.3 21 4.9 69 16.3 137 32.3
midar-iffinder-kapar1000 2536 459 13 225 6.3 1852 52 1007 28
midar-iffinder1000 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
My Image My Image

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:

The sequence of hops
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)

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 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

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.

N293383: 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)

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: N27096926: N242194

We study the particular link cloud between routers N242631, N27096926, and N242194. The algorithm inferred that interfaces (on router N242631) and (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 and that are part of the link cloud do not appear in such traces. Examples of these traces:



Legitimate traces in which the interfaces and are seen are of the form:
(these traces look truncated, and may have ended before the loop. see loop traces below).

Due to their IP addresses, the algorithm infers and 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:, 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.. ..snip

The loop traces are the only instances where and 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?

  Last Modified: Wed Jun-2-2010 15:43:1 PDT
  Page URL: