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

From: "Erik Romijn" <[email-masked]>
Date: Fri, 9 Feb 2007 11:34:03 +0100

Hi all,

seeing that there appear to be no further comments, and that I want RIS
to support 4-byte ASes in the short future, the following will be
implemented as MRT format for the RIS raw data dumps.

(I copied some parts of previous posts, to make sure it is completely
clear what I'm referring to, after all these (useful!) ideas.)

- A new BGP4MP subtype: BGP4MP_STATE_CHANGE_32BIT_AS, assigned subtype 5
  Exactly the same as BGP4MP_STATE_CHANGE, except for a 32bit AS number,
  instead of 16.

- A new MRT routing information type: TABLE_DUMP_V2, assigned MRT type
  13.

TABLE_DUMP_V2 will be implemented as:

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

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.

The subtype field for a TABLE_DUMP_V2 will use the following bitfields:
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

(So IPv6/asn16/unicast would make the subtype value 1, ipv6/asn32 would
be 3.)

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: "Erik Romijn" <[email-masked]>
Date: Fri, 9 Feb 2007 11:34:03 +0100

Hi all,

  0                   1                   2                   3

cheers,

---

From: "Erik Romijn" <[email-masked]>
Date: Fri, 9 Feb 2007 15:19:24 +0100

> - A new BGP4MP subtype: BGP4MP_STATE_CHANGE_32BIT_AS, assigned subtype 5

One trivial change here, suggested by Juergen due to changes in the BGP
4-byte AS draft: the type would better be named BGP4MP_STATE_CHANGE_AS4.

Therefore I also suggest we rename BGP4MP_MESSAGE_32BIT_AS to
BGP4MP_MESSAGE_AS4.

However, this is not that significant as the MRT dump format itsself
will remain the same.

cheers,

---

From: "Erik Romijn" <[email-masked]>
Date: Fri, 9 Feb 2007 15:19:24 +0100

cheers,

---

From: Geoff Huston <[email-masked]>
Date: Sat, 10 Feb 2007 05:37:39 +1100

>However, this is not that significant as the MRT dump format itsself

Pulling the name space into a consistent state with "AS4" makes sense to me

    Geoff

---

From: Geoff Huston <[email-masked]>
Date: Sat, 10 Feb 2007 05:37:39 +1100

Geoff

---

From: "Larry J. Blunk" <[email-masked]>
Date: Fri, 09 Feb 2007 14:39:09 -0500

Erik Romijn wrote:
> On Wed, Jan 24, 2007 at 12:17:36PM +0100, Erik Romijn wrote:
>   
>> On Wed, Jan 24, 2007 at 12:06:04PM +0100, Erik Romijn wrote:
>>     
>>> On Tue, Jan 23, 2007 at 11:32:28AM -0500, Larry J. Blunk wrote:
>>>       
>>>> perhaps an indexed array of peer IP/AS numbers. 
>>>>         
>>> Nice idea. But how much would we save?
>>> [..]
>>> We save about 0.85Mbyte here. A RIS RIB dump on the biggest machine is
>>> 240M uncompressed. So we would save 0.35%.
>>>       
>> 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.
>>     
>
> 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]
>
>   

   Erik,
      I did some calculations with a Routeviews table dump which had
about 9.15M RIB entries and consumed 648MB uncompressed.  By using
an index table and an MRT record per NLRI (instead of an MRT record
per RIB entry), I calculated a savings of around 36% to 415MB.  I'll
post my proposed format in a bit.   I agree that 5% savings is nothing
to get excited about, but 36% seems like it would be worth the effort.
Note that these numbers are for IPv4 peers with 16-bit AS'es.   The savings
where peers have an IPv6 address or 32-bit AS would be higher.

  -Larry

---

From: "Larry J. Blunk" <[email-masked]>
Date: Fri, 09 Feb 2007 14:39:09 -0500

Erik,

  -Larry

---

From: Larry Blunk <[email-masked]>
Date: Sat, 10 Feb 2007 02:06:01 -0500

Here's my proposed format for the TABLE_DUMP_V2 type for comment.

  The following defines a new MRT routing information type called
TABLE_DUMP_V2, which is assigned MRT type 13. 

  The TABLE_DUMP_V2 type updates the TABLE_DUMP type to include 32-bit
ASN support and full support for BGP Multiprotocol extensions.  It also
improves upon the space efficiency of the TABLE_DUMP type by employing
an index table for peers and using a single MRT record per NLRI entry.
The following subtypes are used with the TABLE_DUMP_V2 type.

   1  INDEX_TABLE
   2  IPV4_UNICAST
   3  MULTIPROTOCOL

  An initial INDEX_TABLE MRT record provides a list of indexed peers.
Following the INDEX_TABLE MRT record, a series of IPV4_UNICAST
or MULTI_PROTOCOL records encode the RIB table entries.  The
INDEX_TABLE Subtype is shown below.  The Peer Type field is a bit field
which encodes the type of the AS and IP address as follows:

   Bit 0 - unset for IPv4 Peer IP address, set of IPv6
   Bit 1 - unset when Peer AS field is 16 bits, set when it's 32 bits

 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
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |           Peer Count          | 
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |   Peer Type   |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                   Peer IP address (variable)                  |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                        Peer AS (variable)                     |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 | repeated Peer Type, Peer IP address, and Peer AS fields
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

  The Peer Type, Peer IP, and Peer AS fields are repeated as indicated
by the Peer Count field.  The position of the Peer in the INDEX_TABLE
is used as an index in the IPV4_UNICAST and MULTIPROTCOL
MRT records.  The index number begins with 0.

  The IPV4_UNICAST and MULTIPROTOCOL subtypes include a header
which specify a sequence number, NLRI, and a count of the number of RIB
entries which follow.  The IPV4_UNICAST_NLRI and MULTIPROTOCOL_NLRI have
unique headers followed by a common RIB entry format.

  The IPV4_UNICAST_NLRI header is shown below.  The Prefix Length
and Prefix fields are encoded in the same manner as the BGP
NLRI field.

  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                       |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 | Prefix Length |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                        Prefix (variable)                      |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |         Entry Count           |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

  The MULTIPROTOCOL header is shown below.  It includes Address
Family Identifier (AFI), Subsequent AFI and a single NLRI entry.
The NLRI information is specific to the AFI and SAFI values.
An implementation which does not recognize particular AFI and SAFI
values SHOULD discard the remainder of the MRT record.

  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                       |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |    Address Family Identifier  |Subsequent AFI |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |     Network Layer Reachability Information (variable)         |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |         Entry Count           |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

  The IPV4_UNICAST_NLRI and MULTIPROTOCOL_NLRI headers are followed
by a series of RIB entries which are repeated Entry Count times.
These entries share a common format as shown below.  They include a
Peer Index from the INDEX_TABLE MRT record, an originated time for
the RIB entry, and the BGP path attribute length and attributes
encoded as provided in a BGP Update message.

  0                   1                   2                   3
 |         Peer Index            |

  There is one exception to the encoding of BGP attributes for the BGP
MP_REACH_NLRI attribute (BGP Type Code 14) [RFC 4760].  Since the AFI,
SAFI, and NLRI information is already encoded in the MULTIPROTOCOL
header, only the Next Hop Address Length and Next Hop Address fields
are included.  The Reserved field is omitted.  The attribute length is
also adjusted to reflect only the length of the Next Hop Address Length
and Next Hop Address fields.

---

From: Larry Blunk <[email-masked]>
Date: Sat, 10 Feb 2007 02:06:01 -0500

1  INDEX_TABLE
   2  IPV4_UNICAST
   3  MULTIPROTOCOL

 0                   1                   2                   3

  0                   1                   2                   3

  0                   1                   2                   3

  0                   1                   2                   3

---

From: "Erik Romijn" <[email-masked]>
Date: Mon, 12 Feb 2007 11:10:09 +0100

> Here's my proposed format for the TABLE_DUMP_V2 type for comment.

Seeing your numbers on the RV dumps, it seems sensible to add this
index. As I hope to increase the amount of routes per peer for RIS too,
I suppose it will help us too in disk space savings.

Note that in my calculations, I didn't check for any data saving due to
saving the prefix fields only once per prefix.

So I support this format, and will be implementing it for RIS.

>   1  INDEX_TABLE

A minor esthetical idea: wouldn't PEER_INDEX_TABLE be clearer,
especially for future changes, if any?

>   2  IPV4_UNICAST

One possibly stupid, certainly not all too relevant, question: why is
this called IPV4_UNICAST, while it also stores IPv6 entries?

cheers,

---

From: "Erik Romijn" <[email-masked]>
Date: Mon, 12 Feb 2007 11:10:09 +0100

cheers,

---

From: "Erik Romijn" <[email-masked]>
Date: Mon, 12 Feb 2007 14:28:27 +0100

Hi all,

Implementing this in Quagga now, but there's something I bumped in to:
how does the reader know whether the prefix is IPv4 or IPv6?
Either I misread several times or there is no defined place to specify
this.

cheers,

---

From: "Erik Romijn" <[email-masked]>
Date: Mon, 12 Feb 2007 14:28:27 +0100

Hi all,

cheers,

---

From: Larry Blunk <[email-masked]>
Date: Mon, 12 Feb 2007 15:50:27 -0500

> especially for future changes, if any?

  Okay, that sounds better.
> this called IPV4_UNICAST, while it also stores IPv6 entries?

   IPV6 RIB entries would be stored in the MULTIPROTOCOL subtype.
The IPV4_UNICAST subtype is only for IPv4 Unicast RIB entries,
so there is no need to specify AFI and SAFI values (basically
saving you the 3 bytes needed to specify these).

  I suppose one could use a single "RIB_ENTRY" subtype instead of separate
IPV4_UNICAST and MULTIPROTOCOL subtypes and always
include the AFI/SAFI fields.

 -Larry

---

From: Larry Blunk <[email-masked]>
Date: Mon, 12 Feb 2007 15:50:27 -0500

-Larry

---

From: Larry Blunk <[email-masked]>
Date: Mon, 12 Feb 2007 15:53:09 -0500

> Either I misread several times or there is no defined place to specify

   This is the IPV4_UNICAST subtype header, so it will only contain
IPV4_UNICAST prefixes.  For IPv6 prefixes, you would use the
MULTIPROTOCOL subtype.

 -Larry

---

From: Larry Blunk <[email-masked]>
Date: Mon, 12 Feb 2007 15:53:09 -0500

-Larry

---

From: "Erik Romijn" <[email-masked]>
Date: Tue, 13 Feb 2007 12:20:09 +0100

> saving you the 3 bytes needed to specify these).

OK, that makes good sense. Most of the routes in a dump will be IPv4.
But if we're going for space savings, it might be beneficial to add
IPV6_UNICAST at a later time, when the average dump also contains loads
of IPv6 entries.

Assuming no further comments arise, will a new version of the draft be
published, with the TABLE_DUMP_V2 and BGP_STATE_CHANGE_AS4 types?
It would be nice to have something to refer RIS rawdata users to.*

* I know it's a bad thing(tm) to use a draft as a standard or refer to
  it for documentation, but I doubt I have any other option.

cheers,

---

From: "Erik Romijn" <[email-masked]>
Date: Tue, 13 Feb 2007 12:20:09 +0100

cheers,

---

From: "Erik Romijn" <[email-masked]>
Date: Wed, 21 Feb 2007 10:28:37 +0100

> and Prefix fields are encoded in the same manner as the BGP

If this header is specifically for IPv4, why is the Prefix field not
simply 4 bytes?

cheers,

---

From: "Erik Romijn" <[email-masked]>
Date: Wed, 21 Feb 2007 10:28:37 +0100

cheers,

---

From: "Erik Romijn" <[email-masked]>
Date: Wed, 21 Feb 2007 10:59:54 +0100

> If this header is specifically for IPv4, why is the Prefix field not

Initial guess: depending on the prefix length, only the first few bytes
are saved? (e.g. only the first 3 bytes for a /17-/24)
Perhaps this should be mentioned in the text.

cheers,

---

From: "Erik Romijn" <[email-masked]>
Date: Wed, 21 Feb 2007 10:59:54 +0100

cheers,

---

From: Larry Blunk <[email-masked]>
Date: Fri, 23 Feb 2007 10:34:41 -0500

> Perhaps this should be mentioned in the text.
   Yes, and it is also consistent with the BGP standard.   I'll mention 
it in the text.

 -Larry

---

From: Larry Blunk <[email-masked]>
Date: Fri, 23 Feb 2007 10:34:41 -0500

-Larry