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

From: "manet issue tracker" <[email-masked]>
Date: Wed, 09 Jan 2013 22:26:47 -0000

#13: Supporting monotonically nondecreasing but non-additive metrics

 There are some useful metrics that are nondecreasing but not "naturally"
 additive.  That is, making an additive definition for them requires
 unnatural mental gymnastics.

 A good example is "1 / bandwidth".  This metric is not affected by
 higher-bandwidth links, but only by the link that has the least bandwidth
 from among all the path components of the route.  Strangely, this
 quantity does not seem to have a commonly accepted name that I can find.
 The best I can do so far is to call it the "Slowness" metric.  One
 could use the Slowness metric as a nondecreasing metric which still
 finds the fastest route.

 Supporting such metrics in AODVv2 can be done by simply
 replacing "!RteMsg.Metric + Cost(L)" by another function that
 could be called "!TotalCost (!RteMsg.Metric, Cost(L))".  The impact
 on the specification is minor (only a few lines), and the possible
 future benefit could be substantial.  For !HopCount,
 !TotalCost(!RteMsg.Metric,Cost(L)) is defined to be (!RteMsg.Metric + 1).

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

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

---

From: Abdussalam Baryun <[email-masked]>
Date: Thu, 10 Jan 2013 10:09:30 +0100

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

AB

On 1/9/13, manet issue tracker <[email-masked]> wrote:
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/manet
>

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Thu, 10 Jan 2013 09:50:01 +0000

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

-- 
Christopher Dearlove
Senior Principal Engineer, Communications Group
Communications, Networks and Image Analysis Capability
BAE Systems Advanced Technology Centre
West Hanningfield Road, Great Baddow, Chelmsford, CM2 8HN, UK
Tel: +44 1245 242194 |  Fax: +44 1245 242124
[email-masked] | http://www.baesystems.com

BAE Systems (Operations) Limited
Registered Office: Warwick House, PO Box 87, Farnborough Aerospace Centre, Farnborough, Hants, GU14 6YU, UK
Registered in England & Wales No: 1996687

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of manet issue tracker
Sent: 09 January 2013 22:27
To: [email-masked]
Cc: [email-masked]
Subject: [manet] #13: Supporting monotonically nondecreasing but non-additive metrics

----------------------! WARNING ! ----------------------
This message originates from outside our organisation,
either from an external partner or from the internet.
Keep this in mind if you answer this message.
Follow the 'Report Suspicious Emails' link on IT matters
for instructions on reporting suspicious email messages.
--------------------------------------------------------

********************************************************************
This email and any attachments are confidential to the intended
recipient and may also be privileged. If you are not the intended
recipient please delete it from your system and notify the sender.
You should not copy it or use it for any purpose nor disclose or
distribute its contents to any other person.
********************************************************************

---

From: Abdussalam Baryun <[email-masked]>
Date: Thu, 10 Jan 2013 11:30:37 +0100

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

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.

AB

On 1/10/13, Dearlove, Christopher (UK) <[email-masked]> 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.
>

---

From: Philippe Jacquet <[email-masked]>
Date: Thu, 10 Jan 2013 14:44:32 +0100 (CET)

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

Philippe

---

From: Abdussalam Baryun <[email-masked]>
Date: Thu, 10 Jan 2013 17:58:46 +0100

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

AB
On 1/10/13, Philippe Jacquet <[email-masked]> wrote:
> 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.
>