Subject: [Roll] P2P routing

From: Mukul Goyal <[email-masked]>
Date: Sun, 12 Jul 2009 13:56:40 -0500 (CDT)

The tree/DAG based P2P routing proposed in RPL may not be desirable in many situations.

Here is the outline of an alternative P2P routing solution:

1. The P2P routing would follow a basic DV approach, where nodes would advertize their "cost" to various destinations in Hello/"Router Advertisement" messages and next-hop(s) selection (for a destination) is based on the advertised costs by neighbors.
    1.1 A node may solicit advertisements from its neighbors regarding a destination.
    1.2 The generation of Hello messages may follow a trickle-like approach.
    1.3 In the absence of new advertisements about a destination from a neighbor, the perceived cost of reaching the destination through this neighbor deteriorates with time.
 
2. The LLN would be divided into "domains" such that (costs to) destinations in one domain would be advertized (in Hello messages)by nodes within that domain only. This is to limit the destinations a node may have to advertize. There may be some _super_ destinations that can be advertised across domains.

3. There is no loop avoidance/prevention.

4. There is a loop detection and correction mechanism in place. Periodically, a source node would send a control packet towards the destination. This packet accumulates the path it travels over. If a receiving node finds itself already listed in the path, the routing loop is detected. The node corrects the loop by excluding and punishing the offending nexthop.

Please comment.

Thanks
Mukul

---

From: Philip Levis <[email-masked]>
Date: Sun, 12 Jul 2009 22:42:49 -0700

On Jul 12, 2009, at 11:56 AM, Mukul Goyal wrote:

> 1. The P2P routing would follow a basic DV approach, where nodes  
> would advertize their "cost" to various destinations in  
> Hello/"Router Advertisement" messages and next-hop(s) selection (for  
> a destination) is based on the advertised costs by neighbors.
>    1.3 In the absence of new advertisements about a destination from  
> a neighbor, the perceived cost of reaching the destination through  
> this neighbor deteriorates with time.
>
> 2. The LLN would be divided into "domains" such that (costs to)  
> destinations in one domain would be advertized (in Hello messages)by  
> nodes within that domain only. This is to limit the destinations a  
> node may have to advertize. There may be some _super_ destinations  
> that can be advertised across domains.
>
> 4. There is a loop detection and correction mechanism in place.  
> Periodically, a source node would send a control packet towards the  
> destination. This packet accumulates the path it travels over. If a  
> receiving node finds itself already listed in the path, the routing  
> loop is detected. The node corrects the loop by excluding and  
> punishing the offending nexthop.
>
> Please comment.

In wireless protocols, the devil tends to be in the details. I'd want  
to see a detailed protocol description before commenting.

Phil

---

From: Alexandru Petrescu <[email-masked]>
Date: Mon, 13 Jul 2009 11:01:45 +0200

The routing proposed in RPL does not say how many interfaces a sensor
has, and in some of its pictures shows a sensor with as many as 8
interfaces.  I believe this was not the intention.

However, my interpretation of it does not mean that it is clearer.

How many interfaces does a ROLL node have?

What is the subnet structure in a ROLL network?  Are all sensors in the
same IP subnet?  Or not?  Is there a subnet uniquely between each each
two points?  Or not?

Can IPv6 use link-local multicast in RPL?  Or not?

Without these things clear it is impossible to design a dynamic routing
protocol, let alone an IP addressing structure, not even a static
routing mechanism.

Deciding distance-vector vs link-state vs path-vector, or proactive vs
reactive, or source-routing vs table-based routing, or stateful routing
vs soft-state vs hard-state routing is too early.

TO clarify the IP addressing things (mandatorily preceding what RPL has 
to design), I am optimistically waiting for results of AUTOCONF DT, a 
draft seems to be out about it, but that seems to go against my opinions 
too :-)

Yours,

Alex

Mukul Goyal a écrit :
> would advertize their "cost" to various destinations in Hello/"Router
>  Advertisement" messages and next-hop(s) selection (for a
> destination) is based on the advertised costs by neighbors. 1.1 A
> node may solicit advertisements from its neighbors regarding a
> destination. 1.2 The generation of Hello messages may follow a
> trickle-like approach. 1.3 In the absence of new advertisements about
> a destination from a neighbor, the perceived cost of reaching the
> destination through this neighbor deteriorates with time.
> 
> Thanks Mukul _______________________________________________ Roll 
> mailing list [email-masked] https://www.ietf.org/mailman/listinfo/roll
> 
> 
>

---

From: Dominik Kaspar <[email-masked]>
Date: Mon, 13 Jul 2009 14:27:57 +0200

Hi,

I am also curious about an answer to the question about the number of
interfaces on a ROLL node. Are there any existing sensor network nodes
with a "tiny" form factor, that utilize multiple physical interfaces?

By the way... it might be a good idea to put all the terminology of
the RPL draft into the already existing terminology document.

Greetings,
Dominik

On Mon, Jul 13, 2009 at 11:01 AM, Alexandru
Petrescu<[email-masked]> wrote:
> TO clarify the IP addressing things (mandatorily preceding what RPL has to
> design), I am optimistically waiting for results of AUTOCONF DT, a draft
> seems to be out about it, but that seems to go against my opinions too :-)
>
> Yours,
>
> Alex
>
> Mukul Goyal a écrit :
>>
>> 1. The P2P routing would follow a basic DV approach, where nodes would
>> advertize their "cost" to various destinations in Hello/"Router
>> destinations in one domain would be advertized (in Hello messages)by nodes
>> within that domain only. This is to limit the destinations a node may have
>> to advertize. There may be some _super_ destinations that can be advertised
>> across domains.
>>
>> receiving node finds itself already listed in the path, the routing loop is
>> detected. The node corrects the loop by excluding and punishing the
>> offending nexthop.
>>
>> Please comment.
>>
>> Thanks Mukul _______________________________________________ Roll mailing
>> list [email-masked] https://www.ietf.org/mailman/listinfo/roll
>>
>>
>>
>
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>

---

From: Mukul Goyal <[email-masked]>
Date: Tue, 14 Jul 2009 06:53:38 -0500 (CDT)

Phil

I think that the discussion regarding vital components such as loop avoidance and loop detection & correction techniques can take place even without a draft. I am working on a draft but I would like to discuss these things on the mailing list as well.  

Thanks
Mukul
 
----- Original Message -----
From: "Philip Levis" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "roll" <[email-masked]>
Sent: Monday, July 13, 2009 12:42:49 AM GMT -06:00 US/Canada Central
Subject: Re: [Roll] P2P routing

Phil

---

From: Tim Winter <[email-masked]>
Date: Tue, 14 Jul 2009 13:03:53 -0400

Hi Alex, Dominik,

> the RPL draft into the already existing terminology document.

One transceiver, e.g. one physical interface, seems to be a general case
with LLN nodes.  But there may be multiple logical interfaces as necessary
to support the routing function, depending in part on the subnetwork design
/ how the link layer technology interfaces to IP.

Regarding the underlying implementation of link-local multicast and related
subnetwork issues, I think that RFC3819 provides a great starting point to
understand how a particular link layer technology might be interfaced to IP,
and by extension a ROLL routing solution.  The details of this should be
outside of the scope of ROLL.

--Tim

---

From: Alexandru Petrescu <[email-masked]>
Date: Tue, 14 Jul 2009 19:25:21 +0200

Hello Tim,

Tim Winter a écrit :
> Hi Alex, Dominik,
> 
> Dominik Kaspar wrote:
>> Hi,
>> 
>> I am also curious about an answer to the question about the number
>> of interfaces on a ROLL node. Are there any existing sensor network
>> nodes with a "tiny" form factor, that utilize multiple physical
>> interfaces?
>> 
>> Greetings, Dominik
> One transceiver, e.g. one physical interface, seems to be a general
> case with LLN nodes.  But there may be multiple logical interfaces as
> necessary to support the routing function, depending in part on the
> subnetwork design / how the link layer technology interfaces to IP.

I doubt a constrained device has enough resources to implement logical
or virtual interfaces.

If however it _is_ the case that a ROLL device has several interfaces
then there must be at least one physical interface and there should be a
clear relationship in terms of addressing and routing between the
logical virtual interface(s) and the physical one.  What addresses are
on what interfaces and what routes from which interface to which one.

For example, when the draft-01 pictures a ROLL device with two
interfaces - does it mean that one is physical and the other logical?
Or both are logical and the physical transceiver is absent from the picture?

If this is not clarified and if we continue to assume only one physical
interface then this risks being very theoretical to my reading.

> Regarding the underlying implementation of link-local multicast and
> related subnetwork issues, I think that RFC3819 provides a great
> starting point to understand how a particular link layer technology
> might be interfaced to IP, and by extension a ROLL routing solution.
> The details of this should be outside of the scope of ROLL.

I think the RPL draft should at least say the ROLL node does join all
the link-layer multicast groups as suggested in a certain IPv6 RFC.  It
should also say on which interface it does this joining (the logical?
the physical?)

I think it would be attractive for ROLL protocol to run over link layers
which do support multicast: is this a requirement?  Or could RPL run 
over link-layers which don't support link-layer multicast?

Just some remarks, and thank you for the quick earlier incorporation of 
some of my previous remarks,

Alex

>>> The routing proposed in RPL does not say how many interfaces a
>>> sensor has, and in some of its pictures shows a sensor with as
>>> many as 8 interfaces.  I believe this was not the intention.
>>> 
>>> What is the subnet structure in a ROLL network?  Are all sensors
>>> in the same IP subnet?  Or not?  Is there a subnet uniquely
>>> between each each two points?  Or not?
>>> 
>>> Without these things clear it is impossible to design a dynamic
>>> routing protocol, let alone an IP addressing structure, not even
>>> a static routing mechanism.
>>> 
>>> Deciding distance-vector vs link-state vs path-vector, or
>>> proactive vs reactive, or source-routing vs table-based routing,
>>> or stateful routing vs soft-state vs hard-state routing is too
>>> early.
>>> 
>>> TO clarify the IP addressing things (mandatorily preceding what
>>> RPL has to design), I am optimistically waiting for results of
>>> AUTOCONF DT, a draft seems to be out about it, but that seems to
>>> go against my opinions too :-)
>>> 
>>> Yours,
>>> 
>>> Alex
>>> 
>>> Mukul Goyal a écrit :
>>>> 1. The P2P routing would follow a basic DV approach, where
>>>> nodes would advertize their "cost" to various destinations in
>>>> Hello/"Router Advertisement" messages and next-hop(s) selection
>>>> (for a destination) is based on the advertised costs by
>>>> neighbors. 1.1 A node may solicit advertisements from its
>>>> neighbors regarding a destination. 1.2 The generation of Hello
>>>> messages may follow a trickle-like approach. 1.3 In the absence
>>>> of new advertisements about a destination from a neighbor, the
>>>> perceived cost of reaching the destination through this
>>>> neighbor deteriorates with time.
>>>> 
>>>>  destinations in one domain would be advertized (in Hello
>>>> messages)by nodes within that domain only. This is to limit the
>>>> destinations a node may have to advertize. There may be some
>>>> _super_ destinations that can be advertised across domains.
>>>> 
>>>>  Periodically, a source node would send a control packet
>>>> towards the destination. This packet accumulates the path it
>>>> travels over. If a receiving node finds itself already listed
>>>> in the path, the routing loop is detected. The node corrects
>>>> the loop by excluding and punishing the offending nexthop.
>>>> 
>>>> Please comment.
>>>> 
>>>> Thanks Mukul _______________________________________________
>>>> Roll mailing list [email-masked]
>>> _______________________________________________ Roll mailing list
>>>  [email-masked] https://www.ietf.org/mailman/listinfo/roll
>>> 
>> _______________________________________________ Roll mailing list 
>> [email-masked] https://www.ietf.org/mailman/listinfo/roll
>> 
> _______________________________________________ Roll mailing list 
> [email-masked] https://www.ietf.org/mailman/listinfo/roll
>

---

From: "M. B. Anand" <[email-masked]>
Date: Tue, 14 Jul 2009 19:13:45 -0400

Mukul,
In *very* general terms, nothing wrong this approach. By personal 
experience, pretty much this approach - with added optimizations - has 
been used for networks of over 10s of K nodes with "domains", as you 
called them,  over 2K or so nodes. (sorry, no public reference). The 
ideas of RFC 2091, using incremental updates, can be very effective as 
well. The ROLL protocol survey, draft-ietf-roll-protocols-survey-07 
mentions this. If the "divided" into domains is supposed to be automatic 
and nodes can change domains - and thus drag other nodes into and out of 
domains - that introduces a whole new set of complications involving 
marking and purging destinations and you probably would not be able to 
avoid counting up.

Keep in mind in all of this though, the fundamental point is, simply 
put, the price you pay for generally optimal peer-to-peer routing is a 
massive explosion of state information to be maintained and exchanged - 
every node pretty much has to form a tree rooted at itself. Lot of 
memory to keep all destinations.

On top of that, given typical bandwidth restrictions, and consequently 
the rate and scope of dissemination that is feasible, it has never been 
quite clear if in fact optimality (in shortest path terms) can really be 
achieved in real-life large networks. For a good general discussion of 
this, please see BBN Technical Memorandum No. 1301 (available at 
www.ir.bbn.com/documents/techmemos/TM1301.ps)

Trees and DAGs being discussed in the LLN context all attempt to 
minimize state information by trying to take advantage of certain 
(presumed) flow properties to sacrifice some generality and gain the 
corresponding simplicity benefit.

Of course, the application you envision may only require, or is capable 
of providing, very small domains. In which case, full circle, you might 
want to consider: is the stretch you will presumably get with DAGs and 
trees worth the price of the much larger complexity of general optimal 
peer-to-peer routing ? Because it will be, much more complex I mean.

Regards,
Anand.