Internet Engineering Task Force (IETF) C. Dearlove Request for Comments: 7185 BAE Systems ATC Category: Informational T. Clausen ISSN: 2070-1721 LIX, Ecole Polytechnique P. Jacquet Alcatel-Lucent Bell Labs April 2014 Rationale for the Use of Link Metrics in the Optimized Link State Routing Protocol Version 2 (OLSRv2)
AbstractThe Optimized Link State Routing Protocol version 2 (OLSRv2) includes the ability to assign metrics to links and to use those metrics to allow routing by other than minimum hop count routes. This document provides a historic record of the rationale for, and design considerations behind, how link metrics were included in OLSRv2. Status of This Memo This document is not an Internet Standards Track specification; it is published for informational purposes. This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Not all documents approved by the IESG are a candidate for any level of Internet Standard; see Section 2 of RFC 5741. Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc7185. Copyright Notice Copyright (c) 2014 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English. 1. Introduction ....................................................3 2. Terminology .....................................................5 3. Applicability ...................................................5 4. Motivational Scenarios ..........................................5 5. Link Metrics ....................................................7 5.1. Link Metric Properties .....................................7 5.2. Link Metric Types ..........................................8 5.3. Directional Link Metrics ..................................10 5.4. Reporting Link and Neighbor Metrics .......................10 5.5. Defining Incoming Link Metrics ............................12 5.6. Link Metric Values ........................................12 6. MPRs with Link Metrics .........................................14 6.1. Flooding MPRs .............................................14 6.2. Routing MPRs ..............................................16 6.3. Relationship between MPR Sets .............................19 7. Security Considerations ........................................21 8. Acknowledgements ...............................................21 9. Informative References .........................................21 Appendix A. MPR Routing Property .................................23
RFC3626] is a proactive routing protocol for mobile ad hoc networks (MANETs) [RFC2501]. OLSRv1 finds the shortest, defined as minimum number of hops, routes from a router to all possible destinations. Using only minimum hop routes may result in what are, in practice, inferior routes. Some examples are given in Section 4. Thus, one of the distinguishing features of the Optimized Link State Routing Protocol version 2 (OLSRv2) [RFC7181] is the introduction of the ability to select routes using link metrics other than the number of hops. During the development of OLSRv2, the working group and authors repeatedly discussed how and why some choices were made in the protocol specification, particularly at the metric integration level. Some of the issues may be non-intuitive, and this document is presented as a record of the considerations and decisions to provide informational discussion about motivation and historic design choices. This document is intended to be useful as a reference if those questions arise again. Use of the extensible message format [RFC5444] by OLSRv2 has allowed the addition, by OLSRv2, of link metric information to the HELLO messages defined in the MANET Neighborhood Discovery Protocol (NHDP) [RFC6130] as well as inclusion in the Topology Control (TC) messages defined in [RFC7181]. OLSRv2 essentially first determines local link metrics from 1-hop neighbors, these being defined by a process outside OLSRv2, then distributes required link metric values in HELLO messages and TC messages, and then finally forms routes with minimum total link metric. Using a definition of route metric other than number of hops is a natural extension that is commonly used in link state protocols. A metric-based route selection process for OLSRv2 could have been handled as an extension to OLSRv2. However, were this to have been done, OLSRv2 routers that did not implement this extension would not recognize any link metric information and would attempt to use minimum hop-count routes. This would have meant that, in effect, routers that did implement and routers that did not implement this extension would differ over their valuation of links and routes. This would have led to the fundamental routing problem of "looping". Thus, if metric-based route selection were to have been considered only as an extension to OLSRv2, then routers that did implement and routers that did not implement this extension would not have been
able to interoperate. This would have been a significant limitation of such an extension. Link metrics were therefore included as standard in OLSRv2. This document discusses the motivation and design rationale behind how link metrics were included in OLSRv2. The principal issues involved when including link metrics in OLSRv2 were: o Assigning metrics to links involved considering separate metrics for the two directions of a link, with the receiving router determining the metric from transmitter to receiver. A metric used by OLSRv2 may be either of: * A link metric, the metric of a specific link from an OLSRv2 interface of the transmitting router to an OLSRv2 interface of the receiving router. * A neighbor metric, the minimum of the link metrics between two OLSRv2 routers, in the indicated direction. These metrics are necessarily the same when these routers each have a single OLSRv2 interface but may differ when either has more. HELLO messages may include both link metrics and neighbor metrics. TC messages include only neighbor metrics. o Metrics as used in OLSRv2 are defined to be dimensionless and additive. The assignment of metrics, including their relationship to real parameters such as data rate, loss rate, and delay, and the management of the choice of metric, is outside the scope of [RFC7181], which simply uses these metrics in a consistent manner. Within a single MANET, including all components of a temporarily fragmented MANET, a single choice of link metric is used. By use of a registry of metric types (employing extended types of a single Address Block TLV type), routers can be configured to use only a subset of the available metric types. o Node metrics were not included in OLSRv2. Node metrics can be implemented by the addition of the corresponding value to all incoming link metrics by the corresponding router. o The separation of the two functions performed by multipoint relays (MPRs) in OLSRv1, optimized flooding and reduced topology advertisement for routing, into separate sets of MPRs in OLSRv2 [RFC7181], denoted "flooding MPRs" and "routing MPRs". Flooding MPRs can be calculated as in [RFC3626], but the use of link metrics in OLSRv2 can improve the MPR selection. Routing MPRs need a metric-aware selection algorithm. The selection of routing MPRs guarantees the use of minimum distance routes using the
chosen metric, while using only symmetric 2-hop neighborhood information from HELLO messages and routing MPR selector information from TC messages. o The protocol Information Bases defined in OLSRv2 include required metric values. This has included additions to the protocol Information Bases defined in NHDP [RFC6130] when used by OLSRv2. RFC5444], including "message" and "TLV" (type-length-value), are to be interpreted as described there. All terms introduced in [RFC6130], including "MANET interface", "HELLO message", "heard", "link", "symmetric link", "1-hop neighbor", "symmetric 1-hop neighbor", "2-hop neighbor", "symmetric 2-hop neighbor", "symmetric 2-hop neighborhood", and the symbolic constants SYMMETRIC and HEARD, are to be interpreted as described there. All terms introduced in [RFC7181], including "router", "OLSRv2 interface", "willingness", "multipoint relay (MPR)", "MPR selector", "MPR flooding", and the TLV type LINK_METRIC, are to be interpreted as described there. RFC7181]. This document does not prescribe any behavior but explains some aspects of the operation of OLSRv2. Figure 1. A ----- X ----- B \ / \ / Y ------- Z Figure 1 The minimum hop route from A to B is via X. However, if the links A to X and X to B are poor (e.g., have low data rate or are unreliable) but the links A to Y, Y to Z, and Z to B are better (e.g., have reliable high data rate), then the route A to B via Y and Z may be preferred to that via X.
There are other situations where the use of some links should be discouraged, even if the avoidance of them does not show immediately obvious benefits to users. 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 data rate or through being less reliable. However, even if the long-range links have the same characteristics as the short-range links, it may be better to reserve usage of the long- range links for when this usage is particularly valuable -- for example, when the use of one long-range link saves several short- range links, rather than the single link saving that is needed for a minimum hop route. A related case is that of a privileged relay. An example is an aerial router in an otherwise ground-based network. The aerial router may have a link to many, or even all, other routers. That would lead to all routers attempting to send all their traffic (other than to symmetric 1-hop neighbors and some symmetric 2-hop neighbors) via the aerial router. It may, however, be important to reserve that capacity for cases where the aerial router is actually essential, such as if the ground-based portion of the network is not connected. Link metrics provide a possible solution to these scenarios. For example, in Figure 1, the route A to Y to Z to B could be preferred to A to X to B by making the metrics on the former path 1 and those on the latter path 2. The aerial privileged relay could be used only when necessary by giving its links maximal metric values, with much smaller other metric values or, if the aerial link is to be preferred to N ground links, by giving the ground links metric values of 1 while making the sum of the aerial node uplink and downlink metrics equal to N. Other cases may involve attempts to avoid areas of congestion, attempts to route around insecure routers, and attempts by routers to discourage being used as relays due to, for example, limited battery power. OLSRv2 does have another mechanism to aid in this: a router's willingness to act as an MPR. However, there are cases where that cannot help but where use of non-minimum hop routes could. Similarly, note that OLSRv2's optional use of link quality (through its use of [RFC6130]) is not a solution to these problems. Use of link quality as specified in [RFC6130] allows a router to decline to use a link, not only on its own, but on all routers' behalf. It does not, for example, allow the use of a link otherwise determined to be too low quality to be generally useful as part of a route where no better links exist. These mechanisms (link quality and link metrics) solve distinctly different problems.
It should also be noted that the loop-free property of OLSRv2 applies strictly only in the static state. When the network topology is changing and when messages can be lost, it is possible for transient loops to form. However, with update rates appropriate to the rate of topology change, such loops will be sufficiently rare. Changing link metrics is a form of network topology change and should be limited to a rate slower than the message information update rate (defined by the parameters HELLO_INTERVAL, HELLO_MIN_INTERVAL, REFRESH_INTERVAL, TC_INTERVAL, and TC_MIN_INTERVAL).
direction between OLSRv2 interfaces of those routers. When referring to a specific OLSRv2 interface (for example, in a Link Tuple or a HELLO message sent on that OLSRv2 interface), a link metric always refers to a link on that OLSRv2 interface to or from the indicated 1-hop neighbor OLSRv2 interface, while a neighbor metric may be equal to a link metric to and/or from another OLSRv2 interface.
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 maximal 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. In a well-designed network, all routers will use the same metric type. It will not produce good routes if, for example, some link metrics are based on data rate and some on path loss (except to the extent that these may be correlated). How to achieve this is an administrative matter, outside the scope of OLSRv2. In fact, even the actual physical meanings of the metrics is outside the scope of OLSRv2. This is because new metrics may be added in the future, for example, as data rates increase, and may be based on new, possibly non-physical, considerations, for example, financial cost. Each such type will have a metric type number. Initially, a single link metric type zero is defined as indicating a dimensionless metric with no predefined physical meaning. An OLSRv2 router is instructed which single link metric type to use and recognize, without knowing whether it represents delay, probability of loss, data rate, cost, or any other quantity. This recognized link metric type number is a router parameter and subject to change in case of reconfiguration or possibly the use of a protocol (outside the scope of OLSRv2) permitting a process of link metric type agreement between routers. The use of link metric type numbers also suggests the possibility of use of multiple link metric types and multiple network topologies. This is a possible future extension to OLSRv2. To allow for that future possibility, the sending of more than one metric of different physical types, which should otherwise not be done for reasons of efficiency, is not prohibited, but types other than that configured will be ignored. The following three sections assume a chosen single link metric type, of unspecified physical nature.
RFC6130]; note that this is a distinct mechanism from the use of link metrics.) Section 6.2), which requires use of the lowest metric
link between two routers when more than one link exists. This neighbor metric may be using another OLSRv2 interface, and hence, the link metric alone is insufficient. Metrics are also reported in TC messages. It can be shown that these need to be outgoing metrics: o Router A must be responsible for advertising a metric from router A to router B in TC messages. This can be seen by considering a route connecting single OLSRv2 interface routers P to Q to R to S. Router P receives its only information about the link from R to S in the TC messages transmitted by router R, which is an MPR of router S (assuming that only MPR selectors are reported in TC messages). Router S may not even transmit TC messages (if no routers have selected it as an MPR and it has no attached networks to report). So any information about the metric of the link from R to S must also be included in the TC messages sent by router R; hence, router R is responsible for reporting the metric for the link from R to S. o In a more general case, where there may be more than one link from R to S, the TC message must, so that minimum metric routes can be constructed (e.g., by router P), report the minimum of these outgoing link metrics, i.e., the outgoing neighbor metric from R to S. In this example, router P also receives information about the existence of a link between Q and R in the HELLO messages sent by router Q. Without the use of metrics, this link could be used by OLSRv2 for 2-hop routing to router R, using just HELLO messages sent by router Q. For this property (which accelerates local route formation) to be retained (from OLSRv1), router P must receive the metric from Q to R in HELLO messages sent by router Q. This indicates that router Q must be responsible for reporting the metric for the outgoing link from Q to R. This is in addition to the incoming link metric information that a HELLO message must report. Again, in general, this must be the outgoing neighbor metric, rather than the outgoing link metric. In addition, Section 6.1 offers an additional reason for reporting outgoing neighbor metrics in HELLO messages, without which metrics can properly affect only routing, not flooding. Note that there is no need to report an outgoing link metric in a HELLO message. The corresponding 1-hop neighbor knows that value; it specified it. Furthermore, for 2-hop neighborhood use, neighbor metrics are required (as these will, in general, not use the same OLSRv2 interface).
RFC7181], should be used. RFC7181], using a compressed (lossy) representation that occupies 12 bits. The use of 12 bits is convenient because, when combined with 4 flag bits of additional information, described below, this results in a 2-octet value field. However, the use of 12 bits, and thus the availability of 4 flag bits, was a consequence of a design to use a modified exponent/mantissa form with the following characteristics: o The values represented are to be positive integers starting 1, 2, ... o The maximum value represented should be close to, but less than 2^24 (^ denotes exponentiation in this section). This is so that with a route limited to no more than 255 hops, the maximum route metric is less than 2^32, i.e., can be stored in 32 bits. (The link metric value can be stored in 24 bits.)
A representation that is modified from an exponent/mantissa form with e bits of exponent and m bits of mantissa and that has the first of these properties is one that starts at 1, then is incremented by 1 up to 2^m, then has a further 2^m increments by 2, then a further 2^m increments by 4, and so on for 2^e sets of increments. This means that the represented value is never in error by more than a half (if rounding) or one (if truncating) part in 2^m, usually less. The position in the increment sequence, from 0 to 2^m-1, is 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 exponent and denoted b. The value represented by (b,a) can then be shown to be equal to (2^m+a+1)2^b-2^m. To verify this, note that: o With fixed b, the difference between two values with consecutive values of a is 2^b, as expected. o The value represented by (b,2^m-1) is (2^m+2^m)2^b-2^m. The value represented by (b+1,0) is (2^m+1)(2^(b+1))-2^m. The difference between these two values is 2^(b+1), as expected. 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^(2^e+m). The required 24-bit limit can be achieved if 2^e+m = 24. Of the possible (e,m) pairs that satisfy this equation, the pair e = 4, m = 8 was selected as most appropriate and is that used by OLSRv2. It uses the previously indicated e+m = 12 bits. An algorithm for converting from a 24-bit value v to a 12-bit pair (b,a) is given in Section 6.2 of [RFC7181]. As noted above, the 12-bit representation then shares two octets with 4 flag bits. Putting the flag bits first, it is then natural to put the exponent bits in the last four bits of the first octet and to put the mantissa bits in the second octet. The 12 consecutive bits, using network byte order (most significant octet first), then represent 256b+a. Note that the ordering of these 12-bit representation values is the same as the ordering of the 24-bit metric values. In other words, two 12-bit metrics fields can be compared for equality/ordering as if they were unsigned integers. The four flag bits each represent one kind of metric, defined by its direction (incoming or outgoing) and whether the metric is a link metric or a neighbor metric. As indicated by the flag bits set, a metric value may be of any combination of these four kinds of metric.
RFC6130] and extended in [RFC7181]) and determined from received HELLO messages. o Routing. Non-local link information is based on information recorded in this router's Topology Information Base. That information is based on received TC messages. The neighbor information in these TC messages consists of addresses of the originating router's advertised (1-hop) neighbors, as recorded in that router's Neighbor Set (defined in [RFC6130] and extended in [RFC7181]). These advertised neighbors include all of the MPR selectors of the originating router. Metrics interact with these two uses of MPRs differently, as described in the following two sections. This leads to the requirement for two separate sets of MPRs for these two uses when using metrics. The relationship between these two sets of MPRs is considered in Section 6.3. Figure 2, where numbers are metrics of links in the direction away from router A, towards router D.
3 A ----- B | | 1 | | 1 | | C ----- D 4 Figure 2 Which is the better flooding MPR selection by router A: B or C? If the metric represents probability of message loss, then clearly choosing B maximizes the probability of a message sent by A reaching D. This is despite C having a lower metric in its connection to A than B does. (Similar arguments about a preference for B can be made if, for example, the metric represents data rate or delay rather than probability of loss.) However, neither should only the second hop be considered. If this example is modified to that in Figure 3, where the numbers still are metrics of links in the direction away from router A, towards router D, then it is possible that, when A is selecting flooding MPRs, selecting C is preferable to selecting B. 3 A ----- B | | 1 | | 3 | | C ----- D 4 Figure 3 If the metrics represent scaled values of delay or the probability of loss, then selecting C is clearly better. This indicates that the sum of metrics is an appropriate measure to use to choose between B and C. However, this is a particularly simple example. Usually, it is not a simple choice between two routers as a flooding MPR, each only adding one router coverage. When considering which router to next add as a flooding MPR, a more general process should incorporate the metric to that router and the metric from that router to each symmetric 2-hop neighbor as well as the number of newly covered symmetric 2-hop neighbors. Other factors may also be included.
The required specification for flooding MPR selection is in Section 18.4 (also using Section 18.3) of [RFC7181], which may use the example MPR selection algorithm in Appendix B of [RFC7181]. However, note 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 is correct: for flooding, directional metrics outward from a router are appropriate, i.e., metrics in the direction of the flooding. This is an additional reason for including outward metrics in HELLO messages, as otherwise a metric-aware MPR selection for flooding is not possible. The second-hop metrics are outgoing neighbor metrics because the OLSRv2 interface used for a second-hop transmission may not be the same as that used for the first-hop reception. Figure 4. Numbers are metrics of links in the direction towards router A, away from router D. Router A must pick router B as a routing MPR, whereas for minimum hop count routing, it could alternatively pick router C. Note that the use of incoming neighbor metrics in this case follows the same reasoning as for the directionality of metrics in TC messages, as described in Section 5.4.
2 A ----- B | | 1 | | 1 | | C ----- D 3 Figure 4 In Figure 5, where numbers are metrics of links in the direction towards router A and away from router C, router A must pick router B as a routing MPR, but for minimum hop count routing, it would not need to pick any MPRs. 1 A - B \ | 4 \ | 2 \| C Figure 5 In Figure 6, where numbers are metrics of links in the direction towards router A and away from routers D and E, router A must pick both routers B and C as routing MPRs, but for minimum hop count routing, it could pick either. D E |\ /| | \ 3 / | | \ / | 1 | \/ | 1 | /\ | | / \ | | / 2 \ | |/ \| B C \ | \ / 3 \ / 2 \ / A Figure 6
It is shown in Appendix A that selecting routing MPRs according to this definition and advertising only such links (plus knowledge of local links from HELLO messages) will result in selection of lowest total metric routes, even if all links (advertised or not) are considered in the definition of a shortest route. However, the definition noted above as sufficient for routing MPR selection is not necessary. For example, consider the network in Figure 7, where numbers are metrics of links in the direction towards router A, away from other routers; the metrics from B to C and C to B are both assumed to be 2. 1 A ----- B \ / 4 \ / 2 \ / C ----- D ----- E 3 5 Figure 7 Using the above definition, A must pick both B and C as routing MPRs, in order to cover the symmetric 2-hop neighbors C and D, respectively. (C is a symmetric 2-hop neighbor because the route length via B is shorter than the 1-hop link.) However, A only needs to pick B as a routing MPR, because the only reason to pick C as a routing MPR would be so that C can advertise the link to A for routing -- to be used by, for example, E. However, A knows that no other router should use the link C to A in a shortest route because routing via B is shorter. So, if there is no need to advertise the link from C to A, then there is no reason for A to select C as a routing MPR. This process of "thinning out" the routing MPR selection uses only local information from HELLO messages. Using any minimum distance algorithm, the router identifies shortest routes, whether one, two, or more hops, from all routers in its symmetric 2-hop neighborhood. It then selects as MPRs all symmetric 1-hop neighbors that are the last router (before the selecting router itself) on any such route. Where there is more than one shortest distance route from a router, only one such route is required. Alternative routes may be selected so as to minimize the number of last routers -- this is the equivalent to the selection of a minimal set of MPRs in the non- metric case.
Note that this only removes routing MPRs whose selection can be directly seen to be unnecessary. Consequently, if (as is shown in Appendix A) the first approach creates minimum distance routes, then so does this process. The examples in Figures 5 and 6 show that use of link metrics may require a router to select more routing MPRs than when not using metrics and even require a router to select routing MPRs when, without metrics, it would not need any routing MPRs. This may result in more, and larger, messages being generated and forwarded more often. Thus, the use of link metrics is not without cost, even excluding the cost of link metric signaling. These examples consider only single OLSRv2 interface routers. However, if routers have more than one OLSRv2 interface, then the process is unchanged; other than that, if there is more than one known metric between two routers (on different OLSRv2 interfaces), then, considering symmetric links only (as only these are used for routing) the smallest link metric, i.e., the neighbor metric, is used. There is no need to calculate routing MPRs per OLSRv2 interface. That requirement results from the consideration of flooding and the need to avoid certain "race" conditions, which are not relevant to routing, only to flooding. The required specification for routing MPR selection is in Section 18.5 (also using Section 18.3) of [RFC7181], which may use the example MPR selection algorithm in Appendix B of [RFC7181]. However, note that (as in [RFC3626]) each router can make its own independent choice of routing MPRs, and routing MPR selection algorithm, and still interoperate.
In Figure 8, A does not require any flooding MPRs. However, A must select B as a routing MPR. 1 A - B \ | 4 \ | 2 \| C Figure 8 In Figure 9, A must select C and D as routing MPRs. However, A's minimal set of flooding MPRs is just B. In this example, the set of routing MPRs serves as a set of flooding MPRs, but a non-minimal one (although one that might be better, depending on the relative importance of number of MPRs and flooding link metrics). 2 C --- E / / 1 / / 1 / 4 / A --- B \ \ 1 \ \ 1 \ \ D --- F 2 Figure 9 However, this is not always the case. In Figure 10, A's set of routing MPRs must contain B but need not contain C. A's set of flooding MPRs need not contain B but must contain C. (In this case, flooding with A selecting B rather than C as a flooding MPR will reach D but in three hops rather than the minimum two that MPR flooding guarantees.) 2 1 B - C - D | / 1 | / 4 |/ A Figure 10
RFC7181]. There are possible uses for link metrics in the creation of security countermeasures to prefer the use of links that have better security properties, including better availability, to those with poorer security properties. This, however, is beyond the scope of both this document and [RFC7181]. [RFC2501] Corson, S. and J. Macker, "Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations", RFC 2501, January 1999. [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing Protocol (OLSR)", RFC 3626, October 2003.
[RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format", RFC 5444, February 2009. [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)", RFC 6130, April 2011. [RFC7181] Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg, "The Optimized Link State Routing Protocol Version 2", RFC 7181, April 2014.
Specifically, the routable path property is a corollary of the property that for all positive integers n and all distinct nodes X and Z, if there is any path from X to Z of n arcs or fewer, then there is a shortest path, from among those of n arcs or fewer, that is a routable path. This may be called the n-arc routable path property. The n-arc routable path property is trivial for n = 1 and directly follows from the definition of the MPRs of Z for n = 2. Proceeding by induction, assuming the n-arc routable path property is true for n = k, consider the case that n = k+1. Suppose that X - V1 - V2 - ... - Vk - Z is a shortest k+1 arc path from X to Z. We construct a path that has no more than k+1 arcs, has the same or shorter length (hence has the same, shortest, length considering only paths of up to k+1 arcs, by assumption), and is a routable path. First, consider whether Vk is an MPR of Z. If it is not, then consider the two-arc path Vk-1 - Vk - Z. This can be replaced either by a one-arc path Vk-1 - Z or by a two-arc path Vk-1 - Wk - Z, where Wk is an MPR of Z, such that the metric from Vk-1 to Z by the replacement path is no longer. In the former case (replacement one- arc path), this now produces a path of length k, and the previous inductive step may be applied. In the latter case, we have replaced Vk by Wk, where Wk is an MPR of Z. Thus, we need only consider the case that Vk is an MPR of Z. We now apply the previous inductive step to the path X - V1 - ... - Vk-1 - Vk, replacing it by an equal length path X - W1 - ... Wm-1 - Vk, where m <= k, where this path is a routable path. Then, because Vk is an MPR of Z, the path X - W1 - ... - Wm-1 - Vk - Z is a routable path and demonstrates the n-arc routable path property for n = k+1. This thus shows that for any distinct nodes X and Z, there is a routable path using the MPR-reduced topology from X to Z, i.e., that OLSRv2 finds minimum length paths (minimum total metric routes).
http://www.baesystems.com/ Thomas Heide Clausen LIX, Ecole Polytechnique 91128 Palaiseau Cedex France Phone: +33 6 6058 9349 EMail: T.Clausen@computer.org URI: http://www.thomasclausen.org/ Philippe Jacquet Alcatel-Lucent Bell Labs Phone: +33 6 7337 1880 EMail: firstname.lastname@example.org