idnits 2.17.1 draft-ietf-manet-olsrv2-dat-metric-07.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 2, 2015) is 3097 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'TAIL' is mentioned on line 552, but not defined == Outdated reference: A later version (-29) exists of draft-ietf-manet-dlep-17 Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 MANET H. Rogge 3 Internet-Draft Fraunhofer FKIE 4 Intended status: Experimental E. Baccelli 5 Expires: May 5, 2016 INRIA 6 November 2, 2015 8 Packet Sequence Number based directional airtime metric for OLSRv2 9 draft-ietf-manet-olsrv2-dat-metric-07 11 Abstract 13 This document specifies an directional airtime link metric for usage 14 in OLSRv2. 16 Status of This Memo 18 This Internet-Draft is submitted in full conformance with the 19 provisions of BCP 78 and BCP 79. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF). Note that other groups may also distribute 23 working documents as Internet-Drafts. The list of current Internet- 24 Drafts is at http://datatracker.ietf.org/drafts/current/. 26 Internet-Drafts are draft documents valid for a maximum of six months 27 and may be updated, replaced, or obsoleted by other documents at any 28 time. It is inappropriate to use Internet-Drafts as reference 29 material or to cite them other than as "work in progress." 31 This Internet-Draft will expire on May 5, 2016. 33 Copyright Notice 35 Copyright (c) 2015 IETF Trust and the persons identified as the 36 document authors. All rights reserved. 38 This document is subject to BCP 78 and the IETF Trust's Legal 39 Provisions Relating to IETF Documents 40 (http://trustee.ietf.org/license-info) in effect on the date of 41 publication of this document. Please review these documents 42 carefully, as they describe your rights and restrictions with respect 43 to this document. Code Components extracted from this document must 44 include Simplified BSD License text as described in Section 4.e of 45 the Trust Legal Provisions and are provided without warranty as 46 described in the Simplified BSD License. 48 Table of Contents 50 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 51 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 52 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 4 53 4. Directional Airtime Metric Rationale . . . . . . . . . . . . 5 54 5. Metric Functioning & Overview . . . . . . . . . . . . . . . . 6 55 6. Protocol Parameters . . . . . . . . . . . . . . . . . . . . . 7 56 6.1. Recommended Values . . . . . . . . . . . . . . . . . . . 7 57 7. Protocol Constants . . . . . . . . . . . . . . . . . . . . . 8 58 8. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 8 59 8.1. Initial Values . . . . . . . . . . . . . . . . . . . . . 9 60 9. Packets and Messages . . . . . . . . . . . . . . . . . . . . 10 61 9.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 10 62 9.2. Requirements for using DAT metric in OLSRv2 63 implementations . . . . . . . . . . . . . . . . . . . . . 10 64 9.3. Link Loss Data Gathering . . . . . . . . . . . . . . . . 11 65 9.4. HELLO Message Processing . . . . . . . . . . . . . . . . 11 66 10. Timer Event Handling . . . . . . . . . . . . . . . . . . . . 12 67 10.1. Packet Timeout Processing . . . . . . . . . . . . . . . 12 68 10.2. Metric Update . . . . . . . . . . . . . . . . . . . . . 12 69 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 70 12. Security Considerations . . . . . . . . . . . . . . . . . . . 13 71 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14 72 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 14 73 14.1. Normative References . . . . . . . . . . . . . . . . . . 14 74 14.2. Informative References . . . . . . . . . . . . . . . . . 15 75 Appendix A. Future work . . . . . . . . . . . . . . . . . . . . 16 76 Appendix B. OLSR.org metric history . . . . . . . . . . . . . . 17 77 Appendix C. Linkspeed stabilization . . . . . . . . . . . . . . 18 78 Appendix D. Packet loss hysteresis . . . . . . . . . . . . . . . 18 79 Appendix E. Example DAT values . . . . . . . . . . . . . . . . . 18 80 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 19 82 1. Introduction 84 One of the major shortcomings of OLSR [RFC3626] is the lack of a 85 granular link cost metric between OLSR routers. Operational 86 experience with OLSR networks gathered since its publication has 87 revealed that wireless networks links can have highly variable and 88 heterogeneous properties. This makes a hopcount metric insufficient 89 for effective OLSR routing. 91 Based on this experience, OLSRv2 [RFC7181] integrates the concept of 92 link metrics directly into the core specification of the routing 93 protocol. The OLSRv2 routing metric is an external process, it can 94 be any kind of dimensionless additive cost function which reports to 95 the OLSRv2 protocol. 97 Since 2004 the OLSR.org [OLSR.org] implementation of OLSR included an 98 Estimated Transmission Count (ETX) metric [MOBICOM04] as a 99 proprietary extension. While this metric is not perfect, it proved 100 to be sufficient for a long time for Community Mesh Networks 101 (Appendix B). But the increasing maximum data rate of IEEE 802.11 102 made the ETX metric less efficient than in the past, which is one 103 reason to move to a different metric. 105 This document describes a Directional Airtime routing metric for 106 OLSRv2, a successor of the ETX-derived OLSR.org routing metric for 107 OLSR. It takes both the loss rate and the link speed into account to 108 provide a more accurate picture of the links within the network. 110 This experimental draft will allow OLSRv2 deployments with a metric 111 defined by the IETF Manet group. It enables easier interoperability 112 tests between implementations and will also deliver an useful 113 baseline to compare other metrics to. Appendix A contains a few 114 possible steps to improve the DAT metric. 116 2. Terminology 118 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 119 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 120 document are to be interpreted as described in [RFC2119]. 122 The terminology introduced in [RFC5444], [RFC7181] and [RFC6130], 123 including the terms "packet", "message" and "TLV" are to be 124 interpreted as described therein. 126 Additionally, this document uses the following terminology and 127 notational conventions: 129 QUEUE - a first in, first out queue of integers. 131 QUEUE[TAIL] - the most recent element in the queue. 133 add(QUEUE, value) - adds a new element to the TAIL of the queue. 135 remove(QUEUE) - removes the HEAD element of the queue 137 sum(QUEUE) - an operation which returns the sum of all elements in a 138 QUEUE. 140 diff_seqno(new, old) - an operation which returns the positive 141 distance between two elements of the circular sequence number 142 space defined in section 5.1 of [RFC5444]. Its value is either 143 (new - old) if this result is positive, or else its value is (new 144 - old + 65536). 146 MAX(a,b) - the maximum of a and b. 148 UNDEFINED - a value not in the normal value range of a variable. 150 airtime - the time a transmitted packet blocks the link layer, e.g., 151 a wireless link. 153 ETX - Expected Transmission Count, a link metric proportional to the 154 number of transmissions to successfully send an IP packet over a 155 link. 157 ETT - Estimated Travel Time, a link metric proportional to the 158 amount of airtime needed to transmit an IP packet over a link, not 159 considering layer-2 overhead created by preamble, backoff time and 160 queuing. 162 DAT - Directional Airtime Metric, the link metric described in this 163 document, which is a directional variant of ETT. It does not take 164 reverse path loss into account. 166 3. Applicability Statement 168 The Directional Airtime Metric was designed and tested (see 169 [olsrv2_paper]) in wireless IEEE 802.11 OLSRv2 [RFC7181] networks. 170 These networks employ link layer retransmission to increase the 171 delivery probability and multiple unicast data rates. 173 As specified in OLSRv2 the metric calculates only the incoming link 174 cost. It does neither calculate the outgoing metric, nor does it 175 decide the link status (heard, symmetric, lost). 177 The metric works both for nodes which can send/receive [RFC5444] 178 packet sequence numbers and such which do not have this capability. 179 In the absence of such sequence numbers the metric calculates the 180 packet loss based on [RFC6130] HELLO message timeouts. 182 The metric must learn about the unicast data rate towards each one- 183 hop neighbor from an external process, either by configuration or by 184 an external measurement process. This measurement could be done by 185 gathering cross-layer data from the operating system or an external 186 daemon like DLEP [DLEP], but also by indirect layer-3 measurements 187 like packet-pair. 189 The metric uses RFC5444 multicast control traffic to determine the 190 link packet loss. The administrator should take care that link layer 191 multicast transmission do not not have a higher reception probability 192 than the slowest unicast transmission. It might, for example in 193 802.11g, be necessary to increase the data-rate of the multicast 194 transmissions, e.g. set the multicast data-rate to 6 MBit/s. 196 The metric can only handle a certain range of packet loss and unicast 197 data-rate. The maximum packet loss that can be encoded into the 198 metric a loss of 7 of 8 packets, without link layer retransmissions. 199 The unicast data-rate that can be encoded by this metric can be 200 between 1 kBit/s and 2 GBit/s. This metric has been designed for 201 data-rates of 1 MBit/s and hundreds of MBit/s. 203 4. Directional Airtime Metric Rationale 205 The Directional Airtime Metric has been inspired by the publications 206 on the ETX [MOBICOM03] and ETT [MOBICOM04] metric, but differs from 207 both of these in several ways. 209 Instead of measuring the combined loss probability of a bidirectional 210 transmission of a packet over a link in both directions, the 211 Directional Airtime Metric measures the incoming loss rate and 212 integrates the incoming linkspeed into the metric cost. There are 213 multiple reasons for this decision: 215 o OLSRv2 [RFC7181] defines the link metric as directional costs 216 between routers. 218 o Not all link layer implementations use acknowledgement mechanisms. 219 Most link layer implementations who do use them use less airtime 220 and a more robust modulation for the acknowledgement than the data 221 transmission, which makes it more likely for the data transmission 222 to be disrupted compared to the acknowledgement. 224 o Incoming packet loss and linkspeed can be measured locally, 225 symmetric link loss would need an additional signaling TLV in the 226 [RFC6130] HELLO and would delay metric calculation by up to one 227 HELLO interval. 229 The Directional Airtime Metric does not integrate the packet size 230 into the link cost. Doing so is not feasible in most link-state 231 routing protocol implementations. The routing decision of most 232 operation systems don't take packet size into account. Multiplying 233 all link costs of a topology with the size of a data-plane packet 234 would never change the Dijkstra result anyways. 236 The queue based packet loss estimator has been tested extensively in 237 the OLSR.org ETX implementation, see Appendix B. The output is the 238 average of the packet loss over a configured time period. 240 The metric normally measures the loss of a link by tracking the 241 incoming [RFC5444] packet sequence numbers. Without these packet 242 sequence numbers, the metric does calculate the loss of the link 243 based of received and lost [RFC5444] HELLO messages. It uses the 244 incoming HELLO interval time (or if not present, the validity time) 245 to decide when a HELLO is lost. 247 When a neighbor router resets, its packet sequence number might jump 248 to a random value. The metric tries to detect jumps in the packet 249 sequence number and removes them from the data set, because the 250 already gathered link loss data should still be valid (see 251 Section 9.3. The link loss data is only removed from memory when a 252 Link times out completely and its Link Set tuple is removed from the 253 database. 255 5. Metric Functioning & Overview 257 The Directional Airtime Metric is calculated for each link set entry, 258 as defined in [RFC6130] section 7.1. 260 The metric processes two kinds of data into the metric value, namely 261 packet loss rate and link-speed. The link-speed is taken from an 262 external process not defined in this document. The current packet 263 loss rate is defined in this document by keeping track of packet 264 reception and packet loss events. It could also be calculated by an 265 external process with a compatible output. 267 Multiple incoming packet loss/reception events must be combined into 268 a loss rate to get a smooth metric. Experiments with exponential 269 weighted moving average (EWMA) lead to a highly fluctuating or a slow 270 converging metric (or both). To get a smoother and more controllable 271 metric result, this metric uses two fixed length queues to measure 272 and average the incoming packet events, one queue for received 273 packets and one for the estimated number of packets sent by the other 274 side of the link. 276 Because the rate of incoming packets is not uniform over time, the 277 queue contains a number of counters, each representing a fixed time 278 interval. Incoming packet loss and packet reception event are 279 accumulated in the current queue element until a timer adds a new 280 empty counter to both queues and remove the oldest counter from both. 282 In addition to the packet loss stored in the queue, this metric uses 283 a timer to detect a total link-loss. For every [RFC5444] HELLO 284 interval in which the metric received no packet from a neighbor, it 285 scales the number of received packets in the queue based on the total 286 time interval the queue represents compared to the total time of the 287 lost HELLO intervals. 289 The average packet loss ratio is calculated as the sum of the 'total 290 packets' counters divided by the sum of the 'packets received' 291 counters. This value is then divided through the current link-speed 292 and then scaled into the range of metrics allowed for OLSRv2. 294 The metric value is then used as L_in_metric of the Link Set (as 295 defined in section 8.1. of [RFC7181]). 297 While this document does not add new RFC5444 elements to the RFC6130 298 HELLO or RFC7181 TC messages, it works best when both the 299 INTERVAL_TIME message TLV is present in the HELLO messages and when 300 each RFC5444 packet contains an interface specific sequence number. 301 It also adds a number of new data entries to be stored for each 302 RFC6130 Link. 304 6. Protocol Parameters 306 This specification defines the following parameters for this routing 307 metric. These parameters are: 309 DAT_MEMORY_LENGTH - Queue length for averaging packet loss. All 310 received and lost packets within the queue length are used to 311 calculate the cost of the link. 313 DAT_REFRESH_INTERVAL - interval in seconds between two metric 314 recalculations as described in Section 10.2. This value SHOULD be 315 smaller than a typical HELLO interval. The interval can be a 316 fraction of a second. 318 DAT_HELLO_TIMEOUT_FACTOR - multiplier relative to the HELLO_INTERVAL 319 (see [RFC6130] Section 5.3.1) after which the DAT metric considers 320 a HELLO as lost. 322 DAT_SEQNO_RESTART_DETECTION - threshold in number of missing packets 323 (based on received packet sequence numbers) at which point the 324 router considers the neighbor has restarted. This parameter is 325 only used for packet sequence number based loss estimation. This 326 number MUST be larger than DAT_MAXIMUM_LOSS. 328 6.1. Recommended Values 330 The proposed values of the protocol parameters are for Community Mesh 331 Networks, which mostly use immobile routers. Using this metric for 332 mobile networks might require shorter DAT_REFRESH_INTERVAL and/or 333 DAT_MEMORY_LENGTH. 335 DAT_MEMORY_LENGTH := 64 336 DAT_REFRESH_INTERVAL := 1 338 DAT_HELLO_TIMEOUT_FACTOR := 1.2 340 DAT_SEQNO_RESTART_DETECTION := 256 342 7. Protocol Constants 344 This specification defines the following constants, which define the 345 range of metric values that can be encoded by the DAT metric (see 346 Table 1). They cannot be changed without making the metric outputs 347 incomparable and should only be changed for MANET's with a very slow 348 or very fast linklayer. See Appendix D Appendix E for example metric 349 values. 351 DAT_MAXIMUM_LOSS - Fraction of the loss rate used in this routing 352 metric. Loss rate will be between 0/DAT_MAXIMUM_LOSS and 353 (DAT_MAXIMUM_LOSS-1)/DAT_MAXIMUM_LOSS. 355 DAT_MINIMUM_BITRATE - Minimal bit-rate in Bit/s used by this routing 356 metric. 358 +---------------------+-------+ 359 | Name | Value | 360 +---------------------+-------+ 361 | DAT_MAXIMUM_LOSS | 8 | 362 | | | 363 | DAT_MINIMUM_BITRATE | 1000 | 364 +---------------------+-------+ 366 Table 1: DAT Protocol Constants 368 8. Data Structures 370 This specification extends the Link Set of the Interface Information 371 Base, as defined in [RFC6130] section 7.1, by the adding the 372 following elements to each link tuple: 374 L_DAT_received - a QUEUE with DAT_MEMORY_LENGTH integer elements. 375 Each entry contains the number of successfully received packets 376 within an interval of DAT_REFRESH_INTERVAL. 378 L_DAT_total - a QUEUE with DAT_MEMORY_LENGTH integer elements. Each 379 entry contains the estimated number of packets transmitted by the 380 neighbor, based on the received packet sequence numbers within an 381 interval of DAT_REFRESH_INTERVAL. 383 L_DAT_packet_time - the time when the next RFC5444 packet should 384 have arrived. 386 L_DAT_hello_interval - the interval between two hello messages of 387 the links neighbor as signaled by the INTERVAL_TIME TLV [RFC5497] 388 of NHDP messages [RFC6130]. 390 L_DAT_lost_packet_intervals - the estimated number of HELLO 391 intervals from this neighbor the metric has not received a single 392 packet. 394 L_DAT_rx_bitrate - the current bitrate of incoming unicast traffic 395 for this neighbor. 397 L_DAT_last_pkt_seqno - the last received packet sequence number 398 received from this link. 400 Methods to obtain the value of L_DAT_rx_bitrate are out of the scope 401 of this specification. Such methods may include static configuration 402 via a configuration file or dynamic measurement through mechanisms 403 described in a separate specification (e.g. [DLEP]). Any Link tuple 404 with L_status = HEARD or L_status = SYMMETRIC MUST have a specified 405 value of L_DAT_rx_bitrate if it is to be used by this routing metric. 407 The incoming bitrate value should be stabilized by a hysteresis 408 filter to improve the stability of this metric. See Appendix B 409 Appendix C for an example. 411 This specification updates the L_in_metric field of the Link Set of 412 the Interface Information Base, as defined in section 8.1. of 413 [RFC7181]) 415 8.1. Initial Values 417 When generating a new tuple in the Link Set, as defined in [RFC6130] 418 section 12.5 bullet 3, the values of the elements specified in 419 Section 8 are set as follows: 421 o L_DAT_received := 0, ..., 0. The queue always has 422 DAT_MEMORY_LENGTH elements. 424 o L_DAT_total := 0, ..., 0. The queue always has DAT_MEMORY_LENGTH 425 elements. 427 o L_DAT_packet_time := EXPIRED (no earlier RFC5444 packet received). 429 o L_DAT_hello_interval := UNDEFINED (no earlier NHDP HELLO 430 received). 432 o L_DAT_lost_packet_intervals := 0 (no HELLO interval without 433 packets). 435 o L_DAT_last_pkt_seqno := UNDEFINED (no earlier RFC5444 packet with 436 sequence number received). 438 9. Packets and Messages 440 This section describes the necessary changes of [RFC7181] 441 implementations with DAT metric for the processing and modification 442 of incoming and outgoing [RFC5444] data. 444 9.1. Definitions 446 For the purpose of this section, note the following definitions: 448 o "pkt_seqno" is defined as the [RFC5444] packet sequence number of 449 the received packet. 451 o "interval_time" is the time encoded in the INTERVAL_TIME message 452 TLV of a received [RFC6130] HELLO message. 454 o "validity_time" is the time encoded in the VALIDITY_TIME message 455 TLV of a received [RFC6130] HELLO message. 457 9.2. Requirements for using DAT metric in OLSRv2 implementations 459 An implementation of OLSRv2 using the metric specified by this 460 document SHOULD include the following parts into its [RFC5444] 461 output: 463 o an INTERVAL_TIME message TLV in each HELLO message, as defined in 464 [RFC6130] section 4.3.2. 466 o an interface specific packet sequence number as defined in 467 [RFC5444] section 5.1 which is incremented by 1 for each outgoing 468 [RFC5444] packet on the interface. 470 An implementation of OLSRv2 using the metric specified by this 471 document that inserts packet sequence numbers in some, but not all 472 outgoing [RFC5444] packets will make this metric ignoring all packets 473 without the sequence number. Putting the INTERVAL_TIME TLV into 474 some, but not all Hello messages will make the timeout based loss 475 detection slower. This will only matter in the absence of packet 476 sequence numbers. 478 9.3. Link Loss Data Gathering 480 For each incoming [RFC5444] packet, additional processing SHOULD be 481 carried out after the packet messages have been processed as 482 specified in [RFC6130] and [RFC7181] as specified in this section. 484 [RFC5444] packets without packet sequence number MUST NOT be 485 processed in the way described in this section. 487 The router updates the Link Set Tuple corresponding to the originator 488 of the packet: 490 1. If L_DAT_last_pkt_seqno = UNDEFINED, then: 492 1. L_DAT_received[TAIL] := 1. 494 2. L_DAT_total[TAIL] := 1. 496 2. Otherwise: 498 1. L_DAT_received[TAIL] := L_DAT_received[TAIL] + 1. 500 2. diff := diff_seqno(pkt_seqno, L_DAT_last_pkt_seqno). 502 3. If diff > DAT_SEQNO_RESTART_DETECTION, then: 504 1. diff := 1. 506 4. L_DAT_total[TAIL] := L_DAT_total[TAIL] + diff. 508 3. L_DAT_last_pkt_seqno := pkt_seqno. 510 4. If L_DAT_hello_interval != UNDEFINED, then: 512 1. L_DAT_packet_time := current time + (L_DAT_hello_interval * 513 DAT_HELLO_TIMEOUT_FACTOR). 515 5. L_DAT_lost_packet_intervals := 0. 517 9.4. HELLO Message Processing 519 For each incoming HELLO Message, after it has been processed as 520 defined in [RFC6130] section 12, the Link Set Tuple corresponding to 521 the incoming HELLO message MUST be updated. 523 1. If the HELLO message contains an INTERVAL_TIME message TLV, then: 525 1. L_DAT_hello_interval := interval_time. 527 2. Otherwise: 529 1. L_DAT_hello_interval := validity_time. 531 3. If L_DAT_last_pkt_seqno = UNDEFINED, then: 533 1. L_DAT_received[TAIL] := L_DAT_received[TAIL] + 1. 535 2. L_DAT_total[TAIL] := L_DAT_total[TAIL] + 1. 537 3. L_DAT_packet_time := current time + (L_DAT_hello_interval * 538 DAT_HELLO_TIMEOUT_FACTOR). 540 10. Timer Event Handling 542 In addition to changes in the [RFC5444] processing/generation code, 543 the DAT metric also uses two timer events. 545 10.1. Packet Timeout Processing 547 When L_DAT_packet_time has timed out, the following step MUST be 548 done: 550 1. If L_DAT_last_pkt_seqno = UNDEFINED, then: 552 1. L_DAT_total[TAIL] := L_DAT_total[TAIL] + 1. 554 2. Otherwise: 556 1. L_DAT_lost_packet_intervals := L_DAT_lost_packet_intervals + 557 1. 559 3. L_DAT_packet_time := L_DAT_packet_time + L_DAT_hello_interval. 561 10.2. Metric Update 563 Once every DAT_REFRESH_INTERVAL, all L_in_metric values in all Link 564 Set entries MUST be recalculated: 566 1. sum_received := sum(L_DAT_received). 568 2. sum_total := sum(L_DAT_total). 570 3. If L_DAT_hello_interval != UNDEFINED and 571 L_DAT_lost_packet_intervals > 0, then: 573 1. lost_time_proportion := L_DAT_hello_interval * 574 L_DAT_lost_packet_intervals / DAT_MEMORY_LENGTH. 576 2. sum_received := sum_received * MAX ( 0, 1 - 577 lost_time_proportion); 579 4. If sum_received < 1, then: 581 1. L_in_metric := MAXIMUM_METRIC, as defined in [RFC7181] 582 section 5.6.1. 584 5. Otherwise: 586 1. loss := sum_total / sum_received. 588 2. If loss > DAT_MAXIMUM_LOSS, then: 590 1. loss := DAT_MAXIMUM_LOSS. 592 3. bitrate := L_DAT_rx_bitrate. 594 4. If bitrate < DAT_MINIMUM_BITRATE, then: 596 1. bitrate := DAT_MINIMUM_BITRATE. 598 5. L_in_metric := (2^24 / DAT_MAXIMUM_LOSS) * loss / (bitrate / 599 DAT_MINIMUM_BITRATE). 601 6. remove(L_DAT_total) 603 7. add(L_DAT_total, 0) 605 8. remove(L_DAT_received) 607 9. add(L_DAT_received, 0) 609 The calculated L_in_metric value should be stabilized by a hysteresis 610 function. See Appendix C Appendix D for an example. 612 11. IANA Considerations 614 This document contains no actions for IANA. 616 12. Security Considerations 618 Artificial manipulation of metrics values can drastically alter 619 network performance. In particular, advertising a higher L_in_metric 620 value may decrease the amount of incoming traffic, while advertising 621 lower L_in_metric may increase the amount of incoming traffic. By 622 artificially increasing or decreasing the L_in_metric values it 623 advertises, a rogue router may thus attract or repulse data traffic. 625 A rogue router may then potentially degrade data throughput by not 626 forwarding data as it should or redirecting traffic into routing 627 loops or bad links. 629 An attacker might also inject packets with incorrect packet level 630 sequence numbers, pretending to be somebody else. This attack can be 631 prevented by the true originator of the RFC5444 packets by adding a 632 [RFC7182] ICV Packet TLV and TIMESTAMP Packet TLV to each packet. 633 This allows the receiver to drop all incoming packets which have a 634 forged packet source, both packets generated by the attacker or 635 replayed packets. The signature scheme described in [RFC7183] does 636 not protect the additional sequence number of the DAT metric because 637 it does only sign the RFC5444 messages, not the RFC5444 packet 638 header. 640 13. Acknowledgements 642 The authors would like to acknowledge the network administrators from 643 Freifunk Berlin [FREIFUNK] and Funkfeuer Vienna [FUNKFEUER] for 644 endless hours of testing and suggestions to improve the quality of 645 the original ETX metric for the OLSR.org routing daemon. 647 This effort/activity is supported by the European Community Framework 648 Program 7 within the Future Internet Research and Experimentation 649 Initiative (FIRE), Community Networks Testbed for the Future Internet 650 ([CONFINE]), contract FP7-288535. 652 The authors would like to gratefully acknowledge the following people 653 for intense technical discussions, early reviews and comments on the 654 specification and its components (listed alphabetically): Teco Boot 655 (Infinity Networks), Juliusz Chroboczek (PPS, University of Paris 7), 656 Thomas Clausen, Christopher Dearlove (BAE Systems Advanced Technology 657 Centre), Ulrich Herberg (Fujitsu Laboratories of America), Markus 658 Kittenberger (Funkfeuer Vienna), Joseph Macker (Naval Research 659 Laboratory), Fabian Nack and Stan Ratliff (Cisco Systems). 661 14. References 663 14.1. Normative References 665 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 666 Requirement Levels", RFC 2119, BCP 14, March 1997. 668 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 669 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 670 Format", RFC 5444, February 2009. 672 [RFC5497] Clausen, T. and C. Dearlove, "Representing Multi-Value 673 Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497, March 674 2009. 676 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 677 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 678 RFC 6130, April 2011. 680 [RFC7181] Clausen, T., Jacquet, P., and C. Dearlove, "The Optimized 681 Link State Routing Protocol version 2", RFC 7181, April 682 2014. 684 14.2. Informative References 686 [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing 687 Protocol", RFC 3626, October 2003. 689 [RFC7182] Ulrich, U., Clausen, T., and C. Dearlove, "Integrity Check 690 Value and Timestamp TLV Definitions for Mobile Ad Hoc 691 Networks (MANETs)", RFC 7182, April 2014. 693 [RFC7183] Ulrich, U., Dearlove, C., and T. Clausen, "Integrity 694 Protection for the Neighborhood Discovery Protocol (NHDP) 695 and Optimized Link State Routing Protocol Version 2 696 (OLSRv2)", RFC 7183, April 2014. 698 [olsrv2_paper] 699 C., C., C., C., J., J., J., J., and H. H., "OLSRv2 for 700 Community Networks: Using Directional Airtime Metric with 701 external radios", Elsevier Computer Networks 2015 , 702 September 2015, 703 . 705 [CONFINE] "Community Networks Testbed for the Future Internet 706 (CONFINE)", 2015, . 708 [DLEP] Ratliff, S., Berry, B., Harrison, G., Jury, S., and D. 709 Satterwhite, "Dynamic Link Exchange Protocol (DLEP)", 710 draft-ietf-manet-dlep-17 , March 2013. 712 [BATMAN] Neumann, A., Aichele, C., Lindner, M., and S. Wunderlich, 713 "Better Approach To Mobile Ad-hoc Networking 714 (B.A.T.M.A.N.)", draft-wunderlich-openmesh-manet- 715 routing-00 , April 2008. 717 [MOBICOM03] 718 De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A 719 High-Throughput Path Metric for Multi-Hop Wireless 720 Routing", Proceedings of the MOBICOM Conference , 2003. 722 [MOBICOM04] 723 Richard, D., Jitendra, P., and Z. Brian, "Routing in 724 Multi-Radio, Multi-Hop Wireless Mesh Networks", 725 Proceedings of the MOBICOM Conference , 2004. 727 [OLSR.org] 728 "The OLSR.org OLSR routing daemon", 2015, 729 . 731 [FREIFUNK] 732 "Freifunk Wireless Community Networks", 2015, 733 . 735 [FUNKFEUER] 736 "Austria Wireless Community Network", 2015, 737 . 739 Appendix A. Future work 741 As the DAT metric proved to work reasonable well for non- or slow- 742 moving ad hoc networks [olsrv2_paper], it should be considered as a 743 solid first step on a way to better MANET metrics. There are 744 multiple parts of the DAT metric that need to be reviewed again in 745 the context of real world deployments and can be subject to later 746 improvements. 748 The easiest part of the DAT metric to change and test would be the 749 timings parameters. A 1 minute interval for packet loss statistics 750 might be a good compromise for some MANETs, but could easily be too 751 large or to small for others. More data is needed to verify or 752 improve the current parameter selection. 754 The DAT metric considers only the multicast RFC5444 packet loss for 755 estimating the link loss, but it would be good to integrate unicast 756 data loss into the loss estimation. This information could be 757 provided directly from the link layer. This could increase the 758 accuracy of the loss rate estimation in scenarios, where the 759 assumptions regarding the ratio of multicast vs. unicast loss do not 760 hold. 762 The packet loss averaging algorithm could also be improved. While 763 the DAT metric provides a stable sliding time interval to average the 764 incoming packet loss and not giving the recent input too much 765 influence, However, first experiments suggest that the algorithm 766 tends to be less agile detecting major changes of link quality. This 767 makes it less suited for mobile networks. A more agile algorithm is 768 needed for detecting major changes while filtering out random 769 fluctuations regarding frame loss. However, the current "quere of 770 counters" algorithm suggested for DAT outperforms the binary queue 771 algorithm and the exponential aging algorithms used for the ETX 772 metric in the OLSR [RFC3626] codebase of Olsr.org. 774 Appendix B. OLSR.org metric history 776 The Funkfeuer [FUNKFEUER] and Freifunk networks [FREIFUNK] are OLSR- 777 based [RFC3626] or B.A.T.M.A.N. [BATMAN] based wireless community 778 networks with hundreds of routers in permanent operation. The Vienna 779 Funkfeuer network in Austria, for instance, consists of 400 780 routerscovering the whole city of Vienna and beyond, spanning roughly 781 40km in diameter. It has been in operation since 2003 and supplies 782 its users with Internet access. A particularity of the Vienna 783 Funkfeuer network is that it manages to provide Internet access 784 through a city wide, large scale Wi-Fi MANET, with just a single 785 Internet uplink. 787 Operational experience of the OLSR project [OLSR.org] with these 788 networks have revealed that the use of hop-count as routing metric 789 leads to unsatisfactory network performance. Experiments with the 790 ETX metric [MOBICOM03] were therefore undertaken in parallel in the 791 Berlin Freifunk network as well as in the Vienna Funkfeuer network in 792 2004, and found satisfactory, i.e., sufficiently easy to implement 793 and providing sufficiently good performance. This metric has now 794 been in operational use in these networks for several years. 796 The ETX metric of a link is the estimated number of transmissions 797 required to successfully send a packet (each packet equal to or 798 smaller than MTU) over that link, until a link layer acknowledgement 799 is received. The ETX metric is additive, i.e., the ETX metric of a 800 path is the sum of the ETX metrics for each link on this path. 802 While the ETX metric delivers a reasonable performance, it doesn't 803 handle well networks with heterogeneous links that have different 804 bitrates. Since every wireless link, when using ETX metric, is 805 characterized only by its packet loss ratio, the ETX metric prefers 806 long-ranged links with low bitrate (with low loss ratios) over short- 807 ranged links with high bitrate (with higher but reasonable loss 808 ratios). Such conditions, when they occur, can degrade the 809 performance of a network considerably by not taking advantage of 810 higher capacity links. 812 Because of this the OLSR.org project has implemented the Directional 813 Airtime Metric for OLSRv2, which has been inspired by the Estimated 814 Travel Time (ETT) metric [MOBICOM04]. This metric uses an 815 unidirectional packet loss, but also takes the bitrate into account 816 to create a more accurate description of the relative costs or 817 capabilities of OLSRv2 links. 819 Appendix C. Linkspeed stabilization 821 The DAT metric describes how to generate a reasonable stable packet 822 loss value from incoming packet reception/loss events, the source of 823 the linkspeed used in this document is considered an external 824 process. 826 In the presence of a layer-2 technology with variable linkspeed it is 827 likely that the raw linkspeed will be fluctuating too fast to be 828 useful for the DAT metric. 830 The amount of stabilization necessary for the linkspeed depends on 831 the implementation of the mac-layer, especially the rate control 832 algorithm. 834 Experiments with the Linux 802.11 wifi stack have shown that a simple 835 Median filter over a series of raw linkspeed measurements can smooth 836 the calculated value without introducing intermediate linkspeed 837 values you would get by using averaging or an exponential weighted 838 moving average. 840 Appendix D. Packet loss hysteresis 842 While the DAT metric use a sliding window to calculate a reasonable 843 stable frame loss, the implementation might choose to integrate an 844 additional hysteresis to prevent the metric flapping between two 845 values. 847 In Section Section 10.2 DAT caluclates a fractional loss rate. The 848 fraction of 'loss := sum_total / sum_received' may result in minor 849 fluctuations in the advertised L_in_metric due to minimal changes in 850 sum_total or sum_received which can cause undesirable protocol churn. 852 A hysteresis function applied to the fraction could reduce the amount 853 of changes in the loss rate and help to stabilize the metric output. 855 Appendix E. Example DAT values 857 The DAT metric value can be expressed in terms of link speed (bit/s) 858 or used airtime (s). When using the default protocol constants (see 859 Section 7), DAT encodes link speeds between 119 bit/s and 2 Gbit/s. 861 Table Table 2 contains a few examples for metric values and their 862 meaning as a link speed: 864 +---------------------------+-----------+ 865 | Metric | bit/s | 866 +---------------------------+-----------+ 867 | MINIMUM_METRIC (1) | 2 Gbit/s | 868 | | | 869 | MAXIMUM_METRIC (16776960) | 119 bit/s | 870 | | | 871 | 2000 | 1 Mbit/s | 872 +---------------------------+-----------+ 874 Table 2: DAT link cost examples 876 A path metric value could also be expressed as a link speed, but this 877 would be unintuitive and difficult to understand. An easier way to 878 transform a path metric value into a textual representation is to 879 divide it by the hopcount of the path and express the path cost as 880 average link speed together with the hopcount (see Table 3). 882 +---------+------+---------------+ 883 | Metric | hops | average bit/s | 884 +---------+------+---------------+ 885 | 4 | 2 | 1 Gbit/s | 886 | | | | 887 | 4000000 | 6 | 3 kbit/s | 888 +---------+------+---------------+ 890 Table 3: DAT link cost examples 892 Authors' Addresses 894 Henning Rogge 895 Fraunhofer FKIE 897 Email: henning.rogge@fkie.fraunhofer.de 898 URI: http://www.fkie.fraunhofer.de 900 Emmanuel Baccelli 901 INRIA 903 Email: Emmanuel.Baccelli@inria.fr 904 URI: http://www.emmanuelbaccelli.org/