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

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 January 09, 2014.

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. Metric Functioning & Overview
• 6. Protocol Parameters
• 7. Data Structures
• 8. Initial Values
• 9. Packets and Messages
• 9.1. Definitions
• 9.2. Packet Processing
• 9.3. HELLO Message Processing
• 10. HELLO Timeout
• 11. Periodic Metric Update
• 12. Proposed Values for Parameters and Constants
• 13. IANA Considerations
• 14. Security Considerations
• 15. Acknowledgements
• 16. References
• 16.1. Normative References
• 16.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. A 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 Internet uplink.

Operational experience with these networks have 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 many years.

The ETX metric of a link is the estimated number of transmissions required to successfully send a packet (each packet equal to or smaller than MTU) over that link, until a link-layer 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 bitrates well. Since every wireless link, when using ETX metric, is characterized only by its packet loss ratio, the ETX metric prefers long-ranged links with low bitrate (with low loss ratios) over short-ranged links with high bitrate (with higher but reasonable loss ratios). Such conditions, when they occur, can degrade the performance of a network considerably by not taking advantage of higher capacity links.

Based on the ETX metric this document describes an Estimated Travel Time (ETT) metric [MOBICOM04] for the Optimized Link State Routing Protocol Version 2. This ETT metric also takes the bitrate 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" and "TLV" are to be interpreted as described therein.

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

QUEUE

- a first in, first out queue of integers.

QUEUE[TAIL]

- the most recent element in the queue.

add(QUEUE, value)

- adds a new element to the TAIL of the queue.

remove(QUEUE)

- removes the HEAD element of the queue

sum(QUEUE)

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

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).

MAX(a,b)

- the maximum of a and b.

UNDEFINED

- a constant for -1.

airtime

- the time a transmitted packet blocks a shared medium, e.g., a wireless link.

ETX

- Expected Transmission Count, a link metric proportional to the number of transmissions to sucessfully send an IP packet over a link.

ETT

- Estimated Travel Time, a link metric proportional to the amount of airtime needed to transmit an IP packet over a link, not considering layer-2 overhead created by preamble, backoff time and queuing.

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, used in the OLSR.org implementation of [OLSRV2], is a refinement of the ETX metric that was used in the earlier [RFC3626] implementation. It provides a directional metric that takes packet loss and bitrate of the link into account 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 uses 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 bitrate of the incoming link traffic MUST be known by a router, performing the ETT calculation defined in this specification; either through direct measurement or indirectly delivered by an external source as operation system API, external processes or a configuration file.

Both ETX and ETT metric have been designed for networks with link-layer acknowledgement and retransmission mechanisms for user traffic.

4. Directional Packet-Size Agnostic ETT

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

[MOBICOM04] describes the metric as 'ETX divided by bitrate', but also introduce a 'packet size' variable in the formula representation, describing the metric as 'ETX times packet-size divided by bitrate'.

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

• The original ETT metric was designed for a DSR derived source-routed protocol. Typical link-state 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 spent on a link is proportional to the size of the packet transmitted over the link.
• Multiplying all topology edge costs 'ETX divided by bitrate' 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 packet loss at the receiver.

5. Metric Functioning & Overview

Router A computes the ETX value of a link between an interface of router A and an interface of router B by continuously estimating the loss rates for incoming traffic over this link.

To measure the loss rate of a link, this metric stores the packet sequence number of the last incoming [RFC5444] packet of this link. If one or more consecutive numbers are missing between a received packet and the last one, the metric considers this packets to be lost.

The incoming link bitrate is defined external to this specification, either by measurement or through an administrative process. The bitrate should reflect the datarate of the unicast traffic traveling over this link.

The ETT metric is calculated as the ETX metric, divided by the normalized bitrate of the incoming traffic from the neighbor. This value is then used as L_in_metric of the Link Set (as defined in section 8.1. of [OLSRV2]).

6. Protocol Parameters

This specification defines the following parameters:

ETT_MEMORY_LENGTH

- ETT algorithm queue length. All received and lost packets within the queue are used to calculate the ETT cost of the link.

ETT_REFRESH_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_BITRATE

- Maximum bitrate in bits/s of used in routing metric.

ETT_WORST_BITRATE

- Minimum bitrate in bits/s used in this metric.

ETT_WORST_NO_LOSS_METRIC_VALUE

- metric value for ETX 1.0 and ETT_WORST_BITRATE bitrate.

7. Data Structures

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

L_ETT_received

is a QUEUE with ETT_MEMORY_LENGTH integer elements. Each entry contains the number of successfully received [RFC5444] packets within an interval of ETT_REFRESH_INTERVAL.

L_ETT_total

is a 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_REFRESH_INTERVAL.

L_ETT_last_pkt_seqno

is the last received packet sequence number received from this link.

L_ETT_hello_time

is the time when the next hello will be expected.

L_ETT_hello_interval

is the interval between two hello messages of the links neighbor as signaled by the INTERVAL_TIME TLV [RFC5497] of NHDP messages [RFC6130].

L_ETT_lost_hello_messages

is the estimated number of lost hello messages from this neighbor, based on the value of the hello interval.

L_ETT_rx_bitrate

is the current bitrate of incoming unicast traffic for this neighbor.

Methods to obtain the value of L_ETT_rx_bitrate are out of scope for this specification. Such methods may be static configuration 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_ETT_rx_bitrate if it is to be used by this routing metric.

8. Initial Values

When generating a new tuple in the Link Set, as defined in [RFC6130] section 12.5 bullet 3, the values of the elements specified in Section 7 are set as follows:

• L_ETT_received := 0, ..., 0. The queue always have ETT_MEMORY_LENGTH elements.
• L_ETT_total := 0, ..., 0. The queue always have ETT_MEMORY_LENGTH elements.
• L_ETT_last_pkt_seqno := UNDEFINED.
• L_ETT_hello_time := EXPIRED.
• L_ETT_hello_interval := UNDEFINED.
• L_ETT_lost_hello_messages := 0

9. Packets and Messages

Generated packets and messages use the format defined in [RFC5444]. This ETT metric does neither create RFC5444 messages on its own, nor does it define new TLV types for existing message types.

An implementation of OLSRv2, using the metric specified by this document, MUST include the following parts into its [RFC5444] output:

• an interface specific packet sequence number as defined in [RFC5444] section 5.1 which is incremented by 1 for each outgoing [RFC5444] packet on the interface.
• an INTERVAL_TIME message TLV in each Hello message, as defined in [RFC6130] section 4.3.2.

9.1. Definitions

For the purpose of this section, note the following definitions:

• "pkt_seqno" is defined as the [RFC5444] packet sequence number of the received packet.
• "interval_time" is the time encoded in the INTERVAL_TIME message TLV of a received [RFC6130] HELLO message.

9.2. Packet Processing

For each incoming [RFC5444] packet, additional processing MUST be carried out after the packets messages have been processed as specified in [RFC6130] and [OLSRV2].

[RFC5444] packets without packet sequence number MUST NOT be processed by this metric.

The router MUST update the Link Set Tuple corresponding to the originator of the packet:

1. If L_ETT_last_pkt_seqno = UNDEFINED, then:
   1. L_ETT_received[TAIL] := 1.
   2. L_ETT_total[TAIL] := 1.
2. Otherwise:
   1. L_ETT_received[TAIL] := L_ETT_received[TAIL] + 1.
   2. diff := seq_diff(pkt_seqno, L_ETT_last_pkt_seqno).
   3. If diff > ETT_SEQNO_RESTART_DETECTION, then:
      1. diff := 1.
   4. L_ETT_total[TAIL] := L_ETT_total[TAIL] + diff.
3. L_ETT_last_pkt_seqno := pkt_seqno.
4. If L_ETT_hello_interval != UNDEFINED, then:
   1. L_ETT_hello_time := current time + (L_ETT_hello_interval * ETT_HELLO_TIMEOUT_FACTOR).
5. L_ETT_lost_hello_messages := 0.

9.3. HELLO Message Processing

For each incoming HELLO Message, after it has been processed as defined in [RFC6130] section 12, the Link Set Tuple corresponding to the incoming HELLO message must be updated.

Only HELLO Messages with an INTERVAL_TIME message TLVs must be processed.

1. L_ETT_hello_interval := interval_time.

10. HELLO Timeout

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

1. L_ETT_lost_hello_messages := L_ETT_lost_hello_messages + 1.
2. L_ETT_hello_time := L_ETT_hello_time + L_ETT_hello_interval.

11. Periodic Metric Update

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_REFRESH_INTERVAL, this protocol MUST recalculate all L_in_metric values in all Link Set entries:

1. sum_received := sum(L_ETT_total).
2. sum_total := sum(L_ETT_received).
3. If L_ETT_hello_interval != UNDEFINED and L_ETT_lost_hellos > 0, then:
   1. penalty := L_ETT_hello_interval * L_ETT_lost_hellos / ETT_MEMORY_LENGTH.
   2. sum_received := sum_received * MAX ( 0, 1 - penalty );
4. If sum_received < 1, then:
   1. L_ETT_r_etx := UNDEFINED.
   2. L_in_metric := MAXIMUM_METRIC, as defined in [OLSRV2] section 5.6.1.
5. Otherwise:
   1. etx := sum_total / sum_received.
   2. If etx > ETT_WORST_ETX, then:
      1. etx := ETT_WORST_ETX.
   3. bitrate := L_ETT_rx_bitrate.
   4. If bitrate > ETT_BEST_BITRATE, then:
      1. bitrate := ETT_BEST_BITRATE.
   5. If bitrate < ETT_WORST_BITRATE, then:
      1. bitrate := ETT_WORST_BITRATE.
   6. L_in_metric := ETT_WORST_NO_LOSS_METRIC_VALUE * etx / (bitrate / ETT_WORST_BITRATE).
6. remove(L_ETT_total)
7. add(L_ETT_total, 0)
8. remove(L_ETT_received)
9. add(L_ETT_received, 0)

12. Proposed Values for Parameters and Constants

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

• ETT_MEMORY_LENGTH := 64
• ETT_REFRESH_INTERVAL := 1 second
• ETT_SEQNO_RESTART_DETECTION := 256
• ETT_HELLO_TIMEOUT_FACTOR := 1.5
• ETT_WORST_ETX := 16
• ETT_BEST_BITRATE := 256 MBit/s
• ETT_WORST_BITRATE := 1 MBit/s
• ETT_WORST_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).

The settings were chosen based on the deployment of the original ETX metric in the Funkfeuer community mesh network. They allow the existence of both priority links (links faster than any ETT link) and backup links (links slower than any ETT link) and should deliver a reasonable performance for non-moving mesh networks.

For mobile mesh deployments the administrator should decrease both the memory length and refresh interval to allow a faster metric change.

13. IANA Considerations

This document contains no actions for IANA.

14. 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.

An attacker might also inject packets with incorrect packet-level sequence numbers, pretending to be somebody else. This attack could be prevented by the true originator of the RFC5444 packets by adding a [RFC6622] ICV Packet TLV and TIMESTAMP Packet TLV to each packet. This allows the receiver to drop all incoming packets which have a forged packet source, both packets generated by the attacker or replayed earlier packets by the original sender.

15. 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, Christopher Dearlove (BAE Systems Advanced Technology Centre), Ulrich Herberg (Fujitsu Laboratories of America), Markus Kittenberger (Funkfeuer Vienna) and Joseph Macker (Naval Research Laboratory).

16. References

16.1. Normative References

16.2. Informative References

Authors' Addresses