RFC 8218
Multipath Extension for the Optimized Link State Routing Protocol Version 2 (OLSRv2)
RFC 8218: Multipath Extension for OLSRv2 🦋
okay bestie, this is RFC 8218 🎀. The title is "Multipath Extension for the Optimized Link State Routing Protocol Version 2 (OLSRv2)" and it's dated August 2017. The category is Experimental 🧪 and the ISSN is 2070-1721. The authors are J. Yi from Ecole Polytechnique and B. Parrein from the University of Nantes 💜. The title block doesn't list anything this doc obsoletes or updates ✨.
Abstract 💖
okay so this doc specifies a multipath extension for OLSRv2 that finds multiple disjoint paths for Mobile Ad Hoc Networks (MANETs) 🌸. MANETs are giving dynamic topology, so using multiple paths can boost aggregated throughput and improve reliability by avoiding single route failures 🚀. The best part? Interoperability with OLSRv2 is retained 🫶.
Status of This Memo 📜
This document is not an Internet Standards Track specification; it's published for examination, experimental implementation, and evaluation 🧪.
This doc defines an Experimental Protocol for the Internet community. It's a product of the Internet Engineering Task Force (IETF) and represents the consensus of the IETF community 💅. It got public review and was approved for publication by the Internet Engineering Steering Group (IESG). Not all IESG-approved docs are candidates for any level of Internet Standard, so see Section 2 of RFC 7841 if you want the deets 🤓.
For info on the current status of this doc, any errata, and how to give feedback, check http://www.rfc-editor.org/info/rfc8218 🔗.
Copyright Notice ©️
Copyright (c) 2017 IETF Trust and the persons identified as the document authors. All rights reserved 💜.
This doc is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as in effect on the date of publication. Please review these carefully, bestie, because they describe your rights and restrictions with respect to this doc 📖. Code Components extracted from this doc must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions, and they're provided without warranty as described in the Simplified BSD License ⚠️.
Table of Contents 📚
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Motivation and Experiments to Be Conducted . . . . . . . 4
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 7
3. Applicability Statement . . . . . . . . . . . . . . . . . . . 7
4. Protocol Overview and Functioning . . . . . . . . . . . . . . 8
5. Parameters and Constants . . . . . . . . . . . . . . . . . . 9
5.1. Router Parameters . . . . . . . . . . . . . . . . . . . . 9
6. Packets and Messages . . . . . . . . . . . . . . . . . . . . 10
6.1. HELLO and TC messages . . . . . . . . . . . . . . . . . . 10
6.1.1. SOURCE_ROUTE TLV . . . . . . . . . . . . . . . . . . 10
6.2. Datagram . . . . . . . . . . . . . . . . . . . . . . . . 11
6.2.1. Source Routing Header in IPv4 . . . . . . . . . . . . 11
6.2.2. Source Routing Header in IPv6 . . . . . . . . . . . . 11
7. Information Bases . . . . . . . . . . . . . . . . . . . . . . 11
7.1. SR-OLSRv2 Router Set . . . . . . . . . . . . . . . . . . 11
7.2. Multipath Routing Set . . . . . . . . . . . . . . . . . . 12
8. Protocol Details . . . . . . . . . . . . . . . . . . . . . . 12
8.1. HELLO and TC Message Generation . . . . . . . . . . . . . 12
8.2. HELLO and TC Message Processing . . . . . . . . . . . . . 13
8.3. MPR Selection . . . . . . . . . . . . . . . . . . . . . . 13
8.4. Datagram Processing at the MP-OLSRv2 Originator . . . . . 14
8.5. Multipath Calculation . . . . . . . . . . . . . . . . . . 15
8.5.1. Requirements of Multipath Calculation . . . . . . . . 15
8.5.2. Multipath Dijkstra Algorithm . . . . . . . . . . . . 16
8.6. Multipath Routing Set Updates . . . . . . . . . . . . . . 18
8.7. Datagram Forwarding . . . . . . . . . . . . . . . . . . . 18
9. Configuration Parameters . . . . . . . . . . . . . . . . . . 18
10. Security Considerations . . . . . . . . . . . . . . . . . . . 19
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20
11.1. Message TLV Types . . . . . . . . . . . . . . . . . . . 20
12. References . . . . . . . . . . . . . . . . . . . . . . . . . 21
12.1. Normative References . . . . . . . . . . . . . . . . . . 21
12.2. Informative References . . . . . . . . . . . . . . . . . 22
Appendix A. Examples of Multipath Dijkstra Algorithm . . . . . . 24
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 25
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 261. Introduction ✨
okay so OLSRv2 [RFC7181] is a proactive link state protocol made for MANETs 🌐. It keeps generating routing messages periodically to create and maintain a Routing Set, which holds routing info to all the possible destinations in the routing domain 🗺️. For each destination there's a unique Routing Tuple that tells you the next hop to reach it 🎯.
This doc specifies an extension of the OLSRv2 protocol [RFC7181] that gives you multiple disjoint paths when that's appropriate for a source-destination pair 🦋. Because MANETs are giving [RFC2501] dynamic topology, having multiple paths totally helps with increasing network throughput, improving forwarding reliability, and load-balancing 💅.
Multipath OLSRv2 (MP-OLSRv2), specified in this doc, uses the Multipath Dijkstra Algorithm by default 🧚. It explores multiple disjoint paths from a source router to a destination router, based on the topology info obtained through OLSRv2, and forwards datagrams in a load-balancing manner using source routing 🌈. MP-OLSRv2 is designed to be interoperable with OLSRv2, so it plays nice with the original protocol 🫶.
Part 1 of 6 done!! 💖 Next up: Section 1.1, the motivation and experiments, so stay tuned 🎀
1.1. Motivation and Experiments to Be Conducted ✨
okay so this doc is an experimental extension of OLSRv2 that can boost data forwarding reliability in dynamic, high-load MANET scenarios 💖. It does this by sending datagrams over multiple disjoint paths using source routing. Why? Lowkey genius, bestie 👀
- Disjoint paths can avoid single route failures. 🛟
- Sending datagrams through parallel paths can increase aggregated throughput. 🚀
- Some scenarios may require that some routers must (or must not) be used. 🙅♀️
- Having control of the paths at the source benefits the load-balancing and traffic engineering. 🎀
- It pairs with Forward Error Correction (FEC) coding applied across packets (erasure coding) [WPMC11] 🧚. Packet drops are usually bursty on a path (for example, because of a route failure), so erasure coding is less effective in single path routing protocols 😭. Give it multiple disjoint paths, though, and erasure coding with multipath gets way more resilient to routing failures. main character energy 👑
In existing deployments, running code and simulations have proven that the multipath extension for OLSRv2 is interesting in certain networks [GIIS14][WCNC08][ADHOC11] 🌈. Still, more experiments and experiences are needed to understand the effects of the protocol specified in this Experimental RFC 🔬. The multipath extension for OLSRv2 is expected to be revised and documented as a Standards Track RFC once enough operational experience is collected 📚. Beyond general experiences (including the protocol specification and interoperability with base OLSRv2 implementations), these aspects are highly appreciated 🫶:
- Optimal values for the number of multiple paths (
NUMBER_OF_PATHS, see Section 5) to be used. This depends on the network topology and router density 🕸️. - Optimal values used in the metric functions. Metric functions are applied to increase the metric of used links and nodes so as to obtain disjoint paths. What kind of disjointness is desired (node disjoint or link disjoint) may depend on the Layer 2 protocol used, and it can be achieved by applying different sets of metric functions 🧩.
- Use of different metric types. This multipath extension can be used with metric types that meet the requirement of OLSRv2, such as [RFC7779] 📏. The metric type used also affects the choice of metric functions, as mentioned in the previous bullet point.
- The impact of partial topology information on multipath calculation. OLSRv2 maintains a partial topology information base to reduce protocol overhead. Experience has shown that multiple paths can be obtained even with such partial information. However, depending on the Multipoint Relay (MPR) selection algorithm used, the disjointness of the multiple paths might be impacted 🤔.
- Use of IPv6 loose source routing. In the current specification, only strict source routing is used for IPv6, based on [RFC6554]. [IPv6-SRH] also proposes loose source routing for IPv6. In scenarios where the length of the source routing header is critical, loose source routing can be considered 📦.
- Optimal choice of "key" routers for loose source routing. In some cases, loose source routing is used to reduce overhead or for interoperability with OLSRv2 routers. Apart from the basic rules defined in the following parts of this document, optimal choices of routers to put in the loose source routing header can be further studied 🗝️.
- Different path-selection schedulers. Depending on the application type and transport layer type, either a per-flow scheduler or a per-datagram scheduler is applied. By default, the traffic load should be equally distributed across multiple paths. In some scenarios, weighted scheduling can be considered. For example, paths with lower metrics (i.e., higher quality) can transfer more datagrams or flows than paths with higher metrics ⚖️.
- The impacts of delay variation due to multipath routing. [RFC2991] raises some concerns about multipath routing, especially variable latencies when per-datagram scheduling is applied. Although current experiment results show that multipath routing can reduce jitter in dynamic scenarios, some transport protocols or applications may be sensitive to datagram reordering 😬.
- The disjoint multipath protocol has an interesting application with erasure coding, especially for services like video/audio streaming [WPMC11]. Combining erasure coding mechanisms with this extension is thus encouraged 🎬.
- Different algorithms to obtain multiple paths, other than the default Multipath Dijkstra Algorithm introduced in Section 8.5.2 of this specification 🧠.
- The use of multitopology information. By using [RFC7722], multiple topologies using different metric types can be obtained. There is no work yet defining how this extension can make use of the multitopology information base, so experimenting with multiple metrics for building multiple paths is encouraged 🌟.
Comments are solicited and should be addressed to the MANET working group's mailing list at manet@ietf.org and/or the authors 💌.
2. Terminology 💖
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here 🔠.
This document uses the terminology and notation defined in [RFC5444], [RFC6130], and [RFC7181]. It also defines the following terminology 📖:
OLSRv2 Routing Process: A routing process based on [RFC7181], without the multipath extension specified in this document.
MP-OLSRv2 Routing Process: A Multipath Routing Process based on this specification as an extension to [RFC7181].
SR-OLSRv2 Routing Process: An OLSRv2 Routing Process that supports Source Routing (SR) or an MP-OLSRv2 Routing Process.
3. Applicability Statement 🦋
As an extension of OLSRv2, this specification is applicable to MANETs for which OLSRv2 is applicable (see [RFC7181]). It can operate on single or multiple interfaces to discover multiple disjoint paths from a source router to a destination router 🗺️. MP-OLSRv2 is designed for networks with dynamic topology, so it avoids single route failure. It can also provide higher aggregated throughput and load-balancing 🚀.
In a router supporting MP-OLSRv2, MP-OLSRv2 does not necessarily replace OLSRv2 completely. The extension can be applied to certain applications that suit multipath routing (mainly video or audio streams), based on information such as a Diffserv codepoint [RFC2474] 🎥.
Compared to OLSRv2, this extension does not introduce any new message type. Instead, a new Message TLV Type is introduced to identify the routers that support forwarding based on the source routing header 🏷️. It is interoperable with OLSRv2 implementations that do not have this extension. Because MP-OLSRv2 uses source routing, interoperability in IPv4 networks is achieved using loose source routing headers. In IPv6 networks, it is achieved by eliminating routers that do not support IPv6 strict source routing 🤝.
MP-OLSRv2 supports two different but interoperable multipath calculation approaches: proactive and reactive. In the proactive calculation, the paths to all the destinations are calculated before they are needed. In the reactive calculation, only the paths to desired destination(s) are calculated on demand. The proactive approach requires more computational resources than the reactive one. The reactive approach requires the IP forwarding plane to trigger the multipath calculation ⏱️.
MP-OLSRv2 forwards datagrams using the source routing header. As there are multiple paths to each destination, MP-OLSRv2 requires the IP forwarding plane to be able to choose which source route to put in the source routing header, based on the path scheduler defined by MP-OLSRv2 🧭. For IPv4 networks, implementation of loose source routing is required following [RFC791]. For IPv6 networks, implementation of strict source routing is required, following the source routing header generation and processing defined in [RFC6554] 🛠️.
4. Protocol Overview and Functioning 🌸
This specification uses OLSRv2 [RFC7181] to 🔎:
- Identify all the reachable routers in the network.
- Identify a sufficient subset of links in the network so that routes can be calculated to all reachable destinations.
- Provide a Routing Set containing the shortest routes from this router to all destinations.
In addition, the MP-OLSRv2 Routing Process identifies the routers that support source routing by adding a new Message TLV in HELLO and Topology Control (TC) messages 📨. Based on the information acquired above, every MP-OLSRv2 Routing Process is aware of a reduced topology map of the network and of the routers supporting source routing 🗺️.
A Multipath Routing Set containing the multipath information is maintained. It may be either proactively calculated or reactively calculated 🧮:
- In the proactive approach, multiple paths to all possible destinations are calculated and updated based on control message exchange. The routes are thus available before they are actually needed 🌅.
- In the reactive approach, a multipath algorithm is invoked on demand, i.e., only when there is a datagram to be sent from the source to the destination and there is no available Routing Tuple in the Multipath Routing Set. This requires the IP forwarding information base to trigger the multipath calculation specified in Section 8.5 when no Multipath Routing Tuple is available. The reactive operation is local to the router, and no additional exchange of routing control messages is required. When the paths are being calculated, the datagrams SHOULD be buffered unless the router does not have enough memory 🧺.
Routers in the same network may choose either proactive or reactive multipath calculation independently, according to their computation resources 💻. The Multipath Dijkstra Algorithm (defined in Section 8.5) is introduced as the default algorithm to generate multiple disjoint paths from a source to a destination, and such information is kept in the Multipath Routing Set 🌈.
The datagram is forwarded based on source routing. When there is a datagram to be sent to a destination, the source router acquires a path from the Multipath Routing Set. The path information is stored in the datagram header using the source routing header 🎀.
5. Parameters and Constants 👑
In addition to the parameters and constants defined in [RFC7181], this specification uses the parameters and constants described in this section 🧁.
5.1. Router Parameters 🦋
okay so these are the knobs each router gets to turn 🎛️
NUMBER_OF_PATHS: how many paths the router wants 🛣️✨MAX_SRC_HOPS: the max number of hops allowed in the source routing header. Setting it to 0 means there's no limit 🙌 BUT in an IPv6 network it MUST be set to 0, because [RFC6554] only supports strict source routing 💅 That means every intermediate router MUST be listed in the source routing header, so the number of hops can vary. In an IPv4 network it MUST be strictly less than 11 and greater than 0, because of the length limit on the IPv4 header 😭CUTOFF_RATIO: the ratio that sets the max metric a path can have compared to the shortest path in the OLSRv2 Routing Set 🌈 For example, if the metric to a destination isR_metricbased on the Routing Set, then the max metric allowed for a path isCUTOFF_RATIO * R_metric. CUTOFF_RATIO MUST be greater than or equal to 1. Set it low and you're less likely to find extra paths. Like, setting it to 1 means only equal length paths get considered 🫶SR_TC_INTERVAL: the max time between two successive TC messages sent by an MP-OLSRv2 Routing Process ⏰SR_HOLD_TIME: the min value in the TLV with Type =VALIDITY_TIMEthat's included in TC messages generated based onSR_TC_INTERVAL🎀
6. Packets and Messages 💖
okay this part is where the datagrams get their glow-up ✨ This extension uses the routing control messages HELLO and TC, as defined in OLSRv2 [RFC7181], to get network topology info 🗺️ For the datagram to support source routing, a source routing header gets added to every datagram routed by this extension. Which header you get depends on the IP version, and that's what this section is about 💅
6.1. HELLO and TC messages 🌸
HELLO and TC messages used by the MP-OLSRv2 Routing Process use the same format as in [RFC7181] ✔️ The new part is a new Message TLV Type that identifies the originator of a HELLO or TC message that supports source-route forwarding. This new Message TLV Type is there so MP-OLSRv2 can work as an extension of OLSRv2 🧚 Only routers that support source-route forwarding can be put in the source routing header of a datagram, because adding a router that doesn't understand the source routing header will cause routing failure 😭 not the vibe!!
6.1.1. SOURCE_ROUTE TLV 🍓
The SOURCE_ROUTE TLV is a Message TLV that signals the message was generated by a router that supports source-route forwarding. It can come from an MP-OLSRv2 Routing Process, or from an OLSRv2 Routing Process that supports source-route forwarding 🦋
Every HELLO or TC message generated by an MP-OLSRv2 Routing Process MUST have exactly one SOURCE_ROUTE TLV, and that TLV has no value 💜
Every HELLO or TC message generated by an OLSRv2 Routing Process MUST have exactly one SOURCE_ROUTE TLV, if that OLSRv2 Routing Process supports source-route forwarding and is willing to join the source route generated by other MP-OLSRv2 Routing Processes 🫶 The existence of the SOURCE_ROUTE TLV MUST be consistent for a specific OLSRv2 Routing Process. So either it adds the SOURCE_ROUTE TLV to all of its HELLO/TC messages, or it doesn't add it to any of them. No mixing and matching, bestie 🙅♀️
6.2. Datagram 🎀
6.2.1. Source Routing Header in IPv4 🌈
In IPv4 [RFC791] networks, the MP-OLSRv2 Routing Process uses the loose source routing header, as defined in [RFC791]. It's an option header with option class 0 and option number 3 ✨
The source route info is kept in the route data field of the loose source routing header 📦
6.2.2. Source Routing Header in IPv6 🧚
In IPv6 [RFC8200] networks, the MP-OLSRv2 Routing Process uses the source routing header defined in Section 3 of [RFC6554], with IPv6 Routing Type 3 👑
The source route info is kept in the Addresses field of the routing header 💅
7. Information Bases 🦋
Each MP-OLSRv2 Routing Process keeps the information bases defined in [RFC7181]. On top of that, this specification uses a Multipath Information Base 🗂️ It includes the protocol sets defined below, so let's go 💖
7.1. SR-OLSRv2 Router Set 🌸
The SR-OLSRv2 Router Set records the routers that support source-route forwarding ✨ That includes routers running the MP-OLSRv2 Routing Process and routers running the OLSRv2 Routing Process with source-route forwarding support. The set is made of SR-OLSRv2 Routing Tuples that look like this:
(SR_addr, SR_time)where:
SR_addris the originator address of the router that supports source-route forwarding.SR_timeis the time until which the SR-OLSRv2 Routing Tuple is considered valid ⏳
7.2. Multipath Routing Set 🛣️
The Multipath Routing Set records the full path info for the different paths to a destination 🗺️ It's made of Multipath Routing Tuples that look like this:
(MR_dest_addr, MR_path_set)where:
MR_dest_addris the network address of the destination. It's either the network address of an interface of a destination router, or the network address of an attached network 🏠MP_path_setcontains the multiple paths to the destination, and it's made of a set of Path Tuples.
Each Path Tuple is defined as:
(PT_metric, PT_address[1], PT_address[2], ..., PT_address[n])where:
PT_metricis the metric of the path to the destination, measured inLINK_METRIC_TYPEas defined in [RFC7181] 📏PT_address[1, ..., n-1]are the addresses of the intermediate routers to be visited, numbered from 1 to n-1. Here n is the number of routers in the path, which is the hop count 🦋
8. Protocol Details 💅
This protocol is based on OLSRv2 and extends it to discover multiple disjoint paths from a source router to a destination router 🌈 It keeps the formats of the basic routing control packets, and the OLSRv2 processing that gets topology info for the network. The main differences from the OLSRv2 Routing Process are the datagram processing at the source router, and datagram forwarding 🧚
8.1. HELLO and TC Message Generation 🎀
HELLO messages are generated according to Section 15.1 of [RFC7181], plus a single message TLV with Type := SOURCE_ROUTE included ✨
TC messages are generated according to Section 16.1 of [RFC7181], plus a single message TLV with Type := SOURCE_ROUTE included ✨
For routers that don't generate TC messages according to [RFC7181], at least one TC message MUST be generated by an MP-OLSRv2 Routing Process during the SR_TC_INTERVAL (Section 5), and that SR_TC_INTERVAL MUST be greater than or equal to TC_INTERVAL. Those TC messages MUST NOT carry any advertised neighbor addresses 🙈 This is how those routers advertise the SOURCE_ROUTE TLV, so the other routers can know which routers are source-route enabled and use them as destinations for multipath routing 💖 The validity time in the VALIDITY_TIME TLV of those TC messages equals SR_HOLD_TIME, which MUST be greater than the SR_TC_INTERVAL. If the TC message carries an optional INTERVAL_TIME TLV, it MUST have a value that encodes the SR_TC_INTERVAL 🍓
8.2. HELLO and TC Message Processing 🦋
HELLO and TC messages are processed according to Sections 15.3 and 16.3 of [RFC7181] 🌸
On top of the reasons [RFC7181] gives for discarding a HELLO or TC message on reception, a HELLO or TC message that's received MUST be discarded if it has more than one Message TLV with Type = SOURCE_ROUTE 🚫
For every HELLO or TC message received, if there's a Message TLV with Type := SOURCE_ROUTE, then create the SR-OLSR Routing Tuple, or update it if it already exists, with:
SR_addr := originator address of the HELLO or TC messageSR_time := current_time + validity time of the TC or HELLO message defined in [RFC7181]
8.3. MPR Selection 🌈
Each MP-OLSRv2 Routing Process selects routing MPRs and flooding MPRs following Section 18 of [RFC7181]. In a mixed network with OLSRv2-only routers, these considerations apply when calculating MPRs 👑
- MP-OLSRv2 routers SHOULD be preferred as routing MPRs, to increase the chance of finding disjoint paths using MP-OLSRv2 routers 💜
- The number of routing MPRs that run the MP-OLSRv2 Routing Process MUST be equal to or greater than NUMBER_OF_PATHS, if there are enough MP-OLSRv2 symmetric neighbors. Otherwise, all the MP-OLSRv2 routers are selected as routing MPRs, except the routers with willingness WILL_NEVER 🫶
8.4. Datagram Processing at the MP-OLSRv2 Originator 💌
okay so bestie, if datagrams without a source routing header need to go over multiple paths (like, based on a Diffserv codepoint [RFC2474] 💅), the MP-OLSRv2 Routing Process goes hunting for a Multipath Routing Tuple where:
MR_dest_addr= destination of the datagram
if it doesn't find a matching Multipath Routing Tuple and the Multipath Routing Set is maintained proactively, that just means there's no multipath route to where the datagram wants to go 🙈 so the datagram gets forwarded following the OLSRv2 Routing Process.
if no matching tuple is found and the set is maintained reactively, the multipath algorithm from Section 8.5 gets invoked to calculate the Multipath Routing Tuple to the destination. if that calculation doesn't return any tuple, the following steps are aborted and the datagram goes the OLSRv2 Routing Process route instead 🦋
if we do get a matching tuple, the Path Tuples of it get applied to the datagrams using either per-flow or per-datagram scheduling, depending on the transport layer protocol and the application. by default it's per-flow scheduling, especially for reordering-sensitive transports like TCP. the path choice gets made on the first datagram, and every later datagram in that same flow uses the same path. if the path breaks before the flow closes, another path with the most similar metric gets used. per-datagram scheduling is recommended if the traffic is insensitive to reordering, like unreliable transmission of media traffic or when erasure coding is applied. in that case, each datagram picks its paths independently ✨
by default, the traffic load should be equally distributed in multiple paths. other path-scheduling mechanisms (e.g., assigning more traffic over better paths) are also possible and will not impact the interoperability of different implementations 🌸
the addresses in PT_address[1, ..., n-1] of the chosen Path Tuple get added to the datagram header as the source routing header. for IPv6 networks, strict source routing is used, so all the intermediate routers in the path are stored in the source routing header following the format defined in Section 3 of [RFC6554] with the Routing Type set to 3 👑
for IPv4 networks, loose source routing is used with these rules:
- Only the addresses that exist in the SR-OLSR Router Set can be added to the source routing header.
- If the length of the path (
n) is greater thanMAX_SRC_HOPS(Section 5), or if adding the whole path information exceeds the MTU, only the "key" routers in the path are kept. By default, the key routers are uniformly chosen in the path. If further information, such as the capacity of the routers (e.g., battery life) or the routers' willingness in forwarding data, is available, the routers with higher capacity and willingness are preferred. 🔋 - The routers that are considered not appropriate for forwarding indicated by external policies should be avoided.
it is not recommended to fragment the IP packet if the packet with the source routing header would exceed the minimum MTU along the path. depending on the size of the routing domain, the MTU should be at least 1280 + 40 (for the outer IP header) + 16 * diameter of the network in number of hops (for the source routing header). if the links in the network have different MTU sizes, by using technologies like Path MTU Discovery, the routers are able to be aware of the MTU along the path 🧚 the size of the datagram plus the size of IP headers (including the source routing header) should not exceed the minimum MTU along the path; otherwise, the source routing should not be used.
if the destination of the datagrams is out of the MP-OLSRv2 routing domain, the datagram must be source routed to the gateway between the MP-OLSRv2 routing domain and the rest of the Internet. The gateway MUST remove the source routing header before forwarding the datagram to the rest of the Internet. that's the gateway's whole job, bestie 🫶
8.5. Multipath Calculation 🧮
8.5.1. Requirements of Multipath Calculation
the Multipath Routing Set maintains the information of multiple paths to the destination. The Path Tuples of the Multipath Routing Set (Section 7.2) are generated based on a multipath algorithm.
for each path to a destination, the algorithm must provide:
- The metric of the path to the destination,
- The list of intermediate routers on the path.
for IPv6 networks, as strict source routing is used, only the routers that exist in the SR-OLSRv2 Router Set are considered in the path calculation, i.e., only the source-routing-supported routers can exist in the path.
after the calculation of multiple paths, the metric of paths (denoted c_i for path i) to the destination is compared to the R_metric of the OLSRv2 Routing Tuple ([RFC7181]) to the same destination. If the metric c_i is greater than R_metric * CUTOFF_RATIO (Section 5), the corresponding path i SHOULD NOT be used. If less than two paths are found with metrics less than R_metric * CUTOFF_RATIO, the router SHOULD fall back to OLSRv2 Routing Process without using multipath routing. This can happen if there are too many OLSRv2-only routers in the network, and requiring multipath routing may result in inferior paths 🙃
by invoking the multipath algorithm, up to NUMBER_OF_PATHS paths are obtained and added to the Multipath Routing Set by creating a Multipath Routing Tuple with:
MR_dest_addr := destination of the datagram.- An
MP_path_setwith calculated Path Tuples. Each Path Tuple corresponds to a path obtained in the Multipath Dijkstra Algorithm, withPT_metric := metric of the calculated pathandPT_address[1, ..., n-1] := list of intermediate routers.
8.5.2. Multipath Dijkstra Algorithm
this section introduces the Multipath Dijkstra Algorithm as a default algorithm. It tries to obtain disjoint paths when appropriate, but it does not guarantee strict disjoint paths. The use of other algorithms is not prohibited, as long as the requirements described in Section 8.5.1 are met. Using different multipath algorithms will not impact the interoperability 🦋
the general principle of the Multipath Dijkstra Algorithm [ADHOC11] is to use the Dijkstra Algorithm for multiple iterations and to look for the shortest path P[i] to the destination d at iteration i. After each iteration, the metric of used links is increased. Compared to the original Dijkstra's algorithm, the main modification consists in adding two incremental functions, named metric functions fp and fe, in order to prevent the next steps resulting in similar paths:
fp(c)is used to increase metrics of arcs belonging to the previous pathP[i-1](withi>1), wherecis the value of the previous metric. This encourages future paths to use different arcs but not different vertices.fe(c)is used to increase metrics of the arcs that lead to intermediate vertices of the previous pathP[i-1](withi>1), wherecis the value of the previous metric. The "lead to" means that only one vertex of the arc belongs to the previous pathP[i-1]while the other vertex does not. The "intermediate" means that the source and destination vertices are not considered.
consider the simple example in Figure 1: a path P[i] S--A--D is obtained at step i. For the next step, the metric of link S--A and A--D are to be increased using fp(c) because they belong to the path P[i]. A--B is to be increased using fe(c) because A is an intermediate vertex of path P[i], and B is not part of P[i]. B--D is unchanged 🎀
B
/ \
/ \
/ \
S---------A-----------D
Figure 1it is possible to choose a different fp and fe to get link-disjoint paths or node-disjoint paths as desired. A recommendation for configuration of fp and fe is given in Section 9.
to get NUMBER_OF_PATHS different paths, for each path P[i] (i = 1, ..., NUMBER_OF_PATHS):
- Run Dijkstra's algorithm to get the shortest path
P[i]for the destinationd. - Apply metric function
fpto the metric of links (in both directions) inP[i]. - Apply metric function
feto the metric of links (in both directions) that lead to routers used inP[i].
a simple example of the Multipath Dijkstra Algorithm is illustrated in Appendix A 📚
8.6. Multipath Routing Set Updates 🔄
The Multipath Routing Set MUST be updated when the Local Information Base, the Neighborhood Information Base, or the Topology Information Base indicate a change (including a change of any potentially used outgoing neighbor metric values) of the known symmetric links and/or attached networks in the MANET, hence, changing the Topology Graph as described in Section 17.7 of [RFC7181]. how the Multipath Routing Set is updated depends on whether the set is maintained reactively or proactively:
- In reactive mode, all the Tuples in the Multipath Routing Set are removed. The new arriving datagrams will be processed as specified in Section 8.4.
- In proactive mode, the routes to all the destinations are updated according to Section 8.5.
8.7. Datagram Forwarding 🚀
in IPv4 networks, datagrams are forwarded using loose source routing as specified in Section 3.1 of [RFC791].
in IPv6 networks, datagrams are forwarded using strict source routing as specified in Section 4.2 of [RFC6554], except the applied routers are MP-OLSRv2 routers rather than RPL routers. The last hop of the source route MUST remove the source routing header. bestie, the last hop has ONE job and it's the header cleanup 💖
9. Configuration Parameters 🎀
okay so this section is where the default values and guidelines live, aka the knobs you can actually turn ⚙️ Network admins might wanna change some or all of them for different network setups. And since this is an experimental protocol, everyone's encouraged to play around with different settings in different environments and send feedback back. bestie science 🧪✨
NUMBER_OF_PATHS := 3. This is how many parallel paths get used in datagram forwarding. Set it to1and the spec becomes identical to OLSRv2 🙈 But going too large can cause unnecessary computational overhead and kinda inferior paths, so don't go wild 💅MAX_SRC_HOPS := 10, for IPv4 networks. For IPv6 networks it MUST be set to0, which means there's no constraint on the max number of hops 🦋CUTOFF_RATIO := 1.5. It MUST be greater than or equal to1💖SR_TC_INTERVAL := 10 x TC_INTERVAL. It MUST be greater than or equal toTC_INTERVAL. It SHOULD be significantly greater thanTC_INTERVALso there aren't unnecessary TC message generations 🧚SR_HOLD_TIME := 3 x SR_TC_INTERVAL. It MUST be greater thanSR_TC_INTERVALand SHOULD allow for a small number of lost messages 🌸
If the Multipath Dijkstra Algorithm is applied, these metric functions come into play 👑
fp(c) := 4*c, wherecis the original metric of the link.fe(c) := 2*c, wherecis the original metric of the link.
The way you set the metric functions fp and fc basically decides how the multiple disjoint paths get preferred 🌈 If id is the identity function, meaning fp(c)=c, there are three possible cases:
- if
id=fe<fp, only increase the metric of related links; - if
id<fe=fp, apply equal increase to the metric of related nodes and links; - if
id<fe<fp, apply greater increase to the metric of related links.
Increasing the metric of related links or nodes just means avoiding those links or nodes when calculating the next path ✨
10. Security Considerations 🔥
okay this section is serious, so buckle up 😭 This MP-OLSRv2 spec is an extension of [RFC7181], which means the security considerations and security architecture illustrated in [RFC7181] also apply here. Implementations without security mechanisms are vulnerable to the threats discussed in [RFC8116] 💀
In a mixed network with OLSRv2-only routers, a compromised router can add SOURCE_ROUTE TLVs in its TC and HELLO messages. That makes other MP-OLSRv2 Routing Processes believe it supports source routing 🙈 This can increase the chance of it being picked as an MPR and getting put into the source routing header. The first part lets someone manipulate how TC messages get flooded, and the second makes the datagram pass through the compromised router. Yikes 😬
As with [RFC7181], a conformant implementation of MP-OLSRv2 MUST, at minimum, implement the security mechanisms specified in [RFC7183] to provide integrity and replay protection of routing control messages 🫶
The MP-OLSRv2 Routing Process MUST drop datagrams entering or exiting an OLSRv2/MP-OLSRv2 routing domain that contain a source routing header. This is non-negotiable, bestie 🚫
Compared to OLSRv2, using the source routing header in this spec introduces vulnerabilities related to source routing attacks. These include bypassing filtering devices, bandwidth exhaustion of certain routers, and so on 😵 Those attacks are discussed in Section 5 of [RFC6554] and [RFC5095]. The influence is still limited to the OLSRv2/MP-OLSRv2 routing domain, because the source routing header is only used in the current routing domain 🛡️
If the multiple paths are calculated reactively, the datagrams SHOULD be buffered while the paths are being calculated. Because the path calculation is local and no control message gets exchanged, the buffering time should be trivial ✨ However, depending on the CPU power and memory of the router, a maximum buffer size SHOULD be set so it doesn't hog too much of the router's memory 🧠 When the buffer is full, the oldest datagrams get dropped.
There's also a possible attack where a malicious application sends a huge amount of datagrams to all the other routers in the network. That triggers path calculation to all the other routers, while the datagrams are buffered, and it might flush other legit datagrams out 😤 But the impact is transient: once the path calculation finishes, the datagrams get forwarded and the buffer goes back to empty 💖
11. IANA Considerations 💅
okay so this section adds one new Message TLV, allocated as a new Type Extension to an existing Message TLV 🎀
11.1. Message TLV Types
This specification updates the "Type 7 Message TLV Type Extensions" registry [RFC7181] by adding the new Type Extension SOURCE_ROUTE, as shown in Table 1 🦋
+-----------+--------------+------------------------+---------------+
| Type | Name | Description | Reference |
| Extension | | | |
+-----------+--------------+------------------------+---------------+
| 2 | SOURCE_ROUTE | Indicates that the | This |
| | | originator of the | specification |
| | | message supports | |
| | | source-route | |
| | | forwarding. No value. | |
+-----------+--------------+------------------------+---------------+
Table 1: SOURCE_ROUTE Type for Type 7 Message TLV Type Extensions12. References 📚
12.1. Normative References
[RFC791] Postel, J., "Internet Protocol", STD 5, RFC 791,
DOI 10.17487/RFC0791, September 1981,
<https://www.rfc-editor.org/info/rfc791>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih,
"Generalized Mobile Ad Hoc Network (MANET) Packet/Message
Format", RFC 5444, DOI 10.17487/RFC5444, February 2009,
<https://www.rfc-editor.org/info/rfc5444>.
[RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc
Network (MANET) Neighborhood Discovery Protocol (NHDP)",
RFC 6130, DOI 10.17487/RFC6130, April 2011,
<https://www.rfc-editor.org/info/rfc6130>.
[RFC6554] Hui, J., Vasseur, JP., Culler, D., and V. Manral, "An IPv6
Routing Header for Source Routes with the Routing Protocol
for Low-Power and Lossy Networks (RPL)", RFC 6554,
DOI 10.17487/RFC6554, March 2012,
<https://www.rfc-editor.org/info/rfc6554>.
[RFC7181] Clausen, T., Dearlove, C., Jacquet, P., and U. Herberg,
"The Optimized Link State Routing Protocol Version 2",
RFC 7181, DOI 10.17487/RFC7181, April 2014,
<https://www.rfc-editor.org/info/rfc7181>.
[RFC7183] Herberg, U., Dearlove, C., and T. Clausen, "Integrity
Protection for the Neighborhood Discovery Protocol (NHDP)
and Optimized Link State Routing Protocol Version 2
(OLSRv2)", RFC 7183, DOI 10.17487/RFC7183, April 2014,
<https://www.rfc-editor.org/info/rfc7183>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.12.2. Informative References
[ADHOC11] Yi, J., Adnane, A., David, S., and B. Parrein, "Multipath
optimized link state routing for mobile ad hoc networks",
Elsevier Ad Hoc Networks, Volume 9, Number 1, pp 28-47,
DOI 10.1016/j.adhoc.2010.04.007, January 2011.
[GIIS14] Macedo, R., Melo, R., Santos, A., and M. Nogueria,
"Experimental performance comparison of single-path and
multipath routing in VANETs", In the Global Information
Infrastructure and Networking Symposium (GIIS), Volume 1,
Number 6, pp 15-19, DOI 10.1109/GIIS.2014.6934283,
September 2014.
[IPv6-SRH] Previdi, S., Ed., Filsfils, C., Raza, K., Leddy, J.,
Field, B., Voyer, D., Bernier, S., Matsushima, S., Leung,
I., Linkova, J., Aries, E., Kosugi, T., Vyncke, E.,
Lebrun, D., Steinberg, D., and R. Raszuk, "IPv6 Segment
Routing Header (SRH)", Work in Progress,
draft-ietf-6man-segment-routing-header-07, July 2017.
[RFC2474] Nichols, K., Blake, S., Baker, F., and D. Black,
"Definition of the Differentiated Services Field (DS
Field) in the IPv4 and IPv6 Headers", RFC 2474,
DOI 10.17487/RFC2474, December 1998,
<https://www.rfc-editor.org/info/rfc2474>.
[RFC2501] Corson, S. and J. Macker, "Mobile Ad hoc Networking
(MANET): Routing Protocol Performance Issues and
Evaluation Considerations", RFC 2501,
DOI 10.17487/RFC2501, January 1999,
<https://www.rfc-editor.org/info/rfc2501>.
[RFC2991] Thaler, D. and C. Hopps, "Multipath Issues in Unicast and
Multicast Next-Hop Selection", RFC 2991,
DOI 10.17487/RFC2991, November 2000,
<https://www.rfc-editor.org/info/rfc2991>.
[RFC5095] Abley, J., Savola, P., and G. Neville-Neil, "Deprecation
of Type 0 Routing Headers in IPv6", RFC 5095,
DOI 10.17487/RFC5095, December 2007,
<https://www.rfc-editor.org/info/rfc5095>.
[RFC7722] Dearlove, C. and T. Clausen, "Multi-Topology Extension for
the Optimized Link State Routing Protocol Version 2
(OLSRv2)", RFC 7722, DOI 10.17487/RFC7722, December 2015,
<https://www.rfc-editor.org/info/rfc7722>.
[RFC7779] Rogge, H. and E. Baccelli, "Directional Airtime Metric
Based on Packet Sequence Numbers for Optimized Link State
Routing Version 2 (OLSRv2)", RFC 7779,
DOI 10.17487/RFC7779, April 2016,
<https://www.rfc-editor.org/info/rfc7779>.
[RFC8116] Clausen, T., Herberg, U., and J. Yi, "Security Threats to
the Optimized Link State Routing Protocol Version 2
(OLSRv2)", RFC 8116, DOI 10.17487/RFC8116, May 2017,
<https://www.rfc-editor.org/info/rfc8116>.
[RFC8200] Deering, S. and R. Hinden, "Internet Protocol, Version 6
(IPv6) Specification", STD 86, RFC 8200,
DOI 10.17487/RFC8200, July 2017,
<https://www.rfc-editor.org/info/rfc8200>.
[WCNC08] Yi, J., Cizeron, E., Hamma, S., and B. Parrein,
"Simulation and Performance Analysis of MP-OLSR for Mobile
Ad hoc Networks", In Proceedings of the IEEE Wireless
Communications and Networking Conference (WCNC),
DOI 10.1109/WCNC.2008.395, 2008.
[WPMC11] Yi, J., Parrein, B., and D. Radu, "Multipath Routing
Protocol for MANET: Application to H.264/SVC Video Content
Delivery", Proceedings of the 14th International Symposium
on Wireless Personal Multimedia Communications, 2011.Appendix A. Examples of Multipath Dijkstra Algorithm 🧚
Okay bestie, time for the examples!! 💅 This appendix has two little walkthroughs of the Multipath Dijkstra Algorithm, so grab your snacks 🍓
Here's the network we're working with 🌸
.-----A-----(2)
(1) / \ \
/ / \ \
S (2) (1) D
\ / \ /
(1) / \ / (2)
B----(3)----C
Figure 2The capital letters are the names of the routers 🦋 The metric can be any value from 1 to 3, because we're using an arbitrary metric here. The starting metric of every link is written in the parentheses. For this example we're using the incremental functions fp(c)=4c and fe(c)=2c, and we want two paths from router S to router D. Iconic request, honestly 👑
On the first run of the Dijkstra Algorithm, we get the shortest path S->A->D, with metric 3 ✨
Now the fun part! The incremental function fp gets applied to the links S-A and A-D, and fe gets applied to the links A-B and A-C. Here's what the metrics look like after the bump 🧁
.-----A-----(8)
(4) / \ \
/ / \ \
S (4) (2) D
\ / \ /
(1) / \ / (2)
B----(3)----C
Figure 3On the second run of the Dijkstra Algorithm, we get the second path S->B->C->D, with metric 6 💖 Two paths, both found, no drama 🎀
Now, as mentioned in Section 8.5, the Multipath Dijkstra Algorithm does not guarantee strict disjoint paths 🙈 Why? To avoid choosing inferior paths, bestie! Check out the topology in Figure 4, where we want two paths from node S to node D. Up top there's a high cost path between S and D 💀
If an algorithm tried to get strict disjoint paths, it would end up with S--B--D and S--(high cost path)--D. Those are extremely unbalanced, and that's giving huge delay variance between the paths, which is not it 😭 But the Multipath Dijkstra Algorithm uses the punishing scheme, so it gets S--B--D and S--B--C--D instead. Way more balanced, periodt 💅
--high cost path-
/ \
/ \
S----B--------------D
\ /
\---C-----/
Figure 4Acknowledgments 🫶
Huge shoutout to Sylvain David, Asmaa Adnane, Eddy Cizeron, Salima Hamma, Pascal Lesage, and Xavier Lecourtier 🌈 They put in the work to develop, implement, and test the specification, and we love a dedicated team! 👑 The authors also had some valuable discussions with Thomas Clausen, Ulrich Herberg, Justin Dean, Geoff Ladwig, Henning Rogge, Marcus Barkowsky, and especially Christopher Dearlove, who gave multiple rounds of reviews during the working group last calls. Main character reviewer energy, no cap 🧚✨
Authors' Addresses 🦋
Here are the authors' contact details, bestie 💌
Jiazi Yi
Ecole Polytechnique
91128 Palaiseau Cedex
France
Phone: +33 (0) 1 77 57 80 85
Email: jiazi@jiaziyi.com
URI: http://www.jiaziyi.com/
Benoit Parrein
University of Nantes
IRCCyN Lab - IVC team
Polytech Nantes, rue Christian Pauc, BP50609
44306 Nantes cedex 3
France
Phone: +33 (0) 2 40 68 30 50
Email: Benoit.Parrein@polytech.univ-nantes.fr
URI: http://www.irccyn.ec-nantes.fr/~parrein📦 where this page comes from
- ietf: rfc8218 2017-08
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms