Subject: Re: [manet] #13: Supporting monotonically nondecreasing but non-additive metrics

From: "manet issue tracker" <[email-masked]>
Date: Tue, 25 Jun 2013 03:56:22 -0000

#13: Supporting monotonically nondecreasing but non-additive metrics

Comment (by [email-masked]):

 On 1/10/2013 1:09 AM, Abdussalam Baryun wrote:

 I agree, that is important advantage of using metric and cost for AODVv2.

 -------------------------------------------------------------------------

 On 1/10/2013 1:50 AM, Dearlove, Christopher (UK) wrote:

 Such a metric can, in general, lead to looping. Consider A, B, C, D, E in
 a ring with metric 2 on links A - B, B - C and C - D, and metric 1 on
 links D - E and E - A. Consider a packet from B routed to E. At B it is
 indifferent whether to go via A or C, so may pick C. At C it is
 indifferent whether to go via B or D, so may pick B.

 Of course in that case one can add the additional rule to not send back on
 link just arrived. But a more complicated case can send it in a longer
 loop. You could tie-break by number of hops, but that's actually a more
 complicated metric. However something like that is essential - consider a
 network all of whose links have metric 1. Whether that tie-breaker is, in
 general, sufficient is something not immediately obvious to me.

 And of course that's in general. A specific routing protocol may ensure
 that this doesn't happen. But that would also need work to prove.

 (The essential problem is that non-decreasing is not as good as
 increasing.)

 -------------------------------------------------------------------------

 On 1/10/2013 2:30 AM, Abdussalam Baryun wrote:

 I don't think there is a route until they recieve RREP, the RREP is
 sent through one route. That packet you mentioned will go through the
 path of RREP. I don't think in AODVv2 the metric type and function
 allow loops.  comment in line;

 > Such a metric can, in general, lead to looping. Consider A, B, C, D, E
 in a
 > ring with metric 2 on links A - B, B - C and C - D, and metric 1 on
 links D
 > - E and E - A. Consider a packet from B routed to E. At B it is
 indifferent
 > whether to go via A or C, so may pick C. At C it is indifferent whether
 to
 > go via B or D, so may pick B.
 >

 At B the data packet will go through only one route which should be
 the one received RREP from. It will never receive a RREP from both
 neighbors A and C. At C it will never receive RREP from both nieghbors
 B and D.

 > Of course in that case one can add the additional rule to not send back
 on
 > link just arrived.

 AODV does not care about *links*, it care about *vectors*, I think
 they are different routings even if they may look into the same
 metric-type but different point of views.

 > (The essential problem is that non-decreasing is not as good as
 > increasing.)

 Is there a prove of that? I am not sure we can fix that, because it
 will always depend on why the engineer/applicant used that metric in
 the first place, if that engineer feels that point is true he/she
 should not use non-decreasing, but for some cases an engineer may like
 to use such metric so he/she can use it for a reason.

 -------------------------------------------------------------------------

 On 1/10/2013 5:44 AM, Philippe Jacquet wrote:

 I agree with Chris, this may lead to loops if done careless.

 This metric is the min metric: you replace the + by the min operator, the
 cost of a route is the min bandwidth of the links on the route. The aim is
 to find the route with the max bandwidth, done via an adapted Dijkstra
 (also usable with OLSRv2).

 The problem with this metric is that it does not give an upperbound on the
 number of hops (indeed optimal routes may have unlimited hop count via
 loops), and in general it is better to use it with a lexicographical
 metric (bandwidth,hop-count) so that the optimal route will be the route
 with the min hop count among the routes with the largest bandwidth.

 Everything is computable via Dijkstra since (shortest path on links above
 bandwidth threshold).

 -------------------------------------------------------------------------

-- 
-----------------------------------+------------------------------
 Reporter:  [email-masked]  |       Owner:  Charlie Perkins
     Type:  enhancement            |      Status:  new
 Priority:  minor                  |   Milestone:
Component:  dymo                   |     Version:
 Severity:  Active WG Document     |  Resolution:
 Keywords:  nondecreasing metrics  |
-----------------------------------+------------------------------

Ticket URL: <http://trac.tools.ietf.org/wg/manet/trac/ticket/13#comment:1>
manet <http://tools.ietf.org/manet/>

---

From: "manet issue tracker" <[email-masked]>
Date: Tue, 25 Jun 2013 04:00:54 -0000

On 1/10/2013 8:58 AM, Abdussalam Baryun wrote:

 The AODVv2 insures the loop free as described in; In draft-dymo-25, page
 16

 or see the message on the list;
 http://www.ietf.org/mail-archive/web/manet/current/msg14316.html

 The abovementioned passages depend on the strict monotonicity of the
 metric, and will fail in general if the metric allows some links with zero
 cost (which can happen if the condition is relaxed to simply monotonic
 nondecreasing),

Ticket URL: <http://trac.tools.ietf.org/wg/manet/trac/ticket/13#comment:2>
manet <http://tools.ietf.org/manet/>

---

From: "Charles E. Perkins" <[email-masked]>
Date: Mon, 24 Jun 2013 21:03:03 -0700

Hello folks,

In the absence of a convincing use case for enabling nondecreasing metrics,
and in view of the problems to insure loop freedom, I think it is safe to
close this issue without enabling the feature.

Regards,
Charlie P.

-- 
Regards,
Charlie P.