Mobile Ad hoc Networking (MANET) C. Dearlove
Internet-Draft BAE Systems Advanced Technology
Intended status: Informational Centre
Expires: January 25, 2008 T. Clausen
LIX, Ecole Polytechnique, France
P. Jacquet
INRIA, France
July 24, 2007
Link Metrics for OLSRv2
draft-dearlove-olsrv2-metrics-00
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 25, 2008.
Copyright Notice
Copyright (C) The IETF Trust (2007).
Dearlove, et al. Expires January 25, 2008 [Page 1]
Internet-Draft OLSRv2 Link Metrics July 2007
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.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4. Link Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.1. Directional Link Metrics . . . . . . . . . . . . . . . . . 7
4.2. Reporting Link Metrics . . . . . . . . . . . . . . . . . . 7
4.3. Defining Link Metrics . . . . . . . . . . . . . . . . . . 8
4.4. Link Metric TLVs . . . . . . . . . . . . . . . . . . . . . 9
4.5. Link Metric Values . . . . . . . . . . . . . . . . . . . . 9
5. MPRs with Link Metrics . . . . . . . . . . . . . . . . . . . . 11
6. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14
8. Security Considerations . . . . . . . . . . . . . . . . . . . 15
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 16
9.1. Normative References . . . . . . . . . . . . . . . . . . . 16
9.2. Informative References . . . . . . . . . . . . . . . . . . 16
Appendix A. MPR Routing Property . . . . . . . . . . . . . . . . 17
Appendix B. Acknowledgements . . . . . . . . . . . . . . . . . . 19
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 20
Intellectual Property and Copyright Statements . . . . . . . . . . 21
Dearlove, et al. Expires January 25, 2008 [Page 2]
Internet-Draft OLSRv2 Link Metrics July 2007
1. Introduction
The Optimized Link State Routing Protocol (OLSRv2) [1] is a proactive
routing protocol for Mobile Ad hoc NETworks (MANETs) [3]. In its
current form, this protocol finds shortest paths from a node to all
possible destinations. Here "shortest" is defined as "minimum number
of hops".
However limiting routing paths to minimum hop paths may use 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 [2] 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, nodes which did and
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 [1]. (A
summary of the required changes is given in Section 6.) It includes
only the additions that are required for extensibility, some possible
extensions beyond this are discussed, but do not form part of this
proposal.
Dearlove, et al. Expires January 25, 2008 [Page 3]
Internet-Draft OLSRv2 Link Metrics July 2007
2. Applicability
The objective of this document is to serve as a basis for discussion
as to whether such a revision of [1], to form part of the basic
OLSRv2 specification, is desirable, or even essential for the
widespread adoption of OLSRv2 that is its objective. It is not
intended to cause a significant delay in the adoption of OLSRv2 as a
Proposed Standard. None of the changes proposed in this document
affect any of the other constituent parts of OLSRv2, in particular
they do not affect [4].
Dearlove, et al. Expires January 25, 2008 [Page 4]
Internet-Draft OLSRv2 Link Metrics July 2007
3. 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 25, 2008 [Page 5]
Internet-Draft OLSRv2 Link Metrics July 2007
its use of [4]) is not a solution to these problems, use of link
quality as so specified allows a node to decline to use a link, 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. It should be noted that changing link metrics is a form of
network topology change, and should be limited to a rate consistent
with the message information update rate (the parameters
HELLO_INTERVAL, HELLO_MIN_INTERVAL, TC_INTERVAL and TC_MIN_INTERVAL).
Dearlove, et al. Expires January 25, 2008 [Page 6]
Internet-Draft OLSRv2 Link Metrics July 2007
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
The first point to note is that a link between OLSRv2 interfaces I
and J, on nodes A and B respectively, must be assigned two metrics,
from I to J and J to I. If instead a single metric is assigned, then
this must be by coordination between nodes A and B, and (apart from
not fitting the OLSRv2 model well) this leads to the possibility
(especially with lossy links, as OLSRv2 is designed to handle) of
nodes A and B disagreeing on the metric for the link, which, as noted
in Section 1, leads to the possibility of routing loops. Note that
this is regardless of that OLSRv2 only uses bidirectional links, the
two directions may have different metrics.
Consequently each node is reponsible for defining the metric in one
direction only. The choice of direction is discussed later in this
section. If node A defines one direction of the link between nodes A
and B, then node B must use node A's definition of that metric.
(Node B may however use a bad mismatch as a reason to discontinue use
of this link, using the link quality mechanism in [4].)
4.2. Reporting Link Metrics
Links, and hence link metrics, are reported in HELLO messages and TC
messages. A node must report the metric in the direction which it
defines in its HELLO messages.
To fit the OLSRv2 model, node A must be responsible for advertising a
link from node A to node B in TC messages. This can be seen by
considering a path connecting single 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 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
Dearlove, et al. Expires January 25, 2008 [Page 7]
Internet-Draft OLSRv2 Link Metrics July 2007
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.
Note that 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. Again this indicates that node
Q is responsible for reporting the metric for the link from Q to R.
Note that if this two hop route formation from HELLO messages were to
be removed from OLSRv2 then HELLO messages would not need to report
outgoing link metrics. This is a possible modification of OLSRv2.
However it turns out (see Section 5) that in HELLO (but not TC)
messages that a node has to report incoming link metrics for MPR
selection. Thus a node may have to report link metrics in both
directions in HELLO messages.
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.
There are two possibilities. First, a node may be responsible for
defining incoming link metrics. In this case the node must attach
that link metric to the case LINK_STATUS == HEARD. Second, a node
may be responsible for defining outgoing link metrics. In this case
there is no need to attach a link metric to the case LINK_STATUS ==
HEARD.
The former case is suggested here because, although it requires some
additional information to be transmitted, in general receiving nodes
have more information available to define link metrics (for example
received signal strength, interference levels and error control
coding statistics).
When a node reports a neighbor node in a HELLO message it may do so
for the first time with LINK_STATUS == HEARD. This report must be
accompanied by the link metric because the receiving node may
immediately consider the link to be symmetric and use it.
Consequently a node must be reponsible for defining the metric for
incoming links. The means by which it does so, and the information
it uses to do so, are outside the scope of OLSRv2.
Dearlove, et al. Expires January 25, 2008 [Page 8]
Internet-Draft OLSRv2 Link Metrics July 2007
Note that this procedure requires a node to immediately decide on a
link metric as soon as the link is usable. This may be too early for
a good decision as to that metric, however a choice must be made
(even if only that a default value is used). It 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.
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 [1]. In particular note that 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).
4.4. Link Metric TLVs
Metric values would naturally be those of a new address block TLV.
For TC messages a single such TLV is required. For HELLO messages,
unless two hop routing using HELLO messages is discontinued, TLVs for
each direction are needed. One of these can be the same as that used
in TC messages. Obvious optimizations are that if only one is
present it is treated as covering both, and if neither is present a
default value is used. These two TLVs could be separate TLV types,
or could be subtypes of the same TLV type.
In HELLO messages link metrics (TLV or default) are required for
addresses with LINK_STATUS == HEARD (incoming metric only) and
LINK_STATUS == SYMMETRIC. Link metrics are also required for
addresses with OTHER_IF == SYMMETRIC; in this case if a node has more
than one possible value (on different interfaces) to report, 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 supports this. 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.
Dearlove, et al. Expires January 25, 2008 [Page 9]
Internet-Draft OLSRv2 Link Metrics July 2007
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 [5]. This specifies a value using a
4 bit mantissa and a 4 bit exponent, so that the value (1 + a/16) *
2^b is represented by the transmitted octet 16 * b + a. This
represents values from a minimum of 1 to a maximum of 63488.
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
256 (a == 0, b == 8). It is also suggested that metric summation be
exact. Since a path cannot have more than 255 links, fixed 28 bit
arithmetic, including 4 fractional bits, is sufficient. (To avoid
fractional bits, 16 * b + a may be considered to instead represent
(16 + a) * 2^b, a range of 16 to 1015808, with a default value of
4096. There is no difference in the transmitted octets or
performance, this is just an implementation issue.)
Dearlove, et al. Expires January 25, 2008 [Page 10]
Internet-Draft OLSRv2 Link Metrics July 2007
5. MPRs with Link Metrics
The essential detail of the current MPR specification is that a node
must (per interface) select a set of MPRs which provide a two hop
path from all symmetric strict 2-hop neighbors, with the intermediate
node being an MPR. Note that with minimum hop paths, the path may be
equally well be considered as to each symmetric strict 2-hop
neighbor, but once directional metrics are considered, the path will
need to be from such nodes. This may be seen from the details in
Appendix A.
It is sufficient (but can be improved on, see [6]) 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. (There may be even shorter three, or more, hop paths, but it
is sufficient to consider only two hop paths.) 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 nodes with
willingness WILL_NEVER, and paths through such nodes, are excluded is
retained.)
For example, in the network in Figure 2 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 2
In the network in Figure 3, node A must pick node C as an MPR,
whereas for minimum hop count routing it would not need to pick any
MPRs.
Dearlove, et al. Expires January 25, 2008 [Page 11]
Internet-Draft OLSRv2 Link Metrics July 2007
2 1
B - A - C
\ |
4 \ | 2
\|
D
Figure 3
In the network in Figure 4, node A must pick both nodes B and C as
MPRs, whereas for minimum hop count routing it could pick either.
D E
|\ /|
| \ 3 / |
| \ / |
1 | \/ | 1
| /\ |
| / \ |
| / 2 \ |
|/ \|
B C
\ |
\ /
3 \ / 2
\ /
A
Figure 4
These last two examples show that use of link metrics may rquire a
node to select more MPRs, and even select MPRs when otherwise it
would not. 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 the reduced advertised topology due to use of
MPRs. MPRs also reduce message flooding, for which the addition of
link metrics has no effect. However using the new definition may
result in more message retransmissions. To avoid this it is possible
to split the definition of MPRs, dividing their functions of relaying
and topology advertisement. This would require two separate TLVs,
replacing the single MPR TLV. In this case it is not necessary for
MPRs for topology advertisement to be calculated per interface, that
is required only for MPRs for message relaying.
Dearlove, et al. Expires January 25, 2008 [Page 12]
Internet-Draft OLSRv2 Link Metrics July 2007
6. Summary
The use of link metrics in OLSRv2 has the following requirements and
consequences (excluding matters which are just editorial in the
specification [1]):
o Allocating two address block TLVs (or two subtypes of one address
block TLV) for link metrics. Note that this can be reduced to one
TLV if two hop routing using HELLO messages is not used in OLSRv2.
o Using both of those TLVs in HELLO messages sent by the node, for
all SYMMETRIC neighbors, and in one direction for all HEARD
neighbors (except when using a default value).
o Using one of those TLVs in TC messages sent by the node to provide
an outgoing link metric for all neighbors.
o A default value of link metric allows a link metric TLV to be
omitted if having that value or if the node does not define non-
default link metrics.
o Replacing the distance specified for a GATEWAY TLV by a link
metric TLV. Attached networks with distance zero should always be
treated as local non-OLSRv2 interfaces, and only reported in HELLO
messages, as described in NHDP [4].
o Adding two link metric elements to Link Tuples and 2-Hop Tuples
and one link metric element to Topology Tuples and Attached
Network Tuples (the latter replacing the current distance). It is
intended to introduce these only in [1], not into NHDP [4], in the
same manner as for MPRs. This is because not all alternative uses
of NHDP will need such metrics.
o The processing of HELLO and TC messages must be modified to update
these new link metric elements in the indicated Tuples.
o The definition of the required properties of the MPRs that a node
selects will need to be modified. This may divide the two roles
that MPRs perform (link advertisement and message relaying),
determining them separately.
o The definition of the Network Topology Graph is slightly modified
by the use of these link metrics. The definition of the updating
of the Routing Set is then unchanged (except that for equal
distance paths, one with fewer hops is to be preferred). A
Routing Tuple will need to record both a hop count and a path
metric.
Dearlove, et al. Expires January 25, 2008 [Page 13]
Internet-Draft OLSRv2 Link Metrics July 2007
7. IANA Considerations
This document presents no IANA considerations.
Dearlove, et al. Expires January 25, 2008 [Page 14]
Internet-Draft OLSRv2 Link Metrics July 2007
8. Security Considerations
This document does not specify any security considerations.
Dearlove, et al. Expires January 25, 2008 [Page 15]
Internet-Draft OLSRv2 Link Metrics July 2007
9. References
9.1. Normative References
[1] Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized Link
State Routing Protocol version 2",
draft-ietf-manet-olsrv2-04.txt (work in progress), July 2007.
[2] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized
MANET Packet/Message Format", work in
progress draft-ietf-manet-packetbb-08.txt, July 2007.
9.2. Informative References
[3] Macker, J. and S. Corson, "Mobile Ad hoc Networking (MANET):
Routing Protocol Performance Issues and Evaluation
Considerations", RFC 2501, January 1999.
[4] Clausen, T., Dearlove, C., and J. Dean, "MANET Neighborhood
Discovery Protocol (NHDP)", work in
progress draft-ietf-manet-nhdp-04.txt, June 2007.
[5] Clausen, T. and C. Dearlove, "Representing multi-value time in
MANETs", Work In Progress draft-ietf-manet-timetlv-01.txt,
June 2007.
[6] Baccelli, E., Jacquet, P., Clausen, T., and D. Nguyen, "OSPF MPR
Extension for Ad Hoc Networks", Work In
Progress draft-baccelli-ospf-mpr-ext-03.txt, February 2007.
Dearlove, et al. Expires January 25, 2008 [Page 16]
Internet-Draft OLSRv2 Link Metrics July 2007
Appendix A. MPR Routing Property
In order that nodes can find and use shortest paths in a network
while using the minimum reduced topology supported by OLSRv2 (that a
node only advertises its MPR selectors in TC messages) that 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 this property the routable path property.
This appendix shows that the 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. (OLSRv2 will only use links which are
symmetric, but with possibly different metrics in each direction, but
this is not necessary here. In fact a node can never use a link in
both directions, even in different routes, when using shortest path
routing with positive link metrics.) It considers links to be
between nodes; OLSRv2 actually treat each local interface separately
(creating a set of MPRs for each local interface before unifying
them). The network considered here may be regarded as that for a
single local interface.
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.
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
Dearlove, et al. Expires January 25, 2008 [Page 17]
Internet-Draft OLSRv2 Link Metrics July 2007
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
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 25, 2008 [Page 18]
Internet-Draft OLSRv2 Link Metrics July 2007
Appendix B. 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 25, 2008 [Page 19]
Internet-Draft OLSRv2 Link Metrics July 2007
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 25, 2008 [Page 20]
Internet-Draft OLSRv2 Link Metrics July 2007
Full Copyright Statement
Copyright (C) The IETF Trust (2007).
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.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
Dearlove, et al. Expires January 25, 2008 [Page 21]