Subject: [GROW] proposals for draft-ietf-grow-mrt-03

From: Erik Romijn <[email-masked]>
Date: Mon, 15 Jan 2007 13:02:04 +0100

Hi all,

I'm working with Juergen Kammer to make Quagga's MRT dump code and
libbgpdump support 32bit ASNs. We have a few proposals for things that
appear to be missing in draft-ietf-grow-mrt-03.

We've encountered a few things in the library which are supposed to be
based on working group discussions, but are not included in the
(expired) draft.
However, the old archives are inaccessible and have not been merged with
the new ones. So, I might be repeating a bit of previous discussion here.

What we propose to be included in the draft:

- A new MRT routing information type: TABLE_DUMP_32BIT_AS.
  A current implementation in the library is to encode the 32bit AS flag
  into the address family field of the TABLE_DUMP, but this doesn't seem
  very nice.
  TABLE_DUMP_32BIT_AS would be the same as TABLE_DUMP, except with a
  32bit field for the Peer AS.

- A new BGP4MP type: BGP4MP_STATE_CHANGE_32BIT_AS.
  This would be the same as BGP4MP_STATE_CHANGE, except with a 32bit
  field for the source and destination AS number.

Any comments are welcome.

cheers,
-- 
Erik Romijn                 RIPE NCC jr. software engineer
http://www.ripe.net/        Information Services dept.
_______________________________________________
GROW mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/grow

---

From: "Larry J. Blunk" <[email-masked]>
Date: Mon, 15 Jan 2007 10:46:36 -0500

>   32bit field for the Peer AS.

       Eric,
          My assumption is that implementations would move to
using the BGP4MP_ENTRY type for table dumps as it was meant
to replace the TABLE_DUMP type.    The BGP4MP_ENTRY header
does not encode an AS number in the header and is transparent to
32-bit AS numbers.   I guess I could either create a new
TABLE_DUMP_32BIT_AS type or add text referring to  the
BGP4MP_ENTRY type for 32-bit AS support.

>   field for the source and destination AS number.

    Okay, I had thought that RFC4271 had changed the states in
the state machine and thus would result in the deprecation of the
BGP4MP_STATE_CHANGE type, but I see it has the same
6 states as part of it's FSM.   I can go ahead and add this type.

  -Larry

> ------------------------------------------------------------------------
>
> !DSPAM:45ab6d5c13361242917256!
>

---

From: "Larry J. Blunk" <[email-masked]>
Date: Mon, 15 Jan 2007 10:46:36 -0500

Eric,

  -Larry

---

From: Erik Romijn <[email-masked]>
Date: Tue, 16 Jan 2007 10:57:34 +0100

> BGP4MP_ENTRY type for 32-bit AS support.

I am in favour of TABLE_DUMP_32BIT_AS. I don't see any real advantage to
moving to BGP4MP_ENTRY and do see significant extra work to modify software.
Also, it wouldn't hurt to add TABLE_DUMP_32BIT_AS, would it?

regards,

---

From: Erik Romijn <[email-masked]>
Date: Tue, 16 Jan 2007 10:57:34 +0100

regards,

---

From: Simon Leinen <[email-masked]>
Date: Tue, 16 Jan 2007 15:04:37 +0100

> On Mon, Jan 15, 2007 at 10:46:36AM -0500, Larry J. Blunk wrote:
[...]

> I am in favour of TABLE_DUMP_32BIT_AS. I don't see any real
> advantage to moving to BGP4MP_ENTRY and do see significant extra
> work to modify software.

One advantage of BGP4MP_ENTRY is that it includes the SAFI value.
It is otherwise very similar to TABLE_DUMP, so I don't see how
the extra work would be that much more significant than the work to
implement the TABLE_DUMP_32BIT_AS that you propose.

> Also, it wouldn't hurt to add TABLE_DUMP_32BIT_AS, would it?

Well, not if you have it already, but if not it's more code...
-- 
Simon.

---

From: Simon Leinen <[email-masked]>
Date: Tue, 16 Jan 2007 15:04:37 +0100

[...]

---

From: Erik Romijn <[email-masked]>
Date: Tue, 16 Jan 2007 15:43:07 +0100

> implement the TABLE_DUMP_32BIT_AS that you propose.

One thing I'm missing here. Where is the peer's AS stored in a
BGP4MP_ENTRY? As a BGP attribute? Or is it not stored at all?
I don't see it being mentioned in the draft.

> Well, not if you have it already, but if not it's more code...

We don't have it yet, but for both quagga and libbgpdump
TABLE_DUMP_32BIT_AS would be a trivial 30-second change.
All of the code is already there, we just need to disable the address
family mangling and use TABLE_DUMP_32BIT_AS instead.

Code for BGP4MP_ENTRY in quagga is partial, in libbgpdump non-existing.

regards,

---

From: Erik Romijn <[email-masked]>
Date: Tue, 16 Jan 2007 15:43:07 +0100

regards,

---

From: "Larry J. Blunk" <[email-masked]>
Date: Wed, 17 Jan 2007 17:28:31 -0500

> I don't see it being mentioned in the draft.

Erik,
    The definition of the BGP4MP_ENTRY subtype was taken from
http://www.zebra.org/zebra/Packet-Binary-Dump-Format.html.    The
header does not contain the peer AS  --  although I guess it
be divined from the AS_PATH attribute.

   I did a bit of implementation review regarding the BGP4MP_ENTRY
and found the following:

1) Zebra/Quagga has an incomplete (only supports IPv4, no IPv6)
and inconsistent (does not include "View #" and "Status" fields)
implementation.  Further, it is hard-coded to always use the
TABLE_DUMP type.

2)  The Sprint Labs Python Routing Toolkit (PyRT) defines a new type
(BGP-4PY) which includes a subsecond timestamp field.  This type
is re-named BGP4MP_ET in the Internet Draft.   I had not noticed this
initially, but the BGP4MP_ENTRY definition is modified to include a
source and dest AS number and interface index when used with
the BGP4MP_ET type (which makes it more consistent with
the BGP4MP_STATE_CHANGE and BGP4MP_ENTRY subtypes).
However, PyRT does not actually implement support for the
BGP4MP_ENTRY.

3)  OpenBGPd implements support for BGP4MP_ENTRY, but
it is inconsistent with Zebra/Quagga documentation/implementation.
Namely, it includes source/dest AS, interface index, and source/dest
IP addresses.

   As an observation, I don't see a need for including non-IPv4 NLRI,
SAFI,  and Next-Hop in the BGP4MP_ENTRY header since that info is
already in the MP_REACH_NLRI attribute.

> Code for BGP4MP_ENTRY in quagga is partial, in libbgpdump non-existing.

    Given the inconsistent and confusing implementation
support for BGP4MP_ENTRY,  I'm tempted to mark it as
deprecated and define a new TABLE_DUMP type that includes
support for 16-bit or 32-bit AS numbers, and includes support
for NLRI other than IPv4 and IPv6.    The only question I
have is should it include the local (destination) IP adddress and
AS in addition to the peer's IP and AS numbers?

 -Larry

---

From: "Larry J. Blunk" <[email-masked]>
Date: Wed, 17 Jan 2007 17:28:31 -0500

Erik,

 -Larry

---

From: Erik Romijn <[email-masked]>
Date: Mon, 22 Jan 2007 16:21:12 +0100

On Wed, Jan 17, 2007 at 05:28:31PM -0500, Larry J. Blunk wrote:
> for NLRI other than IPv4 and IPv6.

So basically TABLE_DUMP with a 32-bit AS field and an NLRI field?

> The only question I

For RIS this is essential. When either we (for MySQL database insertion)
or someone else reads the dumps they will have to know where a route
actually came from. Ofcourse, there are messages somewhere in some dump
that contain this information, but that would make things very very
complex.

Peer AS can be read from the AS path in most cases, but what about route
servers that don't add their own AS?

cheers,

---

From: Erik Romijn <[email-masked]>
Date: Mon, 22 Jan 2007 16:21:12 +0100

cheers,

---

From: "Larry J. Blunk" <[email-masked]>
Date: Mon, 22 Jan 2007 15:12:55 -0500

> So basically TABLE_DUMP with a 32-bit AS field and an NLRI field?
    Yes, something like that.

> servers that don't add their own AS?

    Perhaps, I wasn't clear.  I was asking whether we need
to include the local (collector's) IP and AS number in addition
to the peer's IP and AS number.  This information is included
in the BGP4MP_ENTRY type.  I suspect this information is
not really needed and would simply bloat the dump files further.

     Below is a proposed TABLE_DUMP_NEW type.  The
View and Status fields have been dropped and the sequence
number field is expanded to 32-bits (as almost all dumps
contain more the 65,536 entries).  The MRT Subtype field would
use bitfields to indicate peer IP type (IPv4 or IPv6), peer AS
size (16 or 32 bit), and NLRI type (IPv4-Unicast or
multi-protcol).   If the NLRI type is IPv4-Unicast, the Prefix
Length and Prefix fields are included.  If the NLRI type
is multi-protocol, the Prefix Length and Prefix fields are
omitted and the NLRI information is contained in the
MP_REACH_NLRI attribute.

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                         Sequence number                       |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                         Originated Time                       |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                    Peer IP address (variable)                 |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                        Peer AS (variable)                     |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  | Prefix Length |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                        Prefix (variable)                      |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |      Attribute Length         |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                    BGP Attributes... (variable)
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

---

From: "Larry J. Blunk" <[email-masked]>
Date: Mon, 22 Jan 2007 15:12:55 -0500

0                   1                   2                   3

---

From: john heasley <[email-masked]>
Date: Tue, 23 Jan 2007 01:22:12 +0000

> not really needed and would simply bloat the dump files further.

Shouldnt the file be stand-alone?  not require previous knowledge of it's
source and yet be able to differentiate dumps of one source from another?

> size (16 or 32 bit), and NLRI type (IPv4-Unicast or

why bother with 2 byte ASNs?

---

From: john heasley <[email-masked]>
Date: Tue, 23 Jan 2007 01:22:12 +0000

---

From: Erik Romijn <[email-masked]>
Date: Tue, 23 Jan 2007 13:34:19 +0100

Hello Larry, John,

On Tue, Jan 23, 2007 at 01:22:12AM +0000, john heasley wrote:
> > I was asking whether we need

You have a point there. If one takes dump files from random sources, it
is not possible to determine where they came from.

On the other hand, it would add bloat...

> > View and Status fields have been dropped

What about a router with multiple bgp instances?
I think quagga can do this, don't know of any other bgpd.

Wasn't the views field intended to be able to make the distinction
between entries from the different bgp instances?

(this is also solved by adding Peer IP and AS)

> > [..] peer AS size (16 or 32 bit) [..]
> 

Indeed. Why not make Peer AS always 4 bytes?

And if we stick to this, how would a parser know the boundary between
peer AS and Prefix Length?

Except for this, it seems fine to me :-)

cheers,

---

From: Erik Romijn <[email-masked]>
Date: Tue, 23 Jan 2007 13:34:19 +0100

Hello Larry, John,

cheers,

---

From: "Larry J. Blunk" <[email-masked]>
Date: Tue, 23 Jan 2007 11:32:28 -0500

> On the other hand, it would add bloat...
     If the table dumps were done in a single atomic MRT record
(something I've thought about), I think this would be reasonable.
But given the current format of one MRT record per table entry,
it would add considerable bloat (particularly if the collector has
a 32-bit AS number and an IPv6 IP address).    The Routeviews
table dumps are already unwieldy enough as is, I'd really hate
to make them any worse.

    I don't think people are generally in the habit of pulling down
table dumps from random unknown sources.    And in the end,
the IP/AS of the collector is not terribly critical information.   It's
useful to know if a dump came from a Routeviews collector or the
RIS RRC01 collector, but I don't much care what IP/AS number
the Routeviews or RIS collector happened to be using.

   That said, we could perhaps define an initial header MRT
record for table dumps that includes the collector's IP and
AS number and perhaps an indexed array of peer IP/AS
numbers.  By using  a 16-bit array number for a peer
instead of the IP/AS number in each MRT dump record,
you could cut down on the size of the table dumps
considerably (particularly as peers move to IPv6 addresses
and 32-bit AS numbers).   This initial header record could
be generated and written to the beginning of each table
dump file.

> (this is also solved by adding Peer IP and AS)
        Yes, quagga supports views (bgp multiple-instance).  However,
they are named, not numbered, and quagga always hardcodes the
View field in MRT TABLE_DUMP's to be 0.    There are a couple
of ways to handle views.   Either through file-naming of the
generated dump file, or by having a field in an initial header
MRT record as suggested above.

       Don't understand the comment about Peer IP and AS as those
are already in the record.

> Indeed. Why not make Peer AS always 4 bytes?

  Again, bloat.   There's plenty of bits available in the subtype
code field, why not use them?   Lot's less CPU cycles/time
to do a simple bit test for field size than to transfer around
and decompress unneeded bits.

> peer AS and Prefix Length?

   Bits are defined in the subtype code to define both peer
IP address size and AS number size.   You know where the
Prefix Length field begins based on the size of the peer's
IP address and AS number.

 -Larry

---

From: "Larry J. Blunk" <[email-masked]>
Date: Tue, 23 Jan 2007 11:32:28 -0500

-Larry

---

From: john heasley <[email-masked]>
Date: Tue, 23 Jan 2007 18:04:25 +0000

> (this is also solved by adding Peer IP and AS)

That would also produces a file which is not autonmous; you can not
produce the FIB without knowing in which instance the peer was
configured.

---

From: john heasley <[email-masked]>
Date: Tue, 23 Jan 2007 18:04:25 +0000

---

From: Erik Romijn <[email-masked]>
Date: Wed, 24 Jan 2007 12:06:04 +0100

On Tue, Jan 23, 2007 at 11:32:28AM -0500, Larry J. Blunk wrote:
> the IP/AS of the collector is not terribly critical information.

I agree. Let's not bloat it more.

> AS number

That may be useful. But still, there is your good point that people will
not fetch random dumps and then try to find out where they came from.

> perhaps an indexed array of peer IP/AS numbers. 

Nice idea. But how much would we save?

Let's assume asn16/ipv4, so 48 bits of IP/AS per entry. With a bit more
than 200K routes that's 10Mbit of IP/AS.
With the index, assuming a 16-bit number and 200 peers, it would be 9600
bits of array and 3.2M of indexes. So that's 33% cut (on peer
information only).
We save about 0.85Mbyte here. A RIS RIB dump on the biggest machine is
240M uncompressed. So we would save 0.35%.

Assuming best-case, ipv6/asn32. Without array 30Mbit, so that's 0.7% save
based on RIS examples.

With an 8-bit index it's 0.7% for asn16/ipv4 and
1.4% for asn32/ipv6. However, the latter allows only 255 peers.

So the reduction in data is really small. Unless I miscalculated
ofcourse :-)

> >>> The View and Status fields have been dropped
> >>>      
> >

> are already in the record.

I mixed up. I was referring to the collector's own IP and AS, which
doesn't make any sense either. Forget that comment :-)

> and decompress unneeded bits.

I must have missed somewhere that asn16/asn32 would be encoded in the
subtype field.
And yes, if we store the bits (subtype) anyway, your idea is a lot more
efficient as we won't have much asn32* for the coming time.

> IP address and AS number.

Ofcourse. If it's encoded in the subtype, the answer to my question is
very obvious :-)

* Probably the correct term here should be "4-byte only AS", as AS2134
  can be used on an asn32 BGP implementation too, but would be stored as
  16-bit number.

cheers,

---

From: Erik Romijn <[email-masked]>
Date: Wed, 24 Jan 2007 12:06:04 +0100

cheers,

---

From: Erik Romijn <[email-masked]>
Date: Wed, 24 Jan 2007 12:17:36 +0100

[ Insert something with Murphy's law and the send command ]

On Wed, Jan 24, 2007 at 12:06:04PM +0100, Erik Romijn wrote:
> [..]

I'm mixing up again here. That RIS RIB dump is not 200K routes, that
would be a FIB dump. The RIB dump is approximately 30M entries. So
that's 1440Mbits of data on peer IP/AS without indexing (with
asn16/ipv4).

With indexing, it's 480Mbits. So we go from 180MB to 60MB.

So we save about 120MB of the 240MB. That's 50%. For asn16/ipv4.
If we get to asn32/ipv6, this will even be a lot more.

Note that this may not neccesarily decrease the size of the compressed
dump files. I can imagine that gzip/bzip already do something like this.

Short: yes, it seems to save significant data, unless I miscalculated
again :-)

cheers,

---

From: Erik Romijn <[email-masked]>
Date: Wed, 24 Jan 2007 12:17:36 +0100

cheers,

---

From: Erik Romijn <[email-masked]>
Date: Thu, 25 Jan 2007 09:37:18 +0100

On Wed, Jan 24, 2007 at 12:17:36PM +0100, Erik Romijn wrote:
> would be a FIB dump. The RIB dump is approximately 30M entries.

No it's not, it's 3M entries. Without indexing 18MB of peer info data,
with indexing 6MB.
Save of 12MB of 240, so 5% saving.

[Don't try to multiply numbers without a calculator right before lunch]

cheers,

---

From: Erik Romijn <[email-masked]>
Date: Thu, 25 Jan 2007 09:37:18 +0100

cheers,

---

From: Erik Romijn <[email-masked]>
Date: Wed, 31 Jan 2007 10:47:33 +0100

> [Don't try to multiply numbers without a calculator right before lunch]

To finalize, as I don't see any further comments (yet), I think we
should not use this indexed array of peer data.

Which, if I read all discussion correctly, brings us to the format as
initially suggested by Larry.

One last thing to clarify there: in which order are the bits in the
subtype, and what values mean what.
I assume Larry meant (and if not I propose):
0 - unset for IPv4, set for IPv6
1 - unset when AS field is 16 bits, set when it's 32 bits
2 - unset for IPv4 unicast, set for multi-protocol

(I explicitly avoided "asn32" or "4-byte only AS" here, as AS5 or AS100
may be stored in a 32bit field just as well.)

Also, I have one last comment: is it smart to call this type
TABLE_DUMP_NEW? What happens when we update it again? TABLE_DUMP_NEWER?
And then TABLE_DUMP_NEWER_THAN_THE_PREVIOUS_NEWER? :-)

cheers,

---

From: Erik Romijn <[email-masked]>
Date: Wed, 31 Jan 2007 10:47:33 +0100

cheers,