idnits 2.17.1 draft-ietf-manet-olsrv2-dat-metric-09.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 13, 2015) is 3081 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'TAIL' is mentioned on line 551, 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 16, 2016 INRIA 6 November 13, 2015 8 Packet Sequence Number based directional airtime metric for OLSRv2 9 draft-ietf-manet-olsrv2-dat-metric-09 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 16, 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. 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 OLSR [RFC3626] is the lack of a 84 granular link cost metric between OLSR routers. Operational 85 experience with OLSR networks gathered since its publication has 86 revealed that wireless networks links can have highly variable and 87 heterogeneous properties. This makes a hopcount metric insufficient 88 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 ETX-derived OLSR.org 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 an useful 112 baseline to compare other metrics to. Appendix A contains a few 113 possible steps to improve the DAT 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 QUEUE - a first in, first out queue of integers. 130 QUEUE[TAIL] - the most recent element in the queue. 132 add(QUEUE, value) - adds a new element to the TAIL of the queue. 134 remove(QUEUE) - removes the HEAD element of the queue 136 sum(QUEUE) - an operation which returns the sum of all elements in a 137 QUEUE. 139 diff_seqno(new, old) - an operation which returns the positive 140 distance between two elements of the circular sequence number 141 space defined in section 5.1 of [RFC5444]. Its value is either 142 (new - old) if this result is positive, or else its value is (new 143 - old + 65536). 145 MAX(a,b) - the maximum of a and b. 147 UNDEFINED - a value not in the normal value range of a variable. 149 airtime - the time a transmitted packet blocks the link layer, e.g., 150 a wireless link. 152 ETX - Expected Transmission Count, a link metric proportional to the 153 number of transmissions to successfully send an IP packet over a 154 link. 156 ETT - Estimated Travel Time, a link metric proportional to the 157 amount of airtime needed to transmit an IP packet over a link, not 158 considering layer-2 overhead created by preamble, backoff time and 159 queuing. 161 DAT - Directional Airtime Metric, the link metric described in this 162 document, which is a directional variant of ETT. It does not take 163 reverse path loss into account. 165 3. Applicability Statement 167 The Directional Airtime Metric was designed and tested (see 168 [olsrv2_paper]) in wireless IEEE 802.11 OLSRv2 [RFC7181] networks. 169 These networks employ link layer retransmission to increase the 170 delivery probability and multiple unicast data rates. 172 As specified in OLSRv2 the metric calculates only the incoming link 173 cost. It does neither calculate the outgoing metric, nor does it 174 decide the link status (heard, symmetric, lost). 176 The metric works both for nodes which can send/receive [RFC5444] 177 packet sequence numbers and such which do not have this capability. 178 In the absence of such sequence numbers the metric calculates the 179 packet loss based on [RFC6130] HELLO message timeouts. 181 The metric must learn about the unicast data rate towards each one- 182 hop neighbor from an external process, either by configuration or by 183 an external measurement process. This measurement could be done by 184 gathering cross-layer data from the operating system or an external 185 daemon like DLEP [DLEP], but also by indirect layer-3 measurements 186 like packet-pair. 188 The metric uses RFC5444 multicast control traffic to determine the 189 link packet loss. The administrator should take care that link layer 190 multicast transmission do not not have a higher reception probability 191 than the slowest unicast transmission. It might, for example in 192 802.11g, be necessary to increase the data-rate of the multicast 193 transmissions, e.g. set the multicast data-rate to 6 MBit/s. 195 The metric can only handle a certain range of packet loss and unicast 196 data-rate. The maximum packet loss that can be encoded into the 197 metric a loss of 7 of 8 packets, without link layer retransmissions. 198 The unicast data-rate that can be encoded by this metric can be 199 between 1 kBit/s and 2 GBit/s. This metric has been designed for 200 data-rates of 1 MBit/s and hundreds of MBit/s. 202 4. Directional Airtime Metric Rationale 204 The Directional Airtime Metric has been inspired by the publications 205 on the ETX [MOBICOM03] and ETT [MOBICOM04] metric, but differs from 206 both of these in several ways. 208 Instead of measuring the combined loss probability of a bidirectional 209 transmission of a packet over a link in both directions, the 210 Directional Airtime Metric measures the incoming loss rate and 211 integrates the incoming linkspeed into the metric cost. There are 212 multiple reasons for this decision: 214 o OLSRv2 [RFC7181] defines the link metric as directional costs 215 between routers. 217 o Not all link layer implementations use acknowledgement mechanisms. 218 Most link layer implementations who do use them use less airtime 219 and a more robust modulation for the acknowledgement than the data 220 transmission, which makes it more likely for the data transmission 221 to be disrupted compared to the acknowledgement. 223 o Incoming packet loss and linkspeed can be measured locally, 224 symmetric link loss would need an additional signaling TLV in the 225 [RFC6130] HELLO and would delay metric calculation by up to one 226 HELLO interval. 228 The Directional Airtime Metric does not integrate the packet size 229 into the link cost. Doing so is not feasible in most link-state 230 routing protocol implementations. The routing decision of most 231 operation systems don't take packet size into account. Multiplying 232 all link costs of a topology with the size of a data-plane packet 233 would never change the Dijkstra result anyways. 235 The queue based packet loss estimator has been tested extensively in 236 the OLSR.org ETX implementation, see Appendix B. The output is the 237 average of the packet loss over a configured time period. 239 The metric normally measures the loss of a link by tracking the 240 incoming [RFC5444] packet sequence numbers. Without these packet 241 sequence numbers, the metric does calculate the loss of the link 242 based of received and lost [RFC5444] HELLO messages. It uses the 243 incoming HELLO interval time (or if not present, the validity time) 244 to decide when a HELLO is lost. 246 When a neighbor router resets, its packet sequence number might jump 247 to a random value. The metric tries to detect jumps in the packet 248 sequence number and removes them from the data set, because the 249 already gathered link loss data should still be valid (see 250 Section 9.3. The link loss data is only removed from memory when a 251 Link times out completely and its Link Set tuple is removed from the 252 database. 254 5. Metric Functioning & Overview 256 The Directional Airtime Metric is calculated for each link set entry, 257 as defined in [RFC6130] section 7.1. 259 The metric processes two kinds of data into the metric value, namely 260 packet loss rate and link-speed. The link-speed is taken from an 261 external process not defined in this document. The current packet 262 loss rate is defined in this document by keeping track of packet 263 reception and packet loss events. It could also be calculated by an 264 external process with a compatible output. 266 Multiple incoming packet loss/reception events must be combined into 267 a loss rate to get a smooth metric. Experiments with exponential 268 weighted moving average (EWMA) lead to a highly fluctuating or a slow 269 converging metric (or both). To get a smoother and more controllable 270 metric result, this metric uses two fixed length queues to measure 271 and average the incoming packet events, one queue for received 272 packets and one for the estimated number of packets sent by the other 273 side of the link. 275 Because the rate of incoming packets is not uniform over time, the 276 queue contains a number of counters, each representing a fixed time 277 interval. Incoming packet loss and packet reception event are 278 accumulated in the current queue element until a timer adds a new 279 empty counter to both queues and remove the oldest counter from both. 281 In addition to the packet loss stored in the queue, this metric uses 282 a timer to detect a total link-loss. For every [RFC5444] HELLO 283 interval in which the metric received no packet from a neighbor, it 284 scales the number of received packets in the queue based on the total 285 time interval the queue represents compared to the total time of the 286 lost HELLO intervals. 288 The average packet loss ratio is calculated as the sum of the 'total 289 packets' counters divided by the sum of the 'packets received' 290 counters. This value is then divided through the current link-speed 291 and then scaled into the range of metrics allowed for OLSRv2. 293 The metric value is then used as L_in_metric of the Link Set (as 294 defined in section 8.1. of [RFC7181]). 296 While this document does not add new RFC5444 elements to the RFC6130 297 HELLO or RFC7181 TC messages, it works best when both the 298 INTERVAL_TIME message TLV is present in the HELLO messages and when 299 each RFC5444 packet contains an interface specific sequence number. 300 It also adds a number of new data entries to be stored for each 301 RFC6130 Link. 303 6. Protocol Parameters 305 This specification defines the following parameters for this routing 306 metric. These parameters are: 308 DAT_MEMORY_LENGTH - Queue length for averaging packet loss. All 309 received and lost packets within the queue length are used to 310 calculate the cost of the link. 312 DAT_REFRESH_INTERVAL - interval in seconds between two metric 313 recalculations as described in Section 10.2. This value SHOULD be 314 smaller than a typical HELLO interval. The interval can be a 315 fraction of a second. 317 DAT_HELLO_TIMEOUT_FACTOR - multiplier relative to the HELLO_INTERVAL 318 (see [RFC6130] Section 5.3.1) after which the DAT metric considers 319 a HELLO as lost. 321 DAT_SEQNO_RESTART_DETECTION - threshold in number of missing packets 322 (based on received packet sequence numbers) at which point the 323 router considers the neighbor has restarted. This parameter is 324 only used for packet sequence number based loss estimation. This 325 number MUST be larger than DAT_MAXIMUM_LOSS. 327 6.1. Recommended Values 329 The proposed values of the protocol parameters are for Community Mesh 330 Networks, which mostly use immobile routers. Using this metric for 331 mobile networks might require shorter DAT_REFRESH_INTERVAL and/or 332 DAT_MEMORY_LENGTH. 334 DAT_MEMORY_LENGTH := 64 335 DAT_REFRESH_INTERVAL := 1 337 DAT_HELLO_TIMEOUT_FACTOR := 1.2 339 DAT_SEQNO_RESTART_DETECTION := 256 341 7. Protocol Constants 343 This specification defines the following constants, which define the 344 range of metric values that can be encoded by the DAT metric (see 345 Table 1). They cannot be changed without making the metric outputs 346 incomparable and should only be changed for MANET's with a very slow 347 or very fast linklayer. See Appendix D Appendix E for example metric 348 values. 350 DAT_MAXIMUM_LOSS - Fraction of the loss rate used in this routing 351 metric. Loss rate will be between 0/DAT_MAXIMUM_LOSS and 352 (DAT_MAXIMUM_LOSS-1)/DAT_MAXIMUM_LOSS. 354 DAT_MINIMUM_BITRATE - Minimal bit-rate in Bit/s used by this routing 355 metric. 357 +---------------------+-------+ 358 | Name | Value | 359 +---------------------+-------+ 360 | DAT_MAXIMUM_LOSS | 8 | 361 | | | 362 | DAT_MINIMUM_BITRATE | 1000 | 363 +---------------------+-------+ 365 Table 1: DAT Protocol Constants 367 8. Data Structures 369 This specification extends the Link Set of the Interface Information 370 Base, as defined in [RFC6130] section 7.1, by the adding the 371 following elements to each link tuple: 373 L_DAT_received - a QUEUE with DAT_MEMORY_LENGTH integer elements. 374 Each entry contains the number of successfully received packets 375 within an interval of DAT_REFRESH_INTERVAL. 377 L_DAT_total - a QUEUE with DAT_MEMORY_LENGTH integer elements. Each 378 entry contains the estimated number of packets transmitted by the 379 neighbor, based on the received packet sequence numbers within an 380 interval of DAT_REFRESH_INTERVAL. 382 L_DAT_packet_time - the time when the next RFC5444 packet should 383 have arrived. 385 L_DAT_hello_interval - the interval between two hello messages of 386 the links neighbor as signaled by the INTERVAL_TIME TLV [RFC5497] 387 of NHDP messages [RFC6130]. 389 L_DAT_lost_packet_intervals - the estimated number of HELLO 390 intervals from this neighbor the metric has not received a single 391 packet. 393 L_DAT_rx_bitrate - the current bitrate of incoming unicast traffic 394 for this neighbor. 396 L_DAT_last_pkt_seqno - the last received packet sequence number 397 received from this link. 399 Methods to obtain the value of L_DAT_rx_bitrate are out of the scope 400 of this specification. Such methods may include static configuration 401 via a configuration file or dynamic measurement through mechanisms 402 described in a separate specification (e.g. [DLEP]). Any Link tuple 403 with L_status = HEARD or L_status = SYMMETRIC MUST have a specified 404 value of L_DAT_rx_bitrate if it is to be used by this routing metric. 406 The incoming bitrate value should be stabilized by a hysteresis 407 filter to improve the stability of this metric. See Appendix B 408 Appendix C for an example. 410 This specification updates the L_in_metric field of the Link Set of 411 the Interface Information Base, as defined in section 8.1. of 412 [RFC7181]) 414 8.1. Initial Values 416 When generating a new tuple in the Link Set, as defined in [RFC6130] 417 section 12.5 bullet 3, the values of the elements specified in 418 Section 8 are set as follows: 420 o L_DAT_received := 0, ..., 0. The queue always has 421 DAT_MEMORY_LENGTH elements. 423 o L_DAT_total := 0, ..., 0. The queue always has DAT_MEMORY_LENGTH 424 elements. 426 o L_DAT_packet_time := EXPIRED (no earlier RFC5444 packet received). 428 o L_DAT_hello_interval := UNDEFINED (no earlier NHDP HELLO 429 received). 431 o L_DAT_lost_packet_intervals := 0 (no HELLO interval without 432 packets). 434 o L_DAT_last_pkt_seqno := UNDEFINED (no earlier RFC5444 packet with 435 sequence number received). 437 9. Packets and Messages 439 This section describes the necessary changes of [RFC7181] 440 implementations with DAT metric for the processing and modification 441 of incoming and outgoing [RFC5444] data. 443 9.1. Definitions 445 For the purpose of this section, note the following definitions: 447 o "pkt_seqno" is defined as the [RFC5444] packet sequence number of 448 the received packet. 450 o "interval_time" is the time encoded in the INTERVAL_TIME message 451 TLV of a received [RFC6130] HELLO message. 453 o "validity_time" is the time encoded in the VALIDITY_TIME message 454 TLV of a received [RFC6130] HELLO message. 456 9.2. Requirements for using DAT metric in OLSRv2 implementations 458 An implementation of OLSRv2 using the metric specified by this 459 document SHOULD include the following parts into its [RFC5444] 460 output: 462 o an INTERVAL_TIME message TLV in each HELLO message, as defined in 463 [RFC6130] section 4.3.2. 465 o an interface specific packet sequence number as defined in 466 [RFC5444] section 5.1 which is incremented by 1 for each outgoing 467 [RFC5444] packet on the interface. 469 An implementation of OLSRv2 using the metric specified by this 470 document that inserts packet sequence numbers in some, but not all 471 outgoing [RFC5444] packets will make this metric ignore all packets 472 without the sequence number. Putting the INTERVAL_TIME TLV into 473 some, but not all Hello messages will make the timeout based loss 474 detection slower. This will only matter in the absence of packet 475 sequence numbers. 477 9.3. Link Loss Data Gathering 479 For each incoming [RFC5444] packet, additional processing SHOULD be 480 carried out after the packet messages have been processed as 481 specified in [RFC6130] and [RFC7181] as specified in this section. 483 [RFC5444] packets without packet sequence number MUST NOT be 484 processed in the way described in this section. 486 The router updates the Link Set Tuple corresponding to the originator 487 of the packet: 489 1. If L_DAT_last_pkt_seqno = UNDEFINED, then: 491 1. L_DAT_received[TAIL] := 1. 493 2. L_DAT_total[TAIL] := 1. 495 2. Otherwise: 497 1. L_DAT_received[TAIL] := L_DAT_received[TAIL] + 1. 499 2. diff := diff_seqno(pkt_seqno, L_DAT_last_pkt_seqno). 501 3. If diff > DAT_SEQNO_RESTART_DETECTION, then: 503 1. diff := 1. 505 4. L_DAT_total[TAIL] := L_DAT_total[TAIL] + diff. 507 3. L_DAT_last_pkt_seqno := pkt_seqno. 509 4. If L_DAT_hello_interval != UNDEFINED, then: 511 1. L_DAT_packet_time := current time + (L_DAT_hello_interval * 512 DAT_HELLO_TIMEOUT_FACTOR). 514 5. L_DAT_lost_packet_intervals := 0. 516 9.4. HELLO Message Processing 518 For each incoming HELLO Message, after it has been processed as 519 defined in [RFC6130] section 12, the Link Set Tuple corresponding to 520 the incoming HELLO message MUST be updated. 522 1. If the HELLO message contains an INTERVAL_TIME message TLV, then: 524 1. L_DAT_hello_interval := interval_time. 526 2. Otherwise: 528 1. L_DAT_hello_interval := validity_time. 530 3. If L_DAT_last_pkt_seqno = UNDEFINED, then: 532 1. L_DAT_received[TAIL] := L_DAT_received[TAIL] + 1. 534 2. L_DAT_total[TAIL] := L_DAT_total[TAIL] + 1. 536 3. L_DAT_packet_time := current time + (L_DAT_hello_interval * 537 DAT_HELLO_TIMEOUT_FACTOR). 539 10. Timer Event Handling 541 In addition to changes in the [RFC5444] processing/generation code, 542 the DAT metric also uses two timer events. 544 10.1. Packet Timeout Processing 546 When L_DAT_packet_time has timed out, the following step MUST be 547 done: 549 1. If L_DAT_last_pkt_seqno = UNDEFINED, then: 551 1. L_DAT_total[TAIL] := L_DAT_total[TAIL] + 1. 553 2. Otherwise: 555 1. L_DAT_lost_packet_intervals := L_DAT_lost_packet_intervals + 556 1. 558 3. L_DAT_packet_time := L_DAT_packet_time + L_DAT_hello_interval. 560 10.2. Metric Update 562 Once every DAT_REFRESH_INTERVAL, all L_in_metric values in all Link 563 Set entries MUST be recalculated: 565 1. sum_received := sum(L_DAT_received). 567 2. sum_total := sum(L_DAT_total). 569 3. If L_DAT_hello_interval != UNDEFINED and 570 L_DAT_lost_packet_intervals > 0, then: 572 1. lost_time_proportion := L_DAT_hello_interval * 573 L_DAT_lost_packet_intervals / DAT_MEMORY_LENGTH. 575 2. sum_received := sum_received * MAX ( 0, 1 - 576 lost_time_proportion); 578 4. If sum_received < 1, then: 580 1. L_in_metric := MAXIMUM_METRIC, as defined in [RFC7181] 581 section 5.6.1. 583 5. Otherwise: 585 1. loss := sum_total / sum_received. 587 2. If loss > DAT_MAXIMUM_LOSS, then: 589 1. loss := DAT_MAXIMUM_LOSS. 591 3. bitrate := L_DAT_rx_bitrate. 593 4. If bitrate < DAT_MINIMUM_BITRATE, then: 595 1. bitrate := DAT_MINIMUM_BITRATE. 597 5. L_in_metric := (2^24 / DAT_MAXIMUM_LOSS) * loss / (bitrate / 598 DAT_MINIMUM_BITRATE). 600 6. remove(L_DAT_total) 602 7. add(L_DAT_total, 0) 604 8. remove(L_DAT_received) 606 9. add(L_DAT_received, 0) 608 The calculated L_in_metric value should be stabilized by a hysteresis 609 function. See Appendix C Appendix D for an example. 611 11. Security Considerations 613 Artificial manipulation of metrics values can drastically alter 614 network performance. In particular, advertising a higher L_in_metric 615 value may decrease the amount of incoming traffic, while advertising 616 lower L_in_metric may increase the amount of incoming traffic. By 617 artificially increasing or decreasing the L_in_metric values it 618 advertises, a rogue router may thus attract or repulse data traffic. 619 A rogue router may then potentially degrade data throughput by not 620 forwarding data as it should or redirecting traffic into routing 621 loops or bad links. 623 An attacker might also inject packets with incorrect packet level 624 sequence numbers, pretending to be somebody else. This attack can be 625 prevented by the true originator of the RFC5444 packets by adding a 626 [RFC7182] ICV Packet TLV and TIMESTAMP Packet TLV to each packet. 627 This allows the receiver to drop all incoming packets which have a 628 forged packet source, both packets generated by the attacker or 629 replayed packets. The signature scheme described in [RFC7183] does 630 not protect the additional sequence number of the DAT metric because 631 it does only sign the RFC5444 messages, not the RFC5444 packet 632 header. 634 12. Acknowledgements 636 The authors would like to acknowledge the network administrators from 637 Freifunk Berlin [FREIFUNK] and Funkfeuer Vienna [FUNKFEUER] for 638 endless hours of testing and suggestions to improve the quality of 639 the original ETX metric for the OLSR.org routing daemon. 641 This effort/activity is supported by the European Community Framework 642 Program 7 within the Future Internet Research and Experimentation 643 Initiative (FIRE), Community Networks Testbed for the Future Internet 644 ([CONFINE]), contract FP7-288535. 646 The authors would like to gratefully acknowledge the following people 647 for intense technical discussions, early reviews and comments on the 648 specification and its components (listed alphabetically): Teco Boot 649 (Infinity Networks), Juliusz Chroboczek (PPS, University of Paris 7), 650 Thomas Clausen, Christopher Dearlove (BAE Systems Advanced Technology 651 Centre), Ulrich Herberg (Fujitsu Laboratories of America), Markus 652 Kittenberger (Funkfeuer Vienna), Joseph Macker (Naval Research 653 Laboratory), Fabian Nack and Stan Ratliff (Cisco Systems). 655 13. References 657 13.1. Normative References 659 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 660 Requirement Levels", RFC 2119, BCP 14, March 1997. 662 [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, 663 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message 664 Format", RFC 5444, February 2009. 666 [RFC5497] Clausen, T. and C. Dearlove, "Representing Multi-Value 667 Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497, March 668 2009. 670 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 671 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 672 RFC 6130, April 2011. 674 [RFC7181] Clausen, T., Jacquet, P., and C. Dearlove, "The Optimized 675 Link State Routing Protocol version 2", RFC 7181, April 676 2014. 678 13.2. Informative References 680 [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing 681 Protocol", RFC 3626, October 2003. 683 [RFC7182] Ulrich, U., Clausen, T., and C. Dearlove, "Integrity Check 684 Value and Timestamp TLV Definitions for Mobile Ad Hoc 685 Networks (MANETs)", RFC 7182, April 2014. 687 [RFC7183] Ulrich, U., Dearlove, C., and T. Clausen, "Integrity 688 Protection for the Neighborhood Discovery Protocol (NHDP) 689 and Optimized Link State Routing Protocol Version 2 690 (OLSRv2)", RFC 7183, April 2014. 692 [olsrv2_paper] 693 C., C., C., C., J., J., J., J., and H. H., "OLSRv2 for 694 Community Networks: Using Directional Airtime Metric with 695 external radios", Elsevier Computer Networks 2015 , 696 September 2015, 697 . 699 [CONFINE] "Community Networks Testbed for the Future Internet 700 (CONFINE)", 2015, . 702 [DLEP] Ratliff, S., Berry, B., Harrison, G., Jury, S., and D. 703 Satterwhite, "Dynamic Link Exchange Protocol (DLEP)", 704 draft-ietf-manet-dlep-17 , March 2013. 706 [BATMAN] Neumann, A., Aichele, C., Lindner, M., and S. Wunderlich, 707 "Better Approach To Mobile Ad-hoc Networking 708 (B.A.T.M.A.N.)", draft-wunderlich-openmesh-manet- 709 routing-00 , April 2008. 711 [MOBICOM03] 712 De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A 713 High-Throughput Path Metric for Multi-Hop Wireless 714 Routing", Proceedings of the MOBICOM Conference , 2003. 716 [MOBICOM04] 717 Richard, D., Jitendra, P., and Z. Brian, "Routing in 718 Multi-Radio, Multi-Hop Wireless Mesh Networks", 719 Proceedings of the MOBICOM Conference , 2004. 721 [OLSR.org] 722 "The OLSR.org OLSR routing daemon", 2015, 723 . 725 [FREIFUNK] 726 "Freifunk Wireless Community Networks", 2015, 727 . 729 [FUNKFEUER] 730 "Austria Wireless Community Network", 2015, 731 . 733 Appendix A. Future work 735 As the DAT metric proved to work reasonable well for non- or slow- 736 moving ad hoc networks [olsrv2_paper], it should be considered as a 737 solid first step on a way to better MANET metrics. There are 738 multiple parts of the DAT metric that need to be reviewed again in 739 the context of real world deployments and can be subject to later 740 improvements. 742 The easiest part of the DAT metric to change and test would be the 743 timings parameters. A 1 minute interval for packet loss statistics 744 might be a good compromise for some MANETs, but could easily be too 745 large or to small for others. More data is needed to verify or 746 improve the current parameter selection. 748 The DAT metric considers only the multicast RFC5444 packet loss for 749 estimating the link loss, but it would be good to integrate unicast 750 data loss into the loss estimation. This information could be 751 provided directly from the link layer. This could increase the 752 accuracy of the loss rate estimation in scenarios, where the 753 assumptions regarding the ratio of multicast vs. unicast loss do not 754 hold. 756 The packet loss averaging algorithm could also be improved. While 757 the DAT metric provides a stable sliding time interval to average the 758 incoming packet loss and not giving the recent input too much 759 influence, However, first experiments suggest that the algorithm 760 tends to be less agile detecting major changes of link quality. This 761 makes it less suited for mobile networks. A more agile algorithm is 762 needed for detecting major changes while filtering out random 763 fluctuations regarding frame loss. However, the current "quere of 764 counters" algorithm suggested for DAT outperforms the binary queue 765 algorithm and the exponential aging algorithms used for the ETX 766 metric in the OLSR [RFC3626] codebase of Olsr.org. 768 Appendix B. OLSR.org metric history 770 The Funkfeuer [FUNKFEUER] and Freifunk networks [FREIFUNK] are OLSR- 771 based [RFC3626] or B.A.T.M.A.N. [BATMAN] based wireless community 772 networks with hundreds of routers in permanent operation. The Vienna 773 Funkfeuer network in Austria, for instance, consists of 400 routers 774 covering the whole city of Vienna and beyond, spanning roughly 40km 775 in diameter. It has been in operation since 2003 and supplies its 776 users with Internet access. A particularity of the Vienna Funkfeuer 777 network is that it manages to provide Internet access through a city 778 wide, large scale Wi-Fi MANET, with just a single Internet uplink. 780 Operational experience of the OLSR project [OLSR.org] with these 781 networks have revealed that the use of hop-count as routing metric 782 leads to unsatisfactory network performance. Experiments with the 783 ETX metric [MOBICOM03] were therefore undertaken in parallel in the 784 Berlin Freifunk network as well as in the Vienna Funkfeuer network in 785 2004, and found satisfactory, i.e., sufficiently easy to implement 786 and providing sufficiently good performance. This metric has now 787 been in operational use in these networks for several years. 789 The ETX metric of a link is the estimated number of transmissions 790 required to successfully send a packet (each packet equal to or 791 smaller than MTU) over that link, until a link layer acknowledgement 792 is received. The ETX metric is additive, i.e., the ETX metric of a 793 path is the sum of the ETX metrics for each link on this path. 795 While the ETX metric delivers a reasonable performance, it doesn't 796 handle well networks with heterogeneous links that have different 797 bitrates. Since every wireless link, when using ETX metric, is 798 characterized only by its packet loss ratio, the ETX metric prefers 799 long-ranged links with low bitrate (with low loss ratios) over short- 800 ranged links with high bitrate (with higher but reasonable loss 801 ratios). Such conditions, when they occur, can degrade the 802 performance of a network considerably by not taking advantage of 803 higher capacity links. 805 Because of this the OLSR.org project has implemented the Directional 806 Airtime Metric for OLSRv2, which has been inspired by the Estimated 807 Travel Time (ETT) metric [MOBICOM04]. This metric uses an 808 unidirectional packet loss, but also takes the bitrate into account 809 to create a more accurate description of the relative costs or 810 capabilities of OLSRv2 links. 812 Appendix C. Linkspeed stabilization 814 The DAT metric describes how to generate a reasonable stable packet 815 loss value from incoming packet reception/loss events, the source of 816 the linkspeed used in this document is considered an external 817 process. 819 In the presence of a layer-2 technology with variable linkspeed it is 820 likely that the raw linkspeed will be fluctuating too fast to be 821 useful for the DAT metric. 823 The amount of stabilization necessary for the linkspeed depends on 824 the implementation of the mac-layer, especially the rate control 825 algorithm. 827 Experiments with the Linux 802.11 wifi stack have shown that a simple 828 Median filter over a series of raw linkspeed measurements can smooth 829 the calculated value without introducing intermediate linkspeed 830 values you would get by using averaging or an exponential weighted 831 moving average. 833 Appendix D. Packet loss hysteresis 835 While the DAT metric use a sliding window to calculate a reasonable 836 stable frame loss, the implementation might choose to integrate an 837 additional hysteresis to prevent the metric flapping between two 838 values. 840 In Section Section 10.2 DAT caluclates a fractional loss rate. The 841 fraction of 'loss := sum_total / sum_received' may result in minor 842 fluctuations in the advertised L_in_metric due to minimal changes in 843 sum_total or sum_received which can cause undesirable protocol churn. 845 A hysteresis function applied to the fraction could reduce the amount 846 of changes in the loss rate and help to stabilize the metric output. 848 Appendix E. Example DAT values 850 The DAT metric value can be expressed in terms of link speed (bit/s) 851 or used airtime (s). When using the default protocol constants (see 852 Section 7), DAT encodes link speeds between 119 bit/s and 2 Gbit/s. 854 Table Table 2 contains a few examples for metric values and their 855 meaning as a link speed: 857 +---------------------------+-----------+ 858 | Metric | bit/s | 859 +---------------------------+-----------+ 860 | MINIMUM_METRIC (1) | 2 Gbit/s | 861 | | | 862 | MAXIMUM_METRIC (16776960) | 119 bit/s | 863 | | | 864 | 2000 | 1 Mbit/s | 865 +---------------------------+-----------+ 867 Table 2: DAT link cost examples 869 A path metric value could also be expressed as a link speed, but this 870 would be unintuitive and difficult to understand. An easier way to 871 transform a path metric value into a textual representation is to 872 divide it by the hopcount of the path and express the path cost as 873 average link speed together with the hopcount (see Table 3). 875 +---------+------+---------------+ 876 | Metric | hops | average bit/s | 877 +---------+------+---------------+ 878 | 4 | 2 | 1 Gbit/s | 879 | | | | 880 | 4000000 | 6 | 3 kbit/s | 881 +---------+------+---------------+ 883 Table 3: DAT link cost examples 885 Authors' Addresses 887 Henning Rogge 888 Fraunhofer FKIE 890 Email: henning.rogge@fkie.fraunhofer.de 891 URI: http://www.fkie.fraunhofer.de 893 Emmanuel Baccelli 894 INRIA 896 Email: Emmanuel.Baccelli@inria.fr 897 URI: http://www.emmanuelbaccelli.org/