Internet-Draft J. Ahrenholz Mobile Ad Hoc and OSPF Working Groups T. Henderson Expires: November 2005 P. Spagnolo Boeing E. Baccelli T. Clausen P. Jacquet INRIA May 12, 2004 OSPFv2 Wireless Interface Type draft-spagnolo-manet-ospf-wireless-interface-01 Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026. 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. Abstract This draft defines enhancements to the OSPFv2 protocol to support a new interface type for wireless, broadcast-capable, multi-hop networks. This interface type uses an unreliable flooding mechanism to distribute LSAs within a wireless subnet. This draft also defines rules for LSA distribution for edge routers that may have a mix of interface types on different subnets. Spagnolo et al. [Page 1] Internet-Draft OSPFv2 Wireless Interface Type May 2004 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1. Summary of Changes . . . . . . . . . . . . . . . . . . . . 5 1.2. Wireless OSPF Terminology . . . . . . . . . . . . . . . . 5 2. The Link State Database . . . . . . . . . . . . . . . . . . 6 2.1. Representation of routers and networks . . . . . . . . . . 6 2.2. The shortest-path tree . . . . . . . . . . . . . . . . . . 7 2.3. Use of external routing information . . . . . . . . . . . 7 2.4. Equal-cost multipath . . . . . . . . . . . . . . . . . . . 7 3. Splitting the AS into Areas . . . . . . . . . . . . . . . . 7 4. Functional Summary . . . . . . . . . . . . . . . . . . . . . 8 4.1. Inter-area routing . . . . . . . . . . . . . . . . . . . . 8 4.2. AS external routes . . . . . . . . . . . . . . . . . . . . 8 4.3. Routing protocol packets . . . . . . . . . . . . . . . . . 8 4.4. Basic implementation requirements . . . . . . . . . . . . 9 4.5. Optional OSPF capabilities . . . . . . . . . . . . . . . . 9 5. Protocol Data Structures . . . . . . . . . . . . . . . . . . 9 6. The Area Data Structure . . . . . . . . . . . . . . . . . . 10 7. Bringing Up Adjacencies . . . . . . . . . . . . . . . . . . 10 7.1. The Hello Protocol . . . . . . . . . . . . . . . . . . . . 10 7.2. The Synchronization of Databases . . . . . . . . . . . . . 10 7.3. The Designated Router . . . . . . . . . . . . . . . . . . 11 7.4. The Backup Designated Router . . . . . . . . . . . . . . . 11 8. Protocol Packet Processing . . . . . . . . . . . . . . . . . 11 8.1. Sending protocol packets . . . . . . . . . . . . . . . . . 11 8.2. Receiving protocol packets . . . . . . . . . . . . . . . . 12 9. Interface Data Structure . . . . . . . . . . . . . . . . . . 12 9.1. Events causing interface state changes . . . . . . . . . . 13 9.2. Events causing interface state changes . . . . . . . . . . 13 9.3. The Interface state machine . . . . . . . . . . . . . . . 13 9.4. Electing the Designated Router . . . . . . . . . . . . . . 13 9.5. Sending Hello packets . . . . . . . . . . . . . . . . . . 14 9.5.1. Multipoint Relay Selection . . . . . . . . . . . . . . . 14 10. Neighbor Data Structure . . . . . . . . . . . . . . . . . . 16 10.1. Neighbor states . . . . . . . . . . . . . . . . . . . . . 16 10.2. Events causing neighbor state changes . . . . . . . . . . 17 10.3. The Neighbor state machine . . . . . . . . . . . . . . . 17 10.4. Whether to become adjacent . . . . . . . . . . . . . . . 19 10.5. Receiving Hello Packets . . . . . . . . . . . . . . . . . 19 Spagnolo et al. [Page 2] Internet-Draft OSPFv2 Wireless Interface Type May 2004 10.6. Receiving Database Description Packets . . . . . . . . . 19 10.7. Receiving Link State Request Packets . . . . . . . . . . 19 10.8. Sending Database Description Packets . . . . . . . . . . 19 10.9. Sending Link State Request Packets . . . . . . . . . . . 20 11. Routing Table Structure . . . . . . . . . . . . . . . . . . 20 12. Link State Advertisements . . . . . . . . . . . . . . . . . 20 13. The Flooding Procedure . . . . . . . . . . . . . . . . . . 20 13.1. LSF message generation . . . . . . . . . . . . . . . . . 20 13.2. LSF message processing . . . . . . . . . . . . . . . . . 21 13.3. LSA processing . . . . . . . . . . . . . . . . . . . . . 22 14. Aging the Link State Database . . . . . . . . . . . . . . . 23 15. Virtual Links . . . . . . . . . . . . . . . . . . . . . . . 24 16. Calculation of the routing table . . . . . . . . . . . . . 24 17. OSPF data formats . . . . . . . . . . . . . . . . . . . . . 24 17.1. Wireless Hello packet . . . . . . . . . . . . . . . . . . 24 17.2. Link State Flood (LSF) Packet Format . . . . . . . . . . 25 18. Architectural Constants . . . . . . . . . . . . . . . . . . 26 19. Configurable Constants . . . . . . . . . . . . . . . . . . 27 20. Authentication . . . . . . . . . . . . . . . . . . . . . . 27 21. An algorithm for assigning Link State IDs . . . . . . . . . 27 22. Multiple interfaces to the same network/subnet . . . . . . 27 23. Security Considerations . . . . . . . . . . . . . . . . . . 27 24. References . . . . . . . . . . . . . . . . . . . . . . . . 27 25. Authors' Addresses . . . . . . . . . . . . . . . . . . . . 28 26. IANA Considerations . . . . . . . . . . . . . . . . . . . . 28 Spagnolo et al. [Page 3] Internet-Draft OSPFv2 Wireless Interface Type May 2004 1. Introduction Wireless, broadcast-capable, multi-hop networks do not effectively map into one of the four traditional OSPF network types (point-to- point, broadcast, NBMA, or Point-to-MultiPoint). Specifically, NBMA, point-to-point, and Point-to-MultiPoint are defined as non-broadcast networks, and operation of non-broadcast interfaces on broadcast- capable networks leads to high overhead. The OSPF broadcast network type assumes full mesh connectivity between all routers on the subnet, but in mobile wireless networks, connectivity may be partial and the Designated Router election protocol may not converge. Some vendors have extended the Point-to-MultiPoint interface type for operation over multicast-capable networks, but the scaling properties due to exponential growth in router adjacencies as the number of nodes increases are undesirable for large networks. Finally, some subnet technologies allow for a "layer-2 routing" that masks the underlying multi-hop nature of the subnet, allowing a traditional broadcast-based OSPF to operate over it at layer-3, but such operation can lead to extra overhead unless neighbor discovery operations are coordinated across layers and partitioning of the layer-2 network is prevented. Although the IETF MANET working group has been working on a set of routing protocols for multi-hop wireless networks, the protocols are not yet comprehensive enough for operation in heterogeneous IP networks. Therefore, if a legacy routing protocol can be adapted to operate over wireless networks, it may speed the path to deployment [Bak03]. This draft defines a new OSPF "wireless" interface type for a network that has the following characteristics: the medium supports true broadcast transmission, link layer messages can be either multicast or unicast, and the pairwise transmission reachability between nodes can be time-varying (sometimes within one hop, and sometimes requiring more than one hop). Mobile ad hoc networks (MANET) are one example of this type of network. The "wireless" interface type has the following characteristics: i) is multicast capable, and uses multicast for an unreliable flooding of Link State Advertisements (LSAs), ii) does not elect a designated router, and iii) does not attempt database synchronization with neighbors. The wireless interface type accomplishes this through the use of a new OSPF message (Link State Flood) that permits a new mechanism for flooding LSAs within a wireless subnet. The wireless interface type also makes use of the concept of Multipoint Relays (MPRs), introduced in the Optimized Link State Routing (OLSR) protocol [OLSR], to reduce flooding overhead. When selected as an MPR, a new LSF that is received is reflooded on the interface it was received on [Bak02], and sequence numbers are used to avoid flooding duplicates. This OSPFv2 wireless interface type was first described Spagnolo et al. [Page 4] Internet-Draft OSPFv2 Wireless Interface Type May 2004 in [Hen03]. This draft is organized in parallel with the OSPFv2 RFC [OSPF], for easy comparison. This document, read in conjunction with [OSPF], completely specifies the wireless interface extension to the basic OSPFv2 protocol. 1.1. Summary of Changes Changes from version 00 to version 01 - Remove default route bit in the LSF for stub wireless net- works. The OSPF totally stubby area can be used instead (Sec- tion 13.1). - Add a non-default option to flood an LSF in the duplicate ta- ble that has not been previously flooded (Section 13.2). Major changes from RFC 2328 to version 00 - defines a new Wireless Hello message. The new message will add an MPR list and eliminate backup and designated router fields; - implements the MPR selection algorithm and rules for reflood- ing LSAs; - efficiently floods LSAs periodically using a Link State Flood (LSF) message; - eliminates the formation of full adjacencies on wireless interfaces; all neighbor states beyond 2-Way are not reached, and no database synchronization is performed; and - includes a mechanism for suppressing the redundant flooding of "outside" LSAs (LSAs originated external to the wireless sub- net). 1.2. Wireless OSPF 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 [5]. The OSPF wireless interface protocol uses the following terminology: Spagnolo et al. [Page 5] Internet-Draft OSPFv2 Wireless Interface Type May 2004 multipoint relay (MPR) A node which is selected by its one-hop neighbor, node X, to re-transmit all the broadcast messages that it receives from X, provided that the same message was not already received, and the time to live field of the mes- sage is greater than one. multipoint relay selector (MPR selector) A node which has selected its one-hop neighbor, node X, as its multipoint relay, is called a multipoint relay selector of node X. edge router A router that has more than one interface and at least one of these interfaces is a wireless interface. wireless router A router that has at least one wireless interface. outside LSAs With respect to a wireless subnet, outside LSAs refer to all LSAs flooded within the area that are not Type 1 LSAs originated by a node with an active interface on that wireless subnet. 2. The Link State Database This section defines extensions to Section 2 of [OSPF]. 2.1. Representation of routers and networks In wireless mode, OSPF treats all router-to-router connections over the broadcast network similar to a multicast-capable Point-to- MultiPoint network. No Designated Router is elected for the network, nor is there an LSA generated for the network. A vertex for the wireless network does not appear in the graph of the link-state database. Figure 2.1.1 illustrates the link-state database representation of a wireless network. On the left side of the figure, a wireless network is pictured. It is assumed that all routers can communicate directly Spagnolo et al. [Page 6] Internet-Draft OSPFv2 Wireless Interface Type May 2004 with their horizontal and vertical neighbors, but not those across the diagonals. I3 through I6 indicate the routers' IP interface addresses on the wireless network. In the graphical representation of the link-state database, routers that can communicate directly over the wireless network are joined by bi-directional edges, and each router also has a stub connection to its own IP interface address. **FROM** +---+ +---+ |RT3| |RT4| |RT3|RT4|RT5|RT6| +---+ +---+ * -------------------- I3| |I4 * RT3| | X | X | | +----------------------+ T RT4| X | | | X | I5| |I6 O RT5| X | | | X | +---+ +---+ * RT6| | X | X | | |RT5| |RT6| * I3| X | | | | +---+ +---+ I4| | X | | | I5| | | X | | I6| | | | X | Figure 2.1.1: Network map components 2.2. The shortest-path tree There is no change to the calculation of the shortest-path tree described in Section 2.2 of [OSPF]. However, since topology dissemination is unreliable, it is possible for two routers in the same Autonomous system to generate dissimilar routing tables. 2.3. Use of external routing information There are no changes to the use of external routing information described in Section 2.3 of [OSPF]. 2.4. Equal-cost multipath There are no changes to the equal-cost multipath described in Section 2.4 of [OSPF]. 3. Splitting the AS into Areas There are no changes to the splitting the AS into areas described in Section 3 of [OSPF]. Spagnolo et al. [Page 7] Internet-Draft OSPFv2 Wireless Interface Type May 2004 4. Functional Summary This section defines extensions to Section 4 of [OSPF]. A router with a wireless interface sends and receives Wireless Hello packets to detect neighbors. A Wireless Hello packet is similar in format to a normal Hello packet, the difference being that it lists the sender\'s MPR selection, it distinguishes between 1-way and 2-way neighbors, and it does not include fields for designated router or backup designated router. The router dynamically detects its neighboring routers by sending its Wireless Hello packets to the multicast address AllSPFRouters. OSPF adjacencies are not formed on wireless networks. Instead, routers keep a table of neighbors who have selected them as a MPR (MPR selectors). The distribution of topology information is performed by flooding link state information (i.e., LSAs) periodically on all wireless interfaces. MPRs are used to more efficiently flood the information. LSAs are flooded in Link State Flood packets, which are similar to Link State Update packets except that they have a monotonically increasing sequence number for use in duplicate detection. 4.1. Inter-area routing There are no changes to the Inter-area routing described in Section 4.1 of [OSPF]. 4.2. AS external routes There are no changes to the AS external routes described in Section 4.2 of [OSPF]. 4.3. Routing protocol packets The additional OSPF packets used on wireless networks are listed below in Table 4.3.1. Their formats are described in Appendix A. Spagnolo et al. [Page 8] Internet-Draft OSPFv2 Wireless Interface Type May 2004 Type Packet name Protocol function ================================================================== 6 Wireless Hello Discover/maintain neighbors and MPRs 7 Link State Flood Database update Table 4.3.1: OSPF packet types. Wireless Hello packets are used to discover and maintain neighbor relationships and inform neighbors of MPR selections. Wireless Hello packets are never forwarded. Each Link State Flood (LSF) packet carries a set of new or old link state advertisements (LSAs) one hop further away from their point of origination. A single Link State Flood packet may contain the LSAs of several routers. LSA types or formats are not changed. Wireless Hello and LSF packets are only sent and received on interfaces configured as wireless. 4.4. Basic implementation requirements There are no changes to the implementation requirements described in Section 4.4 of [OSPF]. 4.5. Optional OSPF capabilities There are no changes to the optional capabilities in Section 4.5 of [OSPF]. 5. Protocol Data Structures This section defines extensions to Section 5 of [OSPF]. LSF duplicate table The Link State Flood duplicate table keeps track of which LSFs have been seen. Each tuple in the table consists of the originator's Router ID, the flooding sequence number, the time at which the entry expires, and a flag that indicates whether the LSF has been flooded. The table should be empty upon initialization. Spagnolo et al. [Page 9] Internet-Draft OSPFv2 Wireless Interface Type May 2004 6. The Area Data Structure There are no changes to the area data structures described in Section 6 of [OSPF]. 7. Bringing Up Adjacencies This section defines extensions to Section 7 of [OSPF]. Two routers with wireless interface types, who discover that they can communicate bi-directionally with one another over the wireless interface, do not attempt to form an OSPF adjacency, nor do they attempt to synchronize their link state databases over the wireless interfaces. The Hello protocol is used to establish bi-directional communication, to move the routers into a neighbor state of 2-Way. Neighbor state 2-Way is the maximum neighbor state obtained on a wireless interface. 7.1. The Hello Protocol The Hello Protocol is responsible for establishing and maintaining neighbor relationships. It also verifies that communication between neighbors is bi-directional. Wireless Hello packets are sent periodically on all wireless interfaces while standard Hello packets are sent on all other interface types. Bi-directional communication is assumed when the router sees itself listed in the neighbor's wireless Hello Packet. Wireless Hello packets are also responsible for informing a node of its 2-way and 1-way two-hop neighbors and neighbors that selected it as MPR. If a router finds that it is selected as MPR then it begins acting as an MPR for the originator of the Hello packet. The current MPR selectors are stored in the MPR Selector table. The 2-way two- hop neighbors found in Hello packet are stored in the Two Hop Neighbor Table and used to select a node's MPR(s). 7.2. The Synchronization of Databases Databases are synchronized in wireless networks by flooding the LSA information periodically. Since the flooding process is unreliable, there is no guarantee that the databases become identical. Spagnolo et al. [Page 10] Internet-Draft OSPFv2 Wireless Interface Type May 2004 7.3. The Designated Router Designated routers are not elected on Wireless networks. 7.4. The Backup Designated Router Backup designated routers are not elected on Wireless networks. 8. Protocol Packet Processing This section defines extensions to Section 8 of [OSPF]. There are no changes to the procedures for sending protocol packets on existing interface types. Routing protocol packets sent on Wireless interfaces are processed nearly the same. The major change is that LSF packets are sent along bi-directional links as opposed to sending LSUs along adjacencies. 8.1. Sending protocol packets On Wireless networks, no adjacencies are formed and link state advertisements are exchanged unreliably. Therefore, Database Description (DD), Link State Requests (LSR), Link State Updates (LSU), and Link State Acknowledgements (LSAck) are not necessary. DD and LSR messages are not needed because they are used to create adjacencies. LSFs are used in place of LSUs to carry LSAs on wireless networks. LSAcks are not needed because routing packets no longer require acknowledgment. The Wireless protocol packet fields are filled in as standard OSPF packets. The destination of Wireless Hello and LSF packets should be AllSPFRouters. For more information on the format of specific Wireless OSPF packet types, consult the sections listed in Table 8.1.1. Type Packet name detailed section (transmit) ========================================================= 6 Wireless Hello Section 9.5 7 Link State Flood Section 13.1 Table 8.1.1 Sections describing Wireless OSPF protocol packet transmission. Spagnolo et al. [Page 11] Internet-Draft OSPFv2 Wireless Interface Type May 2004 8.2. Receiving protocol packets On wireless interfaces, only type 6 and 7 packets may be received. If the packet type is Wireless Hello, it should be further processed by the Hello Protocol (see Section 10.5). For more specific information on processing specific Wireless OSPF packet types, consult the sections listed in Table 8.2.1. The sender of the LSF packet is identified by the IP source address found in the packet's IP header. The originator address found in the LSF packet is not necessarily the sender. If the packet type is LSF then it should be further processed according to Section 13.2. Type Packet name detailed section (receive) ======================================================== 6 Wireless Hello Section 10.5 7 Link State Flood Section 13.2 Table 8.2.1 Sections describing Wireless OSPF protocol packet reception. 9. Interface Data Structure This section defines extensions to Section 9 of [OSPF]. A new type and three additional data structure are added to the interface. Type The Wireless interface type is added to the Type data structure. MPR List Each wireless interface keeps a list of MPRs that were elected. Each entry in the list is the router ID of the selected MPR. MPR Selector Table The MPR Selector table consists of routers that have selected the calculating router as MPR. These router IDs are stored in the table each time a Wireless Hello mes- sage has been received containing this router as a MPR. Table entries have an expiration time that define when the calculating router should remove the MPR Selector. Spagnolo et al. [Page 12] Internet-Draft OSPFv2 Wireless Interface Type May 2004 Outside LSA Table A table of outside LSAs that have been received on the interface within OUTSIDE_LSA_HOLD_TIME time. Each entry in the table should contain the Router ID of the origina- tor, the LSA sequence number, and the expiration time. The table should initially be empty. 9.1. Interface States There are no changes to the interface states in Section 9.1 of [OSPF]. Wireless interfaces will reach a maximum state of point-to- point. 9.2. Events causing interface state changes There are no changes to the interface state changes in Section 9.2 of [OSPF]. 9.3. The Interface state machine The interface state machine has the following addition for the wireless interfaces. State(s): Down Event: InterfaceUp New state: Point-to-Point Action: Start the interval Hello Timer, enabling the periodic sending of Hello packets out the inter- face. Start the interval LSF Timer, enabling the periodic sending of LSF packets out the interface. 9.4. Electing the Designated Router A Designated Router is not elected on a Wireless interface. Spagnolo et al. [Page 13] Internet-Draft OSPFv2 Wireless Interface Type May 2004 9.5. Sending Hello packets Hello messages are sent out of non-wireless interfaces with no change. Wireless Hello messages are modified from standard Hello messages as follows. Every HELLO_INTERVAL a Wireless Hello message is sent out on all wireless interfaces. The format of the Wireless Hello packet is detailed in Appendix A.1. When a Wireless Hello message is sent it is necessary to calculate the neighbors (no change from non-wireless interfaces) and the MPRs (a new step). The MPRs are calculated if the neighbor state has changed since the last MPR calculation by using the algorithm described below and taken from [OLSR]. Otherwise, the MPRs are taken from MPR list. 9.5.1. Multipoint Relay Selection MPRs are used to flood LSF messages from a node into the network while reducing the number of retransmissions that will occur in a region. Thus, the concept of MPR is an optimization of a classical flooding mechanism. Each node in the network selects, independently, its own set of MPRs among its 2-way neighborhood. The MPR set MUST be calculated by a node in such a way that it, through the neighbors in the MPR-set, can reach all nodes, which have a 2-way neighbor relationship with the 2-way neighbors of the node (Notice that a node, A, that is a 2-way neighbor of another node, B, cannot also be considered as a 2-way neighbor of the 2-way neighbors of B during MPR selection). This means that the union of the 2-way neighborhoods of the MPR nodes contains the 2-way two-hop neighborhood. MPR set recalculation should occur when changes are detected in the neighborhood or in the two-hop neighborhood. While it is not essential that the MPR set is minimal, it is essential that all 2-way two-hop neighbors can be reached through the selected MPR nodes. A node SHOULD select an MPR set such that any 2-way two-hop neighbor is covered by at least one MPR node. By default, the MPR set can coincide with the entire 2-way neighbor set. The following specifies a proposed heuristic for selection of MPRs [OLSR]. It constructs an MPR-set that enables it to reach any 2-way two-hop interface (i.e. any interface of a two-hop neighbor having a 2-way link with a neighbor). The following terminology will be used in describing this algorithm: Spagnolo et al. [Page 14] Internet-Draft OSPFv2 Wireless Interface Type May 2004 N: The set of 2-way neighbors of the node. N2: The set made of the addresses of the 2-way neighbors of N, excluding (i) all the nodes in N and (ii) the node performing the computation. D(y): The degree of an one hop neighbor node y (where y is a member of N), is defined as the number of 2-way neighbors of node y, EXCLUDING all the members of N and EXCLUDING the node performing the computation. Poorly covered node: A poorly covered node is a node in N2 which is covered by only one node in N. The proposed heuristic is as follows: 1 Start with an MPR set made of all members of N. 2 Calculate D(y), where y is a member of N, for all nodes in N. 3 Select as MPRs those nodes in N which cover the poorly cov- ered nodes in N2. The nodes are then removed from N2 for the rest of the computation. 4 While there exist nodes in N2 which are not covered by a node in the in the MPR set: 4.1 For each node in N, calculate the reachability, i.e. the number of nodes in N2 which are not yet covered by at least one node in the MPR set, and which are reachable through this 2-way neighbor; 4.2 Select as a MPR the node from the nodes in N which pro- vides reachability to the maximum number of nodes in N2. Spagnolo et al. [Page 15] Internet-Draft OSPFv2 Wireless Interface Type May 2004 In case of multiple nodes providing the same amount of reachability, an implementation MAY select the node as MPR whose D(y) is greater. Remove the nodes from N2 which are now covered by a node in the MPR set. When the MPR set has been computed, all the corresponding router IDs are stored in the MPR Set. 10. Neighbor Data Structure This section defines extensions to Section 10 of [OSPF]. Two Hop Neighbor Table The two hop neighbor table consists of nodes that are two hops away from the calculating node. They are found by tabulating the 2-way neighbors found in the Wireless Hello of the one hop neighbors. The two hop neighbors exclude the calculating node and those that are one hop neighbors. The two hop neighbor table is used to determine which nodes are used as MPRs. 10.1. Neighbor states In an unreliable routing protocol there is no need to maintain adjacencies between routers. Therefore, the number of neighbor states is reduced when using the wireless interface. Neighbor states consist of Down, Init, and 2-Way. The following reviews these states on a wireless interface. Down A node in the Down state is sending Hello messages, but it has not received any Hello messages. Init A node in the Init state is sending Hello messages, and it has received Hello messages from a neighbor but its own address is not seen in the Hello message. 2-Way The 2-Way state is entered when a Hello is received listing it as a neighbor. MPRs are chosen from among Spagnolo et al. [Page 16] Internet-Draft OSPFv2 Wireless Interface Type May 2004 nodes detected to be in this state. 10.2. Events causing neighbor state changes The events causing neighbor state changes are the same as in [OSPF] with one change on wireless interfaces. 2-WayReceived Bi-directional communication has been realized between the two neighboring routers. This is indicated by the router seeing itself in the neighbor's Hello packet. 10.3. Neighbor Data Structure There are no additions to the neighbor state machine. Since there are fewer states on wireless interfaces, namely only the Down, Init, and 2-Way states, many transitions will never occur. However, there are additional steps that must be performed with the two-hop neighbor table. State(s): Init Event: 2-WayReceived New state: 2-Way Action: The new neighbor state is set to 2-Way. The 2-way neighbors of the neighbor should be added to the Two Hop Neighbor Table if they are not already 2-way one-hop neighbors of the calculating node. In addition, the neighbor should be added to the MPR Selector Table if the calculating node is found in the MPR list. If it is already in the table the expiration time should be refreshed. State(s): Any state Event: KillNbr New state: Down Action: The corresponding entry in the two-hop neighbor table should be cleared. The neighbor should be removed from Spagnolo et al. [Page 17] Internet-Draft OSPFv2 Wireless Interface Type May 2004 MPR Selector table if present. Also, the Inactivity Timer is disabled. State(s): Any state Event: LLDown New state: Down Action: The corresponding entry in the two-hop neighbor table should be cleared. The neighbor should be removed from MPR Selector table if present. Also, the Inactivity Timer is disabled. State(s): Any state Event: InactivityTimer New state: Down Action: The corresponding entry in the two-hop neighbor table should be cleared. The neighbor should be removed from MPR Selector table if present. State(s): 2-Way Event: 1-WayReceived New state: Init Action: The corresponding entry in the two-hop neighbor table should be cleared. The neighbor should be removed from MPR Selector table if present. State(s): 2-Way Event: 2-WayReceived New state: No state change. Action: The 2-way neighbors of the neighbor should be added to the Two Hop Neighbor Table if they are not already 2-way one-hop neighbors of the calculating node. If they already are in the table, no change is necessary. In Spagnolo et al. [Page 18] Internet-Draft OSPFv2 Wireless Interface Type May 2004 addition, the neighbor should be added to the MPR Selector Ta- ble if the calculating node is found in the MPR list. If it is already in the table the expiration time should be refreshed. 10.4. Whether to become adjacent No adjacencies are formed on wireless interfaces. 10.5. Receiving Hello Packets The Wireless Hello message processing performs all of the same one- hop neighbor calculations, using the 1-way and 2-way neighbors listed in the Wireless Hello. The 2-way two-hop neighbors found in the Wireless Hello that are not one-hop and are not the calculating node MUST be stored in the two- hop neighbor table. Each entry in the table consists of the two-hop neighbor's Router ID and the receiving interface address. In addition, if the 2-way two-hop neighbor is in the two-hop neighbor table, but it is not found in the Wireless Hello it MUST be removed. Also, the receiving node must look in the MPR list for its own address. If the node finds its own address in the Wireless Hello it enters the neighbor's Router ID into the MPR Selector table, and the expiration time is set to MPR_SELECTOR_HOLD_TIME. 10.6. Receiving Database Description Packets Database Description packets are not received in on wireless interfaces. 10.7. Receiving Link State Request Packets Link State Request packets are not received in on wireless interfaces. 10.8. Sending Database Description Packets Database Description packets are not sent on wireless interfaces. Spagnolo et al. [Page 19] Internet-Draft OSPFv2 Wireless Interface Type May 2004 10.9. Sending Link State Request Packets Link State Request packets are not sent on wireless interfaces. 11. Routing Table Structure There are no changes to the Routing Table Structure described in Section 11 of [OSPF]. 12. Link State Advertisements This section defines extensions to Section 12 of [OSPF]. An LSA constructed for a wireless interface is constructed the same as a LSA on a Point-to-MultiPoint interface. Network LSAs are not generated on wireless interfaces because all nodes in the same subnet are not necessarily one hop away (broadcast network). The only difference between LSA generation for Point-to-Multipoint and wireless interfaces is, that the neighbor state only needs to be in neighbor state 2-way or above in order for an LSA to be generated on a wireless interface. 13. The Flooding Procedure This section defines extensions to Section 13 of [OSPF]. Link State Flood packets provide the mechanism for flooding LSAs on wireless interfaces. A Link State Flood packet may contain any of the distinct LSAs. The LSF is used to flood each LSA one hop further from its point of origination. Unreliable flooding requires a mechanism to update the network periodically, since there is no assurance that all nodes in the network receive the first flood. The periodicity decreases the probability that a node will not receive route information necessary to send data. Therefore, a router LSF is flooded periodically on each wireless interface (no adjacencies are required). 13.1. LSF message generation Each wireless interface originates an LSF every LSF_INTERVAL. Each time a node generates an LSF it MUST increment the flooding sequence number and add the LSF to the duplicate table. In this table, the node records a duplicate tuple: (originator address, flooding Spagnolo et al. [Page 20] Internet-Draft OSPFv2 Wireless Interface Type May 2004 sequence number, expiration time, and flooded flag). The flooded flag is set to TRUE. The LSF MUST be removed from the duplicate ta- ble after it expires. LSFs are constructed differently for wireless and edge routers. The two steps below explain the different construction. 1 A Type 1 router-LSA for the area associated with the wireless or edge router is added to the LSF. If a router's neighbor states have transitioned since the last LSF send (into or out of state 2-Way), or the LS age field reaches the value LSRe- freshTime, then a new instance of the router-LSA should be originated. Otherwise, the existing instance of the router- LSA in the Link State Database (LSDB) should be added to the LSF. 2 In addition, edge routers must advertise LSAs originated out- side of the wireless network on each wireless interface. 2.1 For stub wireless networks (only one edge router), a large amount of overhead due to propagation of outside LSAs can be avoided. The overhead can be reduced by defining the stub wireless network as a totally stubby area. The stub wireless network is defined in Section 12.4.3.1 of [OSPF]. The area border (edge router) will originate a "default summary LSA" into the area to create the default path out of the stub wireless network. 2.2 In transit wireless networks, any outside LSAs that are self-originated by the router but within flooding scope of the area should be appended to an LSF. Examples of these self-originated outside LSAs include summary and external LSAs. In addition, outside LSAs found in a router's LSDB but originated by other routers should also be appended to an LSF, provided that they are not found in the Outside LSA Table maintained for that interface. 13.2. LSF message processing Each incoming LSF is searched for in the duplicate table. Spagnolo et al. [Page 21] Internet-Draft OSPFv2 Wireless Interface Type May 2004 1 If the LSF is a duplicate, or if the LSF is older than the LSF found in the table, the LSF packet is discarded. An LSF is older if the sequence number of the LSF in the table is greater than the received LSF's sequence number. Standard modulo sequence number comparisons should be applied. 1.1 If the sender is in the MPR selector table, but the flooded flag is FALSE in the duplicate table, then the LSF MAY be reflooded out all MANET interfaces. The flooded flag MUST then be set to TRUE in the duplicate table. Note: Flooding when the flooded flag is FALSE will severely decrease the efficiency of the MPR algo- rithm. The flooded flag is only necessary to prevent insufficient flooding when reordering of packets occurs. Under normal operation, reordering due to layer-2 trans- mission schedules is unlikely; therefore, the option should normally be avoided to reduce flooding overhead. 2 Else, the LSF is added to the LSF duplicate table, and the LSAs are processed according to section 13.3. 2.1 If the sender is in the MPR selector table, the LSF is flooded out all MANET interfaces, and the flooded flag is set to TRUE in the duplicate table. 2.2 Else, the flooded flag is set to FALSE in the duplicate table. 13.3. LSA processing LSAs received within an LSF message should be processed and installed in the database in the same way as those received in an LSU, except that they are not acknowledged, nor are they forwarded based on LSA processing. LSAs are not forwarded based on LSA processing because they are (re)flooded based on the LSF processing. See step 2 of LSF message processing above. Outside LSAs MUST be installed in the Out- side LSA table. In this table, the node records a LSA tuple, (origi- nator address, LSA sequence number, and expiration time). The LSA MUST be removed from the Outside LSA table after it expires. If the LSA received within an LSF message is a network LSA, special care should be taken to avoid having more than one LSA in the database describing the same network. This situation could arise due Spagnolo et al. [Page 22] Internet-Draft OSPFv2 Wireless Interface Type May 2004 to a designated router change in an external network that resulted in a MaxAge LSA not being successfully flooded through the wireless net- work. Upon receiving a network LSA, if a network LSA already exists in the database for that network, but from a different originator, the router LSA of that originator should be consulted to determine if that node is still listed as the designated router for that network. If that router LSA does not exist or fails to list a designated router, the router LSA of the originator of the new network LSA should be consulted. In either case, if the network LSA in the database is now incorrect, it should be removed from the database. If a wireless node receives an outside LSA with a sequence number lower than the LSA in the LSDB, and the age of the received LSA is less than the age of the copy in the LSDB then the age of the LSDB must be compared to the MAX_PACKET_LIFE. If the age of the LSA in the LSDB is greater than MAX_PACKET_LIFE, then the received LSA is added to the LSDB and the database copy is removed. If an edge router receives an LSA on a wireless interface originated by a router on the wireless network, the sequence number and age MUST be checked as follows. If the sequence number of the received LSA is lower than the LSA in the LSDB, and the age of the received LSA is less than the age of the copy in the LSDB then the age of the LSA in the LSDB must be compared to the MAX_PACKET_LIFE. If the age of the LSA in the LSDB is greater than MAX_PACKET_LIFE then the LSA in the LSDB MUST be immediately unicast back to the originator of the LSA in an LSF. When the originator of the LSA receives the unicast LSF, it should re-originate the LSA with a sequence number one greater than the received LSA and install it in the LSDB. The new LSA is then again flooded in an LSF packet at the next LSF_INTERVAL. Max-aged LSAs received on an edge router's wired interfaces MUST be flooded on all wireless interfaces in the LSAs scope. When a max- aged LSA is received on a wired interface it should be stored for flooding on the next LSF interval. Optionally, the LSA could be sent out for the next N LSF intervals, so that the likelihood of reception is increased. N can be any integer greater than or equal to one. 14. Aging the Link State Database There are no changes to the procedures regarding aging of the link state database described in Section 14 of [OSPF]. Spagnolo et al. [Page 23] Internet-Draft OSPFv2 Wireless Interface Type May 2004 15. Virtual Links There are no changes to the procedures regarding virtual links described in Section 15 of [OSPF]. 16. Calculation of the routing table There are no changes to the procedures regarding calculation of the routing table described in Section 16 of [OSPF]. 17. OSPF data formats This section defines extensions to Section A of [OSPF]. The wireless network introduces two new packet types-- the Wireless Hello and the Link State Flood (LSF) packet types. The OSPF packet types are as follows (only packet types 6 and 7 are used on the wireless interface): Type Description ---- ----------- 1 Hello 2 Database Description 3 Link State Request 4 Link State Update 5 Link State Acknowledgment 6 Wireless Hello 7 Link State Flood 17.1. Wireless Hello packet Wireless Hello packets are OSPF packet type 6. These packets are sent periodically on all wireless interfaces in order to establish and maintain neighbor relationships. The Wireless Hello packet has been changed from the Hello packet as follows. The version number is 6, the backup and designated router fields are eliminated, fields for the number of 1-way neighbors, 2-way neighbors, and MPRs are added, the list of neighbors is split into 1-way followed by 2-way, and a list of MPRs is added. Spagnolo et al. [Page 24] Internet-Draft OSPFv2 Wireless Interface Type May 2004 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version # | 6 | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Area ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Checksum | AuType | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Network Mask | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | HelloInterval | Options | Rtr Pri | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RouterDeadInterval | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | # 1way neighb | # 2way neighb | # of MPRS | RESERVED | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1way Neighbor 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1way Neighbor N | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 2way Neighbor 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 2way Neighbor N | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | MPR 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | MPR N | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 17.2. Link State Flood (LSF) Packet Format LSF packets are OSPF packet type 7. The LSF message is used in place of the LSU message on wireless interfaces. A LSF contains all of the Spagnolo et al. [Page 25] Internet-Draft OSPFv2 Wireless Interface Type May 2004 fields contained in an LSU, plus it has a flooding sequence number. The flooding sequence number is used to distinguish different instances of the LSF message. Each node keeps a table of LSF messages that have been seen. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version # | 7 | Packet length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Router ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Area ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Checksum | AuType | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Authentication | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Flooding Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | # advertisements | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | +- +-+ | Link state advertisements | +- +-+ | ... | 18. Architectural Constants This section defines changes to the architectural constants described in Section B of [OSPF]. There is one additional constant. MAX_PACKET_LIFE = 120 seconds Spagnolo et al. [Page 26] Internet-Draft OSPFv2 Wireless Interface Type May 2004 19. Configurable Constants This section defines extensions to Section C of [OSPF]. All of the constants defined below are configurable wireless interface parameters. LSF_INTERVAL = 10 seconds WIRELESS_HELLO_INTERVAL = 10 seconds NEIGHBOR_HOLD_TIME = 3 * WIRELESS_HELLO_INTERVAL MPR_SELECTOR_HOLD_TIME = 3 * WIRELESS_HELLO_INTERVAL LSF_DUPLICATE_HOLD_TIME = 3 * LSF_INTERVAL OUTSIDE_LSA_HOLD_TIME = 2 * LSF_INTERVAL 20. Authentication There are no changes to the authentication procedures described in Section D of [OSPF]. 21. An algorithm for assigning Link State IDs There are no changes to the procedures for assigning Link State IDs described in Section E of [OSPF]. 22. Multiple interfaces to the same network/subnet This section defines extensions to Section F of [OSPF]. 23. Security Considerations There are no additional security considerations beyond those identified in [OSPF]. 24. References [Bak02] Baker, F. et al., "An Outsider's View of MANET" Internet draft: draft-baker-manet-review-01.txt (expired), March 2002. Spagnolo et al. [Page 27] Internet-Draft OSPFv2 Wireless Interface Type May 2004 [Bak03] Baker, F. et al., "Problem Statement for OSPF Extensions for Mobile Ad Hoc Routing," Internet draft, draft-baker-manet-ospf- problem-statement-00 (expired), October 2003. [Hen03] Henderson, T. et al., "A Wireless Interface Type for OSPF," Proceedings of 2003 IEEE MILCOM Conference, October 2003. [OLSR] Clausen, T. and P. Jacquet (ed), "Optimized Link State Routing Protocol,", RFC 3626, October 2003. [OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998. 25. Authors' Addresses {Jeff Ahrenholz, Tom Henderson, Phil Spagnolo}, Boeing Phantom Works, 2760 160th Avenue SE Bldg 33-07 Bellevue, WA 98008, USA, Email: {jeffrey.m.ahrenholz, thomas.r.henderson, phillip.a.spagnolo}@boeing.com {Emmanuel Baccelli, Thomas Heide Clausen, Philippe Jacquet}, HIPERCOM INRIA, Rocquencourt BP 105 78153 Le Chesnay Cedex, France, Email: Emmanuel.Baccelli@inria.fr, Thomas.Clausen@computer.org, Philippe.Jacquet@inria.fr 26. IANA Considerations The following OSPF messages types must be allocated: Message Type Value ------------------------ ----- Wireless HELLO 6 Link State Flood 7 Spagnolo et al. [Page 28]