One document matched: draft-chandra-ospf-manet-ext-03.txt
Differences from draft-chandra-ospf-manet-ext-02.txt
OSPF Working Group M. Chandra
Internet-Draft Cisco Systems
Expires: October 23, 2005 April 21, 2005
Extensions to OSPF to Support Mobile Ad Hoc Networking
draft-chandra-ospf-manet-ext-03
Status of this Memo
This document is an Internet-Draft and is subject to all provisions
of Section 3 of RFC 3667. By submitting this Internet-Draft, each
author represents that any applicable patent or other IPR claims of
which he or she is aware have been or will be disclosed, and any of
which he or she become aware will be disclosed, in accordance with
RFC 3668.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on October 23, 2005.
Copyright Notice
Copyright (C) The Internet Society (2005).
Abstract
This document describes extensions to OSPF to support mobile ad hoc
networking. Specifically, the document specifies a mechanism for
link-local signaling, a OSPF-MANET interface, a simple technique to
reduce the size of Hello packets by only transmitting incremental
state changes, and a method for optimized flooding of routing
updates.
Chandra Expires October 23, 2005 [Page 1]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . 4
1.2 Motivation for extending OSPF to support MANETs . . . . . 5
2. Specification of Requirements . . . . . . . . . . . . . . . 5
3. Proposed Enhancements . . . . . . . . . . . . . . . . . . . 5
3.1 Link Local Signaling . . . . . . . . . . . . . . . . . . . 7
3.1.1 The L Option Bit . . . . . . . . . . . . . . . . . . . 8
3.1.2 LLS Data Block . . . . . . . . . . . . . . . . . . . . 8
3.1.3 LLS TLVs . . . . . . . . . . . . . . . . . . . . . . . 8
3.1.4 Extended Options TLV . . . . . . . . . . . . . . . . . 9
3.1.5 Compatibility Issues . . . . . . . . . . . . . . . . . 9
3.2 OSPF-MANET Interface . . . . . . . . . . . . . . . . . . . 9
3.2.1 Interface Operation . . . . . . . . . . . . . . . . . 10
3.2.2 LSA Formats and Examples . . . . . . . . . . . . . . . 10
3.3 Incremental OSPF-MANET Hellos . . . . . . . . . . . . . . 14
3.3.1 The I Option Bit . . . . . . . . . . . . . . . . . . . 14
3.3.2 State Check Sequence TLV . . . . . . . . . . . . . . . 15
3.3.3 Neighbor Drop TLV . . . . . . . . . . . . . . . . . . 16
3.3.4 'Request From' TLV (RF-TLV) . . . . . . . . . . . . . 16
3.3.5 Full State For TLV (FSF-TLV) . . . . . . . . . . . . . 16
3.3.6 Neighbor Adjacencies . . . . . . . . . . . . . . . . . 17
3.3.7 Sending Hellos . . . . . . . . . . . . . . . . . . . . 18
3.3.8 Receiving Hellos . . . . . . . . . . . . . . . . . . . 19
3.3.9 Interoperability . . . . . . . . . . . . . . . . . . . 21
3.3.10 Support for OSPF Graceful Restart . . . . . . . . . 21
3.4 Optimized Flooding (Overlapping Relays) . . . . . . . . . 21
3.4.1 Operation Overview . . . . . . . . . . . . . . . . . . 22
3.4.2 Determination of Overlapping Relays . . . . . . . . . 22
3.4.3 Terminology . . . . . . . . . . . . . . . . . . . . . 23
3.4.4 Overlapping Relay Discovery Process . . . . . . . . . 23
3.4.5 The F Option Bit . . . . . . . . . . . . . . . . . . . 24
3.4.6 Active Overlapping Relay Extension . . . . . . . . . . 24
3.4.7 Willingness TLV . . . . . . . . . . . . . . . . . . . 26
3.4.8 Flooding and Relay Decisions . . . . . . . . . . . . . 26
3.4.9 Intelligent Transmission of Link State
Acknowledgements . . . . . . . . . . . . . . . . . . . 28
3.4.10 Important Timers . . . . . . . . . . . . . . . . . . 28
3.4.11 Miscellaneous Protocol Considerations . . . . . . . 29
3.4.12 Interoperability . . . . . . . . . . . . . . . . . . 30
3.5 New Bits in OSPFv3 Option Field . . . . . . . . . . . . . 30
4. Security Considerations . . . . . . . . . . . . . . . . . . 30
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . 31
6. Draft Change History . . . . . . . . . . . . . . . . . . . . 31
7. Intellectual Property . . . . . . . . . . . . . . . . . . . 32
8. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 32
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 33
Chandra Expires October 23, 2005 [Page 2]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 33
10.1 Normative References . . . . . . . . . . . . . . . . . . 33
10.2 Informative References . . . . . . . . . . . . . . . . . 34
Author's Address . . . . . . . . . . . . . . . . . . . . . . 34
Intellectual Property and Copyright Statements . . . . . . . 35
Chandra Expires October 23, 2005 [Page 3]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
1. Introduction
Mobile Ad Hoc Networks have been an area of study for some time,
within various working groups and areas within the IETF, various
Military branches, and various government agencies. Recently,
networks with mobile ad hoc requirements are being proposed and
seriously considered for deployment in the near term, which means the
concepts and research now needs to be applied to deployed networks.
Towards that end, this draft applies many of the principles and
concepts learned through prior work to [OSPFv3], along with new
concepts based on current requirements.
1.1 Problem Statement
MANETs are synonymous with packet radio networks, which have been
around since the 1960s in a limited military capacity. With the boom
of mobile devices and wireless communications, MANETs are finding
scope in commercial and military environments. The aim of these
networks is to support robust and efficient communication in a mobile
wireless network by incorporating routing functionality into mobile
nodes.
A MANET is an autonomous set of nodes distributed over a wide
geographical area that communicate over bandwidth-constrained
wireless links. Each node may represent a transmitter, receiver, or
relay station with varying physical capabilities. Packets may
traverse through several intermediate (relay) nodes before reaching
their destination. These networks typically lack infrastructure:
nodes are mobile, there is no central hub or controller, and thus
there is no fixed network topology. Moreover, MANETs must contend
with a difficult and variable communication environment. Packet
transmissions are plagued by the usual problems of radio
communication, which include propagation path loss, signal multipath
and fading, and thermal noise. These effects vary with terminal
movement, which also induces Doppler spreading in the frequency of
the transmitted signal. Finally, transmissions from neighboring
terminals, known as multi-access interference, hostile jammers, and
impulsive interference, e.g., ignition systems, generators, and other
non-similar in-band communications, may contribute additional
interference.
Given this nature of MANETs, the existence of a communication link
between a pair of nodes is a function of their variable link quality,
including signal strength and bandwidth. Thus, routing paths vary
based on environment, and the resulting network topology. In such
networks, the topology may be stable for periods of time, and then
suddenly become unpredictable. Since MANETs are typically
decentralized systems, there are no central controllers or specially
Chandra Expires October 23, 2005 [Page 4]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
designated routers to determine the routing paths as the topology
changes. All of the routing decisions and forwarding (relaying) of
packets must be done by the nodes themselves, and communication is on
a peer-to-peer basis.
1.2 Motivation for extending OSPF to support MANETs
The motivation to extend a standard protocol, OSPF (described in
[OSPF] and [OSPFv3]) to operate on MANET networks is twofold. The
primary reason is for interoperability--MANET devices need to be able
to work when plugged into a wireline network in as many cases as
possible. The junction point between a MANET and wire-line network
should also be as fluid as possible, allowing a MANET network to
"plug in" to just about any location within a wire-line network, and
find connectivity, etc., as needed.
While routes could be redistributed between two routing protocols,
one designed just for wire-line networks, and the other just for
MANET networks, this adds complexity and overhead to the MANET/
wireline interface, increases the odds of an error being introduced
between the two domains, and decreases flexibility.
The second motivation is that OSPF is a well understand and widely
deployed routing protocol. This provides a strong basis of
experience and skills from which to work. A protocol which is known
to work can be extended, rather than developing a new protocol, which
must then be completely troubleshoot, tested, and modified over a
number of years. Working with a well known protocol allows
development effort to be placed in a narrowly focused area, rather
than rebuilding, from scratch, many things which are already known to
work.
2. Specification of Requirements
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
3. Proposed Enhancements
This document proposes modifications to [OSPFv3] to support mobile ad
hoc networks (MANETs). Note that it is possible to use the mechanism
defined in Section "Incremental OSPF-MANET Hellos" and the mechanism
defined in Section "Optimized Flooding (Overlapping Relays)"
independently of one another.
The challenges with deploying standard [OSPFv3] in a MANET
environment fit into two categories. First, traditional link-state
Chandra Expires October 23, 2005 [Page 5]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
routing protocols are designed for a statically configured
environment. As a result, most of the configuration is done manually
when a new router is placed in the network. Thus, OSPF will not
function in an environment where routers interconnect and disconnect
in somewhat random topologies and combinations. There are
modifications that must be made in order for routers running the same
protocol to communicate in a heterogeneous and dynamic environment.
Second, a MANET network must transmit more state information to
maintain reachability. Therefore, OSPF will need scalability
enhancements to support MANETs.
Currently there is no defined interface type that describes a
wireless network. Wireless links have characteristics of both multi-
access and point-to-multipoint links. Treating wireless links as
multi-access does not take into account that not all nodes on the
same Layer 2 link have bi-directional connectivity. However, any
transmission on a link will reach nodes that are within transmission
range. In this way, the link is multi-access due to the fact that
two simultaneous transmissions may collide. A new interface type
needs to be defined in order to accurately describe this behavior.
The second category of challenges fall into is scalability. While
some flooding optimizations are present in OSPF, such as designated
router (DR) election, many of these were built under the assumption
of a true multi-access network. Wireless networks are not true
multi-access because it cannot be assumed that there is two-way
connectivity between everyone on the same Layer 2 link. Therefore,
optimizations such as DR election will not perform correctly in MANET
networks. Without any further optimizations in link-state flooding,
current OSPF would not be able to operate in a highly dynamic
environment in which links are constantly being formed and broken.
The amount of information that would need to be flooded would
overload the network.
Another scalability issue is the periodic transmission of Hello
messages. Currently, even if there are no changes in a router's
neighbor list, the Hello messages still list all the neighbors on a
particular link. For a MANET router, where saving bandwidth and
transmission power is a critical issue, the transmission of
potentially large Hello messages is particularly wasteful.
Finally, current routing protocols will form a neighbor relationship
with any router on a Layer 2 link that is correctly configured. For
MANET routers in a wireless network, this may lead to an excessive
number of parallel links between two routers if communication is
achieved via multiple interfaces. In a statically configured
network, this is not a problem, since the physical topology can be
built to prevent excessive redundancy. However, in a dynamic
Chandra Expires October 23, 2005 [Page 6]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
network, there must exist additional mechanisms to prevent too many
redundant links. (Note that links between two nodes on different
radio types, different antenna, different channels, etc., are
considered different links and not redundant links.) In scalability
tests, it has been demonstrated that the presence of too many
redundant links will increase both the size of routing updates and
cause extra flooding resulting in even relatively small networks not
converging.
3.1 Link Local Signaling
Link Local signaling (LLS) describes a modification to [OSPFv3] to
support exchanging arbitrary data on a link, and is designed
analogously to the LLS for [OSPF] described in [LLS]. OSPFv3 packet
formats are not flexible to introduce new information needed to be
exchanged among neighbors on a link. This section proposes a Type/
Length/Value (TLV) style data block which is capable of carrying
future extension data.
To perform LLS, OSPFv3 routers add a special data block at the end of
OSPFv3 packets. The length of the LLS block is not included in the
OSPFv3 packet length field, but is included in the IP packet length,
as illustrated below.
+---------------------+ --
| IPv6 Header | ^
| Length = HL+X+Y | | Header Length
| | v
+---------------------+ --
| OSPFv3 Header | ^
| Length = X | |
|.....................| | X
| | |
| OSPFv3 Data | |
| | v
+---------------------+ --
| | ^
| LLS Data | | Y
| | v
+---------------------+ --
The LLS data block may be attached to OSPFv3 Hello and Database
Descriptor (DD) packets. The data included in LLS block attached to
a Hello packet may be used for dynamic signaling, since Hello packets
may be sent at any moment in time. However, delivery of LLS data in
Hello packets is not guaranteed. The data sent with DD packets is
guaranteed to be delivered as soon as the adjacency proceeds.
Chandra Expires October 23, 2005 [Page 7]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
This document does not specify how the data transmitted by the LLS
mechanism should be interpreted by OSPFv3 routers. The interface
between OSPFv3 LLS component and its clients is implementation
specific.
3.1.1 The L Option Bit
A new bit, called L (L stands for LLS) is introduced to OSPFv3
Options field. Routers set the L bit in Hello and DD packets to
indicate that the packet contains LLS data block. See Section "New
Bits in OSPFv3 Options Field" for the placement of the L bit in the
OSPFv3 Options Field.
The L bit is set only in Hello and DD packets. It is not set in
OSPFv3 LSAs and may be used in them for different purposes.
3.1.2 LLS Data Block
The data block used for LLS is described below.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Checksum | LLS Data Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| LLS TLVs |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
o The Checksum field contains the standard IP checksum of the entire
contents of the LLS block.
o The 16-bit LLS Data Length field contains the length (in 32-bit
words) of the LLS block including the header and payload. Imple-
mentations should not use the Length field in the IP packet header
to determine the length of the LLS data block.
o The rest of the block contains a set of Type/Length/Value (TLV)
triplets as described in the LLS TLVs section. All TLVs must be
32-bit aligned (with padding if necessary).
3.1.3 LLS TLVs
The LLS data block is constructed using TLVs. Any TLV that is not
understood MUST be silently discarded.
The type field contains the TLV ID which is unique for each type of
TLVs. The Length field contains the length of the Value field (in
bytes) that is variable and contains arbitrary data.
Chandra Expires October 23, 2005 [Page 8]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Note that TLVs are always padded to 32-bit boundary, but padding
bytes are not included in TLV Length field (though it is included in
the LLS Data Length field of the LLS block header). Note that the
value of 0 is reserved.
3.1.4 Extended Options TLV
This subsection describes a TLV called Extended Options (EO) TLV.
The format of EO-TLV is shown below.
Bits in the Value field do not have any semantics from the point of
view of LLS mechanism. This field may be used to announce some
OSPFv3 capabilities that are link-specific. Also, other OSPFv3
extensions may allocate bits in the bit vector to perform boolean
LLS.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Extended Options |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
o Type: Set to 1.
o Length: Set to 4.
o Extended Options: A Bit Map
Only one EO-TLV should appear in the LLS data block.
3.1.5 Compatibility Issues
The modifications to OSPFv3 packet formats are compatible with
standard OSPFv3, because LLS-incapable routers will not consider the
extra data after the packet.
3.2 OSPF-MANET Interface
Interfaces are defined as the connection between a router and one of
its attached networks [OSPF]. Four types of interfaces have been
Chandra Expires October 23, 2005 [Page 9]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
defined and supported in [OSPF] and [OSPFv3]: broadcast, NBMA, point-
to-point, and point-to-multipoint.
Point-to-multipoint model has been chosen to represent MANET
interfaces. (The features designed in this document MAY be included
on other interface types as appropriate.) The MANET interface allows
the following:
o OSPF treats all router-to-router connections over the MANET
interface as if they were point-to-point links.
o Link metric can be set on a per neighbor basis.
o Broadcast and multicast can be accomplished through Layer-2
broadcast or Layer-2 pseudo-broadcast.
* The MANET interface supports Layer-2 broadcast if it is able to
address a single physical message to all of the attached
neighbors. One such example is 802.11.
* The MANET interface supports Layer-2 pseudo-broadcast if it is
able to pick up a packet from the broadcast queue, replicate
the packet, and send a copy over each point-to-point link. One
such example is Frame Relay.
o An API must be provided for Layer-3 to determine the layer-2
broadcast capability. Based on the return of the API, OSPF
classifies the MANET interfaces into the following three types:
MANET broadcast, MANET pseudo-broadcast, and MANET non- broadcast.
o Multicast SHOULD be used for OSPF packets. When the MANET
interface supports Layer-2 broadcast or pseudo-broadcast, the
multicast process is transparent to OSPF. Otherwise, OSPF MUST
replicate multicast packets by itself.
3.2.1 Interface Operation
A MANET node has at least one MANET interface. MANET nodes can
communicate with each other through MANET interfaces. MANET nodes
can communicate with non-MANET routers only through normal
interfaces, such as Ethernet, ATM and etc.
For scalability reasons, it is NOT REQUIRED to configure IPv6 global
unicast addresses on MANET interfaces. Instead, a management
loopback interface, with an IPv6 global unicast address, MAY be
configured on each MANET node.
The LSAs associated with a MANET interface SHOULD have the DC-bit set
in the OSPFv3 Options Field and the DoNotAge bit set in the LS Age
field as described in [OSPFv3].
3.2.2 LSA Formats and Examples
LSA formats are specified in [OSPFv3].
Chandra Expires October 23, 2005 [Page 10]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
In order to display example LSAs, a network map is included below.
Router names are prefixed with the letters RT, network names with the
letter N, and router interface names with the letter I.
o Four MANET nodes, RT1, RT2, RT3, and RT4, reside in area 2.
o RT1 has one MANET interface I11. Through the interface, RT1 is
full adjacent to RT2, RT3, and RT4.
o RT2 has two MANET interfaces, I21 and I22, and one Ethernet
interface I23. RT2 is full adjacent to RT1 and RT4 through the
interface I21, and full adjacent to RT4 through the interface I22.
Stub network N1 is attached with RT2 through the interface I23.
o RT3 has one MANET interface I31, and is full adjacent to RT1
through the interface.
o RT4 has two MANET interfaces, I41 and I42. It is full adjacent to
RT2 through the interface I41, and full adjacent to RT1 and RT2
through the interface I42.
o Moreover, each MANET node is configured with a management loop-
back interface.
+---+I11 I21+---+I23 |
|RT1|-+----------+-|RT2|------|N1
+---+ | | +---+ |
| | VI22
| | +
| | |
| | |
| | |
| | |
| | +
| | ^I41
+---+ | +---+
|RT3|-+ +-|RT4|
+---+I31 I42+---+
The assignment of IPv6 global unicast prefixes to network links is
shown below. (Note: No IPv6 global unicast addresses are configured
on the MANET interfaces)
Chandra Expires October 23, 2005 [Page 11]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
Node Interface IPv6 global unicast prefix
-----------------------------------------------------------
RT1 LOOPBACK 5f00:0001::/64
I11 n/a
RT2 LOOPBACK 5f00:0002::/64
I21 n/a
I22 n/a
I23 5f00:0012::/60
RT3 LOOPBACK 5f00:0003::/64
I31 n/a
RT4 LOOPBACK 5f00:0004::/64
I41 n/a
I42 n/a
The OSPF interface IDs and the link local addresses for the router
interfaces in the network illustrated above below. EUIxy represents
the 64-bit interface identifier of the interface Ixy, in Modified
EUI-64 format [IPV6ADD].
Node Interface Interface ID Link Local address
-----------------------------------------------------------
RT1 LOOPBACK 1 n/a
I11 2 fe80:0002::EUI11
RT2 LOOPBACK 1 n/a
I21 2 fe80:0002::EUI21
I22 3 fe80:0003::EUI22
I23 4 fe80:0004::EUI23
RT3 LOOPBACK 1 n/a
I31 2 fe80:0002::EUI31
RT4 LOOPBACK 1 n/a
I41 2 fe80:0002::EUI41
I42 3 fe80:0003::EUI42
3.2.2.1 Router LSAs
As an example, consider the router LSAs that node RT2 would
originate. Two MANET interfaces, consisting of 3 point-to-point
links, are presented.
Chandra Expires October 23, 2005 [Page 12]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
RT2's router-LSA
LS age = DoNotAge+0 ;newly originated
LS type = 0x2001 ;router-LSA
Link State ID = 0 ;first fragment
Advertising Router = 192.1.1.2 ;RT2's Router ID
bit E = 0 ;not an AS boundary router
bit B = 0 ;not an area border router
Options = (V6-bit|E-bit|R-bit)
Type = 1 ;p2p link to RT1 over I21
Metric = 10 ;cost to RT1
Interface ID = 2 ;Interface ID of I21
Neighbor Interface ID = 2 ;Interface ID of I11
Neighbor Router ID = 192.1.1.1 ;RT1's Router ID
Type = 1 ;p2p link to RT4 over I21
Metric = 25 ;cost to RT4
Interface ID = 2 ;Interface ID of I21
Neighbor Interface ID = 3 ;Interface ID of I42
Neighbor Router ID = 192.1.1.4 ;RT4's Router ID
Type = 1 ;p2p link to RT4 over I22
Metric = 15 ;cost to RT4
Interface ID = 3 ;Interface ID of I22
Neighbor Interface ID = 2 ;Interface ID of I41
Neighbor Router ID = 192.1.1.4 ;RT4's Router ID
3.2.2.2 Link LSAs
A MANET node originates a separate Link-LSA for each attached
interface. As an example, consider the Link-LSA that RT3 will build
for its MANET interface I31.
RT3's Link-LSA for MANET interface I31
LS age = DoNotAge+0 ;newly originated
LS type = 0x0008 ;Link-LSA
Link State ID = 2 ;Interface ID of I31
Advertising Router = 192.1.1.3 ;RT3's Router ID
Rtr Pri = 1 ;default priority
Options = (V6-bit|E-bit|R-bit)
Link-local Interface Address = fe80:0002::EUI31
# prefixes = 0 ;no global unicast address
3.2.2.3 Intra Area Prefix LSAs
A MANET node originates an intra area prefix LSA to advertise its own
prefixes, and those of its attached stub links. As an example,
Chandra Expires October 23, 2005 [Page 13]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
consider the intra area prefix LSA that RT2 will build.
RT2's intra area prefix LSA for its own prefixes
LS age = DoNotAge+0 ;newly originated
LS type = 0x2009 ;intra area prefix LSA
Link State ID = 177 ;or something else
Advertising Router = 192.1.1.2 ;RT2's Router ID
# prefixes = 2
Referenced LS type = 0x2001 ;router LSA reference
Referenced Link State ID = 0 ;always 0 for router-LSA
;reference
Referenced Advertising Router = 192.1.1.2
;RT2's Router ID
PrefixLength = 64 ;prefix on RT2's LOOPBACK
PrefixOptions = 0
Metric = 0 ;cost of RT2's LOOPBACK
Address Prefix = 5f00:0002::
PrefixLength = 60 ;prefix on I23
PrefixOptions = 0
Metric = 10 ;cost of I23
Address Prefix = 5f00:0012:: ;pad to 64-bit
Note: MANET nodes may originate Intra-Area-Prefix-LSAs for attached
transit (broadcast/NBMA) networks. This is normal behavior defined
in [OSPFv3], which is irrelevant to MANET interfaces. Please consult
[OSPFv3] for details.
3.3 Incremental OSPF-MANET Hellos
In MANETs, reducing the size of periodically transmitted packets can
be very important in decreasing the total amount of overhead associ-
ated with routing. Towards this end, removing the list of neighbors
from Hello packets unless that information changes can reduce routing
protocol overhead. While the reduction for each hello packet is
small, over time it will be significant.
A new option bit is defined in this document to facilitate the
operation of incremental Hello packets. A new SCS-TLV and Neighbor
Drop TLV are also defined, transmitted using the LLS technique
described in the "Link Local Signaling" Section.
3.3.1 The I Option Bit
A new I bit is defined in the OSPFv3 option field. The bit is
defined for Hello packets and indicates that only incremental
information is present. See Section "New Bits in OSPFv3 Options
Field" for placement of the I bit within the OSPFv3 options field.
Chandra Expires October 23, 2005 [Page 14]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
3.3.2 State Check Sequence TLV
A new TLV is defined that indicates the current state, which is
represented by an State Check Sequence (SCS) number of the
transmitting router.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SCS Number |R|FS|N | Reserved |
+-----------------------------------------------------------------+
o Type: Type, set to 2.
o Length: Set to 4.
o SCS Number: A circular two octet unsigned integer indicating the
current state of the transmitting device. Note that when the
incremental Hello mechanism is invoked (or re-started), an initial
SCS value of '1' SHOULD be used for the first incremental Hello
packet. This sequence number is referred to as InitialSCS. Note
that InitialSCS also implies a full state.
o R: Request bit. If set, this is a request for current state. The
list of routers who should respond to this request are listed in
the 'Request From' TLV defined below. If the 'Request From' TLV
is not present, it is assumed that the request is meant for all
nodes.
o FS: Full State bit. If set, the Hello packet contains full state
as far as the neighbor(s) in the 'Full State For' TLV (defined
below) are concerned. If the 'Full State For' TLV is not present,
the Hello packet contains full state for all neighbors.
o N: InComplete bit. If NOT set, the complete state associated with
the SCS number is included in the Hello packet. If set, indicates
that the appended TLVs are being sent 'persistently', and that
there is more state associated with the SCS number that was sent
originally, but is not included in this Hello packet. This bit
allows any desired TLVs to be sent 'persistently' for a number of
Hellos with the same SCS number without requiring all of the TLVs
associated with that SCS number to be transmitted. The first time
an SCS number is sent, the entire state associated with that SCS
number is transmitted, and the 'N' bit MUST NOT be set.
o Reserved: Set to 0. Reserved for future use.
A Hello with the State Check Sequence TLV appended with the R bit set
will be referred to as a Hello request.
Chandra Expires October 23, 2005 [Page 15]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
3.3.3 Neighbor Drop TLV
A new TLV is defined in this document which indicates neighbor(s)
that have been removed from the list of known neighbors.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Dropped Neighbor(s) |
+---------------------------------------------------------------+
| ....
+--------------------
o Type: Type, set to 3.
o Length: Set to the number of dropped neighbors included in the TLV
multiplied by 4.
o Dropped Neighbor(s) - Router ID of the neighbor being dropped.
3.3.4 'Request From' TLV (RF-TLV)
A new TLV is defined in this document which indicates neighbor(s)
from which the latest Hello state is being requested.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Request From Neighbor(s) |
+---------------------------------------------------------------+
| ....
+--------------------
Type: set to 4
Length: Set to the number of neighbors included in the TLV
multiplied by 4.
Request From Neighbor(s) - Router ID of the neighbor(s) from which
Hello state is being requested.
3.3.5 Full State For TLV (FSF-TLV)
A new TLV is defined in this document which indicates neighbor(s) to
which the transmitting node is responding with full state.
Chandra Expires October 23, 2005 [Page 16]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Full State For Neighbor(s) |
+---------------------------------------------------------------+
| ....
+--------------------
o Type: set to 5
o Length: Set to the number of neighbors included in the TLV
multiplied by 4.
o Full State For Neighbor(s) - Router ID of the neighbor(s) should
process this packet.
3.3.6 Neighbor Adjacencies
This section describes building neighbor adjacencies and the failure
of such adjacencies using the incremental Hello signaling.
3.3.6.1 Building Neighbor Adjacencies
Hello packets are sent periodically in accordance with [OSPF] and
[OSPFv3]. An OSPF implementation which supports sending only partial
neighbor information in Hello packets SHOULD always set the I bit in
its transmitted Hello packets, except as described elsewhere in this
document. Hello packets MAY be suppressed from being transmitted
every HelloInterval if other packet transmissions are sent by the
router during that time.
On receiving a Hello packet from a new neighbor (in this context, a
new neighbor is a neighbor in less than Init state as defined in
Section 10.1 [OSPF]), if the Hello has the I bit set, a router will:
o Place the new neighbor in the neighbor list described in [OSPFv3],
A.3.2.
o Increment the router's SCS number that it will use in its next
Hello (indicated in the State Check Sequence TLV).
o When the neighbor has reached the EXCHANGE state, described in
[OSPF], 10.1, it is removed from the list of neighbors described
in [OSPFv3], A.3.2.
o If the neighbor is not a DR or backup designated router (BDR) on
an OSPF broadcast link, and the neighbor is advertised as
connected in the Network LSA advertised by the DR, it is removed
from the list of neighbors described in [OSPFv3], A.3.2.
Chandra Expires October 23, 2005 [Page 17]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
3.3.6.2 Adjacency Failure
On discovering an adjacency failure (going to state less than
EXCHANGE), a router using I bit signaling SHOULD:
o Remove the adjacent router from local tables, and take the
appropriate actions for a failed adjacency described in [OSPF] and
[OSPFv3].
o Add the formerly adjacent router to a Neighbor Drop TLV.
o Increment the router's SCS number that it will transmit in its
next Hello.
o Transmit Hellos with this Neighbor Drop TLV - It may be desirable
to send the Neighbor Drop TLV in three consecutive Hellos to
increase the probability of reception. In this case, 'persistent'
Hello packets would be sent with the same SCS number, the Neighbor
Drop TLV, and the 'N' bit set. Thus, the receiver knows that the
Neighbor Drop TLV is being sent persistently and there is more
state associated with the SCS in case it must request missing
state presumably transmitted in a previous Hello.
3.3.7 Sending Hellos
When a device is first attached to a network (whether through being
brought into range of another device, powering the device on, or
enabling the device's radio interface, etc.), it will need to obtain
complete neighbor state from each of its neighbors before it can
utilize the incremental Hello mechanism. Thus, upon initialization,
a device MAY send a multicast Hello request (and omit the 'Request
From' TLV). Neighbors will receive the request and respond with a
Hello with their complete neighbor state.
If a device is in INIT state with a neighbor and receives a Hello
from the neighbor without its router ID listed in the neighbor list,
the device SHOULD request the current state from the neighbor. Note
that this is to avoid a race condition since the received Hello can
either mean that the device is NOT SEEN by the neighbor, or that the
device is adjacent and not listed in the incremental list. Thus, by
receiving a Hello request, the neighbor will respond with its
neighbor state for the neighbor.
The first Hello packet with a particular SCS number MUST contain the
full state associated with that SCS number, i.e., all state changes
since the last SCS number. The 'N' bit MUST NOT be set in the State
Check Sequence TLV.
Incremental Hello packets can be sent persistently (sent in k
successive Hello packets), with flexibility in the actual amount of
information being sent. The three options include:
Chandra Expires October 23, 2005 [Page 18]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
o The entire incremental Hello packet is sent persistently. This is
accomplished by simply sending the entire state associated with a
SCS number for k successive Hellos. Since the SCS number remains
the same, the 'N' bit is not set in these incremental Hello
packets.
o Partial information for a particular SCS number is sent
persistently. After the first Hello packet with a particular SCS
number is sent, only the TLVs that are desired to be sent
persistently are sent in subsequent Hellos with the same SCS
number and the 'N' bit set.
o No information is sent persistently. This is simply the default
behavior where an incremental Hello packet with a particular SCS
number is only sent once.
3.3.8 Receiving Hellos
Each OSPF device supporting incremental Hello signaling, as described
in this document, MUST keep the last known SCS number from each
neighbor it has received Hellos from as long as the neighbor
adjacency structure is maintained.
If a device receives a Hello from an adjacent neighbor with an SCS
number less than the last known SCS number from that neighbor, it
MUST first check if the SCS number is a wrap around. If it is NOT a
wrap around, then the device MUST send a Hello request to the
neighbor.
If it is a wrap around or if a device receives a Hello from an
adjacent neighbor with an SCS number one greater than the last known
SCS number from that neighbor, it MUST:
o Examine the neighbor list described in [OSPFv3], A.3.2. If any
neighbors are contained in this list, increment the SCS number
contained in the adjacent neighbor's data structure.
o Examine the Neighbor-Drop TLV as described in the section
Adjacency Failure. If this list contains a neighbor other than
the local router, increment the SCS number contained in the
adjacent neighbor's data structure.
o Examine the Neighbor Drop TLV as described in the section
Adjacency Failure. If the local router identifier is contained in
this list, destroy the transmitting adjacent neighbor's data
structures.
o Examine any other TLVs incrementally signaled, as described in
drafts referring to this document. If there are other state
changes indicated, increment the SCS number contained in the
adjacent neighbor's data structure.
o If no state change information is contained in the received Hello,
a request for current state (by setting the 'R' bit) is sent in
the next Hello.
Chandra Expires October 23, 2005 [Page 19]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
If a device receives a Hello from an adjacent neighbor with an SCS
number greater than the last known SCS number + 1 from that neighbor,
it MUST send a Hello request to the neighbor since it may be missing
some neighbor state.
3.3.8.1 Receiving Hellos with the N Bit Set
If a device receives a Hello with the State Check Sequence TLV
included, and the 'N' bit set in this TLV, it MUST verify that it has
already received the SCS number with the 'N' bit NOT set from the
neighbor. If the device determines that this is the first reception
of the SCS number from this neighbor, then it MUST send a Hello
request to the neighbor since it missed the initial Hello packet with
the SCS number, and thus is missing state.
3.3.8.2 Receiving Hellos with the R Bit Set
If a device receives a Hello with the State Check Sequence TLV
included, and the R bit set, it looks for the 'Request From' TLV. If
it's router ID is listed in the 'Request From' TLV or the TLV is not
found, it includes its full state in the next Hello. This MUST
include:
o The neighbor ID of the requesting neighbor(s) in the list of
neighbors described in [OSPFv3], A.3.2.,
o An State Check Sequence TLV with the transmitter's current SCS
number, and the FS bit set. Note that the transmitter's SCS
number is NOT incremented.
o Any other TLVs, defined in other drafts referencing this document,
indicating the current state of the local system.
o The neighbor ID of all the neighbors who have requested current
state, in the 'Full State For' TLV.
If the full state is being sent to a large number of existing
neighbors, and implementation could choose to instead generate a full
state for all neighbors and omit the 'Full State For' TLV.
3.3.8.3 Receiving Hellos with the FS Bit Set
When a device receives a Hello with the State Check Sequence TLV
included, and the FS bit set, the Hello packet contains the
neighbor's full state for the device. The packet SHOULD be processed
as follows:
o If the received SCS number is equal to the last known SCS number,
the packet SHOULD be ignored since the device already has the
latest state information.
o If the received SCS number is different than the last known SCS
number, this Hello has new information and MUST be parsed.
Chandra Expires October 23, 2005 [Page 20]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
o If it is listed in the 'Full State For' TLV or if the 'Full State
For' TLV is not present, the device MUST save the SCS number,
process the Hello as described in the Receiving Hellos section,
and process any other appended TLVs.
3.3.9 Interoperability
On receiving a Hello packet from a new neighbor without the I bit
set, the local router will continue to place that router's identifier
in transmitted Hellos on this link as described in [OSPFv3], A.3.2.
3.3.10 Support for OSPF Graceful Restart
OSPF graceful restart, as described in [OSPFRESTART] and [OSPFGR],
relies on the lack of neighbors in the list of neighbors described in
[OSPFv3], A.3.2, to determine that an adjacent router has restarted,
and other signaling to determine the adjacency should not be torn
down. If all Hello packets transmitted by a given router have an
empty Hello list, reliance on an empty Hello packet to signal a
restart (or to reliably tear down an OSPF adjacency) is no longer
possible. Hence, this signaling must be slightly altered.
When a router would like to tear down all adjacencies, or signal it
has restarted:
o On initially restarting, during the first RouterDeadInterval after
restart, the router will transmit Hello packets with an empty
neighbor list, and the I bit cleared. Any normal restart or other
signaling may be included in these initial Hello packets.
o As adjacencies are learned, these newly learned adjacent routers
are included in the multicast Hellos transmitted on the link.
o After one RouterDeadInterval has passed, the incremental Hello
mechanism is invoked. An incremental Hello packet with full state
is sent with the 'I' bit set, and the SCS TLV included with the
'A' bit set and the InitialSCS value, e.g., SCS of '1'.
Subsequent Hello packets will include only incremental state.
Routers which are neighboring with a restarting router MUST continue
sending their Hello packets with the I bit set.
3.4 Optimized Flooding (Overlapping Relays)
A component that may influence the scalability and convergence
characteristics of OSPF [OSPF],[OSPFv3] in a MANET environment is how
much information needs to be flooded. The ideal solution is that a
router will only receive a particular routing update only once.
However, there must be a tradeoff between protocol complexity and
ensuring that every speaker in the network receives all of the
information. Note that a speaker refers to any node in the network
Chandra Expires October 23, 2005 [Page 21]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
that is running the routing protocol and transmitting routing updates
and Hello messages.
Controlling the amount of information on the link has increased
importance in a MANET environment due to the potential transmission
costs and resource availability in general.
In some environments, a group of speakers that share the same logical
segment may not be directly visible to each other; some of the
possible causes are the following: low signal strength, long distance
separation, environmental disruptions, partial VC meshing, etc. In
these networks, a logical segment refers to the local flooding domain
dynamically determined by transmission radius. In these situations,
some speakers (the ones not able to directly reach the sender) may
never be able to synchronize their databases. To solve the
synchronization issues encountered in these environments, a mechanism
is needed through which all the nodes on the same logical segment can
receive the routing information, regardless of the state of their
adjacency to the source.
3.4.1 Operation Overview
The optimized flooding operation relies on the ability of a speaker
to advertise all of its locally connected neighbors. In OSPF, this
ability is realized through the use of link state advertisements
(LSA)s [OSPF],[OSPFv3].
A speaker receives router LSAs from its adjacent neighbors. A
speaker's router LSA conveys the list of the adjacent speakers of the
originator ("neighbor list"). The local speaker can compare the
neighbor list reported by each speaker to its own neighbor list. If
the local neighbor list contains adjacent speakers that the
originator cannot reach directly (i.e. those speakers that are not in
the originator's neighbor list), then these speakers are locally
known as non-overlapping neighbors for the originator.
The local speaker should relay any routing information to non-
overlapping neighbors of the sender based on the algorithm outlined
in the Flooding and Relay Decisions section. Because more than one
such speaker may exist, the mechanism is called "overlapping relays."
The algorithm, however, does select the set of overlapping relays
that should transmit first. This set is known as the active set of
overlapping relays for a speaker.
3.4.2 Determination of Overlapping Relays
The first step in the process is for each speaker to build and
propagate their neighbor lists in router LSAs packets. Every speaker
Chandra Expires October 23, 2005 [Page 22]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
is then in a position to determine their two-hop neighborhood, i.e.,
those nodes that are neighbors of the speaker's one-hop neighbors. A
neighbor is considered an overlapping relay for a speaker if it can
reach a node in the two-hop neighborhood of the neighbor, i.e., if it
has one-hop neighbors.
The set of active overlapping relays for a speaker is the minimum set
of direct neighbors such that every node in the two-hop neighborhood
of the speaker is a neighbor of a least one overlapping relay in the
active set. Each speaker SHOULD select a set of active overlapping
relays based on a selection algorithm (one such algorithm is
suggested in the "Overlapping Relay Discovery Process" Section and is
based on the MPR selection algorithm described in [OLSR]). Note that
a speaker MUST NOT choose a neighbor to serve as an active
overlapping relay if that neighbor set the 'N' bit in its Active
Overlapping Relay TLV as defined in Section "Active Overlapping Relay
Extension", unless the neighbor is the only neighbor to reach a two-
hop neighbor. Election of active overlapping relays is done across
interfaces, and thus, it is node-based and not link-based.
3.4.3 Terminology
The following heuristic and terminology for active overlapping relay
selection is largely taken from [OLSR]:
o FULL: Neighbor state FULL as defined in [OSPF] & [OSPFv3]. Note
that all neighbor references in this document are assumed to be
FULL neighbors.
o 2-hop FULL neighbors: The list of 2-hop neighbors of the node that
are FULL and that can be reached from direct neighbors, excluding
any directly connected neighbors.
o Active Set: A (sub)set of the neighbors selected such that through
these selected nodes, all 2-hop FULL neighbors are reachable.
o N: N is the set of FULL neighbors of the node.
o N2: A subset of 2-hop FULL neighbors excluding the nodes only
reachable by members of N.
o D(y): The degree of a one hop neighbor node y (where y is a member
of N), is defined as the number of FULL neighbors of node y,
EXCLUDING all the members of N and EXCLUDING the node performing
the computation.
3.4.4 Overlapping Relay Discovery Process
A possible algorithm for discovering overlapping relays is the
following:
1. Start with an active set made of all members of N that have set
the 'A' bit in their Active Overlapping Relays TLV as defined in
Section "Active Overlapping Relays Extension".
Chandra Expires October 23, 2005 [Page 23]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
2. Calculate D(y), where y is a member of N, for all nodes in N.
3. Add to the active set those nodes in N, which are the *only*
nodes to provide reachability to a node in N2, i.e., if node-b in
N2 can be reached only through a symmetric link to node-a in N,
then add node-a to the active set. Remove the nodes from N2
which are now covered by a node in the active set.
4. While there exist nodes in N2 which are not covered by at least
one node in the active set:
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 active set, and which are reachable through
this one hop neighbor;
2. Select as an active overlapping relay the node with highest
Willingness among the nodes in N with non-zero reachability.
In case of multiple choice select the node which provides
reachability to the maximum number of nodes in N2. In case
of multiple nodes providing the same amount of reachability,
select the node as active whose D(y) is greater. As a final
tie breaker, the node with the highest router ID should be
chosen. Remove the nodes from N2 which are now covered by a
node in the active set.
5. As an optimization, process each node, y, in the active set in
increasing order of Willingness. If all nodes in N2 are still
covered by at least one node in the active set excluding node y,
and if Willingness of node y is smaller than MAX_WILLINGNESS,
then node y should be removed from the active set.
Note that the active overlapping relays selection algorithm is
implementation specific, and the above is simply a suggested
algorithm. However, the behavior of the overlapping relays MUST
follow that specified in the "Flooding and Relay Decisions" Section.
Moreover, the same selection algorithm MUST be used by all nodes
within an area.
3.4.5 The F Option Bit
A single new option bit, the F bit, is defined in the OSPFv3 option
field. The F bit indicates that the node supports the Optimized
Flooding mechanism as specified in this draft. See Section "New Bits
in OSPFv3 Options Field" for placement of the F bit.
3.4.6 Active Overlapping Relay Extension
A new TLV is defined so that each speaker can convey its set of
active overlapping relays in the Hello messages. The TLV is
transmitted using the Link Local Signaling method described in "Link
Local Signaling" Section.
Chandra Expires October 23, 2005 [Page 24]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Relays Added |A|N| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID(s) of Active Overlapping Relay(s) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
o Type: Type, set to 4.
o Length - variable; Length of TLV in bytes NOT including Type and
Length.
o Relays Added - variable; Number of active overlapping relays that
are being added. Note that the number of active overlapping
relays that are being dropped is then given by: [(Length - 4)/4 -
Relays Added].
o A bit - If this bit is set, the node is specifying that it will
always flood routing updates that it receives, regardless of
whether it is selected as an Active Overlapping Relay.
o N bit - If this bit is set, the node is specifying that it most
likely will not flood routing updates. The node SHOULD NOT be
chosen to be an active overlapping relay unless it is the *only*
neighbor that can reach two-hop neighbor(s). Note that if the
node is selected as an Active Overlapping relay and the node can
not perform the required duties, network behavior is not
compromised since it results in the same behavior as if the node
was not chosen as an active overlapping relay.
o Reserved - Reserved for future use and MUST be ignored upon
reception.
o Router ID(s) of Active Overlapping Relay(s) - The router ID(s) of
neighbor(s) that are either chosen to serve as an active
overlapping relay, or removed from serving as an active
overlapping relay. The active overlapping relays that are being
added MUST be listed first, and the number of such relays MUST
equal Add Length. The remaining list of relays are being dropped
as active overlapping relays, and the number of such relays MUST
equal [(Length - 4)/4 - Relays Added].
Note that the 'A' bit and 'N' bit are independent of any particular
selection algorithm to determine the set of Active Overlapping
Relays. However, the bits SHOULD be considered as input into the
selection algorithm.
If a node is selected as an active overlapping relay and it does not
support the Incremental Hello mechanism defined in the "Incremental
Chandra Expires October 23, 2005 [Page 25]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
OSPF-MANET Hellos" Section, then it SHOULD always be included as an
Active Overlapping Relay in the TLV. Note that while a node needs to
know whether it is an active overlapping relay, it does not
necessarily have to know the identities of the other active
overlapping relays.
3.4.7 Willingness TLV
A new TLV is defined so that each speaker can convey its willingness
to serve as an active overlapping relay in the Hello meassage. The
TLV is transmitted using the Link Local Signaling method described in
the "Link Local Signaling" Section.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Willingness | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
o Type: Type, set to 5.
o Length - 4 bytes. It does not include the Type and Length fields.
o Willingness - 1 byte to indicate the willingness of the node to
serve as an active overlapping relay for its neighbors.
* 0: MIN_WILLINGNESS
* 128: DEFAULT_WILLINGNESS
* 255: MAX_WILLINGNESS
The TLV is optional and MUST be silently ignored if not understood.
If the Willingness TLV is not included in the Hello packet, the
Willingness value SHOULD be taken as DEFAULT_WILLINGNESS.
3.4.8 Flooding and Relay Decisions
The decision whether to relay any received LSAs and when to relay
such information, is made depending on the topology and whether the
node is part of the set of active overlapping relays.
Upon receiving an LSA from an adjacent speaker, a node makes flooding
decisions based on the following algorithm:
1. If the node is an active overlapping relay for the adjacent
speaker, then the router SHOULD immediately relay any information
received from the adjacent speaker.
2. If the node is a non-active overlapping relay for the adjacent
speaker, then the router SHOULD wait a specified amount of time
(PushbackInterval plus jitter, see "Important Timers" Section) to
decide whether to transmit. [Jitter is used to try to avoid
Chandra Expires October 23, 2005 [Page 26]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
several non-active overlapping relays from propagating redundant
information.] Note that a node with the 'N' bit set in the
'Active Overlapping Relays' Extension will not be chosen as an
active overlapping relay unless it is the only node to provide
reachability to a two-hop neighbor. However, it MUST perform the
duties of a non-active overlapping relay as required. Non-active
overlapping relays MUST follow the acknowledgment mechanism
outlined in the section 'Intelligent Transmission of Link State
Acknowledgements.'
1. During this time, if the node determines that flooding the
LSA will only result in a redundant transmission, the node
MUST suppress its transmission. Otherwise, it MUST transmit
upon expiration of PushbackInterval plus jitter.
2. If a non-active overlapping relay hears a re-flood from
another node that covers its non-overlapping neighbors before
its timer to transmit expires, it SHOULD reset its
PushbackInterval plus jitter timer. (Note that the
implementation should take care to avoid resetting the
PushbackInterval timer based on transmissions from active
overlapping relays.) During this time, if the node
determines that flooding the update will only result in a
redundant transmission, the node MUST suppress its
transmission. Otherwise, it MUST transmit upon expiration of
PushbackInterval + jitter.
3. If a non-active overlapping relay hears an old instance of
the LSA during this time, it SHOULD ignore the LSA and it
SHOULD NOT send a unicast packet to the neighbor with the
most recent LSA as specified in [OSPFv3].
3. For LSAs that are received unicast because of retransmission by
the originator, the node MUST determine whether it has already
received the LSA from another speaker. If it already has the
current instance of the LSA in its database, it MUST do nothing
further in terms of flooding the LSA (since it would have taken
appropriate behavior when it initially received the LSA.)
However, if it does not have the current instance of the LSA in
its database, it MUST take action according to the rules above,
just as if it received the multicast LSA. The acknowledgement
mechanism outlined in the section 'Intelligent Transmission of
Link State Acknowledgements' MUST be followed, and any timeout
mechanism for unicast LSAs MAY be followed.
Note that a node can determine whether further flooding a LSA will
only result in a redundant transmission by already having heard link
state acknowledgements (ACKs) or floods for the LSA from all of its
neighbors.
Due to the dynamic nature of a network, the set of active overlapping
relays may not be up to date at the time the relay decision is made
Chandra Expires October 23, 2005 [Page 27]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
or may not be able to perform the flooding duties, e.g., due to poor
link quality. The non-active overlapping relays prevent this
situation from causing database synchronization issues and thus,
packet loss.
Since the originator of the information, the relay, and the receiver
are all in the same dynamically determined local flooding domain, the
relay MUST NOT change the routing update information. In general,
LSAs SHOULD be sent to a well-known multicast address. In some
cases, routing updates MAY be sent using unicast packets.
3.4.9 Intelligent Transmission of Link State Acknowledgements
In order to optimize the bandwidth utilization on the link, a speaker
MUST follow these recommendations related to ACK transmissions:
1. All ACKs MUST be sent via multicast.
2. Typically, LSAs are acknowledged by all of the adjacent speakers.
In the case of relayed information, the relay MUST only expect
either explicit or implicit acknowledgements from neighbors that
have not previously acknowledged this LSA.
3. Because routing updates are sent via multicast, the set of
overlapping speakers will usually receive the same update more
than once. A speaker SHOULD only acknowledge the first update
received on the link.
4. An active overlapping relay SHOULD NOT explicitly acknowledge
information that it is relaying. The relayed information will
serve as an acknowledgement to the sender. If no information is
being relayed, than an explicit ACK MUST be sent.
5. Several ACKs MAY be bundled into a single packet. The wait
(AckInterval) before sending one such packet reduces the number
of packet transmissions required in acknowledging multiple LSAs.
6. All ACK packets SHOULD reset the RouterDeadInterval at the
receiver. If there is no state waiting to be transmitted in a
Hello packet at the sender, then the HelloInterval at the sender
SHOULD be reset. Note that an ACK serves as a Hello packet with
no state change.
7. Any LSA received via unicast MUST be acknowledged. (Note that
acknowledgment is via multicast as specified in rule (1) above.)
An ACK received from a non-overlapping neighbor should prevent
redundant transmission of the information to it by another
overlapping relay.
3.4.10 Important Timers
This section details the timers that are introduced in the Flooding
and Relay Decisions and Intelligent Transmission of Link State
Acknowledgements sections.
Chandra Expires October 23, 2005 [Page 28]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
o PushbackInterval: The length of time in seconds that a non-active
overlapping relay SHOULD wait before further flooding an LSA if
needed. This timer MUST be less than 1/2 of the RxmtInterval
[OSPF],[OSPFv3] minus propagation delays, i.e., (PushbackInterval
+ propagation delay) < RxmtInterval/2. The PushbackInterval is
set by a non-active overlapping relay upon reception of an LSA.
o AckInterval: After a node determines that it must transmit an ACK
and the AckInterval timer is not already set, the node SHOULD set
the AckInterval timer. The AckInterval is the length of time in
seconds that a node should wait in order to transmit many ACKs in
the acknowledgement packet. This wait reduces the number of
packet transmissions required in acknowledging multiple LSAs. The
AckInterval MUST be less than the PushbackInterval minus
propagation delays, i.e., (AckInterval + propagation delay) <
PushbackInterval.
3.4.11 Miscellaneous Protocol Considerations
The mechanism described refers to the operation of relays on a common
media segment. In other words, an LSA is only relayed out the same
interface through which it was received. However, the concept of
information relay may be extended to the flooding of all link state
advertisements received on any interface (and forwarded on any other
interface). OSPF works on the premise that all of the nodes in a
flooding domain will receive all of the routing information. Note
that one of the important properties is that the routing information
is not altered when relayed.
If each speaker advertised all of its adjacent neighbors on all
interfaces, then the overlap check would result in the determination
of which speakers are adjacent to both speakers. As a result, link
state information should only be flooded to non-overlapping neighbors
(taking all of the interfaces into account).
The flooding mechanism in OSPF relies on a designated router to
guarantee that any new LSA received by one router attached to the
broadcast network will be reflooded properly to all the other routers
attached to the broadcast network. Such desginated routers must be
able to reach all of the other speakers on the same subnet. A
designated router SHOULD NOT be elected if overlapping relays are
used.
If such designated routers already exist, then the relays MUST be
capable of differentiating them, and then making the relaying
decisions based on the OSPF's normal operation. As a result, there
may be groups of neighbors to which some information should not be
relayed. This mode of operation is NOT RECOMMENDED as it adds to the
complexity of the system.
Chandra Expires October 23, 2005 [Page 29]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
The intent of the overlapping relay mechanism is to optimize flooding
of routing control information. However, other information (such as
data) may also be relayed in some networks using the same mechanism.
3.4.12 Interoperability
On receiving a Hello packet from a new neighbor without the F bit
set, the local router will assume that the new neighbor will flood
normally as described in [OSPFv3]. Thus, the local router SHOULD
include the neighbor in its overlapping relay set since the neighbor
will flood by default. This will allow the local router to more
optimally select its entire overlapping relay set.
If the F bit is set and the I bit as defined in Section "Incremental
OSPF-MANET Hellos" is not set in the neighbor's Hello and the
neighbor is selected as an overlapping relay by the local router, the
local router will continue to include the neighbor's identifier in
its active relay set.
3.5 New Bits in OSPFv3 Option Field
Three new option bits are defined in the OSPFv3 Options Field
(defined in [OSPFv3], A.2) as follows:
0 1 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+-+-+--+--+--+--+--+--+
| | | | | | | | | | | | |F|I|L|AF|*|*|DC| R| N|MC| E|V6|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+-+-+--+--+--+--+--+--+
o L bit - defined in Section "L Option Bit": Routers set the L bit
in Hello and DD packets to indicate that the packet contains LLS
data block. The next available bit is used for the purposes of
this document.
o I bit - defined in Section "I Option Bit": The I bit is only
defined for Hello packets and indicates that only incremental
information is present.
o F bit - defined in Section "F Option Bit": The F bit indicates
that the node supports the Optimized Flooding mechanism as
specified in this draft.
4. Security Considerations
In a MANET network, security is both more difficult and important due
to the wireless nature of the medium. Controlling the ability of
devices to connect to a MANET network at Layer 2 will be relegated to
Layer 2 security mechanisms, such as 802.1x, and others. Controlling
the ability of attached devices to transit traffic will require some
Chandra Expires October 23, 2005 [Page 30]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
type of security system (outside the scope of this document) which
can authenticate and provide authorization for individual members of
the routing domain.
5. IANA Considerations
This document creates several new name spaces. This section
summarizes them and the criteria to be used for their assignment. It
is expected that IANA will maintain a registry and make the
assignments as explained below using the policies outlined in [IANA].
The "LLS TLVs" section defines a two-octet field called Type to
uniquely identify each type of TLV. Type 0 is reserved. Values 1
through 32767 are to be assigned using the "IETF Consensus" policy;
values 1 through 5 are assigned in this document. Values 32768
through 49151 are to be assigned using "Specification Required."
Values 49152 and above are for "Private Use."
The "Extended Options TLV" section defines a four-octet bitfield
called Extended Options. Values 0x00000001 through 0x08000000 are to
be assigned using the "IETF Consensus." Values 0x10000000 through
0x80000000 are for "Private Use."
The assignment of any of the Reserved fields requires the review of
the OSPF WG.
In addition to the maintenance of the name spaces described above,
IANA is is expected to assign the following:
o An option bit value for the L-bit defined in the "Link-local
Signaling" section.
o An option bit value for the I-bit defined in the "The I Option
Bit" section.
6. Draft Change History
Changes from Version 2 to Version 3:
o Modified Incremental Hello mechanism so that Hello requests are
replied to in a more unified fashion.
o Introduced a new 'Full State For' TLV in the Incremental Hello
mechanism to allow a Hello packet to only contain full state as
far are those neighbors are concerned.
o Modified placement of bits in the OSPFv3 Options Field.
o Clarified that selection of Overlapping Relays is across an
interface.
o Added an Interoperability subsection to the "Optimized Flooding
(Overlapping Relays)" Section.
Chandra Expires October 23, 2005 [Page 31]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
Changes from Version 1 to Version 2:
o Introduced an 'F' bit in OSPFv3 Options Field to explicitly
specify that a node support Optimized Flooding. Added supporting
text to specify behavior.
o Modified Active Overlapping Relays TLV to include 'A' bit and 'N'
bit. Added supporting text to specify behavior.
o Modified/clarified Willingness values in Willingness TLV.
o Clarified text regarding setting of the Pushback Timer.
o Introduced notion of an initial SCS value
o Clarified text regarding support for graceful restart.
o Renumbered subsections in the 'Incremental OSPF-MANET Hellos"
section.
o Editorial changes to clarify text.
Changes from Version 0 to Version 1:
o Introduced an Incomplete Bit ('N' bit) to the SCS TLV to allow for
flexibility in sending persistent information.
o Editorial changes to clarify text.
7. Intellectual Property
By submitting this Internet-Draft, we certify that any applicable
patent or other IPR claims of which we are aware have been disclosed,
and any of which we become aware will be disclosed, in accordance
with RFC 3668.
8. Contributors
The following persons are contributing authors to the document:
Chandra Expires October 23, 2005 [Page 32]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
Fred Baker Dave Cook
Cisco Systems Cisco Systems
1121 Via Del Rey 7025-4 Kit Creek Road
Santa Barbara, CA 93117 RTP, NC 27709
USA USA
Email: fred@cisco.com Email: dacook@cisco.com
Phone: +1-408-526-4257 Phone: +1-919-392-8772
Alvaro Retana Abhay Roy
Cisco Systems Cisco Systems
7025-4 Kit Creek Road 170 W. Tasman Drive
RTP, NC 27709 San Jose, CA 95134
USA USA
Email: aretana@cisco.com Email: akr@cisco.com
Phone: +1-919-392-2061 Phone: +1-408-527-2028
Russ White Yi Yang
Cisco Systems Cisco Systems
7025-4 Kit Creek Road 7025-4 Kit Creek Road
RTP, NC 27709 RTP, NC 27709
USA USA
Email: riw@cisco.com Email: yiya@cisco.com
Phone: +1-919-392-3139 Phone: +1-919-392-4035
9. Acknowledgements
The authors and contributors would like to thank Pratap Pellakuru and
Stan Ratliff for their feedback and implementation of the document.
10. References
10.1 Normative References
[OSPF] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[OSPFv3] Coltun, R., Ferguson, D., and J. Moy, "OSPF for IPv6",
RFC 2740, December 1999.
[IANA] Narten, T. and H. Alvestrand, "Guidelines for Writing an
IANA Considerations Section in RFCs", BCP 26, RFC 2434,
October 1998.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
Chandra Expires October 23, 2005 [Page 33]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
10.2 Informative References
[IPV6ADD] Hinden, R. and S. Deering, "Internet Protocol Version 6
(IPv6) Addressing Architecture", RFC 3513, April 2003.
[OSPFRESTART]
Moy, J., Pillay-Esnault, P., and A. Lindem, "Graceful OSPF
Restart", RFC 3623, November 2003.
[OSPFGR] Zinin, A., Roy, A., and L. Nguyen, "OSPF Restart
Signaling", draft-nguyen-ospf-restart-04 (work in
progress), January 2004.
[TE] Katz, D., Yeung, D., and K. Kompella, "Traffic Engineering
Extensions to OSPF", RFC 3630, September 2003.
[LLS] Zinin, A., Friedman, B., Roy, A., Nguyen, L., and D.
Yeung, "OSPF Link-local Signaling",
draft-nguyen-ospf-lls-04 (work in progress), January 2004.
[OLSR] Clausen, T. and P. Jacquet, "Optimized Link State Routing
Protocol", draft-ietf-manet-olsr-06 (work in progress),
March 2002.
Author's Address
Madhavi W. Chandra
Cisco Systems
Chandra Expires October 23, 2005 [Page 34]
Internet-Draft Extensions to OSPF to Support MANETs April 2005
Intellectual Property Statement
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Disclaimer of Validity
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Copyright Statement
Copyright (C) The Internet Society (2005). This document is subject
to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights.
Acknowledgment
Funding for the RFC Editor function is currently provided by the
Internet Society.
Chandra Expires October 23, 2005 [Page 35]
| PAFTECH AB 2003-2026 | 2026-04-23 10:28:02 |