Internet DRAFT - draft-wunderlich-openmesh-manet-routing

draft-wunderlich-openmesh-manet-routing






Network Working Group                                         A. Neumann
Internet-Draft                                                C. Aichele
Intended status: Experimental                                 M. Lindner
Expires: October 9, 2008                                   S. Wunderlich
                                                            Apr 07, 2008


       Better Approach To Mobile Ad-hoc Networking (B.A.T.M.A.N.)
               draft-wunderlich-openmesh-manet-routing-00

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

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

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on October 9, 2008.

Copyright Notice

   Copyright (C) The IETF Trust (2008).

Abstract

   This document specifies a simple and robust algorithm for
   establishing multi-hop routes in mobile ad-hoc networks.  It ensures
   highly adaptive and loop-free routing while causing only low
   processing and traffic cost.






Neumann, et al.          Expires October 9, 2008                [Page 1]

Internet-Draft              Abbreviated Title                   Apr 2008


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
     1.1.  Terminology  . . . . . . . . . . . . . . . . . . . . . . .  4
     1.2.  Protocol Overview  . . . . . . . . . . . . . . . . . . . .  4
   2.  Protocol and Port Number . . . . . . . . . . . . . . . . . . .  6
   3.  B.A.T.M.A.N. Packet Formats  . . . . . . . . . . . . . . . . .  6
     3.1.  General B.A.T.M.A.N. Packet Format . . . . . . . . . . . .  6
     3.2.  Originator Message (OGM) Format  . . . . . . . . . . . . .  8
       3.2.1.  Originator Message (OGM) Fields  . . . . . . . . . . .  8
     3.3.  HNA Message Format . . . . . . . . . . . . . . . . . . . .  9
       3.3.1.  HNA Message Fields . . . . . . . . . . . . . . . . . .  9
   4.  Conceptual Data Structures . . . . . . . . . . . . . . . . . .  9
     4.1.  Originator List  . . . . . . . . . . . . . . . . . . . . .  9
     4.2.  Sequence Numbers, Ranges, and Windows  . . . . . . . . . . 11
   5.  Flooding Mechanism . . . . . . . . . . . . . . . . . . . . . . 13
     5.1.  Broadcasting own Originator Messages (OGMs)  . . . . . . . 13
     5.2.  Receiving Originator Messages  . . . . . . . . . . . . . . 14
     5.3.  Bidirectional Link Check . . . . . . . . . . . . . . . . . 14
     5.4.  Neighbor Ranking . . . . . . . . . . . . . . . . . . . . . 15
     5.5.  Re-broadcasting other nodes' OGMs  . . . . . . . . . . . . 15
   6.  Routing  . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
     6.1.  Route Selection and Establishing . . . . . . . . . . . . . 16
     6.2.  Route Deletion . . . . . . . . . . . . . . . . . . . . . . 17
     6.3.  Opportunistic Routing Deletion Policy  . . . . . . . . . . 17
       6.3.1.  Opportunistic Routing Deletion Policy Consideration  . 17
   7.  Gateway  . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
     7.1.  Gateway Announcement . . . . . . . . . . . . . . . . . . . 17
     7.2.  Gateway Selection  . . . . . . . . . . . . . . . . . . . . 18
     7.3.  Gateway Tunneling/Encapsulation  . . . . . . . . . . . . . 19
     7.4.  Gateway hopping (testing/accepting)  . . . . . . . . . . . 19
   8.  Proposed Values for Constants  . . . . . . . . . . . . . . . . 19
   9.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 20
   10. Security Considerations  . . . . . . . . . . . . . . . . . . . 20
     10.1. Confidentiality  . . . . . . . . . . . . . . . . . . . . . 20
     10.2. Overflow of routing entries  . . . . . . . . . . . . . . . 20
     10.3. Route manipulation . . . . . . . . . . . . . . . . . . . . 21
   11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21
     11.1. Normative References . . . . . . . . . . . . . . . . . . . 21
     11.2. Informative References . . . . . . . . . . . . . . . . . . 22
   Appendix A.  Contributors  . . . . . . . . . . . . . . . . . . . . 22
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22
   Intellectual Property and Copyright Statements . . . . . . . . . . 24








Neumann, et al.          Expires October 9, 2008                [Page 2]

Internet-Draft              Abbreviated Title                   Apr 2008


1.  Introduction

   B.A.T.M.A.N. is a proactive routing protocol for Wireless Ad-hoc Mesh
   Networks, including (but not limited to) Mobile Ad-hoc Networks
   (MANETs).  The protocol proactively maintains information about the
   existence of all nodes in the mesh that are accessible via single-hop
   or multi-hop communication links.  The strategy of B.A.T.M.A.N. is to
   determine for each destination in the mesh one single-hop neighbor,
   which can be utilized as best gateway to communicate with the
   destination node.  In order to perform multi-hop IP-based routing,
   the routing table of a node must contain a link-local gateway for
   each host or network route.  To learn about the best next-hop for
   each destination is all that the B.A.T.M.A.N. algorithm cares about.
   There is no need to find out or calculate the complete route, which
   makes a very fast and efficient implementation possible.

   Wireless mesh networks have special difficulties unlike wired
   networks: Data packets can and will get lost in noisy areas.  Mesh
   networks consisting of nodes with only one wireless communication
   interface (which are usually operating on the same wireless channel)
   have to cope with self-inflicted interference caused by their own
   wireless traffic.  Thus communication links may have varying quality
   in terms of packet loss, data rates, and interference.  Even the
   protocol traffic from the routing protocol itself causes
   interference.  Therefore communication link quality changes even in
   static network topologies.  New links appear and known links
   disappear frequently, especially in MANETs.  The quality of one
   communication direction may differ to the opposite direction ( e.g.
   asymmetric links).

   B.A.T.M.A.N. considers these challenges by doing statistical analysis
   of protocol packet loss and propagation speed and does not depend on
   state or topology information from other nodes.  Rather than trusting
   on metadata contained in received protocol traffic - which could be
   delayed, outdated, or lost - routing decisions are based on the
   knowledge about the existence or lack of information.  B.A.T.M.A.N.
   protocol packets contain only a very limited amount of information
   and are therefore very small.  Lost protocol packets due to
   unreliable links are not countered with redundancy, but are detected
   and utilized for better routing decisions.  B.A.T.M.A.N. chooses the
   most reliable route upon the next-hop routing decision of individual
   nodes.  This approach has shown in practise that it is reliable and
   loop-free.

   Comments are solicited and should be addressed to the B.A.T.M.A.N.
   mailing list at b.a.t.m.a.n@open-mesh.net and/or the authors.





Neumann, et al.          Expires October 9, 2008                [Page 3]

Internet-Draft              Abbreviated Title                   Apr 2008


1.1.  Terminology

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

   Node - A mesh router which utilizes the B.A.T.M.A.N. protocol as
   specified in this document on at least one network interface.

   Link - wired or wireless communication link, which can be
   unidirectional or bidirectional

   Direct Link - single-hop communication link between two particular
   B.A.T.M.A.N. interfaces

   Bidirectional Link - direct link with bidirectional (symmetric)
   communication capability

   Unidirectional Link - direct link with only unidirectional
   (asymmetric) communication capability

   Bidirectional Neighbor - single-hop neighbor, available via a direct
   bidirectional link

   Best Link - the most promising outgoing interface and next hop
   towards a given originator

   B.A.T.M.A.N. Interface - Network interface utilized by B.A.T.M.A.N.
   This is also a synonym for an Originator.

   Host Network Announcement (HNA) - Message type, used to announce a
   gateway to a network or host

   Originator Message (OGM) - B.A.T.M.A.N. protocol message advertising
   the existence of an Originator.  OGMs are used for link quality and
   path detection.

   Originator - Synonym for a B.A.T.M.A.N. Network Interface, announced
   by B.A.T.M.A.N. Originator Messages.

1.2.  Protocol Overview

   B.A.T.M.A.N. detects the presence of B.A.T.M.A.N.-Originators, no
   matter whether the communication path to/from an Originator is a
   single-hop or multi-hop communication link.  The protocol does not
   try to find out the full routing path, instead it only learns which
   link-local neighbor is the best gateway to each Originator.  It also
   keeps track of new Originators and informs its neighbors about their



Neumann, et al.          Expires October 9, 2008                [Page 4]

Internet-Draft              Abbreviated Title                   Apr 2008


   existence.  The protocol ensures that a route consists of
   bidirectional links only.

   On a regular basis every node broadcasts an originator message (or
   OGM), thereby informing its link-local neighbors about its existence
   (first step).  Link-local neighbors which are receiving the
   Originator messages are relaying them by rebroadcasting it, according
   to specific B.A.T.M.A.N. forwarding rules.  The B.A.T.M.A.N. mesh
   network is therefore flooded with Originator messages.  This flooding
   process will be performed by single-hop neighbors in the second step,
   by two-hop neighbors in the third step, and so forth.  OGMs are send
   and repeated as UDP broadcasts, therefore OGMs are flooded until
   every node has received it at least once, or until they got lost due
   to packet loss of communication links, or until their TTL (time to
   live) value has expired.  In practise OGM packet loss caused by
   interference, collision or congestion is significant.  The number of
   OGMs received from a given Originator via each link-local neighbor is
   used to estimate the quality of a (single-hop or multi-hop) route.
   In order to be able to find the best route to a certain Originator,
   B.A.T.M.A.N counts the originator-messages received and logs which
   link-local neighbor relayed the message.  Using this information
   B.A.T.M.A.N. maintains a table with the best link-local router
   towards every Originator on the network.  By using a sequence number,
   embedded in each OGM, B.A.T.M.A.N. can distinguish between new
   Originator message packets and duplicates ensuring that every OGM
   gets only counted once.

   B.A.T.M.A.N. was not designed to operate on stable and reliable
   media, such as cable networks, but rather to function on unreliable
   media inherently experiencing high levels of instability and data
   loss.  The protocol was devised to counteract the side effects of a
   network's fluctuation and compensate its instability, thus allowing
   for a high level of robustness.  It also embodies the idea of
   collective intelligence opposed to link state routing.  The
   topographical information is not handled by a single node, but spread
   across the whole network.  No central entity knows all possible ways
   through the network.  Every node only determines the data to choose
   the next hop, making the protocol very lightweight and quickly
   adapting to fluctuating network topologies.

   B.A.T.M.A.N. Originators can announce themselves as gateways to the
   internet.  Their announcement includes a gateway-class, which is
   specifying the connection speed of their up- and downlink to the
   internet.  Gateways also send a port-number which is used by gateway
   clients to establish a unidirectional UDP-tunnel to the gateway.  The
   decision which gateway is selected for a destination is performed by
   the gateway-client.




Neumann, et al.          Expires October 9, 2008                [Page 5]

Internet-Draft              Abbreviated Title                   Apr 2008


   The method of tunneling between a B.A.T.M.A.N. internet gateway
   client and the internet gateway ensures a stable route to the
   internet as long as the protocol can maintain a working communication
   path between both peers.  This is particularly important when the
   internet gateway has to perform Network Address Translation (NAT)
   between nodes using private IP address space in the mesh and public
   IP networks.

   Once the tunnel is established the network topology and routing paths
   between the B.A.T.M.A.N. gateway and the gateway client may change
   but the data will get routed via the initial gateway and back without
   changes, as long as the protocol can provide a working communication
   route.  Thus, B.A.T.M.A.N. is capable to provide stable session-based
   internet-traffic in MANETs with more than one gateway to other
   network segments.  Apart from stable routing the tunneling also
   allows for techniques such as black hole detection to be used in
   B.A.T.M.A.N. networks.


2.  Protocol and Port Number

   Packets in B.A.T.M.A.N. are communicated using UDP.  Port 4305 has
   been assigned by IANA for exclusive usage by the B.A.T.M.A.N.
   protocol.


3.  B.A.T.M.A.N. Packet Formats

3.1.  General B.A.T.M.A.N. Packet Format

   The general layout of a B.A.T.M.A.N. packet (without the trailing IP
   and UDP header).



















Neumann, et al.          Expires October 9, 2008                [Page 6]

Internet-Draft              Abbreviated Title                   Apr 2008


                    General B.A.T.M.A.N. packet format.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   +                                                               +
   |                   Originator Message (OGM)                    |
   +                                                               +
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :                      Optional HNA Messages                    :
   :               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   :               |                                               :
   +-+-+-+-+-+-+-+-+                                               :
   :                             (etc.)                            :

                                 Figure 1

   Each B.A.T.M.A.N. packet is encapsulated in a single UDP data packet.

   A B.A.T.M.A.N. packet consists of one originator message (OGM) and
   zero or more attached HNA extension messages.

   Originator Message (OGM):

             OGMs have a fixed size of 12 octets.  They are further
             described in Section Section 3.2.

   Optional HNA Extension Messages:

             An OGM may be followed by zero or more HNA extension
             messages.  Each extension message following a preceding OGM
             is associated with the preceding OGM and MUST be processed
             respectively.

             HNA messages have a fixed size of 5 octets.  It is
             described in Section Section 3.3.













Neumann, et al.          Expires October 9, 2008                [Page 7]

Internet-Draft              Abbreviated Title                   Apr 2008


3.2.  Originator Message (OGM) Format

                     Originator Message (OGM) format.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    Version    |U|D|           |      TTL      |    GWFlags    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |        Sequence Number        |             GW Port           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                      Originator Address                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                                 Figure 2

3.2.1.  Originator Message (OGM) Fields

   Version:

             MUST be set to VERSION.  Each packet received with a
             version field different from VERSION MUST be ignored.

   Is-direct-link flag:

             This flag indicates whether a Node is a direct neighbor or
             not.

   Unidirectional flag:

             This flag indicates whether the neighboring node is
             bidirectional or not.

   TTL (Time To Live):

             The TTL can be used to define an upper limit on the number
             of hops an OGM can be transmitted

   Gateway flags (GWFlags):

             MUST be set according to description in Section 7.1.

   Sequence Number:

             The originator of an OGM consecutively numbers each new OGM
             with an incremented (by one) sequence number.  To get an
             overview about the Sequence Number handling see
             Section 4.2.



Neumann, et al.          Expires October 9, 2008                [Page 8]

Internet-Draft              Abbreviated Title                   Apr 2008


   Originator Address:

             The IPv4 address of the B.A.T.M.A.N. interface on which
             behalf the OGM has been generated.

3.3.  HNA Message Format

                       HNA-extension-message format.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Network Address                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    Netmask    |
   +-+-+-+-+-+-+-+-+

                                 Figure 3

3.3.1.  HNA Message Fields

   Netmask:

             The number of bits presenting the size of the announced
             network.

   Network Address:

             The IPv4 network address of the announced network.


4.  Conceptual Data Structures

   Each node must maintain certain information about its own and other
   B.A.T.M.A.N. originators in the network and how these originators are
   related to neighboring nodes and to the B.A.T.M.A.N. interfaces of
   the node itself.  This Section conceptionally describes the
   information necessary to conform to the protocol described in this
   document.

4.1.  Originator List

   Each node maintains information about the known other originators
   (B.A.T.M.A.N. Interfaces) in the network in an Originator List.  The
   Originator List contains one entry for each Originator from which or
   via which an OGM has been received within the last PURGE_TIMEOUT
   seconds.  If OGMs from different Originators (B.A.T.M.A.N.
   interfaces) of the same node are received then there MUST be one



Neumann, et al.          Expires October 9, 2008                [Page 9]

Internet-Draft              Abbreviated Title                   Apr 2008


   entry for each Originator.  In fact, the receiving node does not
   necessarily know that certain different Originators (and
   corresponding IP addresses) are belonging to the same B.A.T.M.A.N.
   node.

   For each Originator the following Information must be maintained:

   o  Originator IPv4 Address:

           The IPv4 address of the Originator (B.A.T.M.A.N. Interface)
           as given in the corresponding field of the received OGM.

   o  Last Aware time:

           A timestamp which MUST be updated with every OGM that has
           been received from or via the given Originator.

   o  Bidirect Link(s) Sequence Number:

           The bidirectional Link Check requires a Node to save the
           information which direct neighbor successfully rebroadcasted
           its own OGM.  Therefore, the Sequence Number of the last
           accepted self-initiated OGM received from a direct link
           neighbor is to be saved here on a per Interface basis.  This
           is described in Section 5.3.

   o  Current Sequence Number:

           The newest OGM Sequence Number that has been accepted from
           the given Originator.  This is described in Section 4.2.

   o  HNA List:

           All announced Networks of the Originator with their IP-Range
           and Netmask.

   o  Gateway capabilities:

           If the Originator offers a Gateway, and its announced
           parameters.

   o  Neighbor information List:

           for each Direct Link to each Neighbor of the node the
           following information must be maintained:

           +  Sliding Window:




Neumann, et al.          Expires October 9, 2008               [Page 10]

Internet-Draft              Abbreviated Title                   Apr 2008


                   For each In-Window Sequence Number it is remarked if
                   an OGM with this Sequence Number has been received.
                   This is described in Section 4.2.

           +  Packet Count:

                   The amount of Sequence Numbers recorded in the
                   Sliding Window.  It is used as a metric for the path
                   to the Originator via this neighbor.

           +  Last Valid Time:

                   The timestamp when the last valid OGM was received
                   via this neighbor.

           +  Last TTL:

                   The TTL of the last OGM which was received via this
                   neighbor.

4.2.  Sequence Numbers, Ranges, and Windows

   B.A.T.M.A.N. is Sequence Number oriented.  In fact, the Sequence
   Number of a received OGM is the key information that is transmitted
   with each OGM.

   Sequence Numbers are recorded in dedicated sliding windows until they
   are considered Out-Of Range.  Thus, such a sliding window always
   contains the set of recently received Sequence Numbers.  The amount
   of Sequence Numbers recorded in the Sliding Window is used as a
   metric for the quality of detected links and paths.

   The Sequence Number range is not an infinite space but is limited to
   the range of 0 .. 2^16 - 1.  Since the space is limited, all
   arithmetical operations must be performed modulo 2^16.  With this,
   sequence numbers cycle from 0 to 2^16-1 and start from 0 again when
   reaching the maximum value.  Therefore, special care must be taken
   with comparisons.  For example, the 7 Sequence Numbers below 5 modulo
   2^16 are 4,3,2,1,0,65535 and 65534.












Neumann, et al.          Expires October 9, 2008               [Page 11]

Internet-Draft              Abbreviated Title                   Apr 2008


     Conceptional illustration of In-Window and Out-Of-Range Sequence
   Numbers for a WINDOW_SIZE of 8 (The proposed WINDOW_SIZE constant is
                           defined in Section 8)

                          n=Current Sequence Number
  <...- - - - - - - - - - + + + + + + + + + + + + + + + + + + + + + +..>
      1                   0                   1                   2
      0 9 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  <--+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+->
           |<------------>|
           | WINDOW_SIZE  |
           |              |
  <------->|<------------>|<----------------------------------------->
  Out-Of-  | In-Window    |                Out-Of Range
   Range   |              |

                                 Figure 4

   In-Window Sequence Numbers:

             The In-Window Sequence Numbers represent the latest
             sequence numbers.  They include the Current Sequence Number
             from this Originator and the WINDOW_SIZE - 1 Sequence
             Numbers below it.

             The Current Sequence Number of each Originator MUST be
             maintained, as well as information if an OGM has been
             received or not for each In-Window Sequence Number.

             If an OGM from this Originator with a In-Window Sequence
             Number is received, the Current Sequence Number will NOT be
             updated, and therefore the Sliding Window is not moved.  It
             must be memorized that an OGM with Sequence Number has been
             received.

   Out-Of-Range Sequence Numbers:

             Out-Of-Range Sequence Numbers are all Sequence Numbers
             which are not in the In-Window range.  They are considered
             new or next-expected Sequence Numbers.

             If an OGM from this Originator with an Out-Of-Range
             Sequence Number is received, the Current Sequence Number is
             set to this new Sequence Number.  This means that the
             Sliding Window is moved, and Sequence Numbers which are not
             in the In-Window Range anymore drop out of the Window.
             Information if OGMs have been received or not with Sequence
             Numbers which dropped out of the Window MUST be purged.



Neumann, et al.          Expires October 9, 2008               [Page 12]

Internet-Draft              Abbreviated Title                   Apr 2008


5.  Flooding Mechanism

   The flooding mechanism can be divided into several parts:

   o  How to generate and broadcast OGMs is described in Section 5.1.

   o  The reception and evaluation of OGMs is described in Section 5.2.

   o  The update and usage of the Bidirectional Link Check is explained
      in Section 5.3.

   o  The Neighbor Ranking and Best Link detection is described in
      Section 5.4.

   o  The rebroadcast mechanism is described in Section 5.5.

5.1.  Broadcasting own Originator Messages (OGMs)

   Each node MUST periodically generate and broadcast OGMs for each
   B.A.T.M.A.N. Interface.  The Message(s) MUST be broadcasted every
   ORIGINATOR_INTERVAL via all B.A.T.M.A.N. Interfaces.  A jitter may be
   applied to avoid collisions.  The OGM MUST be initialized as follows:

   o  Version: Set your internal compatibility version.

   o  Flags: Set the Is-direct-link and Unidirectional flag to zero.

   o  TTL: Set the TTL to the desired value in the range of TTL_MIN and
      TTL_MAX.

   o  Sequence number: On first broadcast set the sequence number to an
      arbitrary value and increment the field by one for each following
      broadcast.

   o  GWFlags: If this host offers an internet connection set the field
      as described in Section 7.1 otherwise set it to zero.

   o  GWPort: If this host offers an internet connection set the field
      to your desired tunneling port otherwise set it to zero.

   o  Originator Address: Set this field to the IP address of this
      B.A.T.M.A.N. Interface.

   If this Node wants to announce access to non-B.A.T.M.A.N. networks
   via HNA it SHOULD append an HNA Extension Messages for every network
   to be announced.  See Section 3.3 for a detailed description of that
   message type.




Neumann, et al.          Expires October 9, 2008               [Page 13]

Internet-Draft              Abbreviated Title                   Apr 2008


5.2.  Receiving Originator Messages

   Upon receiving a general B.A.T.M.A.N. packet a Node MUST perform the
   following preliminary checks before the packet is further processed:

   1.  If the OGM contains a version which is different to the own
       internal version the message MUST be silently dropped (thus, it
       MUST NOT be further processed or broadcasted).

   2.  If the sender address of the OGM belongs to one of the
       B.A.T.M.A.N. interfaces the message MUST be silently dropped as
       this OGM originated from this Node.

   3.  If the sender address of the OGM is a broadcast address of an own
       B.A.T.M.A.N. interface the message MUST be silently dropped.

   4.  If the Originator Address of the OGM is identical with any of the
       Nodes' own B.A.T.M.A.N. Interfaces then the OGM has been
       originated by the Node itself.  The processing of the OGM MUST
       continue as described in Section 5.3 and afterwards silently
       dropped.

   5.  If the unidirectional flag of the OGM is set the message MUST be
       silently dropped.

   6.  If the OGM has been received via a Bidirectional link AND
       contains a New Sequence Number (is NOT a duplicate) then the OGM
       MUST be processed as described in Section 5.4.

   7.  The OGM has to be rebroadcasted as described in Section 5.5 if:

       *  the OGM has been received from a single hop neighbor (sender
          address equals Originator Address)

       *  the OGM was received via a Bidirectional link AND via the Best
          Link AND is either not a duplicate or has the same TTL as the
          last packet which was not a duplicate (last TTL)

5.3.  Bidirectional Link Check

   A Bidirectional Link check is used to verify that a detected link to
   a given neighbor can be used in both directions.

   Therefore the Sequence Number of each self-originated OGM (re-
   broadcasted by a direct link neighbor) for each Interface must be
   recorded (Bidirect Link Sequence Number) if:





Neumann, et al.          Expires October 9, 2008               [Page 14]

Internet-Draft              Abbreviated Title                   Apr 2008


   o  the self-originated OGM has been received via the Interface for
      which the OGM has been generated

   o  the direct-link-flag is set

   o  the Sequence Number matches the Sequence Number send with the last
      OGM broadcasted for that Interface

   The bidirectional link check succeeds if the last originated Sequence
   number does not differ more than BI_LINK_TIMEOUT from the recorded
   Sequence number.

5.4.  Neighbor Ranking

   Upon reception of an OGM from another node the following must be
   performed:

   o  The Packet Count MUST be updated.

   o  If the OGMs Sequence Number is newer than the Current Sequence
      Number:

      *  The new Current Sequence Number MUST be set to the Sequence
         Number contained in the received OGM.

      *  The Last TTL of this neighbor MUST be updated.

      *  The Sliding Windows of all known links to the Originator of the
         OGM must be updated (purged) to reflect the new upper and lower
         boundaries of the Ranking Range.  The Sequence Number of the
         received OGM must be added to the Sliding Window representing
         the link via which the OGM has been received.

   o  If the Sliding Window of the link via which the OGM has been
      received contains the most (In-Ranking-Range) Sequence Numbers
      then this link is said to be the new Best Link to the Originator
      of the OGM.  Otherwise the previously considered Best Link MUST
      NOT change.

5.5.  Re-broadcasting other nodes' OGMs

   When an OGM is to be re-broadcasted some of the message fields MUST
   be changed others MUST be left unchanged.  All fields not mentioned
   in the following section remain untouched:

   o  The TTL must be decremented by one.  If the TTL becomes zero
      (after the decrementation) the packet MUST be dropped.




Neumann, et al.          Expires October 9, 2008               [Page 15]

Internet-Draft              Abbreviated Title                   Apr 2008


   o  The Is-direct-link MUST be set if the OGM has been received from a
      Direct Link Neighbor AND if it is re-broadcasted via the link via
      which it has been received.

   o  The Unidirectional flag must be set if an OGM is to be re-
      broadcasted that has been received via an unidirectional link.


6.  Routing

   In order to maintain the routing table of a B.A.T.M.A.N. node, the
   routing daemon keeps track of incoming new OGMs and maintains a list
   of all Originators which have sent Originator messages as shown in
   section Section 4.

   B.A.T.M.A.N. maintains one dedicated routing entry for each known
   Originator and HNA announcement.  Each routing entry defines the
   outgoing B.A.T.M.A.N. interface and the IP address of the next-hop
   direct-link neighbor towards the corresponding Originator.
   B.A.T.M.A.N. must add a host route to all Originators, even if they
   are link-local bidirectional single-hop neighbors.

6.1.  Route Selection and Establishing

   If a OGM from an unknown Originator or to an unknown network/host via
   HNA is received, it will be added to the routing table, and the best
   ranking link-local bidirectional neighbor is selected as gateway to
   the destination.  If the destination is a host, a host route will be
   added via the best ranking bidirectional single-hop neighbor for the
   destination.  If the destination is a network, announced by HNA
   information included in a OGM message, a network route is added via
   the best ranking bidirectional single-hop neighbor.  A bidirectional
   single-hop neighbor may or may not be selected as gateway to itself.
   In case a single-hop Originator is not the best gateway to itself, an
   host route via another bidirectional single-hop neighbor MUST be
   chosen.

   If the best ranking neighbor to the destination changes, the routing
   table must be updated.

   The gateway of each host route to an Originator must be in sync with
   the Best Link identified for the Originator, as described in Section
   Section 5.4.  The gateway of each HNA related host or network route
   must be in sync with the host route of the Originator that ownes the
   corresponding HNA message.






Neumann, et al.          Expires October 9, 2008               [Page 16]

Internet-Draft              Abbreviated Title                   Apr 2008


6.2.  Route Deletion

   In case a node does not receive a single OGM or HNA from a known
   Originator for a time longer than the sliding WINDOW_SIZE and the
   PURGE_TIMEOUT interval, the route is considered to be expired and
   will be removed from the routing table.

6.3.  Opportunistic Routing Deletion Policy

   B.A.T.M.A.N. should behave opportunistic when deleting routes: The
   suggested purging intervals for routes should be long, compared to
   the sliding window size (Recommended value: PURGE_TIMEOUT = 10 x
   WINDOW_SIZE x ORIGINATOR_INTERVAL).

6.3.1.  Opportunistic Routing Deletion Policy Consideration

   A routing entry to a destination that is no longer working, is a
   minor problem in terms of managing network traffic efficiently.  The
   only disadvantage is, that a node may utilize the network trying to
   send information to an unreachable destination for a while, before
   giving up.  On the other hand, having no routing entry to a
   destination that would otherwise be accessible, is problematic in
   terms of routing functionality.  To avoid an overflow of routing
   information, the routing table is purged from expired entrys
   according to the PURGE_TIMEOUT interval.  However, as soon as new
   OGMs from a destination are received, the routing entry is updated if
   a change in the network topology has occurred.


7.  Gateway

7.1.  Gateway Announcement

   A B.A.T.M.A.N. node with access to the internet and routing
   capabilities MAY act as a internet Gateway.  The Gateway is announced
   with the GWFlags transmitted within the B.A.T.M.A.N.-OGM packets.  If
   the node does not provide access to the internet, it MUST set GWFlags
   to 0.  Otherwise, the GWFlags contains the provided bandwidth encoded
   as described below.  The providing node SHOULD set this value to the
   best approximate estimate of available bandwidth.











Neumann, et al.          Expires October 9, 2008               [Page 17]

Internet-Draft              Abbreviated Title                   Apr 2008


                            The GWFlags fields.

    0
    0 1 2 3 4 5 6 7
   +-+-+-+-+-+-+-+-+
   |S| down  | up  |
   +-+-+-+-+-+-+-+-+

                                 Figure 5

   The GWFlags encodes the approximate available bandwidth in kbit per
   second.  The downstream and upstream bandwidth is calculated based on
   the fields, which are interpreted as binary numbers:

        downstream bandwidth = 32 * (S + 2) * 2^down kbit/s

        upstream bandwidth = ((up +1) * (downstream bandwidth)) / 8
        kbit/s

   (annotation: 2^x means 2 raised to the power of x)

7.2.  Gateway Selection

   The B.A.T.M.A.N.-nodes can determine the gateway in several ways.
   The individual node on the network can either choose to decide upon
   the gateway to be used according to the download speed and connection
   quality or only according to the connection speed with the gateway
   itself or as a suitable solution for mobile nodes only by checking
   for the gateway with the best download speed, but this inherits a
   frequent change in the gateway used.

   It is suggested that the B.A.T.M.A.N.-nodes should, in order to
   guarantee functionality, be able to determine and decide upon their
   internet-gateways in multiple ways.  It would seem useful that the
   individual user could, for example, be able to choose any given
   combination of the download speed and the connection strength to the
   internet-gateway i.e. only looking at a combination of the conditions
   noted or decide to disregard one.  This might be important for mobile
   nodes for example as it could be their priority to have a good
   connection to their gateway rather than having the focus on their
   internet-connection's speed.  On the other hand would this allow for
   static users to accept a worse connection to the gateway itself to
   have a faster connection to the internet.  And in some cases it might
   prove useful to combine both methods although a dynamically chosen
   internet-gateway always brings with it the possibility of all
   connections being reset due to switching from one gateway to another.
   Hence it is strongly suggested that the routing-protocol should
   include the possibility for the user to set his gateway statically



Neumann, et al.          Expires October 9, 2008               [Page 18]

Internet-Draft              Abbreviated Title                   Apr 2008


   and not having the protocol deciding upon the best route to the
   internet but using this as a fallback method should the gateway
   configured by the user not be reachable.

7.3.  Gateway Tunneling/Encapsulation

   A GW-client node tunnels all data to the internet (all IP packets
   with a destination address that does only match the default route)
   via a selected GW node.  No encapsulation is used for packets from
   the internet to the GW-client nodes.  The GW-client node encapsulates
   the internet data into a IP/UDP datagram and forwards the
   encapsulated data to the selected GW node.  The GW node identifies
   the encapsulated packets based on the port number of the outer UDP
   header.  It decapsulates the original packet and forwards it to its'
   original destination.  This procedure is completely stateless.

   For encapsulation, a GW-client node MUST set the outer IP header
   source and destination address to the Originator Address of the GW-
   Client node and the GW node.  The outer UDP source and destination
   MUST be set to the GW Port number given by the OGM of the GW node.
   The inner IP header and all following data represents the original IP
   packet.  All data of the inner IP packet MUST be left unchanged.  If
   the size of the original IP packet does not fit into the payload
   section of the outer UDP datagram the packet must be dropped.  If
   virtual interfaces are used to integrate an implementation of the
   B.A.T.M.A.N protocol into a network environment then the maximum
   transfer unit (MTU) of the virtual interface should reflect the
   maximum payload size of the inner UDP datagram.

7.4.  Gateway hopping (testing/accepting)

   test the gateway (is it connected to the internet?) choose a better
   gateway if its not available.


8.  Proposed Values for Constants

   VERSION = 4

   TTL_MIN = 2

   TTL_MAX = 255

   SEQNO_MAX = 65535

   BROADCAST_DELAY_MAX (Milliseconds) = 100

   ORIGINATOR_INTERVAL (Milliseconds) = 1000



Neumann, et al.          Expires October 9, 2008               [Page 19]

Internet-Draft              Abbreviated Title                   Apr 2008


   ORIGINATOR_INTERVAL_JITTER (Milliseconds)= 200

   WINDOW_SIZE = 128

   PURGE_TIMEOUT = 10 x WINDOW_SIZE x ORIGINATOR_INTERVAL


9.  IANA Considerations

   This memo includes no request to IANA.

   All drafts are required to have an IANA considerations section (see
   the update of RFC 2434 [I-D.narten-iana-considerations-rfc2434bis]
   for a guide).  If the draft does not require IANA to do anything, the
   section contains an explicit statement that this is the case (as
   above).  If there are no requirements for IANA, the section will be
   removed during conversion into an RFC by the RFC Editor.


10.  Security Considerations

   Routing protocols have to rely on information from other nodes in the
   network.  Therefore they are susceptible to various attacks and
   B.A.T.M.A.N. being one of these protocols has to bear with them.  The
   B.A.T.M.A.N. protocol can be enhanced by the use of common encryption
   and authentication technologies to insure that routing information is
   only accepted from trusted nodes.  To increase the level of security,
   all information on the wireless layer itself may also be encrypted.
   However, these approaches do not solve the challenges of a mesh
   network consisting of non-authenticated, non-trusted peers and are
   not in the scope of this document.  In case there is no closed
   trusted group of peers, the routing algorithm itself has to be robust
   against false protocol informations.  B.A.T.M.A.N.'s protocol design
   inherently limits the impact of different attack vectors.

10.1.  Confidentiality

   A B.A.T.M.A.N. Node knows of the existence of all other nodes in the
   network which are in the range of multi-hop communication links, but
   due to its design it does not know the whole topology of the network.
   A Nodes' topology view is limited to a one hop horizon.  B.A.T.M.A.N.
   accepts packets from arbitrary sources and builds its routing table
   by analyzing the statistics of received Originator Messages.

10.2.  Overflow of routing entries

   A malicious host could send Originator Messages that are announcing
   the existence of non-existing nodes to cause an overflow of routing



Neumann, et al.          Expires October 9, 2008               [Page 20]

Internet-Draft              Abbreviated Title                   Apr 2008


   entrys or excessive cpu load and memory consumption.  This attack can
   be intercepted by sanity checks.  If the number of routing entries
   goes through the roof, Originators with very low Originator Message
   count must be removed.

10.3.  Route manipulation

   An attacker can also generate OGMs from an existing Originator with
   continuing valid Sequence Numbers that he actually didn't receive -
   in order to manipulate other hosts routing, and redirect the route to
   the destination to itself.  Since routing decisions are based on
   statistical analysis of the number of incoming Originator Messages,
   rather than on information contained in packets, the attacker has to
   generate many falsified protocol messages.  Like valid protocol
   messages, phony messages created by the attacker are subject to
   packet loss.  If an attacker wants to make sure that a route via his
   controlled host will be chosen, he has to win the ranking towards the
   destination continuously.  This limits the range of successful
   attacks to areas where the attacker can deliver enough false messages
   to override valid messages.

   If the Sequence numbers sent by the attacker differ more than the
   sliding window size, the victims will assume that the other host has
   restarted and will purge the ranking.  The attacker can constantly
   generate OGMs with Sequence numbers that induce all receiving nodes
   to purge the ranking every time they receive a phony OGM.  But every
   time a valid OGM is received by the victims, his phony routing
   information will be purged again.  This limits the range and duration
   of a successful attack.

   The attacker may send phony OGMs for an existing Originator, that are
   a few counts ahead of the real Sequence Number.  This way the packets
   from the attacker will be preferred in the ranking, and will not
   induce the victims to purge the ranking.  However if the number of
   phony OGMs delivered to the victim is too low to win the ranking, the
   attack will have no effect.  Again, the range of an attack is
   limited.


11.  References

11.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, Current Status BEST
              CURRENT PRACTICE, March 1997.





Neumann, et al.          Expires October 9, 2008               [Page 21]

Internet-Draft              Abbreviated Title                   Apr 2008


11.2.  Informative References

   [I-D.narten-iana-considerations-rfc2434bis]
              Narten, T. and H. Alvestrand, "Guidelines for Writing an
              IANA Considerations Section in RFCs",
              draft-narten-iana-considerations-rfc2434bis-09 (work in
              progress), March 2008.

   [RFC3552]  Rescorla, E. and B. Korver, "Guidelines for Writing RFC
              Text on Security Considerations", BCP 72, RFC 3552,
              July 2003.


Appendix A.  Contributors

   This specification is the result of the joint efforts of the
   following contributors -- listed alphabetically.

   Andreas Langer

   Axel Neumann

   Corinna (Elektra) Aichele

   Felix Fietkau

   Ludger Schmudde

   Marek Lindner

   Simon Wunderlich

   Thomas Lopatic


Authors' Addresses

   Axel Neumann

   Email: axel@open-mesh.net


   Corinna (Elektra) Aichele

   Email: elektra@open-mesh.net






Neumann, et al.          Expires October 9, 2008               [Page 22]

Internet-Draft              Abbreviated Title                   Apr 2008


   Marek Lindner

   Email: lindner_marek@yahoo.de


   Simon Wunderlich

   Email: siwu@hrz.tu-chemnitz.de











































Neumann, et al.          Expires October 9, 2008               [Page 23]

Internet-Draft              Abbreviated Title                   Apr 2008


Full Copyright Statement

   Copyright (C) The IETF Trust (2008).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.


Acknowledgment

   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).





Neumann, et al.          Expires October 9, 2008               [Page 24]