Packet Sequence Number based directional ETT Metric for OLSRv2
draft-rogge-baccelli-olsrv2-ett-metric-00

Abstract

This document specifies an Estimated Travel Time (ETT) link metric for usage in OLSRv2.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on December 19, 2013.

Copyright Notice

Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

Table of Contents

• 1. Introduction
• 2. Terminology
• 3. Applicability Statement
• 4. Directional Packet-Size Agnostic ETT
• 5. Protocol Functioning & Overview
• 6. Data Structures
• 7. Initial Values
• 8. Protocol Parameters
• 9. Packets and Messages
• 9.1. Packet Processing
• 10. HELLO Timeout
• 11. Periodic Metric Computation
• 12. Proposed Values for Parameters and Constants
• 13. Security Considerations
• 14. Acknowledgements
• 15. References
• 15.1. Normative References
• 15.2. Informative References
• Authors' Addresses

1. Introduction

The Funkfeuer [FUNKFEUER] and Freifunk networks [FREIFUNK] are OLSR-based [RFC3626] wireless community networks with hundreds of routers in permanent operation. The Vienna Funkfeuer network in Austria, for instance, consists of 400 routers (around 600 routes) covering the whole city of Vienna and beyond, spanning roughly 40km in diameter. It has been in operation since 2003 and supplies its users with Internet access. The particularity of the Vienna Funkfeuer network is that it manages to provide Internet access through a city wide, large scale Wi-Fi mesh cloud, with just a single uplink.

Operational experience with such a network has revealed that the use of hop-count as routing metric leads to unsatisfactory network performance. Experiments with the ETX metric [MOBICOM03] were therefore undertaken in parallel in the Berlin Freifunk network as well as in the Vienna Funkfeuer network, and found satisfactory, i.e. sufficiently easy to implement and providing sufficiently good performance. This metric has now been in operational use in these networks for more than 2 years.

This ETX metric of a link is the estimated number of transmissions required to successfully send a packet (each packet smaller than MTU) over that link, until an acknowledgement is received. The ETX metric is additive, i.e. the ETX metric of a path is the sum of the ETX metrics for each link on this path.

While the ETX metric delivers a reasonable performance, it doesn't handle networks with heterogeneous links that have different linkspeed well. Every link is only measured by its packet loss, the metric prefers long and slow links over short and fast links, which can degrade the performance of a network considerably.

Based on the ETX metric this document describes an Estimated Travel Time (ETT) metric [MOBICOM04] for the usage with the Optimized Link State Routing Protocol Version 2, which also takes the link-speed into account. More precisely, this document specifies the processing for NHDP [RFC6130] in order to establish the ETT metric value for a link.

2. Terminology

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

The terminology introduced in [RFC5444], [olsrv2] and [RFC6130], including the terms "packet", "message", "Address Block", "TLV Block","TLV", "address", "address prefix", and "address object" are to be interpreted as described therein.

Additionally, this document uses the following terminology and notational conventions:

LIFO

- a last in, first out queue of numbers.

LIFO[current]

- the most recent entry added to the queue.

push(LIFO, value)

- an operation which removes the oldest entry in the queue and places a new entry at the head of the queue.

sum(LIFO)

- an operation which returns the sum of all elements in a LIFO.

diff_seqno(new, old)

- an operation which returns the positive distance between two elements of the circular sequence number space defined in Section 5.1 of [RFC5444]. Its value is either (new - old) if this result is positive, or else its value is (new - old + 65536).

UNDEFINED

- a constant for -1.

3. Applicability Statement

The mechanism specified in this document is based on the ETX metric used daily by hundreds of routers in the Funkfeuer network [FUNKFEUER], as well as in similar OLSR-based wireless community networks which use the OLSR.org [OLSR.org] code base, such as [FREIFUNK], [AWMN], [NINUX], [GUIFI] and [OPENAIR]. Operational experience suggests that this mechanism is viable in (at least) these kinds of networks.

The ETT metric of the new OLSRv2 implementation of Olsr.org is a refinement of the ETX metric, providing a directional metric that takes into account the speed of the link to compute the link cost.

The ETX metric value of a link is established by measuring the rate of successful exchange of OLSRv2 control packets over that link, which use the format defined in [RFC5444]. ETX metric computation is thus based only on layer 3 signaling, and is therefore independent from underlying link layer technologies. Moreover, ETX metric computation does not require inspection of data traffic.

The ETT metric value can only be computed if the outgoing linkspeed to each one-hop neighbor is known to the routing daemon, either by measurement or from a configuration file.

4. Directional Packet-Size Agnostic ETT

The metric specified in this document is based on the Estimated Travel Time (ETT) metric published in [MOBICOM04].

The paper describes the metric as 'ETX divided by link-speed', but introduce a 'packet size' variable in the formula representation, describing the metric as 'ETX times packet-size divided by link-speed'.

This document specifies the use of a variant of the ETT metric without any packet-size variable integrated into the link costs. There are two reasons for this decision:

• The original ETT metric was designed for a DSR derived source-routed protocol. Typical linkstate protocols like OSLRv2 do not process each data-plane packet on its own, which makes it difficult to integrate the size of the data-plane packets into the routing metric.
• The original ETT metric assumes that the airtime spend on a link is proportional to the size of the packet transmitted over the link.
• Multiplying all topology edge costs 'ETX divided by link-speed' with the size of a packet would not change the result of the shortest path calculation, independently of the packet size. This means both description of ETT should result in the same next-hop decision.

In addition to this, the metric described in this document is directional, it does calculate the ETX value only based on the loss in one direction.

5. Protocol Functioning & Overview

Router A computes the ETX value of its link to router B by continuously estimating the loss rates for incoming traffic over this link. The ETT metric is calculated as the ETX metric, divided by a normalized link speed of the incoming unicast traffic and use this value as L_in_metric for NHDP (as defined in section 8.1. of NHDP).

6. Data Structures

This specification extends the Link Set per Interface Information Base, as defined in [RFC6130], with the following additional elements for each link tuple:

• L_METRIC_received_lifo is a LIFO queue with ETT_MEMORY_LENGTH integer elements. Each entry contains the number of successfully received [RFC5444] packets within an interval of ETT_METRIC_INTERVAL.
• L_METRIC_total_lifo is a LIFO queue with ETT_MEMORY_LENGTH integer elements. Each entry contains the estimated number of [RFC5444] packets transmitted by the neighbor, based on the received packet sequence numbers within an interval of ETT_METRIC_INTERVAL.
• L_METRIC_last_pkt_seqno is the last received packet sequence number received from this link.
• L_METRIC_hello_time is the time when the next hello will be expected. This is used to detect missing hellos by timeout [RFC5497].
• L_METRIC_hello_interval is the interval between two hello messages of the links neighbor as signaled by the INTERVAL_TIME TLV.
• L_METRIC_lost_hello_messages is the estimated number of lost hello messages from this neighbor, based on the value of the hello interval.
• L_METRIC_rx_bitrate is the current linkspeed of incoming unicast traffic for this neighbor.

Methods to obtain the value of L_METRIC_rx_bitrate are out of scope for this specification. Such methods may be static autoconfiguration via a configuration file, or dynamic measurement through mechanisms described in a separate specification. Any Link tuple with L_status = HEARD or L_status = SYMMETRIC MUST have a specified value of L_METRIC_rx_bitrate if it is to be used by this routing metric.

7. Initial Values

When generating a new tuple in the Link Set, the values of the elements specified above are set as follows:

• L_METRIC_received_lifo := 0, ..., 0.
• L_METRIC_total_lifo := 0, ..., 0.
• L_METRIC_last_pkt_seqno := UNDEFINED.
• L_METRIC_hello_time := EXPIRED.
• L_METRIC_hello_interval := UNDEFINED.
• L_METRIC_lost_hello_messages := 0

8. Protocol Parameters

This specification uses the parameters defined in [olsrv2]. This specification defines the following additional parameters:

ETT_MEMORY_LENGTH

- ETT algorithm memory length in seconds. All received and lost packets within this time period are used to calculate the ETT cost of the link.

ETT_METRIC_INTERVAL

- interval in seconds between two metric recalculations as described in Section 11.

ETT_SEQNO_RESTART_DETECTION

- threshold in number of missing packets (based on received packet sequence numbers) at which point the router considers the neighbor has restarted.

ETT_HELLO_TIMEOUT_FACTOR

- timeout factor for HELLO interval at which point a HELLO is definitely considered lost. The value must be a floating point number larger than 1.0.

ETT_WORST_ETX

- Maximum ETX value used in this routing metric.

ETT_BEST_LINKSPEED

- Maximum link speed in bits/s of used in routing metric.

ETT_WORST_LINKSPEED

- Minimum link speed in bits/s used in this metric.

ETT_NO_LOSS_METRIC_VALUE

- metric value for ETX 1.0 and ETT_WORST_LINKSPEED linkspeed.

9. Packets and Messages

Generated packets and messages use the format defined in [RFC5444]. The present specification adds the following constraints:

• A packet MUST contain a packet sequence number as defined in [RFC5444]. This sequence number MUST be interface specific and must be incremented by 1 for each packet.

9.1. Packet Processing

Each incoming packet is processed as defined in OLSRv2 [olsrv2]. Furthermore, the following additional processing MUST be carried out after the packet has been processed on the link set tuple corresponding to the source of the packet:

1. If L_METRIC_last_pkt_seqno = UNDEFINED, then:
   1. L_METRIC_received_lifo[current] := 1.
   2. L_METRIC_total_lifo[current] := 1.
2. Otherwise:
   1. L_METRIC_received_lifo[current] := L_METRIC_received_lifo[current] + 1.
   2. diff := seq_diff(seqno, L_METRIC_last_pkt_seqno).
   3. If diff > ETT_SEQNO_RESTART_DETECTION, then:
      1. diff := 1.
   4. L_METRIC_total_lifo[current] := L_METRIC_total_lifo[current] + diff.
3. L_METRIC_last_pkt_seqno := seqno.

10. HELLO Timeout

When L_METRIC_hello_time has timed out, the following step MUST be done:

1. L_METRIC_lost_hellos := L_METRIC_lost_hellos + 1.
2. L_METRIC_hello_time := L_METRIC_hello_time + L_METRIC_hello_interval.

11. Periodic Metric Computation

This metric stores the number of received packets per link from a neighbor and use the packet sequence number to calculate the total number of sent packets from the neighbor. The total number of packets divided by the number of received packets is used as an ETX value for the link.

If connectivity of link with a node is lost, no packets are received anymore and neither the received nor total value of packets will change. To prevent a constant result in this case, the metric stores the number of HELLO message interval timeouts since the last received packet from a neighbor and uses this value to reduce the received packet count proportionally to the length of the metric memory ETT_MEMORY_LENGTH.

Once every ETT_METRIC_INTERVAL, this protocol MUST recalculate all L_in_metric values in all Link Set entries:

1. sum_received := sum(L_METRIC_total_lifo).
2. sum_total := sum(L_METRIC_received_lifo).
3. If L_METRIC_hello_interval != UNDEFINED and L_METRIC_lost_hellos > 0, then:
   1. penalty := L_METRIC_hello_interval * L_METRIC_lost_hellos / ETT_MEMORY_LENGTH.
   2. sum_received := sum_received * ( 1 - penalty );
4. If sum_received < 1, then:
   1. L_METRIC_r_etx := UNDEFINED.
   2. L_in_metric := MAXIMUM_METRIC.
5. Otherwise:
   1. etx := sum_total / sum_received.
   2. If etx > ETT_WORST_ETX, then:
      1. etx := ETT_WORST_ETX.
   3. speed := L_METRIC_rx_bitrate.
   4. If speed > ETT_BEST_LINKSPEED, then:
      1. speed := ETT_BEST_LINKSPEED.
   5. If speed < ETT_WORST_LINKSPEED, then:
      1. speed := ETT_WORST_LINKSPEED.
   6. L_in_metric := ETT_NO_LOSS_METRIC_VALUE * etx / (speed / ETT_WORST_LINKSPEED).
6. push(L_METRIC_total_lifo, 0)
7. push(L_METRIC_received_lifo, 0)

12. Proposed Values for Parameters and Constants

This section proposes values for various parameters used in this specification.

• ETT_MEMORY_LENGTH := 64 seconds
• ETT_METRIC_INTERVAL := 1 second
• ETT_SEQNO_RESTART_DETECTION := 256
• ETT_HELLO_TIMEOUT_FACTOR := 1.5
• ETT_WORST_ETX := 16
• ETT_BEST_LINKSPEED := 256 MBit/s
• ETT_WORST_LINKSPEED := 1 MBit/s
• ETT_NO_LOSS_METRIC_VALUE := 4096

With this values this ETT metric will go from 16 (256+ MBit/s, ETX 1.0) over 4096 (1 MBit/s, ETX 1.0) to a maximum of 65536 (1 MBit/s, ETX 16.0).

13. Security Considerations

Artificial manipulation of metrics values can drastically alter network performance. In particular, advertising a higher L_in_metric value may decrease the amount of incoming traffic, while advertising lower L_in_metric may increase the amount of incoming traffic. By artificially increasing or decreasing the L_in_metric values it advertises, a rogue router may thus attract or repulse data traffic. A rogue router may then potentially degrade data throughput by not forwarding data as it should or redirecting traffic into routing loops or bad links.

14. Acknowledgements

The authors would like to acknowledge the network administrators from Freifunk Berlin [FREIFUNK] and Funkfeuer Vienna [FUNKFEUER] for endless hours of testing and suggestions to improve the quality of the original ETX metric for the olsr.org routing daemon.

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

The authors would like to gratefully acknowledge the following people for intense technical discussions, early reviews and comments on the specification and its components (listed alphabetically): Teco Boot (Infinity Networks), Thomas Clausen (LIX, Ecole Polytechnique), Christopher Dearlove (BAE Systems Advanced Technology Centre), Ulrich Herberg (Fujitsu Laboratories of America), Markus Kittenberger (Funkfeuer Vienna).

15. References

15.1. Normative References

15.2. Informative References

Authors' Addresses