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

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]