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]