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