idnits 2.17.1 draft-ietf-manet-olsrv2-dat-metric-11.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 (December 15, 2015) is 3048 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'TAIL' is mentioned on line 561, 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: June 17, 2016 INRIA 6 December 15, 2015 8 Packet Sequence Number based directional airtime metric for OLSRv2 9 draft-ietf-manet-olsrv2-dat-metric-11 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 June 17, 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 . . . . . . . . . . . . . . . . . . . . . . . 9 59 8.1. Initial Values . . . . . . . . . . . . . . . . . . . . . 10 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 . . . . . . . . . . . . . . . . 12 66 10. Timer Event Handling . . . . . . . . . . . . . . . . . . . . 12 67 10.1. Packet Timeout Processing . . . . . . . . . . . . . . . 12 68 10.2. Metric Update . . . . . . . . . . . . . . . . . . . . . 13 69 11. Security Considerations . . . . . . . . . . . . . . . . . . . 13 70 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 71 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14 72 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 15 73 14.1. Normative References . . . . . . . . . . . . . . . . . . 15 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 . . . . . . . . . . . . . . . . . 19 80 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 19 82 1. Introduction 84 One of the major shortcomings of Optimized Link State Routing (OLSR) 85 [RFC3626] is the lack of a granular link cost metric between OLSR 86 routers. Operational experience with OLSR networks gathered since 87 its publication has revealed that wireless networks links can have 88 highly variable and heterogeneous properties. This makes a hopcount 89 metric insufficient 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 has 98 included an Estimated Transmission Count (ETX) metric [MOBICOM04] as 99 a proprietary extension. While this metric is not perfect, it proved 100 to be sufficient for a long time for Community Mesh Networks (see 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 OLSR.org ETX-derived 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 specification allows OLSRv2 deployments with a metric defined by 111 the IETF MANET working group. It enables easier interoperability 112 tests between implementations and targets to deliver a useful 113 baseline to compare with, for experiments with this metric as well as 114 other metrics. Appendix A contains a few possible steps to improve 115 the Directional Airtime Metric. Coming experiments should also allow 116 to judge if the DAT metric can be useful for other IETF protocol, 117 both inside and out of the MANET working group. This could lead 118 either to moving this draft to Standard Track or to replace it with 119 an improved document. 121 2. Terminology 123 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 124 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 125 document are to be interpreted as described in [RFC2119]. 127 The terminology introduced in [RFC5444], [RFC7181] and [RFC6130], 128 including the terms "packet", "message" and "TLV" are to be 129 interpreted as described therein. 131 Additionally, this document uses the following terminology and 132 notational conventions: 134 DAT - Directional Airtime (Metric), the link metric specified in 135 this document, which is a directional variant of ETT. It does not 136 take reverse path loss into account. 138 QUEUE - a first in, first out queue of integers. 140 QUEUE[TAIL] - the most recent element in the queue. 142 add(QUEUE, value) - adds a new element to the TAIL of the queue. 144 remove(QUEUE) - removes the HEAD element of the queue 145 sum(QUEUE) - an operation which returns the sum of all elements in a 146 QUEUE. 148 diff_seqno(new, old) - an operation which returns the positive 149 distance between two elements of the circular sequence number 150 space defined in section 5.1 of [RFC5444]. Its value is either 151 (new - old) if this result is positive, or else its value is (new 152 - old + 65536). 154 MAX(a, b) - the maximum of a and b. 156 MIN(a, b) - the minimum of a and b. 158 UNDEFINED - a value not in the normal value range of a variable. 160 airtime - the time a transmitted packet blocks the link layer, e.g., 161 a wireless link. 163 ETX - Expected Transmission Count, a link metric proportional to the 164 number of transmissions to successfully send an IP packet over a 165 link. 167 ETT - Estimated Travel Time, a link metric proportional to the 168 amount of airtime needed to successfully transmit an IP packet 169 over a link, not considering layer-2 overhead created by preamble, 170 backoff time and queuing. 172 3. Applicability Statement 174 The Directional Airtime Metric was designed and tested (see 175 [COMNET15]) in wireless IEEE 802.11 OLSRv2 [RFC7181] networks. These 176 networks employ link layer retransmission to increase the delivery 177 probability. A dynamic rate selection algorithm selects the unicast 178 data rate independently for each neighbor. 180 As specified in OLSRv2, the metric calculates only the incoming link 181 cost. It does neither calculate the outgoing metric, nor does it 182 decide the link status (heard, symmetric, lost). 184 The metric works both for nodes which can send/receive [RFC5444] 185 packet sequence numbers and those which do not have this capability. 186 In the absence of such sequence numbers the metric calculates the 187 packet loss based on [RFC6130] HELLO message timeouts. 189 The metric must learn about the unicast data rate towards each one- 190 hop neighbor from an external process, either by configuration or by 191 an external measurement process. This measurement could be done via 192 gathering cross-layer data from the operating system, via an external 193 daemon like DLEP [DLEP], or via indirect layer-3 measurements like 194 packet-pair (see [MOBICOM04]). 196 The metric uses [RFC5444] multicast control traffic to determine the 197 link packet loss. The administrator should take care that link layer 198 multicast transmission do not have a higher reception probability 199 than the slowest unicast transmission without retransmission. For 200 example, with 802.11g, it might be necessary to increase the data- 201 rate of the multicast transmissions, e.g. set the multicast data-rate 202 to 6 MBit/s. 204 The metric can only handle a certain range of packet loss and unicast 205 data-rate. The maximum packet loss that can be encoded into the 206 metric is a loss of 7 of 8 packets (87.5%), without link layer 207 retransmissions. The unicast data-rate that can be encoded by this 208 metric can be between 1 kBit/s and 2 GBit/s. This metric has been 209 designed for data-rates of 1 MBit/s and hundreds of MBit/s. 211 4. Directional Airtime Metric Rationale 213 The Directional Airtime Metric has been inspired by the publications 214 on the ETX [MOBICOM03] and ETT [MOBICOM04] metric, but differs from 215 both of these in several ways. 217 Instead of measuring the combined loss probability of a bidirectional 218 transmission of a packet over a link in both directions, the 219 Directional Airtime Metric measures the incoming loss rate and 220 integrates the incoming linkspeed into the metric cost. There are 221 multiple reasons for this decision: 223 o OLSRv2 [RFC7181] defines the link metric as directional costs 224 between routers. 226 o Not all link layer implementations use acknowledgement mechanisms. 227 Most link layer implementations who do use them use less airtime 228 and a more robust modulation for the acknowledgement than the data 229 transmission, which makes it more likely for the data transmission 230 to be disrupted compared to the acknowledgement. 232 o Incoming packet loss and linkspeed can be measured locally, while 233 symmetric link loss would need an additional signaling TLV in the 234 [RFC6130] HELLO and would delay metric calculation by up to one 235 HELLO interval. 237 The Directional Airtime Metric does not integrate the packet size 238 into the link cost. Doing so is not feasible in most link-state 239 routing protocol implementations. The routing decision of most 240 operation systems don't take packet size into account. Multiplying 241 all link costs of a topology with the size of a data-plane packet 242 would never change the Dijkstra result anyways. 244 The queue based packet loss estimator specified in this document has 245 been tested extensively in the OLSR.org ETX implementation, see 246 Appendix B. The output is the average of the packet loss over a 247 configured time period. 249 The metric normally measures the loss of a link by tracking the 250 incoming [RFC5444] packet sequence numbers. Without these packet 251 sequence numbers, the metric does calculate the loss of the link 252 based of received and lost [RFC5444] HELLO messages. It uses the 253 incoming HELLO interval time (or if not present, the validity time) 254 to decide when a HELLO is lost. 256 When a neighbor router resets, its packet sequence number might jump 257 to a random value. The metric tries to detect jumps in the packet 258 sequence number and removes them from the data set, because the 259 already gathered link loss data should still be valid (see 260 Section 9.3. The link loss data is only removed from memory when a 261 Link times out completely and its Link Set tuple is removed from the 262 database. 264 5. Metric Functioning & Overview 266 The Directional Airtime Metric is calculated for each link set entry, 267 as defined in [RFC6130] section 7.1. 269 The metric processes two kinds of data into the metric value, namely 270 packet loss rate and link-speed. The link-speed is taken from an 271 external process not defined in this document. The current packet 272 loss rate is defined in this document by keeping track of packet 273 reception and packet loss events. It could also be calculated by an 274 external process with a compatible output. 276 Multiple incoming packet loss/reception events must be combined into 277 a loss rate to get a smooth metric. Experiments with exponential 278 weighted moving average (EWMA) lead to a highly fluctuating or a slow 279 converging metric (or both). To get a smoother and more controllable 280 metric result, this metric uses two fixed length queues to measure 281 and average the incoming packet events, one queue for received 282 packets and one for the estimated number of packets sent by the other 283 side of the link. 285 Because the rate of incoming packets is not uniform over time, the 286 queue contains a number of counters, each representing a fixed time 287 interval. Incoming packet loss and packet reception event are 288 accumulated in the current queue element until a timer adds a new 289 empty counter to both queues and remove the oldest counter from both. 291 In addition to the packet loss stored in the queue, this metric uses 292 a timer to detect a total link-loss. For every [RFC5444] HELLO 293 interval in which the metric received no packet from a neighbor, it 294 scales the number of received packets in the queue based on the total 295 time interval the queue represents compared to the total time of the 296 lost HELLO intervals. 298 The average packet loss ratio is calculated as the sum of the 'total 299 packets' counters divided by the sum of the 'packets received' 300 counters. This value is then divided through the current link-speed 301 and then scaled into the range of metrics allowed for OLSRv2. 303 The metric value is then used as L_in_metric of the Link Set (as 304 defined in section 8.1. of [RFC7181]). 306 While this document does not add new RFC5444 elements to the RFC6130 307 HELLO or RFC7181 TC messages, it works best when both the 308 INTERVAL_TIME message TLV is present in the HELLO messages and when 309 each RFC5444 packet contains an interface specific sequence number. 310 It also adds a number of new data entries to be stored for each 311 RFC6130 Link. 313 6. Protocol Constants 315 This specification defines the following constants, which define the 316 range of metric values that can be encoded by the DAT metric (see 317 Table 1). They cannot be changed without making the metric outputs 318 incomparable and should only be changed for a MANET with very slow or 319 very fast link layer. See Appendix E for example metric values. 321 DAT_MAXIMUM_LOSS - Fraction of the loss rate used in this routing 322 metric. Loss rate will be between 0/DAT_MAXIMUM_LOSS and 323 (DAT_MAXIMUM_LOSS-1)/DAT_MAXIMUM_LOSS. 325 DAT_MINIMUM_BITRATE - Minimal bit-rate in Bit/s used by this routing 326 metric. 328 +---------------------+-------+ 329 | Name | Value | 330 +---------------------+-------+ 331 | DAT_MAXIMUM_LOSS | 8 | 332 | | | 333 | DAT_MINIMUM_BITRATE | 1000 | 334 +---------------------+-------+ 336 Table 1: DAT Protocol Constants 338 7. Protocol Parameters 340 This specification defines the following parameters for this routing 341 metric. These parameters are: 343 DAT_MEMORY_LENGTH - Queue length for averaging packet loss. All 344 received and lost packets within the queue length are used to 345 calculate the cost of the link. 347 DAT_REFRESH_INTERVAL - interval in seconds between two metric 348 recalculations as described in Section 10.2. This value SHOULD be 349 smaller than a typical HELLO interval. The interval can be a 350 fraction of a second. 352 DAT_HELLO_TIMEOUT_FACTOR - multiplier relative to the HELLO_INTERVAL 353 (see [RFC6130] Section 5.3.1) after which the DAT metric considers 354 a HELLO as lost. 356 DAT_SEQNO_RESTART_DETECTION - threshold in number of missing packets 357 (based on received packet sequence numbers) at which point the 358 router considers the neighbor has restarted. This parameter is 359 only used for packet sequence number based loss estimation. This 360 number MUST be larger than DAT_MAXIMUM_LOSS. 362 7.1. Recommended Values 364 The proposed values of the protocol parameters are for Community Mesh 365 Networks, which mostly use routers that are not mobile. Using this 366 metric for mobile networks might require shorter DAT_REFRESH_INTERVAL 367 and/or DAT_MEMORY_LENGTH. 369 DAT_MEMORY_LENGTH := 64 371 DAT_REFRESH_INTERVAL := 1 373 DAT_HELLO_TIMEOUT_FACTOR := 1.2 375 DAT_SEQNO_RESTART_DETECTION := 256 377 8. Data Structures 379 This specification extends the Link Set of the Interface Information 380 Base, as defined in [RFC6130] section 7.1, by the adding the 381 following elements to each link tuple: 383 L_DAT_received - a QUEUE with DAT_MEMORY_LENGTH integer elements. 384 Each entry contains the number of successfully received packets 385 within an interval of DAT_REFRESH_INTERVAL. 387 L_DAT_total - a QUEUE with DAT_MEMORY_LENGTH integer elements. Each 388 entry contains the estimated number of packets transmitted by the 389 neighbor, based on the received packet sequence numbers within an 390 interval of DAT_REFRESH_INTERVAL. 392 L_DAT_packet_time - the time when the next RFC5444 packet should 393 have arrived. 395 L_DAT_hello_interval - the interval between two hello messages of 396 the links neighbor as signaled by the INTERVAL_TIME TLV [RFC5497] 397 of NHDP messages [RFC6130]. 399 L_DAT_lost_packet_intervals - the estimated number of HELLO 400 intervals from this neighbor the metric has not received a single 401 packet. 403 L_DAT_rx_bitrate - the current bitrate of incoming unicast traffic 404 for this neighbor. 406 L_DAT_last_pkt_seqno - the last received packet sequence number 407 received from this link. 409 Methods to obtain the value of L_DAT_rx_bitrate are out of the scope 410 of this specification. Such methods may include static configuration 411 via a configuration file or dynamic measurement through mechanisms 412 described in a separate specification (e.g. [DLEP]). Any Link tuple 413 with L_status = HEARD or L_status = SYMMETRIC MUST have a specified 414 value of L_DAT_rx_bitrate if it is to be used by this routing metric. 416 The incoming bitrate value should be stabilized by a hysteresis 417 filter to improve the stability of this metric. See Appendix C for 418 an example. 420 This specification updates the L_in_metric field of the Link Set of 421 the Interface Information Base, as defined in section 8.1. of 422 [RFC7181]) 424 8.1. Initial Values 426 When generating a new tuple in the Link Set, as defined in [RFC6130] 427 section 12.5 bullet 3, the values of the elements specified in 428 Section 8 are set as follows: 430 o L_DAT_received := 0, ..., 0. The queue always has 431 DAT_MEMORY_LENGTH elements. 433 o L_DAT_total := 0, ..., 0. The queue always has DAT_MEMORY_LENGTH 434 elements. 436 o L_DAT_packet_time := EXPIRED (no earlier RFC5444 packet received). 438 o L_DAT_hello_interval := UNDEFINED (no earlier NHDP HELLO 439 received). 441 o L_DAT_lost_packet_intervals := 0 (no HELLO interval without 442 packets). 444 o L_DAT_last_pkt_seqno := UNDEFINED (no earlier RFC5444 packet with 445 sequence number received). 447 9. Packets and Messages 449 This section describes the necessary changes of [RFC7181] 450 implementations with DAT metric for the processing and modification 451 of incoming and outgoing [RFC5444] data. 453 9.1. Definitions 455 For the purpose of this section, note the following definitions: 457 o "pkt_seqno" is defined as the [RFC5444] packet sequence number of 458 the received packet. 460 o "interval_time" is the time encoded in the INTERVAL_TIME message 461 TLV of a received [RFC6130] HELLO message. 463 o "validity_time" is the time encoded in the VALIDITY_TIME message 464 TLV of a received [RFC6130] HELLO message. 466 9.2. Requirements for using DAT metric in OLSRv2 implementations 468 An implementation of OLSRv2 using the metric specified by this 469 document SHOULD include the following parts into its [RFC5444] 470 output: 472 o an INTERVAL_TIME message TLV in each HELLO message, as defined in 473 [RFC6130] section 4.3.2. 475 o an interface specific packet sequence number as defined in 476 [RFC5444] section 5.1 which is incremented by 1 for each outgoing 477 [RFC5444] packet on the interface. 479 An implementation of OLSRv2 using the metric specified by this 480 document that inserts packet sequence numbers in some, but not all 481 outgoing [RFC5444] packets will make this metric ignore all packets 482 without the sequence number. Putting the INTERVAL_TIME TLV into 483 some, but not all Hello messages will make the timeout based loss 484 detection slower. This will only matter in the absence of packet 485 sequence numbers. 487 9.3. Link Loss Data Gathering 489 For each incoming [RFC5444] packet, additional processing SHOULD be 490 carried out after the packet messages have been processed as 491 specified in [RFC6130] and [RFC7181] as specified in this section. 493 [RFC5444] packets without packet sequence number MUST NOT be 494 processed in the way described in this section. 496 The router updates the Link Set Tuple corresponding to the originator 497 of the packet: 499 1. If L_DAT_last_pkt_seqno = UNDEFINED, then: 501 1. L_DAT_received[TAIL] := 1. 503 2. L_DAT_total[TAIL] := 1. 505 2. Otherwise: 507 1. L_DAT_received[TAIL] := L_DAT_received[TAIL] + 1. 509 2. diff := diff_seqno(pkt_seqno, L_DAT_last_pkt_seqno). 511 3. If diff > DAT_SEQNO_RESTART_DETECTION, then: 513 1. diff := 1. 515 4. L_DAT_total[TAIL] := L_DAT_total[TAIL] + diff. 517 3. L_DAT_last_pkt_seqno := pkt_seqno. 519 4. If L_DAT_hello_interval != UNDEFINED, then: 521 1. L_DAT_packet_time := current time + (L_DAT_hello_interval * 522 DAT_HELLO_TIMEOUT_FACTOR). 524 5. L_DAT_lost_packet_intervals := 0. 526 9.4. HELLO Message Processing 528 For each incoming HELLO Message, after it has been processed as 529 defined in [RFC6130] section 12, the Link Set Tuple corresponding to 530 the incoming HELLO message MUST be updated. 532 1. If the HELLO message contains an INTERVAL_TIME message TLV, then: 534 1. L_DAT_hello_interval := interval_time. 536 2. Otherwise: 538 1. L_DAT_hello_interval := validity_time. 540 3. If L_DAT_last_pkt_seqno = UNDEFINED, then: 542 1. L_DAT_received[TAIL] := L_DAT_received[TAIL] + 1. 544 2. L_DAT_total[TAIL] := L_DAT_total[TAIL] + 1. 546 3. L_DAT_packet_time := current time + (L_DAT_hello_interval * 547 DAT_HELLO_TIMEOUT_FACTOR). 549 10. Timer Event Handling 551 In addition to changes in the [RFC5444] processing/generation code, 552 the DAT metric also uses two timer events. 554 10.1. Packet Timeout Processing 556 When L_DAT_packet_time has timed out, the following step MUST be 557 done: 559 1. If L_DAT_last_pkt_seqno = UNDEFINED, then: 561 1. L_DAT_total[TAIL] := L_DAT_total[TAIL] + 1. 563 2. Otherwise: 565 1. L_DAT_lost_packet_intervals := L_DAT_lost_packet_intervals + 566 1. 568 3. L_DAT_packet_time := L_DAT_packet_time + L_DAT_hello_interval. 570 10.2. Metric Update 572 Once every DAT_REFRESH_INTERVAL, all L_in_metric values in all Link 573 Set entries MUST be recalculated: 575 1. sum_received := sum(L_DAT_received). 577 2. sum_total := sum(L_DAT_total). 579 3. If L_DAT_hello_interval != UNDEFINED and 580 L_DAT_lost_packet_intervals > 0, then: 582 1. lost_time_proportion := L_DAT_hello_interval * 583 L_DAT_lost_packet_intervals / DAT_MEMORY_LENGTH. 585 2. sum_received := sum_received * MAX ( 0, 1 - 586 lost_time_proportion); 588 4. If sum_received < 1, then: 590 1. L_in_metric := MAXIMUM_METRIC, as defined in [RFC7181] 591 section 5.6.1. 593 5. Otherwise: 595 1. loss := MIN(sum_total / sum_received, DAT_MAXIMUM_LOSS). 597 2. bitrate := MAX(L_DAT_rx_bitrate, DAT_MINIMUM_BITRATE). 599 3. L_in_metric := (2^24 / DAT_MAXIMUM_LOSS) * loss / (bitrate / 600 DAT_MINIMUM_BITRATE). 602 6. remove(L_DAT_total) 604 7. add(L_DAT_total, 0) 606 8. remove(L_DAT_received) 608 9. add(L_DAT_received, 0) 610 The calculated L_in_metric value should be stabilized by a hysteresis 611 function. See Appendix D for an example. 613 11. Security Considerations 615 Artificial manipulation of metrics values can drastically alter 616 network performance. In particular, advertising a higher L_in_metric 617 value may decrease the amount of incoming traffic, while advertising 618 lower L_in_metric may increase the amount of incoming traffic. By 619 artificially increasing or decreasing the L_in_metric values it 620 advertises, a rogue router may thus attract or repulse data traffic. 621 A rogue router may then potentially degrade data throughput by not 622 forwarding data as it should or redirecting traffic into routing 623 loops or bad links. It might also attract traffic for "Man in the 624 Middle" attacks or traffic analysis. 626 An attacker might also inject packets with incorrect packet level 627 sequence numbers, pretending to be somebody else. This attack can be 628 prevented by the true originator of the RFC5444 packets by adding a 629 [RFC7182] ICV Packet TLV and TIMESTAMP Packet TLV to each packet. 630 This allows the receiver to drop all incoming packets which have a 631 forged packet source, both packets generated by the attacker or 632 replayed packets. The security mechanism described in [RFC7183] does 633 not protect the sequence number used by the DAT metric because it 634 does only sign the RFC5444 messages, not the RFC5444 packet header 635 (which contains the RFC5444 packet sequence number). 637 Protection mechanisms against "Man in the Middle" attacks are 638 nevertheless out of scope of this document. 640 12. IANA Considerations 642 This document has no actions for IANA. 644 13. Acknowledgements 646 The authors would like to acknowledge the network administrators from 647 Freifunk Berlin [FREIFUNK] and Funkfeuer Vienna [FUNKFEUER] for 648 endless hours of testing and suggestions to improve the quality of 649 the original ETX metric for the OLSR.org routing daemon. 651 This effort/activity is supported by the European Community Framework 652 Program 7 within the Future Internet Research and Experimentation 653 Initiative (FIRE), Community Networks Testbed for the Future Internet 654 ([CONFINE]), contract FP7-288535. 656 The authors would like to gratefully acknowledge the following people 657 for intense technical discussions, early reviews and comments on the 658 specification and its components (listed alphabetically): Teco Boot 659 (Infinity Networks), Juliusz Chroboczek (PPS, University of Paris 7), 660 Thomas Clausen, Christopher Dearlove (BAE Systems Advanced Technology 661 Centre), Ulrich Herberg (Fujitsu Laboratories of America), Markus 662 Kittenberger (Funkfeuer Vienna), Joseph Macker (Naval Research 663 Laboratory), Fabian Nack (Freie Universitaet Berlin) and Stan Ratliff 664 (Cisco Systems). 666 14. References 668 14.1. Normative References 670 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 671 Requirement Levels", RFC 2119, BCP 14, March 1997. 673 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 674 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 675 Format", RFC 5444, February 2009. 677 [RFC5497] Clausen, T. and C. Dearlove, "Representing Multi-Value 678 Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497, March 679 2009. 681 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 682 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 683 RFC 6130, April 2011. 685 [RFC7181] Clausen, T., Jacquet, P., and C. Dearlove, "The Optimized 686 Link State Routing Protocol version 2", RFC 7181, April 687 2014. 689 14.2. Informative References 691 [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing 692 Protocol", RFC 3626, October 2003. 694 [RFC7182] Ulrich, U., Clausen, T., and C. Dearlove, "Integrity Check 695 Value and Timestamp TLV Definitions for Mobile Ad Hoc 696 Networks (MANETs)", RFC 7182, April 2014. 698 [RFC7183] Ulrich, U., Dearlove, C., and T. Clausen, "Integrity 699 Protection for the Neighborhood Discovery Protocol (NHDP) 700 and Optimized Link State Routing Protocol Version 2 701 (OLSRv2)", RFC 7183, April 2014. 703 [COMNET15] 704 Barz, C., Fuchs, C., Kirchhoff, J., Niewiejska, J., and H. 705 Rogge, "OLSRv2 for Community Networks: Using Directional 706 Airtime Metric with external radios", Elsevier Computer 707 Networks 2015 , September 2015, 708 . 710 [CONFINE] "Community Networks Testbed for the Future Internet 711 (CONFINE)", 2015, . 713 [DLEP] Ratliff, S., Berry, B., Harrison, G., Jury, S., and D. 714 Satterwhite, "Dynamic Link Exchange Protocol (DLEP)", 715 draft-ietf-manet-dlep-17 , October 2015. 717 [BATMAN] Neumann, A., Aichele, C., Lindner, M., and S. Wunderlich, 718 "Better Approach To Mobile Ad-hoc Networking 719 (B.A.T.M.A.N.)", draft-wunderlich-openmesh-manet- 720 routing-00 , April 2008. 722 [MOBICOM03] 723 De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A 724 High-Throughput Path Metric for Multi-Hop Wireless 725 Routing", Proceedings of the MOBICOM Conference , 2003. 727 [MOBICOM04] 728 Richard, D., Jitendra, P., and Z. Brian, "Routing in 729 Multi-Radio, Multi-Hop Wireless Mesh Networks", 730 Proceedings of the MOBICOM Conference , 2004. 732 [OLSR.org] 733 "The OLSR.org OLSR routing daemon", 2015, 734 . 736 [FREIFUNK] 737 "Freifunk Wireless Community Networks", 2015, 738 . 740 [FUNKFEUER] 741 "Austria Wireless Community Network", 2015, 742 . 744 Appendix A. Future work 746 As the DAT metric proved to work reasonably well for non- or slow- 747 moving ad hoc networks [COMNET15], it should be considered as a solid 748 first step on a way to better MANET metrics. There are multiple 749 parts of the DAT metric that need to be reviewed again in the context 750 of real world deployments and can be subject to later improvements. 752 The easiest part of the DAT metric to change and test would be the 753 timings parameters. A 1 minute interval for packet loss statistics 754 might be a good compromise for some MANETs, but could easily be too 755 large or to small for others. More data is needed to verify or 756 improve the current parameter selection. 758 The DAT metric considers only the multicast RFC5444 packet loss for 759 estimating the link loss, but it would be good to integrate unicast 760 data loss into the loss estimation. This information could be 761 provided directly from the link layer. This could increase the 762 accuracy of the loss rate estimation in scenarios, where the 763 assumptions regarding the ratio of multicast vs. unicast loss do not 764 hold. 766 The packet loss averaging algorithm could also be improved. While 767 the DAT metric provides a stable sliding time interval to average the 768 incoming packet loss and not giving the recent input too much 769 influence, first experiments suggest that the algorithm tends to be 770 less agile in detecting major changes of link quality. This makes it 771 less suited for mobile networks. A more agile algorithm is needed 772 for detecting major changes while filtering out random fluctuations 773 regarding frame loss. However, the current "queue of counters" 774 algorithm suggested for DAT outperforms the binary queue algorithm 775 and the exponential aging algorithms used for the ETX metric in the 776 OLSR [RFC3626] codebase of Olsr.org. 778 Appendix B. OLSR.org metric history 780 The Funkfeuer [FUNKFEUER] and Freifunk networks [FREIFUNK] are OLSR- 781 based [RFC3626] or B.A.T.M.A.N. [BATMAN] based wireless community 782 networks with hundreds of routers in permanent operation. The Vienna 783 Funkfeuer network in Austria, for instance, consists of 400 routers 784 covering the whole city of Vienna and beyond, spanning roughly 40km 785 in diameter. It has been in operation since 2003 and supplies its 786 users with Internet access. A particularity of the Vienna Funkfeuer 787 network is that it manages to provide Internet access through a city 788 wide, large scale Wi-Fi MANET, with just a single Internet uplink. 790 Operational experience of the OLSR project [OLSR.org] with these 791 networks have revealed that the use of hop-count as routing metric 792 leads to unsatisfactory network performance. Experiments with the 793 ETX metric [MOBICOM03] were therefore undertaken in parallel in the 794 Berlin Freifunk network as well as in the Vienna Funkfeuer network in 795 2004, and found satisfactory, i.e., sufficiently easy to implement 796 and providing sufficiently good performance. This metric has now 797 been in operational use in these networks for several years. 799 The ETX metric of a link is the estimated number of transmissions 800 required to successfully send a packet (each packet equal to or 801 smaller than MTU) over that link, until a link layer acknowledgement 802 is received. The ETX metric is additive, i.e., the ETX metric of a 803 path is the sum of the ETX metrics for each link on this path. 805 While the ETX metric delivers a reasonable performance, it doesn't 806 handle well networks with heterogeneous links that have different 807 bitrates. When using ETX metric, since every wireless link is 808 characterized only by its packet loss ratio, long-ranged links with 809 low bitrate (with low loss ratios) are preferred over short-ranged 810 links with high bitrate (with higher but reasonable loss ratios). 811 Such conditions, when they occur, can degrade the performance of a 812 network considerably, by not taking advantage of higher capacity 813 links. 815 Because of this the OLSR.org project has implemented the Directional 816 Airtime Metric for OLSRv2, which has been inspired by the Estimated 817 Travel Time (ETT) metric [MOBICOM04]. This metric uses an 818 unidirectional packet loss, but also takes the bitrate into account 819 to create a more accurate description of the relative costs or 820 capabilities of OLSRv2 links. 822 Appendix C. Linkspeed stabilization 824 The DAT metric specifies how to generate a reasonably stable packet 825 loss rate value based on incoming packet reception/loss events, but 826 the source of the linkspeed used in this document is considered an 827 external process. 829 In the presence of a layer-2 technology with variable linkspeed it is 830 likely that the raw linkspeed will be fluctuating too fast to be 831 useful for the DAT metric. 833 The amount of stabilization necessary for the linkspeed depends on 834 the implementation of the mac-layer, especially the rate control 835 algorithm. 837 Experiments with the Linux 802.11 wifi stack have shown that a simple 838 Median filter over a series of raw linkspeed measurements can smooth 839 the calculated value without introducing intermediate linkspeed 840 values one would obtain by using averaging or an exponential weighted 841 moving average. 843 Appendix D. Packet loss hysteresis 845 While the DAT metric uses a sliding window to compute a reasonably 846 stable frame loss, the implementation might choose to integrate an 847 additional hysteresis to prevent undesirable oscillations between two 848 values (i.e. metric flapping). 850 In Section Section 10.2 DAT calculates a fractional loss rate. The 851 fraction of 'loss := sum_total / sum_received' may result in minor 852 fluctuations in the advertised L_in_metric due to minimal changes in 853 sum_total or sum_received, which can cause undesirable protocol 854 churn. 856 A hysteresis function applied to the fraction could reduce the amount 857 of changes in the loss rate and help to further stabilize the metric 858 output. 860 Appendix E. Example DAT values 862 The DAT metric value can be expressed in terms of link speed (bit/s) 863 or used airtime (s). When using the default protocol constants (see 864 Section 6), DAT encodes link speeds between 119 bit/s and 2 Gbit/s. 866 Table Table 2 contains a few examples for metric values and their 867 meaning as a link speed: 869 +---------------------------+-----------+ 870 | Metric | bit/s | 871 +---------------------------+-----------+ 872 | MINIMUM_METRIC (1) | 2 Gbit/s | 873 | | | 874 | MAXIMUM_METRIC (16776960) | 119 bit/s | 875 | | | 876 | 2000 | 1 Mbit/s | 877 +---------------------------+-----------+ 879 Table 2: DAT link cost examples 881 A path metric value could also be expressed as a link speed, but this 882 would be less intuitive. An easier way to transform a path metric 883 value into a textual representation is to divide it by the hopcount 884 of the path and express the path cost as average link speed together 885 with the hopcount (see Table 3). 887 +---------+------+---------------+ 888 | Metric | hops | average bit/s | 889 +---------+------+---------------+ 890 | 4 | 2 | 1 Gbit/s | 891 | | | | 892 | 4000000 | 6 | 3 kbit/s | 893 +---------+------+---------------+ 895 Table 3: DAT link cost examples 897 Authors' Addresses 899 Henning Rogge 900 Fraunhofer FKIE 902 Email: henning.rogge@fkie.fraunhofer.de 903 URI: http://www.fkie.fraunhofer.de 904 Emmanuel Baccelli 905 INRIA 907 Email: Emmanuel.Baccelli@inria.fr 908 URI: http://www.emmanuelbaccelli.org/