Subject: Re: [Roll] ROLL Routing Metrics - WF feed-back needed

From: "MiJeom Kim" <[email-masked]>
Date: Mon, 3 Nov 2008 18:19:14 +0900

Hi, Phil,

You are absolutely right. I missed link asymmetry.

However, in link state protocols, nodes keep the list of neighbors. Even in
distance vector protocols, I think there is a high chance for nodes to be
aware of their neighbors as time goes. As you mentioned, for constrained
nodes, it might be overhead to keep the neighbor list. But, I don't think it
is very resource consuming to find out the neighbors unless considering very
dynamic networks.

My main concern is whether we need the node degree as a LLN routing metric
and if we do, how we manipulate it. As the document says, it is questionable
whether high node degrees are preferable or not. The decision requires too
many factors need to be considered. Consequently, it's challenging to make
use of node degree as a metric.

Thanks.

Mijeom.

On Sat, Nov 1, 2008 at 1:13 AM, Philip Levis <[email-masked]> wrote:

>
> On Oct 31, 2008, at 1:20 AM, MiJeom Kim wrote:
>
>
>> 4.6: Is the intention that a node calculates its degree? This is very
>> difficult (some might say impossible under any realistic network scenario).
>> First, it requires O(n^2) communication. The observation that routing
>> protocols might want to change decisions based on density makes sense, but
>> by stating it is a metric that implies nodes calculate it.
>> ===>
>> I think a node can figure out its degree by overhearing. So as time goes,
>> it can get the number of neighbors more precisely.
>>
>
> That would be true if degree were defined as the number of neighbors a node
> can hear. However, it's defined as
>
>   Node degree is the number of neighbors that can receive a message
>   from the node directly.
>
> Unless you assume asymmetric links do not exist, this requires each node to
> report the set of nodes from which it hears messages, so those nodes can
> calculate their degree. It also requires a node to maintain state linear in
> the number of its neighbors, which is problematic.
>
> Phil
>
_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: JP Vasseur <[email-masked]>
Date: Tue, 04 Nov 2008 09:30:57 +0100

Hi,

On 11/3/08 10:19 AM, "MiJeom Kim" <[email-masked]> wrote:

> However, in link state protocols, nodes keep the list of neighbors.
> 
> JP> In link state each node knows the entire topology, thus the set of
> neighbors.
> 
> Even in distance vector protocols, I think there is a high chance for nodes to
> be aware of their neighbors as time goes. As you mentioned, for constrained
> JP> This is clearly a tradeoff between protocol overhead to keep track of a
> list of neighbors (potentially not a negligible amount of data) compared to
> what it brings to routing. If the motivation is to compute alternate routes,
> there are other technique and the node degree is not sufficient to compute
> diverse path anyway so this would at best be used as a heuristic.
>  
> My main concern is whether we need the node degree as a LLN routing metric and
> if we do, how we manipulate it. As the document says, it is questionable
> many factors need to be considered. Consequently, it's challenging to make use
> of node degree as a metric.
> 
> JP> Right. 
> 
> So .. I guess that we have a WG consensus not to use it.
> 
> Anybody with a different opinion ?
> 
> Thanks.
> 
> JP.
>  
> Thanks.
> Mijeom.
> 
>>> I think a node can figure out its degree by overhearing. So as time goes, it
>>> can get the number of neighbors more precisely.
>>

---

From: "Schoofs, Anthony" <[email-masked]>
Date: Wed, 5 Nov 2008 10:12:27 +0100

In 6lowPAN networks, a node may be able to calculate its degree thanks to 6lowpan Neighbor Discovery mechanisms.
LowPAN routers could know how many nodes are surrounding them via Router Solicitations and Router Registration messages they receive from neighboring nodes.
Because these mechanisms are repeated periodically, LowPAN Routers may be able to maintain a "fresh" node degree without having to generate extra packets.

Best regards,
Anthony

________________________________
From: [email-masked] [mailto:[email-masked]] On Behalf Of JP Vasseur
Sent: Tuesday 4 November 2008 9:31
To: MiJeom Kim; Philip Levis
Cc: ROLL WG
Subject: Re: [Roll] ROLL Routing Metrics - WF feed-back needed

Hi,

JP> In link state each node knows the entire topology, thus the set of neighbors.

Even in distance vector protocols, I think there is a high chance for nodes to be aware of their neighbors as time goes. As you mentioned, for constrained nodes, it might be overhead to keep the neighbor list. But, I don't think it is very resource consuming to find out the neighbors unless considering very dynamic networks.

JP> This is clearly a tradeoff between protocol overhead to keep track of a list of neighbors (potentially not a negligible amount of data) compared to what it brings to routing. If the motivation is to compute alternate routes, there are other technique and the node degree is not sufficient to compute diverse path anyway so this would at best be used as a heuristic.

My main concern is whether we need the node degree as a LLN routing metric and if we do, how we manipulate it. As the document says, it is questionable whether high node degrees are preferable or not. The decision requires too many factors need to be considered. Consequently, it's challenging to make use of node degree as a metric.

JP> Right.

Thanks.

JP.

Thanks.
Mijeom.

4.6: Is the intention that a node calculates its degree? This is very difficult (some might say impossible under any realistic network scenario). First, it requires O(n^2) communication. The observation that routing protocols might want to change decisions based on density makes sense, but by stating it is a metric that implies nodes calculate it.
===>
I think a node can figure out its degree by overhearing. So as time goes, it can get the number of neighbors more precisely.

That would be true if degree were defined as the number of neighbors a node can hear. However, it's defined as

Unless you assume asymmetric links do not exist, this requires each node to report the set of nodes from which it hears messages, so those nodes can calculate their degree. It also requires a node to maintain state linear in the number of its neighbors, which is problematic.

Phil

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

________________________________
The information contained in this message may be confidential and legally protected under applicable law. The message is intended solely for the addressee(s). If you are not the intended recipient, you are hereby notified that any use, forwarding, dissemination, or reproduction of this message is strictly prohibited and may be unlawful. If you are not the intended recipient, please contact the sender by return e-mail and destroy all copies of the original message.
_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: Jonathan Hui <[email-masked]>
Date: Mon, 10 Nov 2008 08:24:24 -0800

Hi Anthony,

This implies that nodes will have sufficient capabilities to maintain  
a list for an arbitrary number of neighbors. In some cases, a node may  
have hundreds of neighbors and the routing protocol should not fail  
simply because it cannot maintain state for a significant portion of  
them.

--
Jonathan Hui

On Nov 5, 2008, at 1:12 AM, Schoofs, Anthony wrote:

> In 6lowPAN networks, a node may be able to calculate its degree  
> thanks to 6lowpan Neighbor Discovery mechanisms.
> LowPAN routers could know how many nodes are surrounding them via  
> Router Solicitations and Router Registration messages they receive  
> from neighboring nodes.
> Because these mechanisms are repeated periodically, LowPAN Routers  
> may be able to maintain a “fresh” node degree without having to  
> generate extra packets.
>
> Best regards,
> Anthony
>
>
> Even in distance vector protocols, I think there is a high chance  
> for nodes to be aware of their neighbors as time goes. As you  
> mentioned, for constrained nodes, it might be overhead to keep the  
> neighbor list. But, I don't think it is very resource consuming to  
> find out the neighbors unless considering very dynamic networks.
>
> JP> This is clearly a tradeoff between protocol overhead to keep  
> track of a list of neighbors (potentially not a negligible amount of  
> data) compared to what it brings to routing. If the motivation is to  
> compute alternate routes, there are other technique and the node  
> degree is not sufficient to compute diverse path anyway so this  
> would at best be used as a heuristic.
>
> My main concern is whether we need the node degree as a LLN routing  
> metric and if we do, how we manipulate it. As the document says, it  
> is questionable whether high node degrees are preferable or not. The  
> decision requires too many factors need to be considered.  
> Consequently, it's challenging to make use of node degree as a metric.
>
> JP> Right.
>
> 4.6: Is the intention that a node calculates its degree? This is  
> very difficult (some might say impossible under any realistic  
> network scenario). First, it requires O(n^2) communication. The  
> observation that routing protocols might want to change decisions  
> based on density makes sense, but by stating it is a metric that  
> implies nodes calculate it.
> ===>
> I think a node can figure out its degree by overhearing. So as time  
> goes, it can get the number of neighbors more precisely.
>
> That would be true if degree were defined as the number of neighbors  
> a node can hear. However, it's defined as
>
> Unless you assume asymmetric links do not exist, this requires each  
> node to report the set of nodes from which it hears messages, so  
> those nodes can calculate their degree. It also requires a node to  
> maintain state linear in the number of its neighbors, which is  
> problematic.
>
> Phil
>
> The information contained in this message may be confidential and  
> legally protected under applicable law. The message is intended  
> solely for the addressee(s). If you are not the intended recipient,  
> you are hereby notified that any use, forwarding, dissemination, or  
> reproduction of this message is strictly prohibited and may be  
> unlawful. If you are not the intended recipient, please contact the  
> sender by return e-mail and destroy all copies of the original  
> message.

---

From: JP Vasseur <[email-masked]>
Date: Mon, 10 Nov 2008 17:44:20 +0100

Furthermore, it is not yet obvious that such metric will be so useful from a
routing standpoint ...

On 11/10/08 5:24 PM, "Jonathan Hui" <[email-masked]> wrote:

>> may be able to maintain a ³fresh² node degree without having to
>> generate extra packets.
>> 
>> Best regards,
>> Anthony
>> 
>>

---

From: Jonathan Hui <[email-masked]>
Date: Mon, 10 Nov 2008 08:46:59 -0800

Completely agree. We also haven't yet come up with a clear definition  
of node degree.

--
Jonathan Hui

---

From: "Schoofs, Anthony" <[email-masked]>
Date: Mon, 10 Nov 2008 19:16:03 +0100

Hi Jonathan,

The draft currently says that "Node degree is the number of neighbors that can receive a message from the node directly. "

If this implies that you need to maintain a list for an arbitrary number of neighbors , then it is indeed not favorable.
If you are only interested in the number of neighbours, there may be some ways to deliver that number without having to maintain a list of neighbors. For example (just a try), adding +1 to a Node degree variable for each new ICMP message (RS or RR) received by a LowPAN router and have the variable reseted periodically (depending on the RS and RR refresh periods of the LowPAN hosts) could give a node degree to LowPAN routers.

Besides, I also agree that we shoud consider first whether we need the Node degree metric.

Best regards,
Anthony

________________________________________
From: Jonathan Hui [[email-masked]]
Sent: Monday, November 10, 2008 5:24 PM
To: Schoofs, Anthony
Cc: JP Vasseur; MiJeom Kim; Philip Levis; ROLL WG
Subject: Re: [Roll] ROLL Routing Metrics - WF feed-back needed

Hi Anthony,

--
Jonathan Hui

---

From: Jonathan Hui <[email-masked]>
Date: Mon, 10 Nov 2008 10:33:39 -0800

Hi Anthony,

On Nov 10, 2008, at 10:16 AM, Schoofs, Anthony wrote:
> If this implies that you need to maintain a list for an arbitrary  
> number of neighbors , then it is indeed not favorable.
> If you are only interested in the number of neighbours, there may be  
> some ways to deliver that number without having to maintain a list  
> of neighbors. For example (just a try), adding +1 to a Node degree  
> variable for each new ICMP message (RS or RR) received by a LowPAN  
> router and have the variable reseted periodically (depending on the  
> RS and RR refresh periods of the LowPAN hosts) could give a node  
> degree to LowPAN routers.

This requires nodes to broadcast beacons with a fixed period and  
implies that beacon periods are not adaptive to local conditions - not  
good characteristics if we're trying to develop an energy efficient  
protocol.

--
Jonathan Hui

---

From: JP Vasseur <[email-masked]>
Date: Thu, 13 Nov 2008 10:43:36 +0100

And still, it is far from being obvious that such metric is useful at all.
One can of course specify heuristic to make "some" use of it ... But I'm
personally not convince at all, as many of you of the list.

Cheers,

JP.