Internet-Draft J. Ahrenholz Mobile Ad Hoc and OSPF Working Groups T. Henderson Expires: 17 April 2004 P. Spagnolo Boeing E. Baccelli T. Clausen P. Jacquet INRIA 17 October 2003 OSPFv2 Wireless Interface Type draft-spagnolo-manet-ospf-wireless-interface-00 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 17 October 2003 Table of Contents Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 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 . . . . . . . . . . . . . . . . . . . . . 7 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 . . . . . . . . . . . . . . . . . . 9 7. Bringing Up Adjacencies . . . . . . . . . . . . . . . . . . 9 7.1. The Hello Protocol . . . . . . . . . . . . . . . . . . . . 10 7.2. The Synchronization of Databases . . . . . . . . . . . . . 10 7.3. The Designated Router . . . . . . . . . . . . . . . . . . 10 7.4. The Backup Designated Router . . . . . . . . . . . . . . . 10 8. Protocol Packet Processing . . . . . . . . . . . . . . . . . 10 8.1. Sending protocol packets . . . . . . . . . . . . . . . . . 11 8.2. Receiving protocol packets . . . . . . . . . . . . . . . . 11 9. Interface Data Structure . . . . . . . . . . . . . . . . . . 12 9.1. Events causing interface state changes . . . . . . . . . . 12 9.2. Events causing interface state changes . . . . . . . . . . 12 9.3. The Interface state machine . . . . . . . . . . . . . . . 13 9.4. Electing the Designated Router . . . . . . . . . . . . . . 13 9.5. Sending Hello packets . . . . . . . . . . . . . . . . . . 13 9.5.1. Multipoint Relay Selection . . . . . . . . . . . . . . . 13 10. Neighbor Data Structure . . . . . . . . . . . . . . . . . . 15 10.1. Neighbor states . . . . . . . . . . . . . . . . . . . . . 16 10.2. Events causing neighbor state changes . . . . . . . . . . 16 10.3. The Neighbor state machine . . . . . . . . . . . . . . . 16 10.4. Whether to become adjacent . . . . . . . . . . . . . . . 18 Spagnolo et al. [Page 2] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 10.5. Receiving Hello Packets . . . . . . . . . . . . . . . . . 18 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 . . . . . . . . . . . 19 11. Routing Table Structure . . . . . . . . . . . . . . . . . . 19 12. Link State Advertisements . . . . . . . . . . . . . . . . . 19 13. The Flooding Procedure . . . . . . . . . . . . . . . . . . 20 13.1. LSF message generation . . . . . . . . . . . . . . . . . 20 13.2. LSF message processing . . . . . . . . . . . . . . . . . 21 13.3. LSA processing . . . . . . . . . . . . . . . . . . . . . 21 14. Aging the Link State Database . . . . . . . . . . . . . . . 23 15. Virtual Links . . . . . . . . . . . . . . . . . . . . . . . 23 16. Calculation of the routing table . . . . . . . . . . . . . 23 A. OSPF data formats . . . . . . . . . . . . . . . . . . . . . 23 A.1. Wireless Hello packet . . . . . . . . . . . . . . . . . . 23 A.2. Link State Flood (LSF) Packet Format . . . . . . . . . . 25 B. Architectural Constants . . . . . . . . . . . . . . . . . . 25 C. Configurable Constants . . . . . . . . . . . . . . . . . . 26 D. Authentication . . . . . . . . . . . . . . . . . . . . . . 26 E. An algorithm for assigning Link State IDs . . . . . . . . . 26 F. Security Considerations . . . . . . . . . . . . . . . . . . 26 G. References . . . . . . . . . . . . . . . . . . . . . . . . 27 H. Authors' Addresses . . . . . . . . . . . . . . . . . . . . 27 I. IANA Considerations . . . . . . . . . . . . . . . . . . . . 27 Spagnolo et al. [Page 3] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 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 a 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. Finally, the flooding mechanism repeats a new LSA in a multicast on the interface it was received on [Bak02], and uses sequence numbers to avoid flooding duplicates. This OSPFv2 wireless interface type was first Spagnolo et al. [Page 4] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 described in [Hen03]. This draft is organized in parallel with the OSPFv2 RFC [OSPF], for easy comparison. This document, read in conjunction with [OSPF], specifies the wireless interface extension to the basic OSPFv2 protocol. 1.1. Summary of Changes The OSPFv2 wireless interface type has the following key properties: - defines a new Wireless Hello message. The new message adds 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: 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. Spagnolo et al. [Page 5] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 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, LSAs that were not originated by nodes with an interface on that wireless subnet are referred to as outside LSAs. 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 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. Spagnolo et al. [Page 6] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 **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 splitting the AS into areas described in Section 3 of [OSPF]. 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 differences being that it lists the MPRs, it distinguishes between asymmetric and symmetric Spagnolo et al. [Page 7] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 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, and they are not acknowledged. A capability for a subset of LSAs to be reliably flooded is under study. 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. 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. 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. Spagnolo et al. [Page 8] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 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, and the time at which the entry expires. The table should be empty upon initialization. 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. Spagnolo et al. [Page 9] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 7.1. The Hello Protocol The Hello Protocol is responsible for establishing and maintaining neighbor relationships. It also ensures 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 symmetric and asymmetric 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 symmetric 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. 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. Spagnolo et al. [Page 10] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 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. 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. Spagnolo et al. [Page 11] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 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. 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]. Spagnolo et al. [Page 12] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 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. 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 Spagnolo et al. [Page 13] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 reach all symmetric 2-hop neighbors. (Notice that a node, A that is a direct neighbor of another node, B, cannot also be a 2-hop neighbor of node B). This means that the union of the 2-way neighborhoods of the MPR nodes contains the symmetric 2-hop neighborhood. MPR set recalculation should occur when changes are detected in the neighborhood or in the 2-hop neighborhood. While it is not essential that the MPR set is minimal, it is essential that all symmetric 2-hop neighbors can be reached through the selected MPR nodes. A node SHOULD select an MPR set such that any symmetric 2-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 symmetric 2-hop interface (i.e. any interface of a 2-hop neighbor having a 2-way link with a neighbor). The following terminology will be used in describing this algorithm: N: The set of neighbors with which there exists a symmetric link. N2: The set made of the addresses of the symmetric 2-hop neighbor set 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 symmetric 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: Spagnolo et al. [Page 14] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 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 one hop 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. 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 main addresses 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 symmetric 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. Spagnolo et al. [Page 15] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 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 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. Spagnolo et al. [Page 16] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 State(s): Init Event: 2-WayReceived New state: 2-Way Action: The new neighbor state is set to 2-Way. The sym- metric neighbors of the neighbor should be added to the Two Hop Neighbor Table if they are not already symmetric one-hops 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 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: LLDown New state: Down Action: 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 two-hop neighbor table should be cleared. The neighbor should be removed from MPR Selector table if present. Spagnolo et al. [Page 17] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 State(s): 2-Way Event: 1-WayReceived New state: Init Action: 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 symmetric neighbors of the neighbor should be added to the Two Hop Neighbor Table if they are not already symmetric one-hops of the calculating node. If they already are in the table, no change is necessary. In addition, the neighbor should be added to the MPR Selector Table if the cal- culating 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 asymmetric and symmetric neighbors listed in the Wireless Hello. The symmetric 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 symmetric 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 Spagnolo et al. [Page 18] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 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. 10.9. Sending Link State Request Packets Link State Request packets are not sent on wireless interfaces. 11. Routing Table Structure This section defines extensions to Section 11 of [OSPF]. Stub Wireless Network A wireless router (excluding edge routers) MUST add a default route to the routing table when an LSF with the default route bit set is received from an edge router. The default route is set to the edge router's interface on the wireless subnet. The wireless interface address can be found in the edge router's router LSA. 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 Spagnolo et al. [Page 19] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 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 to generate an LSA. 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 sequence number, and expiration time). The LSF MUST be removed from the duplicate table after it expires. LSFs are constructed differently for wireless and edge routers. The two steps below explain the different construction. 1 A self-router LSA should be appended to the LSF for each area associated with the wireless or edge router. If a router's neighbor states have transitioned, since the last LSF send, from 2-Way to below or from below 2-Way to 2-Way then a new self-router LSA should be added. Else, the self-router LSA in the Link State Database (LSDB) should be used. 2 In addition, edge routers must advertise LSAs originated out- side of the wireless network on each wireless interface unless the interface is configured as stub wireless. Spagnolo et al. [Page 20] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 2.1 For stub wireless networks, a large amount of overhead due to propagation of outside LSAs can be avoided. The overhead is reduced by configuring an edge routers wire- less interface as a stub. The stub setting results in the default route bit being set in LSFs originated from the stub wireless interface. The LSF default route bit indicates the path to outside of the wireless network. Only router LSAs are flooded within a stub wireless net- work. 2.2 In transit wireless networks, any LSAs originated by the router should be appended to an LSF. Outside LSAs found in its LSDB should also be appended to an LSF, provided that it is 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. 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 know to be older if the sequence number of the LSF in the ta- ble is greater than the received LSF's sequence number. Stan- dard modulo sequence number comparisons should be applied. 2 Else, the LSF is added to the LSF duplicate table, and the LSAs are processed according to section 13.3. If the LSF's default route bit is set a default route should be added according to Section 11. The LSDB should be cleaned to contain only router LSAs generated from routers in the wireless network. If the sender is in the MPR selector table, the LSF is flooded out all MANET interfaces. 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 Spagnolo et al. [Page 21] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 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 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 those wireless interfaces not defined as stubs. 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. Spagnolo et al. [Page 22] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 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]. 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]. A. 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 A.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 asymmetric neighbors, symmetric neighbors, and MPRs are added, the list of neighbors is Spagnolo et al. [Page 23] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 split into asymmetric followed by symmetric, and a list of MPRs is added. 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | # asym neighb | # sym neighb | # of MPRS | RESERVED | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Asym Neighbor 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Asym Neighbor N | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sym Neighbor 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sym Neighbor N | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | MPR 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | MPR N | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Spagnolo et al. [Page 24] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 A.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 fields contained in an LSU, plus it has a flooding sequence number and a default route flag. 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. The Default route flag "D" is adjacent to the flooding sequence number below and indicates that the originating node is the only access out of the wireless network. 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 |D| Flooding Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | # advertisements | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | +- +-+ | Link state advertisements | +- +-+ | ... | B. Architectural Constants This section defines changes to the architectural constants described in Section B of [OSPF]. There is one additional constant. Spagnolo et al. [Page 25] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 MAX_PACKET_LIFE = 120 seconds C. 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 D. Authentication There are no changes to the authentication procedures described in Section D of [OSPF]. E. 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]. F. Security Considerations There are no additional security considerations beyond those identified in [OSPF]. Spagnolo et al. [Page 26] Internet-Draft OSPFv2 Wireless Interface Type 17 October 2003 G. References [Bak02] Baker, F. et al., "An Outsider's View of MANET" Internet draft: draft-baker-manet-review-01.txt (expired), March 2002. [Bak03] Baker, F. et al., "Problem Statement for OSPF Extensions for Mobile Ad Hoc Routing," Internet draft, draft-baker-manet-ospf- problem-statement-00, work in progress. [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. H. Authors' Addresses {Jeff Ahrenholz, Tom Henderson, Phil Spagnolo}, Boeing Phantom Works, 616 SW 41st Street, Renton, WA, 98055, 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, Thomas.Clausen, Philippe.Jacquet}@inria.fr I. IANA Considerations The following OSPF messages types must be allocated: Message Type Value ------------------------ ----- Wireless HELLO 6 Link State Flood 7