INTERNET-DRAFT Thomas Clausen
IETF MANET Working Group Philippe Jacquet
Expiration: August 2004 Emmanuel Baccelli
Project Hipercom
INRIA Rocquencourt, France
February 2004
DB Exchange for OSPFv2 Wireless Interface Type
draft-clausen-manet-ospf-dbx-00.txt
Status of this Memo
This document is a submission by the Mobile Ad Hoc Networking Working
Group of the Internet Engineering Task Force (IETF). Comments should
be submitted to the manet@itd.nrl.navy.mil mailing list.
Distribution of this memo is unlimited.
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.
Clausen, Baccelli, Jacquet [Page 1]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
Abstract
This memo describes a mechanism providing database exchange and
reliable transmission capabilities in a way which is adapted to link
state routing on ad hoc networks. This mechanism is specified in
this document for wireless OSPF interfaces as specified in draft-
spagnolo-manet-ospf-wireless-interface-00.txt. A signature exchange
technique is proposed, providing a very compact way for the nodes to
communicate and compare the state of their respective link-state
databases. Upon receiving such a signature, a node can quickly
detect if a discrepancy is present and, furthermore, determine which
information must be exchanged in order to alleviate this discrepancy.
Clausen, Baccelli, Jacquet [Page 2]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.Changes . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2. Derivations from OSPF Database Exchange . . . . . . . . . 7
1.3. Signature Exchange Terminology . . . . . . . . . . . . . . 8
2. The Link State Database . . . . . . . . . . . . . . . . . . 8
3. Splitting the AS into Areas . . . . . . . . . . . . . . . . 9
4. Functional Summary . . . . . . . . . . . . . . . . . . . . . 9
4.1. Inter-area Routing . . . . . . . . . . . . . . . . . . . . 9
4.2. AS External Routes . . . . . . . . . . . . . . . . . . . . 9
4.3. Routing Protocol Packets . . . . . . . . . . . . . . . . . 9
4.4. Basic Implementation Requirements . . . . . . . . . . . . 9
4.5. Optional OSPF Capabilities . . . . . . . . . . . . . . . . 10
5. Protocol Data Structures . . . . . . . . . . . . . . . . . . 10
6. The Area Data Structure . . . . . . . . . . . . . . . . . . 10
7. Bringing Up Adjacencies . . . . . . . . . . . . . . . . . . 10
7.1. The Hello Protocol . . . . . . . . . . . . . . . . . . . . 10
7.2. The Synchronization of Databases . . . . . . . . . . . . . 10
7.2.1. Informational Signatures . . . . . . . . . . . . . . . . 11
7.2.2. Database Exchange Signatures . . . . . . . . . . . . . . 11
7.2.3. Signature Message Generation . . . . . . . . . . . . . . 11
7.2.3.1. Info Signatures Generation . . . . . . . . . . . . . . 12
7.2.3.2. Dbx Signatures Generation . . . . . . . . . . . . . . 12
7.2.4. Checking Signatures . . . . . . . . . . . . . . . . . . 13
7.2.5. Database Exchange . . . . . . . . . . . . . . . . . . . 14
7.3. The Designated Router . . . . . . . . . . . . . . . . . . 15
7.4. The Backup Designated Router . . . . . . . . . . . . . . . 15
8. Protocol Packet Processing . . . . . . . . . . . . . . . . . 15
9. Interface Data Structure . . . . . . . . . . . . . . . . . . 15
10. Neighbor Data Structure . . . . . . . . . . . . . . . . . . 15
11. Routing Table Structure . . . . . . . . . . . . . . . . . . 15
12. Link State Advertisements . . . . . . . . . . . . . . . . . 15
13. The Flooding Procedure . . . . . . . . . . . . . . . . . . 16
14. Aging the Link State Database . . . . . . . . . . . . . . . 16
Clausen, Baccelli, Jacquet [Page 3]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
15. Virtual Links . . . . . . . . . . . . . . . . . . . . . . . 16
16. Calculation of the Routing Table . . . . . . . . . . . . . 16
A. OSPF Data Formats . . . . . . . . . . . . . . . . . . . . . 16
A.1. Signature Packet Format . . . . . . . . . . . . . . . . . 16
A.2. Prefix Signature Format . . . . . . . . . . . . . . . . . 18
B. Architectural Constants . . . . . . . . . . . . . . . . . . 20
C. Configurable Constants . . . . . . . . . . . . . . . . . . 20
D. Authentication . . . . . . . . . . . . . . . . . . . . . . 20
E. An Algorithm for Assigning Link State IDs . . . . . . . . . 20
F. Multiple Interfaces to the same Network/Subnet . . . . . . 20
G. Differences from RFC 2178 . . . . . . . . . . . . . . . . . 20
H. Signature Hashing Calculation . . . . . . . . . . . . . . . 21
I. Applicability Scenarios . . . . . . . . . . . . . . . . . . 22
I.1. Emerging node . . . . . . . . . . . . . . . . . . . . . . 22
I.2. Merging Wireless Clouds . . . . . . . . . . . . . . . . . 22
I.3. Acknowledgments . . . . . . . . . . . . . . . . . . . . . 23
J. Security Considerations . . . . . . . . . . . . . . . . . . 23
K. IANA Considerations . . . . . . . . . . . . . . . . . . . . 23
L. Authors' Addresses . . . . . . . . . . . . . . . . . . . . 23
Clausen, Baccelli, Jacquet [Page 4]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
Clausen, Baccelli, Jacquet [Page 5]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
1. Introduction
This document discusses a mechanism providing OSPF-style database
exchanges for wireless OSPF interfaces as defined by draft-spagnolo-
manet-ospf-wireless-interface-00 [WOSPF].
OSPF [OSPF] database exchanges intend to synchronize the link-state
database between routers in the network. In OSPF, database
description packets are exchanged between two nodes through one node
(the master) polling an other node (the slave), which responds. Both
polls and responses have the form of database description packets
containing a set of complete LSA headers, describing (a partial set
of) the respective link-state databases of each of the two nodes.
These database description packets are used by the nodes to compare
their link-state databases. If any of the two nodes involved in the
exchange detects it has out-of-date or missing information, it issues
link-state request packets to request the pieces of information from
the other node, which would update its link-state database.
In the context of wireless OSPF interfaces as defined in [WOSPF],
wireless broadcast interfaces are assumed, as well as a high degree
of network topology dynamics. This implies that inconsistencies
between the link-state databases of different nodes in the network
can be assumed to be frequently occuring. Simillarly, changes in the
network topology are anticipated to happen at a much quicker pace on
a wireless OSPF interface than on other OSPF interfaces. Moreover,
the broadcast nature of the [WOSPF] network interfaces implies that
the bandwidth in a region is shared among the nodes in that region.
In terms of database exchange, this implies that in a wireless
broadcast environment:
(i) database exchanges may occur frequently;
(ii) a database exchange has limited time to complete before
the network topology changes;
(iii) limited bandwidth is available per node-per for completing
a database exchange.
The goal of the database exchange mechanism is, effectively, to
ensure that the nodes in the network have the same updated
information about the network topology recorded in their respective
link-state databases. This doccument provides this functionality,
adapted to the conditions of a wireless ad-hoc environment.
The mechanism described in this document is somewhat inspired by the
one employed by IS-IS [ISIS]. In IS-IS, packets which list the most
recent sequence number of one or more LSAs (so called Sequence
Numbers packets) are used to ensure that neighboring nodes agree on
Clausen, Baccelli, Jacquet [Page 6]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
what is the most recent link state information from each other node.
I.e., rather than transmitting complete LSA headers (as in OSPF),
ISIS employs a more compact representation for database description
messages. Additionally, Sequence Numbers packets accomplish a
function similar to conventional acknowledgment packets. Sequence
Numbers packets also allow more efficient operation, in the sense
that they may act as a request for information, i.e., a complete
Sequence Number packet containing the most recent sequence number of
all the LSAs in the database may be used to ensure synchronization of
the database between adjacent routers either periodically, or when a
link first comes up, much like the database exchange mechanism.
This document is organized as a supplement to the wireless OSPF
interface specifications as defined by [WOSPF]. Read in conjunction
with [WOSPF] and [OSPF], this memo completely specifies the
mechanisms for database exchange, adapted to the WOSPF interface
type.
1.1. Changes
This is the initial version of this specification.
1.2. Derivations from OSPF Database Exchange
The database exchange mechanism, as specified in this document,
derivates from the database exchange mechanism in [OSPF] by the
addition of a database signature mechanism with the following
properties:
- create the new Signature Packet format. The new message will
advertise a set of compact "signatures" of the link state
database of a given node;
- periodically compute, send signatures;
- check received signatures;
- operate database information updates in case of descrepencies
detected with neighbors' link state databases.
Signature messages can make use of boundaries on the age of the LSAs
that participate in the signature computation. For example, it may
be considered a waste of resources to check for databases consistency
for LSAs issued from wireless environments: LSAs from wireless nodes
Clausen, Baccelli, Jacquet [Page 7]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
are transmitted frequently (periodically), thus information
describing these nodes is frequently updated and thereby of an age
smaller than a threshold, roughly close to the LSF period.
With this perspective, if one wants to limit the scope of the
database synchronization exchanges to the LSAs that are less
frequently updated (i.e. LSAs issued from usual wired environments),
it suffices to set the LSA age floor limit above the LSF period and
the LSA age ceiling to MaxAge in the signature messages.
1.3. Signature Exchange 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
signature exchange mechanism uses the following terminology:
Signature Message
This new message type advertises a set compact signatures (hashing)
of the link state database of a given node. Nodes can then compare
the state of their respective databases by exchanging these mes-
sages.
Informational Signatures (or info signatures)
This kind of signature message is broadcasted periodically to all
neighbor nodes in order to detect if there is any descrepancy
between the respective link state databases of the node and its
neighbors.
Dababase Exchange Signatures (or dbx signatures)
This second kind of signature message is sent to a single neighbor
only. The purpose of emitting a dbx signature is, for a node, to
initiate an exchange of database information with one specific
neighbor node when a discrepancy has been detected.
2. The Link State Database
There are no changes to the link state database described in section
2 in [OSPF] and [WOSPF].
Clausen, Baccelli, Jacquet [Page 8]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
3. Splitting the AS into Areas
There are no changes to the AS splitting described in section 3 in
[OSPF].
4. Functional Summary
This section defines extensions to Section 4 of [WOSPF].
A router with a wireless interface sends and receives signature
messages (on its wireless interface). Signature messages are used by
routers to compare their link state databases, detect discrepancies,
and alleviate them. They serve a similar purpose as the database
exchange packets and the acknowledgements on non-wireless interfaces,
but in a different fashion that is more adapted to mobile wireless
ad-hoc environments.
4.1. Inter-area Routing
There are no changes to section 4.1 in [OSPF].
4.2. AS External Routes
There are no changes to section 4.2 in [OSPF].
4.3. Routing Protocol Packets
This section defines extensions to section 4.3 in [WOSPF]. An
additional OSPF packet type is used: Type 8 Signature Packets. Their
format is specified in section A.
4.4. Basic Implementation Requirements
There are no changes to section 4.4 in [OSPF].
Clausen, Baccelli, Jacquet [Page 9]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
4.5. Optional OSPF Capabilities
There are no changes to section 4.5 in [OSPF].
5. Protocol Data Structures
There are no changes to the protocol data structures described in the
corresponding section in [WOSPF].
6. The Area Data Structure
There are no changes to the area data structure described in the
corresponding section in [OSPF] and [WOSPF].
7. Bringing Up Adjacencies
This section defines extensions to section 7 of [WOSPF].
7.1. The Hello Protocol
There are no changes to the hello protocol described in section 7.1
in [WOSPF].
7.2. The Synchronization of Databases
This section defines extensions to section 7.2 in [WOSPF].
On wireless interfaces, as specified in [WOSPF], adjacencies are not
formed like in regular OSPF, and therefore neither does the database
synchronization. However, a similar mechanism, adapted to wireless
ad-hoc interfaces, is available. This technique features compact
signatures (hashing) of the link state database that are periodically
exchanged between nodes. By checking each others' signatures,
neighbors can compare their respective databases, detect
discrepancies and if so, trigger an update of database information
between two neighbors.
Signatures are exchanged by nodes via Signature Packets. Their
format is described in section A. There are two kinds of signature
packets: informational signatures, and database exchange signatures.
Clausen, Baccelli, Jacquet [Page 10]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
Their different use, generation and checking are documented in the
following sections.
7.2.1. Informational Signatures
Each node periodically broadcasts informational (info) signatures, as
well as receives info signatures from its neighbor nodes. This
exchange allows nodes to detect any discrepancies between their
respective link-state databases.
7.2.2. Database Exchange Signatures
Contrary to the informative signatures, Database Exchange (dbx)
signatures are directed towards a single neighbor only. The purpose
of emitting a dbx signature is, for a node, to initiate an update of
database information with one specific neighbor node.
When a node detects a discrepancy between its own link-state database
and the link-state database of one (or more) of its neighbors, a
database exchange is desired to eliminate that discrepancy. The
node, detecting the discrepancy, generates a dbx signature,
effectively requesting the database exchange to take place. In OSPF
terms, the node requesting the database exchange is the "master" of
that exchange. The dbx signature is transmitted with the destination
address of one node among the discrepant neighbors. In OSPF-terms,
that neighbor node would be the "slave" in the database exchange. If
possible, the slave should be an MPR for the selecting node. The
node build a dbx message signature, based on the information acquired
from the info signature exchange.
7.2.3. Signature Message Generation
This section describes how signature messages are generated, for each
type. That is to say, (i) informative signature messages, and (ii)
database exchange signature messages. The actual mathematical
calculation of the signature hashing of the link state database is
described in section H.
Clausen, Baccelli, Jacquet [Page 11]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
7.2.3.1. Info Signature Generation
An informative signature message (also called info signature) can be
sent for periodical mutual check and describes the complete link
state database of the node that sends it. Namely, if no information
is given here about a given prefix, a neighbor can implicitly
understand that the node has no corresponding LSA in its database.
The set of prefix signatures in an informative signature message can
be generated with the following algorithm (Tunstall Splitting), where
the length L of the info signature (the number of prefix signatures
in the message) can be chosen at will.
We define the weight, and the timed weight, of a given prefix as the
functions:
Weight(prefix)= number of LSAs whose originator matches
the prefix.
Timed Weight(prefix)= number of LSAs whose originator matches
the prefix and whose age falls inside
the age interval.
Then, starting with the set of prefix signatures equal to
{(0,signature(0))}, recursively do the following.
As long as:
|set of prefix signatures| < L
- Find in the set of prefix signatures the prefix with largest
timed weight, let it be called mprefix.
- Replace the single (mprefix,signature(mprefix)) by the pair
{(mprefix0,signature(mprefix0)),(mprefix1,signature(mprefix1))}
- If one of the expanded prefix of mprefix has weight equal to 0,
then remove the corresponding tuple.
7.2.3.2. Dbx Signature Generation
When a node realizes there are discrepancies between his database and
the signature sent by neighbors, it sends a database exchange
signature message (also called dbx signature) to trigger the exchange
of descrepant LSAs with one of these neighbors, preferably an MPR,
Clausen, Baccelli, Jacquet [Page 12]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
which is designated in the destination field.
The set of prefix signatures in a database exchange signature message
can be generated with the following algorithm, where the length L of
the dbx signature (the number of prefix signatures in the message)
can be chosen at will.
Start with the same set of prefix signatures as one of the received
info signature where the descrepencies were noticed.
Remove from that set all the prefix signatures such that
signature(prefix) is not descrepant (with the LSA database). Use the
same age interval and key used in the received info signature. Then
recursively do the following.
As long as:
|set of prefix signatures| < L
- Find in the set of prefix signatures the prefix with largest timed
weight, let it be called mprefix.
- Replace the single (mprefix,signature(mprefix)) by the pair
{(mprefix0,signature(mprefix0)),(mprefix1,signature(mprefix1))}
Notice that contrary to info signature messages, the prefixes with
zero weight are not removed here, since the signature is not
complete, i.e. the signature might not describe the whole database.
Therefore a prefix with empty weight may be an indication of missing
LSAs.
7.2.4. Checking Signatures
Upon receiving a signature message from a neighbor, a node can check
its local LSA database and determine if it differs with the
neighbor's. For this purpose, it computes its own prefix signatures
locally using the same prefixes, time interval and key specified in
the received signature message. A prefix signature differs with the
local prefix signature when any of the following conditions occurs:
(i) both the number of LSAs and the timed number of LSAs
differ;
(ii) both the timed partial signatures and the (primary partial
signature, secondary partial signature) tuples differ.
Clausen, Baccelli, Jacquet [Page 13]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
The use of a secondary signature based on a random key is a way to
cope with the unfrequent but still possible cases when the primary
signatures agree although the databases differ. In this case, it can
be assumed that using a random key renders the probability that both
primary and secondary signatures agree while databases are different,
to be very small.
7.2.5. Database Exchange
When a node receives a dbx signature with its own ID in the
destination field, the node has been identified as the slave for a
database exchange. The task is, then, to ensure that information is
exchanged to remove the discrepancies between the link-state
databases of the master and the slave.
Thus, the slave must identify which LSA messages it must retransmit,
in order to bring the information in the master up-to-date. The
slave must then proceed to rebroadcast those LSA messages.
More precisely, the slave rebroadcasts the LSA messages which match
the following criteria:
- the age belongs to the age interval indicated in the dbx
signature, AND
- the prefix corresponds to a signed prefix in the dbx
signature, where the signature generated by the master
differs from the signature as calculated within the slave
for the same segment of the link-state database.
When a node is triggered to perform a database exchange it generates
a new LSF with TTL equal to 1 (one hop only) and fills it with the
update LSAs. These LSAs must indicate the age featured at the moment
in the database, from which they are taken.
Optionally, the host can use a new type of LSF (denoted an LSF-D)
which, contrary to the one hop LSF described above, is retransmitted
as a normal LSF making use of MPRs. An LSF-D is transmitted with TTL
equal to infinity. Upon receiving of such a packet, successive nodes
remove from the LSF-D the LSAs already present in their database
before retransmitting the LSF-D. If the LSF-D is empty after such a
processing, a node will simply not retransmit the LSF-D. The use of
LSF-D packets is more efficient for fast wide-area database updates
in case of merging of two independent wireless networks.
Clausen, Baccelli, Jacquet [Page 14]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
7.3. The Designated Router
There are no changes to the the section 7.3 in [WOSPF]. Designated
routers are not elected on wireless networks.
7.4. The Backup Designated Router
There are no changes to the the section 7.4 in [WOSPF]. Backup
designated routers are not elected on wireless networks.
8. Protocol Packet Processing
This section defines extensions to the processing described in
section 8 in [OSPF] and [WOSPF].
The processing of Signature Packets is documented in section 7.2.
9. Interface Data Structure
There are no changes to the interface data structure described in
section 9 in [WOSPF].
10. Neighbor Data Structure
There are no changes to the neighbor data structure described in
section 10 in [WOSPF].
11. Routing Table Structure
There are no changes to the routing table structure described in
section 11 in [WOSPF] and [OSPF].
12. Link State Advertisements
There are no changes to the link state advertisements described in
section 12 in [WOSPF].
Clausen, Baccelli, Jacquet [Page 15]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
13. The Flooding Procedure
There are no changes to the flooding procedure described in section
13 of [WOSPF].
14. Aging the Link State Database
There are no changes to the aging described in section 14 in [OSPF].
15. Virtual Links
There are no changes to the virtual links described in section 15 in
[OSPF].
16. Calculation of the Routing Table
There are no changes to the calculation described in section 16 in
[OSPF].
A. OSPF Data Formats
This section defines extensions to section A in [WOSPF].
The wireless database exchange mechanism introduces a new packet type
8: signature packets.
A.1. Signature Packet Format
Clausen, Baccelli, Jacquet [Page 16]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version # | 8 | Packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Area ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Checksum | AuType |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| AgeMin | AgeMax |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Reserved | Secondary signature key |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Prefix Signature |
| |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Prefix Signature |
| |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ (etc.) +
| |
Version #, Packet length, Router ID, Area ID, Checksum, AuType and
Authentication fields are the OSPF control packet header as
described in [OSPF]
AgeMin, AgeMax
AgeMin and AgeMax defines the age interval [AgeMin,AgeMax],
used for computing the timed partial signatures in the prefix
signatures as described in section 2.1.
Type
Specifies if the signature is an info or a dbx signature,
Clausen, Baccelli, Jacquet [Page 17]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
according to the following:
Value Type
==================================
1 info (informative)
2 dbx (database exchange)
Reserved
Must be set to "00000000" for compliance with this
specification.
Secondary signature key
The key of the secondary signature is a random number of 32
bits. Used for computing the secondary partial signature as
described in section 2.1.
Destination
if the signature is of type = 2, then this field contains
the address of the slave, with which a database exchange is
requested.
if the signature is of type = 1, then this field must contain
the following "000000000000000000000000000000"
Prefix signature
the set of prefixes signatures contains the sub-signatures
for different parts of the link-state database. The layout
of
the prefix signatures is detailed in section 4.2.
A.2. Prefix Signature Format
Clausen, Baccelli, Jacquet [Page 18]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved | Prefix length | # of LSAs |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Primary partial signature | Secondary parial signature |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Timed # of LSAs | Timed partial signature |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Prefix identifier and Prefix length
indicates the length of the prefix for the part of the
link-state database, as well as the exact prefix.
# of LSAs
the number of LSAs in the emitting nodes link-state database,
matching by the prefix identifier and prefix legth.
Primary partial signature
the arithmetic sum of the CRCs of each string made of the
concatenation of sequence number and LSA-originator ID fields
of the tuples (LSA-originator ID, LSAsequence-number,
LSA-age) from the emitting nodes link-state database such
that the LSA-originator ID and prefix ID has same prefix of
length prefix-length.
Secondary partial signature
the arithmetic sum of the XOR between the secondary
signature key and each of the CRCs of each string made of the
concatenation of sequence number and LSA-originator ID fields
of the tuples (LSA-originator ID, LSAsequence-number,
LSA-age) from the emitting nodes link-state database such
that the LSA-originator ID and prefix ID has same prefix of
length prefix-length.
Timed # of LSAs
the number of LSAs in the emitting nodes link-state database,
matching by the prefix identifier and prefix legth and
satisfying the condition that the LSA age is between AgeMin
and AgeMax.
Clausen, Baccelli, Jacquet [Page 19]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
Timed partial signature
the arithmetic sum of the CRCs of each string made of the
concatenation of sequence number and LSA-originator ID fields
of the tuples (LSA-originator-ID,LSA sequence-number,
LSA-age) from the emitting nodes link-state database such
that:
- Prefix ID and LSA-originator ID has same prefix of length
prefix-length
- LSA-age is between AgeMin and AgeMax.
B. Architectural Constants
There are no changes to the constants documented in section B in
[OSPF].
C. Configurable Constants
There are no changes to the constants described in section C in
[OSPF] and [WOSPF].
D. Authentication
There are no changes to the authentication described in section D in
[OSPF].
E. An Algorithm for Assigning Link State IDs
There are no changes to the algorithm described in section E in
[OSPF].
F. Multiple Interfaces to the same Network/Subnet
There are no changes to the section F in [OSPF].
G. Differences from RFC 2178
There are no changes to section G in [OSPF].
Clausen, Baccelli, Jacquet [Page 20]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
H. Signature Hashing Calculation
A signature message is a tuple:
signature message = (age interval, key, {prefix signature}+)
with a each prefix signature from the set being defined as:
prefix signature = (prefix, sign(prefix))
The signature for a prefix is constructed thus:
sign(prefix) = (primary partial signature, #LSA,
secondary partial signature,
timed partial signature, timed #LSA)
A primary partial signature for a prefix is computed as a sum overall
LSAs in a nodes link-state database where the prefix matches the
adverticing router of the LSA:
primary partial signature = sum_p (CRC(LSA-identifier))
With sum_p denoting the sum over prefixes matching the adverticing
router of the LSA.
The secondary partial signature for a prefix is computed as a sum
over all LSAs in a nodes link-state database, where the prefix
matches the adverticing router of the LSA:
secondary partial signature = sum_p (CRC(LSA-identifier)) * key
With sum_p denoting the sum over prefixes matching the adverticing
router of the LSA.
The timed partial signature for a prefix and an age interval is
computed as the sum over LSAs in a nodes link-state database where:
- the prefix matches the adverticing router of the LSA,
- the age falls within the age interval of the
advertisement.
Its expression is then the following:
timed partial signature = sum_p_t (CRC(LSA-identifier))
With sum_p_t denoting the sum over prefixes matching the adverticing
router of the LSA and where the age falls within the age interval of
Clausen, Baccelli, Jacquet [Page 21]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
the advertisement.
The LSA identifier is the string, obtained through concaternating the
following fields from the LSA header:
- LS type
- LS ID
- Adverticing router
- LSA sequence number
I. Applicability Scenarios
This section outlines the applicability of the specified mechanisms
in a set of common scenarios.
I.1. Emerging node
When a new node emerges in an existing network, the initialization
time for that node is the time until it has acquired link-state
information, allowing it to participate fully in the network.
Ordinarily, this time is determined solely by the frequency of
control traffic transmissions. In order to reduce the initialization
time, the database exchange mechanisms can be employed as soon as the
node has established a relationship with one neighbor node already
initialized. This emerging node will select a neighbor as slave and
transmit a dbx signature of the form ([age min, age
max],{(*,signature(*)}), "*" implying an empty prefix. The slave
will respond by, effectively, offering its entire link-state database
to the master. In particular in situations where the some LSAs are
not transmitted frequently (outside LSAs would be an example of
such), this mechanism may drastically reduce the initialization time
of new nodes in the network.
I.2. Merging Wireless Clouds
Two disjoint sets of nodes, employing [WOSPF] as their routing
Clausen, Baccelli, Jacquet [Page 22]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
protocol, may at some point merge or join -- i.e. that a direct
(radio) link is established. Prior to the merger, the respective
clouds are "stable", periodically broadcasting consistent info
signatures within their respective networks. At the point of merger,
at least two nodes, one from each network, will be able to establish
a direct link and exchange control traffic. The combined network is
now in an unstable state, with great discrepancies between the link-
state databases of the nodes in the formerly two networks. Employing
signature and database exchanges through the LSF-D mechanism, the
convergence time until a new stable state is achieved can be kept at
a minimum.
I.3. Acknowledgments
If a node wants a specific LSA to be reliably transmitted to its
neighbor, the db signature mechanism can be employed outside of
general periodic signature consistency check. The node transmitting
the LSA message broadcasts an info signature, containing the full
LSA-originator ID as signed prefix and a very narrow age interval,
centered on the age of the LSA which is to be reliably transmitted.
A neighbor which does not have the LSA in its database will therefore
automatically trigger a database exchange concerning this LSA and
send a dbx signature containing the LSA-originator ID signed with an
empty signature. The receiving of such a dbx signature will trigger
the first node to retransmit the LSA right away with a new LSF to
ensure that the LSA does get through.
J. Security Considerations
This doccument does currently not discuss security considerations.
K. IANA Considerations
An OSPF packet number needs be assigned for the signature packet.
L. Authors' Addresses
Thomas Heide Clausen, Project HIPERCOM, INRIA Rocquencourt, BP 105,
78153 Le Chesnay Cedex, France, Phone: +33 1 3963 5133, Email:
Thomas.Clausen@inria.fr
Clausen, Baccelli, Jacquet [Page 23]
INTERNET-DRAFT DB Exchange for OSPFv2 Wireless Interfaces 06 Feb 2004
Emmanuel Baccelli Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153
Le Chesnay Cedex, France, Phone: +33 1 3963 5889, Email:
Emmanuel.Baccelli@inria.fr
Philippe Jacquet, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153
Le Chesnay Cedex, France, Phone: +33 1 3963 5263, Email:
Philippe.Jacquet@inria.fr
M. References
[WOSPF] J. Ahrenholz, T. Henderson, P. Spangnolo, P. Jacquet,
E. Bacelli, T. Clausen.
"OSPFv2 Wireless Interface Type",
draft-spagnolo-manet-ospf-wireless-interface-00.txt,
November 2003, work in progress.
[OSPF] Moy, J., "OSPF Version 2", RFC 2328, April 1998.
[ISIS] D. Oran, "OSI IS-IS Intra-domain Routing Protocol,"
RFC 1142, http://ietf.org/rfc/rfc1142.txt, 1990.