Subject: Re: [Roll] P2P routing

From: Mukul Goyal <[email-masked]>
Date: Wed, 15 Jul 2009 19:32:52 -0500 (CDT)

Anand

Thanks for your email. It allows me a satisfaction that my emails to this list are not an exercise in soliloquy. :)

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

The "domains" is just one approach to limit the spread of reachability information (about a destination) in an LLN. I agree that dymanic membership to a domain is perhaps not a good idea. For LLN with static nodes, the node locations may naturally provide domain boundaries. 

We can also borrow ideas from fish-eye routing where the probability of whether a node maintains state regarding a destination depends on its distance from the destination. 

It seems to me that the LLN may enforce GLOBAL policies (e.g. domains) and then nodes may additionally have LOCAL policies (e.g. fish-eye routing etc.) regarding the maintenance and advertizing of the routing state. Within the constraints imposed by GLOBAL policy, the nodes MUST be able to enforce its LOCAL policy. For example, a node MUST be able to not advertize a destination even if it belongs to the same domain as the node. The local policy could very well be to advertize no destination at all (i.e. the node refuses to participate in routing packets) or a default destination or any subset of destinations allowed under the global policy.
   
>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.

A desirable solution should not _enforce_ optimal P2P routing; it should _allow_ optimal (whatever that means) P2P routing, which RPL does not. The quality of routes would be a function of how much routing state the nodes maintain and advertize. As I mentioned before, the nodes MUST be allowed to implement local policies regarding routing state. There is no requirement that all nodes maintain state regarding all destinations.

Another point to consider is that the problem of routing state explosion seems universal. Even in RPL, facilitating P2MP routing risks state space explosion. The RPL nodes, especially at higher echelons in the DAG, may have tough time storing all the DAOs they may receive. 
  
>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)

I agree that optimality may be a mirage. But that seems like an issue involving proper selection of routing metrics.

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

I love DAGs (and RPL) for GLOBAL MP2P traffic. Where such traffic is dominant, RPL is great. But, there has to be an alternative available when this is not so. There are LLN applications where there exist several localized P2P or MP2P traffic flows that do not form a natural DAG when considered together. Why enforce a DAG in such cases?

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

The LLN applications deserve a choice. Choice to use DAGs and RPL where they are appropriate and use some other solution when RPL is not appropriate. If the stretch in routes caused by RPL's routing along a DAG is acceptable, the application should use RPL by all means. If not, there must be an alternative available. As I mentioned before, we can design the alternative solution so that it allows a tradeoff between the quality (or optimality) of routes and the routing state the nodes maintain.

Again, thanks for taking time to send comments.

Regards
Mukul

>Regards,
>Anand.

> 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   
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>
>   

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