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.