Re: [Roll] [roll] #11: Decision on prefix packing in DIO messages

[JP Vasseur <jvasseur at cisco.com>]

Dear all, 

Here is a proposed resolution.

Issue: as of today: there is exactly one prefix per DAO. Thanks to the DelayDAO timer,

we may have a chance to perform data aggregation (when possible) but we would 

still end up with an increasing number of DAO as we get closer to the sink, with the 

worst case being one DAO per leaf ...

As a reminder, here is the format of the DAO message:

        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |         DAO Sequence          |  InstanceID   |   DAO Rank    |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                          DAO Lifetime                         |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                           Route Tag                           |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       | Prefix Length |    RRCount    |                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               |
       |                   Prefix (Variable Length)                    |
       .                                                               .
       .                                                               .
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |             Reverse Route Stack (Variable Length)             |
       .                                                               .
       .                                                               .
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

We have three options:

1) Option 1 (Trivial packing): we change the DAO message structure to carry more than one prefix

in a DAO message. This is of course only possible for prefixes sharing the same route tag, rank.

2) Option 2: we also try to factorize common element. By adopting a flexible encoding, we avoid  

repeating fields that are identical for a set of prefixes. Back to the example provided below, this would

avoid repeating the value of the Reverse Route Stack for each prefix that uses the same recorded

path.

Thoughts ?

Thanks.

JP.

On Nov 2, 2009, at 3:04 PM, roll issue tracker wrote:

#11: Decision on prefix packing in DIO messages
--------------------------------+-------------------------------------------
Reporter:  jpv at …               |       Owner:  jpv at …        
    Type:  enhancement         |      Status:  new          
Priority:  major               |   Milestone:               
Component:  rpl                 |     Version:               
Severity:  Active WG Document  |    Keywords:               
--------------------------------+-------------------------------------------
Currently RPL requires one DAO per message.

JP's proposal below:

Hi Jonathan,

What I was referring to was to pack prefix in DAO, a very light change in
the spec (just make use of TLV) and factor the common fields. This allows
to reduce the number of packets very significantly as we get closer to the
root.

There two benefits here:
1) You send one DAO between C and D instead of 3
2) You can also pack the Reverse Route Stack whenever possible for all
prefix sharing the same routes.

Let's suppose that:
1) X advertises two prefixes X1 and X2
2) Y advertises two prefixes Y1, Y2 and Y3
3) Z advertised one prefix: Z1

Instead of sending 6 DAO, C would send one DAO to D would look like this:
X1,X2[XBC], Y1,Y2,Y3[YBC], Z1[ZBC]

Note that you could when possible also aggregates prefixes at the same
time if they share a common path.

BAck to you timing question Richard, it depends of the sequence of events
but there is no need to wait.
C could start with one DAO and then start to pack at it receives more, the
same reasoning applies to other
nodes.

Others, thoughts ?

Thanks.

JP.

--
Ticket URL: <https://svn.tools.ietf.org/wg/roll/trac/ticket/11>
roll <http://tools.ietf.org/wg/roll/>