Subject: Re: [RRG] Routers in DFZ - reliable figures from iPlane

From: Robin Whittle <[email-masked]>
Date: Tue, 07 Aug 2007 21:40:05 +1000

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 [email-masked] 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

---

From: "Ricardo V. Oliveira" <[email-masked]>
Date: Tue, 7 Aug 2007 09:47:43 -0400

Robin,

iPlane is doing a great job going further in revealing the structure  
of the network. Said that, I think you probably need to rephrase some  
of the statements bellow.

>      Routers in Default Free Zone:  123k

1. What do you call DFZ routers are not DFZ, i.e. DFZ is not the same  
as multihomed, a stub can be multihomed and only use half of the  
routing table, the other half use default routing.
What you call singlehome may not be singlehome because of the limited  
visibility of iPlane.

2. These numbers are at most a lower bound on the numbers you are  
looking for, and we have no way to tell how tight this bound is.  
iPlane data is incomplete because of several reasons, such as limited  
number of vantage points, blocking of ICMP/UDP by routers, MPLS  
tunnels,.... Furthermore, there's the problem of converting router  
interfaces to AS numbers which is not entirely resolved, see these  
papers:
http://irl.cs.ucla.edu/topology/chang01inferring.ps
http://irl.cs.ucla.edu/topology/fwdPath.pdf
http://irl.cs.ucla.edu/topology/3rdparty.pdf

> number and capacity of interfaces etc. - and also their cost.
And getting realistic numbers for those is an unfeasible task as of  
now, at least for the entire Internet. My advice is to get accurate  
data for a tier-1 ISP directly and start from there.

> "transit routers" in the DFZ - all with two or more BGP peers.
Nope. A router can have multiple interfaces connecting to same provider.

--Ricardo

---

From: Robin Whittle <[email-masked]>
Date: Wed, 08 Aug 2007 00:13:55 +1000

Hi Ricardo,

Thanks for your response.  I asked Harsha to join the RRG list and
respond to you, since I don't know enough about this to answer your
critiques.

You wrote:

> a stub can be multihomed and only use half of the routing
> table, the other half use default routing.

"Multihomed" to me means it has two or more links to "the rest of
the Internet" meaning that it has to choose between these two or
more links for packets addressed to every prefix except those of the
local network(s) its other links lead to.

"Stub" to me means it has one link - so I don't see how a router
could be a stub and multihomed.

> What you call singlehome may not be singlehome because of the limited

Hartha would need to comment on whatever limits there are to the
reach of iPlane's research.

> looking for, and we have no way to tell how tight this bound is. iPlane
> data is incomplete because of several reasons, such as limited number of
> vantage points, blocking of ICMP/UDP by routers, MPLS tunnels,....

I can imagine there must be some limitations on what any research
project could achieve.

> Furthermore, there's the problem of converting router interfaces to AS
> numbers which is not entirely resolved, see these papers:

I can't comment on how iPlane tackles these problems.

> And getting realistic numbers for those is an unfeasible task as of now,
> at least for the entire Internet. My advice is to get accurate data for
> a tier-1 ISP directly and start from there.

How would knowing the number of routers for one large ISP help
determine the total number in the Net?

> Nope. A router can have multiple interfaces connecting to same provider.

Sure, but if they go to different routers, then the router needs to
do the full BGP operation and compare notes with these two or more
peers, decide on the best path for each of 220,000+ prefixes etc.
As far as I know, it doesn't matter which provider the router's
peers are in - but please correct any mistake I am making, since you
and most other people on this list know more about this than I do.

  - Robin

---

From: "Harsha V. Madhyastha" <[email-masked]>
Date: Tue, 7 Aug 2007 17:00:46 -0700

I concur with Ricardo on both of these statements.

1. These numbers are at most a lower bound on the numbers you are  
looking for, and we have no way to tell how tight this bound is.  
iPlane data is incomplete because of several reasons, such as limited  
number of vantage points, blocking of ICMP/UDP by routers, MPLS  
tunnels,.... Furthermore, there's the problem of converting router  
interfaces to AS numbers which is not entirely resolved.

2. And getting realistic numbers for those is an unfeasible task as  
of now, at least for the entire Internet.

iPlane data has its limitations. But, irrespective, computing exact  
figures for the numbers you are looking for is infeasible by  
performing measurements of the Internet.

I'm not sure if starting off with numbers from a tier-1 ISP serves  
your purpose in terms of being representative of the entire Internet.  
Maybe you are better off combining numbers from iPlane with that from  
other measurement projects such as Skitter and DIMES. Those numbers  
too won't be precise, but I think that's the best we can do as of now.

Cheers,
Harsha