Mobile Ad hoc Networking (MANET)                             C. Dearlove
Internet-Draft                                           BAE Systems ATC
Intended status: Informational                                T. Clausen
Expires: January 7, 2013                LIX, Ecole Polytechnique, France
                                                              P. Jacquet
                                                Alcatel-Lucent Bell Labs
                                                            July 6, 2012


  Link Metrics for the Mobile Ad Hoc Network (MANET) Routing Protocol
                           OLSRv2 - Rationale
                    draft-dearlove-olsrv2-metrics-06

Abstract

   This document describes the rationale for and design considerations
   behind how link metrics are included in OLSRv2, in order to allow
   routing by other than minimum hop count routes.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on January 7, 2013.

Copyright Notice

   Copyright (c) 2012 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of



Dearlove, et al.         Expires January 7, 2013                [Page 1]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

   This document may contain material from IETF Documents or IETF
   Contributions published or made publicly available before November
   10, 2008.  The person(s) controlling the copyright in some of this
   material may not have granted the IETF Trust the right to allow
   modifications of such material outside the IETF Standards Process.
   Without obtaining an adequate license from the person(s) controlling
   the copyright in such materials, this document may not be modified
   outside the IETF Standards Process, and derivative works of it may
   not be created outside the IETF Standards Process, except to format
   it for publication as an RFC or to translate it into languages other
   than English.

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  5
   3.  Applicability  . . . . . . . . . . . . . . . . . . . . . . . .  6
   4.  Motivational Scenarios . . . . . . . . . . . . . . . . . . . .  7
   5.  Link Metrics . . . . . . . . . . . . . . . . . . . . . . . . .  9
     5.1.  Link Metric Properties . . . . . . . . . . . . . . . . . .  9
     5.2.  Link Metric Types  . . . . . . . . . . . . . . . . . . . . 10
     5.3.  Directional Link Metrics . . . . . . . . . . . . . . . . . 11
     5.4.  Reporting Link and Neighbor Metrics  . . . . . . . . . . . 12
     5.5.  Defining Incoming Link Metrics . . . . . . . . . . . . . . 13
     5.6.  Link Metric Values . . . . . . . . . . . . . . . . . . . . 14
   6.  MPRs with Link Metrics . . . . . . . . . . . . . . . . . . . . 16
     6.1.  Flooding MPRs  . . . . . . . . . . . . . . . . . . . . . . 16
     6.2.  Routing MPRs . . . . . . . . . . . . . . . . . . . . . . . 18
     6.3.  Relationship Between MPR Sets  . . . . . . . . . . . . . . 21
   7.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 23
   8.  Security Considerations  . . . . . . . . . . . . . . . . . . . 24
   9.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 25
   10. Informative References . . . . . . . . . . . . . . . . . . . . 26
   Appendix A.  MPR Routing Property  . . . . . . . . . . . . . . . . 27














Dearlove, et al.         Expires January 7, 2013                [Page 2]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


1.  Introduction

   The Optimized Link State Routing Protocol version 1 (OLSRv1)
   [RFC3626] is a proactive routing protocol for Mobile Ad hoc NETworks
   (MANETs) [RFC2501].  OLSRv1 finds shortest, defined as minimum number
   of hops, routes from a router to all possible destinations.

   Using only minimum hop routes may result in what are, in practice,
   inferior routes.  Some examples are given in Section 4.  Thus, one of
   the distinguishing features of the Optimized Link State Routing
   Protocol version 2 (OLSRv2) [OLSRv2] is the introduction of the
   ability to select routes using link metrics other than the number of
   hops.

   OLSRv2 essentially first determines local link metrics from 1-hop
   neighbors, these being defined by a process outside OLSRv2, then
   distributes required link metric values in HELLO and TC messages, and
   then finally forms routes with minimum total link metric.  Using a
   definition of route metric other than number of hops is a natural
   extension that is commonly used in link state protocols.

   Use of the extensible message format [RFC5444] by OLSRv2 has allowed
   the addition, by OLSRv2, of link metric information to the HELLO
   messages defined in the MANET NeighborHood Discovery Protocol (NHDP)
   [RFC6130] as well as inclusion in the Topology Control (TC) messages
   defined in [OLSRv2].

   A metric-based route selection processes for OLSRv2 could have been
   handled as an extension to OLSRv2.  However in this case, legacy
   OLSRv2 routers, which would not recognize any link metric
   information, would still attempt to use minimum hop-count routes.
   This would mean that, in effect, routers differed over their
   valuation of links and routes.  This would have led to the
   fundamental routing problem of "looping".  Thus if metric-based route
   selection were to have been considered only as an extension to
   OLSRv2, then routers which did, and routers which did not, implement
   the extension would not have been able to interoperate.  This would
   have been a significant limitation of such an extension.  Link
   metrics were therefore included as standard in OLSRv2.

   This document discusses the motivation and design rationale behind
   how link metrics were included in OLSRv2.  The principal issues
   involved when including link metrics in OLSRv2 were:

   o  Assigning metrics to links involved considering separate metrics
      for the two directions of a link, with the receiving router
      determining the metric from transmitter to receiver.  A metric
      used by OLSRv2 may be either of:



Dearlove, et al.         Expires January 7, 2013                [Page 3]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


      *  A link metric, the metric of a specific link from an OLSRv2
         interface of the transmitting router to an OLSRv2 interface of
         the receiving router.

      *  A neighbor metric, the minimum of the link metrics between two
         OLSRv2 routers, in the indicated direction.

      These metrics are necessarily the same when these routers each
      have a single OLSRv2 interface, but may differ when either has
      more.  HELLO messages may include both link metrics and neighbor
      metrics.  TC messages include only neighbor metrics.

   o  Metrics as used in OLSRv2 were defined to be dimensionless and
      additive.  The assignment of metrics, including their relationship
      to real parameters such as bandwidth, loss rate and delay, is
      outside the scope of OLSRv2, which simply uses these metrics in a
      consistent manner.  However by use of a registry of metric types
      (employing extended types of a single address block TLV type),
      routers can use only metrics of the physical type that they are
      configured to use.

   o  The separation of the two functions performed by MPRs in OLSRv1,
      optimized flooding and reduced topology advertisement for routing,
      into separate sets of MPRs in OLSRv2 [OLSRv2], denoted "flooding
      MPRs" and "routing MPRs".  Flooding MPRs can be calculated as in
      [RFC3626], but the use of link metrics in OLSRv2 can improve the
      MPR selection.  Routing MPRs need a metric-aware selection
      algorithm.  The selection of routing MPRs guarantees the use of
      minimum distance routes using the chosen metric, while using only
      symmetric 2-hop neighborhood information from HELLO messages and
      routing MPR selector information from TC messages.

   o  The protocol Information Bases defined in OLSRv2 include required
      metric values.  This has included additions to the protocol
      Information Bases defined in NHDP [RFC6130] when used by OLSRv2.
















Dearlove, et al.         Expires January 7, 2013                [Page 4]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


2.  Terminology

   All terms introduced in [RFC5444], including "message" and "TLV", are
   to be interpreted as described there.

   All terms introduced in [RFC6130], including "MANET Interface",
   "HELLO message", "heard", "link", symmetric link", "1-hop neighbor",
   "symmetric 1-hop neighbor", "2-hop neighbor", "symmetric 2-hop
   neighbor", and "symmetric 2-hop neighborhood", are to be interpreted
   as described there.

   All terms introduced in [OLSRv2], including "router", "OLSRv2
   interface", "willingness", "MultiPoint Relay (MPR)", "MPR selector",
   and "MPR flooding" are to be interpreted as described there.





































Dearlove, et al.         Expires January 7, 2013                [Page 5]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


3.  Applicability

   The objective of this document is to retain the design considerations
   behind how link metrics were included in [OLSRv2].  The document does
   not prescribe any behavior, but explains some aspects of the
   operation of OLSRv2.













































Dearlove, et al.         Expires January 7, 2013                [Page 6]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


4.  Motivational Scenarios

   The basic situation that suggests the desirability of use of routes
   other than minimum hop routes is shown in Figure 1.

                             A ----- X ----- B
                              \             /
                               \           /
                                Y ------- Z

                                 Figure 1

   The minimum hop route from A to B is via X. However if the links A to
   X and X to B are poor (e.g., having low bandwidth or being
   unreliable) but the links A to Y, Y to Z and Z to B are better (e.g.,
   having reliable high bandwidth) then the route A to B via Y and Z may
   be preferred to that via X.

   There are other situations where, even if the avoidance of some links
   do not show immediately obvious benefits to users, their use should
   be discouraged.  Consider a network with many short range links, and
   a few long range links.  Use of minimum hop routes will immediately
   lead to heavy use of the long range links.  This will be particularly
   undesirable if those links achieve their longer range through reduced
   bandwidth, or through being less reliable.  However, even if the long
   range links have the same characteristics as the short range links,
   it may be better to reserve usage of the long range links for when
   this usage is particularly valuable - for example when the use of one
   long range link saves several short range links, rather than the
   single link saving that is all that is needed for a minimum hop
   route.

   A related case is that of a privileged relay.  An example is an
   aerial router in an otherwise ground based network.  The aerial
   router may have a link to many, or even all, other routers.  That
   would lead to all routers attempting to send all their traffic (other
   than to symmetric 1-hop neighbors and some symmetric 2-hop neighbors)
   via the aerial router.  It may however be important to reserve that
   capacity for cases where the aerial router is actually essential,
   such as if the ground based portion of the network is not connected.

   Other cases may involve attempts to avoid areas of congestion, to
   route around insecure routers (by preference, but prepared to use
   them if there is no other alternative) and routers attempting to
   discourage their use as relays due to, for example, limited battery
   power.  OLSRv2 does have another mechanism to aid in this, a router's
   willingness to act as an MPR.  However there are cases where that
   cannot help, but where use of non-minimum hop routes could.



Dearlove, et al.         Expires January 7, 2013                [Page 7]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


   Similarly note that OLSRv2's optional use of link quality (through
   its use of [RFC6130]) is not a solution to these problems.  Use of
   link quality as specified in [RFC6130] allows a router to decline to
   use a link, not only on its own, but on all routers' behalf.  It does
   not, for example, allow the use of a link otherwise determined to be
   too low quality to be generally useful, as part of a route where no
   better links exist.  These mechanisms (link quality and link metrics)
   solve distinctly different problems.

   It should also be noted that the loop-free property of OLSRv2 applies
   strictly only in the static state.  When the network topology is
   changing, and with possibly lossy messages, it is possible for
   transient loops to form.  However with update rates appropriate to
   the rate of topology change, such loops will be sufficiently rare.
   Changing link metrics is a form of network topology change, and
   should be limited to a rate slower than the message information
   update rate (defined by the parameters HELLO_INTERVAL,
   HELLO_MIN_INTERVAL, REFRESH_INTERVAL, TC_INTERVAL and
   TC_MIN_INTERVAL).
































Dearlove, et al.         Expires January 7, 2013                [Page 8]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


5.  Link Metrics

   This section describes the required and selected properties of the
   link metrics used in OLSRv2, followed by implementation details
   achieving those properties.

5.1.  Link Metric Properties

   Link metrics in OLSRv2 are:

   o  Dimensionless.  While they may, directly or indirectly, correspond
      to specific physical information (such as delay, loss rate or
      bandwidth), this knowledge is not used by OLSRv2.  Instead,
      generating the metric value is the responsibility of a mechanism
      external to OLSRv2.

   o  Additive, so that the metric of a route is the sum of the metrics
      of the links forming that route.  Note that this requires a metric
      where a low value of a link metric indicates a "good" link and a
      high value of a link metric indicates a "bad" link, where the
      former will be preferred to the latter.

   o  Directional, the metric from router A to router B need not be the
      same as the metric from router B to router A, even when using the
      same OLSRv2 interfaces.  At router A, a link metric from router B
      to router A is referred to as an incoming link metric, while a
      link metric from router A to router B is referred to as an
      outgoing link metric.  (These are, of course, reversed at router
      B.)

   o  Specific to a pair of OLSRv2 interfaces, so that if there is more
      than one link from router A to router B, each has its own link
      metric in that direction.  There is also be an overall metric, a
      "neighbor metric", from router A to router B (its 1-hop neighbor).
      This is the minimum value of the link metrics from router A to
      router B, considering symmetric links only; it is undefined if
      there are no such symmetric links.  A neighbor metric from one
      router to another is always equal to a link metric in the same
      direction between OLSRv2 interfaces of those routers.  When
      referring to a specific OLSRv2 interface (for example in a Link
      Tuple or a HELLO message sent on that OLSRv2 interface) a link
      metric always refers to a link on that OLSRv2 interface, to or
      from the indicated 1-hop neighbor OLSRv2 interface, while a
      neighbor metric may be equal to a link metric to and/or from
      another OLSRv2 interface.






Dearlove, et al.         Expires January 7, 2013                [Page 9]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


5.2.  Link Metric Types

   There are various physical characteristics that may be used to define
   a link metric.  Some examples, which also illustrate some
   characteristics of metrics that result, are:

   o  Delay is a straightforward metric, as it is naturally additive,
      the delay of a multi-link route is the sum of the delays of the
      links.  (This does not directly take into account delays due to
      routers, rather than links, but these can be divided among
      incoming and outgoing links.)  However, given a limited range of
      link metric value, more than one type of delay metric may be
      required, representing different ranges of delay value.

   o  Probability of loss on a link is, as long as probabilities of loss
      are small and independent, approximately additive.  (A slightly
      more accurate approach is using a negatively scaled logarithm of
      the probability of not losing a packet.)  If losses are not
      independent then this will be pessimistic.  Again, more than one
      range of values (or more than one scaling of the logarithms) may
      be needed.

   o  Bandwidth is not additive, it even has the wrong characteristic of
      being good when high, bad when low; thus a mapping that inverts
      its ordering must be applied.  Such a mapping can, at best, only
      produce a metric that it is acceptable to treat as additive.
      Consider, for example, a preference for a route that maximizes the
      minimum bandwidth link on the route, and then prefers a route with
      the fewest links of each bandwidth from the lowest.  If links may
      be of three discrete bandwidths, "high", "medium" and low", then
      this preference can be achieved, on the assumption that no route
      will have more than 10 links, with metric values of 1, 10 and 100
      for the three bandwidths.  If routes can have more than 10 links,
      the range of metrics must be increased; this indicates a
      preference for a wide "dynamic range" of link metric values.
      Depending on the ratios of the numerical values of the three
      bandwidths, the same effect may be achieved by using a scaling of
      an inverse power of the numerical values of the bandwidths.  For
      example if the three bandwidths were 2, 5 and 10 Mbit/s, then a
      possible mapping would be the fourth power of 10 Mbit/s divided by
      the bandwidth, giving metric values of 625, 16 and 1 (good for up
      to 16 links in a route).  This mapping can be extended to a system
      with more bandwidth values, for example giving a 4 Mbit/s
      bandwidth a metric value of about 39.  This may lose the
      capability to produce an absolutely maximum minimum bandwidth
      route, but will usually produce either that, or something close
      (and at times maybe better, is a route of three 5 Mbit/s links
      really better than one of a single 4 Mbit/s link?)  Specific



Dearlove, et al.         Expires January 7, 2013               [Page 10]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


      metrics will need to define the mapping (e.g., a power and
      bandwidth scaling).

   There are also many other possible metrics, including physical layer
   information (such as signal to noise ratio, and error control
   statistics) and information such as packet queuing statistics.

   In a well-designed network, all routers will use the same physical
   metric type.  It will not produce good routes if, for example, some
   link metrics are based on bandwidth and some on path loss (except to
   the extent that these may be correlated).  How to achieve this is an
   administrative matter, outside the scope of OLSRv2.  In fact even the
   actual physical meanings of the metrics is outside the scope of
   OLSRv2.  This is because new metrics may be added in the future, for
   example as bandwidths increase, and may be based on new, possibly
   non-physical, considerations, for example financial cost.  Each such
   type will have a metric type number.  Initially a single link metric
   type zero is defined as indicating a dimensionless metric with no
   predefined physical meaning.

   An OLSRv2 router is instructed which single link metric type to use
   and recognize, without knowing whether it represents delay,
   probability of loss, bandwidth, cost or any other quantity.  This
   recognized link metric type number is a router parameter, and subject
   to change in case of reconfiguration, or possibly the use of a
   protocol (outside the scope of OLSRv2) permitting a process of link
   metric type agreement between routers.

   The use of link metric type numbers also suggests the possibility of
   use of multiple link metric types and multiple network topologies.
   This is a possible future extension to OLSRv2.  To allow for that
   future possibility, the sending of more than one metric, of different
   physical types, which should otherwise not be done for reasons of
   efficiency, is not prohibited, but types other than that configured
   will be ignored.

   The following three sections assume a chosen single link metric type,
   of unspecified physical nature.

5.3.  Directional Link Metrics

   OLSRv2 uses only "symmetric" (bidirectional) links, which may carry
   traffic in either direction.  A key decision was whether these links
   should each be assigned a single metric, used in both directions, or
   a metric in each direction, noting that:






Dearlove, et al.         Expires January 7, 2013               [Page 11]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


   o  Links can have different characteristics in each direction, use of
      directional link metrics recognizes this.

   o  In many (possibly most) cases, the two ends of a link will
      naturally form different views as to what the link metric should
      be.  To use a single link metric requires a coordination between
      the two that can be avoided if using directional metrics.  Note
      that if using a single metric, it would be essential that the two
      ends agree as to its value, otherwise it is possible for looping
      to occur.  This problem does not occur for directional metrics.

   Based on these considerations, directional metrics are used in
   OLSRv2.  Each router must thus be responsible for defining the metric
   in one direction only.  This could have been in either direction,
   i.e., that a router is responsible for either incoming or outgoing
   link metrics, as long as the choice is universal.  The former
   (incoming) case is used in OLSRv2 because, in general, receiving
   routers have more information available to determine link metrics
   (for example received signal strength, interference levels, and error
   control coding statistics).

   Note that, using directional metrics, if router A defines the metric
   of the link from router B to router A, then router B must use router
   A's definition of that metric on that link in that direction.
   (Router B could, if appropriate, use a bad mismatch between
   directional metrics as a reason to discontinue use of this link,
   using the link quality mechanism in [RFC6130].)

5.4.  Reporting Link and Neighbor Metrics

   Links, and hence link metrics, are reported in HELLO messages.  A
   router must report incoming link metrics in its HELLO messages in
   order that these are each available at the other end of the link.
   This means that, for a symmetric link, both ends of the link will
   know both of the incoming and outgoing link metrics.

   As well as advertising incoming link metrics, HELLO messages also
   advertise incoming neighbor metrics.  These are used for routing MPR
   selection (see Section 6.2), which requires use of the lowest metric
   link between two routers when more than one link exists.  This
   neighbor metric may be using another OLSRv2 interface, and hence the
   link metric alone is insufficient.

   Metrics are also reported in TC messages.  It can be shown that these
   need to be outgoing metrics:

   o  Router A must be responsible for advertising a metric from router
      A to router B in TC messages.  This can be seen by considering a



Dearlove, et al.         Expires January 7, 2013               [Page 12]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


      route connecting single OLSRv2 interface routers P to Q to R to S.
      Router P receives its only information about the link from R to S
      in the TC messages transmitted by router R, which is an MPR of
      router S (assuming that only MPR selectors are reported in TC
      messages).  Router S may not even transmit TC messages (if no
      routers have selected it as an MPR and it has no attached networks
      to report).  So any information about the metric of the link from
      R to S must also be included in the TC messages sent by router R,
      hence router R is responsible for reporting the metric for the
      link from R to S.

   o  In a more general case, where there may be more than one link from
      R to S, the TC message must, in order that minimum metric routes
      can be constructed (e.g., by router P) report the minimum of these
      outgoing link metrics, i.e., the outgoing neighbor metric from R
      to S.

   In this example, router P also receives information about the
   existence of a link between Q and R in the HELLO messages sent by
   router Q. Without the use of metrics, this link may be used by OLSRv2
   for two hop routing to router R using just HELLO messages sent by
   router Q. For this property (which accelerates local route formation)
   to be retained (from OLSRv1) router P must receive the metric from Q
   to R in HELLO messages sent by router Q. This indicates that router Q
   must be responsible for reporting the metric for the outgoing link
   from Q to R. This is in addition to the incoming link metric
   information that a HELLO message must report.  Again, in general,
   this must be the outgoing neighbor metric, rather than the outgoing
   link metric.

   In addition, Section 6.1 offers an additional reason for reporting
   outgoing neighbor metrics in HELLO messages, without which metrics
   can properly affect only routing, not flooding.

   Note that there is no need to report an outgoing link metric in a
   HELLO message.  The corresponding 1-hop neighbor knows that value, it
   specified it, and for 2-hop neighborhood use neighbor metrics are
   required (as these will, in general, not use the same OLSRv2
   interface).

5.5.  Defining Incoming Link Metrics

   When a router reports a 1-hop neighbor in a HELLO message it may do
   so for the first time with link status HEARD.  The receiving router
   will then immediately consider the link to be symmetric and thus will
   use it.

   As the router is responsible for defining and reporting incoming link



Dearlove, et al.         Expires January 7, 2013               [Page 13]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


   metrics, it must evaluate that metric, and attach that link metric to
   the appropriate address (which will have link status HEARD) in the
   next HELLO message reporting that address on that OLSRv2 interface.
   There will, at this time, be no outgoing link metric available to
   report.

   Thus a router must be able to immediately decide on an incoming link
   metric once it has heard a 1-hop neighbor on an OLSRv2 interface for
   the first time.  This is because, on receiving a HELLO message from
   this router, that 1-hop neighbor will (unless link quality indicates
   otherwise) immediately consider the link to be symmetric and use it.
   It may, depending on the physical nature of the link metric, be too
   early for an ideal decision as to that metric, however a choice must
   be made.  The metric value may later be refined based on further
   observation of HELLO messages, other message transmissions between
   the routers, or other observations of the environment.  It will
   probably be best to over-estimate the metric if initially uncertain
   as to its value, to discourage, rather than over-encourage, its use.
   If no information other than the receipt of the HELLO message is
   available, then a conservative maximum link metric value, in [OLSRv2]
   denoted MAXIMUM_METRIC, should be used.

5.6.  Link Metric Values

   Link metric values are recorded in LINK_METRIC TLVs, defined in
   [OLSRv2], using a compressed representation that occupies 12 bits.
   The use of 12 bits is convenient because, when combined with 4 flag
   bits of additional information, described below, this produced a 2
   octet value field.  However the use of 12 bits was a result from a
   design to use a modified exponent/mantissa form with the following
   characteristics:

   o  The values represented are to be positive integers starting 1, 2,
      ...

   o  The maximum value represented should be close to, but less than
      2^24 (^ denotes exponentiation in this section).  This is so that
      with a route limited to no more than 255 hops, the maximum route
      metric is less than 2^32, i.e., can be stored in 32 bits.  (The
      link metric value can be stored in 24 bits.)

   A representation, modified from an exponent/mantissa form with e bits
   of exponent and m bits of mantissa, and which has the first of these
   properties is one that starts at 1, then is incremented by 1 up to
   2^m, then has a further 2^m increments by 2, then a further 2^m
   increments by 4, and so on for 2^e sets of increments.

   The position in the increment sequence, from 0 to 2^m-1, is



Dearlove, et al.         Expires January 7, 2013               [Page 14]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


   considered as a form of mantissa, and denoted b.  The increment
   sequence number, from 0 to 2^e-1, is considered as a form of
   exponent, and denoted a.

   The value represented by (a,b) can then be shown to be equal to (2^m+
   b+1)2^a-2^m.  To verify this, note that:

   o  With fixed a, the difference between two values with consecutive
      values of b is 2^a, as expected.

   o  The value represented by (a,2^m-1) is (2^m+2^m)2^a-2^m.  The value
      represented by (a+1,0) is (2^m+1)(2^(a+1))-2^m.  The difference
      between these two values is 2^(a+1), as expected.

   The maximum represented value has a = 2^e-1 and b = 2^m-1, and is
   (2^m+2^m)(2^(2^e-1))-2^m = 2^(2^e+m)-2^m.  This is slightly less than
   2^(2^e+m).  The required 24 bit limit can be achieved if 2^e+m = 24.
   An appropriate pair of values to achieve this is e = 4, m = 8.

   As noted above, the 12 bit representation shares two octets with 4
   flag bits.  Putting the flag bits first, it is then natural to put
   the exponent bits in the last four bits of the first octet, and to
   put the mantissa bits in the second octet.  The 12 consecutive bits,
   using normal network octet ordering (high first) then represent
   256a+b.  Note that the ordering of these 12 bit representation values
   is the same as the ordering of the 24 bit metric values.  In other
   words two 12 bit metrics fields can be compared for equality/ordering
   as if they were unsigned integers.

   The four flag bits each represent one kind of metric, defined by its
   direction (incoming or outgoing) and whether the metric is a link
   metric or a neighbor metric.  As indicated by the flag bits set, a
   metric value may be of any combination of these four kinds of metric.


















Dearlove, et al.         Expires January 7, 2013               [Page 15]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


6.  MPRs with Link Metrics

   MPRs are used for two purposes in OLSRv2.  In both cases it is MPR
   selectors that are actually used, MPR selectors being determined from
   MPRs advertised in HELLO messages.

   o  Optimized Flooding.  This uses the MPR selector status of
      symmetric 1-hop neighbor routers from which messages are received
      in order to determine if these messages are to be forwarded.  MPR
      selector status is recorded in the Neighbor Set (defined in
      [RFC6130] and extended in [OLSRv2]), and determined from received
      HELLO messages.

   o  Routing.  Non-local link information is based on information
      recorded in this router's Topology Information Base.  That
      information is based on received TC messages.  The neighbor
      information in these TC messages consists of addresses of the
      originating router's advertised (1-hop) neighbors, as recorded in
      that router's Neighbor Set (defined in [RFC6130] and extended in
      [OLSRv2]).  These advertised neighbors include all of the MPR
      selectors of the originating router.

   Metrics interact with these two uses of MPRs differently, as
   described in the following two sections, and which leads to the
   requirement for two separate sets of MPRs for these two uses when
   using metrics.  The relationship between these two sets of MPRs is
   considered in Section 6.3.

6.1.  Flooding MPRs

   MPR selection for flooding can ignore metrics.  Selection using any
   algorithm that ignores metrics, including any allowed by [OLSRv2],
   will produce a flooding solution that works.

   However, that does not mean that metrics cannot be usefully
   considered in selecting such "flooding MPRs".  Consider the network
   in Figure 2, where numbers are metrics of links in the direction away
   from router A, towards router D.

                                     3
                                 A ----- B
                                 |       |
                               1 |       | 1
                                 |       |
                                 C ----- D
                                     4

                                 Figure 2



Dearlove, et al.         Expires January 7, 2013               [Page 16]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


   Which is the better flooding MPR selection by router A: B or C?  If
   the metric represents probability of message loss, then clearly
   choosing B maximizes the probability of a message sent by A reaching
   D. This is despite that C has a lower metric in its connection to A
   than B does.  (Similar arguments about a preference for B can be made
   if, for example, the metric represents bandwidth or delay rather than
   probability of loss.)

   However, neither should only the second hop be considered.  If this
   example is modified to that in Figure 3, where the numbers still are
   metrics of links in the direction away from router A, towards router
   D:

                                     3
                                 A ----- B
                                 |       |
                               1 |       | 3
                                 |       |
                                 C ----- D
                                     4

                                 Figure 3

   then it is possible that, when A is selecting flooding MPRs,
   selecting C is preferable to selecting B. If the metrics represent
   scaled values of delay, or the probability of loss, then selecting C
   is clearly better.  This indicates that the sum of metrics is an
   appropriate measure to use to choose between B and C.

   However, this is a particularly simple example.  Usually it is not a
   simple choice between two routers as a flooding MPR, each only adding
   one router coverage.  A more general process, when considering which
   router to next add as a flooding MPR, should incorporate the metric
   to that router, and the metric from that router to each symmetric
   2-hop neighbor, as well as the number of newly covered symmetric
   2-hop neighbors as well as the other factors used in the example
   algorithm in [OLSRv2].

   A candidate algorithm for flooding MPR selection is described in
   [OLSRv2].  However, note that in [OLSRv2] (as in [RFC3626]), each
   router can make its own independent choice of flooding MPRs, and
   flooding MPR selection algorithms, and still interoperate.

   Also note that the references above to the direction of the metrics
   is correct: for flooding, directional metrics outward from a router
   are appropriate, i.e., metrics in the direction of the flooding.
   This is an additional reason for including outward metrics in HELLO
   messages, as otherwise a metric-aware MPR selection for flooding is



Dearlove, et al.         Expires January 7, 2013               [Page 17]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


   not possible.  The second hop metrics are outgoing neighbor metrics
   because the OLSRv2 interface used for a second hop transmission may
   not be the same as that used for the first hop reception.

6.2.  Routing MPRs

   The essential detail of the MPR selection specification in [OLSRv2]
   is that a router must, per OLSRv2 interface, select a set of MPRs
   such that there is a two hop route from each symmetric 2-hop neighbor
   of the selecting router to the selecting router, with the
   intermediate router on each such route being an MPR of the selecting
   router.

   It is sufficient, when using an additive link metric rather than a
   hop count, to require that these "routing MPRs" provide not just a
   two hop route, but a minimum distance two hop route.  In addition, a
   router is a symmetric 2-hop neighbor even if it is a symmetric 1-hop
   neighbor, as long as there is a two hop route from it that is shorter
   than the one hop link from it.  (The property that no routes go
   through routers with willingness WILL_NEVER is retained.  Examples
   below assume that all routers are equally willing, with none having
   willingness WILL_NEVER.)

   For example, consider the network in Figure 4.  Numbers are metrics
   of links in the direction towards router A, away from router D.
   Router A must pick router B as a routing MPR, whereas for minimum hop
   count routing it could alternatively pick router C. Note that the use
   of incoming neighbor metrics in this case follows the same reasoning
   as for the directionality of metrics in TC messages, as described in
   Section 5.4.

                                     2
                                 A ----- B
                                 |       |
                               1 |       | 1
                                 |       |
                                 C ----- D
                                     3

                                 Figure 4

   In Figure 5, where numbers are metrics of links in the direction
   towards router A, away from router C, router A must pick router B as
   a routing MPR, but for minimum hop count routing it would not need to
   pick any MPRs.






Dearlove, et al.         Expires January 7, 2013               [Page 18]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


                                     1
                                   A - B
                                    \  |
                                   4 \ | 2
                                      \|
                                       C

                                 Figure 5

   In Figure 6, where numbers are metrics of links in the direction
   towards router A, away from routers D and E, router A must pick both
   routers B and C as routing MPRs, but for minimum hop count routing it
   could pick either.

                                D        E
                                |\      /|
                                | \ 3  / |
                                |  \  /  |
                              1 |   \/   | 1
                                |   /\   |
                                |  /  \  |
                                | / 2  \ |
                                |/      \|
                                B        C
                                 \       |
                                  \     /
                                 3 \   / 2
                                    \ /
                                     A

                                 Figure 6

   It is shown in Appendix A that selecting routing MPRs according to
   this definition, and advertising only such links (plus knowledge of
   local links from HELLO messages), will result in selection of lowest
   total metric routes, even if all links (advertised or not) are
   considered in the definition of a shortest route.

   However the definition noted above as sufficient for routing MPR
   selection is not necessary.  For example, consider the network in
   Figure 7, where numbers are metrics of links in the direction towards
   router A, away from other routers; the metrics from B to C and C to B
   are both assumed to be 2.








Dearlove, et al.         Expires January 7, 2013               [Page 19]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


                                 1
                             A ----- B
                              \     /
                             4 \   / 2
                                \ /
                                 C ----- D ----- E
                                     3       5

                                 Figure 7

   Using the above definition, A must pick both B and C as routing MPRs,
   in order to cover the symmetric 2-hop neighbors C and D,
   respectively.  (C is a symmetric 2-hop neighbor because the route
   length via B is shorter than the 1-hop link.)

   However, A only needs to pick B as a routing MPR, because the only
   reason to pick C as a routing MPR would be so that C can advertise
   the link to A for routing - to be used by, for example, E. But A
   knows that no other router should use the link C to A in a shortest
   route, because routing via B is shorter.  So if there is no need to
   advertise the link from C to A, then there is no reason for A to
   select C as a routing MPR.

   This process of "thinning out" the routing MPR selection uses only
   local information from HELLO messages.  Using any minimum distance
   algorithm, the router identifies shortest routes, whether one, two or
   more hops, from all routers in its symmetric 2-hop neighborhood.  It
   then selects as MPRs all symmetric 1-hop neighbors that are the last
   router (before the selecting router itself) on any such route.  Where
   there is more than one shortest distance route from a router, only
   one such route is required.  Alternative routes may be selected so as
   to minimize the number of last routers - this is the equivalent to
   the selection of a minimal set of MPRs in the non-metric case.

   Note that this only removes routing MPRs whose selection can be
   directly seen to be unnecessary.  Consequently if (as is shown in
   Appendix A) the first approach creates minimum distance routes, then
   so does this process.

   The examples in Figure 5 and Figure 6 show that use of link metrics
   may require a router to select more routing MPRs than when not using
   metrics, and even require a router to select routing MPRs when
   without metrics it would not need any routing MPRs.  This may result
   in more, and larger, messages being generated, and forwarded more
   often.  Thus the use of link metrics is not without cost, even
   excluding the cost of link metric signaling.

   These examples consider only single OLSRv2 interface routers.



Dearlove, et al.         Expires January 7, 2013               [Page 20]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


   However if routers have more than one OLSRv2 interface, then the
   process is unchanged, other than that if there is more than one known
   metric between two routers (on different OLSRv2 interfaces), then,
   considering symmetric links only (as only these are used for routing)
   the smallest link metric, i.e., the neighbor metric, is used.  There
   is no need to calculate routing MPRs per OLSRv2 interface.  That
   requirement results from the consideration of flooding and the need
   to avoid certain "race" conditions, which are not relevant to
   routing, only to flooding.

   A candidate algorithm for routing MPR selection is described in
   [OLSRv2].  However, note that in [OLSRv2] (as in [RFC3626]), each
   router can make its own independent choice of routing MPRs, and
   routing MPR selection algorithms, and still interoperate.

6.3.  Relationship Between MPR Sets

   It would be convenient if the two sets of flooding and routing MPRs
   were the same.  This can be the case if all metrics are equal, but in
   general, for "good" sets of MPRs they are not.  (A reasonable
   definition of this is that there is no common minimal set of MPRs.)
   If metrics are asymmetrically valued (the two sets of MPRs use
   opposite direction metrics), or routers have multiple OLSRv2
   interfaces (where routing MPRs can ignore this, but flooding MPRs
   cannot) this is particularly unlikely.  However even using a
   symmetrically valued metric with a single OLSRv2 interface on each
   router, the ideal sets need not be equal, nor is one always a subset
   of the other.  To show this, consider these examples, where all
   lettered routers are assumed equally willing to be MPRs, and numbers
   are bidirectional metrics for links.

   In Figure 8, A does not require any flooding MPRs.  However A must
   select B as a routing MPR.

                                     1
                                   A - B
                                    \  |
                                   4 \ | 2
                                      \|
                                       C

                                 Figure 8

   In Figure 9, A must select C and D as routing MPRs.  However A's
   minimal set of flooding MPRs is just B. In this example the set of
   routing MPRs serves as a set of flooding MPRs, but a non-minimal one
   (although one that might be better, depending on the relative
   importance of number of MPRs and flooding link metrics).



Dearlove, et al.         Expires January 7, 2013               [Page 21]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


                                       2
                                    C --- E
                                   /     /
                                1 /     / 1
                                 /  4  /
                                A --- B
                                 \     \
                                1 \     \ 1
                                   \     \
                                    D --- F
                                       2

                                 Figure 9

   However, this is not always the case.  In Figure 10, A's set of
   routing MPRs must contain B, but need not contain C. A's set of
   flooding MPRs need not contain B, but must contain C. (In this case,
   flooding with A selecting B rather than C as a flooding MPR will
   reach D, but in three hops rather than the minimum two that MPR
   flooding guarantees.)

                                   2   1
                                 B - C - D
                                 |  /
                               1 | / 4
                                 |/
                                 A

                                 Figure 10






















Dearlove, et al.         Expires January 7, 2013               [Page 22]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


7.  IANA Considerations

   This document has no actions for IANA.

   This section may be removed by the RFC Editor.














































Dearlove, et al.         Expires January 7, 2013               [Page 23]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


8.  Security Considerations

   This document does not specify any security considerations.

   This section may be removed by the RFC Editor.














































Dearlove, et al.         Expires January 7, 2013               [Page 24]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


9.  Acknowledgements

   The authors would like to gratefully acknowledge the following people
   for intense technical discussions, early reviews and comments on the
   specification and its components (listed alphabetically): Brian
   Adamson (NRL), Alan Cullen (BAE Systems), Justin Dean (NRL), Stan
   Ratliff (Cisco), Charles Perkins (Huawei), Henning Rogge (FGAN), and
   Ulrich Herberg (Fujitsu).











































Dearlove, et al.         Expires January 7, 2013               [Page 25]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


10.  Informative References

   [RFC2501]  Macker, J. and S. Corson, "Mobile Ad hoc Networking
              (MANET): Routing Protocol Performance Issues and
              Evaluation Considerations", RFC 2501, January 1999.

   [RFC3626]  Clausen, T. and P. Jacquet, "The Optimized Link State
              Routing Protocol", RFC 3626, October 2003.

   [RFC5444]  Clausen, T., Dean, J., Dearlove, C., and C. Adjih,
              "Generalized MANET Packet/Message Format", RFC 5444,
              February 2009.

   [RFC6130]  Clausen, T., Dean, J., and C. Dearlove, "Mobile Ad Hoc
              Network (MANET) Neighborhood Discovery Protocol (NHDP)",
              RFC 6130, April 2011.

   [OLSRv2]   Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized
              Link State Routing Protocol version 2",
              draft-ietf-manet-olsrv2-15.txt (work in progress),
              May 2012.






























Dearlove, et al.         Expires January 7, 2013               [Page 26]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


Appendix A.  MPR Routing Property

   In order that routers can find and use shortest routes in a network
   while using the minimum reduced topology supported by OLSRv2 (that a
   router only advertises its MPR selectors in TC messages), routing MPR
   selection must result in the property that there are shortest routes
   with all intermediate routers being routing MPRs.

   This appendix uses the following terminology and assumptions:

   o  The network is a graph of nodes connected by arcs, where nodes
      correspond to routers with willingness not equal to WILL_NEVER
      (except possibly at the ends of routes).  An arc corresponds to
      the set of symmetric links connecting those routers; the OLSRv2
      interfaces used by those links are not relevant.

   o  Each arc has a metric in each direction, being the minimum of the
      corresponding link metrics in that direction, i.e., the
      corresponding neighbor metric.  This metric must be positive.

   o  A sequence of arcs joining two nodes is referred to as a path.

   o  Node A is an MPR of node B, if corresponding router A is a routing
      MPR of router B.

   The required property (of using shortest routes with reduced
   topology) is equivalent to that for any pair of distinct nodes X and
   Z there is a shortest path from X to Z, X - Y1 - Y2 - ... - Ym - Z
   such that Y1 is an MPR of Y2, ...  Ym is an MPR of Z. Call such a
   path a routable path, and call this property the routable path
   property.

   The required definition for a node X selecting MPRs is that for each
   distinct node Z from which there is a two arc path, there is a
   shorter, or equally short, path which is either Z - Y - X where Y is
   an MPR of X, or is the one arc path Z - X. Note that the existence of
   locally known, shorter, but more than two arc paths, which can be
   used to reduce the numbers of MPRs, is not considered here.  (Such
   reductions are only when the remaining MPRs can be seen to retain all
   necessary shortest paths, and therefore retains the required
   property.)

   Although this appendix is concerned with paths with minimum total
   metric, not number of arcs (hop count), it proceeds by induction on
   the number of arcs in a path.  Although it considers minimum metric
   routes with a bounded number of arcs, it then allows that number of
   arcs to increase so that overall minimum metric paths, regardless of
   the number of arcs, are considered.



Dearlove, et al.         Expires January 7, 2013               [Page 27]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


   Specifically, the routable path property is a corollary of the
   property that for all positive integers n, and all distinct nodes X
   and Z, if there is any path from X to Z of n arcs or fewer, then
   there is a shortest path, from among those of n arcs or fewer, that
   is a routable path.  This may be called the n-arc routable path
   property.

   The n-arc routable path property is trivial for n = 1, and directly
   follows from the definition of the MPRs of Z for n = 2.

   Proceeding by induction, assuming the n-arc routable path property is
   true for n = k, consider the case that n = k+1.

   Suppose that X - V1 - V2 - ... - Vk - Z is a shortest k+1 arc path
   from X to Z. We construct a path which has no more than k+1 arcs, has
   the same or shorter length (hence has the same, shortest, length
   considering only paths of up to k+1 arcs, by assumption) and is a
   routable path.

   First consider whether Vk is an MPR of Z. If it is not then consider
   the two arc path Vk-1 - Vk - Z. This can be replaced either by a one
   arc path Vk-1 - Z or by a two arc path Vk-1 - Wk - Z where Wk is an
   MPR of Z, such that the metric from Vk-1 to Z by the replacement path
   is no longer.  In the former case (replacement one arc path) this now
   produces a path of length k, and the previous inductive step may be
   applied.  In the latter case we have replaced Vk by Wk, where Wk is
   an MPR of Z. Thus we need only consider the case that Vk is an MPR of
   Z.

   We now apply the previous inductive step to the path X - V1 - ... -
   Vk-1 - Vk, replacing it by an equal length path X - W1 - ...  Wm-1 -
   Vk, where m <= k, where this path is a routable path.  Then because
   Vk is an MPR of Z, the path X - W1 - ... - Wm-1 - Vk - Z is a
   routable path, and demonstrates the n-arc routable path property for
   n = k+1.

   This thus shows that for any distinct nodes X and Z, there is a
   routable path using the MPR-reduced topology from X to Z, i.e., that
   OLSRv2 finds minimum length paths (minimum total metric routes).












Dearlove, et al.         Expires January 7, 2013               [Page 28]


Internet-Draft             OLSRv2 Link Metrics                 July 2012


Authors' Addresses

   Christopher Dearlove
   BAE Systems ATC

   Phone: +44 1245 242194
   EMail: chris.dearlove@baesystems.com
   URI:   http://www.baesystems.com/


   Thomas Heide Clausen
   LIX, Ecole Polytechnique, France

   Phone: +33 6 6058 9349
   EMail: T.Clausen@computer.org
   URI:   http://www.ThomasClausen.org/


   Philippe Jacquet
   Alcatel-Lucent Bell Labs

   Phone: +33 6 7337 1880
   EMail: philippe.jacquet@alcatel-lucent.fr




























Dearlove, et al.         Expires January 7, 2013               [Page 29]