MANET Pr. Mase Internet-Draft C. Adjih Expires: November 27, 2005 Information and Communication Network Lab., Niigata University May 26, 2005 No Overhead Autoconfiguration OLSR draft-mase-manet-autoconf-noaolsr-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 November 27, 2005. Copyright Notice Copyright (C) The Internet Society (2005). Abstract This document specifies one method for autoconfiguration for the Optimized Link State Routing (OLSR) protocol for ad hoc networks. OLSR is a routing protocol for mobile ad hoc networks, designed for use in multi-hop wireless ad hoc networks ; and as such it specifies how individual nodes can construct routes to each other. To achieve this, it relies on preliminary assignment of unique IP addresses to OLSR interfaces ; hence the task of assigning addresses to Mase & Adjih Expires November 27, 2005 [Page 1] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 interfaces, and checking their uniqueness is defined externally. This document proposes a complementary method, called "No Overhead Autoconfiguration for OLSR" (NOA-OLSR), to perform this task of ensuring uniqueness (Duplicate Address Detection, DAD) of addresses which have been selected. This method consists of modifications in the OLSR specification. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Autoconfiguration Method Overview . . . . . . . . . . . . . . 6 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 9 4. Autoconfiguration Algorithms . . . . . . . . . . . . . . . . . 11 4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Address Selection . . . . . . . . . . . . . . . . . . . . 11 4.3 Duplicate Address Detection . . . . . . . . . . . . . . . 11 4.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . 11 4.3.2 Notation . . . . . . . . . . . . . . . . . . . . . . . 12 4.3.3 Neighbor Duplicate Address Detection . . . . . . . . . 13 4.3.3.1 Rule R1 . . . . . . . . . . . . . . . . . . . . . 13 4.3.4 Two-hop duplicate address detection . . . . . . . . . 14 4.3.4.1 Rule R2 . . . . . . . . . . . . . . . . . . . . . 14 4.3.4.2 Rule R3 . . . . . . . . . . . . . . . . . . . . . 14 4.3.5 Multihop duplicate address detection . . . . . . . . . 15 4.3.5.1 Multihop DAD with two TC generators . . . . . . . 16 4.3.5.2 Multihop DAD with two non-generators . . . . . . . 17 4.3.5.3 Multihop DAD with one TC Generator and one Non-Generator . . . . . . . . . . . . . . . . . . 21 4.3.5.4 Three-hop DAD, Specific Case . . . . . . . . . . . 24 4.4 Sequence Number Consistency . . . . . . . . . . . . . . . 25 4.4.1 Minimum Wrap-Around Limit . . . . . . . . . . . . . . 25 4.4.2 HELLO Sequence Number Consistency . . . . . . . . . . 25 4.4.3 TC Sequence Number Consistency . . . . . . . . . . . . 26 4.5 Autoconfiguration State . . . . . . . . . . . . . . . . . 27 4.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . 27 4.5.2 Functionning . . . . . . . . . . . . . . . . . . . . . 27 4.6 Node Familiarity . . . . . . . . . . . . . . . . . . . . . 29 5. Autoconfiguration Specifications . . . . . . . . . . . . . . . 30 5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2 Information Repository . . . . . . . . . . . . . . . . . . 30 5.2.1 Autoconfiguration State . . . . . . . . . . . . . . . 30 5.2.2 State Information Base . . . . . . . . . . . . . . . . 30 5.2.3 Duplicate Set . . . . . . . . . . . . . . . . . . . . 31 5.2.3.1 Message Content Identifier . . . . . . . . . . . . 31 5.2.4 Set and Unset Fields . . . . . . . . . . . . . . . . . 32 5.3 Address Selection and Address Change . . . . . . . . . . . 32 5.3.1 Address Selection . . . . . . . . . . . . . . . . . . 32 5.3.2 Address Change . . . . . . . . . . . . . . . . . . . . 33 Mase & Adjih Expires November 27, 2005 [Page 2] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 5.4 State Set Update . . . . . . . . . . . . . . . . . . . . . 34 5.4.1 Populating the State Set . . . . . . . . . . . . . . . 34 5.4.2 State Tuple Update . . . . . . . . . . . . . . . . . . 35 5.4.3 Associated State Tuple Retrieval . . . . . . . . . . . 36 5.4.4 State Tuple: HELLO information update . . . . . . . . 36 5.4.5 State Tuple: TC information update . . . . . . . . . . 37 5.4.6 State Tuple: MPR information update . . . . . . . . . 37 5.4.7 Familiarity . . . . . . . . . . . . . . . . . . . . . 37 5.5 Changes in Message Processing . . . . . . . . . . . . . . 38 5.5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . 38 5.5.2 Packet Processing and Message Flooding . . . . . . . . 38 5.5.2.1 Special Retransmission . . . . . . . . . . . . . . 39 5.5.2.2 Special Duplicate Tuple Creation . . . . . . . . . 39 5.5.3 Autoconfiguration Message Pre-Processing . . . . . . . 40 5.5.3.1 Hello Message Pre-Processing . . . . . . . . . . . 40 5.5.3.2 TC Message Pre-Processing . . . . . . . . . . . . 41 5.5.4 Autoconfiguration Message Post-Processing . . . . . . 43 5.6 Changes in OLSR Message Processing . . . . . . . . . . . . 43 5.6.1 Changes in HELLO Message Format . . . . . . . . . . . 43 5.6.2 Changes in HELLO Message Processing . . . . . . . . . 44 5.6.2.1 State Set Update from HELLO . . . . . . . . . . . 46 5.6.3 Changes in HELLO Message Generation . . . . . . . . . 47 5.6.4 Changes in TC Message Format . . . . . . . . . . . . . 48 5.6.5 Changes in TC Message Processing . . . . . . . . . . . 48 5.6.5.1 State Set Update from TC . . . . . . . . . . . . . 49 5.6.5.2 Conflict detection based on TC message content . . 49 5.6.5.3 Dismissed TC messages . . . . . . . . . . . . . . 50 5.6.5.4 Dismissed addresses in TC messages . . . . . . . . 50 5.6.6 Changes in TC Message Generation . . . . . . . . . . . 51 5.6.7 Message Type for HELLO and TC Messages . . . . . . . . 53 5.7 Changes in MPR Computation . . . . . . . . . . . . . . . . 53 5.8 Changes in Routing Table Calculation . . . . . . . . . . . 54 6. Proposed Values for Constants . . . . . . . . . . . . . . . . 55 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 56 8. Limitations and interoperability considerations . . . . . . . 57 8.1 Limitations . . . . . . . . . . . . . . . . . . . . . . . 57 8.2 Interoperability with Standard OLSR . . . . . . . . . . . 58 8.2.1 Considerations for Interoperability with Standard OLSR . . . . . . . . . . . . . . . . . . . . . . . . . 58 8.2.2 Considerations for Isolation from Standard OLSR Nodes . . . . . . . . . . . . . . . . . . . . . . . . 59 9. Requirements notation . . . . . . . . . . . . . . . . . . . . 61 10. Security Considerations . . . . . . . . . . . . . . . . . . 62 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 63 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 64 12.1 Normative References . . . . . . . . . . . . . . . . . . . 64 12.2 Informative References . . . . . . . . . . . . . . . . . . 64 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 65 Mase & Adjih Expires November 27, 2005 [Page 3] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Intellectual Property and Copyright Statements . . . . . . . . 67 Mase & Adjih Expires November 27, 2005 [Page 4] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 1. Introduction A mobile ad hoc network is a collection of nodes, which collaborate to each other without depending on centralized control for enabling wireless communication among nodes. When two nodes are within direct transmission range, they communicate directly (one hop wireless communication) ; and otherwise they communicate using other nodes as intermediary nodes (multihop wireless communication), where the intermediary nodes act as routers for forwarding IP datagrams. Accordingly, routing is a key problem for mobile ad hoc networks and many routing protocols have been proposed. In IETF, in the MANET working group, two proactive routing protocols, OLSR [3] and TBRPF [4], and two reactive routing protocols, AODV [5] and DSR [6] are or will progress to experimental RFC status. However these routing protocols assume that each node has been assigned an unique IP address on each of its network interfaces. IP address autoconfiguration is therefore an important pratical issue and accordingly, many autoconfiguration methods for various types of MANET networks have been proposed. Many conventional methods are organized independently from routing protocols so that they can be used for any MANET regardless of the routing protocols. Some other methods are intended to work jointly with the routing protocols to improve efficiency of IP address autoconfiguration and duplicated address detection. For example, information about IP addresses in use can be collected with support of the routing protocol and can be used in selecting a new free addresses for a node seeking address allocation. Unfortunately, all of these proposed methods are rather expensive as they require significant control message overhead for either avoiding or resolving address conflicts. We propose a novel IP address autoconfiguration method for MANET with proactive routing for OLSR. Our method is an duplicate address detection without overhead based on properties of proactive link state routing protocols. The algorithmic and research related aspect can be find in the joint publication [9]. Mase & Adjih Expires November 27, 2005 [Page 5] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 2. Autoconfiguration Method Overview In this section, an overview of the autoconfiguration method is given, followed by a description of the structure of the document. The autoconfiguration algorithm detailed in this document applies to the OLSR protocol, and changes its operation. The node is assumed to implement the OLSR protocol ([3], thereafter denoted "standard OLSR"), complemented by the modifications specified here (thenceforth, "NOA-OLSR"). The node is also assumed to operate in a OLSR MANET environment in which the limitations and restrictions enumerated in Section 8 are respected. Under these assumptions, an OLSR node running NOA-OLSR will proceed as follows. An address is initially selected for its OLSR interface (manually, or using the autoconfiguration methods suggested in this document). Then, the node runs the OLSR protocol using this address, while at the same time constantly checking that it is not conflicting with the address of another node in the network (using the detection algorithm of this document). Finally, it doesn't run fully OLSR protocol initially, because it might be entering in a network where its address could be already used by another node, and it would possibly break routes of nodes which are already running. Instead, the node goes through several states, in the last of which, only, the node will ultimately run the full OLSR protocol. Similarily, in order to avoid routing table contamination, the other nodes avoid relying on this node initially, and will rely on it for routing and forwarding messages, when it has reached proper states. To sum up, the autoconfiguration of an OLSR node includes in three parts: o Address selection o Ongoing duplicate address detection o Gradual entry in the OLSR network and routing table contamination avoidance Considering the address selection, it is actually a peripherical issue of the protocol described in this document, because it is fairly independent of it. Hence an overview of address selection is provided, along with guidelines, and pointers to relevant references. The ongoing duplicate address detection is the main addition to the OLSR protocol, detailed in section Section 4.3 is , checking for inconsistencies in the routing protocol messages to diagnose duplicate address detection, using variants of the ideas pioneered by Mase & Adjih Expires November 27, 2005 [Page 6] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 [8]: o The first kind of inconsistency is based on information included in OLSR messages (such as HELLO messages and TC messages): many cases of duplicate address in one MANET network result into inconsistent information being received ; topology information, for instance. o The second kind of inconsistency is based on sequence numbers: when two nodes, which selected the same IP address, are present in a network, they would send control messages that will be inconsistent. Finally the protocol introduces a state for each OLSR node, the "autoconfiguration state". As mentioned, it allows one OLSR node with a newly selected address to enter gradually in running OLSR network, by sending messages which will be used by more and more nodes. At the same time, it also prevents routing table calculation contamination by ensuring that routes go through nodes which have been present in the network long enough for the duplicate address detection to have been performed. The description of the autoconfiguration state is given in section Section 4.5. The description of the three parts constitutes the major part of this document. However, they include both algorithm aspects (such as how and why some DAD rule is used), and detailed specifications (such as the information bases used to implement the protocol). The choice was made to divide the document in two parts: first the algorithmic part which describe the ideas used, then the detailed specifications. Including some additional sections, the remaining of this document is organized as follows: o Section 3 collects specific terminology used o Section 4 provides the high-level, algorithmic, part of this document. It includes: * Address selection. * Ongoing duplicate address detection. * Principles behind checking sequence number consistency of messages. * Gradual entry in the OLSR network and routing table contamination avoidance. Mase & Adjih Expires November 27, 2005 [Page 7] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 o Section 5 provides the specification of NOA-OLSR. It includes: * Description of the additions and changes to the information repository of OLSR. * Population of (new) state set. * Constraints of address selection. * Changes in packet processing, in OLSR message processing and OLSR message generation. * Changes in MPR computation and routing table calculation. Mase & Adjih Expires November 27, 2005 [Page 8] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 3. Terminology This section provides definition for terms that have a specific meaning to the protocol specified in this document and that are used throughout the text. Address Conflict: When two nodes in the same MANET network share the same address, the situation is described as an "Address Conflict". The nodes involved are "conflicting nodes" and their shared address is called "conflicting address". Conflicting nodes may each send one message with the same sequence number and same message type: such messages are denoted "conflicting messages". Autoconfiguration State: The current autoconfiguration state of the node, one of HELLO, TOPOLOGY, and NORMAL, which indicates what messages it should (or should not) generate and processing it should (or should not) do (see Section 4.5). Busy Address: An address which is being used by some node in the network (see Section 4.2). Duplicate Address Detection (DAD): Duplicate address detection is the action of detecting address conflict, the situation where some nodes are using the same address in the same MANET network. Duplicate Address Detection Rule (DAD Rule): A duplicate address detection rule is one rule of this document, which used to detect the existence of address conflict (see Section 4.3). Familiar Address (Node): An address is familiar for a node, if the node has seen it in an OLSR message, for a sufficiently long period of time (see Section 4.6 and Section 5.4.7). A node is familiar for another node if it has a familiar address for this other node. An address or a node which is not familiar is said "unfamiliar". Message Content Identifier: A message content identifier is computed internally by the node to differentiate between the content of different messages, independently of the message header (see Section 5.2.3.1). Message Content Identifier Generation Method: The message content identifier generation method, is the method that one node implements to compute a message content identifier from the content of a message (see Section 5.2.3.1). Mase & Adjih Expires November 27, 2005 [Page 9] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 NOA-OLSR: "NOA-OLSR" is the protocol specified by this document. It is the standard OLSR protocol [3] with the additions and changes specified in this document. Routing Table Contamination Avoidance: Routing table contamination avoidance is the idea of preserving the routing table from incorrect information due to address conflict. This is achieved by using the autoconfiguration state (see Section 4.5). Sequence Number Consistency: All OLSR messages have a sequence number. One trademark of duplicate addresses, is sequence numbers of different messages, which could not result from a correct implementation of the OLSR protocol (such as decrease in sequence numbers, etc.). The properties of sequence numbers which would result from the normal OLSR protocol implementation are termed "Sequence number consistency" (see Section 4.4). Standard OLSR: The terms "standard OLSR protocol" refer to the OLSR protocol specified in [3]. The term "standard" is meant to differentiate with the "non-standard" OLSR protocol proposed in this document (thereafter, "NOA-OLSR"). It is not meant to express its normative status within IETF or standardization organizations. TC Generator: A node which generates TC messages (as originator). Mase & Adjih Expires November 27, 2005 [Page 10] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 4. Autoconfiguration Algorithms 4.1 Overview This section provides a high-level view of the method used for autoconfiguration of the node: address selection, duplicate address detection based on rules, principles for sequence number consistency, use of the autoconfiguration state. The detailed specifications of the method are in Section 5. 4.2 Address Selection When a node is present in a MANET, it can monitor the protocol message exchanges and collect information regarding the addresses in use, the "busy address list". It can then selects its own address from the pool of free addresses by avoiding the busy address list. With OLSR, it is possible for each node to obtain busy address information through routing control messages received from other nodes (such information is available as part of the State Set introduced in Section 4.5). This document doesn't specify how the addresses should be selected, apart from the fact any selected address should not be the "busy address list". Some discussions and references about address selection (including IPv4 and IPv6 stateless address autoconfiguration) can be found, for instance, in the document [7]. 4.3 Duplicate Address Detection 4.3.1 Overview Duplicate Address Detection is performed passively, i.e., without additional control messages. Some various passive DAD techniques were proposed in [8], we propose some others. In this section, the detection algorithms are detailed. Protocol specifications are given in a later section. In a MANET network with nodes running the OLSR, several different scenarios of address conflicts may occur. There are classified in three separated cases: Neighbor duplicate address detection: in this case, two neighbor nodes (in range of each other) have selected the same address. Mase & Adjih Expires November 27, 2005 [Page 11] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 Two-hop duplicate address detection: in this case, two nodes which have selected the same address are two-hop neighbors. That is, there is another node in the network which is the neighbor of those both nodes. Multihop duplicate address detection: in this case, the two nodes in conflict are separated by two nodes or more. The three cases of duplicate address are different in that they can be detected by different methods: for instance the multihop duplicate address detection requires the use of TC message information, while the first two cases need not. Also, an additional case is added: it's a specific multihop address conflict case, where the address conflict results in deficiencies in the MPR selection. 4.3.2 Notation In the Section 4.3, the following conventions are used to describe the duplicate address conflict cases for the algorithms: o Capital letters are used to denote different nodes: such as "A", "B", "C", etc... o Numbers are used to represent different addresses, such as "1", "2", "3", etc... o The following notation is employed to represent the node "A" which has the address "1": "A{1}". In the event of an address conflict, two nodes may be using the same address, such as "A{1}" and "B{1}" for instance. o Each DAD rule is associated to a figure which graphically represents the topology. An example is given on Figure 1: one node "A" with address "1". In the figures which will follow, the nodes which should apply the DAD rule, are highlighted by the mark "**", like "A" is, on the sample figure. +--------------+ | ** Node A{1} | +--------------+ Figure 1 Mase & Adjih Expires November 27, 2005 [Page 12] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 4.3.3 Neighbor Duplicate Address Detection In the case of "neighbor duplicate address", two conflicting nodes are neighbors (see Figure 2). This case is special since many different non-OLSR methods could be used to detect the conflict: because the neighbor nodes would receive messages from each other directly, as they would, for instance, if they were connected on a Ethernet network. Thus, most of methods designed for (non-MANET) IP networks, such as IPv4 autoconfiguration detection methods or IPv6 DAD, could be used. Still, due to topology changes such methods could fail, or could not be available in a node. Hence a rule to detect conflicts at the OLSR protocol level in this case is proposed. At mininum, the two OLSR nodes should at least periodically generate HELLO messages, hence the following duplicate address detection rule is used: 4.3.3.1 Rule R1 Rule: R1 (see Figure 2) Context: An HELLO message is received by a node A{1}. Check: Is the address {1}, the address of the originator node ? Action: If it is the case, this node is in conflict and must select a new address. Rationale: A node doesn't receive its own HELLO messages (they are not forwarded), hence the occurence of such an event means that a node with the same address has sent an HELLO. +--------------+ +--------------+ | ** Node A{1} | <---> | ** Node B{1} | +--------------+ +--------------+ Figure 2 As mentioned, this rule can be completed by other duplicate address detection mechanisms, not specified in this document, as they are beyond its scope. The detection R1 can be performed using HELLO messages (in any autoconfiguration state, including HELLO_STATE). Mase & Adjih Expires November 27, 2005 [Page 13] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 4.3.4 Two-hop duplicate address detection In this case, the two conflicting nodes are two-hop neighbors, that is: they are not neighbor, but they have a common neighbor (see Figure 3). The rule proposed here relies on the fact that a common neighbor exists, and will receive the HELLO from both nodes. The detection proceeds in three steps: the common neighbor detects the conflict using those HELLOs, then it advertises the conflict in some message(s) (rule R2), and finally, the conflicting nodes change their address upon receiving this conflict advertisement (rule R3). 4.3.4.1 Rule R2 Rule: R2 (see Figure 3) Context: In node B{2}: an HELLO message from address {1} was received previously, and another HELLO from address {1} is just received by B{2}. Check: Are the sequence numbers of the HELLOs inconsistent (as defined in Section 4.4)? Action: If it is the case, there are two or more neighbors using the same address {1}. B{2} will advertise that the address {1} is conflicting in its HELLO messages. Rationale: If two neighbors of one node have conflicting addresses, the HELLO sequence numbers will be inconsistent. +--------------+ +--------------+ +--------------+ | Node A{1} | <---> | ** Node B{2} | <---> | Node C{1} | +--------------+ +--------------+ +--------------+ Figure 3 4.3.4.2 Rule R3 Rule: R3 (see Figure 4) Context: In node A{1} (and node C{1}): a neighbor B{2} is advertising that conflict exists with the address {1}. Check: - Mase & Adjih Expires November 27, 2005 [Page 14] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 Action: If it is the case, A{1} is a conflicting node and must select a new address. +--------------+ +--------------+ +--------------+ | ** Node A{1} | <---> | Node B{2} | <---> | ** Node C{1} | +--------------+ +--------------+ +--------------+ Figure 4 The detections R2 and R3 can be performed using HELLO messages (in any autoconfiguration state, including HELLO_STATE). 4.3.5 Multihop duplicate address detection In this section, DAD rules are proposed to handle the case where the distance between conflicting nodes is three hops or more. In this case, in general, it cannot be assumed that a single node has enough information to detect the conflict using exclusively the HELLO messages. Hence, the logical choice is here to use information inside TC messages. However the duplicate address detection is complicated by the optimizations of the OLSR routing protocol: first, not all nodes originate TC messages ; second, TC messages might include only a subset of neighbors ; third, OLSR messages may be split and as a consequence, an individual TC message from one node might not include all the topology information that the node should periodically refresh. Finally, the MPR selection algorithm can be affected by duplicate addresses, and prevent proper operation of the MPR flooding mechanism, hence prevent proper propagation of the TCs used by DAD. The DAD rules that are specified in the case of multihop DAD are classified depending on the status of the conflicting nodes with respect to TC generation: a node which generates TC messages (when it is a multipoint relay of some node) is called a TC generator. Three cases are possible and are handled: o Both conflicting nodes are TC generators. o One of the conflicting nodes is a TC generator, and the other is not. o None of the conflicting nodes is TC generator. In each of the three cases, the DAD rules allow detection both on the conflicting nodes (which would then change address) and on intermediary nodes (which would then avoid routing table contamination). Finally some DAD rules are used for preventing the Mase & Adjih Expires November 27, 2005 [Page 15] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 following case: o Conflicting nodes are impeding MPR selection. The following four sections handle individually each case. 4.3.5.1 Multihop DAD with two TC generators In this case, the two nodes in conflict are both TC generators. Then each of them would ultimately receive one TC with its own originator address, but which it did not generate (for it was generated by the other node). The intermediate nodes would also detect conflict by noticing discrepancy in the sequence numbers or discrepancy in the content of the TC messages with same sequence number. The first rule applies to conflicting nodes (R4 (Section 4.3.5.1.1)), the second applies to other nodes in the network (R5 (Section 4.3.5.1.2)). 4.3.5.1.1 Rule R4 Rule: R4 (see Figure 5) Context: In node A{1} (or node C{1}): a TC with originator address {1} has been received. A{1} keeps track of the TC messages that it has sent. Check: Verify whether A has actually sent that TC: the message sequence number should be the same as one message that A has sent in the past, and then the content should be the same. Action: If it is not the case, A{1} is a conflicting node and must select a new address. +--------------+ +--------------+ +--------------+ | ** Node A{1} | <- .. -> | Node B{2} | <- .. -> | ** Node C{1} | | TC generator | | | | TC generator | +--------------+ +--------------+ +--------------+ Figure 5 4.3.5.1.2 Rule R5 Mase & Adjih Expires November 27, 2005 [Page 16] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 Rule: R5 (see Figure 6) Context: In node B{2}: an TC message with originator address {1} was received previously by the node, and another TC with originator address {1} is just received by B{2} Check: Are the sequence numbers of the TC messages consistent (as defined in Section 4.4)? Is the content of the TC identical to the one(s) received before? Action: If it not is the case, there are two or more nodes using the same address {1}: then the TC should be forwarded (if it is has not already been), but the content of the TC will be ignored and not processed Rationale: This detects a conflict between TC generators. If the conflicting nodes are sending TC messages with same sequence number, standard MPR flooding might not allow the TC messages to reach the other node. Hence in case of conflict, the TC should be forwarded by default. Also, because a conflict has been detected, the received TC is guaranted to hold information which is inconsistent with the information already processed because it was issued by a different node ; and hence, the content of TC message should be ignored. +--------------+ +--------------+ +--------------+ | Node A{1} | <- .. -> | ** Node B{2} | <- .. -> | Node C{1} | | TC generator | | | | TC generator | +--------------+ +--------------+ +--------------+ Figure 6 4.3.5.2 Multihop DAD with two non-generators In this section, DAD rules are given for the case where none of the conflicting nodes is a TC generator. In such a configuration, the conflict is detected by means of by using the TC messages of the multi-point relays of the nodes. As one conflicting node selects some MPR, these MPR will send TC messages indicating this selection: when one of the TC messages reaches the other conflicting node, this node will detect inconsistency by discovering that it did not, actually, select the TC originator as MPR. The DAD for intermediate nodes is, however more complex, because they cannot rely on sequence numbers as in previous section Section 4.3.5.1, nor they can rely on knowledge of the actual MPR Mase & Adjih Expires November 27, 2005 [Page 17] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 selection of every node like the nodes in conflict. Hence to detect occurences of such conflicts, another mechanism is used: it is based on the concept of familiar nodes. A node (an IP address) is familiar for another node, when the last one has had knowledge of existence of the first one for sufficiently long (see Section 4.6). The hypothesis made now is that most conflicts occur because of network merges. In such an address conflict, now, let's assume a node from one network is now sending TC messages including the address of one node (in conflict with this network) from another, newly merged, network. For instance, let us consider Figure 7, and let us assume that A{1}, C{2}, and E{4} were previously part of one network, while B{1} and D{3} (one of its MPRs) were part of another. It is reasonable to assume that D{3} will become the neighbor of few nodes of the first network, which it will advertise. Hence, most likely, the TC messages of D{3}, which advertise the conflicting node B{1}, also include mostly addresses of nodes from the merged network, which would be unfamiliar nodes for A{1}. Thence the DAD rule: ignore the information relative to familiar nodes, when it is inside TC messages from unfamiliar nodes, which also include too many unfamiliar nodes. Another rule is added for neighbors of the node A{1}, such as C{2}: because they have knowledge of the neighborhood of A{1}, they are able to directly check if D{3} is a neighbor of A{1}. 4.3.5.2.1 Rule R6 Rule: R6 (see Figure 7) Context: In node A{1}: a TC message with originator address {3} has been received. Check: If this TC includes the address {1} of A, A checks whether it had recently selected {3} as MPR. Action: If it is not the case, A{1} is a conflicting node and must select a new address. Rationale: If A{1} has not selected {3} as MPR, then another node with address {1} must have done so, hence there is an address conflict. Mase & Adjih Expires November 27, 2005 [Page 18] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 +--------------+ +--------------+ | ** Node A{1} | | ** Node B{1} | | (non-MPR) | | (non-MPR) | +--------------+ +--------------+ ^ ^ | | V V +--------------+ +--------------+ +--------------+ | Node C{2} | <- .. -> | Node E{4} | <- .. -> | Node D{3} | | TC generator | | | | TC generator | +--------------+ +--------------+ +--------------+ Figure 7 4.3.5.2.2 Rule R7 Rule: R7 (see Figure 8) Context: In node E{4}: a TC message from originator {2}, which is familiar for E, had been received. It included the familiar (for E) address {1}. Another TC, from originator {3}, an unfamiliar node for E, is including the same familiar address {1}. Check: In this TC, check how many addresses are from familiar nodes. If too little addresses are familiar, then the TC is assumed to include an address {1} which is conflicting. Action: If conflict is assumed, then the information of the TC of {3} about address {1} is ignored (the previous one from {3} will still be used), but all other content is kept. Rationale: This is an heuristic for detecting conflict. Note that in any case, a route to {1} can still be computed using the TC message from {2}. Note also that after some time, {3} and all the nodes advertised by {3} will be familiar to E, ensuring that this rule will no longer apply. Mase & Adjih Expires November 27, 2005 [Page 19] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 +--------------+ +--------------+ | Node A{1} | | Node B{1} | | (non-MPR) | | (non-MPR) | +--------------+ +--------------+ ^ ^ | | V V +--------------+ +--------------+ +--------------+ | Node C{2} | <- .. -> | ** Node E{4} | <- .. -> | Node D{3} | | TC generator | | | | TC generator | +--------------+ +--------------+ +--------------+ Figure 8 4.3.5.2.3 Rule R8 Rule: R8 (see Figure 9) Context: In node C{2}: a HELLO message from node {1} was previously received, and a TC message from node {3} is now received. Check: If the TC message from {3} includes {1} as MPR selector, the HELLO from {1} should also have included {3} as symmetrical neighbor (actually more: as MPR) Action: If this not the case, then a conflict is assumed for address {1}. Then the information of the TC message of {3} about address {1} is ignored (the previous one from {3} will still be used), but all other content is kept. Rationale: This is another heuristic for detecting conflict, for every node which is neighbor of the conflicting nodes. +--------------+ +--------------+ | Node A{1} | | Node B{1} | | (non-MPR) | | (non-MPR) | +--------------+ +--------------+ ^ ^ | | V V +--------------+ +--------------+ +--------------+ | ** Node C{2} | <- .. -> | Node E{4} | <- .. -> | Node D{3} | | A's neighbor | | | | TC generator | +--------------+ +--------------+ +--------------+ Figure 9 Mase & Adjih Expires November 27, 2005 [Page 20] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 4.3.5.3 Multihop DAD with one TC Generator and one Non-Generator In case one of the nodes in conflict is a TC generator while the other one is not, the conflict can be detected by as previously. The TC generator can conduct duplicate address detection by checking the TC messages of the MPR of the other node using DAD rule R6 (Section 4.3.5.2.1). The conflicting node that does not generate TC messages, can detect conflict with DAD rule R4 (Section 4.3.5.1.1). However for intermediary nodes, a new case is possible. We still assume most conflicts occur because of network merges. Then it is possible that for one network, one conflicting node is a TC generator in the other network, while the other one is not. Using the same logic as previously, the TC message of that conflicting node would include many unfamiliar nodes, hence one DAD rule is to reject such TC. 4.3.5.3.1 Rule R9 Rule: R9 (see Figure 10) Context: In node E{4}: a TC from originator familiar node {2} (familiar for E) had been received and it included the (familiar for E) address {1}. Another TC message, from originator {1}, is received. Check: In this TC, check how many addresses are from familiar nodes. If too little addresses are familiar, then the TC is assumed to be from an unfamiliar node from a merged network. Action: If conflict is assumed, then the information of the TC is ignored (the previous one from {2} will still be used). Rationale: This is an heuristic for detecting conflict. Note that in any case, a route to {1} can still be computed using {2} and note that in absence of conflict, anyway, after some time, all the nodes advertised by {1} will be familiar to E, ensuring that this rule will no longer apply. Mase & Adjih Expires November 27, 2005 [Page 21] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 +--------------+ | Node A{1} | | (non-MPR) | +--------------+ ^ | V +--------------+ +--------------+ +--------------+ | Node C{2} | <- .. -> | ** Node E{4} | <- .. -> | Node B{1} | | TC generator | | | | TC generator | +--------------+ +--------------+ +--------------+ Figure 10 Additionally, still in the case of network merge, the nodes that are on the border of the network merge can actually use some heuristics for detecting conflicts. Indeed, if a node, is from another (merging) network, it is likely to have many unfamiliar nodes as neighbors. And those unfamiliar nodes will be present in the Hello messages of the node. Hence when a node detects that one of its neighbors has too many other neighbors that are unfamiliar, it can suspect the neighbor is from another network. In case the node is a TC generator, it will then mark the address of the node as unfamiliar. 4.3.5.3.2 Rule R10 Rule: R10 (see Figure 11) Context: In node C{3}: a TC message is being generated, and it includes neighbor {1}. Check: \myitem{Check:} In the neighborhood of X{1} (which is obtained from the Hello messages, in the two-hop tuple set) check how many addresses are from familiar nodes. If too little addresses are familiar, then the neighbor is assumed to be an node from a merged network. Action: If too little address are familiar, the address {1} is advertised as being "with too many unfamiliar neighbors". Rationale: This is an heuristic to avoid routing table contamination. Note that the address {1} is still advertised and can be used by node A{1} to detect the conflict. Mase & Adjih Expires November 27, 2005 [Page 22] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 +--------------+ | Node X{1} | | | +--------------+ ^ | V +--------------+ +--------------+ +--------------+ | Node A{1} | <- .. -> | Node B{2} | <- .. -> | ** Node C{3} | | | | | | TC generator | +--------------+ +--------------+ +--------------+ Figure 11 The following rule uses the information transmitted by the previous one: 4.3.5.3.3 Rule R11 Rule: R11 (see Figure 12) Context: In node B{2}: a TC message has been received from originator {3} and it includes neighbor {1} marked as ``with too many unfamiliar neighbors'', by rule R10 in node {3}. Check: - Action: The address {1} should be ignored in the processing of the TC message. But the other addresses may still be used, and the TC should still be forwarded.%with std MPR flooding. Rationale: This is an heuristic to avoid routing table contamination, using information from rule R10. +--------------+ | Node X{1} | | | +--------------+ ^ | V +--------------+ +--------------+ +--------------+ | Node A{1} | <- .. -> | ** Node B{2} | <- .. -> | Node C{3} | | | | | | TC generator | +--------------+ +--------------+ +--------------+ Figure 12 Mase & Adjih Expires November 27, 2005 [Page 23] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 4.3.5.4 Three-hop DAD, Specific Case It has been noted that in some cases the MPR selection process can fail because of duplicate addresses (see [8]). As a result, the MPR flooding mechanism may fail to deliver a message to the entire network, and then the previous DAD rules may fail to detect the duplicate address detection. This situation is illustrated on Figure 13. A specific rule can be devised to prevent this situation and allow proper MPR selection: on the figure, the node B{2} is able to detect that there is an inconsistency in the neighborhood advertised by {1} and {3}, which may possibly arise from {1} being a duplicate address. In this case, the MPR selection of B would be deficient: so B can still preventively select {3} as MPR by itself. That way, the messages from A{1} going through B will reach D{1} (triggering one of the previous DAD rules). 4.3.5.4.1 Rule R12 Rule: R12 (see Figure 13) Context: In node B{2}: a HELLO from node {1} had been received, and now an HELLO from node {3} is received. Check: If the HELLO from {3} includes {1} as symmetrical neighbor, the HELLO from {1} should also have included {3} as symmetrical neighbor. Action: If it is not the case, there is an inconsistency and the node B should select {3} as MPR. Rationale: Such inconsistencies should never happen in a static network, unless there is a conflict. Note also that due to topology changes, they may do so even if there is no conflict. In that case, note that the only penalty is an temporary increase of the number of MPR selected. It is still an excellent heuristic that will solve the MPR selection problem when the network is static. Mase & Adjih Expires November 27, 2005 [Page 24] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 +--------------+ +--------------+ | Node A{1} | | Node D{1} | +--------------+ +--------------+ ^ ^ | | V V +--------------+ +--------------+ | ** Node B{2} | <---> | Node C{3} | +--------------+ +--------------+ Figure 13 4.4 Sequence Number Consistency In [8], the use of sequence numbers to verify consistency has been used in some general cases. Here, sequence number consistency is checked for the OLSR protocol, and consist really of two cases: HELLO sequence number consistency, and TC sequence number consistency. 4.4.1 Minimum Wrap-Around Limit In the OLSR protocol [3], it is implicitly assumed that the sequence number of one node will wrap-around within an interval of time greater than DUP_HOLD_TIME. Hence this value is a good reference for the minimum expected interval before a wrap-round the sequence number of any node in the network, denoted MIN_WRAP_AROUND_INTERVAL. 4.4.2 HELLO Sequence Number Consistency In case of HELLO messages, it is assumed that they would be received in the same order as they are transmitted (because they are not forwarded). In this case, a node observing the HELLO messages from a neighbor will see that their sequence numbers are permanently increasing. Now if there are two neighbors B and C of one node A, the node A will receive alternatively messages from B and C, because each is transmitting indefinitly. Hence A must receive a sequence of packets from B, then some packets from C, then some packets from B, and so on. Let's assume that ultimately a sufficiently long sequence is received without packet loss, and which then will be in this order: o one packet B1 from B (possibly the last one of a sequence of packets from B) o some packets from C Mase & Adjih Expires November 27, 2005 [Page 25] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 o one packet B2 from B (possibly the first one of a sequence of packets from B) Now because there was no packet loss, the sequence number of the packet B2 is the sequence number of the packet B1 plus 1. As a result, considering the sequence number of any packet from C: o If it is greater than the sequence number of B1, then: the sequence number of the packet B2 will be less or equal to the sequence number of the packets from C. o Otherwise it is equal to or less than the sequence number of B1. In both events, A observes a decrease or a repetition of the sequence numbers of B. Hence, for HELLO messages, it is sufficient to check if the HELLO received from one address is equal to, or less than, the sequence number of the previous HELLO received from this address. However, because a node may not be constantly a neighbor (and hence, quite naturally, a large number of successive HELLO messages may not be received), this condition should be checked only when there was no wrap-around, hence when the interval between the previous HELLO received and the last HELLO received from the same address is less than MIN_WRAP_AROUND_INTERVAL. 4.4.3 TC Sequence Number Consistency Because TC messages are forwarded with the MPR flooding mechanism, first, the same message may be received several time, secondly, the packet order can be changed, especially with the use of jitter. Hence the algorithm used previously for checking consistency of HELLO messages (Section 4.4.2) can not be used as is. Hence the following principles are used: o The sequence number and the receving time of the last TC message for each originator is recorded. o Each time a TC message is received from a given originator, with a given sequence number, the node checks whether if a TC message with similar identification already was received. If it was, it checks that the previous content is identical to the current content. o If the sequence number difference (in absolute value) between the new TC and previous TC from the same originator is above a given Mase & Adjih Expires November 27, 2005 [Page 26] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 threshold MAX_TC_DIFF_SEQ_NUM, then duplicate address can be suspected. Such an event is possible, for instance if another node sends many non-TC messages or cease to be TC generator for some time ; thus an additional check is performed on the message rate: an approximation of the message rate is computed as the "sequence number difference divided by the reception time difference". If this message rate is greater than a threshold MAX_MESSAGE_RATE, then the TC Sequence Number are deemed inconsistent. If precise adjustement is desired for the values of MAX_TC_DIFF_SEQ_NUM, and MAX_MESSAGE_RATE (peak rate), it can be observed that one of the worst case occurs when two nodes are in conflict, and one is using the same sequence numbers of the other with a delay a little greater than DUP_HOLD_TIME. 4.5 Autoconfiguration State 4.5.1 Introduction Each node has an "autoconfiguration state". This state is an indicator of how long the node has been in the network. The central idea, is that each time a node selects a new address, it should enter the network gradually, running a restrained version of the OLSR protocol. By this way, that the node can detect which addresses are being used, checking for duplicates of its own address, while avoiding to disrupt the routing tables of the other nodes, in the event that its address is actually found to be in conflict. 4.5.2 Functionning There are exactly 3 autoconfiguration states, in each of which the behavior of the node is: HELLO_STATE: When a node newly assigns its own address, it enters the HELLO_STATE, where it generates HELLO messages, but not topology control (TC) messages. It does not participate in MPR selection nor MPR flooding, and does not participate in data packet forwarding either. It doesn't fill the topology set nor the routing table. When it detects that it has an address conflict with other nodes based on received hello messages (rules R1 to R3, and rule R12), it re-selects a new address based on the busy address list. When a pre-determined time has elapsed, in this state, without detecting address conflict, the node enters the topology state. Mase & Adjih Expires November 27, 2005 [Page 27] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 TOPOLOGY_STATE: In this state, a node generates HELLO messages, but not TC messages. It processes TC messages, and performs MPR selection, but cannot be MPR itself and hence, does not forward TC messages. It fills the network topology set but not the routing table, and does not participate in data packet forwarding. When it detects that it has an address conflict with another node (based rules R1 to R12 applied to received messages), it re- selects a new address (using the recommendations of Section 4.2) and returns to the HELLO_STATE. When a pre-determined time elapses in the TOPOLOGY_STATE without detecting address conflict, the node enters the NORMAL_STATE. NORMAL_STATE: In this state, the node is running the "normal" OLSR protocol, completed with the algorithms specified in this document , and without message processing/generation restrictions associated to the state. More precisely, the node generates both HELLO messages and TC messages as usual. It processes TC messages generated by other nodes and forwards them as usual based on MPR flooding. It fills the topology set, calculates routing tables and participates in data forwarding. Only nodes in the NORMAL_STATE are selected as the intermediary nodes (forwarders) in the routing table calculation. When the node detects that it has an address conflict with other nodes (according to one of the rules R1 to R12), it re-selects a new address and enters the HELLO_STATE. The behavior in each state is summarized in the following table: +----------------+----------------+----------------+----------------+ | State | HELLO_ STATE | TOPOLOGY_ | NORMAL_ STATE | | | | STATE | | +----------------+----------------+----------------+----------------+ | Selectable as | no | no | yes | | MPR | | | | | | | | | | MPR selection | no | yes | yes | | | | | | | TC message | no | no | yes | | forwarding | | | | | | | | | | TC message | no | yes | yes | | processing | | | | | (MPR flooding) | | | | | | | | | | TC message | no | no | yes | | generation | | | | | | | | | Mase & Adjih Expires November 27, 2005 [Page 28] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 | Routing table | no | no | yes | | (and | | | | | forwarding) | | | | | | | | | | DAD rules | R1, R2, R3, | R1 to R12 | R1 to R12 | | | and R12 | | | | | | | | | State duration | HELLO_ STATE_ | TOPOLOGY_ | forever | | (if no address | DURATION | STATE_ | | | change) | | DURATION | | +----------------+----------------+----------------+----------------+ 4.6 Node Familiarity The concept of "node familiarity" is introduced for use of some heuristics in DAD rules. The definition is the following: a node (or more precisely, an IP address) is "familiar" for another node, when the last one has had knowledge of existence of the first one for sufficiently long. An node which is not familiar is "unfamiliar". In NOA-OLSR, a node (more precisely, an address) considered familiar when the time elapsed since the first time that its address has appeared in any OLSR message, is greater than a fixed time interval NODE_FAMILIAR_TIME (see Section 6). Mase & Adjih Expires November 27, 2005 [Page 29] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 5. Autoconfiguration Specifications 5.1 Overview This section provide a low-level view of the changes and additions to the standard OLSR, necessary to implement NOA-OLSR performing duplicate address detection. The high-level description of the method, including algorithms, is in Section 4. 5.2 Information Repository Though the exchange of OLSR control messages, each node accumulates information about the network. This information is stored according to the descriptions in section 4 of the OLSR specification [3], modified accordingly to the changes proposed to this section. 5.2.1 Autoconfiguration State Each node has one "autoconfiguration state" (see Section 4.5), which is one of HELLO_STATE, TOPOLOGY_STATE and NORMAL_STATE. 5.2.2 State Information Base The State Information Base is the State Set: a set of type which hold some information relevant to autoconfiguration for each address. For each address in the network, a 'State Tuple' (S_main_addr, S_time, S_state, S_last_hello_time, S_last_hello_seq_num, S_last_tc_time, S_last_tc_seq_num, S_conflict_time, S_MPR_remember_time, S_MPR_forced_time, S_creation_time) is recorded. A state tuple primarily records information about the autoconfiguration state of the node, but also with a set of data about these addresses, which are used to perform autoconfiguration. S_main_addr: the address of the node S_state: the autoconfiguration state of the address (see Section 4.5) S_time: the time after which the tuple should be deleted S_last_hello_time, S_last_hello_seq_num: the last time an HELLO has been received from this address, and the sequence number of this last HELLO S_last_tc_time, S_last_tc_seq_num: the last time an TC has been received from this address (as originator), and the sequence Mase & Adjih Expires November 27, 2005 [Page 30] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 number of this last TC S_conflict_time: the time until which the address is considered to be in conflict S_MPR_remember_time: the time after which the node forgets that this address was selected as MPR by this node. S_MPR_forced_time: the time during which this address must be choosen as MPR S_creation_time: the time at which the state tuple was created 5.2.3 Duplicate Set In the standard OLSR protocol, each node recorded a "Duplicate Tuple" which includes the following fields (D_addr, D_seq_num, D_retransmitted, D_iface_list, D_time) (see section 3.4 of the OLSR specification [3] where they are documented). In NOA-OLSR, the following field is added: D_content_id. D_content_id is used to identify the content of the message which was received, and is should be a sequence of bytes. Use and requirement of D_content_id are highlighted in the next section. 5.2.3.1 Message Content Identifier A message content identifier is used by NOA-OLSR to check whether the content of a message is identical to one received previously. In standard OLSR functionning, the message sequence numbers are used for this purpose ; however in NOA-OLSR, because of the possibility of duplicate addresses, two messages with same originator address and same sequence number can be different if they are originated from conflicting nodes. The message content identifier is used in this context, to verify whether the message are actually identical. Each implementation must have a method to generate message content identifiers from a received message, and such a method is naturally denoted "Message Content Identifier Generation Method". It is typically some kind of hash method, and it should met the following requirements: It must take in input the message content, and output one "message content identifier" (whose exact implementation is left to implementors). The message content is defined as the sequence of bytes of an OLSR message, excluding the message header (section 3.3.2 of the OLSR specification [3]). Mase & Adjih Expires November 27, 2005 [Page 31] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 It must consistently generate the same message content identifier, when it is applied on the same message content. It should generate different message content identifiers, for different message contents, with a high probability (typically larger than the probability of address collision of one node). Two examples of methods which satisfy the requirements are the following: Copy method: the message content identifier is the sequence of bytes which constitute the message content itself. Hash method: the message content identifier is a sequence of bytes obtained after applying a hash function on the sequence of bytes of the message content. For instance the MD5 Message-Digest Algorithm [2], suitable at least for networks with less that one billion of OLSR nodes. Because the message content identifiers are not transmitted to other nodes, different nodes can implement different generation methods without compromising interoperability. 5.2.4 Set and Unset Fields Several of the newly introduced fields in the miscellanous tuple are not necessarily initialized at the tuple set creation. Such fields are: In state tuples, the fields: S_last_hello_time, S_last_hello_seq_num, S_last_tc_time, S_last_tc_seq_num, S_conflict_time, S_MPR_remember_time, S_MPR_forced_time In duplicate tuples, the field D_content_id After tuple creation, the node must be able to identify the fact that the field has been already set or not. How to do so is indeed an implementation issue, but in the remaining it is assumed that a node can verify whether a field "is set" which means that a value has been affected to the field yet. In the opposite case, the field "is not set". 5.3 Address Selection and Address Change 5.3.1 Address Selection A node can choose an address using any algorithm, as highlighted in Section 4.2, subject to one constraint. The only constraint is that Mase & Adjih Expires November 27, 2005 [Page 32] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 the address MUST NOT select any busy address, that is an address which has recently been used in the network. Precisely, a busy address is an address such that: o There exists a State Tuple in the State Set with: * S_main_addr == the given address ; and * S_time is not expired Hence it is required that either the address selection algorithm yields addresses which are different from any such addresses, or alternatively, that the algorithm run until the last address it generates is no longer busy. In case the algorithm is unable to generate a new address, the node may stop. 5.3.2 Address Change Upon detection of a conflict a node MUST change its address, by selecting a new one as described in Section 5.3.1. When a node sets a new address (for initialisation, or because it has just changed its address because of a conflict), the node SHOULD perform the following steps: The node sets its autoconfiguration state to HELLO_STATE. Any potential OLSR message waiting for transmission or forwarding at the routing protocol level, should be either send with the new proper address (originator), or should be discarded. Each link tuple of the Link Set must be modified so that L_local_iface_addr (which should be the previous address of the node), is set to new address. The MPR Selector Set is emptied. The routing table is emptied. Additionally, the autoconfiguration state evolves as follows: Also each time a conflict is detected, the node selects a new address and restarts from HELLO_STATE. If the node has been in state HELLO_STATE without address conflict for a duration greater than HELLO_STATE_DURATION, then: Mase & Adjih Expires November 27, 2005 [Page 33] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 The node sets its autoconfiguration state to TOPOLOGY_STATE The node recomputes its MPR set If the node has been in state TOPOLOGY_STATE without address conflict for a duration greater than TOPOLOGY_STATE_DURATION, then: The node sets its autoconfiguration state to NORMAL_STATE The node recomputes its MPR set The node recalculates its routing table 5.4 State Set Update The State Set records information that the node gathered about all the addresses which are known in the network. It is updated by a variety of means at different steps of the OLSR processing. 5.4.1 Populating the State Set One of the main informations that State Set records is whether an address has already been seen in the network, and what was the autoconfiguration state associated with that address. Because all external addresses of the network come from OLSR messages received, such messages are the source of information used to populate the State Set. Because state tuples may be used quite early in the processing, the node MUST satisfy the following requirements: o For any address which is to be used, the node must preliminary update its state tuple with the proper associated autoconfiguration state if it is know, or with the STATE_UNDEFINED autoconfiguration state. More precisely, in the basic functionning of the OLSR protocol, TC and HELLO messages are exchanged and upon receiving such a message, and: o The node should update the state tuple of Sender Interface Address with STATE_UNDEFINED (as per Section 5.4.2). o The node should update the state tuple of the Originator Address with STATE_UNDEFINED (as per Section 5.4.2). Mase & Adjih Expires November 27, 2005 [Page 34] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 o Depending on the message type, it should perform the following updates if it is one of the following: * HELLO_MESSAGE, HELLO_MESSAGE_WITH_STATE: update the state set according to Section 5.6.2.1 * TC_MESSAGE, TC_MESSAGE_WITH_STATE: update the state set according to Section 5.6.5.1 5.4.2 State Tuple Update This section describes the steps taken for the action refered in other sections as: updating the state tuple for a given address "Address" with a given state "Autoconfiguration State". The steps are the following: o If there exists no state tuple where: S_main_addr == given Address then one is created and inserted in the tuple set with the following values: * S_main_addr = given Address * S_creation_time = current time * S_state = STATE_UNDEFINED * S_MPR_remember_time is not set * S_MPR_forced_time is not set * S_conflict_time is not set * S_last_hello_time is not set * S_last_tc_time is not set o The state tuple (newly created or not) where S_main_addr == given Address is then modified as follows: S_time = current time + NODE_STATE_HOLD_TIME Mase & Adjih Expires November 27, 2005 [Page 35] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 After that, if the following condition is true: the given Autoconfiguration State is different from STATE_UNDEFINED, AND S_state is different from the given Autoconfiguration State Then a potential topology change is recorded and the state tuple is modified as follows: * S_state = given Autoconfiguration state A potential topology change implies that both the MPR set and the routing table SHOULD be recomputed. 5.4.3 Associated State Tuple Retrieval In many cases, the steps related to autoconfiguration use the state tuple associated to one address, that is: the state tuple such as S_main_addr is equal to that address (it is necessarily unique). If such a state tuple exists, then this is the one which is used when the "associated state tuple is retrieved". However, although such a state tuple should exist, it may be the case that such a state tuple has been deleted, because S_time has expired. This is because the state set is kept relatively independent from other processings and from other sets by design. When this case occurs when the "associated state tuple is retrieved", a new state tuple is created using the method in Section 5.4.2 (using STATE_UNDEFINED). 5.4.4 State Tuple: HELLO information update Each time the handling of a received HELLO message has been finished, the state tuple of its originator, that is the state tuple where: S_main_addr == Originator Address will exist (as an application of the rules Section 5.4.1). The node should then update or ensure that it had been updated as follows: S_last_hello_time = current time S_last_hello_seq_num = HELLO message sequence number Mase & Adjih Expires November 27, 2005 [Page 36] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 5.4.5 State Tuple: TC information update Each time the handling of a received TC message has been finished, the state tuple of its originator, that is the state tuple where: S_main_addr == Originator Address will exist (as an application of the rules Section 5.4.1). The node should then update or ensure that it had been updated as follows: S_last_tc_time = current time S_last_tc_seq_num = TC message sequence number 5.4.6 State Tuple: MPR information update Before recomputing its MPR set, as documented in section 8.3 of the OLSR specification [3], a node MUST use the current list of MPR to save the information that those nodes had been choosen as MPR in the recent past. This is used for DAD rule Section 4.3.5.2.1. For each address in its MPR set, the associated state tuple is retrieved (as per Section 5.4.3), and is modified as follows: o S_MPR_remember_time = current time + MAX_MPR_REMEMBER_TIME 5.4.7 Familiarity The concept of familiar addresses, which is described in Section 4.6, is used by NOA-OLSR. In the actual specification, the fact that a given address is familiar or unfamiliar is determined from the state set, as follows: 1. If there exists a state tuple in the state set, such as: S_main_addr = given address, AND current time > S_creation_time + NODE_FAMILIAR_TIME then: the address is familiar 2. Otherwise, the address is unfamiliar. Mase & Adjih Expires November 27, 2005 [Page 37] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 5.5 Changes in Message Processing 5.5.1 Overview This section gives a description of the changes in the processing of standard OLSR messages, namely HELLO messages and TC messages. 5.5.2 Packet Processing and Message Flooding The packet processing algorithm, documented in section 3.4 of the OLSR specification [3], has been changed. For convenience, such changes have been denoted "message pre-processing" and "message post- processing". Hence, an autoconfiguration pre-processing step and an autoconfiguration post-processing step have been added to the message processing of the standard OLSR. Upon receiving a OLSR packet, a node MUST perform a number of tasks for each encapsulated message, listed in section 3.4 of the OLSR specification [3]. The steps which have been added or changed are the following: 1 ... 1 bis {CHANGED:}Depending on whether or not the node has decided to interoperate with standard OLSR nodes (see Section 8.2), the node MUST check whether it must reject the message based on requirements of Section 5.6.7. It the message must be rejected, the processing of the message stops here. 2 If the time to live of the message is less than or equal to '0' (zero), the message MUST silently be dropped. {CHANGED:} Even if the message was sent by the receiving node (i.e., the Originator Address of the message is the main address of the receiving node), the node MUST perform the autoconfiguration pre-processing given indicated in Section 5.5.3. This pre-processing will finish with one of four statuses: Address conflict detected The node MUST then stop the processing of the packet and change its address according to the rules of Section 5.3.2. Interrupt message processing The node MUST then skip the processing of the current message, and proceed to the processing of the next message (if any) of the packet. Mase & Adjih Expires November 27, 2005 [Page 38] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 Retransmit message and interrupt message processing The node MUST first perform a special retransmission of the message according to the rules listed in Section 5.5.2.1, then skip the processing of the current message, and proceed to the processing of the next message (if any) of the packet. Continue message processing The node MUST continue the processing of the message. 3 ... 4 (same as in section 3.4 of the OLSR specification [3]) 5 {CHANGED:} the message SHOULD be post-processed according the the specifications of Section 5.5.4. 5.5.2.1 Special Retransmission A special retransmission method is used when it is assumed, that, in presence of address conflict, the MPR flooding mechanism alone would not necessarily guarantee the proper distribution of one message to the entire network. This retransmission can be performed as a result of the message pre-processing steps, it includes creation of a new duplicate tuple, followed by a retransmission of the message section 3.4.1 of the OLSR specification [3]: 1. A new duplicate tuple is inserted in the duplicate set with the special duplicate tuple creation documented in Section 5.5.2.2. 2. The TTL of the message is reduced by one. 3. The hop-count of the message is increased by one. 4. The message is broadcast on all interfaces (Notice: the remaining fields of the message header SHOULD be left unmodified.) 5.5.2.2 Special Duplicate Tuple Creation This document uses the duplicate set in additional ways differing from the standard OLSR [3]. Indeed, the duplicate set is also used for both messages generated by the node and for messages retransmitted using the Special Retransmission (Section 5.5.2.1) method. Such use relies on the creation of a duplicate tuple in a special way by one method, herehence called "Special Duplicate Tuple Creation". The duplicate tuple is created for a given message, and refering to the fields of the message, it is created as follows: Mase & Adjih Expires November 27, 2005 [Page 39] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 D_addr = Originator Address D_seq_num = Message Sequence Number D_retransmitted = true D_time = current time + DUP_HOLD_TIME D_iface_list contains all the interfaces of the node D_content_id = computed message content identifier (Section 5.2.3.1) 5.5.3 Autoconfiguration Message Pre-Processing This section specifies the message pre-processing which MUST be implemented. Note that the message pre-processing uses the message headers but doesn't interpret (parse) the message content ; instead it considers the message content as a sequence of bytes. The following steps MUST be followed: 1. If the message is a HELLO_MESSAGE or HELLO_WITH_STATE_MESSAGE, the node pre-processes the messages according to Section 5.5.3.1. 2. Otherwise, if the message is a TC_MESSAGE or TC_WITH_STATE_MESSAGE, the node pre-processes the messages according to Section 5.5.3.2. 3. Otherwise: 1. If the message was sent by the receiving node (i.e., the Originator Address of the message is the main address of the receiving node) the message pre-processing finish with status 'Interrupt Message Processing' 2. Otherwise, this pre-processing finishes with status 'Continue Message Processing'. 5.5.3.1 Hello Message Pre-Processing The pre-processing of such messages MUST be performed as follows, checking for the R1 (Section 4.3.3.1). 1. If the Originator Address of the message is the main address of the receiving node: Mase & Adjih Expires November 27, 2005 [Page 40] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 1. there is a conflict and the pre-processing finishes with status 'Address conflict detected' (in accordance to DAD rule R1 (Section 4.3.3.1)) 2. Otherwise, the pre-processing finishes with status 'Continue message processing' 5.5.3.2 TC Message Pre-Processing The pre-processing of such message MUST be performed checking for the DAD rules R4 (Section 4.3.5.1.1) and R5 (Section 4.3.5.2.2) as follows: 5.5.3.2.1 Rule R4 check o If the following condition is true: Originator Address == main address of the node o AND if there exists no tuple in the tuple set where: D_addr == Originator Address, AND D_seq_num == Message Sequence Number D_content_id == computed message content identifier o then, in accordance to rule R4 (Section 4.3.5.1.1), a conflict as been detected and the pre-processing is finished with status 'Address conflict detected'. 5.5.3.2.2 Rule R5 check The DAD rule R5 requires checking two conditions, namely, consistency of sequence numbers of TC messages, and consistency of message content of TC messages. The check for consistent sequence numbers is the following: o If the following condition is true: * Originator Address is different from main address of the node AND such TC has never been seen, that is: there exists no tuple in the duplicate set where: Mase & Adjih Expires November 27, 2005 [Page 41] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 D_addr == Originator Address, AND D_seq_num == Message Sequence Number AND a TC sequence number inconsistency is detected using the rules of Section 4.4.3, that is, precisely: there exists one tuple in the state set where: S_main_addr == Originator Address, AND S_last_tc_time is set , AND | Message Sequence Number - S_last_tc_seq_um | > MAX_TC_DIFF_SEQ_NUM, (where |a| is the absolute value of 'a'), AND | Message Sequence Number - S_last_tc_seq_um | > (current time - S_last_tc_time) * MAX_MESSAGE_RATE then, in accordance to rule R5 (Section 4.3.5.1.2) a conflict has been detected between two other nodes, and the pre-processing is finished with status 'Retransmit message and interrupt message processing'. The check for consistent TC message content is the following: o If the following condition is true: * Originator Address is different from main address of the node AND such TC has been seen, that is: there exists at least one tuple in the duplicate set where: D_addr == Originator Address, AND D_seq_num == Message Sequence Number AND there exists no tuple in the duplicate set where: D_addr == Originator Address, AND D_seq_num == Message Sequence Number, AND D_content_id == computed message content identifier (see Section 5.2.3.1) then, in accordance to rule R5 (Section 4.3.5.1.2) a conflict has been detected between two other nodes, and the pre-processing is Mase & Adjih Expires November 27, 2005 [Page 42] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 finished with status 'Retransmit message and interrupt message processing'. 5.5.4 Autoconfiguration Message Post-Processing The node MUST do the following post-processing, to ensure that any forwared TC has an associated duplicate tuple with proper D_content_id: 1. If the message is a TC_MESSAGE or a TC_WITH_STATE_MESSAGE: * If there exists a duplicate tuple such that: D_addr == Originator Address, AND D_seq_num == Message Sequence Number, AND D_content_id is not set * Then: The field D_content_id of this duplicate tuple is set to the value of the computed message content identifier (Section 5.2.3.1). 2. Otherwise the post-processing stops. 5.6 Changes in OLSR Message Processing This section documents the changes to be applied in the general processing of the OLSR protocol: OLSR message processing for HELLO and TC messages. 5.6.1 Changes in HELLO Message Format A new kind of HELLO message is used: it includes now both the autoconfiguration state of the node which generates the HELLO and the autoconfiguration state of neighbor interface addresses. The Message Type of the message is HELLO_WITH_STATE_MESSAGE (see also Section 5.6.7). Although another general format might be used, it is choosen to keep the format of a message HELLO_WITH_STATE is similar to a normal HELLO, except for the following: the reserved field is split in two and includes the state of the nodes (for the originator of the HELLO, and the neighbor nodes), as shown on Figure 14. Mase & Adjih Expires November 27, 2005 [Page 43] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Node State | Neigh. State | Htime | Willingness | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Code | Reserved | Link Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... Figure 14 "Node State" is the autoconfiguration state of the node. "Neighbor State" ("Neigh. State") is the autoconfiguration state of the neighbors being advertised. As a result, only neighbors which all have the same autoconfiguration state can be sent in the same HELLO_WITH_STATE: this is not restrictive in practice, because several different HELLO_WITH_STATE can be generated at the same time (each with different neighbor state). The choice if which of HELLO or HELLO_WITH_STATE to use, is specified in Section 5.6.7. 5.6.2 Changes in HELLO Message Processing The HELLO Message Processing modifies on the processing described in section 7.1.1 of the OLSR specification [3], in section 8.2.1 of the OLSR specification [3], and in section 8.4.1 of the OLSR specification [3]. The changes in the HELLO Message Processing are related to the DAD rules R2 (Section 4.3.4.1), R3 (Section 4.3.4.2), and R12 (Section 4.3.5.4.1). The "Originator Address" of a HELLO message is the main address of the node, which has emitted the message. Likewise, the "Neighbor State" MUST be computed from the Neighbor State field of the HELLO message (see Section 5.6.1). The application of the DAD rule R2 (Section 4.3.4.1) is done by performing the following processing with the message originator address: 1. The state tuple relative to the Originator Address of the message is updated (see Section 5.4.2) with autoconfiguration state equal Mase & Adjih Expires November 27, 2005 [Page 44] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 to the Neighbor State. 2. If that associated state tuple verifies: * S_last_hello_seq_num is set, AND * current time - S_last_hello_time < MIN_WRAP_AROUND_INTERVAL, AND * S_last_hello_seq_num is equal or greater to the Message Sequence Number of the received HELLO then the Originator is conflicting with another node, according to rule R2 (Section 4.3.4.1), and as a consequence, the state tuple MUST be updated as follow: * S_conflict_time = current time + CONFLICT_HOLD_TIME The application of the DAD rule R3 (Section 4.3.4.2) is done by checking whether the address of the node is advertised by the means of Section 5.6.3 in the HELLO of another node, as follows: 1. If inside the same HELLO message from another node, the address of the node appears more than one time, then: The node is in conflict and node MUST then stop the processing of the packet and change its address according to the rules of Section 5.3.2 The DAD rule @R12@ adds the following processing upon receiving a HELLO message: o for each address (henceforth: 2-hop neighbor address), listed in the HELLO message with Neighbor Type equal to SYM_NEIGH or MPR_NEIGH: 1. if the main address of the 2-hop neighbor address == main address of the receiving node: silently ignore the 2-hop address 2. otherwise if there exists a associated neighbor tuple where: N_neighbor_main_addr == 2-hop neighbor address, AND additionally there exists no two hop neighbor tuple where: Mase & Adjih Expires November 27, 2005 [Page 45] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 N_neighbor_main_addr == 2-hop neighbor address, AND N_2hop_addr == Originator address then, a potential conflict is assumed and: + state tuple associated to the 2-hop neighbor address is retrieved (see Section 5.4.3), and it is updated as follows: + S_MPR_forced_time = current time + CONFLICT_HOLD_TIME Additionally, the node would now process its own HELLO messages, because one check has been removed in Section 5.5.2. This should be avoided, hence now prior to performing the HELLO processing of section 7.1.1 of the OLSR specification [3], the node should check that: The Originator Address of HELLO message is not one of the main address of node and if it is not the case, the standard HELLO processing should be skipped. 5.6.2.1 State Set Update from HELLO The "Originator Address" of a HELLO message is the main address of the node, which has emitted the message, and is in the message header of the message (section 3.3.2 of the OLSR specification [3]). The "Node State" and the "Neighbor State" are fields inside the HELLO message and have been added for NOA-OLSR (see Section 5.6.1). Upon receiving a HELLO, and before any processing of the content (i.e. before using any of the addresses), the node SHOULD update the state set as follows: 1. The state tuple associated to Originator Address must be updated with the autoconfiguration state "Node State" (as per Section 5.4.2) 2. For each of the neighbor interface address received in the HELLO message: 1. The state tuple associated to neighbor interface address must be updated with the autoconfiguration state "Neighbor State" Mase & Adjih Expires November 27, 2005 [Page 46] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 5.6.3 Changes in HELLO Message Generation The HELLO Message Generation is the one described in section 6.2 of the OLSR specification [3], with modifications described in this section. There are two modifications. The first one is the application of the the DAD rule Section 4.3.4.2 and is related to rule Section 4.3.4.1: the address of neighbors which have been detected to be in conflict are advertised in the HELLO messages. There are implicitly advertised by a specific means: they are included twice in the HELLO message. The second modification relates to the specification of the autoconfiguration states in the messages. The amendments of section 6.2 of the OLSR specification [3] are hence: o The Node State field is set such that it corresponds to the node's current autoconfiguration state. o The Neighbor State field is set such that it corresponds to the autoconfiguration state of all addresses listed in the HELLO messages. Namely, for any Neighbor Interface Address which is advertised, it MUST be advertised in an HELLO message such that: * the associated state tuple (Section 5.4.3) has a S_state identical to the Neighbor State the message As a consequence, one node will send at least many different HELLO as there are different autoconfiguration states of neighbors. o The following rule is added: any neighbor conflicting address, as identified by the fact that there is one state tuple where: S_main_addr == address, AND S_conflict_time > current time and for which there exists one associated neighbor tuple where: N_neighbor_main_addr == S_main_addr this conflicting address MUST be cited at least once within the predetemined refreshing period REFRESH_INTERVAL in the following way: it must figure listed twice (or more) in the same link message, with proper Neighbor Code, and with either proper Link Code or LINK_UNSPEC. Mase & Adjih Expires November 27, 2005 [Page 47] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 5.6.4 Changes in TC Message Format A new kind of TC message is used: it includes now both the autoconfiguration state of the node which generates the TC and the autoconfiguration state of advertised addresses. The Message Type of the message is TC_WITH_STATE_MESSAGE. A similar change to HELLO messages (see Section 5.6.1) is performed: use of the reserved field for storing an extra Node State and Neighbor State (each of them within one byte) 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ANSN | Node State | Neigh. State | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Advertised Neighbor Main Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... Figure 15 "Node State" is the autoconfiguration state of the node. "Neighbor State" ("Neigh. State") is the autoconfiguration state of the neighbors being advertised. Note that only nodes in STATE_NORMAL are sending TCs, and only nodes in STATE_TOPOLOGY or STATE_NORMAL are selecting MPR (as per Section 4.5.2), hence the possible values in the "Node State" and "Neighbor State" fields are limited. Still, upon receiving a TC message, the TC processing should not assume this property is necessarily verified, for possible interoperability reasons. Additionaly, requirements about which of TC or TC_WITH_STATE to use, are specified in Section 5.6.7. 5.6.5 Changes in TC Message Processing The TC Message Processing specified in the section 9.5 of the OLSR specification [3] is now verifying the DAD rules R6 (Section 4.3.5.2.1), R7 (Section 4.3.5.2.2), R8 (Section 4.3.5.2.3) and R9 (Section 4.3.5.3.1), and additionally, is adapted in several ways. The following adaptions SHOULD be added: o The TC processing of section 9.5 of the OLSR specification [3] and the additional TC processing in this section, is only performed when the node is in TOPOLOGY_STATE or NORMAL_STATE. Mase & Adjih Expires November 27, 2005 [Page 48] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 o The state set should be updated from the TC messages. o Some TC messages uncover an address conflict involving the receiving node (rule R6 (Section 4.3.5.2.1)). o Some TC messages are to be ignored because they are estimated to include invalid information (rules R9 (Section 4.3.5.3.1)). o Some information in the TC messages (some addresses) should be ignored because it is estimated to be invalid (rules R5 (Section 4.3.5.1.2) and @R12@). Each of these are described in the following sections. 5.6.5.1 State Set Update from TC The "Originator Address" of a TC message is the main address of the node, which has emitted the message, and is in the message header of the message (section 3.3.2 of the OLSR specification [3]). The "Node State" and the "Neighbor State" are fields inside the TC message and have been added for NOA-OLSR (see Section 5.6.4). Upon receiving a TC, and before any processing of the content (i.e. before using any of the addresses), the node SHOULD update the state set as follows: 1. The state tuple associated to Originator Address must be updated with the autoconfiguration state "Node State" (as per Section 5.4.2) 2. For each of the advertised neighbor main address received in the TC message: 1. The state tuple associated to advertised neighbor address must be updated with the autoconfiguration state "Neighbor State" 5.6.5.2 Conflict detection based on TC message content The rule R6 (Section 4.3.5.2.1) asserts that the node is in conflict, if it receives a TC which advertises its address in an situation where it shouldn't. The pratical steps for completing this check are the following: o If in the received TC message: * the advertised address includes the main address of the node, AND Mase & Adjih Expires November 27, 2005 [Page 49] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 * the originator address is not in the MPR set of the node, AND * the associated state tuple of the originator address is such that at least one of the two following conditions is verified: + S_MPR_remember_time is not set, or else, + S_MPR_remember_time < current time o Then the node is in conflict: it will then stop the processing of the message and it MUST change its address according to the rules of Section 5.3.2. 5.6.5.3 Dismissed TC messages The rule R9 (Section 4.3.5.3.1) require certain TC messages to be dismissed because they are inconsistent with the collected information, and would contaminate routing tables. The familiarity (see Section 4.6) is at the core of the verification of rule R9. Before further processing a TC , the node MUST first checks whether the originator address of the TC is familiar (as described Section 5.4.7). If and only if, it is the case, the following steps determine whether the TC processing should be interrupted according to rule R9: 1. The number of familiar addresses Nf and the number of unfamiliar addresses Nu is computed for TC 2. If the ratio of familiar addresses is too low, that is precisely if: Nf < (Nf + Nu) * MIN_TC_FAMILIARITY_RATE Then: * the TC message should be ignored 5.6.5.4 Dismissed addresses in TC messages Upon receiving a TC and prior to TC processing of each address according to section 9.5 of the OLSR specification [3], the DAD rules R7 (Section 4.3.5.2.2) and R8 (Section 4.3.5.2.3) require some addresses to be ignored to prevent routing table contamination. In application of the rule R7 (Section 4.3.5.2.2), the node SHOULD Mase & Adjih Expires November 27, 2005 [Page 50] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 ignore any advertised address in a TC message which verifies the following conditions simultaneously: o The advertised address is not one interface address of the node, AND o The Originator Address of the TC is familiar (as per Section 5.4.7), AND o The advertised address is familiar (as per Section 5.4.7), AND o There exists no topology tuple where: * Either T_last_addr == advertised address * or T_dest_addr == advertised address Additionaly, in application of the rule R8 (Section 4.3.5.2.3), the node SHOULD ignore any advertised address in a TC message which verifies the following conditions simultaneously: o There exists a neighbor tuple where: * N_neighbor_main_addr == advertised address, AND * N_status == SYM and then, o There exists no two hop tuple where: * N_neighbor_main_addr == advertised address, AND * N_2hop_addr == Originator Address 5.6.6 Changes in TC Message Generation In order to build the topology information base, each node, which has been selected as MPR, broadcasts Topology Control (TC) messages in the OLSR protocol. The following changes should be made in the TC message generation of section 9.3 of the OLSR specification [3]. The conditions for actually generating TC messages, now additionally take into account the autoconfiguration state (see Section 4.5.2): o A node SHOULD only generate messages when it is in STATE_NORMAL Mase & Adjih Expires November 27, 2005 [Page 51] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 The format of TC messages is different, and hence the TC message generation should fill properly the extra information: o The Node State field is set such that it corresponds to the current autoconfiguration state of the node. o The Neighbor State field is set such that it corresponds to the autoconfiguration state of all addresses advertised in the TC message. Namely, for any address which is advertised, it MUST be advertised in an TC message such that: * the associated state tuple (Section 5.4.3) has a S_state identical to the Neighbor State of the message As a consequence, one node will send at least as many different TCs as there are different autoconfiguration states of advertised addresses. Finally, the node MUST keep track of the TCs it has sent, and this is done by adding information in the duplicate set. To do so, after the generation of each TC message, the node records it by creating a duplicate tuple. However due to an address conflict, the node may already have such a tuple for a received TC from a conflicting node, hence the two steps update: first check whether there is such TC, and second, if not, create the duplicate tuple. This is done as follows, before the TC message is actually sent: 1. the message content identifier is computed (as per Section 5.2.3.1) 2. If there exists a duplicate tuple where: * D_addr == main address of node * D_seq_num == TC message sequence number (in message header) Then the node is in conflict (as an application of rule R4 (Section 4.3.5.1.1)), and * it will then stop the processing of the message and it MUST change its address according to the rules of Section 5.3.2 3. Otherwise the node creates a duplicate tuple, accordingly to Special Duplicate Tuple Creation (Section 5.5.2.2). Mase & Adjih Expires November 27, 2005 [Page 52] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 5.6.7 Message Type for HELLO and TC Messages New message types are introduced by NOA-OLSR, for use with the new HELLO message format in Section 5.6.1, and the new TC message format inSection 5.6.4. Because these messages simply use "reserved" (blank) fields in standard OLSR messages, it would be possible to use the standard message types HELLO_MESSAGE and TC_MESSAGE. However for interoperability reasons, a node SHOULD NOT do so. Instead it should decide first whether it wants to interoperate with standard OLSR implementations, or not interoperate. See Section 8.2 for a comprehensive discussion of interoperability with standard OLSR. Depending on whether it chooses to interoperate with the standard OLSR implementations the node, should originate messages as follows: Interoperating with standard OLSR: The node MUST generate messages with HELLO_MESSAGE type and TC_MESSAGE type when the fields "node state" and the "neighbor state" of the message are both in state NORMAL. It MUST ignore all the messages with "node state" == NORMAL_STATE and message type HELLO_WITH_STATE_MESSAGE or TC_WITH_STATE_MESSAGE. Never interoperating with standard OLSR: The node MUST generate all HELLO and TC messages with a message type of HELLO_WITH_STATE_MESSAGE or TC_WITH_STATE_MESSAGE. It MUST ignore all the messages with message type HELLO_MESSAGE and TC_MESSAGE. 5.7 Changes in MPR Computation The MPR computation is changed as follows. First, before any new MPR computation, it must be kept track of the previous MPR set, as indicated in Section 5.4.6. During MPR computation, the node should avoid any node in a state different from STATE_NORMAL (as Section 4.5.2 specifies). After the MPR computation has been achieved, yielding a new MPR set, this set is completed with the MPR enforced by autoconfiguration rules (namely rule R12 (Section 4.3.5.4.1)), as follows: The node MUST add to its MPR set, the address S_main_addr of any state tuple where: S_main_addr is not already in the newly computed MPR list S_MPR_forced_time > current time Mase & Adjih Expires November 27, 2005 [Page 53] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 There exists a neighbor tuple in the neighbor set where: N_neighbor_main_addr == S_main_addr N_status == SYM 5.8 Changes in Routing Table Calculation Standard routing table calculation is described in section 10 of the OLSR specification [3]. However with the introduction of the autoconfiguration state, it should now be exclusively be performed when the node is in NORMAL_STATE (see Section 4.5.2). The computed routes should also only have forwarders which are in the NORMAL_STATE, and hence the routing table computation algorithm should be modified. The property of using only forwarders in the NORMAL_STATE can be expressed as ensuring that only route entries where: R_next_addr is associated to a state tuple (as retrieved by Section 5.4.3) where S_state == NORMAL_STATE OR ELSE: R_next_addr == R_dest_addr (i.e. this is a direct neighbor) This property can be ensured by: o in step 3 of the algorithm of section 10 of the OLSR specification [3], using only 2-hop tuples where N_neighbor_main_addr is associated to a state tuple (Section 5.4.3) with S_state == NORMAL_STATE o in "the second step 3", sub-step 3.1: using only topology tuples where T_last_addr is associated to a state tuple (Section 5.4.3) with S_state == NORMAL_STATE Mase & Adjih Expires November 27, 2005 [Page 54] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 6. Proposed Values for Constants The proposed values of the specification are documented here. Many of them are depend on the constants section 18 of the OLSR specification [3]. HELLO_STATE_DURATION (= HELLO_INTERVAL) TOPOLOGY_STATE_DURATION (= TC_INTERVAL) MAX_MPR_REMEMBER_TIME (= 2 x NEIGHB_HOLD_TIME) CONFLICT_HOLD_TIME (= NEIGHB_HOLD_TIME) NODE_FAMILIAR_TIME MIN_WRAP_AROUND_INTERVAL (= DUP_HOLD_TIME) MIN_TC_FAMILIARITY_RATE (= 50%) MAX_TC_DIFF_SEQ_NUM, MAX_MESSAGE_RATE NODE_STATE_HOLD_TIME (= 10 x DUP_HOLD_TIME) Codes for Autoconfiguration State (in messages) o NORMAL_STATE = 0 o TOPOLOGY_STATE = 1 o HELLO_STATE = 2 o UNDEFINED_STATE = 3 In this section, several proposed values are dependent on OLSR protocol values. However, it is allowed in standard OLSR, to change some parameters (which will result in changes of "validity time" of some messages, for instance): then there is an ambiguity about which parameters should be chosen: the parameters of the receiving node, or the parameters of the sender node. The values that are proposed here can be used by default, and can be replaced by more appropriate values where necessary. Mase & Adjih Expires November 27, 2005 [Page 55] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 7. IANA Considerations Two new types of control messages are defined in NOA-OLSR. Because this document is a draft, some values in the range reserved for private/local use (see section 22 of the OLSR specification [3]) are proposed: HELLO_WITH_STATE_MESSAGE = 130 TC_WITH_STATE_MESSAGE = 131 Values in the range 5-127 might be allocated in the OLSR registry using standards action, for these new messages. Mase & Adjih Expires November 27, 2005 [Page 56] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 8. Limitations and interoperability considerations There are several limitations associated with NOA-OLSR proposed in this specification. The most important of them is related to the fact that the node is assumed to work exclusively in an environment where all nodes have a single interface, but there exists some other minor limitations which are explained in Section 8.1. The other kind of limitation is a direct consequence of the previous one: although an implementation of NOA-OLSR will interoperate with most standard OLSR implementations, some features of standard OLSR interact negatively, and unconditional interoperability is not warranted. The conditions of interoperability are documented in Section 8.1. 8.1 Limitations The limitations of NOA-OLSR protocol are highlighted in this document. Some of the limitations will be addressed in future versions of this document, some are intrinsic to the method, and may be lifted by added requirements on the OLSR protocol. In this section, the analysis of these limitations is provided. In this version of this draft, the first one, the duplicate detection rules have been specified only the most common case, where the node has a single interface participating in the MANET. This rules can naturally be extended to integrate multiple interfaces, but doing so is not immediatly straightforward, and hence will be the subject of further specification. Meanwhile, an implementation of this specification of NOA-OLSR cannot be expected to perform reliably with several interfaces, and more precisely: o Some duplicate address conflicts will not be detected. o The assumptions of some rules are no longer verified. For instance, rule R1 assumes that a node will not receive the HELLO messages that it generates. o The changes in OLSR processing will result, in some cases, in a general state of the node (including the data of the miscellaneous information repositories) which is inconsistent and otherwise impossible in both the standard OLSR and NOA-OLSR. This will result in unpredictable behavior. Another present restriction derives from the assumption that TC messages will include only MPR selectors in rule R6. The rule could be approprietly relaxed, but for any implementation which doesn't, in some cases, the node will not interoperate with nodes which are advertising more than their MPR selector set. Precisely, these are nodes which include they auxiliary functionning of "Redundant Mase & Adjih Expires November 27, 2005 [Page 57] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 Topology Information" in section 15 of the OLSR specification [3] (with TC_REDUNDANCY different from 0, see section 15.1 of the OLSR specification [3]). Concerning the intrisic restrictions due to the DAD rules, the most noticeable is the use of message sequence numbers to detect message inconsistency (as Section 4.4). This assumes, logically, that the message sequence numbers will be linearily incremented, however this is property of the standard OLSR is not stated as a "REQUIREMENT". Practices such as computing a sequence number from the content of the message, for instance, would defeat autoconfiguration mechanisms. Finally, the necessary changes auxiliary functions of OLSR (such as for options "Non-OLSR Interfaces", section 12 of the OLSR specification [3]), are not addressed in this documente, and the impact of NOA-OLSR on auxiliary functionning is not addressed for the time being. 8.2 Interoperability with Standard OLSR A node implementing NOA-OLSR protocol relies on some assumptions given in the previous Section 8.1, hence might not be able to interoperate successfully with a MANET comprising given standard OLSR implementations. Two modes of operation are defined in Section 5.6.7: o a node that never interoperates with nodes running standard OLSR. o a node that always interoperates with nodes running the standard OLSR protocol. The discussion and logic behind interoperability is found in Section 8.2.1, and the discussion and logic behind isolation is in Section 8.2.2. 8.2.1 Considerations for Interoperability with Standard OLSR A sufficient condition for interoperability between two link state routing protocols running on the same network, is that they both use the same topology information and the same algorithm for route calculation, and also if topology information exchange is not disrupted. This sufficient condition is verified for the standard OLSR and NOA-OLSR, when it is implemented as documented here and in Section 5.6.7. Namely: o When a node is in the NORMAL_STATE, it will advertise all information about addresses in NORMAL_STATE inside HELLO and TC Mase & Adjih Expires November 27, 2005 [Page 58] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 messages which are compliant with standard OLSR. o When a node is not in the NORMAL_STATE, or alternatively when it advertises information about addresses which are not in NORMAL_STATE, it uses messages that the standard OLSR will not process. The sufficient conditions are satisfied because: o As the standard OLSR does, NOA-OLSR uses only nodes in the NORMAL_STATE for computing routes as forwarders. o MPR flooding is not disrupted, because: nodes with NOA-OLSR which are not in NORMAL_STATE are invisible to the standard OLSR. As a result: * MPR flooding from Sstandard OLSR nodes: standard OLSR nodes will never attempt to select as MPR some nodes which are not in NORMAL_STATE, hence no problem arises. * MPR flooding from nodes with NOA-OLSR: nodes implementing NOA- OLSR, that are not in NORMAL_STATE, are not selected as MPR. Because of some of the current restrictions of NOA-OLSR, it might be the case that in some networks, one given implementation of modified OLSR won't interoperate with one given standard OLSR implementation. This issue is addressed in the next Section 8.2.2. 8.2.2 Considerations for Isolation from Standard OLSR Nodes It may be desired to isolate an implementation of NOA-OLSR from the standard OLSR networks. This is a perticuliar instance of the related problem of separating of a OLSR, MANET or general network in different administrative entities. In the OLSR protocol, all links between OLSR interfaces are discovered by means of neighbor sensing. Then, isolating one node to another node can be achieved by either of them ignoring the messages of the other. This results into an asymmetrical link, which will neither be used for MPR selection, nor MPR flooding nor route calculation, and in practice, in isolation of the nodes from each other. However doing so, requires generally an external mechanism to exchange information sufficient for one node to determine whether it want to be isolated from another. In the case of NOA-OLSR, this information is implicitly provided as follows: Mase & Adjih Expires November 27, 2005 [Page 59] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 o A node which doesn't wish to interoperate with standard OLSR, should transmit all its HELLO and TC messages with message type HELLO_WITH_STATE and TC_WITH_STATE o A node which wishes to interoperate with standard OLSR, should transmit all its HELLO and TC messages, when in STATE_NORMAL, , with message type HELLO_MESSAGE and TC_MESSAGE These rules must be respected, as enforced by Section 5.6.7. Note that as a consequence, a node which receives HELLO message from a node in STATE_NORMAL (or from a standard OLSR node), can deduce which kind of policy it enforce. Mase & Adjih Expires November 27, 2005 [Page 60] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 9. Requirements notation 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 [1]. Mase & Adjih Expires November 27, 2005 [Page 61] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 10. Security Considerations As the standard OLSR does not specify any special security measure, it makes a target for various attacks (see section 20 of the OLSR specification [3]) ; NOA-OLSR is subject to the same attacks, but also to other attacks: such as forging messages in order to deliberatly trigger some DAD rules, hence forcing an address change, or increasing OLSR control traffic. However the conditions in which such attacks can be sucessfully conducted are some conditions in which more severe attacks can be conducted with the standard OLSR protocol. Hence, in practice, vulnerability of NOA-OLSR protocol against deliberate attacks, is identical to the vulnerability of the standard OLSR protocol. Mase & Adjih Expires November 27, 2005 [Page 62] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 11. Acknowledgements This work was funded by Strategic Information and Communications R&D Promotion Programme (SCOPE), Ministry of Internal Affairs and Communications, Japan. The authors would also like to thank Sota Yoshida, Masoto Goto, Takashi Hasegawa for their valuable contributions to NOA-OLSR, along wth Yasuhiro Owada, and many other students of Information and Communication Network Laboratory for other various aspects for developping and testing of this protocol. (document generation date: Thu May 26 15:00:15 2005) Mase & Adjih Expires November 27, 2005 [Page 63] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 12. References 12.1 Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 12.2 Informative References [2] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 1992. [3] Clausen, T. and P. Jacquet, "Optimized Link State Routing Protocol (OLSR)", RFC 3626, October 2003. [4] Ogier, R., Templin, F., and M. Lewis, "Topology Dissemination Based on Reverse-Path Forwarding (TBRPF)", RFC 3684, February 2004. [5] Perkins, C., Belding-Royer, E., and S. Das, "Ad hoc On-Demand Distance Vector (AODV) Routing", RFC 3561, July 2003. [6] Johnson, D., "The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)", draft-ietf-manet-dsr-10 (work in progress), July 2004. [7] Ruffino, S., Stupar, P., and T. Clausen, "Autoconfiguration in a MANET: connectivity scenarios and technical issues", draft-ruffino-manet-autoconf-scenarios-00 (work in progress), October 2004. [8] Weniger, K., "Passive Duplicate Address Detection in Mobile Ad hoc Networks", March 2003. [9] Mase, K., "No Overhead IP Address Autoconfiguration for Mobile Ad Hoc Networks with Proactive Routing", Work in progress. Mase & Adjih Expires November 27, 2005 [Page 64] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 Authors' Addresses Pr. Kenichi Mase Information and Communication Network Lab.,Niigata University Niigata University Niigata 950-2181, Japan Phone: +81 25 262 7446 Email: mase@ie.niigata-u.ac.jp URI: http://www.net.ie.niigata-u.ac.jp/ Cedric Adjih Information and Communication Network Lab.,Niigata University Niigata University (Permanent address: INRIA Domaine de Voluceau, Rocquencourt, France) Niigata 950-2181, Japan Email: cedric@net.ie.niigata-u.ac.jp, cedric.adjih@inria.fr Mase & Adjih Expires November 27, 2005 [Page 65] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 Index D Duplicate Address Detection Rule R1 13 R2 14 R3 14 R4 16 R5 16 R6 18 R7 19 R8 20 R9 21 R10 22 R11 23 R12 24 I Index Document structure 7 S Specification Busy Address 33 T terminology Address Conflict 9 Autoconfiguration State 9 Busy Address 9 Conflicting Address 9 Conflicting Message 9 Conflicting Node 9 DAD Rule 9 Duplicate Address Detection (DAD) 9 familiar address 9 familiar node 9 Message Content Identifier Generation Method 9 Message Content Identifier 9 NOA-OLSR 10 Routing Table Contamination Avoidance 10 Sequence Number Consistency 10 Standard OLSR 10 TC Generator 10 unfamiliar node 9 Mase & Adjih Expires November 27, 2005 [Page 66] Internet-Draft No Overhead Autoconfiguration OLSR May 2005 Intellectual Property Statement 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. Disclaimer of Validity 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 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. Copyright Statement Copyright (C) The Internet Society (2005). 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. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Mase & Adjih Expires November 27, 2005 [Page 67]