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]