RFC 7779

Directional Airtime Metric Based on Packet Sequence Numbers for Optimized Link State Routing Version 2 (OLSRv2)

📅 published April 2016, from ietf

okay so this one is an Experimental RFC 🧪 from April 2016 (ISSN 2070-1721). It was written by H. Rogge from Fraunhofer FKIE and E. Baccelli from INRIA 🎀. It doesn't list anything it obsoletes or updates, so it's doing its own thing ✨

Abstract 🌸

This doc specifies a Directional Airtime (DAT) link metric that you can use in Optimized Link State Routing version 2 (OLSRv2) 🦋

Status of This Memo 📋

Okay, the important bit first: this is not an Internet Standards Track spec. It's published so people can examine it, experiment with it, and evaluate it 🧪

It's an Experimental Protocol for the Internet community 💅 It's a product of the Internet Engineering Task Force (IETF) and it reflects the consensus of the IETF community. It went through public review and was approved for publication by the Internet Engineering Steering Group (IESG). Not every IESG-approved doc is a candidate for any level of Internet Standard, so check Section 2 of RFC 5741 if you're curious 🤓

Want the latest status, errata, or a way to send feedback? Head to http://www.rfc-editor.org/info/rfc7779 🔗

Copyright (c) 2016 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 they were on the publication date. Please actually read these, because they lay out your rights and restrictions for this doc 📜 Code Components pulled out of this doc must include Simplified BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come with no warranty, as described in the Simplified BSD License ⚠️

Table of Contents 🗺️

1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
2.  Terminology . . . . . . . . . . . . . . . . . . . . . . . . .   3
3.  Applicability Statement . . . . . . . . . . . . . . . . . . .   4
4.  Directional Airtime Metric Rationale  . . . . . . . . . . . .   5
5.  Metric Functioning and Overview . . . . . . . . . . . . . . .   6
6.  Protocol Constants  . . . . . . . . . . . . . . . . . . . . .   7
7.  Protocol Parameters . . . . . . . . . . . . . . . . . . . . .   8
  7.1.  Recommended Values  . . . . . . . . . . . . . . . . . . .   8
8.  Data Structures . . . . . . . . . . . . . . . . . . . . . . .   8
  8.1.  Initial Values  . . . . . . . . . . . . . . . . . . . . .   9
9.  Packets and Messages  . . . . . . . . . . . . . . . . . . . .  10
  9.1.  Definitions . . . . . . . . . . . . . . . . . . . . . . .  10
  9.2.  Requirements for Using DAT Metric in OLSRv2
        Implementations . . . . . . . . . . . . . . . . . . . . .  10
  9.3.  Link-Loss Data Gathering  . . . . . . . . . . . . . . . .  11
  9.4.  HELLO Message Processing  . . . . . . . . . . . . . . . .  12
10. Timer Event Handling  . . . . . . . . . . . . . . . . . . . .  12
  10.1.  Packet Timeout Processing  . . . . . . . . . . . . . . .  12
  10.2.  Metric Update  . . . . . . . . . . . . . . . . . . . . .  13
11. Security Considerations . . . . . . . . . . . . . . . . . . .  14
12. References  . . . . . . . . . . . . . . . . . . . . . . . . .  14
  12.1.  Normative References . . . . . . . . . . . . . . . . . .  14
  12.2.  Informative References . . . . . . . . . . . . . . . . .  15
Appendix A.  Future Work  . . . . . . . . . . . . . . . . . . . .  17
Appendix B.  OLSR.org Metric History  . . . . . . . . . . . . . .  17
Appendix C.  Link-Speed Stabilization . . . . . . . . . . . . . .  18
Appendix D.  Packet-Loss Hysteresis . . . . . . . . . . . . . . .  19
Appendix E.  Example DAT Values . . . . . . . . . . . . . . . . .  19
Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . .  20
Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  21

1. Introduction 🌷

okay so one of the biggest problems with Optimized Link State Routing (OLSR) [RFC3626] is that it doesn't have a granular link-cost metric between routers 😩 Once people started running OLSR networks in the wild, they found out wireless links can be super variable and totally heterogeneous. A hop count just isn't enough for good OLSR routing 💀

So OLSRv2 [RFC7181] built link metrics right into the core spec 🙌 The OLSRv2 routing metric is an external process, and it can be any dimensionless additive cost function that reports to the OLSRv2 protocol. Iconic behaviour, honestly ✨

The OLSR.org [OLSR.org] implementation has been shipping an Estimated Transmission Count (ETX) metric [MOBICOM04] since 2004, as a proprietary extension 🧃 ETX isn't perfect, but it worked well for a long time in Community Mesh Networks (see Appendix B). Then IEEE 802.11 kept getting faster, and ETX stopped being as efficient 📉 That's one of the reasons people wanted a different metric 🦋

This doc describes a Directional Airtime routing metric for OLSRv2. It's the successor to the ETX-derived metric from OLSR.org, and it's giving accuracy. It takes both the loss rate and the link speed into account, so you get a clearer picture of the links in your network 🔥

This spec lets OLSRv2 deployments use a metric defined by the IETF Mobile Ad Hoc Networks (MANET) working group 🫶 It makes interoperability testing between implementations way easier, and it's meant to be a useful baseline to compare other metrics against, whether you're experimenting with this one or not 🧪 Appendix A has a few possible steps for improving the Directional Airtime metric ✨ Future experiments should also figure out whether the DAT metric is useful for other IETF protocols, both inside and outside the MANET working group. If that happens, this doc could move to the Standards Track or get replaced by an improved document 🚀

2. Terminology 📖

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119] 🎀

The terminology introduced in [RFC5444], [RFC7181], and [RFC6130] is to be interpreted as described in those docs, including the terms "packet", "message" and "TLV" 🧩

On top of that, this doc uses the following terms and notation 👑

  • DAT - Directional Airtime (metric). This is the link metric specified here. It's a directional variant of ETT, and it does not take reverse path loss into account.
  • QUEUE - A first in, first out queue of integers.
  • QUEUE[TAIL] - The most recent element in the queue.
  • add(QUEUE, value) - Adds a new element to the TAIL of the queue.
  • remove(QUEUE) - Removes the HEAD element of the queue.
  • sum(QUEUE) - An operation that returns the sum of all elements in a QUEUE.
  • diff_seqno(new, old) - An operation that returns the positive distance between two elements of the circular sequence number space defined in Section 5.1 of [RFC5444]. Its value is (new - old) if that result is positive. Otherwise, its value is (new - old + 65536) 🌀
  • MAX(a, b) - The maximum of a and b.
  • MIN(a, b) - The minimum of a and b.
  • UNDEFINED - A value that's not in the normal value range of a variable 🙈
  • airtime - The time a transmitted packet blocks the link layer, e.g., a wireless link 📡
  • ETX - Expected Transmission Count. A link metric that's proportional to the number of transmissions needed to successfully send an IP packet over a link 🔁
  • ETT - Estimated Travel Time. A link metric that's proportional to the amount of airtime needed to successfully transmit an IP packet over a link. It doesn't count Layer 2 overhead from preamble, backoff time, and queuing 🕰️

3. Applicability Statement 🧭

The Directional Airtime metric was designed and tested (see [COMNET15]) in wireless IEEE 802.11 OLSRv2 networks [RFC7181] 📶 These networks use link-layer retransmission to increase the delivery probability, and a dynamic rate selection algorithm picks the unicast data rate separately for each neighbor 🔄

As specified in OLSRv2, the metric only calculates the incoming link cost. It doesn't calculate the outgoing metric, and it doesn't decide the link status (heard, symmetric, lost) 🙅‍♀️

The metric works for nodes that can send and receive [RFC5444] packet sequence numbers, and for nodes that can't. Without sequence numbers, the metric calculates packet loss based on HELLO message [RFC6130] timeouts instead 🫧

The metric must learn about the unicast data rate towards each one-hop neighbor from an external process, either by configuration or by an external measurement process. That measurement could come from cross-layer data gathered from the operating system, from an external daemon like Dynamic Link Exchange Protocol [DLEP], or from indirect Layer 3 measurements like packet-pair (see [MOBICOM04]) 🛰️

The metric uses [RFC5444] multicast control traffic to determine the link packet loss. The administrator should take care that link-layer multicast transmissions don't have a higher reception probability than the slowest unicast transmission without retransmission ⚠️ For example, with 802.11g, it might be necessary to increase the data rate of multicast transmissions, e.g., set the multicast data rate to 6 Mbit/s 🐢

The metric can only handle a certain range of packet loss and unicast data rate. The maximum packet loss it can encode is a loss of 7 of 8 packets (87.5%), without link-layer retransmissions 📉 The unicast data rate it can encode is between 1 kbit/s and 2 Gbit/s. This metric was designed for data rates of 1 Mbit/s and hundreds of Mbit/s 💫

4. Directional Airtime Metric Rationale ✨

Okay so the Directional Airtime metric is totally inspired by the ETX [MOBICOM03] and ETT [MOBICOM04] metrics 💅 but it does its own thing in a bunch of ways.

Instead of measuring the combined loss probability of a bidirectional transmission of a packet over a link in both directions, the Directional Airtime metric measures the incoming loss rate and integrates the incoming link speed into the metric cost. There are multiple reasons for this decision 🎀

  • OLSRv2 [RFC7181] defines the link metric as directional costs between routers. 🦋
  • Not all link-layer implementations use acknowledgement mechanisms. Most link-layer implementations that do use them use less airtime and a more robust modulation for the acknowledgement than the data transmission, which makes it more likely for the data transmission to be disrupted compared to the acknowledgement. 😭
  • Incoming packet loss and link speed can be measured locally, while symmetric link loss would need an additional signaling TLV in the HELLO [RFC6130] and would delay metric calculation by up to one HELLO interval. 🧚

The Directional Airtime metric does not integrate the packet size into the link cost. Doing so is not feasible in most link-state routing protocol implementations. The routing decision of most operation systems does not take packet size into account. 🙈

Multiplying all link costs of a topology with the size of a data-plane packet would never change the Dijkstra result in any way. Literally never. 💀

The queue-based packet-loss estimator specified in this document has been tested extensively in the OLSR.org ETX implementation; see Appendix B. The output is the average of the packet loss over a configured time period. Iconic testing era 👑

The metric normally measures the loss of a link by tracking the incoming [RFC5444] packet sequence numbers. Without these packet sequence numbers, the metric does calculate the loss of the link based on the received and lost [RFC6130] HELLO messages. It uses the incoming HELLO interval time (or if not present, the validity time) to decide when a HELLO is lost. 🌸

When a neighbor router resets, its packet sequence number might jump to a random value. The metric tries to detect jumps in the packet sequence number and removes them from the data set because the previously gathered link-loss data should still be valid (see Section 9.3). The link-loss data is only removed from memory when a link times out completely and its Link Set Tuple is removed from the database. Main character energy, the data sticks around until it truly has to go 🫶

5. Metric Functioning and Overview 🌈

The Directional Airtime metric is calculated for each Link Set entry, as defined in [RFC6130], Section 7.1.

The metric processes two kinds of data into the metric value, namely packet-loss rate and link speed. The link speed is taken from an external process not defined in this document. The current packet-loss rate is defined in this document by keeping track of packet reception and packet-loss events. It could also be calculated by an external process with a compatible output. 🍓

MultiplE incoming packet-loss/reception events must be combined into a loss rate to get a smooth metric. Experiments with exponential weighted moving average (EWMA) lead to a highly fluctuating or a slow converging metric (or both). To get a smoother and more controllable metric result, this metric uses two fixed-length queues to measure and average the incoming packet events, one queue for received packets and one for the estimated number of packets sent by the other side of the link. Bestie, EWMA really said "no thanks" 😭

Because the rate of incoming packets is not uniform over time, the queue contains a number of counters, each representing a fixed time interval. Incoming packet-loss and packet-reception events are accumulated in the current queue element until a timer adds a new empty counter to both queues and removes the oldest counter from both. ⭐

In addition to the packet loss stored in the queue, this metric uses a timer to detect a total link loss. For every [RFC6130] HELLO interval in which the metric received no packet from a neighbor, it scales the number of received packets in the queue based on the total time interval the queue represents compared to the total time of the lost HELLO intervals. 🔥

The average packet-loss ratio is calculated as the sum of the 'total packets' counters divided by the sum of the 'packets received' counters. This value is then divided through the current link speed and then scaled into the range of metrics allowed for OLSRv2. 💜

The metric value is then used as L_in_metric of the Link Set (as defined in Section 8.1. of [RFC7181]).

While this document does not add new [RFC5444] elements to HELLO [RFC6130] or TC messages [RFC7181], it works best when both the INTERVAL_TIME message TLV is present in the HELLO messages and when each [RFC5444] packet contains an interface-specific sequence number. It also adds a number of new data entries to be stored for each [RFC6130] link. 🎀

6. Protocol Constants 💖

This specification defines the following constants, which define the range of metric values that can be encoded by the DAT metric (see Table 1). They cannot be changed without making the metric outputs incomparable and should only be changed for a MANET with a very slow or a very fast link layer. See Appendix E for example metric values.

  • DAT_MAXIMUM_LOSS - Fraction of the loss rate used in this routing metric. Loss rate will be between 0/DAT_MAXIMUM_LOSS and (DAT_MAXIMUM_LOSS-1)/DAT_MAXIMUM_LOSS.
  • DAT_MINIMUM_BITRATE - Minimal bitrate in Bit/s used by this routing metric.
                      +---------------------+-------+
                      |         Name        | Value |
                      +---------------------+-------+
                      |   DAT_MAXIMUM_LOSS  |   8   |
                      |                     |       |
                      | DAT_MINIMUM_BITRATE |  1000 |
                      +---------------------+-------+

                      Table 1: DAT Protocol Constants

7. Protocol Parameters 🧚

This specification defines the following parameters for this routing metric. These parameters are:

  • DAT_MEMORY_LENGTH - Queue length for averaging packet loss. All received and lost packets within the queue length are used to calculate the cost of the link.
  • DAT_REFRESH_INTERVAL - Interval in seconds between two metric recalculations as described in Section 10.2. This value SHOULD be smaller than a typical HELLO interval. The interval can be a fraction of a second.
  • DAT_HELLO_TIMEOUT_FACTOR - Multiplier relative to the HELLO_INTERVAL (see Section 5.3.1 of [RFC6130]) after which the DAT metric considers a HELLO as lost.
  • DAT_SEQNO_RESTART_DETECTION - Threshold in the number of missing packets (based on received packet sequence numbers) at which point the router considers the neighbor has restarted. This parameter is only used for loss estimation based on packet sequence numbers. This number MUST be larger than DAT_MAXIMUM_LOSS.

The proposed values of the protocol parameters are for Community Mesh Networks, which mostly use routers that are not mobile. Using this metric for mobile networks might require shorter DAT_REFRESH_INTERVAL and/or DAT_MEMORY_LENGTH.

   DAT_MEMORY_LENGTH  := 64

   DAT_REFRESH_INTERVAL  := 1

   DAT_HELLO_TIMEOUT_FACTOR  := 1.2

   DAT_SEQNO_RESTART_DETECTION  := 256

8. Data Structures 🦋

This specification extends the Link Set of the Interface Information Base, as defined in Section 7.1 of [RFC6130], by the adding the following elements to each Link Tuple:

  • L_DAT_received - A QUEUE with DAT_MEMORY_LENGTH integer elements. Each entry contains the number of successfully received packets within an interval of DAT_REFRESH_INTERVAL.
  • L_DAT_total - A QUEUE with DAT_MEMORY_LENGTH integer elements. Each entry contains the estimated number of packets transmitted by the neighbor, based on the received packet sequence numbers within an interval of DAT_REFRESH_INTERVAL.
  • L_DAT_packet_time - The time when the next [RFC5444] packet should have arrived.
  • L_DAT_hello_interval - The interval between two HELLO messages of the links neighbor as signaled by the INTERVAL_TIME TLV [RFC5497] of NHDP messages [RFC6130].
  • L_DAT_lost_packet_intervals - The estimated number of HELLO intervals from this neighbor from which the metric has not received a single packet.
  • L_DAT_rx_bitrate - The current bitrate of incoming unicast traffic for this neighbor.
  • L_DAT_last_pkt_seqno - The last received packet sequence number received from this link.

Methods to obtain the value of L_DAT_rx_bitrate are out of the scope of this specification. Such methods may include static configuration via a configuration file or dynamic measurement through mechanisms described in a separate specification (e.g., [DLEP]). Any Link Tuple with L_status = HEARD or L_status = SYMMETRIC MUST have a specified value of L_DAT_rx_bitrate if it is to be used by this routing metric.

The incoming bitrate value should be stabilized by a hysteresis filter to improve the stability of this metric. See Appendix D for an example.

This specification updates the L_in_metric field of the Link Set of the Interface Information Base, as defined in Section 8.1. of [RFC7181]).

8.1. Initial Values 🌈

When generating a new tuple in the Link Set, as defined in item 3 of Section 12.5 of [RFC6130], the values of the elements specified in Section 8 are set as follows:

  • L_DAT_received := 0, ..., 0. The queue always has DAT_MEMORY_LENGTH elements.
  • L_DAT_total := 0, ..., 0. The queue always has DAT_MEMORY_LENGTH elements.
  • L_DAT_packet_time := EXPIRED (no earlier [RFC5444] packet received).
  • L_DAT_hello_interval := UNDEFINED (no earlier NHDP HELLO received).
  • L_DAT_lost_packet_intervals := 0 (no HELLO interval without packets).
  • L_DAT_last_pkt_seqno := UNDEFINED (no earlier [RFC5444] packet with sequence number received).

9. Packets and Messages 💜

This section describes the necessary changes of [RFC7181] implementations with DAT metric for the processing and modification of the incoming and outgoing [RFC5444] data.

9.1. Definitions 🎀

For the purpose of this section, note the following definitions:

  • "pkt_seqno" is defined as the [RFC5444] packet sequence number of the received packet.
  • "interval_time" is the time encoded in the INTERVAL_TIME message TLV of a received HELLO message [RFC6130].
  • "validity_time" is the time encoded in the VALIDITY_TIME message TLV of a received HELLO message [RFC6130].

9.2. Requirements for Using DAT Metric in OLSRv2 Implementations 💅

okay bestie, if you're building an OLSRv2 implementation that uses this metric, you SHOULD put these two things into your [RFC5444] output 💖:

  • An INTERVAL_TIME message TLV in each HELLO message, as defined in [RFC6130], Section 4.3.2.
  • An interface-specific packet sequence number as defined in [RFC5444], Section 5.1 that is incremented by 1 for each outgoing [RFC5444] packet on the interface.

so here's the tea 🍵. If you only stick packet sequence numbers on some of your outgoing [RFC5444] packets, this metric is gonna ignore every packet that doesn't have one 💀. And if you only put the INTERVAL_TIME TLV in some HELLO messages, the timeout-based loss detection gets slower 🐢. That part only matters if you're missing packet sequence numbers, but still, be consistent, babe 🫶.

for every incoming [RFC5444] packet, extra processing SHOULD be carried out after the packet's messages have been handled as specified in [RFC6130] and [RFC7181], as described in this section 🌸.

[RFC5444] packets without packet sequence numbers MUST NOT be processed in the way described in this section. no seq number, no entry, periodt 🙅‍♀️.

the router updates the Link Set Tuple for whoever originated the packet 🦋:

  1. If L_DAT_last_pkt_seqno = UNDEFINED, then:
    • L_DAT_received[TAIL] := 1.
    • L_DAT_total[TAIL] := 1.
  2. Otherwise:
    • L_DAT_received[TAIL] := L_DAT_received[TAIL] + 1.
    • diff := diff_seqno(pkt_seqno, L_DAT_last_pkt_seqno).
    • If diff > DAT_SEQNO_RESTART_DETECTION, then:
      • diff := 1.
    • L_DAT_total[TAIL] := L_DAT_total[TAIL] + diff.
  3. L_DAT_last_pkt_seqno := pkt_seqno.
  4. If L_DAT_hello_interval != UNDEFINED, then:
    • L_DAT_packet_time := current time + (L_DAT_hello_interval * DAT_HELLO_TIMEOUT_FACTOR).
  5. L_DAT_lost_packet_intervals := 0.

9.4. HELLO Message Processing 🎀

for each incoming HELLO Message, once it's been processed as defined in Section 12 of [RFC6130], the Link Set Tuple for that incoming HELLO message MUST be updated. no skipping this one, bestie 😤.

  1. If the HELLO message contains an INTERVAL_TIME message TLV, then:
    • L_DAT_hello_interval := interval_time.
  2. Otherwise:
    • L_DAT_hello_interval := validity_time.
  3. If L_DAT_last_pkt_seqno = UNDEFINED, then:
    • L_DAT_received[TAIL] := L_DAT_received[TAIL] + 1.
    • L_DAT_total[TAIL] := L_DAT_total[TAIL] + 1.
    • L_DAT_packet_time := current time + (L_DAT_hello_interval * DAT_HELLO_TIMEOUT_FACTOR).

10. Timer Event Handling ⏰

in addition to the changes in the [RFC5444] processing/generation code, the DAT metric also runs on two timer events 🧚.

10.1. Packet Timeout Processing 💜

when L_DAT_packet_time has timed out, the following step MUST be done 😭:

  1. If L_DAT_last_pkt_seqno = UNDEFINED, then:
    • L_DAT_total[TAIL] := L_DAT_total[TAIL] + 1.
  2. Otherwise:
    • L_DAT_lost_packet_intervals := L_DAT_lost_packet_intervals + 1.
  3. L_DAT_packet_time := L_DAT_packet_time + L_DAT_hello_interval.

10.2. Metric Update 🔥

once every DAT_REFRESH_INTERVAL, all L_in_metric values in all Link Set entries MUST be recalculated. this is the glow-up moment 💅:

  1. sum_received := sum(L_DAT_received).
  2. sum_total := sum(L_DAT_total).
  3. If L_DAT_hello_interval != UNDEFINED and L_DAT_lost_packet_intervals > 0, then:
    • lost_time_proportion := L_DAT_hello_interval * L_DAT_lost_packet_intervals / DAT_MEMORY_LENGTH.
    • sum_received := sum_received * MAX(0, 1 - lost_time_proportion);
  4. If sum_received < 1, then:
    • L_in_metric := MAXIMUM_METRIC, as defined in [RFC7181], Section 5.6.1.
  5. Otherwise:
    • loss := MIN(sum_total / sum_received, DAT_MAXIMUM_LOSS).
    • bitrate := MAX(L_DAT_rx_bitrate, DAT_MINIMUM_BITRATE).
    • L_in_metric := (2^24 / DAT_MAXIMUM_LOSS) * loss / (bitrate / DAT_MINIMUM_BITRATE).
  6. remove(L_DAT_total)
  7. add(L_DAT_total, 0)
  8. remove(L_DAT_received)
  9. add(L_DAT_received, 0)

the calculated L_in_metric value should be stabilized by a hysteresis function, lowkey a must for not being jumpy 🦋. See Appendix D for an example.

11. Security Considerations 🚨

okay, serious moment incoming 🙈. Artificially messing with metric values can drastically change network performance, like, it's giving chaos 💀. Advertising a higher L_in_metric value may decrease the amount of incoming traffic, while advertising a lower L_in_metric may increase the amount of incoming traffic.

for example, an attacker could artificially attract mesh routes and then drop the incoming traffic, which can cause a Denial of Service (DoS) against other mesh nodes 😱. Similarly, an attacker may achieve Man-in-the-Middle (MITM) attacks or traffic analysis by concentrating the traffic routed over a node the attacker controls (and end-to-end encryption is not used or somehow broken). Protection mechanisms against such MITM or DoS attacks are nevertheless out of scope of this document 🫠.

security threats also include potential attacks on the integrity of the control traffic that DAT passively monitors to measure link quality 🕵️‍♀️. For example, an attacker might inject packets pretending to be somebody else and using incorrect sequence numbers. This attack can be prevented by the true originator of the [RFC5444] packets by adding an ICV Packet TLV and TIMESTAMP Packet TLV [RFC7182] to each packet. This lets the receiver drop all incoming packets that have a forged packet source, both packets generated by the attacker or replayed packets. However, the security mechanism described in [RFC7183] does not protect the sequence number used by the DAT metric, because it only signs the [RFC5444] messages, not the [RFC5444] packet header (which contains the [RFC5444] packet sequence number) 🥲.

12. References 📚

12.1. Normative References

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <http://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, <http://www.rfc-editor.org/info/rfc5444>.

[RFC5497] Clausen, T. and C. Dearlove, "Representing Multi-Value Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497, DOI 10.17487/RFC5497, March 2009, <http://www.rfc-editor.org/info/rfc5497>.

[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, <http://www.rfc-editor.org/info/rfc6130>.

[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, <http://www.rfc-editor.org/info/rfc7181>.

12.2. Informative References 🌈

[RFC3626] Clausen, T., Ed. and P. Jacquet, Ed., "Optimized Link State Routing Protocol (OLSR)", RFC 3626, DOI 10.17487/RFC3626, October 2003, <http://www.rfc-editor.org/info/rfc3626>.

[RFC7182] Herberg, U., Clausen, T., and C. Dearlove, "Integrity Check Value and Timestamp TLV Definitions for Mobile Ad Hoc Networks (MANETs)", RFC 7182, DOI 10.17487/RFC7182, April 2014, <http://www.rfc-editor.org/info/rfc7182>.

[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, <http://www.rfc-editor.org/info/rfc7183>.

[COMNET15] Barz, C., Fuchs, C., Kirchhoff, J., Niewiejska, J., and H. Rogge, "OLSRv2 for Community Networks: Using Directional Airtime Metric with external radios", Elsevier Computer Networks 2015, DOI 10.1016/j.comnet.2015.09.022, September 2015, <http://dx.doi.org/10.1016/j.comnet.2015.09.022>.

[CONFINE] "Community Networks Testbed for the Future Internet (CONFINE)", <http://www.confine-project.eu>.

[DLEP] Ratliff, S., Berry, B., Jury, S., Satterwhite, D., and R. Taylor, "Dynamic Link Exchange Protocol (DLEP)", Work in Progress, draft-ietf-manet-dlep-22, April 2016.

[BATMAN] Neumann, A., Aichele, C., Lindner, M., and S. Wunderlich, "Better Approach To Mobile Ad-hoc Networking (B.A.T.M.A.N.)", Work in Progress, draft-wunderlich-openmesh-manet-routing-00, April 2008.

[MOBICOM03] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A High-Throughput Path Metric for Multi-Hop Wireless Routing", Proceedings of the MOBICOM Conference, DOI 10.1145/938985.939000, 2003.

[MOBICOM04] Draves, R., Padhye, J., and B. Zill, "Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks", Proceedings of the MOBICOM Conference, DOI 10.1145/1023720.1023732, 2004.

[OLSR.org] "OLSR.org Wiki", <http://www.olsr.org/>.

[FREIFUNK] "Freifunk Wireless Community Networks", <http://www.freifunk.net>.

[FUNKFEUER] "Austria Wireless Community Network", <http://www.funkfeuer.at>.

Appendix A. Future Work 🔮

as the DAT metric proved to work reasonably well for non- or slow-moving ad hoc networks [COMNET15], it should be considered a solid first step toward better MANET metrics 🎀. There are multiple parts of the DAT metric that need to be reviewed again in the context of real-world deployments, and they can be improved later 🛠️.

the easiest part of the DAT metric to change and test would be the timing parameters. A 1-minute interval for packet-loss statistics might be a good compromise for some MANETs, but it could easily be too large or too small for others 🙃. More data is needed to verify or improve the current parameter selection.

the DAT metric only considers multicast [RFC5444] packet loss when estimating the link, but it would be good to integrate unicast data loss into the loss estimation too 💭. This information could be provided directly from the link layer, and it could increase the accuracy of the loss rate estimation in scenarios where the assumptions about the ratio of multicast vs. unicast loss do not hold.

the packet-loss averaging algorithm could also be improved 🌟. While the DAT metric provides a stable sliding time interval to average the incoming packet loss and does not give recent input too much influence, first experiments suggest that the algorithm tends to be less agile at detecting major changes in link quality. This makes it less suited for mobile networks. A more agile algorithm is needed for detecting major changes while filtering out random fluctuations in frame loss. However, the current "queue of counters" algorithm suggested for DAT outperforms the binary queue algorithm and the exponential aging algorithms used for the ETX metric in the OLSR [RFC3626] codebase of OLSR.org 🏆.

Appendix B. OLSR.org Metric History 🌸

Okay so the Funkfeuer [FUNKFEUER] and Freifunk networks [FREIFUNK] are both wireless community networks built on OLSR [RFC3626] or B.A.T.M.A.N. [BATMAN], with hundreds of routers running permanently. 🛜 The Vienna Funkfeuer network in Austria has 400 routers covering the whole city of Vienna and beyond, spanning roughly 40 km across. It's been giving its users Internet access since 2003. ✨ The iconic part is that it provides Internet access over a city-wide, large-scale Wi-Fi MANET with just a single Internet uplink. Literally wild. 🔥

The OLSR project [OLSR.org] learned from operating these networks that using hop-count as the routing metric leads to unsatisfactory network performance. 😬 So experiments with the ETX metric [MOBICOM03] ran in parallel in the Berlin Freifunk network and the Vienna Funkfeuer network in 2004. The verdict was satisfactory, meaning it was sufficiently easy to implement and gave sufficiently good performance. 💖 It has now been in operational use in these networks for several years.

The ETX metric of a link is the estimated number of transmissions required to successfully send a packet (each packet equal to or smaller than MTU) over that link, until a link-layer acknowledgement is received. 🦋 The ETX metric is additive, so the ETX metric of a path is the sum of the ETX metrics for each link on that path.

ETX is giving reasonable performance, ngl, but it doesn't handle networks with heterogeneous links that have different bitrates very well. 🙈 Since every wireless link is characterised only by its packet-loss ratio, long-ranged links with low bitrate (and low loss ratios) get preferred over short-ranged links with high bitrate (and higher but reasonable loss ratios). When those conditions show up, the network's performance can drop a lot, because the higher-capacity links never get used. 💀

So the OLSR.org project implemented the Directional Airtime metric for OLSRv2, inspired by the Estimated Travel Time (ETT) metric [MOBICOM04]. 👑 This metric uses a unidirectional packet loss, but it also takes the bitrate into account, so it gives a more accurate picture of the relative costs or capabilities of OLSRv2 links. Main character energy. 💅

The DAT metric specifies how to generate a reasonably stable packet-loss rate value from incoming packet reception and loss events. 🌈 The source of the link speed used in this document, though, is considered an external process. Not my problem, bestie, that's on the outside. 🫶

If you're on a Layer 2 technology with variable link speed, the raw link speed is likely to fluctuate too fast to be useful for the DAT metric. 😭

How much stabilization the link speed needs depends on the implementation of the MAC layer, especially the rate-control algorithm. 🍓

Experiments with the Linux 802.11 Wi-Fi stack showed that a simple Median filter over a series of raw link-speed measurements can smooth the calculated value. The bonus is that it doesn't introduce intermediate link-speed values the way averaging or an exponential weighted moving average would. ✨

Appendix D. Packet-Loss Hysteresis 🦋

While the DAT metric uses a sliding window to compute a reasonably stable frame loss, an implementation might choose to add an extra hysteresis to prevent undesirable oscillations between two values (i.e., metric flapping). 🙃

In Section 10.2, DAT calculates a fractional loss rate. The fraction loss := sum_total / sum_received can cause minor fluctuations in the advertised L_in_metric when sum_total or sum_received change only a little. Those little wiggles can cause undesirable protocol churn, and nobody wants that drama. 😤

A hysteresis function applied to the fraction could reduce how often the loss rate changes, and that can help stabilise the metric output even more. 🎀

Appendix E. Example DAT Values 💜

The DAT metric value can be expressed in terms of link speed (bit/s) or used airtime (s). When you use the default protocol constants (see Section 6), DAT encodes link speeds between 119 bit/s and 2 Gbit/s. 🔥

Table 2 has a few examples of metric values and what they mean as a link speed:

             +---------------------------+-----------+
             |           Metric          |   bit/s   |
             +---------------------------+-----------+
             |     MINIMUM_METRIC (1)    |  2 Gbit/s |
             |                           |           |
             | MAXIMUM_METRIC (16776960) | 119 bit/s |
             |                           |           |
             |            2000           |  1 Mbit/s |
             +---------------------------+-----------+

                  Table 2: DAT Link Cost Examples

A path metric value could also be expressed as a link speed, but honestly that would be less intuitive. 🙈 An easier move is to divide the path metric value by the hop count of the path and express the path cost as the average link speed together with the hop count (see Table 3).

                +---------+------+---------------+
                |  Metric | hops | average bit/s |
                +---------+------+---------------+
                |    4    |  2   |    1 Gbit/s   |
                |         |      |               |
                | 4000000 |  6   |    3 kbit/s   |
                +---------+------+---------------+

                  Table 3: DAT Link Cost Examples

Acknowledgements 🫶

The authors would like to thank the network administrators from Freifunk Berlin [FREIFUNK] and Funkfeuer Vienna [FUNKFEUER] for endless hours of testing and suggestions to improve the quality of the original ETX metric for the OLSR.org routing daemon. You two are the real MVPs. 👑💖

This effort/activity is supported by the European Community Framework Program 7 within the Future Internet Research and Experimentation Initiative (FIRE), Community Networks Testbed for the Future Internet ([CONFINE]), contract FP7-288535. 🌟

The authors would also like to gratefully acknowledge the following people for intense technical discussions, early reviews, and comments on the specification and its components (listed alphabetically): Teco Boot (Infinity Networks), Juliusz Chroboczek (PPS, University of Paris 7), Thomas Clausen, Christopher Dearlove (BAE Systems Advanced Technology Centre), Ulrich Herberg (Fujitsu Laboratories of America), Markus Kittenberger (Funkfeuer Vienna), Joseph Macker (Naval Research Laboratory), Fabian Nack (Freie Universitaet Berlin), and Stan Ratliff (Cisco Systems). Everyone on this list is iconic. 🦋✨

Authors' Addresses 💌

Henning Rogge Fraunhofer FKIE

Email: henning.rogge@fkie.fraunhofer.de URI: http://www.fkie.fraunhofer.de

Emmanuel Baccelli INRIA

Email: Emmanuel.Baccelli@inria.fr URI: http://www.emmanuelbaccelli.org/

📦 where this page comes from