draft-ietf-manet-olsrv2-metrics-rationale-00.txt   draft-ietf-manet-olsrv2-metrics-rationale-01.txt 
Mobile Ad hoc Networking (MANET) C. Dearlove Mobile Ad hoc Networking (MANET) C. Dearlove
Internet-Draft BAE Systems ATC Internet-Draft BAE Systems ATC
Intended status: Informational T. Clausen Intended status: Informational T. Clausen
Expires: February 2, 2013 LIX, Ecole Polytechnique, France Expires: April 12, 2013 LIX, Ecole Polytechnique, France
P. Jacquet P. Jacquet
Alcatel-Lucent Bell Labs Alcatel-Lucent Bell Labs
August 1, 2012 October 9, 2012
Link Metrics for the Mobile Ad Hoc Network (MANET) Routing Protocol Link Metrics for the Mobile Ad Hoc Network (MANET) Routing Protocol
OLSRv2 - Rationale OLSRv2 - Rationale
draft-ietf-manet-olsrv2-metrics-rationale-00 draft-ietf-manet-olsrv2-metrics-rationale-01
Abstract Abstract
This document describes the rationale for and design considerations This document describes the rationale for and design considerations
behind how link metrics are included in OLSRv2, in order to allow behind how link metrics are included in OLSRv2, in order to allow
routing by other than minimum hop count routes. routing by other than minimum hop count routes.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
skipping to change at page 1, line 36 skipping to change at page 1, line 36
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on February 2, 2013. This Internet-Draft will expire on April 12, 2013.
Copyright Notice Copyright Notice
Copyright (c) 2012 IETF Trust and the persons identified as the Copyright (c) 2012 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 3, line 21 skipping to change at page 3, line 21
Using only minimum hop routes may result in what are, in practice, Using only minimum hop routes may result in what are, in practice,
inferior routes. Some examples are given in Section 4. Thus, one of inferior routes. Some examples are given in Section 4. Thus, one of
the distinguishing features of the Optimized Link State Routing the distinguishing features of the Optimized Link State Routing
Protocol version 2 (OLSRv2) [OLSRv2] is the introduction of the Protocol version 2 (OLSRv2) [OLSRv2] is the introduction of the
ability to select routes using link metrics other than the number of ability to select routes using link metrics other than the number of
hops. hops.
OLSRv2 essentially first determines local link metrics from 1-hop OLSRv2 essentially first determines local link metrics from 1-hop
neighbors, these being defined by a process outside OLSRv2, then neighbors, these being defined by a process outside OLSRv2, then
distributes required link metric values in HELLO and TC messages, and distributes required link metric values in HELLO messages and TC
then finally forms routes with minimum total link metric. Using a messages, and then finally forms routes with minimum total link
definition of route metric other than number of hops is a natural metric. Using a definition of route metric other than number of hops
extension that is commonly used in link state protocols. is a natural extension that is commonly used in link state protocols.
Use of the extensible message format [RFC5444] by OLSRv2 has allowed Use of the extensible message format [RFC5444] by OLSRv2 has allowed
the addition, by OLSRv2, of link metric information to the HELLO the addition, by OLSRv2, of link metric information to the HELLO
messages defined in the MANET NeighborHood Discovery Protocol (NHDP) messages defined in the MANET NeighborHood Discovery Protocol (NHDP)
[RFC6130] as well as inclusion in the Topology Control (TC) messages [RFC6130] as well as inclusion in the Topology Control (TC) messages
defined in [OLSRv2]. defined in [OLSRv2].
A metric-based route selection processes for OLSRv2 could have been A metric-based route selection processes for OLSRv2 could have been
handled as an extension to OLSRv2. However in this case, legacy handled as an extension to OLSRv2. However in this case, legacy
OLSRv2 routers, which would not recognize any link metric OLSRv2 routers, which would not recognize any link metric
skipping to change at page 4, line 19 skipping to change at page 4, line 19
* A neighbor metric, the minimum of the link metrics between two * A neighbor metric, the minimum of the link metrics between two
OLSRv2 routers, in the indicated direction. OLSRv2 routers, in the indicated direction.
These metrics are necessarily the same when these routers each These metrics are necessarily the same when these routers each
have a single OLSRv2 interface, but may differ when either has have a single OLSRv2 interface, but may differ when either has
more. HELLO messages may include both link metrics and neighbor more. HELLO messages may include both link metrics and neighbor
metrics. TC messages include only neighbor metrics. metrics. TC messages include only neighbor metrics.
o Metrics as used in OLSRv2 were defined to be dimensionless and o Metrics as used in OLSRv2 were defined to be dimensionless and
additive. The assignment of metrics, including their relationship additive. The assignment of metrics, including their relationship
to real parameters such as bandwidth, loss rate and delay, is to real parameters such as data rate, loss rate and delay, is
outside the scope of OLSRv2, which simply uses these metrics in a outside the scope of OLSRv2, which simply uses these metrics in a
consistent manner. However by use of a registry of metric types consistent manner. However by use of a registry of metric types
(employing extended types of a single address block TLV type), (employing extended types of a single address block TLV type),
routers can use only metrics of the physical type that they are routers can use only metrics of the physical type that they are
configured to use. configured to use.
o The separation of the two functions performed by MPRs in OLSRv1, o The separation of the two functions performed by MPRs in OLSRv1,
optimized flooding and reduced topology advertisement for routing, optimized flooding and reduced topology advertisement for routing,
into separate sets of MPRs in OLSRv2 [OLSRv2], denoted "flooding into separate sets of MPRs in OLSRv2 [OLSRv2], denoted "flooding
MPRs" and "routing MPRs". Flooding MPRs can be calculated as in MPRs" and "routing MPRs". Flooding MPRs can be calculated as in
skipping to change at page 5, line 10 skipping to change at page 5, line 10
o The protocol Information Bases defined in OLSRv2 include required o The protocol Information Bases defined in OLSRv2 include required
metric values. This has included additions to the protocol metric values. This has included additions to the protocol
Information Bases defined in NHDP [RFC6130] when used by OLSRv2. Information Bases defined in NHDP [RFC6130] when used by OLSRv2.
2. Terminology 2. Terminology
All terms introduced in [RFC5444], including "message" and "TLV", are All terms introduced in [RFC5444], including "message" and "TLV", are
to be interpreted as described there. to be interpreted as described there.
All terms introduced in [RFC6130], including "MANET Interface", All terms introduced in [RFC6130], including "MANET interface",
"HELLO message", "heard", "link", symmetric link", "1-hop neighbor", "HELLO message", "heard", "link", symmetric link", "1-hop neighbor",
"symmetric 1-hop neighbor", "2-hop neighbor", "symmetric 2-hop "symmetric 1-hop neighbor", "2-hop neighbor", "symmetric 2-hop
neighbor", and "symmetric 2-hop neighborhood", are to be interpreted neighbor", and "symmetric 2-hop neighborhood", are to be interpreted
as described there. as described there.
All terms introduced in [OLSRv2], including "router", "OLSRv2 All terms introduced in [OLSRv2], including "router", "OLSRv2
interface", "willingness", "MultiPoint Relay (MPR)", "MPR selector", interface", "willingness", "MultiPoint Relay (MPR)", "MPR selector",
and "MPR flooding" are to be interpreted as described there. and "MPR flooding" are to be interpreted as described there.
3. Applicability 3. Applicability
The objective of this document is to retain the design considerations The objective of this document is to retain the design considerations
behind how link metrics were included in [OLSRv2]. The document does behind how link metrics were included in [OLSRv2]. This document
not prescribe any behavior, but explains some aspects of the does not prescribe any behavior, but explains some aspects of the
operation of OLSRv2. operation of OLSRv2.
4. Motivational Scenarios 4. Motivational Scenarios
The basic situation that suggests the desirability of use of routes The basic situation that suggests the desirability of use of routes
other than minimum hop routes is shown in Figure 1. other than minimum hop routes is shown in Figure 1.
A ----- X ----- B A ----- X ----- B
\ / \ /
\ / \ /
Y ------- Z Y ------- Z
Figure 1 Figure 1
The minimum hop route from A to B is via X. However if the links A to 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 X and X to B are poor (e.g., having low data rate or being
unreliable) but the links A to Y, Y to Z and Z to B are better (e.g., 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 having reliable high data rate) then the route A to B via Y and Z may
be preferred to that via X. be preferred to that via X.
There are other situations where, even if the avoidance of some links There are other situations where, even if the avoidance of some links
do not show immediately obvious benefits to users, their use should does not show immediately obvious benefits to users, their use should
be discouraged. Consider a network with many short range links, and be discouraged. Consider a network with many short range links, and
a few long range links. Use of minimum hop routes will immediately 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 lead to heavy use of the long range links. This will be particularly
undesirable if those links achieve their longer range through reduced undesirable if those links achieve their longer range through reduced
bandwidth, or through being less reliable. However, even if the long data rate, or through being less reliable. However, even if the long
range links have the same characteristics as the short range links, 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 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 this usage is particularly valuable - for example when the use of one
long range link saves several short range links, rather than the long range link saves several short range links, rather than the
single link saving that is all that is needed for a minimum hop single link saving that is all that is needed for a minimum hop
route. route.
A related case is that of a privileged relay. An example is an A related case is that of a privileged relay. An example is an
aerial router in an otherwise ground based network. The aerial aerial router in an otherwise ground based network. The aerial
router may have a link to many, or even all, other routers. That router may have a link to many, or even all, other routers. That
skipping to change at page 8, line 5 skipping to change at page 8, line 5
such as if the ground based portion of the network is not connected. such as if the ground based portion of the network is not connected.
Other cases may involve attempts to avoid areas of congestion, to Other cases may involve attempts to avoid areas of congestion, to
route around insecure routers (by preference, but prepared to use route around insecure routers (by preference, but prepared to use
them if there is no other alternative) and routers attempting to them if there is no other alternative) and routers attempting to
discourage their use as relays due to, for example, limited battery discourage their use as relays due to, for example, limited battery
power. OLSRv2 does have another mechanism to aid in this, a router's 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 willingness to act as an MPR. However there are cases where that
cannot help, but where use of non-minimum hop routes could. cannot help, but where use of non-minimum hop routes could.
Similarly note that OLSRv2's optional use of link quality (through Similarly, note that OLSRv2's optional use of link quality (through
its use of [RFC6130]) is not a solution to these problems. Use of 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 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 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 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 too low quality to be generally useful, as part of a route where no
better links exist. These mechanisms (link quality and link metrics) better links exist. These mechanisms (link quality and link metrics)
solve distinctly different problems. solve distinctly different problems.
It should also be noted that the loop-free property of OLSRv2 applies It should also be noted that the loop-free property of OLSRv2 applies
strictly only in the static state. When the network topology is strictly only in the static state. When the network topology is
changing, and with possibly lossy messages, it is possible for changing, and when messages can be lost, it is possible for transient
transient loops to form. However with update rates appropriate to loops to form. However with update rates appropriate to the rate of
the rate of topology change, such loops will be sufficiently rare. topology change, such loops will be sufficiently rare. Changing link
Changing link metrics is a form of network topology change, and metrics is a form of network topology change, and should be limited
should be limited to a rate slower than the message information to a rate slower than the message information update rate (defined by
update rate (defined by the parameters HELLO_INTERVAL, the parameters HELLO_INTERVAL, HELLO_MIN_INTERVAL, REFRESH_INTERVAL,
HELLO_MIN_INTERVAL, REFRESH_INTERVAL, TC_INTERVAL and TC_INTERVAL and TC_MIN_INTERVAL).
TC_MIN_INTERVAL).
5. Link Metrics 5. Link Metrics
This section describes the required and selected properties of the This section describes the required and selected properties of the
link metrics used in OLSRv2, followed by implementation details link metrics used in OLSRv2, followed by implementation details
achieving those properties. achieving those properties.
5.1. Link Metric Properties 5.1. Link Metric Properties
Link metrics in OLSRv2 are: Link metrics in OLSRv2 are:
o Dimensionless. While they may, directly or indirectly, correspond o Dimensionless. While they may, directly or indirectly, correspond
to specific physical information (such as delay, loss rate or to specific physical information (such as delay, loss rate or data
bandwidth), this knowledge is not used by OLSRv2. Instead, rate), this knowledge is not used by OLSRv2. Instead, generating
generating the metric value is the responsibility of a mechanism the metric value is the responsibility of a mechanism external to
external to OLSRv2. OLSRv2.
o Additive, so that the metric of a route is the sum of the metrics 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 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 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 high value of a link metric indicates a "bad" link, and the former
former will be preferred to the latter. will be preferred to the latter.
o Directional, the metric from router A to router B need not be the 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 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 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 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 link metric from router A to router B is referred to as an
outgoing link metric. (These are, of course, reversed at router outgoing link metric. (These are, of course, reversed at router
B.) B.)
o Specific to a pair of OLSRv2 interfaces, so that if there is more 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 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 metric in that direction. There is also an overall metric, a
"neighbor metric", from router A to router B (its 1-hop neighbor). "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 This is the minimum value of the link metrics from router A to
router B, considering symmetric links only; it is undefined if router B, considering symmetric links only; it is undefined if
there are no such symmetric links. A neighbor metric from one there are no such symmetric links. A neighbor metric from one
router to another is always equal to a link metric in the same router to another is always equal to a link metric in the same
direction between OLSRv2 interfaces of those routers. When direction between OLSRv2 interfaces of those routers. When
referring to a specific OLSRv2 interface (for example in a Link referring to a specific OLSRv2 interface (for example in a Link
Tuple or a HELLO message sent on that OLSRv2 interface) 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 metric always refers to a link on that OLSRv2 interface, to or
from the indicated 1-hop neighbor OLSRv2 interface, while a from the indicated 1-hop neighbor OLSRv2 interface, while a
skipping to change at page 10, line 13 skipping to change at page 10, line 13
another OLSRv2 interface. another OLSRv2 interface.
5.2. Link Metric Types 5.2. Link Metric Types
There are various physical characteristics that may be used to define There are various physical characteristics that may be used to define
a link metric. Some examples, which also illustrate some a link metric. Some examples, which also illustrate some
characteristics of metrics that result, are: characteristics of metrics that result, are:
o Delay is a straightforward metric, as it is naturally additive, 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 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 links. This does not directly take into account delays due to
routers, rather than links, but these can be divided among routers (such as due to router queues or transiting packets
incoming and outgoing links.) However, given a limited range of between router interfaces), rather than links, but these delays
link metric value, more than one type of delay metric may be can be divided among incoming and outgoing links.
required, representing different ranges of delay value.
o Probability of loss on a link is, as long as probabilities of loss o Probability of loss on a link is, as long as probabilities of loss
are small and independent, approximately additive. (A slightly are small and independent, approximately additive. (A slightly
more accurate approach is using a negatively scaled logarithm of more accurate approach is using a negatively scaled logarithm of
the probability of not losing a packet.) If losses are not the probability of not losing a packet.) If losses are not
independent then this will be pessimistic. Again, more than one independent then this will be pessimistic.
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 o Data rates are not additive, it even has the wrong characteristic
being good when high, bad when low; thus a mapping that inverts 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 its ordering must be applied. Such a mapping can, at best, only
produce a metric that it is acceptable to treat as additive. produce a metric that it is acceptable to treat as additive.
Consider, for example, a preference for a route that maximizes the Consider, for example, a preference for a route that maximizes the
minimum bandwidth link on the route, and then prefers a route with minimum data rate link on the route, and then prefers a route with
the fewest links of each bandwidth from the lowest. If links may the fewest links of each data rate from the lowest. If links may
be of three discrete bandwidths, "high", "medium" and low", then be of three discrete data rates, "high", "medium", and "low", then
this preference can be achieved, on the assumption that no route 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 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, for the three data rates.
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
metrics will need to define the mapping (e.g., a power and
bandwidth scaling).
There are also many other possible metrics, including physical layer If routes can have more than 10 links, the range of metrics must
information (such as signal to noise ratio, and error control be increased; this was one reason for a preference for a wide
"dynamic range" of link metric values. Depending on the ratios of
the numerical values of the three data rates, the same effect may
be achieved by using a scaling of an inverse power of the
numerical values of the data rates. For example if the three data
rates were 2, 5 and 10 Mbit/s, then a possible mapping would be
the fourth power of 10 Mbit/s divided by the data rate, 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 data
rate values, for example giving a 4 Mbit/s data rate a metric
value of about 39. This may lose the capability to produce an
absolutely maximum minimum data rate 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 metrics will need to define
the mapping.
There are also many other possible metrics, including using physical
layer information (such as signal to noise ratio, and error control
statistics) and information such as packet queuing statistics. statistics) and information such as packet queuing statistics.
In a well-designed network, all routers will use the same physical In a well-designed network, all routers will use the same metric
metric type. It will not produce good routes if, for example, some type. It will not produce good routes if, for example, some link
link metrics are based on bandwidth and some on path loss (except to metrics are based on data rate and some on path loss (except to the
the extent that these may be correlated). How to achieve this is an extent that these may be correlated). How to achieve this is an
administrative matter, outside the scope of OLSRv2. In fact even the administrative matter, outside the scope of OLSRv2. In fact even the
actual physical meanings of the metrics is outside the scope of actual physical meanings of the metrics is outside the scope of
OLSRv2. This is because new metrics may be added in the future, for OLSRv2. This is because new metrics may be added in the future, for
example as bandwidths increase, and may be based on new, possibly example as data rates increase, and may be based on new, possibly
non-physical, considerations, for example financial cost. Each such non-physical, considerations, for example financial cost. Each such
type will have a metric type number. Initially a single link metric type will have a metric type number. Initially a single link metric
type zero is defined as indicating a dimensionless metric with no type zero is defined as indicating a dimensionless metric with no
predefined physical meaning. predefined physical meaning.
An OLSRv2 router is instructed which single link metric type to use An OLSRv2 router is instructed which single link metric type to use
and recognize, without knowing whether it represents delay, and recognize, without knowing whether it represents delay,
probability of loss, bandwidth, cost or any other quantity. This probability of loss, data rate, cost or any other quantity. This
recognized link metric type number is a router parameter, and subject recognized link metric type number is a router parameter, and subject
to change in case of reconfiguration, or possibly the use of a to change in case of reconfiguration, or possibly the use of a
protocol (outside the scope of OLSRv2) permitting a process of link protocol (outside the scope of OLSRv2) permitting a process of link
metric type agreement between routers. metric type agreement between routers.
The use of link metric type numbers also suggests the possibility of The use of link metric type numbers also suggests the possibility of
use of multiple link metric types and multiple network topologies. use of multiple link metric types and multiple network topologies.
This is a possible future extension to OLSRv2. To allow for that This is a possible future extension to OLSRv2. To allow for that
future possibility, the sending of more than one metric, of different future possibility, the sending of more than one metric, of different
physical types, which should otherwise not be done for reasons of physical types, which should otherwise not be done for reasons of
skipping to change at page 13, line 23 skipping to change at page 13, line 18
link from R to S. link from R to S.
o In a more general case, where there may be more than one link from 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 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 can be constructed (e.g., by router P) report the minimum of these
outgoing link metrics, i.e., the outgoing neighbor metric from R outgoing link metrics, i.e., the outgoing neighbor metric from R
to S. to S.
In this example, router P also receives information about the In this example, router P also receives information about the
existence of a link between Q and R in the HELLO messages sent by 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 router Q. Without the use of metrics, this link could be used by
for two hop routing to router R using just HELLO messages sent by OLSRv2 for two hop routing to router R, using just HELLO messages
router Q. For this property (which accelerates local route formation) sent by router Q. For this property (which accelerates local route
to be retained (from OLSRv1) router P must receive the metric from Q formation) to be retained (from OLSRv1) router P must receive the
to R in HELLO messages sent by router Q. This indicates that router Q metric from Q to R in HELLO messages sent by router Q. This indicates
must be responsible for reporting the metric for the outgoing link that router Q must be responsible for reporting the metric for the
from Q to R. This is in addition to the incoming link metric outgoing link from Q to R. This is in addition to the incoming link
information that a HELLO message must report. Again, in general, metric information that a HELLO message must report. Again, in
this must be the outgoing neighbor metric, rather than the outgoing general, this must be the outgoing neighbor metric, rather than the
link metric. outgoing link metric.
In addition, Section 6.1 offers an additional reason for reporting In addition, Section 6.1 offers an additional reason for reporting
outgoing neighbor metrics in HELLO messages, without which metrics outgoing neighbor metrics in HELLO messages, without which metrics
can properly affect only routing, not flooding. can properly affect only routing, not flooding.
Note that there is no need to report an outgoing link metric in a 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 HELLO message. The corresponding 1-hop neighbor knows that value, it
specified it, and for 2-hop neighborhood use neighbor metrics are specified it. Furthermore, for 2-hop neighborhood use, neighbor
required (as these will, in general, not use the same OLSRv2 metrics are required (as these will, in general, not use the same
interface). OLSRv2 interface).
5.5. Defining Incoming Link Metrics 5.5. Defining Incoming Link Metrics
When a router reports a 1-hop neighbor in a HELLO message it may do 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 so for the first time with link status HEARD. As the router is
will then immediately consider the link to be symmetric and thus will responsible for defining and reporting incoming link metrics, it must
use it. 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, but 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.
As the router is responsible for defining and reporting incoming link This is because, when receiving a HELLO message from this router, the
metrics, it must evaluate that metric, and attach that link metric to 1-hop neighbor seeing its own address listed with link status HEARD
the appropriate address (which will have link status HEARD) in the will (unless link quality indicates otherwise) immediately consider
next HELLO message reporting that address on that OLSRv2 interface. that link to be SYMMETRIC, advertise it with that link status in
There will, at this time, be no outgoing link metric available to future HELLO messages, and use it (for MPR selection and data traffic
report. forwarding).
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 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 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 be made. The metric value may later be refined based on further
observation of HELLO messages, other message transmissions between observation of HELLO messages, other message transmissions between
the routers, or other observations of the environment. It will the routers, or other observations of the environment. It will
probably be best to over-estimate the metric if initially uncertain probably be best to over-estimate the metric if initially uncertain
as to its value, to discourage, rather than over-encourage, its use. as to its value, to discourage, rather than over-encourage, its use.
If no information other than the receipt of the HELLO message is If no information other than the receipt of the HELLO message is
available, then a conservative maximum link metric value, in [OLSRv2] available, then a conservative maximum link metric value, denoted
denoted MAXIMUM_METRIC, should be used. MAXIMUM_METRIC in [OLSRv2], should be used.
5.6. Link Metric Values 5.6. Link Metric Values
Link metric values are recorded in LINK_METRIC TLVs, defined in Link metric values are recorded in LINK_METRIC TLVs, defined in
[OLSRv2], using a compressed representation that occupies 12 bits. [OLSRv2], using a compressed representation that occupies 12 bits.
The use of 12 bits is convenient because, when combined with 4 flag The use of 12 bits is convenient because, when combined with 4 flag
bits of additional information, described below, this produced a 2 bits of additional information, described below, this results in a 2
octet value field. However the use of 12 bits was a result from a octet value field. However the use of 12 bits was a consequence of a
design to use a modified exponent/mantissa form with the following design to use a modified exponent/mantissa form with the following
characteristics: characteristics:
o The values represented are to be positive integers starting 1, 2, o The values represented are to be positive integers starting 1, 2,
... ...
o The maximum value represented should be close to, but less than o The maximum value represented should be close to, but less than
2^24 (^ denotes exponentiation in this section). This is so that 2^24 (^ denotes exponentiation in this section). This is so that
with a route limited to no more than 255 hops, the maximum route 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 metric is less than 2^32, i.e., can be stored in 32 bits. (The
link metric value can be stored in 24 bits.) link metric value can be stored in 24 bits.)
A representation, modified from an exponent/mantissa form with e 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 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 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 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. 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 The position in the increment sequence, from 0 to 2^m-1, is
considered as a form of mantissa, and denoted b. The increment considered as a form of mantissa, and denoted a. The increment
sequence number, from 0 to 2^e-1, is considered as a form of sequence number, from 0 to 2^e-1, is considered as a form of
exponent, and denoted a. exponent, and denoted b.
The value represented by (a,b) can then be shown to be equal to (2^m+ 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: a+1)2^b-2^m. To verify this, note that:
o With fixed a, the difference between two values with consecutive o With fixed b, the difference between two values with consecutive
values of b is 2^a, as expected. values of a is 2^b, as expected.
o The value represented by (a,2^m-1) is (2^m+2^m)2^a-2^m. The value o The value represented by (b,2^m-1) is (2^m+2^m)2^b-2^m. The value
represented by (a+1,0) is (2^m+1)(2^(a+1))-2^m. The difference represented by (b+1,0) is (2^m+1)(2^(b+1))-2^m. The difference
between these two values is 2^(a+1), as expected. between these two values is 2^(b+1), as expected.
The maximum represented value has a = 2^e-1 and b = 2^m-1, and is The maximum represented value has b = 2^e-1 and a = 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^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. 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. 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 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 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 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, put the mantissa bits in the second octet. The 12 consecutive bits,
using normal network octet ordering (high first) then represent using network byte order (most significant octet first), then
256a+b. Note that the ordering of these 12 bit representation values represent 256b+a. Note that the ordering of these 12 bit
is the same as the ordering of the 24 bit metric values. In other representation values is the same as the ordering of the 24 bit
words two 12 bit metrics fields can be compared for equality/ordering metric values. In other words, two 12 bit metrics fields can be
as if they were unsigned integers. compared for equality/ordering as if they were unsigned integers.
The four flag bits each represent one kind of metric, defined by its The four flag bits each represent one kind of metric, defined by its
direction (incoming or outgoing) and whether the metric is a link 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 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. metric value may be of any combination of these four kinds of metric.
6. MPRs with Link Metrics 6. MPRs with Link Metrics
MPRs are used for two purposes in OLSRv2. In both cases it is MPR MPRs are used for two purposes in OLSRv2. In both cases it is MPR
selectors that are actually used, MPR selectors being determined from selectors that are actually used, MPR selectors being determined from
skipping to change at page 16, line 35 skipping to change at page 16, line 35
selectors of the originating router. selectors of the originating router.
Metrics interact with these two uses of MPRs differently, as Metrics interact with these two uses of MPRs differently, as
described in the following two sections, and which leads to the described in the following two sections, and which leads to the
requirement for two separate sets of MPRs for these two uses when requirement for two separate sets of MPRs for these two uses when
using metrics. The relationship between these two sets of MPRs is using metrics. The relationship between these two sets of MPRs is
considered in Section 6.3. considered in Section 6.3.
6.1. Flooding MPRs 6.1. Flooding MPRs
MPR selection for flooding can ignore metrics. Selection using any The essential detail of the "flooding MPR" selection specification is
algorithm that ignores metrics, including any allowed by [OLSRv2], that a router must select a set of MPRs such that a message
will produce a flooding solution that works. transmitted by a router, and re-transmitted by all its flooding MPRs,
will reach all of the selecting router's symmetric 2-hop neighbors.
However, that does not mean that metrics cannot be usefully Flooding MPR selection can ignore metrics and produce produce a
considered in selecting such "flooding MPRs". Consider the network solution that meets the required specification. However, that does
in Figure 2, where numbers are metrics of links in the direction away not mean that metrics cannot be usefully considered in selecting
from router A, towards router D. 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 3
A ----- B A ----- B
| | | |
1 | | 1 1 | | 1
| | | |
C ----- D C ----- D
4 4
Figure 2 Figure 2
Which is the better flooding MPR selection by router A: B or C? If Which is the better flooding MPR selection by router A: B or C? If
the metric represents probability of message loss, then clearly the metric represents probability of message loss, then clearly
choosing B maximizes the probability of a message sent by A reaching 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 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 than B does. (Similar arguments about a preference for B can be made
if, for example, the metric represents bandwidth or delay rather than if, for example, the metric represents data rate or delay rather than
probability of loss.) probability of loss.)
However, neither should only the second hop be considered. If this However, neither should only the second hop be considered. If this
example is modified to that in Figure 3, where the numbers still are 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 metrics of links in the direction away from router A, towards router
D: D:
3 3
A ----- B A ----- B
| | | |
skipping to change at page 17, line 40 skipping to change at page 17, line 50
scaled values of delay, or the probability of loss, then selecting C scaled values of delay, or the probability of loss, then selecting C
is clearly better. This indicates that the sum of metrics is an is clearly better. This indicates that the sum of metrics is an
appropriate measure to use to choose between B and C. appropriate measure to use to choose between B and C.
However, this is a particularly simple example. Usually it is not a However, this is a particularly simple example. Usually it is not a
simple choice between two routers as a flooding MPR, each only adding simple choice between two routers as a flooding MPR, each only adding
one router coverage. A more general process, when considering which one router coverage. A more general process, when considering which
router to next add as a flooding MPR, should incorporate the metric router to next add as a flooding MPR, should incorporate the metric
to that router, and the metric from that router to each symmetric 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 neighbor, as well as the number of newly covered symmetric
2-hop neighbors as well as the other factors used in the example 2-hop neighbors, and may include other factors.
algorithm in [OLSRv2].
A candidate algorithm for flooding MPR selection is described in The required specification for flooding MPR selection is in Section
[OLSRv2]. However, note that in [OLSRv2] (as in [RFC3626]), each 18.4 (also using Section 18.3) of [OLSRv2]. which may use the example
router can make its own independent choice of flooding MPRs, and MPR selection algorithm in Appendix A of [OLSRv2]. However, note
flooding MPR selection algorithms, and still interoperate. that (as in [RFC3626]) each router can make its own independent
choice of flooding MPRs, and flooding MPR selection algorithm, and
still interoperate.
Also note that the references above to the direction of the metrics Also note that the references above to the direction of the metrics
is correct: for flooding, directional metrics outward from a router is correct: for flooding, directional metrics outward from a router
are appropriate, i.e., metrics in the direction of the flooding. are appropriate, i.e., metrics in the direction of the flooding.
This is an additional reason for including outward metrics in HELLO This is an additional reason for including outward metrics in HELLO
messages, as otherwise a metric-aware MPR selection for flooding is messages, as otherwise a metric-aware MPR selection for flooding is
not possible. The second hop metrics are outgoing neighbor metrics not possible. The second hop metrics are outgoing neighbor metrics
because the OLSRv2 interface used for a second hop transmission may because the OLSRv2 interface used for a second hop transmission may
not be the same as that used for the first hop reception. not be the same as that used for the first hop reception.
6.2. Routing MPRs 6.2. Routing MPRs
The essential detail of the MPR selection specification in [OLSRv2] The essential detail of the "routing MPR" selection specification is
is that a router must, per OLSRv2 interface, select a set of MPRs that a router must, per OLSRv2 interface, select a set of MPRs such
such that there is a two hop route from each symmetric 2-hop neighbor that there is a two hop route from each symmetric 2-hop neighbor of
of the selecting router to the selecting router, with the the selecting router to the selecting router, with the intermediate
intermediate router on each such route being an MPR of the selecting router on each such route being a routing MPR of the selecting
router. router.
It is sufficient, when using an additive link metric rather than a It is sufficient, when using an additive link metric rather than a
hop count, to require that these "routing MPRs" provide not just a hop count, to require that these routing MPRs provide not just a two
two hop route, but a minimum distance two hop route. In addition, a 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 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 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 than the one hop link from it. (The property that no routes go
through routers with willingness WILL_NEVER is retained. Examples through routers with willingness WILL_NEVER is retained. Examples
below assume that all routers are equally willing, with none having below assume that all routers are equally willing, with none having
willingness WILL_NEVER.) willingness WILL_NEVER.)
For example, consider the network in Figure 4. Numbers are metrics For example, consider the network in Figure 4. Numbers are metrics
of links in the direction towards router A, away from router D. 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 Router A must pick router B as a routing MPR, whereas for minimum hop
skipping to change at page 21, line 15 skipping to change at page 21, line 25
However if routers have more than one OLSRv2 interface, then the However if routers have more than one OLSRv2 interface, then the
process is unchanged, other than that if there is more than one known process is unchanged, other than that if there is more than one known
metric between two routers (on different OLSRv2 interfaces), then, metric between two routers (on different OLSRv2 interfaces), then,
considering symmetric links only (as only these are used for routing) considering symmetric links only (as only these are used for routing)
the smallest link metric, i.e., the neighbor metric, is used. There the smallest link metric, i.e., the neighbor metric, is used. There
is no need to calculate routing MPRs per OLSRv2 interface. That is no need to calculate routing MPRs per OLSRv2 interface. That
requirement results from the consideration of flooding and the need requirement results from the consideration of flooding and the need
to avoid certain "race" conditions, which are not relevant to to avoid certain "race" conditions, which are not relevant to
routing, only to flooding. routing, only to flooding.
A candidate algorithm for routing MPR selection is described in The required specification for routing MPR selection is in Section
[OLSRv2]. However, note that in [OLSRv2] (as in [RFC3626]), each 18.5 (also using Section 18.3) of [OLSRv2]. which may use the example
router can make its own independent choice of routing MPRs, and MPR selection algorithm in Appendix A of [OLSRv2]. However, note
routing MPR selection algorithms, and still interoperate. that (as in [RFC3626]) each router can make its own independent
choice of routing MPRs, and routing MPR selection algorithm, and
still interoperate.
6.3. Relationship Between MPR Sets 6.3. Relationship Between MPR Sets
It would be convenient if the two sets of flooding and routing MPRs 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 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 general, for "good" sets of MPRs they are not. (A reasonable
definition of this is that there is no common minimal set of MPRs.) definition of this is that there is no common minimal set of MPRs.)
If metrics are asymmetrically valued (the two sets of MPRs use If metrics are asymmetrically valued (the two sets of MPRs use
opposite direction metrics), or routers have multiple OLSRv2 opposite direction metrics), or routers have multiple OLSRv2
interfaces (where routing MPRs can ignore this, but flooding MPRs interfaces (where routing MPRs can ignore this, but flooding MPRs
skipping to change at page 26, line 24 skipping to change at page 26, line 24
[RFC5444] Clausen, T., Dean, J., Dearlove, C., and C. Adjih, [RFC5444] Clausen, T., Dean, J., Dearlove, C., and C. Adjih,
"Generalized MANET Packet/Message Format", RFC 5444, "Generalized MANET Packet/Message Format", RFC 5444,
February 2009. February 2009.
[RFC6130] Clausen, T., Dean, J., and C. Dearlove, "Mobile Ad Hoc [RFC6130] Clausen, T., Dean, J., and C. Dearlove, "Mobile Ad Hoc
Network (MANET) Neighborhood Discovery Protocol (NHDP)", Network (MANET) Neighborhood Discovery Protocol (NHDP)",
RFC 6130, April 2011. RFC 6130, April 2011.
[OLSRv2] Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized [OLSRv2] Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized
Link State Routing Protocol version 2", Link State Routing Protocol version 2",
draft-ietf-manet-olsrv2-15.txt (work in progress), draft-ietf-manet-olsrv2-16.txt (work in progress),
May 2012. October 2012.
Appendix A. MPR Routing Property Appendix A. MPR Routing Property
In order that routers can find and use shortest routes in a network In order that routers can find and use shortest routes in a network
while using the minimum reduced topology supported by OLSRv2 (that a while using the minimum reduced topology supported by OLSRv2 (that a
router only advertises its MPR selectors in TC messages), routing MPR router only advertises its MPR selectors in TC messages), routing MPR
selection must result in the property that there are shortest routes selection must result in the property that there are shortest routes
with all intermediate routers being routing MPRs. with all intermediate routers being routing MPRs.
This appendix uses the following terminology and assumptions: This appendix uses the following terminology and assumptions:
 End of changes. 49 change blocks. 
144 lines changed or deleted 147 lines changed or added

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/