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


Initially, I tried to work out the number of singlehomed routers and
DFZ routers from the file "Lists of alias clusters" at:


   "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


   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

  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

  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

   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
       3     54
       4     56
       1     57
       2     58
       1     59
       1     61
       1     62
       1     64
       3     66
       1     67
       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:       s9-1-0-20-0.e0.dlls.broadwing.net       -       -       -        -      -

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