idnits 2.17.1 draft-ietf-manet-olsrv2-dat-metric-10.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 : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 24, 2015) is 3076 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'TAIL' is mentioned on line 556, but not defined == Outdated reference: A later version (-29) exists of draft-ietf-manet-dlep-17 Summary: 1 error (**), 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 27, 2016 INRIA 6 November 24, 2015 8 Packet Sequence Number based directional airtime metric for OLSRv2 9 draft-ietf-manet-olsrv2-dat-metric-10 11 Abstract 13 This document specifies an Directional Airtime (DAT) link metric for 14 usage 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 27, 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 Constants . . . . . . . . . . . . . . . . . . . . . 7 56 7. Protocol Parameters . . . . . . . . . . . . . . . . . . . . . 8 57 7.1. Recommended Values . . . . . . . . . . . . . . . . . . . 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. Security Considerations . . . . . . . . . . . . . . . . . . . 13 70 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14 71 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 14 72 13.1. Normative References . . . . . . . . . . . . . . . . . . 14 73 13.2. Informative References . . . . . . . . . . . . . . . . . 15 74 Appendix A. Future work . . . . . . . . . . . . . . . . . . . . 16 75 Appendix B. OLSR.org metric history . . . . . . . . . . . . . . 17 76 Appendix C. Linkspeed stabilization . . . . . . . . . . . . . . 18 77 Appendix D. Packet loss hysteresis . . . . . . . . . . . . . . . 18 78 Appendix E. Example DAT values . . . . . . . . . . . . . . . . . 18 79 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 19 81 1. Introduction 83 One of the major shortcomings of Optimized Link State Routing (OLSR) 84 [RFC3626] is the lack of a granular link cost metric between OLSR 85 routers. Operational experience with OLSR networks gathered since 86 its publication has revealed that wireless networks links can have 87 highly variable and heterogeneous properties. This makes a hopcount 88 metric insufficient for effective OLSR routing. 90 Based on this experience, OLSRv2 [RFC7181] integrates the concept of 91 link metrics directly into the core specification of the routing 92 protocol. The OLSRv2 routing metric is an external process, it can 93 be any kind of dimensionless additive cost function which reports to 94 the OLSRv2 protocol. 96 Since 2004 the OLSR.org [OLSR.org] implementation of OLSR included an 97 Estimated Transmission Count (ETX) metric [MOBICOM04] as a 98 proprietary extension. While this metric is not perfect, it proved 99 to be sufficient for a long time for Community Mesh Networks 100 (Appendix B). But the increasing maximum data rate of IEEE 802.11 101 made the ETX metric less efficient than in the past, which is one 102 reason to move to a different metric. 104 This document describes a Directional Airtime routing metric for 105 OLSRv2, a successor of the OLSR.org ETX-derived routing metric for 106 OLSR. It takes both the loss rate and the link speed into account to 107 provide a more accurate picture of the links within the network. 109 This experimental draft will allow OLSRv2 deployments with a metric 110 defined by the IETF Manet group. It enables easier interoperability 111 tests between implementations and will also deliver a useful baseline 112 to compare other metrics to. Appendix A contains a few possible 113 steps to improve the Directional Airtime Metric. 115 2. Terminology 117 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 118 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 119 document are to be interpreted as described in [RFC2119]. 121 The terminology introduced in [RFC5444], [RFC7181] and [RFC6130], 122 including the terms "packet", "message" and "TLV" are to be 123 interpreted as described therein. 125 Additionally, this document uses the following terminology and 126 notational conventions: 128 DAT - Directional Airtime (Metric), the link metric described in 129 this document, which is a directional variant of ETT. It does not 130 take reverse path loss into account. 132 QUEUE - a first in, first out queue of integers. 134 QUEUE[TAIL] - the most recent element in the queue. 136 add(QUEUE, value) - adds a new element to the TAIL of the queue. 138 remove(QUEUE) - removes the HEAD element of the queue 140 sum(QUEUE) - an operation which returns the sum of all elements in a 141 QUEUE. 143 diff_seqno(new, old) - an operation which returns the positive 144 distance between two elements of the circular sequence number 145 space defined in section 5.1 of [RFC5444]. Its value is either 146 (new - old) if this result is positive, or else its value is (new 147 - old + 65536). 149 MAX(a, b) - the maximum of a and b. 151 MIN(a, b) - the minimum of a and b. 153 UNDEFINED - a value not in the normal value range of a variable. 155 airtime - the time a transmitted packet blocks the link layer, e.g., 156 a wireless link. 158 ETX - Expected Transmission Count, a link metric proportional to the 159 number of transmissions to successfully send an IP packet over a 160 link. 162 ETT - Estimated Travel Time, a link metric proportional to the 163 amount of airtime needed to successfully transmit an IP packet 164 over a link, not considering layer-2 overhead created by preamble, 165 backoff time and queuing. 167 3. Applicability Statement 169 The Directional Airtime Metric was designed and tested (see 170 [olsrv2_paper]) in wireless IEEE 802.11 OLSRv2 [RFC7181] networks. 171 These networks employ link layer retransmission to increase the 172 delivery probability. A dynamic rate selection algorithm selects the 173 unicast data rate independently for each neighbor. 175 As specified in OLSRv2, the metric calculates only the incoming link 176 cost. It does neither calculate the outgoing metric, nor does it 177 decide the link status (heard, symmetric, lost). 179 The metric works both for nodes which can send/receive [RFC5444] 180 packet sequence numbers and those which do not have this capability. 181 In the absence of such sequence numbers the metric calculates the 182 packet loss based on [RFC6130] HELLO message timeouts. 184 The metric must learn about the unicast data rate towards each one- 185 hop neighbor from an external process, either by configuration or by 186 an external measurement process. This measurement could be done by 187 gathering cross-layer data from the operating system or an external 188 daemon like DLEP [DLEP], but also by indirect layer-3 measurements 189 like packet-pair (see [MOBICOM04]). 191 The metric uses [RFC5444] multicast control traffic to determine the 192 link packet loss. The administrator should take care that link layer 193 multicast transmission do not have a higher reception probability 194 than the slowest unicast transmission without retransmission. It 195 might, for example in 802.11g, be necessary to increase the data-rate 196 of the multicast transmissions, e.g. set the multicast data-rate to 6 197 MBit/s. 199 The metric can only handle a certain range of packet loss and unicast 200 data-rate. The maximum packet loss that can be encoded into the 201 metric a loss of 7 of 8 packets (87.5%), without link layer 202 retransmissions. The unicast data-rate that can be encoded by this 203 metric can be between 1 kBit/s and 2 GBit/s. This metric has been 204 designed for data-rates of 1 MBit/s and hundreds of MBit/s. 206 4. Directional Airtime Metric Rationale 208 The Directional Airtime Metric has been inspired by the publications 209 on the ETX [MOBICOM03] and ETT [MOBICOM04] metric, but differs from 210 both of these in several ways. 212 Instead of measuring the combined loss probability of a bidirectional 213 transmission of a packet over a link in both directions, the 214 Directional Airtime Metric measures the incoming loss rate and 215 integrates the incoming linkspeed into the metric cost. There are 216 multiple reasons for this decision: 218 o OLSRv2 [RFC7181] defines the link metric as directional costs 219 between routers. 221 o Not all link layer implementations use acknowledgement mechanisms. 222 Most link layer implementations who do use them use less airtime 223 and a more robust modulation for the acknowledgement than the data 224 transmission, which makes it more likely for the data transmission 225 to be disrupted compared to the acknowledgement. 227 o Incoming packet loss and linkspeed can be measured locally, 228 symmetric link loss would need an additional signaling TLV in the 229 [RFC6130] HELLO and would delay metric calculation by up to one 230 HELLO interval. 232 The Directional Airtime Metric does not integrate the packet size 233 into the link cost. Doing so is not feasible in most link-state 234 routing protocol implementations. The routing decision of most 235 operation systems don't take packet size into account. Multiplying 236 all link costs of a topology with the size of a data-plane packet 237 would never change the Dijkstra result anyways. 239 The queue based packet loss estimator has been tested extensively in 240 the OLSR.org ETX implementation, see Appendix B. The output is the 241 average of the packet loss over a configured time period. 243 The metric normally measures the loss of a link by tracking the 244 incoming [RFC5444] packet sequence numbers. Without these packet 245 sequence numbers, the metric does calculate the loss of the link 246 based of received and lost [RFC5444] HELLO messages. It uses the 247 incoming HELLO interval time (or if not present, the validity time) 248 to decide when a HELLO is lost. 250 When a neighbor router resets, its packet sequence number might jump 251 to a random value. The metric tries to detect jumps in the packet 252 sequence number and removes them from the data set, because the 253 already gathered link loss data should still be valid (see 254 Section 9.3. The link loss data is only removed from memory when a 255 Link times out completely and its Link Set tuple is removed from the 256 database. 258 5. Metric Functioning & Overview 260 The Directional Airtime Metric is calculated for each link set entry, 261 as defined in [RFC6130] section 7.1. 263 The metric processes two kinds of data into the metric value, namely 264 packet loss rate and link-speed. The link-speed is taken from an 265 external process not defined in this document. The current packet 266 loss rate is defined in this document by keeping track of packet 267 reception and packet loss events. It could also be calculated by an 268 external process with a compatible output. 270 Multiple incoming packet loss/reception events must be combined into 271 a loss rate to get a smooth metric. Experiments with exponential 272 weighted moving average (EWMA) lead to a highly fluctuating or a slow 273 converging metric (or both). To get a smoother and more controllable 274 metric result, this metric uses two fixed length queues to measure 275 and average the incoming packet events, one queue for received 276 packets and one for the estimated number of packets sent by the other 277 side of the link. 279 Because the rate of incoming packets is not uniform over time, the 280 queue contains a number of counters, each representing a fixed time 281 interval. Incoming packet loss and packet reception event are 282 accumulated in the current queue element until a timer adds a new 283 empty counter to both queues and remove the oldest counter from both. 285 In addition to the packet loss stored in the queue, this metric uses 286 a timer to detect a total link-loss. For every [RFC5444] HELLO 287 interval in which the metric received no packet from a neighbor, it 288 scales the number of received packets in the queue based on the total 289 time interval the queue represents compared to the total time of the 290 lost HELLO intervals. 292 The average packet loss ratio is calculated as the sum of the 'total 293 packets' counters divided by the sum of the 'packets received' 294 counters. This value is then divided through the current link-speed 295 and then scaled into the range of metrics allowed for OLSRv2. 297 The metric value is then used as L_in_metric of the Link Set (as 298 defined in section 8.1. of [RFC7181]). 300 While this document does not add new RFC5444 elements to the RFC6130 301 HELLO or RFC7181 TC messages, it works best when both the 302 INTERVAL_TIME message TLV is present in the HELLO messages and when 303 each RFC5444 packet contains an interface specific sequence number. 304 It also adds a number of new data entries to be stored for each 305 RFC6130 Link. 307 6. Protocol Constants 309 This specification defines the following constants, which define the 310 range of metric values that can be encoded by the DAT metric (see 311 Table 1). They cannot be changed without making the metric outputs 312 incomparable and should only be changed for MANET's with a very slow 313 or very fast link layer. See Appendix D Appendix E for example 314 metric values. 316 DAT_MAXIMUM_LOSS - Fraction of the loss rate used in this routing 317 metric. Loss rate will be between 0/DAT_MAXIMUM_LOSS and 318 (DAT_MAXIMUM_LOSS-1)/DAT_MAXIMUM_LOSS. 320 DAT_MINIMUM_BITRATE - Minimal bit-rate in Bit/s used by this routing 321 metric. 323 +---------------------+-------+ 324 | Name | Value | 325 +---------------------+-------+ 326 | DAT_MAXIMUM_LOSS | 8 | 327 | | | 328 | DAT_MINIMUM_BITRATE | 1000 | 329 +---------------------+-------+ 331 Table 1: DAT Protocol Constants 333 7. Protocol Parameters 335 This specification defines the following parameters for this routing 336 metric. These parameters are: 338 DAT_MEMORY_LENGTH - Queue length for averaging packet loss. All 339 received and lost packets within the queue length are used to 340 calculate the cost of the link. 342 DAT_REFRESH_INTERVAL - interval in seconds between two metric 343 recalculations as described in Section 10.2. This value SHOULD be 344 smaller than a typical HELLO interval. The interval can be a 345 fraction of a second. 347 DAT_HELLO_TIMEOUT_FACTOR - multiplier relative to the HELLO_INTERVAL 348 (see [RFC6130] Section 5.3.1) after which the DAT metric considers 349 a HELLO as lost. 351 DAT_SEQNO_RESTART_DETECTION - threshold in number of missing packets 352 (based on received packet sequence numbers) at which point the 353 router considers the neighbor has restarted. This parameter is 354 only used for packet sequence number based loss estimation. This 355 number MUST be larger than DAT_MAXIMUM_LOSS. 357 7.1. Recommended Values 359 The proposed values of the protocol parameters are for Community Mesh 360 Networks, which mostly use immobile routers. Using this metric for 361 mobile networks might require shorter DAT_REFRESH_INTERVAL and/or 362 DAT_MEMORY_LENGTH. 364 DAT_MEMORY_LENGTH := 64 366 DAT_REFRESH_INTERVAL := 1 368 DAT_HELLO_TIMEOUT_FACTOR := 1.2 370 DAT_SEQNO_RESTART_DETECTION := 256 372 8. Data Structures 374 This specification extends the Link Set of the Interface Information 375 Base, as defined in [RFC6130] section 7.1, by the adding the 376 following elements to each link tuple: 378 L_DAT_received - a QUEUE with DAT_MEMORY_LENGTH integer elements. 379 Each entry contains the number of successfully received packets 380 within an interval of DAT_REFRESH_INTERVAL. 382 L_DAT_total - a QUEUE with DAT_MEMORY_LENGTH integer elements. Each 383 entry contains the estimated number of packets transmitted by the 384 neighbor, based on the received packet sequence numbers within an 385 interval of DAT_REFRESH_INTERVAL. 387 L_DAT_packet_time - the time when the next RFC5444 packet should 388 have arrived. 390 L_DAT_hello_interval - the interval between two hello messages of 391 the links neighbor as signaled by the INTERVAL_TIME TLV [RFC5497] 392 of NHDP messages [RFC6130]. 394 L_DAT_lost_packet_intervals - the estimated number of HELLO 395 intervals from this neighbor the metric has not received a single 396 packet. 398 L_DAT_rx_bitrate - the current bitrate of incoming unicast traffic 399 for this neighbor. 401 L_DAT_last_pkt_seqno - the last received packet sequence number 402 received from this link. 404 Methods to obtain the value of L_DAT_rx_bitrate are out of the scope 405 of this specification. Such methods may include static configuration 406 via a configuration file or dynamic measurement through mechanisms 407 described in a separate specification (e.g. [DLEP]). Any Link tuple 408 with L_status = HEARD or L_status = SYMMETRIC MUST have a specified 409 value of L_DAT_rx_bitrate if it is to be used by this routing metric. 411 The incoming bitrate value should be stabilized by a hysteresis 412 filter to improve the stability of this metric. See Appendix B 413 Appendix C for an example. 415 This specification updates the L_in_metric field of the Link Set of 416 the Interface Information Base, as defined in section 8.1. of 417 [RFC7181]) 419 8.1. Initial Values 421 When generating a new tuple in the Link Set, as defined in [RFC6130] 422 section 12.5 bullet 3, the values of the elements specified in 423 Section 8 are set as follows: 425 o L_DAT_received := 0, ..., 0. The queue always has 426 DAT_MEMORY_LENGTH elements. 428 o L_DAT_total := 0, ..., 0. The queue always has DAT_MEMORY_LENGTH 429 elements. 431 o L_DAT_packet_time := EXPIRED (no earlier RFC5444 packet received). 433 o L_DAT_hello_interval := UNDEFINED (no earlier NHDP HELLO 434 received). 436 o L_DAT_lost_packet_intervals := 0 (no HELLO interval without 437 packets). 439 o L_DAT_last_pkt_seqno := UNDEFINED (no earlier RFC5444 packet with 440 sequence number received). 442 9. Packets and Messages 444 This section describes the necessary changes of [RFC7181] 445 implementations with DAT metric for the processing and modification 446 of incoming and outgoing [RFC5444] data. 448 9.1. Definitions 450 For the purpose of this section, note the following definitions: 452 o "pkt_seqno" is defined as the [RFC5444] packet sequence number of 453 the received packet. 455 o "interval_time" is the time encoded in the INTERVAL_TIME message 456 TLV of a received [RFC6130] HELLO message. 458 o "validity_time" is the time encoded in the VALIDITY_TIME message 459 TLV of a received [RFC6130] HELLO message. 461 9.2. Requirements for using DAT metric in OLSRv2 implementations 463 An implementation of OLSRv2 using the metric specified by this 464 document SHOULD include the following parts into its [RFC5444] 465 output: 467 o an INTERVAL_TIME message TLV in each HELLO message, as defined in 468 [RFC6130] section 4.3.2. 470 o an interface specific packet sequence number as defined in 471 [RFC5444] section 5.1 which is incremented by 1 for each outgoing 472 [RFC5444] packet on the interface. 474 An implementation of OLSRv2 using the metric specified by this 475 document that inserts packet sequence numbers in some, but not all 476 outgoing [RFC5444] packets will make this metric ignore all packets 477 without the sequence number. Putting the INTERVAL_TIME TLV into 478 some, but not all Hello messages will make the timeout based loss 479 detection slower. This will only matter in the absence of packet 480 sequence numbers. 482 9.3. Link Loss Data Gathering 484 For each incoming [RFC5444] packet, additional processing SHOULD be 485 carried out after the packet messages have been processed as 486 specified in [RFC6130] and [RFC7181] as specified in this section. 488 [RFC5444] packets without packet sequence number MUST NOT be 489 processed in the way described in this section. 491 The router updates the Link Set Tuple corresponding to the originator 492 of the packet: 494 1. If L_DAT_last_pkt_seqno = UNDEFINED, then: 496 1. L_DAT_received[TAIL] := 1. 498 2. L_DAT_total[TAIL] := 1. 500 2. Otherwise: 502 1. L_DAT_received[TAIL] := L_DAT_received[TAIL] + 1. 504 2. diff := diff_seqno(pkt_seqno, L_DAT_last_pkt_seqno). 506 3. If diff > DAT_SEQNO_RESTART_DETECTION, then: 508 1. diff := 1. 510 4. L_DAT_total[TAIL] := L_DAT_total[TAIL] + diff. 512 3. L_DAT_last_pkt_seqno := pkt_seqno. 514 4. If L_DAT_hello_interval != UNDEFINED, then: 516 1. L_DAT_packet_time := current time + (L_DAT_hello_interval * 517 DAT_HELLO_TIMEOUT_FACTOR). 519 5. L_DAT_lost_packet_intervals := 0. 521 9.4. HELLO Message Processing 523 For each incoming HELLO Message, after it has been processed as 524 defined in [RFC6130] section 12, the Link Set Tuple corresponding to 525 the incoming HELLO message MUST be updated. 527 1. If the HELLO message contains an INTERVAL_TIME message TLV, then: 529 1. L_DAT_hello_interval := interval_time. 531 2. Otherwise: 533 1. L_DAT_hello_interval := validity_time. 535 3. If L_DAT_last_pkt_seqno = UNDEFINED, then: 537 1. L_DAT_received[TAIL] := L_DAT_received[TAIL] + 1. 539 2. L_DAT_total[TAIL] := L_DAT_total[TAIL] + 1. 541 3. L_DAT_packet_time := current time + (L_DAT_hello_interval * 542 DAT_HELLO_TIMEOUT_FACTOR). 544 10. Timer Event Handling 546 In addition to changes in the [RFC5444] processing/generation code, 547 the DAT metric also uses two timer events. 549 10.1. Packet Timeout Processing 551 When L_DAT_packet_time has timed out, the following step MUST be 552 done: 554 1. If L_DAT_last_pkt_seqno = UNDEFINED, then: 556 1. L_DAT_total[TAIL] := L_DAT_total[TAIL] + 1. 558 2. Otherwise: 560 1. L_DAT_lost_packet_intervals := L_DAT_lost_packet_intervals + 561 1. 563 3. L_DAT_packet_time := L_DAT_packet_time + L_DAT_hello_interval. 565 10.2. Metric Update 567 Once every DAT_REFRESH_INTERVAL, all L_in_metric values in all Link 568 Set entries MUST be recalculated: 570 1. sum_received := sum(L_DAT_received). 572 2. sum_total := sum(L_DAT_total). 574 3. If L_DAT_hello_interval != UNDEFINED and 575 L_DAT_lost_packet_intervals > 0, then: 577 1. lost_time_proportion := L_DAT_hello_interval * 578 L_DAT_lost_packet_intervals / DAT_MEMORY_LENGTH. 580 2. sum_received := sum_received * MAX ( 0, 1 - 581 lost_time_proportion); 583 4. If sum_received < 1, then: 585 1. L_in_metric := MAXIMUM_METRIC, as defined in [RFC7181] 586 section 5.6.1. 588 5. Otherwise: 590 1. loss := MIN(sum_total / sum_received, DAT_MAXIMUM_LOSS). 592 2. bitrate := MAX(L_DAT_rx_bitrate, DAT_MINIMUM_BITRATE). 594 3. L_in_metric := (2^24 / DAT_MAXIMUM_LOSS) * loss / (bitrate / 595 DAT_MINIMUM_BITRATE). 597 6. remove(L_DAT_total) 599 7. add(L_DAT_total, 0) 601 8. remove(L_DAT_received) 603 9. add(L_DAT_received, 0) 605 The calculated L_in_metric value should be stabilized by a hysteresis 606 function. See Appendix C Appendix D for an example. 608 11. Security Considerations 610 Artificial manipulation of metrics values can drastically alter 611 network performance. In particular, advertising a higher L_in_metric 612 value may decrease the amount of incoming traffic, while advertising 613 lower L_in_metric may increase the amount of incoming traffic. By 614 artificially increasing or decreasing the L_in_metric values it 615 advertises, a rogue router may thus attract or repulse data traffic. 616 A rogue router may then potentially degrade data throughput by not 617 forwarding data as it should or redirecting traffic into routing 618 loops or bad links. It might also attract traffic for "Man in the 619 Middle" attacks or traffic analysis. 621 An attacker might also inject packets with incorrect packet level 622 sequence numbers, pretending to be somebody else. This attack can be 623 prevented by the true originator of the RFC5444 packets by adding a 624 [RFC7182] ICV Packet TLV and TIMESTAMP Packet TLV to each packet. 625 This allows the receiver to drop all incoming packets which have a 626 forged packet source, both packets generated by the attacker or 627 replayed packets. The security mechanism described in [RFC7183] does 628 not protect the additional sequence number of the DAT metric because 629 it does only sign the RFC5444 messages, not the RFC5444 packet 630 header. 632 Protection against "Man in the Middle" attacks are out of scope of 633 this document. 635 12. Acknowledgements 637 The authors would like to acknowledge the network administrators from 638 Freifunk Berlin [FREIFUNK] and Funkfeuer Vienna [FUNKFEUER] for 639 endless hours of testing and suggestions to improve the quality of 640 the original ETX metric for the OLSR.org routing daemon. 642 This effort/activity is supported by the European Community Framework 643 Program 7 within the Future Internet Research and Experimentation 644 Initiative (FIRE), Community Networks Testbed for the Future Internet 645 ([CONFINE]), contract FP7-288535. 647 The authors would like to gratefully acknowledge the following people 648 for intense technical discussions, early reviews and comments on the 649 specification and its components (listed alphabetically): Teco Boot 650 (Infinity Networks), Juliusz Chroboczek (PPS, University of Paris 7), 651 Thomas Clausen, Christopher Dearlove (BAE Systems Advanced Technology 652 Centre), Ulrich Herberg (Fujitsu Laboratories of America), Markus 653 Kittenberger (Funkfeuer Vienna), Joseph Macker (Naval Research 654 Laboratory), Fabian Nack and Stan Ratliff (Cisco Systems). 656 13. References 658 13.1. Normative References 660 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 661 Requirement Levels", RFC 2119, BCP 14, March 1997. 663 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 664 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 665 Format", RFC 5444, February 2009. 667 [RFC5497] Clausen, T. and C. Dearlove, "Representing Multi-Value 668 Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497, March 669 2009. 671 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 672 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 673 RFC 6130, April 2011. 675 [RFC7181] Clausen, T., Jacquet, P., and C. Dearlove, "The Optimized 676 Link State Routing Protocol version 2", RFC 7181, April 677 2014. 679 13.2. Informative References 681 [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing 682 Protocol", RFC 3626, October 2003. 684 [RFC7182] Ulrich, U., Clausen, T., and C. Dearlove, "Integrity Check 685 Value and Timestamp TLV Definitions for Mobile Ad Hoc 686 Networks (MANETs)", RFC 7182, April 2014. 688 [RFC7183] Ulrich, U., Dearlove, C., and T. Clausen, "Integrity 689 Protection for the Neighborhood Discovery Protocol (NHDP) 690 and Optimized Link State Routing Protocol Version 2 691 (OLSRv2)", RFC 7183, April 2014. 693 [olsrv2_paper] 694 C., C., C., C., J., J., J., J., and H. H., "OLSRv2 for 695 Community Networks: Using Directional Airtime Metric with 696 external radios", Elsevier Computer Networks 2015 , 697 September 2015, 698 . 700 [CONFINE] "Community Networks Testbed for the Future Internet 701 (CONFINE)", 2015, . 703 [DLEP] Ratliff, S., Berry, B., Harrison, G., Jury, S., and D. 704 Satterwhite, "Dynamic Link Exchange Protocol (DLEP)", 705 draft-ietf-manet-dlep-17 , March 2013. 707 [BATMAN] Neumann, A., Aichele, C., Lindner, M., and S. Wunderlich, 708 "Better Approach To Mobile Ad-hoc Networking 709 (B.A.T.M.A.N.)", draft-wunderlich-openmesh-manet- 710 routing-00 , April 2008. 712 [MOBICOM03] 713 De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A 714 High-Throughput Path Metric for Multi-Hop Wireless 715 Routing", Proceedings of the MOBICOM Conference , 2003. 717 [MOBICOM04] 718 Richard, D., Jitendra, P., and Z. Brian, "Routing in 719 Multi-Radio, Multi-Hop Wireless Mesh Networks", 720 Proceedings of the MOBICOM Conference , 2004. 722 [OLSR.org] 723 "The OLSR.org OLSR routing daemon", 2015, 724 . 726 [FREIFUNK] 727 "Freifunk Wireless Community Networks", 2015, 728 . 730 [FUNKFEUER] 731 "Austria Wireless Community Network", 2015, 732 . 734 Appendix A. Future work 736 As the DAT metric proved to work reasonable well for non- or slow- 737 moving ad hoc networks [olsrv2_paper], it should be considered as a 738 solid first step on a way to better MANET metrics. There are 739 multiple parts of the DAT metric that need to be reviewed again in 740 the context of real world deployments and can be subject to later 741 improvements. 743 The easiest part of the DAT metric to change and test would be the 744 timings parameters. A 1 minute interval for packet loss statistics 745 might be a good compromise for some MANETs, but could easily be too 746 large or to small for others. More data is needed to verify or 747 improve the current parameter selection. 749 The DAT metric considers only the multicast RFC5444 packet loss for 750 estimating the link loss, but it would be good to integrate unicast 751 data loss into the loss estimation. This information could be 752 provided directly from the link layer. This could increase the 753 accuracy of the loss rate estimation in scenarios, where the 754 assumptions regarding the ratio of multicast vs. unicast loss do not 755 hold. 757 The packet loss averaging algorithm could also be improved. While 758 the DAT metric provides a stable sliding time interval to average the 759 incoming packet loss and not giving the recent input too much 760 influence, However, first experiments suggest that the algorithm 761 tends to be less agile detecting major changes of link quality. This 762 makes it less suited for mobile networks. A more agile algorithm is 763 needed for detecting major changes while filtering out random 764 fluctuations regarding frame loss. However, the current "quere of 765 counters" algorithm suggested for DAT outperforms the binary queue 766 algorithm and the exponential aging algorithms used for the ETX 767 metric in the OLSR [RFC3626] codebase of Olsr.org. 769 Appendix B. OLSR.org metric history 771 The Funkfeuer [FUNKFEUER] and Freifunk networks [FREIFUNK] are OLSR- 772 based [RFC3626] or B.A.T.M.A.N. [BATMAN] based wireless community 773 networks with hundreds of routers in permanent operation. The Vienna 774 Funkfeuer network in Austria, for instance, consists of 400 routers 775 covering the whole city of Vienna and beyond, spanning roughly 40km 776 in diameter. It has been in operation since 2003 and supplies its 777 users with Internet access. A particularity of the Vienna Funkfeuer 778 network is that it manages to provide Internet access through a city 779 wide, large scale Wi-Fi MANET, with just a single Internet uplink. 781 Operational experience of the OLSR project [OLSR.org] with these 782 networks have revealed that the use of hop-count as routing metric 783 leads to unsatisfactory network performance. Experiments with the 784 ETX metric [MOBICOM03] were therefore undertaken in parallel in the 785 Berlin Freifunk network as well as in the Vienna Funkfeuer network in 786 2004, and found satisfactory, i.e., sufficiently easy to implement 787 and providing sufficiently good performance. This metric has now 788 been in operational use in these networks for several years. 790 The ETX metric of a link is the estimated number of transmissions 791 required to successfully send a packet (each packet equal to or 792 smaller than MTU) over that link, until a link layer acknowledgement 793 is received. The ETX metric is additive, i.e., the ETX metric of a 794 path is the sum of the ETX metrics for each link on this path. 796 While the ETX metric delivers a reasonable performance, it doesn't 797 handle well networks with heterogeneous links that have different 798 bitrates. Since every wireless link, when using ETX metric, is 799 characterized only by its packet loss ratio, the ETX metric prefers 800 long-ranged links with low bitrate (with low loss ratios) over short- 801 ranged links with high bitrate (with higher but reasonable loss 802 ratios). Such conditions, when they occur, can degrade the 803 performance of a network considerably by not taking advantage of 804 higher capacity links. 806 Because of this the OLSR.org project has implemented the Directional 807 Airtime Metric for OLSRv2, which has been inspired by the Estimated 808 Travel Time (ETT) metric [MOBICOM04]. This metric uses an 809 unidirectional packet loss, but also takes the bitrate into account 810 to create a more accurate description of the relative costs or 811 capabilities of OLSRv2 links. 813 Appendix C. Linkspeed stabilization 815 The DAT metric describes how to generate a reasonable stable packet 816 loss value from incoming packet reception/loss events, the source of 817 the linkspeed used in this document is considered an external 818 process. 820 In the presence of a layer-2 technology with variable linkspeed it is 821 likely that the raw linkspeed will be fluctuating too fast to be 822 useful for the DAT metric. 824 The amount of stabilization necessary for the linkspeed depends on 825 the implementation of the mac-layer, especially the rate control 826 algorithm. 828 Experiments with the Linux 802.11 wifi stack have shown that a simple 829 Median filter over a series of raw linkspeed measurements can smooth 830 the calculated value without introducing intermediate linkspeed 831 values you would get by using averaging or an exponential weighted 832 moving average. 834 Appendix D. Packet loss hysteresis 836 While the DAT metric use a sliding window to calculate a reasonable 837 stable frame loss, the implementation might choose to integrate an 838 additional hysteresis to prevent the metric flapping between two 839 values. 841 In Section Section 10.2 DAT caluclates a fractional loss rate. The 842 fraction of 'loss := sum_total / sum_received' may result in minor 843 fluctuations in the advertised L_in_metric due to minimal changes in 844 sum_total or sum_received which can cause undesirable protocol churn. 846 A hysteresis function applied to the fraction could reduce the amount 847 of changes in the loss rate and help to stabilize the metric output. 849 Appendix E. Example DAT values 851 The DAT metric value can be expressed in terms of link speed (bit/s) 852 or used airtime (s). When using the default protocol constants (see 853 Section 6), DAT encodes link speeds between 119 bit/s and 2 Gbit/s. 855 Table Table 2 contains a few examples for metric values and their 856 meaning as a link speed: 858 +---------------------------+-----------+ 859 | Metric | bit/s | 860 +---------------------------+-----------+ 861 | MINIMUM_METRIC (1) | 2 Gbit/s | 862 | | | 863 | MAXIMUM_METRIC (16776960) | 119 bit/s | 864 | | | 865 | 2000 | 1 Mbit/s | 866 +---------------------------+-----------+ 868 Table 2: DAT link cost examples 870 A path metric value could also be expressed as a link speed, but this 871 would be unintuitive and difficult to understand. An easier way to 872 transform a path metric value into a textual representation is to 873 divide it by the hopcount of the path and express the path cost as 874 average link speed together with the hopcount (see Table 3). 876 +---------+------+---------------+ 877 | Metric | hops | average bit/s | 878 +---------+------+---------------+ 879 | 4 | 2 | 1 Gbit/s | 880 | | | | 881 | 4000000 | 6 | 3 kbit/s | 882 +---------+------+---------------+ 884 Table 3: DAT link cost examples 886 Authors' Addresses 888 Henning Rogge 889 Fraunhofer FKIE 891 Email: henning.rogge@fkie.fraunhofer.de 892 URI: http://www.fkie.fraunhofer.de 894 Emmanuel Baccelli 895 INRIA 897 Email: Emmanuel.Baccelli@inria.fr 898 URI: http://www.emmanuelbaccelli.org/