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

From: "roll issue tracker" <[email-masked]>
Date: Mon, 02 Nov 2009 14:04:16 -0000

#11: Decision on prefix packing in DIO messages
--------------------------------+-------------------------------------------
 Reporter:  jpv@…               |       Owner:  jpv@…        
     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/>

---

From: JP Vasseur <[email-masked]>
Date: Mon, 9 Nov 2009 12:34:25 +0100

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:

> -------------------------------- 
> +-------------------------------------------
> -------------------------------- 
> +-------------------------------------------

---

From: "Mathilde Durvy (mdurvy)" <[email-masked]>
Date: Mon, 9 Nov 2009 13:49:15 +0100

Hi JP,
 
Quick questions to help make my choice:
- Is it correct to say that all the fields except the Instance ID, the
RRcount and the Reverse Route Stack are per prefix?
- Why do you need the instance ID? Either you assume that DAO are sent
in unicast to preferred parents and hence you only receive DAO from
childs belonging to your DAG iteration or you would need to specify the
InstanceID, DAGID, DAG sequence triplet no?
- The route tag (32bits!) usage is undefined for now, shall we drop it?

Best,
Mathilde
________________________________

From: [email-masked] [mailto:[email-masked]] On Behalf Of
JP Vasseur (jvasseur)
Sent: lundi, 9. novembre 2009 12:34
To: [email-masked]
Subject: Re: [Roll] [roll] #11: Decision on prefix packing in DIO
messages

Dear all,  

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 ...

        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:

Thoughts ?

Thanks.

JP.

	
--------------------------------+---------------------------------------
----
	Reporter:  jpv@...               |       Owner:  jpv@...        
	    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:
	
	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.

---

From: JP Vasseur <[email-masked]>
Date: Tue, 10 Nov 2009 15:42:00 +0100

On Nov 9, 2009, at 12:34 PM, JP Vasseur wrote:

> Issue: as of today: there is exactly one prefix per DAO. Thanks to  
> the DelayDAO timer,
> still end up with an increasing number of DAO as we get closer to  
> the sink, with the
> 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.
> repeating fields that are identical for a set of prefixes. Back to  
> the example provided below, this would

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Tue, 10 Nov 2009 17:06:24 +0100

Hi all,
 
many prefixes will not share the same rank, but packing is still good
for these different prefixes, hence i do not think we can leave rank
prefix independant. same for route tag. rr stack is more tricky. we
could use:
 
common header:
dao sequence, lifetime and instance
 
option:
type | length | NB prefixes | 
rank | route tag | rr count | rr stack | prefix 1 len | prefix 1 |
prefix 2 len | prefix 2
 
A DAO would look like:
header | option 1, includes 2 prefixes | option 2, includes 3
prefixes...
 
thoughts?
Julien

	From: [email-masked] [mailto:[email-masked]] On
Behalf Of JP Vasseur (jvasseur)
	Sent: mardi 10 novembre 2009 15:42
	To: roll WG
	Subject: [Roll] OPINION TO CLOSE TICKET 11: Decision on prefix
packing inDIO messages

		Dear all,  

		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 ...

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

		

		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.

	
--------------------------------+---------------------------------------
----
			Reporter:  jpv@...               |       Owner:
jpv@...        
			    Type:  enhancement         |      Status:
new          
			Priority:  major               |   Milestone:

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

---

From: JP Vasseur <[email-masked]>
Date: Tue, 10 Nov 2009 17:12:55 +0100

HI Julien,

So I guess that your preference is to pack (option 2), thanks. We can  
propose a BNF for that.

JP.

On Nov 10, 2009, at 5:06 PM, Julien Abeille (jabeille) wrote:

> Hi all,
>
> many prefixes will not share the same rank, but packing is still  
> good for these different prefixes, hence i do not think we can leave  
> rank prefix independant. same for route tag. rr stack is more  
> tricky. we could use:
>
> common header:
> From: [email-masked] [mailto:[email-masked]] On Behalf  
> Of JP Vasseur (jvasseur)
>> we may have a chance to perform data aggregation (when possible)  
>> but we would
>> avoid repeating the value of the Reverse Route Stack for each  
>> prefix that uses the same recorded
>> path.
>>
>> Thoughts ?
>>
>> Thanks.
>>
>> JP.
>>