Subject: [manet] Path Accumulation in DyMO

From: Ian Chakeres <[email-masked]>
Date: Fri, 12 Nov 2004 06:59:15 -0500

At the MANET meeting I presented DyMO (Dynamic MANET On-demand Routing 
Protocol).  My slides from the presentation are available at 
http://moment.cs.ucsb.edu/~idc/pub/chakeres_ietf61_presentation.pdf.

There was a short discussion about using path accumulation in the base 
specification.  Most people expressed their feelings that path 
accumulation is useful for additional route information dissemination. 
I believe there was consensus to not include path accumulation in the 
core spec though it should definitely be included as an optimization.  
If you disagree, lets discuss it more on the list.

Thanks.
Ian Chakeres

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: Justin Dean <[email-masked]>
Date: Wed, 17 Nov 2004 15:26:58 -0500

I don't know that I agree or if I disagree.  I see tradeoffs in complexity 
no matter which method is used.  With accumulation the problem of large 
packet headers, without storing state.  Although I am leaning towards not 
having it in the base specification because it seems to me easier to 
optionally add accumulation than it would be to take it away.

Justin Dean

At 06:59 AM 11/12/2004 -0500, Ian Chakeres wrote:
>accumulation is useful for additional route information dissemination. I 
>believe there was consensus to not include path accumulation in the core 
>spec though it should definitely be included as an optimization.

---

From: "Charles E.Perkins" <[email-masked]>
Date: Wed, 17 Nov 2004 12:54:42 -0800

Hello Justin,

It seems to me that the path accumulation feature is potentially
quite valuable, and that therefore we should encourage it to be
part of any reactive routing specification.  Whether or not it
should be mandated is a tough question, because one can argue
both sides of the debate by invoking the goal of simplicity.

On the one hand, not having path accumulation in a node certainly
makes the implementation of that node simpler.  Unfortunately, it
makes implementation in the other nodes more complicated, if
those other nodes wish to provide and use the path accumulation
information.  If not all nodes comply, then adjacency cannot be
inferred for the nodes in the accumulated list.  In order to
account for this, the data structure used for reporting the path
accumulation data may have to be expanded somewhat.

So, over time as more and more nodes implement the path
accumulation feature, I think that the results of noncompliance
by some nodes would be:
- an increase in the overall complexity of the network
- an increase in the amount of data per node reported, because
  of the expanded data structures required
- a reduction in the effectiveness of the algorithm
- consequently an increase in the number of route discoveries,
- because of that an increase in congestion

I don't have any good data right now about the magnitude
of these likely effects.  Furthermore, I would not let my
intuitions about the need for path accumulation stand in the
way of promulgating a standard for a reactive routing protocol.
But, if I can get the data to quantify the abovementioned
effects, then it would probably make sense for us to weigh
the performance implications when we are engineering the
protocol.

Regards,
Charlie P.

---

From: Thomas Heide Clausen <[email-masked]>
Date: Thu, 18 Nov 2004 14:11 +0100

Ian,

I am still of the general opinion that leaving an option unspecified is a 
bad thing, assuming that it's an option which (i) a plurality of 
deployments might use and (ii) where different approaches/implementations 
might impair interoperability.

What's the general observations on (i) and (ii) regarding path-accumulation?

--thomas
___
Sent with SnapperMail
www.snappermail.com

...... Original Message .......

---

From: Justin Dean <[email-masked]>
Date: Thu, 18 Nov 2004 09:41:52 -0500

I tend to agree with your intuition about the complexity
that arises when some nodes implement path accumulation
and others don't.  And I guess my general feeling of things
is that IF the option to not have path accumulation is a desired
goal, for whatever reason, then it would seem to be easier to add a form
of path accumulation on top of a network which does not do path
accumulation than it would be to take it away from a network.

On the other hand having the extra link state information disseminated
throughout the network on route requests can lead, down the line, to
some nice proactive options.

I also wanted to elaborate one something you said.

"If not all nodes comply, then adjacency cannot be
inferred for the nodes in the accumulated list."

Correct but virtual adjacency can be inferred and with a metric
inclusive path accumulation method a "longer" path can be added
to the packet when it re-enters the network doing path accumulation.

I am still on the fence with this issue and either way is doable
depending on how the spec is written.

Justin Dean

---

From: Ian Chakeres <[email-masked]>
Date: Thu, 18 Nov 2004 12:33:31 -0800

First I want to issue a query to the list.  Does anyone think we should 
use path accumulation to alleviate creating a reverse route to the 
source during RREQ propagation? I'd like to get consensus that this is 
a non-issue.

Given that we don't perform path accumulation for the reason of not 
storing the reverse route during RREQ propagation, I think there are a 
large number of possibilities for disseminating additional information. 
For example, we could include each node on the path, and their sequence 
number. Alternatively we could create a more modular option that allows 
us to include only some nodes on the path. Or even more versatile a 
method to disseminate routes that are not on the RREQ/RREP path (i.e. 
gateways). It could even carry additional information, hop count, 
metric, security information, etc...

Given all these choices I would prefer to leave this as an open issue 
pending experimentation, instead of attempting to specify the "way" to 
do it in the base spec.  Obviously we could do both, specify one way 
and allow additional options for others.  I'm open to that option also.

Does anyone have a feeling as to what if any technique should be 
included in the base specification but not mandated? What information 
should be disseminated?

Thanks.
Ian Chakeres

---

From: Li Li <[email-masked]>
Date: Fri, 19 Nov 2004 11:03:49 -0500

At 12:33 PM 11/18/2004 -0800, Ian Chakeres wrote:
>number. 

Correct me if I'm wrong. I think this is an option doing the path
accumulation, to know the reverse path. As Justin pointed out in his
earlier email that we may use the RREQ and RRES to carry the path instead
of storing the state. RRES can pop off the used address to cut short the
header along the way. Carrying the path may not bring much complexity in
implementation but would result in a longer header to take more bandwidth.
Don't know if someone has some data to compare the bandwidth taken by the
longer header vs. taken by the messages needed to get a reverse path? I
somehow favor carrying the path. Used it in other protocols before and felt
it very handy. I think path accumulation is very valuable to be included in
the protocol. 

Thanks,

li li

---

From: Li Li <[email-masked]>
Date: Fri, 19 Nov 2004 13:45:30 -0500

At 12:33 PM 11/18/2004 -0800, Ian Chakeres wrote:
> Alternatively we could create a more modular option that allows 
If including only some nodes not every node, then the format/structure and
the procedure may be more complex than every node is included? Is this for
the purpose that nodes can have an option of not supporting the feature? 

Using RREQ/RREP etc. to disseminate all kinds of information should be
optional based on which feature it is for, if the feature is optional or
mandatory. I feel path accumulation for routing more valuable than some of
the others. Also saodv draft has proposed some security information for the
security requirements. 

li li
Li Li, Ph.D
Communications Research Centre, Industry Canada
3701 Carling avenue 
P.O. box 11490 
Station H, Ottawa, 
Ontario, Canada K2H 8S2 
Tel: (613) 990-5246 
Email: [email-masked]