Mobile Ad hoc Networking (MANET) T. Clausen Internet-Draft LIX, Ecole Polytechnique, France Expires: December 28, 2006 C. Dearlove BAE Systems Advanced Technology Centre P. Jacquet Project Hipercom, INRIA The OLSRv2 Design Team MANET Working Group June 26, 2006 The Optimized Link-State Routing Protocol version 2 draft-ietf-manet-olsrv2-02 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 December 28, 2006. Copyright Notice Copyright (C) The Internet Society (2006). Abstract This document describes version 2 of the Optimized Link State Routing (OLSRv2) protocol for mobile ad hoc networks. The protocol embodies Clausen, et al. Expires December 28, 2006 [Page 1] Internet-Draft OLSRv2 June 2006 an optimization of the classical link state algorithm tailored to the requirements of a mobile wireless LAN. The key optimization of OLSRv2 is that of multipoint relays, providing an efficient mechanism for network-wide broadcast of link- state information (i.e. reducing the cost of performing a network- wide link-state broadcast). A secondary optimization is that OLSRv2 employs partial link-state information: each node maintains information about all destinations, but only a subset of links. This allows that only select nodes diffuse link-state advertisements (i.e. reduces the number of network-wide link-state broadcasts) and that these advertisements contain only a subset of links (i.e. reduces the size of each network-wide link-state broadcast). The partial link- state information thus obtained still allows each OLSRv2 node to at all times maintain optimal (in terms of number of hops) routes to all destinations in the network. OLSRv2 imposes minimum requirements to the network by not requiring sequenced or reliable transmission of control traffic. Furthermore, the only interaction between OLSRv2 and the IP stack is routing table management. OLSRv2 is particularly suitable for large and dense networks as the technique of MPRs works well in this context. Clausen, et al. Expires December 28, 2006 [Page 2] Internet-Draft OLSRv2 June 2006 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 6 1.2. Applicability Statement . . . . . . . . . . . . . . . . . 6 2. Protocol Overview and Functioning . . . . . . . . . . . . . . 8 2.1. Protocol Extensibility . . . . . . . . . . . . . . . . . . 10 3. Processing and Forwarding Repositories . . . . . . . . . . . . 11 3.1. Received Set . . . . . . . . . . . . . . . . . . . . . . . 11 3.2. Fragment Set . . . . . . . . . . . . . . . . . . . . . . . 11 3.3. Processed Set . . . . . . . . . . . . . . . . . . . . . . 12 3.4. Forwarded Set . . . . . . . . . . . . . . . . . . . . . . 12 3.5. Relay Set . . . . . . . . . . . . . . . . . . . . . . . . 12 4. Packet Processing and Message Forwarding . . . . . . . . . . . 14 4.1. Actions when Receiving an OLSRv2 Packet . . . . . . . . . 14 4.2. Actions when Receiving an OLSRv2 Message . . . . . . . . . 14 4.3. Message Considered for Processing . . . . . . . . . . . . 15 4.4. Message Considered for Forwarding . . . . . . . . . . . . 17 5. Information Repositories . . . . . . . . . . . . . . . . . . . 20 5.1. Neighborhood Information Base . . . . . . . . . . . . . . 20 5.1.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . 20 5.1.2. MPR Set . . . . . . . . . . . . . . . . . . . . . . . 21 5.1.3. MPR Selector Set . . . . . . . . . . . . . . . . . . . 21 5.2. Topology Information Base . . . . . . . . . . . . . . . . 21 5.2.1. Advertised Neighbor Set . . . . . . . . . . . . . . . 21 5.2.2. ANSN History Set . . . . . . . . . . . . . . . . . . . 22 5.2.3. Topology Set . . . . . . . . . . . . . . . . . . . . . 22 5.2.4. Attached Network Set . . . . . . . . . . . . . . . . . 23 5.2.5. Routing Set . . . . . . . . . . . . . . . . . . . . . 23 6. OLSRv2 Control Message Structures . . . . . . . . . . . . . . 24 6.1. General OLSRv2 Message TLVs . . . . . . . . . . . . . . . 24 6.1.1. VALIDITY_TIME TLV . . . . . . . . . . . . . . . . . . 24 6.2. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 25 6.2.1. HELLO Message OLSRv2 Message TLVs . . . . . . . . . . 26 6.2.2. HELLO Message OLSRv2 Address Block TLVs . . . . . . . 26 6.3. TC Messages . . . . . . . . . . . . . . . . . . . . . . . 27 6.4. TC Message: OLSRv2 Address Block TLVs . . . . . . . . . . 27 7. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 29 7.1. HELLO Message: Transmission . . . . . . . . . . . . . . . 29 8. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 30 8.1. Populating the MPR Selector Set . . . . . . . . . . . . . 30 8.2. Symmetric Neighborhood and 2-Hop Neighborhood Changes . . 31 9. TC Message Generation . . . . . . . . . . . . . . . . . . . . 32 9.1. TC Message: Transmission . . . . . . . . . . . . . . . . . 33 10. TC Message Processing . . . . . . . . . . . . . . . . . . . . 34 10.1. Single TC Message Processing . . . . . . . . . . . . . . . 34 10.1.1. Populating the ANSN History Set . . . . . . . . . . . 35 10.1.2. Populating the Topology Set . . . . . . . . . . . . . 35 Clausen, et al. Expires December 28, 2006 [Page 3] Internet-Draft OLSRv2 June 2006 10.1.3. Populating the Attached Network Set . . . . . . . . . 36 10.2. Completed TC Message Processing . . . . . . . . . . . . . 37 10.2.1. Purging the Topology Set . . . . . . . . . . . . . . . 37 10.2.2. Purging the Attached Network Set . . . . . . . . . . . 37 11. Populating the MPR Set . . . . . . . . . . . . . . . . . . . . 38 12. Populating Derived Sets . . . . . . . . . . . . . . . . . . . 39 12.1. Populating the Relay Set . . . . . . . . . . . . . . . . . 39 12.2. Populating the Advertised Neighbor Set . . . . . . . . . . 39 13. Routing Table Calculation . . . . . . . . . . . . . . . . . . 40 14. Proposed Values for Constants . . . . . . . . . . . . . . . . 44 14.1. Neighborhood Discovery Constants . . . . . . . . . . . . . 44 14.2. Message Intervals . . . . . . . . . . . . . . . . . . . . 44 14.3. Holding Times . . . . . . . . . . . . . . . . . . . . . . 44 14.4. Willingness . . . . . . . . . . . . . . . . . . . . . . . 44 15. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . 45 16. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 46 16.1. Multicast Addresses . . . . . . . . . . . . . . . . . . . 46 16.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 46 16.3. TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 46 17. References . . . . . . . . . . . . . . . . . . . . . . . . . . 48 17.1. Normative References . . . . . . . . . . . . . . . . . . . 48 17.2. Informative References . . . . . . . . . . . . . . . . . . 48 Appendix A. Example Heuristic for Calculating MPRs . . . . . . . 49 Appendix B. Heuristics for Generating Control Traffic . . . . . 52 Appendix C. Protocol and Port Number . . . . . . . . . . . . . . 53 Appendix D. Packet and Message Layout . . . . . . . . . . . . . 54 Appendix D.1. OLSRv2 Packet Format . . . . . . . . . . . . . . . . 54 Appendix E. Node Configuration . . . . . . . . . . . . . . . . . 59 Appendix F. Jitter . . . . . . . . . . . . . . . . . . . . . . . 60 Appendix G. Security Considerations . . . . . . . . . . . . . . 63 Appendix G.1. Confidentiality . . . . . . . . . . . . . . . . . . 63 Appendix G.2. Integrity . . . . . . . . . . . . . . . . . . . . . 63 Appendix G.3. Interaction with External Routing Domains . . . . . 64 Appendix G.4. Node Identity . . . . . . . . . . . . . . . . . . . 65 Appendix H. Flow and Congestion Control . . . . . . . . . . . . 66 Appendix I. Contributors . . . . . . . . . . . . . . . . . . . . 67 Appendix J. Acknowledgements . . . . . . . . . . . . . . . . . . 68 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 69 Intellectual Property and Copyright Statements . . . . . . . . . . 70 Clausen, et al. Expires December 28, 2006 [Page 4] Internet-Draft OLSRv2 June 2006 1. Introduction The Optimized Link State Routing protocol version 2 (OLSRv2) is an update to OLSRv1 as published in RFC3626 [1]. Compared to RFC3626, OLSRv2 retains the same basic mechanisms and algorithms, while providing an even more flexible signaling framework and some simplification of the messages being exchanged. Also, OLSRv2 takes care to accommodate both IPv4 and IPv6 addresses in a compact fashion. OLSRv2 is developed for mobile ad hoc networks. It operates as a table driven, proactive protocol, i.e. it exchanges topology information with other nodes of the network regularly. Each node selects a set of its neighbor nodes as "MultiPoint Relays" (MPRs). Only nodes that are selected as such MPRs are then responsible for forwarding control traffic intended for diffusion into the entire network. MPRs provide an efficient mechanism for flooding control traffic by reducing the number of transmissions required. Nodes selected as MPRs also have a special responsibility when declaring link state information in the network. Indeed, the only requirement for OLSRv2 to provide shortest path routes to all destinations is that MPR nodes declare link-state information for their MPR selectors. Additional available link-state information may be utilized, e.g. for redundancy. Nodes which have been selected as multipoint relays by some neighbor node(s) announce this information periodically in their control messages. Thereby a node announces to the network that it has reachability to the nodes which have selected it as an MPR. Thus, as well as being used to facilitate efficient flooding, MPRs are also used for route calculation from any given node to any destination in the network. A node selects MPRs from among its one hop neighbors with "symmetric", i.e. bi-directional, linkages. Therefore, selecting routes through MPRs automatically avoids the problems associated with data packet transfer over uni-directional links (such as the problem of not getting link-layer acknowledgments for data packets at each hop, for link-layers employing this technique for unicast traffic). OLSRv2 is developed to work independently from other protocols. Likewise, OLSRv2 makes no assumptions about the underlying link- layer. However, OLSRv2 may use link-layer information and notifications when available and applicable. OLSRv2, as OLSRv1, inherits the concept of forwarding and relaying from HIPERLAN (a MAC layer protocol) which is standardized by ETSI Clausen, et al. Expires December 28, 2006 [Page 5] Internet-Draft OLSRv2 June 2006 [6]. 1.1. Terminology The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC2119 [2]. MANET specific terminology is to be interpreted as described in [3] and [4]. Additionally, this document uses the following terminology: node - A MANET router which implements the Optimized Link State Routing protocol version 2 as specified in this document. OLSRv2 interface - A MANET interface, running OLSRv2. symmetric strict 2-hop neighbor - A symmetric 2-hop neighbor which is not a symmetric 1-hop neighbor and is not a 2-hop neighbor only through a symmetric 1-hop neighbor with willingness WILL_NEVER. (If node Z is a symmetric 2-hop neighbor of node X then there is a node Y such that node Z is a symmetric 1-hop neighbor of node Y and node Y is a symmetric 1-hop neighbor of node X. If node Z is a symmetric strict 2-hop neighbor of node X then there is such a node Y with willingness which is not WILL_NEVER.) symmetric strict 2-hop neighborhood - The set of the symmetric strict 2-hop neighbors of node X. multipoint relay (MPR) - A node which is selected by its symmetric 1-hop neighbor, node X, to "re-transmit" all the broadcast messages that it receives from node X, provided that the message is not a duplicate, and that the hop limit field of the message is greater than one. MPR selector - A node which has selected its symmetric 1-hop neighbor, node X, as one of its MPRs is an MPR selector of node X. 1.2. Applicability Statement OLSRv2 is a proactive routing protocol for mobile ad hoc networks (MANETs) [7], [8]. It is well suited to large and dense networks of mobile nodes, as the optimization achieved using the MPRs works well in this context. The larger and more dense a network, the more optimization can be achieved as compared to the classic link state algorithm. OLSRv2 uses hop-by-hop routing, i.e. each node uses its local information to route packets. Clausen, et al. Expires December 28, 2006 [Page 6] Internet-Draft OLSRv2 June 2006 As OLSRv2 continuously maintains routes to all destinations in the network, the protocol is beneficial for traffic patterns where the traffic is random and sporadic between a large subset of nodes, and where the [source, destination] pairs are changing over time: no additional control traffic need be generated in this situation since routes are maintained for all known destinations at all times. Also, since routes are maintained continuously, traffic is subject to no delays due to buffering/route-discovery. This continued route maintenance may be done using periodic message exchange, as detailed in this specification, or triggered by external events if available. OLSRv2 supports nodes which have multiple interfaces which participate in the MANET. OLSRv2, additionally, supports nodes which have non-MANET interfaces which can serve as (if configured to do so) gateways towards other networks. The message exchange format, contained in previous versions of this specification, has been factored out to an independent specification [3], which is used for carrying OLSRv2 control signals. OLSRv2 is thereby able to allow for extensions via "external" and "internal" extensibility. External extensibility implies that a protocol extension may specify and exchange new message types, formatted according to [3], which can be forwarded and delivered correctly. Internal extensibility implies that a protocol extension may define additional attributes to be carried embedded in the standard OLSRv2 control messages detailed in this specification, using the TLV mechanism specified in [3], while OLSRv2 control messages with additional attributes can still be correctly understood by all OLSRv2 nodes. The OLSRv2 neighborhood discovery protocol using HELLO messages has likewise been factored out to an independent specification [4]. This neighborhood discovery protocol serves to ensure that each OLSRv2 node has available continuously updated information repositories describing the node's 1-hop and 2-hop neighbors. [4] uses the message format specified in [3], and hence is extensible as described above. Clausen, et al. Expires December 28, 2006 [Page 7] Internet-Draft OLSRv2 June 2006 2. Protocol Overview and Functioning OLSRv2 is a proactive routing protocol for mobile ad hoc networks. The protocol inherits the stability of a link state algorithm and has the advantage of having routes immediately available when needed due to its proactive nature. OLSRv2 is an optimization over the classical link state protocol, tailored for mobile ad hoc networks. The main tailoring and optimizations of OLSRv2 are: o periodic, unacknowledged transmission of all control messages; o optimized flooding for global link-state information diffusion; o partial topology maintenance - each node knows only a subset of the links in the network, sufficient for a minimum hop route to all destinations. Using the message exchange format [3] and the neighborhood discovery protocol [4], OLSRv2 also contains the following main components: o a TLV, to be included within the HELLO messages of [4], allowing a node to signal MPR selection; o an optimized flooding mechanism for global information exchange, denoted "MPR flooding"; o a specification of global signaling, denoted TC (Topology Control) messages. TC messages in OLSRv2 serve to: * inject link-state information into the entire network; * inject addresses of hosts and networks for which they may serve as a gateway into the entire network. TC messages are emitted periodically, thereby allowing nodes to continuously track global changes in the network. The use of [4] allows a node to continuously track changes to its local topology up to two hops away. This allows a node to make provisions for ensuring optimized flooding, denoted "MPR flooding", as well as injection of link-state information into the network. This is done through the notion of MultiPoint Relays (MPRs). The idea of MPRs is to minimize the overhead of flooding messages in the network by reducing redundant retransmissions of messages in the same region. Each node in the network selects an MPR Set, a set of nodes in its symmetric 1-hop neighborhood which may retransmit its messages. The 1-hop neighbors of a node which are not in its MPR set Clausen, et al. Expires December 28, 2006 [Page 8] Internet-Draft OLSRv2 June 2006 receive and process broadcast messages, but do not retransmit broadcast messages received from that node. The MPR Set of a node X may be any subset of its symmetric 1-hop neighborhood such that every node in its symmetric strict 2-hop neighborhood has a symmetric link to a node in the MPR Set of node X. The MPR Set of a node may thus be said to "cover" the node's symmetric strict 2-hop neighborhood. The smaller a MPR Set, the fewer times messages are forwarded and the less resulting control traffic overhead. [8] gives an analysis and example of MPR selection algorithms. Note that as long as the condition above is satisfied, any algorithm selecting MPR Sets is acceptable in terms of implementation interoperability. Each node maintains information about the set of symmetric 1-hop neighbors that have selected it as MPR. This set is called the MPR Selector Set of the node. A node obtains this information from an MPR TLV which is inserted into the HELLO message exchange of [4]. Each node also maintains a Relay Set, which is the set of nodes for which a node is to relay broadcast traffic. The Relay Set is derived from the MPR Selector Set in that the Relay Set MUST contain all the nodes in the MPR Selector set and MAY contain additional nodes. Using the MPR flooding mechanism, link-state information can be injected into the network. For this purpose, a node maintains an Advertised Neighbor Set which MUST contain all the nodes in the MPR selector set and MAY contain additional nodes. If the Advertised Neighbor Set of a node is non-empty, it is reported in TC messages generated by that node. If the Advertised Neighbor Set is empty, TC messages are not generated by that node, unless needed for gateway reporting, or for a short period to accelerate the removal of unwanted links. OLSRv2 is designed to work in a completely distributed manner and does not depend on any central entity. The protocol does not require reliable transmission of control messages: each node sends control messages periodically, and can therefore sustain a reasonable loss of some such messages. Such losses may occur frequently in radio networks due to collisions or other transmission problems. OLSRv2 does not require sequenced delivery of messages. Each control message contains a sequence number which is incremented for each message. Thus the recipient of a control message can, if required, easily identify which information is more recent - even if messages have been re-ordered while in transmission. OLSRv2 does not require any changes to the format of IP packets, any existing IP stack can be used as is: OLSRv2 only interacts with routing table management. OLSR sends its control messages using UDP. Clausen, et al. Expires December 28, 2006 [Page 9] Internet-Draft OLSRv2 June 2006 2.1. Protocol Extensibility OLSRv2 uses the neighborhood discovery mechanism of [4], and specifies additionally one message type, TC, and a number of TLVs. All messages exchanged by [4] and by OLSRv2 use and comply with the extensible message exchange format of [3], thus OLSR provides both "external" extensibility (addition of new message types as in OLSRv1 [1]) and "internal" extensibility (addition of information to existing messages through TLVs) as described in [3]. Those nodes which do not recognize a new message type ("external extensibility") will ignore this message type for processing, but will correctly forward the message, if specified in the message header. Those nodes which do not recognize a newly defined TLV type ignore the added TLV, but process (if the message type is recognized) the message correctly, as well as forwards the message, if specified in the message header. Clausen, et al. Expires December 28, 2006 [Page 10] Internet-Draft OLSRv2 June 2006 3. Processing and Forwarding Repositories The following data structures are employed in order to ensure that a message is processed at most once and is forwarded at most once per interface of a node, and that fragmented content is treated correctly. 3.1. Received Set Each node maintains, for each OLSRv2 interface, a set of signatures of messages, which have been received over that interface, in the form of "Received Tuples": (RX_type, RX_orig_addr, RX_seq_number, RX_time) where: RX_type is the received message type, or zero if the received message sequence number is not type-specific; RX_orig_addr is the originator address of the received message; RX_seq_number is the message sequence number of the received message; RX_time specifies the time at which this Received Tuple expires and *MUST* be removed. In a node, this is denoted the "Received Set" for that interface. 3.2. Fragment Set Each node stores messages containing fragmented content until all fragments are received and the message processing can be completed, in the form of "Fragment Tuples": (FG_message, FG_time) where: FG_message is the message containing fragmented content; FG_time specifies the time at which this Fragment Tuple expires and MUST be removed. In a node, this is denoted the "Fragment Set". Clausen, et al. Expires December 28, 2006 [Page 11] Internet-Draft OLSRv2 June 2006 3.3. Processed Set Each node maintains a set of signatures of messages which have been processed by the node, in the form of "Processed Tuples": (P_type, P_orig_addr, P_seq_number, P_time) where: P_type is the processed message type, or zero if the processed message sequence number is not type-specific; P_orig_addr is the originator address of the processed message; P_seq_number is the message sequence number of the processed message; P_time specifies the time at which this Processed Tuple expires and *MUST* be removed. In a node, this is denoted the "Processed Set". 3.4. Forwarded Set Each node maintains a set of signatures of messages which have been retransmitted/forwarded by the node, in the form of "Forwarded Tuples": (FW_type, FW_orig_addr, FW_seq_number, FW_time) where: FW_type is the forwarded message type, or zero if the forwarded message sequence number is not type-specific; FW_orig_addr is the originator address of the forwarded message; FW_seq_number is the message sequence number of the forwarded message; FW_time specifies the time at which this Forward Tuple expires and *MUST* be removed. In a node, this is denoted the "Forwarded Set". 3.5. Relay Set Each node maintains a set of neighbor interface addresses for which it is to relay flooded messages, in the form of "Relay Tuples": Clausen, et al. Expires December 28, 2006 [Page 12] Internet-Draft OLSRv2 June 2006 (RY_iface_addr) where: RY_iface_addr is the address of a neighbor interface for which the node SHOULD relay flooded messages. This MUST include a prefix length. In a node, this is denoted the "Relay Set". Clausen, et al. Expires December 28, 2006 [Page 13] Internet-Draft OLSRv2 June 2006 4. Packet Processing and Message Forwarding On receiving a basic packet, as defined in [3], a node examines each of the message headers. If the message type is known to the node, the message is processed locally according to the specifications for that message type. The message is also independently evaluated for forwarding. 4.1. Actions when Receiving an OLSRv2 Packet On receiving a packet, a node MUST perform the following tasks: 1. The packet may be fully parsed on reception, or the packet and its messages may be parsed only as required. (It is possible to parse the packet header, or determine its absence, without parsing any messages. It is possible to divide the packet into messages without even fully parsing their headers. It is possible to determine whether a message is to be forwarded, and to forward it, without parsing its body. It is possible to determine whether a message is to be processed without parsing its body. It is possible to determine if that processing may be delayed because the message is a fragment by inspecting the first few octets of the message body without fully parsing it.) 2. If parsing fails at any point the relevant entity (packet or message) MUST be silently discarded, other parts of the packet (up to the whole packet) MAY be silently discarded; 3. Otherwise if the packet header is present and it contains a packet TLV block, then each TLV in it is processed according to its type; 4. Otherwise each message in the packet, if any, is treated according to Section 4.2. 4.2. Actions when Receiving an OLSRv2 Message A node MUST perform the following tasks for each received OLSRv2 message: 1. If the received OLSRv2 message header cannot be correctly parsed according to the specification in [3], or if the node recognizes from the originator address of the message that the message is one which the receiving node itself originated, then the message MUST be silently discarded; 2. Otherwise: Clausen, et al. Expires December 28, 2006 [Page 14] Internet-Draft OLSRv2 June 2006 1. If the received message is of a known type then the message is considered for processing according to Section 4.3, AND; 2. If for the received message ( + ) > 1, then the message is considered for forwarding according to Section 4.4. 4.3. Message Considered for Processing If a message (the "current message") is considered for processing, the following tasks MUST be performed: 1. If an entry exists in the Processed Set where: * P_type == the message type of the current message, or 0 if the typedep bit in the message semantics octet (in the message header) of the current message is cleared ('0'), AND; * P_orig_addr == the originator address of the current message, AND; * P_seq_number == the message sequence number of the current message. then the current message MUST NOT be processed. 2. Otherwise: 1. Create an entry in the Processed Set with: + P_type = the message type of the current message, or 0 if the typedep bit in the message semantics octet (in the message header) of the current message is cleared ('0'); + P_orig_addr = originator address of the current message; + P_seq_number = sequence number of the current message; + P_time = current time + P_HOLD_TIME. 2. If the current message does not contain a valid message TLV with Type == FRAGMENTATION (or if it does and the indicated number of fragments is one) then process the message fully according to its type. 3. Otherwise: Clausen, et al. Expires December 28, 2006 [Page 15] Internet-Draft OLSRv2 June 2006 1. If the current message does not contain a valid message TLV with Type == CONT_SEQ_NUM then the current message MUST be silently discarded; 2. Otherwise if the current message is "partially or wholly self-contained", as indicated by the notselfcont bit in the Value field of the TLV with Type == FRAGMENTATION being cleared ('0'), then process the current message as far as possible according to its type; 3. If the Fragment Set includes any Fragment Tuples with: - either the typedepseq bit in the Value field of the TLV with Type == FRAGMENTATION in the current message is cleared ('0') OR message type of FG_message == message type of current message, AND; - originator address of FG_message == originator address of current message, AND; - content sequence number (the Value field of the message TLV with Type == CONT_SEQ_NUM) of FG_message == content sequence number of current message; AND - either fragment number (from the Value field of the TLV with Type == FRAGMENTATION) in FG_message == fragment number of current message OR number of fragments (from the Value field of the TLV with Type == FRAGMENTATION) of FG_message != number of fragments of current message; then remove these Fragment Tuples from the Fragment Set; 4. If the Fragment Set includes Fragment Tuples containing all the remaining fragments of the same overall message as the current message, i.e. if the number of Fragment Tuples such that: - either the typedepseq bit in the Value field of the TLV with Type == FRAGMENTATION in the current message is cleared ('0') OR message type of FG_message == message type of current message, AND; - originator address of FG_message == originator address of current message, AND; - content sequence number (the Value field of the message TLV with Type == CONT_SEQ_NUM) of FG_message Clausen, et al. Expires December 28, 2006 [Page 16] Internet-Draft OLSRv2 June 2006 == content sequence number of current message is equal to (number of fragments of current message, less one) then all of these Fragment Tuples are removed from the Fragment Set and their messages processed according to their type (taking account of any previous processing of any which are partially or wholly self-contained); 5. Otherwise, a Fragment Tuple is added to the Fragment Set with - FG_message = current message; - FG_time = current time + FG_HOLD_TIME; possibly replacing a previously received instance of the same fragment. 4.4. Message Considered for Forwarding If a message is considered for forwarding, and it is either of a message type defined in this document or of an unknown message type, then it MUST use the following algorithm. A message type not defined in this document MAY specify the use of this, or another algorithm. (Such an other algorithm MAY use the Received Set for the receiving interface, it SHOULD use the Forwarded Set similarly to the following algorithm.) If a message is considered for forwarding according to this algorithm, the following tasks MUST be performed: 1. If the sending interface (as indicated by the source interface of the IP datagram containing the message) does not match (taking into account any address prefix of) any N_neighbor_iface_addr in any Symmetric Neighbor Tuple, then the message MUST be silently discarded. 2. Otherwise: 1. If an entry exists in the Received Set for the receiving interface, where: + RX_type == the message type, or 0 if the typedep bit in the message semantics octet (in the message header) is cleared ('0'), AND; + RX_orig_addr == the originator address of the received message, AND; Clausen, et al. Expires December 28, 2006 [Page 17] Internet-Draft OLSRv2 June 2006 + RX_seq_number == the sequence number of the received message. then the message MUST be silently discarded. 2. Otherwise: 1. Create an entry in the Received Set for the receiving interface with: - RX_type = the message type, or 0 if the typedep bit in the message semantics octet (in the message header) is cleared ('0'); - RX_orig_addr = originator address of the message; - RX_seq_number = sequence number of the message; - RX_time = current time + RX_HOLD_TIME. 2. If an entry exists in the Forwarded Set where: - FW_type == the message type, or 0 if the typedep bit in the message semantics octet (in the message header) is cleared ('0'); - FW_orig_addr == the originator address of the received message, AND; - FW_seq_number == the sequence number of the received message. then the message MUST be silently discarded. 3. Otherwise if a Relay Tuple exists whose RY_iface_addr matches (taking into account any address prefix) the sending interface (as indicated by the source interface of the IP datagram containing the message): 1. Create an entry in the Forwarded Set with: o FW_type = the message type, or 0 if the typedep bit in the message semantics octet (in the message header) is cleared ('0'); o FW_orig_addr = originator address of the message; Clausen, et al. Expires December 28, 2006 [Page 18] Internet-Draft OLSRv2 June 2006 o FW_seq_number = sequence number of the message; o FW_time = current time + FW_HOLD_TIME. 2. The message header is modified as follows: o Decrement in the message header by 1; o Increment in the message header by 1; 3. Transmit the message on all OLSRv2 interfaces of the node. Messages are retransmitted in the format specified by [3] with the ALL-MANET-NEIGHBORS address (see Section 16.1) as destination IP address. Clausen, et al. Expires December 28, 2006 [Page 19] Internet-Draft OLSRv2 June 2006 5. Information Repositories The purpose of OLSRv2 is to determine the Routing Set, which may be used to update IP's Routing Table, providing "next hop" routing information for IP datagrams. In order to accomplish this, OLSRv2 uses a number of protocol sets: the Neighborhood Information Base, provided by [4], is in OLSRv2 augmented by information allowing MPR selection and signaling. Additionally, OLSRv2 specifies a Topology Information Base, which describes the information used for and acquired through TC message exchange - in other words: the topology base represents the network topology graph as seen from each node. Addresses (other than originator addresses) recorded in the Neighborhood Information Base and the Topology Information Base MUST all be recorded with prefix lengths, in order to allow comparison with addresses received in HELLO and TC messages. For the Topology Information Base this applies to A_neighbor_iface_addr, T_dest_iface_addr, T_last_iface_addr, AN_net_addr, AN_gw_iface_addr, R_dest_addr, R_dest_addr, R_next_iface_addr and R_local_iface_addr, but not AH_orig_addr. For the Neighborhood Information Base see [4]. 5.1. Neighborhood Information Base The neighborhood information base stores information about links between local interfaces and interfaces on adjacent nodes. In addition to the sets described in [4], OLSRv2 adds an element to each Link Tuple to allow a node to record the willingness of a 1-hop neighbor node to be selected as an MPR. Also, OLSRv2 adds an MPR Set and an MPR Selector Set to the Neighborhood Information Base. The MPR Set is used by a node to record which of its symmetric 1-hop neighbors are selected as MPRs, and the MPR Selector Set is used by a node to record which of its symmetric 1-hop neighbors have selected it as MPR. Thus the MPR Set is used, in addition to what is specified in [4], when generating HELLO messages, and the MPR Selector Set is populated, in addition to what is specified in [4] when processing HELLO messages. 5.1.1. Link Set The Link Tuples, specified in [4] are augmented by an element, L_willingness: L_willingness is the node's willingness to be selected as an MPR; The remaining elements of the Link Tuples are as specified in [4]. Clausen, et al. Expires December 28, 2006 [Page 20] Internet-Draft OLSRv2 June 2006 5.1.2. MPR Set A node maintains a set of all of the OLSRv2 interface addresses with which the node has a symmetric link and which are of 1-hop symmetric neighbors which the node has selected as MPRs. This is denoted the "MPR Set". 5.1.3. MPR Selector Set A node maintains a set of "MPR Selector Tuples" containing all of the OLSRv2 interface addresses with which the node has a symmetric link and which are of 1-hop symmetric neighbors which have selected the node as an MPR. (MS_neighbor_iface_addr, MS_time) MS_neighbor_iface_addr specifies an OLSRv2 interface address with which the node has a symmetric link and which is of a 1-hop symmetric neighbor which has selected the node as an MPR; MS_time specifies the time at which this MPR Selector Tuple expires and *MUST* be removed. In a node, the set of MPR Selector Tuples is denoted the "MPR Selector Set". 5.2. Topology Information Base The Topology Information Base stores information, required for the generation and processing of TC messages. The Advertised Neighbor Set contains OLSRv2 interface addresses of symmetric 1-hop neighbors which are to be reported in TC messages. The Topology Set and Attached Network Set both record information received through TC messages. Thus the Advertised Neighbor Set is used for generating TC messages, while the Topology Set and Attached Network Set are populated when processing TC messages. Additionally, a Routing Set is maintained, derived from the information recorded in the Neighborhood Information Base, Topology Set and Attached Network Set. 5.2.1. Advertised Neighbor Set A node maintains a set of OLSRv2 interface addresses of symmetric 1-hop neighbors, which are to be advertised through TC messages: (A_neighbor_iface_addr) Clausen, et al. Expires December 28, 2006 [Page 21] Internet-Draft OLSRv2 June 2006 For this set, an Advertised Neighbor Set Sequence Number (ANSN) is maintained. Each time the Advertised Neighbor Set is updated, the ANSN MUST be incremented. The ANSN MUST also be incremented if any locally advertised attached networks are added or removed. 5.2.2. ANSN History Set A node records a set of "ANSN History Tuples", recording information about the freshness of the topology information received from each other node: (AH_orig_addr, AH_seq_number, AH_time) AH_orig_addr is the originator address of a received TC message; AH_seq_number is the highest ANSN in any TC message received which originated from AH_orig_addr; AH_time is the time at which this ANSN History Tuple expires and *MUST* be removed. In a node, the set of ANSN History Tuples is denoted the "ANSN History Set". 5.2.3. Topology Set Each node in the network maintains topology information about the network in the form of "Topology Tuples": (T_dest_iface_addr, T_last_iface_addr, T_seq_number, T_time) T_dest_iface_addr is an OLSRv2 interface address of a destination node, which may be reached in one hop from the node with the OLSRv2 interface address T_last_iface_addr; T_last_iface_addr is, conversely, an OLSRv2 interface address of a node which is the last hop on a path towards the node with OLSRv2 interface address T_dest_iface_addr. Typically, the node with OLSRv2 interface address T_last_iface_addr is a MPR of the node with OLSRv2 interface address T_dest_iface_addr; T_seq_number is the highest received ANSN associated with the information contained in this Topology Tuple; T_time specifies the time at which this Topology Tuple expires and *MUST* be removed. In a node, the set of Topology Tuples is denoted the "Topology Set". Clausen, et al. Expires December 28, 2006 [Page 22] Internet-Draft OLSRv2 June 2006 5.2.4. Attached Network Set Each node in the network maintains information about attached networks in the form of "Attached Network Tuples": (AN_net_addr, AN_gw_iface_addr, AN_seq_number, AN_time) AN_net_addr is the network address (including prefix length) of an attached network, which may be reached via the node with the OLSRv2 interface address AN_gw_iface_addr; AN_gw_iface_addr is the address of an OLSRv2 interface of a node which can act as gateway to the network identified by AN_net_addr; AN_seq_number is the highest received ANSN associated with the information contained in this Attached Network Tuple; AN_time specifies the time at which this Attached Network Tuple expires and *MUST* be removed. In a node, the set of Attached Network Tuples is denoted the "Attached Network Set". 5.2.5. Routing Set A node records a set of "Routing Tuples" describing the selected path to each destination in the network for which a route is known: (R_dest_addr, R_next_iface_addr, R_dist, R_local_iface_addr) R_dest_addr is the address of the destination, either the address of an OLSRv2 interface of a destination node, or the network address of an attached network; R_next_iface_addr is the OLSRv2 interface address of the "next hop" on the selected path to the destination; R_dist is the number of hops on the selected path to the destination; R_local_iface_addr is the address of the local interface over which a packet MUST be sent to reach the destination. In a node, the set of Routing Tuples is denoted the "Routing Set". Clausen, et al. Expires December 28, 2006 [Page 23] Internet-Draft OLSRv2 June 2006 6. OLSRv2 Control Message Structures Nodes using OLSRv2 exchange information through messages. One or more messages sent by a node at the same time are combined into a packet. These messages may have originated at the sending node, or have originated at another node and forwarded by the sending node. Messages with different originators may be combined in the same packet. The packet and message format used by OLSRv2 is defined in [3]. However this specification contains some options which are not used by OLSRv2. In particular (using the syntactical elements defined in the packet format specification): o All OLSRv2 packets, not limited to those defined in this document, include a . o All OLSRv2 packets, not limited to those defined in this document, have the pseqnum bit of cleared ('0'), i.e. they include a packet sequence number. o OLSRv2 packets MAY include packet TLVs, however OLSRv2 itself does not specify any packet TLVs. o All OLSRv2 messages, not limited to those defined in this document, include a full and hence have the noorig and nohops bits of cleared ('0'). o All OLSRv2 message defined in this document have the typedep bit, and all reserved bits of cleared ('0'). Other options defined in [3] may be freely used, in particular any other values of or consistent with its specification. OLSRv2 messages are sent using UDP, see Appendix C. The remainder of this section defines, within the framework of [3], message types and TLVs specific to OLSRv2. 6.1. General OLSRv2 Message TLVs This document specifies two message TLVs, which can be applied to any OLSRv2 control messages, VALIDITY_TIME and INTERVAL_TIME. 6.1.1. VALIDITY_TIME TLV All OLSRv2 messages specified in this document MUST include a Clausen, et al. Expires December 28, 2006 [Page 24] Internet-Draft OLSRv2 June 2006 VALIDITY_TIME TLV, specifying a period following receipt of a message, after which the receiving node MUST consider the message content to no longer be valid (unless repeated in a later message). The validity time of a message MAY be specified to depend on the distance from the originator (i.e. the field in the message header as defined in [3]). Thus, a VALIDITY_TIME TLV's value field MAY contain a sequence of pairs (time, hop limit) in increasing hop limit order; it MUST contain a final default value. This is an extended, and compatible, version of the VALIDITY_TIME TLV defined in [4]. Thus, an instance of a VALIDITY_TIME TLV MAY have the following value field: ... .... Which would mean that the message carrying this VALIDITY_TIME TLV would have the following validity times: o in the interval from 0 (exclusive) to (inclusive) hops away from the originator; o in the interval from (exclusive) to (inclusive) hops away from the originator; o in the interval from (exclusive) to 255 (inclusive) hops away from the originator. The VALIDITY_TIME message TLV specification is given in Table 1. +----------------+------+-------------------+-----------------------+ | Name | Type | Length | Value | +----------------+------+-------------------+-----------------------+ | VALIDITY_TIME | TBD | (2*n+1) * 8 bits | {