Mobile Ad hoc Networking (MANET)                             C. Dearlove
Internet-Draft                           BAE Systems Advanced Technology
Intended status: Informational                                    Centre
Expires: January 11, 2009                                     T. Clausen
                                        LIX, Ecole Polytechnique, France
                                                              P. Jacquet
                                                           INRIA, France
                                                           July 10, 2008


                        Link Metrics for OLSRv2
                    draft-dearlove-olsrv2-metrics-02

Status of This Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

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

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on January 11, 2009.














Dearlove, et al.        Expires January 11, 2009                [Page 1]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


Abstract

   This document describes how link metrics may be added, in a
   relatively straightforward manner, to the specification of OLSRv2, in
   order to allow routing by other than minimum hop count paths.  In
   addition to metric signaling and use, the most significant change is
   a separation of the routing and flooding functions of MPRs.

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Applicability  . . . . . . . . . . . . . . . . . . . . . . . .  5
   3.  Motivational Scenarios . . . . . . . . . . . . . . . . . . . .  6
   4.  Link Metrics . . . . . . . . . . . . . . . . . . . . . . . . .  8
     4.1.  Directional Link Metrics . . . . . . . . . . . . . . . . .  8
     4.2.  Reporting Link Metrics . . . . . . . . . . . . . . . . . .  9
     4.3.  Defining Link Metrics  . . . . . . . . . . . . . . . . . . 10
     4.4.  Link Metric TLVs . . . . . . . . . . . . . . . . . . . . . 11
     4.5.  Link Metric Values . . . . . . . . . . . . . . . . . . . . 11
   5.  MPRs with Link Metrics . . . . . . . . . . . . . . . . . . . . 13
     5.1.  Flooding MPRs  . . . . . . . . . . . . . . . . . . . . . . 13
     5.2.  Routing MPRs . . . . . . . . . . . . . . . . . . . . . . . 14
     5.3.  Relationship Between MPR Sets  . . . . . . . . . . . . . . 17
   6.  Implementation . . . . . . . . . . . . . . . . . . . . . . . . 19
     6.1.  Local Information Base . . . . . . . . . . . . . . . . . . 19
     6.2.  Interface Information Base . . . . . . . . . . . . . . . . 20
     6.3.  Node Information Base  . . . . . . . . . . . . . . . . . . 21
     6.4.  Topology Information Base  . . . . . . . . . . . . . . . . 21
     6.5.  Processing and Information Base  . . . . . . . . . . . . . 22
     6.6.  Metric Representation  . . . . . . . . . . . . . . . . . . 22
     6.7.  MPR Representation . . . . . . . . . . . . . . . . . . . . 23
     6.8.  HELLO Message Generation . . . . . . . . . . . . . . . . . 23
     6.9.  HELLO Message Processing . . . . . . . . . . . . . . . . . 24
     6.10. MPR Calculation and Neighbor Set Update  . . . . . . . . . 25
     6.11. TC Message Generation  . . . . . . . . . . . . . . . . . . 25
     6.12. TC Message Processing  . . . . . . . . . . . . . . . . . . 25
     6.13. Routing Set Calculation  . . . . . . . . . . . . . . . . . 26
   7.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 27
   8.  Security Considerations  . . . . . . . . . . . . . . . . . . . 28
   9.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 29
     9.1.  Normative References . . . . . . . . . . . . . . . . . . . 29
     9.2.  Informative References . . . . . . . . . . . . . . . . . . 29
   Appendix A.  MPR Routing Property  . . . . . . . . . . . . . . . . 30
   Appendix B.  Routing MPR Calculation . . . . . . . . . . . . . . . 32
   Appendix C.  Acknowledgements  . . . . . . . . . . . . . . . . . . 35






Dearlove, et al.        Expires January 11, 2009                [Page 2]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


1.  Introduction

   The Optimized Link State Routing Protocol [OLSRv2] is a proactive
   routing protocol for Mobile Ad hoc NETworks (MANETs) [RFC2501].  In
   its current form, this protocol finds shortest, defined as minimum
   number of hops, paths from a node to all possible destinations.

   However limiting routing paths to minimum hop paths may yield what
   are, to the user, inferior paths.  Some examples are given in
   Section 3.  This limitation is not, however, fundamental to OLSRv2.
   First, the extensible message format [packetbb] used by OLSRv2
   naturally permits the addition of additional information regarding
   links to OLSRv2 messages.  Second, OLSRv2 essentially first collects
   topological information from the network and then forms minimum
   length paths.  Using a definition of path length other than number of
   hops is a natural extension.

   Addition of alternative path selection processes to OLSRv2 could be
   treated as a possible future extension.  However in this case, legacy
   OLSRv2 nodes, which would not recognize any additional link
   information, would still attempt to use minimum hop paths.  This
   would mean that, in effect, nodes differed over their valuation of
   links and paths.  This can lead to the fundamental routing problem of
   "looping", and must be avoided.  Thus if alternative path selection
   were to be considered only as a future extension, then nodes which
   did, and nodes which did not, implement the extension could not
   interoperate.  This would be a significant limitation of such an
   extension.

   This document discusses a possible extension to OLSRv2 which could be
   fairly straightforwardly incorporated in a revision of [OLSRv2].  The
   principal changes to OLSRv2 which this extension involves are:

   o  Assigning metrics to links.  This involves considering separate
      metrics for the two directions of a link, with the receiving node
      determining the metric in that direction.  Directional metrics
      must be signaled in HELLO messages, and are also included in TC
      messages.

   o  Metrics to be used in OLSRv2 are 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 would use these metrics in a
      consistent manner.

   o  The separation of the two functions performed by MPRs in OLSRv2,
      optimized flooding and reduced topology advertisement for routing,
      into separate sets of MPRs, denoted flooding MPRs and routing



Dearlove, et al.        Expires January 11, 2009                [Page 3]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


      MPRs.  Flooding MPRs can be calculated as MPRs currently are (but
      can improve the selection using metrics) while routing MPRs need a
      metric-aware selection algorithm, an example of which is given in
      this document.  This guarantees the use of minimum distance routes
      using the chosen metric, while still using only two hop
      neighborhood information from HELLO messages and routing MPR
      selector information in TC messages.

   o  Appropriate changes to protocol Information Bases, messages (new
      metric and modified MPR TLVs) and message processing.  These are
      described in some detail in this document.








































Dearlove, et al.        Expires January 11, 2009                [Page 4]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


2.  Applicability

   The objective of this document is to serve as a basis for discussion
   as to whether such a revision of [OLSRv2], to form part of the basic
   OLSRv2 specification, is desirable, or even essential for the
   widespread adoption of OLSRv2 that is its objective.  None of the
   changes proposed in this document affect any of the other constituent
   parts of OLSRv2, in particular they do not affect [NHDP], since as
   some uses of that protocol will not need metrics, they should not
   have metrics imposed on them.









































Dearlove, et al.        Expires January 11, 2009                [Page 5]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


3.  Motivational Scenarios

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

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

                                 Figure 1

   The minimum hop path 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 path A to B via Y and Z may be
   preferred.

   There are other situations where even if 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 being less reliable.  However even if the long range
   links have the same characteristics, it may be better to reserve
   their usage for when it is particularly valuable - for example when
   the use of one long range link saves several short range links
   (rather than the single link that is all that is needed to be saved
   for a minimum hop path).

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

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



Dearlove, et al.        Expires January 11, 2009                [Page 6]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


   its use of [NHDP]) is not a solution to these problems, use of link
   quality as so specified allows a node to decline to use a link, not
   only on its own, but on all nodes' behalf.  It does not allow the use
   of a link, for example, if all else fails.  Note that it is not
   suggested that use of non-minimum hop paths will replace those
   mechanisms, there is a place for each used together.

   It should also be noted that the loop-free property of OLSRv2, and of
   this modification, apply 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, but with update rates
   appropriate to the rate of topology change, these are 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, TC_INTERVAL and TC_MIN_INTERVAL).



































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


Internet-Draft             OLSRv2 Link Metrics                 July 2008


4.  Link Metrics

   The approach suggested here is the straightforward one of assigning
   metrics to links, and then of taking the overall path metric to be
   the sum of the link metrics.  A link metric is a dimensionless value.

   The principal advantage of this approach is its simplicity and
   mathematical tractability.  There are cases where a user may have a
   different preference (for example "the shortest path such that all
   links support at least a given bandwidth").  It is discussed below
   how, although the suggested approach cannot cover all such
   requirements, it can be adapted to provide what may often be a
   tolerable approximation.

4.1.  Directional Link Metrics

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

   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 links.  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 preferred.
   Each node must thus be responsible for defining the metric in one
   direction only.  This could be in either direction, i.e. that a node
   is responsible for either incoming or outgoing link metrics, as long
   as the choice is universal.  The former (incoming) case is used
   because, in general, receiving nodes 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 node A defines the metric of
   the link from node B to node A, then node B must use node A's
   definition of that metric on that link in that direction.  (Node 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 [NHDP].)




Dearlove, et al.        Expires January 11, 2009                [Page 8]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


4.2.  Reporting Link Metrics

   Links, and hence link metrics, will be reported in HELLO messages and
   TC messages.  A node must report the incoming directional metric in
   its HELLO messages in order that this is available at the other end
   of the link.  This will mean that, for a bidirectional link, both
   ends of the link will know both metrics.

   To fit the OLSRv2 model, node A must be responsible for advertising
   the metric from node A to node B in TC messages.  (This is the
   opposite of HELLO messages, which advertise the metric from node B to
   node A in node A's HELLO messages.)  This can be seen by considering
   a path connecting single OLSRv2 interface nodes P to Q to R to S.
   Node P receives its only information about the link from R to S in
   the TC messages transmitted by node R, which is an MPR of node S
   (assuming that only MPR selectors are reported in TC messages).  Node
   S may not even transmit TC messages (if no nodes 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 node R, hence node R is
   responsible for reporting the metric for the link from R to S.

   In this example, node P also receives information about the link
   between Q and R in the HELLO messages sent by node Q. Without the
   presence of link metrics, this link may be used by OLSRv2 for two hop
   routing to node R using just HELLO messages sent by node Q. Assuming
   that this property (which accelerates local route formation) is to be
   retained, node P must receive the metric of the link from Q to R in
   HELLO messages sent by node Q. This indicates that node Q must be
   responsible for reporting the metric for the link from Q to R. This
   is an addition to the incoming link metric information that a HELLO
   message must report.

   This leaves two possible design choices:

   o  HELLO messages can report only incoming link metrics.  This is
      required only for links on this OLSRv2 interface, i.e. with a
      LINK_STATUS TLV, and only when indicating HEARD or LOST.  This
      prevents the use of two-hop routes informed only by HELLO
      messages, and would be a change to OLSRv2.

   o  HELLO messages report both incoming and outgoing link metrics.
      The former is required only for links on this OLSRv2 interface,
      i.e. with a LINK_STATUS TLV, and only when indicating HEARD or
      LOST.  The latter is required for all OLSRv2 interfaces, i.e.
      including those with an OTHER_NEIGHB TLV as well as a LINK_STATUS
      TLV, but only when each is SYMMETRIC.  In some cases the two sent
      metrics will be equal, and signaling that allows just one metric



Dearlove, et al.        Expires January 11, 2009                [Page 9]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


      to be sent in such cases will improve efficiency.

   Accelerated two-hop route formation is a feature of OLSRv2 it would
   be unfortunate to lose, and hence the latter approach is used.  In
   addition Section 5.1 offers an additional reason for reporting
   outgoing link metrics, without which metrics can affect only routing,
   not flooding.

4.3.  Defining Link Metrics

   When a node reports a neighbor node in a HELLO message it may do so
   for the first time with LINK_STATUS == HEARD.  The receiving node may
   immediately consider the link to be symmetric and use it.

   As the node is responsible for defining and reporting incoming link
   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 is no outgoing link metric available to report.

   This procedure requires a node to immediately decide on a link metric
   once it has heard a neighbor on an OLSRv2 interface for the first
   time.  This is because, on receiving a HELLO message from this node,
   that neighbor will (unless link quality indicates otherwise)
   immediately consider the link to be symmetric and use it.  This may
   be too early for an ideal decision as to that metric, however a
   choice must be made (even if only that a default value is used).  The
   metric may later be refined based on further observation of HELLO
   messages, other message transmissions between the nodes (it may be
   appropriate to use unicast packets to test the link) 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.

   In order that nodes can accurately define link metrics, it may be
   appropriate (in OLSRv2 messages or otherwise) to send information
   relating to link characteristics, such as bandwidth or signal
   strength, from one node to another.  If done within OLSRv2 then
   additional TLVs may be defined to include such information.  However
   all such signaling, and any such TLVs, are outside the scope of a
   revision of [OLSRv2].  In particular it does not matter for
   interoperability whether node A understands such signaling by node B;
   as long as it defines the metrics it is responsible for, the network
   will function, without routing loops (although possibly sub-
   optimally).






Dearlove, et al.        Expires January 11, 2009               [Page 10]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


4.4.  Link Metric TLVs

   Metric values will naturally be reported using a new address block
   TLV.  For TC messages a single such TLV is required.  For HELLO
   messages, TLVs for each direction are needed.

   In HELLO messages link metrics (using a TLV or a default value) are
   required for addresses with LINK_STATUS == HEARD (incoming metric
   only) and LINK_STATUS == SYMMETRIC.  Link metrics are also required
   for addresses with OTHER_NEIGHB == SYMMETRIC; in this case if a node
   has more than one possible value (on different OLSRv2 interfaces), it
   must use the smallest.

4.5.  Link Metric Values

   As noted above, the actual preferred approach to path selection may
   not be directly modeled by an additive metric.  However there are
   uses of an additive metric that support some alternatives.  For
   example if there are "high capacity" and "low capacity" links, and
   the preference is for all high capacity links, then if (for example)
   we assume that routes will not contain more than 10 links, we can set
   the metric for high capacity links to 1, and for low capacity links
   to 10.  If there are three grades of link, then values of 1, 10 and
   100 will work.

   Such examples, particularly when the number of grades of link
   increases, suggest that a reasonably wide dynamic range of link
   metrics is desirable.  On the other hand, link metrics that occupy no
   more than one octet are also desirable for message size reasons.  One
   approach that includes both requirements is already in use in OLSRv2,
   for time values, as described in [timetlv].  This specifies a value
   using a mantissa and exponent, together occupying 8 bits.  For link
   metric purposes a 4 bit mantissa and a 4 bit exponent is suggested
   here. ([timetlv] uses a 3 bit mantissa and a 5 bit exponent, offering
   increased range but reduced precision.)  This could be used so that
   the transmitted octet 16*b + a represents the value (1 + a/16) * 2^b.
   This would then represents values from a minimum of 1 to a maximum of
   63488.  However this also allows fractional metrics, as so for
   convenience it is suggested that the metric value range used is from
   a minimum of 16 to a maximum of 16 * 63488 (= 1015808), i.e. that 16
   * b + a represents the value (16 + a) * 2^b.  Note that this
   rescaling has no effect on message contents or performance.

   As noted above, in order that metric use can be most efficient, a
   default value is needed (including in networks which choose to use
   minimum hop paths).  It is suggested that this is in the centre of
   the above range logarithmically; the closest representable value is
   4096 (a == 0, b == 8).  It is also suggested that path metric



Dearlove, et al.        Expires January 11, 2009               [Page 11]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


   summation be exact.  Since a path cannot have more than 255 links, 28
   bit (or more, in practice probably 32 bit) arithmetic can be used.

















































Dearlove, et al.        Expires January 11, 2009               [Page 12]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


5.  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.  Note that this is currently managed by this
      node's Relay Set, whose minimum contents are the set of the OLSRv2
      interface addresses of this node's MPR selectors which are
      connected to the relevant OLSRv2 interface of this node.  A change
      to this approach is included in this document.

   o  Routing.  Note that routing is based on the Topology Set, which is
      based on received TC messages, whose contents are set from the
      Advertised Neighbor Set, whose minimum contents are the OLSRv2
      interface addresses of the MPR selectors of this node.

   Metrics interact with these two uses of MPRs differently, which are
   considered separately in the following two sections.  The
   relationship between the two sets of MPRs is considered in
   Section 5.3.

5.1.  Flooding MPRs

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

   That does not mean however that metrics cannot be usefully considered
   in selecting MPRs for flooding.  Consider the network in Figure 2,
   where numbers are metrics of links away from node A, by shortest
   paths.  (Simple metric values are used for clarity.)

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

                                 Figure 2

   Which is the better MPR selection by 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



Dearlove, et al.        Expires January 11, 2009               [Page 13]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


   example, the metric represents bandwidth or delay rather than
   probability of loss.)

   However, this does not automatically mean that, as in the example
   above, only the second hop should be considered.  If this example is
   modified to that in Figure 3:

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

                                 Figure 3

   then it is possible that selecting C is preferable to selecting B for
   A. If the metrics represent negatively scaled logarithms of
   probability of loss, so that overall probability of loss is defined
   by the sum of metrics (which is therefore a good choice for metrics
   which are, as assumed here, to be considered as additive) then
   selecting C is better.  This applies more simply when the metric is
   delay (suitably scaled).  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 nodes as an MPR, each only adding one node
   coverage.  A more general process, when considering which node to
   next add as an MPR, should incorporate the metric to that node, and
   the metric from that node to each symmetric strict 2-hop neighbor, as
   well as the number of newly covered symmetric strict 2-hop neighbors
   as well as the other factors used in the example algorithm in
   [OLSRv2].

   Note that, as in [OLSRv2], each node can make its own independent
   choice of MPRs, and MPR selection algorithms, and still interoperate.
   A specific candidate algorithm is not suggested in this document.

   Note that the references above to the direction of the metrics is
   correct: for flooding, directional metrics outward from a node are
   appropriate, i.e. metrics in the direction of the flooding.  This is
   an additional reason for including outward metrics in HELLO messages.

5.2.  Routing MPRs

   The essential detail of the current MPR specification in [OLSRv2] is
   that a node must, per OLSRv2 interface, select a set of MPRs which



Dearlove, et al.        Expires January 11, 2009               [Page 14]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


   provide a two hop path from all symmetric strict 2-hop neighbors,
   with the intermediate node being an MPR.

   It is sufficient, when using an additive link metric rather than a
   hop count, to require that the MPRs provide not just a two hop path,
   but a minimum distance two hop path.  In addition, the concept of
   symmetric strict 2-hop neighbor needs an adjustment.  A node is a
   symmetric strict 2-hop neighbor even if it is a symmetric 1-hop
   neighbor, as long as there is a two hop path from it that is shorter
   than the one hop link from it.  (The property that no routes go
   through nodes with willingness WILL_NEVER is retained.  Examples
   assume that all nodes do not have willingness WILL_NEVER.)

   For example, in the network in Figure 4, node A must pick node B as
   an MPR, whereas for minimum hop count routing it could alternatively
   pick node C. (Numbers are metrics of links towards node A, by
   shortest paths, in each case.)

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

                                 Figure 4

   In Figure 5, node A must pick node C as an MPR, but for minimum hop
   count routing it would not need to pick any MPRs.

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

                                 Figure 5

   In Figure 6, node A must pick both nodes B and C as MPRs, but for
   minimum hop count routing it could pick either.









Dearlove, et al.        Expires January 11, 2009               [Page 15]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


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

                                 Figure 6

   It is shown in Appendix A that selecting MPRs according to this
   definition, and advertising only such links (plus knowledge of local
   links from HELLO messages) will result in selection of shortest
   routes even if all links are considered.

   However the definition noted above as sufficient for MPR selection is
   not necessary.  For example consider the network in Figure 7.  (The
   metrics from B to C and C to B are both assumed to be 2.)

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

                                 Figure 7

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

   However, A only needs to pick B as an MPR, because the only reason to
   pick C as an 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
   node 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 an MPR.



Dearlove, et al.        Expires January 11, 2009               [Page 16]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


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

   Note that, compared to the first proposed approach, this only removes
   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 revised process.

   Note that the examples in Figure 5 and Figure 6 show that use of link
   metrics may require a node to select more MPRs, and even select MPRs
   when otherwise it would not when not using metrics.  This may result
   in more, and larger, messages being generated, and forwarded more
   often.  Thus use of link metrics is not without cost, even excluding
   the cost of link metric signaling.  There is however no cost (in
   message size or number of messages) if all link metrics are default
   valued and no link metric TLV is used.

   These examples consider only single OLSRv2 interface nodes.  However
   if nodes have more than one OLSRv2 interface, then the process is
   unchanged, other than that if there is more than one known metric
   between two nodes (on different OLSRv2 interfaces), then the smallest
   should be used.  There is no need to calculate MPRs per OLSRv2
   interface for routing.  That requirement results from the
   consideration of flooding and the need to avoid certain "deadlock"
   conditions, which are not relevant to routing.

5.3.  Relationship Between MPR Sets

   It would be convenient if the two sets of MPRs were the same.  This
   can be the case if all metrics are equal (whether to the default
   value or any other value), 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 nodes have
   multiple 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
   node, the sets are not equal, nor is one always a subset of the
   other.  To show this, consider these examples, where all lettered



Dearlove, et al.        Expires January 11, 2009               [Page 17]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


   nodes are assumed equally willing to be MPRs, and numbers are
   bidirectional metrics for links.

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

                                 Figure 8

   In Figure 8, for flooding, A does not require any MPRs.  For routing,
   A must select B as an MPR.

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

                                 Figure 9

   In Figure 9, for routing, A must select C and D as MPRs.  For
   flooding a minimal set of MPRs for A is to just select B. In this
   example the set of routing MPRs will serve as a set of flooding MPRs,
   but a non-minimal one.

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

                                 Figure 10

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



Dearlove, et al.        Expires January 11, 2009               [Page 18]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


6.  Implementation

   Implementation of metrics in OLSRv2 requires the following additions
   to [OLSRv2]:

   o  Definition of the constant default metric value DEFAULT_METRIC.

   o  Addition of link metric information to the Local Information Base,
      the Interface Information Base and the Topology Information Base.

   o  Modifications to the Interface Information Base, Node Information
      Base and Processing and Forwarding Information Base to reflect the
      two types of MPRs to be used.

   o  A TLV to represent metrics, to handle incoming and outgoing/agreed
      cases.

   o  A modification of the TLV to represent MPRs, to handle routing and
      flooding cases.

   o  HELLO message generation to add metrics and both MPR types.

   o  HELLO message processing to use metrics and both MPR types.

   o  Separate routing and flooding MPR calculations and update of
      Neighbor Set.

   o  TC message generation to add metrics.

   o  TC message processing to use metrics.

   o  Routing Set updates to use metrics.

   o  The constraints on the Information Bases will need to be updated,
      along with explanatory material and various other minor details
      that are not covered in this document.

   These changes are summarized in the following sections.

6.1.  Local Information Base

   Each Local Attached Network Tuple, defined in [OLSRv2] will need one
   additional element:

   AL_metric  is the metric of the link to the attached network with
      address AL_net_addr from this node;

   This could replace the existing AL_dist element, however in order



Dearlove, et al.        Expires January 11, 2009               [Page 19]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


   that the R_dist elements in a Routing Set can be set correctly (as
   there may be an external use for these) the AL_dist element has been
   retained, and hence also the hop count value in the GATEWAY TLV.
   Attached networks have not been discussed in this document up to this
   point, but they will behave very similarly to as currently defined in
   [OLSRv2], with appropriate use of the metric.

6.2.  Interface Information Base

   Each Link Tuple, defined in [OLSRv2] by reference to [NHDP], will
   need three additional elements:

   L_in_metric  is the metric of the link from the OLSRv2 interface with
      addresses L_neighbor_iface_addr_list to this OLSRv2 interface;

   L_out_metric  is the metric of the link to the OLSRv2 interface with
      addresses L_neighbor_iface_addr_list from this OLSRv2 interface;

   L_mpr_selector  is a boolean flag, describing if this neighbor has
      selected this node as a flooding MPR, i.e. is a flooding MPR
      selector of this node.

   L_in_metric will be specified by a process outside the OLSRv2
   specification, similarly to L_quality.  When a Link Tuple is created,
   the default value of L_in_metric (used if not over-ridden) is
   DEFAULT_METRIC.

   L_out_metric will be defined by this protocol.  When a Link Tuple is
   created, the default value of L_out_metric will be set as unspecified
   (may be considered to be infinite, probably the simplest
   representation is as the otherwise unused value zero).  Setting
   L_out_metric will require the corresponding N_metric to be updated
   by:

   o  If there is no old N_metric, or if the new L_out_metric is less
      than the old N_metric, then set the new N_metric to the new
      L_out_metric.

   o  Otherwise, if the old L_out_metric is equal to the old N_metric,
      and the new L_out_metric is greater than the old N_metric, then
      set the new N_metric to the minimum of all corresponding
      L_out_metric values, including the new L_out_metric.

   The recording of flooding MPR selectors in the Link Set is part of a
   process that includes deleting the Relay Set from the Processing and
   Forwarding Information Base, and making relaying decisions specified
   only by the flooding MPR selector.




Dearlove, et al.        Expires January 11, 2009               [Page 20]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


   Each 2-Hop Tuple, defined in [OLSRv2] by reference to [NHDP], will
   need two additional elements:

   N2_in_metric  is the metric of the link from the node with address
      N2_2hop_iface_addr to the node with OLSRv2 interface addresses
      N2_neighbor_iface_addr_list, being the lowest known metric
      received on that OLSRv2 interface;

   N2_out_metric  is the metric of the link to the node with address
      N2_2hop_iface_addr from the node with OLSRv2 interface addresses
      N2_neighbor_iface_addr_list, being the lowest known metric
      received on that OLSRv2 interface;

6.3.  Node Information Base

   Each Neighbor Tuple, defined in [OLSRv2] by reference to [NHDP], will
   need four additional or modified elements:

   N_metric  is the minimum metric of any link from this node to this
      neighbor, the minimum of any corresponding L_out_metric;

   N_routing_mpr  is a boolean flag, describing if this neighbor is
      selected as a routing MPR by this node;

   N_flooding_mpr  is a boolean flag, describing if this neighbor is
      selected as a flooding MPR by this node;

   N_mpr_selector  is a boolean flag, describing if this neighbor has
      selected this node as a routing MPR, i.e. is a routing MPR
      selector of this node.

   Note that flooding MPR selection is recorded in the Link Sets, not in
   the Neighbor Set. N_routing_mpr and N_flooding_mpr replace N_mpr.

6.4.  Topology Information Base

   The Advertised Neighbor Set will consist of Advertised Neighbor
   Tuples.  In addition to A_neighbor_iface_addr these will contain one
   additional element:

   A_metric  is the metric from this node to the node with OLSRv2
      interface address A_neighbor_iface_addr.

   Modifying any A_metric will update the ANSN.

   Each Topology Tuple, defined in [OLSRv2], will need one additional
   element:




Dearlove, et al.        Expires January 11, 2009               [Page 21]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


   T_metric  is the metric of the link from the node with originator
      address T_orig_addr to the OLSRv2 interface with address
      T_dest_iface_addr.

   Each Attached Network Tuple, defined in [OLSRv2], will need one
   additional element:

   AN_metric  is the metric of the link from the node with originator
      address AN_orig_addr to the attached network with address
      AN_net_addr.

   The existing AN_dist element is retained, as for AL_dist in the Local
   Attached Network Tuple.

   Each Routing Tuple, defined in [OLSRv2], will need one additional
   element:

   R_metric  is the metric of the route to the destination with address
      R_dest_addr.

   The R_dist element has been retained as well as adding R_metric.  It
   is outside the scope of OLSRv2 to specify how R_dist and/or R_metric
   may be used when the Routing Set is used to update the IP routing
   table or for any other purpose.

6.5.  Processing and Information Base

   The Relay Sets are removed, as noted in Section 6.2.

6.6.  Metric Representation

   Both HELLO messages and TC messages will need to associate metric
   values with neighbor addresses that they report.  This will use a new
   TLV, named LINK_METRIC.

   HELLO messages will need to report incoming metrics.  These will be
   required for all addresses with an associated LINK_STATUS TLV with
   Type == HEARD or Type == SYMMETRIC.  If no such TLV is supplied in
   either case then the metric will be assumed to be DEFAULT_METRIC.

   HELLO messages will need to report outgoing metrics.  These will be
   required for all addresses with an associated LINK_STATUS TLV with
   Type == SYMMETRIC, or OTHER_NEIGHB TLV with Type == SYMMETRIC.  If no
   such TLV is supplied in either case then the metric will be assumed
   to be DEFAULT_METRIC.

   There will thus be three possible reporting cases: incoming, outgoing
   and a common value.  Rather than using three separate TLVs, it is



Dearlove, et al.        Expires January 11, 2009               [Page 22]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


   suggested that three extended types are used to represent these.  The
   most efficient extended type, zero, could be used for a protocol-
   specified direction, and in OLSRv2 interpreted for HELLO messages as
   incoming, and for TC messages as outgoing.

   For values, a single octet representation with 4 bit mantissa and 4
   bit exponent is suggested, with 16*b + a representing (16 + a) * 2^b.
   This means that zero cannot be represented, which is convenient as it
   would be invalid.  DEFAULT_METRIC is then 4096, which would be
   represented by the single octet 128.  A single representation of
   metric value avoids adding complexity, and multiplying type
   extensions.

6.7.  MPR Representation

   The current single TLV which reports MPR status will need to report
   both routing and flooding MPR status.  As the current TLV, it will
   report this for all relevant addresses of the node; however for
   flooding MPRs it does so only for addresses which have a symmetric
   link on the reporting OLSRv2 interface.

   Rather than using separate TLVs, it is suggested that two extended
   types are used to represent these two types, and a third extended
   type is used to indicate both.  The most efficient type extension,
   zero, could be used to represent both when a LINK_STATUS TLV with
   Type == SYMMETRIC is present, but to represent only routing MPR
   status when only an OTHER_NEIGHB TLV with Type == SYMMETRIC is
   present.

6.8.  HELLO Message Generation

   The following additional contents of a HELLO message are required:

   o  Each included address from an L_neighbor_iface_addr_list with an
      associated LINK_STATUS TLV with Value == HEARD or Value ==
      SYMMETRIC must have an associated LINK_METRIC TLV reporting an
      incoming metric with Value == L_in_metric, unless this is
      DEFAULT_METRIC, in which case it can be omitted.

   o  Each included address from an N_neighbor_iface_addr_list with an
      associated LINK_STATUS or OTHER_NEIGHB TLV with Value == SYMMETRIC
      must have an associated LINK_METRIC TLV reporting an outgoing
      metric with Value == N_metric, unless this is DEFAULT_METRIC, in
      which case it can be omitted.

   o  Each included address from an L_neighbor_iface_addr_list with an
      associated LINK_STATUS TLV with Value == SYMMETRIC must have an
      associated MPR TLV indicating flooding MPR status if and only if



Dearlove, et al.        Expires January 11, 2009               [Page 23]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


      the corresponding N_flooding_mpr == true.

   o  Each included address from an N_neighbor_iface_addr_list with an
      associated LINK_STATUS or OTHER_NEIGHB TLV with Value == SYMMETRIC
      must have an associated MPR TLV indicating routing MPR status if
      and only if the corresponding N_routing_mpr == true.

   Incoming and outgoing link metrics, or routing and flooding MPR
   indications, can be combined when appropriate.

6.9.  HELLO Message Processing

   Processing a HELLO message has the following extra steps:

   o  When adding or updating a Link Tuple when the HELLO message
      includes an address of the receiving OLSRv2 interface with a
      LINK_STATUS TLV, if the reported status is HEARD or SYMMETRIC,
      then the appropriate L_out_metric must be set to the value of any
      LINK_METRIC TLV associated with this address in the incoming (to
      the sending node) direction.  If there is no such TLV then
      L_out_metric is set to DEFAULT_METRIC.  If the reported status is
      LOST then L_out_metric is set as unspecified.  The corresponding
      N_metric must also be updated.

   o  All 2-Hop Tuples that are added or updated by the HELLO message
      also have their N2_in_metric updated to any associated metric
      value using a LINK_STATUS TLV in the incoming (to the sending
      node) direction.  If there is no such TLV then N2_in_metric is set
      to DEFAULT_METRIC.

   o  All 2-Hop Tuples that are added or updated by the HELLO message
      also have their N2_out_metric updated to any associated metric
      value using a LINK_STATUS TLV in the outgoing (to the sending
      node) direction.  If there is no such TLV then N2_out_metric is
      set to DEFAULT_METRIC.

   o  When adding or updating a Link Tuple when the HELLO message
      includes an address of the receiving OLSRv2 interface with a
      LINK_STATUS TLV, if the reported status is SYMMETRIC, then the
      presence or absence of an associated MPR TLV indicating flooding
      TLV status will set or clear the appropriate L_mpr_selector.

   o  When adding or updating a Link Tuple when the HELLO message
      includes an address of the receiving OLSRv2 interface with a
      LINK_STATUS TLV, if the reported status is SYMMETRIC, then the
      presence or absence of an associated MPR TLV indicating routing
      TLV status will set or clear the appropriate N_mpr_selector.




Dearlove, et al.        Expires January 11, 2009               [Page 24]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


   o  The reasons for considering the local neighborhood to have
      changed, and hence requiring an update of the two sets of MPRs
      (whose conditions will be different) must be specified (not given
      in this document).  This will also include using the appropriate
      N_metric to set corresponding values of A_metric.

6.10.  MPR Calculation and Neighbor Set Update

   For routing MPRs, a possible algorithm is given in Appendix B.  This
   sets or clears N_routing_mpr in all Neighbor Tuples with N_symmetric
   == true.

   For flooding MPRs, the existing per OLSRv2 interface algorithm can be
   used unchanged.  In particular its first stage (adding necessary
   MPRs) and third stage (removing unnecessary MPRs) are appropriate
   unchanged.  Its second stage, which prioritizes possible added MPRs,
   can have link metrics (L_out_metric + N2_out_metric) added as a
   consideration in that prioritization.  No specific suggestion is made
   in this document.  Whatever algorithm is used, sets or clears
   N_flooding_mpr instead of the current N_mpr.

6.11.  TC Message Generation

   The following additional contents of a TC message are required:

   o  Each included A_neighbor_iface_addr has an associated outgoing
      LINK_METRIC TLV with Value == A_metric, unless that is
      DEFAULT_METRIC, when it can be omitted.

   o  Each included AL_net_addr has an associated outgoing LINK_METRIC
      TLV with Value == AL_metric, unless that is DEFAULT_METRIC, when
      it can be omitted.

6.12.  TC Message Processing

   Processing a HELLO message has the following extra steps:

   o  When adding or updating a Topology Tuple, set T_metric to the
      value of any associated LINK_METRIC TLV, or to DEFAULT_METRIC if
      none.

   o  When adding or updating an Attached Network Tuple, set AN_metric
      to the value of any associated LINK_METRIC TLV, or to
      DEFAULT_METRIC if none.







Dearlove, et al.        Expires January 11, 2009               [Page 25]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


6.13.  Routing Set Calculation

   Routing Set calculation using the Network Topology Graph is
   unchanged, except that the arcs in the latter have metrics rather
   than hop counts:

   o  For a local symmetric link use L_out_metric.

   o  For a 2-hop symmetric link use N2_out_metric.

   o  For an advertised symmetric link use T_metric.

   o  For a symmetric 1-hop neighbor address use N_metric.

   o  For an attached network address use AN_metric.




































Dearlove, et al.        Expires January 11, 2009               [Page 26]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


7.  IANA Considerations

   This document presents no IANA considerations.  Addition of metrics
   to [OLSRv2] will add to that document's IANA considerations.















































Dearlove, et al.        Expires January 11, 2009               [Page 27]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


8.  Security Considerations

   This document does not specify any security considerations.
















































Dearlove, et al.        Expires January 11, 2009               [Page 28]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


9.  References

9.1.  Normative References

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

   [packetbb]  Clausen, T., Dearlove, C., Dean, J., and C. Adjih,
               "Generalized MANET Packet/Message Format",
               draft-ietf-manet-packetbb-13.txt (work in progress),
               June 2008.

9.2.  Informative References

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

   [NHDP]      Clausen, T., Dearlove, C., and J. Dean, "MANET
               Neighborhood Discovery Protocol (NHDP)",
               draft-ietf-manet-nhdp-07.txt (work in progress),
               July 2008.

   [timetlv]   Clausen, T. and C. Dearlove, "Representing multi-value
               time in MANETs", draft-ietf-manet-timetlv-05.txt (work in
               progress), July 2008.























Dearlove, et al.        Expires January 11, 2009               [Page 29]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


Appendix A.  MPR Routing Property

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

   More formally, the required property is that for any 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.

   This appendix shows that the simplest previously described
   redefinition of MPR selection with link metrics has the consequence
   that the routable path property is satisfied.  It assumes that nodes
   with willingness WILL_NEVER have been removed.  It assumes a network
   of directed links each with a positive metric.  It considers links to
   be between nodes, independent of interfaces.

   The required definition for a node X selecting MPRs is that for each
   distinct node Z from which there is a two hop 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 direct link Z - X. Note that the existence of
   locally known, shorter, but more than two hop paths, which can be
   used to reduce the numbers of MPRs, is not considered here.

   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 hops or fewer, then there is a shortest
   path, from among those of n hops or fewer, that is a routable path.
   This may be called the n-hop routable path property.

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

   Proceeding by induction, assuming the n-hop 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 hop path
   from X to Z. We construct a path which has no more than k+1 hops, has
   the same or shorter length (hence has the same, shortest, length
   considering only paths of up to k+1 hops, by assumption) and is a
   routable path.

   First consider whether Vk is an MPR of Z. If it is not then consider
   the two hop path Vk-1 - Vk - Z. This can be replaced either by a



Dearlove, et al.        Expires January 11, 2009               [Page 30]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


   direct link Vk-1 - Z or by a two hop 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 hop link)
   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
   Wk is an MPR of Z, the path X - W1 - ... - Wm-1 - Vk - Z is a
   routable path, and demonstrates the n-hop routable path property for
   n = k+1.

   This thus shows that, with the revised MPR definition, for any
   distinct nodes X and Z, there is a routable path (using OLSRv2's MPR-
   based reduced topology) from X to Z, i.e. that this modification of
   OLSRv2 still finds minimum length paths.
































Dearlove, et al.        Expires January 11, 2009               [Page 31]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


Appendix B.  Routing MPR Calculation

   This a possible algorithm for calculating routing MPRs.  At the start
   of the calculation set N_routing_mpr = false in all Neighbor Tuples.

   This calculation is not per OLSRv2 interface, but is for all OLSRv2
   interfaces together.  Thus all Link Sets and all 2-Hop Sets are
   considered in what follows.

   For convenience assign each Link Tuple a unique identity L_id, and
   each Neighbor Tuple a unique identity N_id.  These are transient,
   used during this calculation only.

   Note that each 2-Hop Tuple has a unique corresponding Link Tuple and
   each Link Tuple has a unique corresponding Neighbor Tuple.  Thus for
   each 2-Hop Tuple we can determine corresponding values of L_id, N_id,
   L_in_metric and N_willingness.

   Define a Local Topology Tuple (used only during MPR calculation),
   which represents a route from a final node to this node, to include:

   LT_next_id  is the identity of the Neighbor Tuple corresponding to
      the nearest node to this node on the route;

   LT_last_id  is the identity of a Link Tuple corresponding to the
      furthest node on the route from this node, other than the final
      node, for an OLSRv2 interface on which that furthest node has a
      symmetric link to this node;

   LT_final_iface_addr  is an address of the final node;

   LT_last_metric  is the metric of the part of the route from the last
      node to this node;

   LT_final_metric  is the metric of the link from the final node to the
      last node;

   LT_number_hops  is the number of hops on the route from the final node
      to this node.

   All such final nodes can reach this node in two hops, the first hop
   being to the last node other than the final node, but the preferred
   route may use more hops with a lower metric.  When the route uses two
   hops, the last and next nodes are the same (the node between this
   node and the final node).  As for 2-Hop Tuples, a separate Local
   Topology Tuple is used for each address of each final node.

   It is assumed here that between routes with equal metric, a route



Dearlove, et al.        Expires January 11, 2009               [Page 32]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


   with fewest hops is preferred.

   Then, for each 2-Hop Tuple whose corresponding N_willingness is not
   equal to WILL_NEVER, create a Local Topology Tuple with:

   o  LT_next_id = corresponding N_id

   o  LT_last_id = corresponding L_id

   o  LT_final_iface_addr = N2_2hop_iface_addr

   o  LT_last_metric = corresponding L_in_metric

   o  LT_final_metric = N2_in_metric

   o  LT_number_hops = 2

   Now, while there are any two Local Topology Tuples (Tuple A and Tuple
   B) such that:

   o  A's LT_final_iface_addr is in the L_neighbor_iface_addr_list
      corresponding to B's LT_last_id, and

   o  A's LT_last_metric + LT_final_metric < B's LT_last_metric

   update Tuple B by:

   o  LT_next_id = A's LT_next_id

   o  LT_last_metric = A's LT_last_metric + LT_final_metric

   o  LT_number_hops = A's LT_number_hops + 1

   This replaces Tuple B's route from this node to its last node by
   Tuple A's route from this node to its final node.

   Once that process is finished, remove all Local Topology Tuples such
   that either:

   o  there is a Link Tuple with LT_final_iface_addr in
      L_neighbor_iface_addr_list; AND

   o  L_out_metric <= LT_final_metric

   or:

   o  there is another Local Topology Tuple with the same
      LT_final_iface_addr; AND



Dearlove, et al.        Expires January 11, 2009               [Page 33]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


      *  a smaller value of LT_last_metric + LT_final_metric; OR

      *  an equal value of LT_last_metric + LT_final_metric and a
         smaller value of LT_number_hops.

   This removes Local Topology Tuples where either there is a Link Tuple
   offering a better one hop route, or another Local Topology Tuple
   offering a better route, from the final node.

   For each remaining Local Topology Tuple define that the Neighbor
   Tuple with identity LT_next_id covers the 2-hop neighbor address
   LT_final_iface_addr.

   A valid set of routing MPRs is any subset of these Neighbor Tuples
   which collectively cover all of these LT_final_iface_addr.  Set the
   corresponding N_routing_mpr = true.

   While any subset is valid, a heuristic for a "good" subset is
   required.  The current heuristic has three main steps: add necessary
   neighbors, add additional neighbors in a prioritized order until
   coverage is complete, remove unneeded neighbors (possibly in order of
   ascending willingness).  There is no reason to modify this.  The
   middle step currently uses the following priority order: greatest
   willingness, maximum new coverage, maximum coverage, if an MPR
   selector, any.  This will still work (the MPR selector step should be
   routing MPR selector).  It may be considered that metrics could be
   used.  However in principle this is not necessary, as metrics have
   already been taken into account in this construction.  (This differs
   from flooding MPRs, where considering metrics in this step is
   appropriate as they are not used up to this point.)





















Dearlove, et al.        Expires January 11, 2009               [Page 34]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


Appendix C.  Acknowledgements

   The authors would like to thank Alan Cullen (BAE Systems) for review
   and comments on this document.  Discussions with Brian Adamson and
   Justin Dean (both NRL) have been an inspiration of this document.














































Dearlove, et al.        Expires January 11, 2009               [Page 35]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


Authors' Addresses

   Christopher Dearlove
   BAE Systems Advanced Technology Centre

   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
   INRIA, France

   Phone: +33 1 3963 5263
   EMail: Philippe.Jacquet@inria.fr
   URI:   http://hipercom.inria.fr/



























Dearlove, et al.        Expires January 11, 2009               [Page 36]


Internet-Draft             OLSRv2 Link Metrics                 July 2008


Full Copyright Statement

   Copyright (C) The IETF Trust (2008).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.












Dearlove, et al.        Expires January 11, 2009               [Page 37]