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