[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [RRG] Routers in DFZ - reliable figures from iPlane
Here is reliable information - the only information I can find - on
the number of BGP routers, and how many of them are in the DFZ. I
will mention this on RAM, IDR and IETF lists.
Short version, according to advice from the iPlane project:
Singlehomed routers: 87k
Routers in Default Free Zone: 123k
Total BGP routers: 210k
Long version:
We are currently considering a major, kludgey, mapping and tunneling
overlay architecture to add to the Internet, in addition to moderate
and generally improvements to the BGP protocol itself. Before
anyone could do a cost-benefit analysis of this, they would need an
estimate of how many DFZ routers are afflicted by the problems which
prompted us to propose such a drastic solution. They would need to
roughly characterise those routers in terms of their model number,
number and capacity of interfaces etc. - and also their cost.
The information below might be the starting point for such a project.
I have been corresponding with Harsha V. Madhyastha of iPlane:
http://iplane.cs.washington.edu
Initially, I tried to work out the number of singlehomed routers and
DFZ routers from the file "Lists of alias clusters" at:
http://iplane.cs.washington.edu/data.html
http://iplane.cs.washington.edu/data/alias_lists.txt
"Each line in this file contains a space-separated list of
interfaces that correspond to a single router.
This file is updated every two months. It is the result of several
algorithms which are described in section "2.2 Clustering of
Interfaces":
http://iplane.cs.washington.edu/osdi06.pdf
iPlane: An Information Plane for Distributed Services.
Harsha V. Madhyastha, Tomas Isdal, Michael Piatek, Colin Dixon,
Thomas Anderson, Arvind Krishnamurthy and Arun Venkataramani.
OSDI 2006, November 2006.
According to my understanding of this file, each line represents a
BGP router in the reasonably complete set of traceroutes the iPlane
project works from. Each line contains an IP address for each of
its interfaces. So I thought it would be easy to count these, to
find how many had a single IP address - those would be single-homed
routers and the rest would be "multihomed border routers" and
"transit routers" in the DFZ - all with two or more BGP peers.
The version on the site now, and on July 30 has 58,834 lines. The
one I got on July 12 had 62,698. Only 566 lines of the later file
had a single IP address, so either this data is incomplete, or more
likely my interpretation of it is wrong. My analysis of the file is
below my signature, but how valid it is, I am not sure. Probably
the 566 single IP address lines are anomalous, since maybe it should
really only have lines with two or more IP addresses.
In the abovementioned PDF file, the authors give an analysis of the
clustering:
This clustering algorithm, when executed on a typical traceroute
output, clusters 762,701 interfaces into 54,530 clusters.
653,455 interfaces are in 10,713 clusters of size greater than
10, while 21,217 interfaces are in singleton clusters.
I couldn't reconcile that with the July 30 version of
alias_lists.txt, so I wrote to Harsha. He responded with some new
analysis, because the number of DFZ routers couldn't be inferred
from the existing data.
He wrote:
I dug through our topology measurements from yesterday. I observe
210k unique routers, of which 93K are within an AS, 64s are border
routers that are single-homed, and 53k are multi-homed border
routers.
Feel free to share this data.
Here is an edited version of our correspondence, correcting for some
numeric errors I made:
RW: I understand that you find 210k BGP routers in total and that
64k appear to have a single link to a BGP router in another AS,
and are therefore border routers which are singlehomed.
53k have two or more links to routers in one or more other ASes
- so all these can be considered as multihomed border routers.
HM: Your interpretation of these numbers is precisely right.
RW: The remainder - 93k - have links only to BGP routers in the
same AS. Some of those might have a single link, but I guess
most (or perhaps all?) would have two or more links to other
routers. This makes most (or perhaps all?) of them DFZ routers
as well, probably best regarded as "transit" routers.
HM: I dug into this a bit more. Turns out the split among the 93k is
that 23k have a single link, and the remaining 70k have two or
more links.
RW: I would have thought that your "Lists of alias clusters" should
reflect these figures, but there are only 58,834 lines in the
current copy. If I understand the format of this file
correctly, lines with a single IP address refer to routers with
a single BGP link, and therefore a single BPG peer. The rest
are multihomed. In that case, I would expect the file to have
about 210k lines, with 64k or somewhat more (singlehomed BGP
routers with their peer being in the same AS) having a single IP
address, and the rest with two or more IP addresses.
I didn't get a response to this directly, but he also wrote:
HM: We see around 250k router interfaces in the traceroutes we issue
daily. We gathered such interfaces over several months, and
amassed a list of around 1.5M interfaces. We then probed all of
these interfaces with UDP packets to determine which pairs of
interfaces could possibly be aliases, i.e., interfaces on the
same router. The alias_lists.txt file only has entries for
those router interfaces that we suspected could have aliases.
Each line in this file corresponds to one router; all the
interfaces on a line belong to the same router.
I looked at the interfaces we saw in yesterday's traceroutes,
mapped them to routers using the alias_lists.txt file, and
then mapped each router to its AS by considering the majority of
the ASes that the interfaces on the router map to. Then, for
each router, I counted the number of ASes that its neighboring
routers map to.
I don't yet fully understand this, but it seems we can conclude:
BGP routers in total: 210k
1 peer in another AS: 64k
2 or more peers, of which at
least one is in another AS: 53k <- Multihomed border
routers
All peers { Single link: 23k
in the {
same AS {
(93k): { 2 or more links: 70k <- Transit routers
Singlehomed routers: 87k
Routers in Default Free Zone: 123k
- Robin http://www.firstpr.com.au/ip/ivip/
http://iplane.cs.washington.edu/data/alias_lists.txt 2007-07-30:
58,834 lines
566 with 1 address
22,211 2 addresses
12,793 3
7,267 4
4,462 5
2,703 6
1,836 7
1,344 8
1,048 9
-------------
842 10 Total of 4,568 with 10 or more addresses.
622 11
The full analysis is below. I did this manually with a text editor,
deleting digits and sorting the remaining lines which contained dots
and spaces. "... ..." = two IP addresses.
58,834 lines
566 with 1 address
22,211 2 addresses
12,793 3
7,267 4
4,462 5
2,703 6
1,836 7
1,344 8
1,048 9
842 10
622 11
486 12
384 13
351 14
299 15
239 16
197 17
169 18
140 19
112 20
103 21
92 22
76 23
57 24
42 25
43 26
36 27
28 28
24 29
30 30
22 31
25 32
16 33
22 34
13 35
17 36
8 37
10 38
6 39
9 40
5 41
9 42
11 43
9 44
6 45
5 46
5 47
3 48
3 49
3 50
1 51
3 52
53
3 54
55
4 56
1 57
2 58
1 59
60
1 61
1 62
63
1 64
65
3 66
1 67
68
1 69
1 73
1 74
3 79
1 82
1 83
1 85
2 91
1 93
1 96
1 112
1 125
The last one is line 998, apparently a router in broadwing.net,
now part of Level 3. If someone is looking for the world's biggest
router, this might be a place to start!
The IP addresses on that line, sorted are:
65.88.15.161 s9-1-0-20-0.e0.dlls.broadwing.net
65.88.15.173 -
65.88.15.181 -
65.88.15.185 -
65.88.15.41 -
65.89.102.169 -
65.89.102.181
65.89.185.1
65.89.185.157
65.89.185.253
65.89.99.149
65.90.12.101
65.90.12.113
65.90.12.229
65.90.12.253
65.90.12.49
65.90.12.61
65.91.164.45
65.91.20.1
65.91.20.121
65.91.20.17
65.91.20.205
65.91.20.21
65.91.20.229
65.91.20.29
65.91.20.33
65.91.216.1
65.91.68.141
67.96.55.1
67.96.55.105
67.96.55.141
67.96.55.153
67.96.55.161
67.96.55.165
67.96.55.169
67.96.55.173
67.96.55.233
67.96.55.45
67.96.55.53
67.97.105.1
67.97.105.153
67.97.105.209
67.97.105.213
67.97.105.37
67.97.105.41
67.97.144.173
67.97.233.121
67.97.233.125
67.97.233.161
67.97.233.29
67.97.233.33
67.97.233.37
67.97.233.45
67.97.233.81
67.98.168.245
67.98.170.105
67.98.170.129
67.98.170.145
67.98.170.225
67.98.170.237
67.98.170.249
67.98.171.1
67.98.171.105
67.98.171.149
67.98.171.153
67.98.171.157
67.98.171.161
67.98.171.165
67.98.171.169
67.98.171.173
67.98.171.177
67.98.171.181
67.98.171.185
67.98.171.189
67.98.171.193
67.98.171.197
67.98.171.201
67.98.171.205
67.98.171.209
67.98.171.213
67.98.171.217
67.98.171.221
67.98.171.225
67.98.171.229
67.98.171.233
67.98.171.237
67.98.171.253
67.98.171.33
67.98.171.65
67.98.171.69
67.98.171.73
67.98.171.77
67.98.171.85
67.99.43.169
67.99.43.173
67.99.43.73
67.99.43.89
67.99.43.93
67.99.45.213
67.99.45.57
67.98.171.109
216.140.243.225
216.140.4.234
216.140.4.238
216.140.48.121
216.140.48.145
216.140.48.205
216.140.48.73
216.140.49.69
216.141.184.13
216.141.184.17
216.141.184.209
216.141.184.81
216.141.185.105
216.141.185.197
216.141.185.49
216.141.185.77
216.142.90.141
216.142.90.209
216.143.248.101
216.143.248.13
216.143.248.137
216.143.248.145
216.143.248.161
216.143.248.9
--
to unsubscribe send a message to rrg-request@psg.com with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg