Subject: [Roll] Metrics ID, need for a new 'filling rate' metric

From: Nicolas DEJEAN <[email-masked]>
Date: Wed, 23 Jun 2010 15:32:05 +0200

Hello WG,

In networks where the application traffic is well-known, a balanced
graph is a fine way for ensuring the expected lifetime of the whole
network.

However, proactively building a balanced graph as leaf nodes are
turned on one after the other would require a new kind of metric
expressing the current number of children of a given router or better
its 'filling rate'.

A format on 2 or 3 bits for the 'filling rate' might be enough for this purpose.

Your thoughts?

Nicolas.

---

From: <[email-masked]>
Date: Wed, 23 Jun 2010 15:40:28 +0200

Would that be a normalized measure, like 0b111 is "nearly 100% full" and 0b000 is "0%" ?
I guess you mean "fill ratio", not "rate".
If yes, this sounds good to me !

Would this go in the NSA object, alongside the O bit ?
How different is it from the O bit, apart from being 2 or 3 bits ?
If the O were extended to 2 or 3 bits, couldn't it be used for that same purpose (in networks were graph balance is sufficient to balance traffic and energy consumption)?

Just thinking aloud...

Dominique 

-----Message d'origine-----
De : [email-masked] [mailto:[email-masked]] De la part de Nicolas DEJEAN
Envoyé : mercredi 23 juin 2010 15:32
À : roll WG
Objet : [Roll] Metrics ID, need for a new 'filling rate' metric

Hello WG,

In networks where the application traffic is well-known, a balanced graph is a fine way for ensuring the expected lifetime of the whole network.

However, proactively building a balanced graph as leaf nodes are turned on one after the other would require a new kind of metric expressing the current number of children of a given router or better its 'filling rate'.

Your thoughts?

Nicolas.
_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: Nicolas DEJEAN <[email-masked]>
Date: Fri, 25 Jun 2010 18:04:29 +0200

Dominique,

yes for sure, 'ratio' is the right word, thanks for the correction.

I think this would not be an extension of the 'O' bit.
The 'O' bit is really 'stop routing traffic through that node', the
node is overloaded (it could have only a few children and be
overloaded or have a lot of children and not be overloaded).

The 'O' bit is usefull 'dynamically' when traffic load implied by the
application running on the network is not known a priori.

I think, we really have a new metric to define here.
Maybe it could be embedded into the NSA object as a new field but I
would prefer defining a new object for this metric mainly for clarity
and usability as a constraint.

Cheers,

Nicolas.

---

From: JP Vasseur <[email-masked]>
Date: Fri, 25 Jun 2010 18:52:34 +0200

Hi,

> overloaded or have a lot of children and not be overloaded).

Right and the O bit could be set as a result of a number of events.

> and usability as a constraint.

Makes sense to me too.

JP.

>> If the O were extended to 2 or 3 bits, couldn't it be used for that  
>> same purpose (in networks were graph balance is sufficient to  
>> balance traffic and energy consumption)?
>>
>> Just thinking aloud...
>>
>> Dominique
>>
>> expressing the current number of children of a given router or  
>> better its 'filling rate'.
>>

---

From: Philip Levis <[email-masked]>
Date: Mon, 28 Jun 2010 09:27:04 -0700

> and usability as a constraint.

We experimented with a mechanism in CTP that is similar to the 'O' bit. The message has two parts: our experiences and what I'd recommend based on these experiences.

Experiences
----------------
The 'O' bit is pretty dangerous. In CTP, we tried for 6 months so to incorporate a similar mechanism: it was called the 'C' or 'Congested' bit. It turned out to be a complete disaster: after 6 months of trying to get it to work we gave up. There are two basic problems: dynamism and clearing the bit. In particular "stop routing traffic through that node" is a terrible policy.

The reason is pretty simple: let's say you have a topology where there are N nodes that can choose from K next hops (K < N). Because this is wireless, those K next hops are mostly within radio range of one another. For whatever reason, the load that those N nodes offer is greater than a next hop can sustain (e.g., its next hop link ETX goes up, such that it can send fewer packets/s). The current next hop, k, sees its queue is overflowing and sets the 'O' bit. It multicasts a DIO to tell its children to stop routing through it.

So all of the children chose a different next hop. Because their load is greater than what a single next hop can sustain, this node sets the 'O' bit as well. They quickly cycle through the K next hops, all of whom set the 'O' bit. Now they have to increase in Rank in order to choose a next hop.

Furthermore, informing them of a cleared 'O' bit requires a new multicast DIO. As soon as any of the K nodes sends such a DIO, all of the N nodes start forwarding through it again, causing it to set the 'O' bit...

Basically, what we saw was that as soon as a node sets the 'O' bit, this denotes a burst or losses or reduced throughput further along in the DODAG. As soon as one node sets it, there's a cascade of failures and the topology in that sub-DODAG collapses.

Recommendation
-----------------
We concluded that statements of MUST/SHOULD/MAY relating to the 'O' bit have to only related to *when* the bit is set, and can't relate to how a node *responds* to hearing the 'O' bit. 

For example, CTP started with saying that a node, upon hearing the 'O' bit set, MUST NOT route through a node until it hears the 'O' bit cleared. This was a disaster. The text now reads that a node MUST set the 'O' bit when it drops a packet due to a queue overflow. Of course, if you don't specify either when to set it or what to do when it is set, then the bit is meaningless. 

Phil

Phil

---

From: Nicolas DEJEAN <[email-masked]>
Date: Wed, 30 Jun 2010 21:08:20 +0200

Hello Philip,

> We experimented with a mechanism in CTP that is similar to the 'O' bit. The message has two parts: our experiences and what I'd recommend based on these experiences.

Thanks for the experience sharing and the detailed explanation.

> Recommendation

What I understand here is that the conclusion of your experiments is
that the 'O' bit cannot be used as I described. Right?

So what do we have?

About the 'O' bit, the metrics-07 is aligned with your recommandations.
(My own interpretation was not and I thank you again for all the details.)
Moreover, the meaning of this flag is clearly expressed as "may not be
able to process traffic". Some text also describes how it could be
used in a similar way than IS-IS.
However, for the moment, how to set the bit and what to do when it is
set is described as outside the scope.
Does CTP propose a solution about what to do when hearing the 'O' bit?

The 'fill ratio' metric I described has really a different meaning and
should be managed in a separate metric as an implementation could use
both mechanisms (but also for clarity and usage as a constraint).

What do you think?

> Phil

Best regards,

Nicolas.

---

From: Philip Levis <[email-masked]>
Date: Wed, 30 Jun 2010 13:10:21 -0700

> that the 'O' bit cannot be used as I described. Right?

I wouldn't go that far. Instead, we tried for a good six months to make it work as described and concluded it probably wasn't the right approach.

> Does CTP propose a solution about what to do when hearing the 'O' bit?

It does not propose a solution. We tried a few and none worked well. So we have left it as an open question.

> both mechanisms (but also for clarity and usage as a constraint).

I don't know. I tend to be pretty conservative in these things. Wireless protocol design is littered with so many ideas that looked good on paper but didn't work well in practice. So I generally shrug until I've seen supporting data from real-world networks. I don't see any reasons off the top of my head why the metric you proposed would be unlikely to work in practice, but there very well could be some that none of us know.

Phil

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 01 Jul 2010 08:57:12 +0200

Le 30/06/2010 19:23, Philip Levis a écrit :
>
> On Jun 30, 2010, at 8:54 AM, Alexandru Petrescu wrote:
>
>> Le 30/06/2010 17:03, Pascal Thubert (pthubert) a écrit :
>>> cribed.
>>>
>>> Anything else we need to add / update / delete ?
>>
>> Yes add IPsec AH I can write text if you need.
>
> Alex,
>
> Are you suggesting that AH should replace the current security
> mechanisms, or that it's an additional option?

Replace.

IPsec AH covers ICMP completely and potentially other headers proposed
for RPL in 6MAN - it would be worthless to have two signatures one IPsec
and one issued from Abit CCM*.

Proposal to write IPsec AH first, and make the current (A) bit and CCM*
optional enhancements.

Alex