MANET H. Rogge
Internet-Draft Fraunhofer FKIE
Intended status: Informational E. Baccelli
Expires: December 19, 2013 INRIA
June 17, 2013
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.
Rogge & Baccelli Expires December 19, 2013 [Page 1]
Internet-Draft Directional ETT for OLSRv2 June 2013
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Applicability Statement . . . . . . . . . . . . . . . . . . . 4
4. Directional Packet-Size Agnostic ETT . . . . . . . . . . . . . 5
5. Protocol Functioning & Overview . . . . . . . . . . . . . . . 5
6. Data Structures . . . . . . . . . . . . . . . . . . . . . . . 6
7. Initial Values . . . . . . . . . . . . . . . . . . . . . . . . 6
8. Protocol Parameters . . . . . . . . . . . . . . . . . . . . . 7
9. Packets and Messages . . . . . . . . . . . . . . . . . . . . . 7
9.1. Packet Processing . . . . . . . . . . . . . . . . . . . . 8
10. HELLO Timeout . . . . . . . . . . . . . . . . . . . . . . . . 8
11. Periodic Metric Computation . . . . . . . . . . . . . . . . . 9
12. Proposed Values for Parameters and Constants . . . . . . . . . 10
13. Security Considerations . . . . . . . . . . . . . . . . . . . 10
14. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 11
15. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11
15.1. Normative References . . . . . . . . . . . . . . . . . . . 11
15.2. Informative References . . . . . . . . . . . . . . . . . . 12
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12
Rogge & Baccelli Expires December 19, 2013 [Page 2]
Internet-Draft Directional ETT for OLSRv2 June 2013
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].
Rogge & Baccelli Expires December 19, 2013 [Page 3]
Internet-Draft Directional ETT for OLSRv2 June 2013
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.
Rogge & Baccelli Expires December 19, 2013 [Page 4]
Internet-Draft Directional ETT for OLSRv2 June 2013
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:
o 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.
o The original ETT metric assumes that the airtime spend on a link
is proportional to the size of the packet transmitted over the
link.
o 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).
Rogge & Baccelli Expires December 19, 2013 [Page 5]
Internet-Draft Directional ETT for OLSRv2 June 2013
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.
Rogge & Baccelli Expires December 19, 2013 [Page 6]
Internet-Draft Directional ETT for OLSRv2 June 2013
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:
Rogge & Baccelli Expires December 19, 2013 [Page 7]
Internet-Draft Directional ETT for OLSRv2 June 2013
o 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.
Rogge & Baccelli Expires December 19, 2013 [Page 8]
Internet-Draft Directional ETT for OLSRv2 June 2013
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.
Rogge & Baccelli Expires December 19, 2013 [Page 9]
Internet-Draft Directional ETT for OLSRv2 June 2013
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.
o ETT_MEMORY_LENGTH := 64 seconds
o ETT_METRIC_INTERVAL := 1 second
o ETT_SEQNO_RESTART_DETECTION := 256
o ETT_HELLO_TIMEOUT_FACTOR := 1.5
o ETT_WORST_ETX := 16
o ETT_BEST_LINKSPEED := 256 MBit/s
o ETT_WORST_LINKSPEED := 1 MBit/s
o 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
Rogge & Baccelli Expires December 19, 2013 [Page 10]
Internet-Draft Directional ETT for OLSRv2 June 2013
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
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", RFC 2119, BCP 14, March 1997.
[RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State Routing
Protocol", RFC 3626, October 2003.
[RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih,
"Generalized Mobile Ad Hoc Network (MANET) Packet/Message
Format", RFC 5444, February 2009.
[RFC5497] Clausen, T. and C. Dearlove, "Representing Multi-Value
Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497,
March 2009.
[RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc
Network (MANET) Neighborhood Discovery Protocol (NHDP)",
Rogge & Baccelli Expires December 19, 2013 [Page 11]
Internet-Draft Directional ETT for OLSRv2 June 2013
RFC 6130, April 2011.
15.2. Informative References
[CONFINE] "Community Networks Testbed for the Future Internet
(CONFINE)", 2013, <http://www.confine-project.eu>.
[olsrv2] Clausen, T., Jacquet, P., and C. Dearlove, "The Optimized
Link State Routing Protocol version 2",
draft-ietf-manet-olsrv2-19 , March 2013.
[MOBICOM03]
De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A
High-Throughput Path Metric for Multi-Hop Wireless
Routing", Proceedings of the MOBICOM Conference , 2003.
[MOBICOM04]
Richard, D., Jitendra, P., and Z. Brian, "Routing in
Multi-Radio, Multi-Hop Wireless Mesh Networks",
Proceedings of the MOBICOM Conference , 2004.
[OLSR.org]
"The olsr.org OLSR routing daemon", 2013,
<http://www.olsr.org/>.
[FREIFUNK]
"Freifunk Wireless Community Networks", 2013,
<http://www.freifunk.net>.
[FUNKFEUER]
"Austria Wireless Community Network", 2013,
<http://www.funkfeuer.at>.
[AWMN] "Athens Wireless Community Network", 2013,
<http://awmn.net>.
[GUIFI] "Barcelona Wireless Community Network", 2013,
<http://www.guifi.net>.
[NINUX] "Roma Wireless Community Network", 2013,
<http://www.ninux.org>.
[OPENAIR] "Boston Wireless Community Network", 2013,
<http://openairboston.net>.
Rogge & Baccelli Expires December 19, 2013 [Page 12]
Internet-Draft Directional ETT for OLSRv2 June 2013
Authors' Addresses
Henning Rogge
Fraunhofer FKIE
Email: henning.rogge@fkie.fraunhofer.de
URI: http://www.fkie.fraunhofer.de
Emmanuel Baccelli
INRIA
Email: Emmanuel.Baccelli@inria.fr
URI: http://www.emmanuelbaccelli.org/
Rogge & Baccelli Expires December 19, 2013 [Page 13]