INTERNET-DRAFT Philippe Jacquet IETF MANET Working Group Paul Muhlethaler Expiration: 24 May 2001 Amir Qayyum Anis Laouiti Laurent Viennot Thomas Clausen INRIA Rocquencourt, France 24 November 2000 Optimized Link State Routing Protocol draft-ietf-manet-olsr-03.txt Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026 except that the right to produce derivative works is not granted. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract This document describes the Optimized Link State Routing (OLSR) protocol for mobile ad hoc networks. The protocol is an optimization of the pure link state algorithm tailored to the requirements of a mobile wireless LAN. The key concept used in the protocol is that of multipoint relays (MPRs) [1] & [2]. MPRs are selected nodes which forward broadcast packets during the flooding process. This technique substantially reduces the packet overhead as compared to pure flooding mechanism where every node retransmits the packet when it receives the first copy of the packet. In OLSR protocol, the information flooded in the network "through" these multipoint relays is also "about" the multipoint relays. Thus a Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 1] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 second optimization is achieved by minimizing the "contents" of the control packets flooded in the network. Hence, as contrary to the classic link state algorithm, only a small subset of links with the neighbor nodes are declared instead of all the links. This information is then used by the OLSR protocol for route calculation. As a consequence hereof, the routes contain only the MPRs as intermediate nodes from a Source to a Destination. OLSR provides optimal routes (in terms of number of hops). The protocol is particularly suitable for large and dense networks as the technique of multipoint relays works well in this context. Contents Status of This Memo 1 Abstract 1 1. Introduction 3 2. Changes 3 3. OLSR terminology 4 4. Applicability Section 5 4.1 Networking Context 5 4.2 Protocol Characteristics and Mechanisms 5 5. Protocol Overview 7 6. Multipoint relays 9 7. Protocol functioning 10 7.1 Packet format 10 7.1.1 Packet Header 11 7.1.2 Message Header 12 7.1.3 Packet Processing 12 7.2 Neighbor sensing 13 7.2.1 HELLO message broadcast 13 7.2.2 HELLO message processing 16 7.3 Multipoint relay selection 19 7.4 Multipoint relay information declaration 20 7.4.1 TC message broadcast 20 7.4.2 TC message processing 23 7.5 Routing table calculation 25 7.6.Link layer notification 27 8. Packet Forwarding 27 8.1 Data packet forwarding 27 8.2 OLSR message forwarding 28 9. Proposed values for constants 28 10. References 29 11. Authors' addresses 30 Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 2] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 1. Introduction This Optimized Link State Routing protocol inherits the concept of forwarding and relaying from HIPERLAN (a MAC layer protocol) which is standardized by ETSI [3]. The OLSR protocol is developed in the IPANEMA project (part of Euclid program) and in the PRIMA project (part of RNRT program). This protocol is developed for mobile ad hoc networks. It operates as a table driven or proactive protocol and exchanges topology information with other nodes of the network at regular intervals. The nodes which are selected as a multipoint relay by some neighbor nodes announce this information periodically in their control messages. The protocol uses the multipoint relays to facilitate efficient flooding of control messages in the network. In route calculation, the multipoint relays are used to form the route from a given node to any destination in the network. Multipoint relays are selected by a node among its one hop neighbors with "symmetric", i.e. bi-directional, link. Therefore, selecting the route through multipoint relays automatically avoids the problems associated with data packet transfer on uni-directional links (such as the problem of getting the link-layer acknowledgement for the data packets at each hop) The OLSR protocol is developed to work independently from other protocols. But it can be adapted to operate with a protocol (like IMEP [4]) which could provide common functionalities such as neighbor sensing, multipoint relaying, security authentication, etc. 2. Changes Major changes from version 02 to version 03 - Introduction of assigned port number for use with OLSR - The packet format now uses "message length" rather than an offset to the next message - Optional section describing how link-layer notifications can be utilized included. Major changes from version 01 to version 02 - Introduction of a unified packet format for encapsulation of all messages being exchanged between nodes. This also serves to facilitate extensions in future versions of the protocol (i.e. introduction of new protocol messages) without breaking backwards compatibility. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 3] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 - Removal of "Power Conservation" from this draft. Power Conservation may be considered as an extension to the basic routing capabilities, and the information is therefore moved to draft-ietf-manet-olsr-extensions-00.txt. 3. OLSR Terminology The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECCOMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC2119 [9]. The OLSR protocol uses the following terminology, in addition to the terms defined in [5]. connection A communication channel or medium *on the same physical interface*, over which the nodes can communicate with each other. holding time The lifetime associated with an entry in any table. An entry is kept in the table for a period of time, equal to its holding time. If the entry is not refreshed during this period, it is removed from the table when the holding time expires. multipoint relay (MPR) A node which is selected by its one-hop neighbor, node X, to "re-transmit" all the broadcast packets that it receives from X, provided that the same packet is not already received, and the hop count field of the packet is greater than zero. multipoint relay selector (MPR-S) A node which has selected its one-hop neighbor, node X, as its multipoint relay, will be called a multipoint relay selector of node X. node A MANET router which implements this Optimized Link State Routing protocol. symmetric link A bi-directional *link* (not connection) between two neighbor nodes, i.e. node X and node Y where both can hear each other. This bi-directional link can be a union of two oppositely-directed uni-directional connections using different interfaces. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 4] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 4. Applicability Section This section dictates the characteristics of the OLSR protocol as specified in the Applicability Statement draft [6]. 4.1. Networking Context The protocol is best suited to large and dense networks, as the optimization achieved using the multipoint relays works well in this context. The larger and more dense a network, the more optimization can be achieved as compared to the normal link state algorithm. OLSR uses hop-by-hop routing, i.e. each node uses its most recent information to route packets. Thus when a node is moving, its speed should be such that its movement could be followed in *at least* its neighborhood, in order to correctly route packets to the destination. This protocol is best suited for networks where the traffic is random and sporadic between "several" nodes rather than being almost exclusively between a small specific set of nodes in the network. The performance of the protocol when comparing to a reactive protocol is even better if these [source, destination] pairs change with time [8]. Such changes may initiate substantial traffic (Query flooding) in case of reactive protocol, but nothing in OLSR, as the routes are maintained for each known destination all the time. 4.2. Protocol Characteristics and Mechanisms * Does the protocol provide shortest path routes ? Yes. * Does the protocol provide support for unidirectional links? (if so, how?) No. It uses only bi-directional links (like in 802.11), but these links may be composed of oppositely directed uni-directional "connections". * Does the protocol require the use of tunneling? (if so, how?) No. * Does the protocol require using some form of source routing? (if so, how?) No. The protocol uses hop-by-hop routing. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 5] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 * Does the protocol require the use of periodic messaging? (if so, how?) Yes. Periodically, each node in the network sends a message containing the addresses of the neighbors which have selected that node as a multipoint relay. This information enables other nodes to build routes to that node through the multipoint relays. * Does the protocol require the use of reliable or sequenced packet delivery? (if so, how?) No. As the packets are sent periodically, they need not be sent reliably. Each packet not only contains a unique Packet Sequence Number, but it also contains the sequence number for the most recent information (for example "MPR Sequence Number" in the TC packet), so un-sequenced delivery of packets will also not create any problem. * Does the protocol provide support for routing through a multi- technology routing fabric? (if so, how?) Yes. Each network interface is assigned a unique IP address. * Does the protocol provide support for multiple hosts per router? (if so, how?) Yes. The concept of RID [4] may be used to associate to a single RID (which can also be a unique IP address) more than one IP addresses which represent different hosts associated to the router. * Does the protocol support the IP addressing architecture? (if so, how?) Yes. * Does the protocol require link or neighbor status sensing (if so, how?) Yes. The protocol requires the link status sensing. This service is provided by sending/receiving periodic HELLO messages to/from one hop neighbors. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 6] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 * Does the protocol depend on a central entity? (if so, how?) No. All the routers in the network have their own routing tables and do not depend on any specific node. * Does the protocol function reactively? (if so, how?) No. But it decreases and increases the interval (within certain limits) of sending the TC packet periodically, depending upon the rate of link changes in its neighborhood. * Does the protocol function proactively? (if so, how?) Yes. It periodically sends the information about its multipoint relay selectors, which helps other nodes to build routes to it. * Does the protocol provide loop-free routing? (if so, how?) As the protocol uses a link state algorithm, the routing is loop-free when in a stable state. * Does the protocol provide for sleep period operation? (if so, how?) Yes, OLSR can provide support for sleep period operation. To enable this feature, a node should select its multipoint relays from among those neighbors which can (or agree to) store its packets while it is in sleep mode. * Does the protocol provide some form of security? (if so, how?) No, not itself. It can use other protocols (like IMEP [4]) which provide authentication and security. * Does the protocol provide support for utilizing multi-channel, link-layer technologies? (if so, how?) Yes. 5. Protocol Overview OLSR is a proactive routing protocol for mobile ad hoc networks. The protocol inherits the stability of a link state algorithm and has the advantage of having the routes immediately available when needed due to its proactive nature. OLSR is an optimization over the pure link state protocol, tailored for mobile ad hoc networks. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 7] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 Firstly, it reduces the size of the control packets: rather than declaring all links, a node declares only a subset of links with its neighbors, namely the links to those nodes which are its multipoint relay selectors (see section 6 on Multipoint Relays). Secondly, OLSR minimizes flooding of control traffic by using only selected nodes, called multipoint relays, to diffuse its messages. This technique significantly reduces the number of retransmissions in a flooding or broadcast procedure. The protocol MAY optimize the reactivity to topological changes by reducing the time interval for periodic control message transmission. Furthermore, as OLSR protocol keeps the routes for all destinations in the network, the protocol is beneficial for traffic patterns where a large subset of nodes are communicating with another large subset of nodes, and where the [source,destination] pairs are changing over time. The protocol is particularly suited for large and dense networks, as the optimization done using the multipoint relays works well in this context. The larger and more dense a network, the more optimization can be achieved as compared to the normal link state algorithm. The protocol is designed to work in a completely distributed manner and thus does not depend on any central entity. The protocol does NOT REQUIRE reliable transmission for control messages: each node sends control messages periodically, and can therefore sustain an occasional loss of some packets. Such losses occur very often in the radio networks due to collisions or other transmission problems. Also, the protocol does NOT REQUIRE sequenced delivery of messages. Each control message contains a sequence number which is incremented for each message. Thus the recipient of a control packet can easily identify which information is newer - even if messages have been re-ordered while in transmission. Furthermore, OLSR provides support for protocol extensions such as sleep mode operation, multicast-routing etc. Such extensions may be introduced as additions to the protocol without breaking backwards compatibility with earlier versions. OLSR performs hop by hop routing, i.e. each node uses its most recent information to route the packet. Hence for OLSR to be able to route packets, the speed of mobile nodes should be limited such that their movements can be tracked, at least by their neighborhood. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 8] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 OLSR does NOT REQUIRE any changes to the format of IP packets. Thus any existing IP stack can be used as it is: the protocol only interacts with routing table management. 6. Multipoint Relays The idea of multipoint relays is to minimize flooding of broadcast messages in the network by reducing duplicate retransmissions in the same region. Each node in the network selects a set of nodes in its neighborhood which may retransmit its packets. This set of selected neighbor nodes is called the multipoint relay (MPR) set of that node. The neighbors of node N which are *NOT* in its MPR set, receive and process broadcast messages but do not retransmit broadcast messages received from node N. Each node selects its MPR set among its one hop neighbors. This set is selected such that it covers (in terms of radio range) all the nodes that are two hops away. The neighborhood of any node N can be defined as the set of nodes which have a symmetric link to N. The two hop neighborhood of N can be defined as the set of nodes which don't have a symmetric link to N but have a symmetric link to the neighborhood of N. The multipoint relay set of N, denoted as MPR(N), is then an arbitrary subset of the neighborhood of N which satisfies the following condition: every node in the two hop neighborhood of N must have a symmetric link toward MPR(N). The smaller the multipoint relay set is, the more optimal is the routing protocol. [2] gives an analysis and example about multipoint relay selection algorithms. Each node maintains information about a set of its neighbors. This is the set of neighbors, called the "Multipoint Relay Selectors", which have selected the node as a MPR. A node obtain this information from the periodic HELLO messages received from the neighbors. A broadcast message, intended to be diffused in the whole network, coming from these MPR Selector neighbor nodes is assumed to be retransmitted by the node. This set can change over time (i.e. when a node selects another MPR-set) and is indicated by the selector nodes in their HELLO messages. Each node has a specific Multipoint relay Selector Sequence Number (MSSN) associated with this set. Whenever its MPR selector set is updated, the node also increments its MSSN. OLSR relies on selection of multipoint relays, and calculates the routes to a destination through these nodes. I.e. MPR nodes are selected as intermediate nodes in the path between a source and a Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 9] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 destination. To implement this, each node in the network periodically broadcast the information describing which neighbors have selected it as a multipoint relay. Upon receipt of this "MPR Selectors" information, each node calculates or updates the route to each known destination. So principally, the route is a sequence of hops through the multipoint relays from source to the destination. Multipoint relays are selected among the one hop neighbors with "symmetric" i.e. bi-directional link. Therefore, selecting the route through multipoint relays automatically avoids the problems associated with data packet transfer on uni-directional links such as the problem of getting an acknowledgement for the data packets at each hop. 7. Protocol Functioning In this section we describe the details of the protocol functioning. This includes descriptions of the format and contents of the packets being exchanged by routers, the algorithms (e.g. for packet handling and routing table calculation) and suggested data structures internally in each router. 7.1. Protocol and Port Number Packages in OLSR are communicated using UDP. Port 698 has been assigned by IANA for exclusive usage by the OLSR protocol. 7.1. Packet Format OLSR communicates using an unified packet format for all data related to the protocol. Inspired by the concept of "extension headers" from IPv6, the purpose of this is to facilitate extensibility of the protocol without breaking backwards compatibility as well as to provide an easy way of piggybacking different "types" of information into a single transmission. These packets are embedded in UDP datagrams for transmission over the network. The present draft uses IPv4 addresses. The support for IPv6 will be described in a future draft. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 10] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 The basic layout of any packet in OLSR will be as follows: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Packet Length | Reserved for future use | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Type | Reserved |B| Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | : : : MESSAGE : : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Type | Reserved |B| Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | : : : MESSAGE : : : | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : (etc) 7.1.1. Packet Header Packet Length The length (in bytes) of the packet Reserved for future use MUST be set to '0000000000000000' to be in compliance with this version of the draft. The information in the header of this packet is equivalent to the information obtainable from the UDP header. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 11] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 7.1.2. Message Header Message Type This field indicates which type of message are to be found in the "MESSAGE" partition. Message types in the range of 0-127 are reserved for messages in this draft and in draft-ietf-manet-olsr-extensions-00.txt. B This field indicates to a node whether the message is meant for diffusion into the entire network. This enables a node to forward messages correctly, even if it doesn't recognize the "Message Type". Reserved MUST be set to '0000000' to be in compliance with this version of the draft. Message Size This field gives the size of this message, measured from the beginning of the "Message Type" field and until the beginning of the next "Message Type" field (or - if there are no following messages - the end of the packet). 7.1.3. Packet Processing Upon receiving such a basic packet, the protocol parser examines each of the "extension headers". Based on the value of the "Message Type" field, the parser can determine the faith of the data portion of the message: 1. If the data are of a type which the receiving node can process, then this data is processed. 2. Otherwise, if the "Message Type" indicates a type, unknown to the node, the message SHOULD silently be dropped. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 12] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 By defining a set of message types, which MUST be recognized by all implementations of OLSR, it will be possible to extend the protocol through introduction of additional message types, while still be able to maintain compatibility with older implementations. The two REQUIRED message types for OLSR are: - HELLO-messages, performing the task of neighbor sensing. - TC-messages, performing the task of multipoint relay information declaration. Extensions may e.g. be PC-messages for enabling power conservation / sleep mode, multicast routing, gateway announcements etc. 7.2. Neighbor sensing 7.2.1. HELLO message broadcast Each node should detect the neighbor nodes with which it has a direct and symmetric link. The uncertainties over radio propagation may make some links asymmetric. Consequently, all links MUST be checked in both directions in order to be considered valid. To accomplish this, each node broadcasts HELLO messages, containing information about neighbors and their link status. The link status may either be "symmetric", "heard" (asymmetric) or "MPR". "Symmetric" indicates, that the link has been verified to be bi-directional, i.e. it is possible to transmit data in both directions. "Heard" indicates that the node is hearing from a neighbor, but it is not confirmed that this neighbor is also hearing from the node. "MPR" indicates, that a node is selected by the sender as multipoint relay. MPR status implies that the link is symmetric too. These control messages are broadcast to all one-hop neighbors, but are *not relayed* to further nodes. A HELLO-message contains at a minimum: - a list of addresses of neighbors, to which there exists a symmetric link; - a list of addresses of neighbors, which have been "heard"; - a list of neighbors, which have been selected as multipoint relays. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 13] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 The list of neighbors in a HELLO message can be partial (e.g. due to message size limitations, imposed by the network), the rule being that all neighbor nodes are cited at least once within a predetermined refreshing period (HELLO_INTERVAL). To accommodate for the above constraints, as well as to accommodate for future extensions, an approach similar to the overall packet format (see section 6.1) is taken. Thus the proposed format of a HELLO message is: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Sequence Number | MPR Sequence number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Type | Reserved | Link Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Type | Reserved | Link Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : : : (etc) This is sent as the data-portion of the general packet format described in 6.1, with the "Message Type" set to HELLO_MESSAGE and the broadcast field set to NO_BROADCAST. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 14] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 7.2.1.1. Description of the fields Message Sequence Number While generating a HELLO message, the node will assign a unique identification number to this message. This number is put into the Sequence Number field. This sequence number will be different for all the messages originated by that node. MPR Sequence Number This field indicates the sequence number corresponding to the most recent multipoint relay set, calculated by the sender node. Link Type This field specifies the type of link the sending node has to the following list of neighbors. As a minimum, the following three link types are REQUIRED by OLSR: - ASYM_LINK - indicating that the links between the sender and the neighbors in the following list are asymmetric (i.e. the neighbor is "heard"). - SYM_LINK - indicating that the links between the sender and the neighbors in the following list are symmetric. - MPR_LINK - indicating, that the nodes in the following list have been selected by the sender as multipoint relays. (Notice: this implies, that the links from the sender of the HELLO and to the nodes in the list are symmetric). It is possible to provide additional information by specifying additional link-types, e.g. LOST_LINK - indicating that the link between the sender and the neighbors in the following list has been lost. Upon processing a HELLO message, a node silently ignores link-types, which are unknown. Reserved This field is reserved for future usage, and MUST be set to 00000000 for compliance with this draft. Link Message Size The size of the link message, measured from the beginning of the "Link Type" field and until the next "Link Type" field (or - if there are no more link types - the end of the message). Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 15] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 Neighbor Address The address of a neighbor. 7.2.2. HELLO message processing The HELLO messages permit each node to acquire information about its neighborhood up to two hops. A node maintains a Neighbor table in which it records the information (obtained from the HELLO messages) about its one hop neighbors, the status of the link with these neighbors, a list of two hop neighbors that these one hop neighbors give access to, and an associated holding time. The information is recorded in the Neighbor table as a neighbor entry, with the following field names: 1. N_addr N_status N_2hop_list N_time 2. N_addr N_status N_2hop_list N_time 3. ,, ,, ,, ,, Each entry in the table consists of N_addr, N_status, N_2hop_list, and N_time. This specifies that the node with address N_addr is a one-hop neighbor to this node, the status of the link between them is N_status, and this neighbor provides access to the two hop neighbors listed in N_2hop_list. Each entry in N_2hop_list consists of a 2 hop neighbor address and associated holding time. The N_status can be ASYM_LINK, SYM_LINK or MPR_LINK. A link status of MPR_LINK implies that the link with the neighbor node N_addr is symmetric *AND* the node N_addr is selected as a multipoint relay by this node. Each neighbor entry has an associated holding time N_time, upon expiration of which it is no longer valid and hence MUST be removed. The node also contains a sequence number N_MPR_seq. This specifies that the node has selected its most recent MPR set with the sequence number N_MPR_seq. Every time a node selects or updates its multipoint relay set, N_MPR_seq is incremented to a higher value. This number is put into the HELLO messages as described in 6.2.1. Upon receiving a HELLO message, the node should update the neighbor entry corresponding to the sender node address (a node may - e.g. for security reasons - wish to restrict updating the neighbor-table, i.e. ignoring HELLO messages from some nodes): 1. If the entry already exists: 1.1 if the recipient of the HELLO has recorded the sender as asymetric: 1.1.1 if the node finds its own address among the addresses listed in the HELLO message (with Link Type ASYM_LINK, SYM_LINK or MPR_LINK), it updates the status of the link to the sender node as SYM_LINK and refreshes the N_time to NEIGHB_HOLDING_TIME. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 16] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 1.1.2 otherwise, if the node does not find its own address among the addresses listed in the HELLO message, it refreshes the N_time to NEIGHB_HOLDING_TIME. 1.2 otherwise, if the recipient of the HELLO has recorded the sender as symetric (or MPR): 1.2.1 if the node finds its own address among the addresses listed in the HELLO message (with Link Type ASYM_LINK, SYM_LINK or MPR_LINK), it refreshes the N_time to NEIGHB_HOLDING_TIME. 2. Otherwise, a new entry is recorded in the Neighbor table with: - N_addr is set to the address of the sender node, - N_status is set to the value of SYM_LINK if the node finds its own address (with Link Type ASYM_LINK, SYM_LINK or MPR_LINK) among the addresses listed in the HELLO message, and to the value of ASYM_LINK otherwise - N_time is set to the value of NEIGHB_HOLD_TIME The N_2hop_list of the entry of the sender is updated, as follows. For each address listed in the HELLO message with Link Type SYM_LINK or MPR_LINK: 1. if an entry with this address exists in the N_2hop_list, then the associated holding time is refreshed to NEIGHB_HOLD_TIME 2. otherwise an entry with this address and holding time NEIGHB_HOLD_TIME is added to the N_2hop_list. Based on the information obtained from the HELLO messages, each node construct its MPR Selector table. In this table, the node registers the addresses of those one hop neighbor nodes which have selected the node as a multipoint relay. The MPR Selector table may have the following format: 1. MS_addr MS_seq_num MS_time 2. MS_addr MS_seq_num MS_time 3. ,, ,, ,, Each entry in the table consists of MS_addr, MS_seq_num and MS_time, which specifies that the node with address MS_addr has selected this node as its multipoint relay with the MPR sequence number equal to MS_seq_num. Each entry has an associated holding time MS_time, upon expiation of which it is no longer valid and hence removed. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 17] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 A sequence number, MSSN, is associated with this table. This number specifies that the multipoint relay selector set of the node keeping this MPR Selector table is most recently modified with the sequence number MSSN. The node modifies its MPR Selector set according to the information it receives in the HELLO messages, and increment this sequence number upon each modification. Upon receiving a HELLO message, if a node finds its own address in the address list with a link type of "MPR", it MUST update the entry corresponding to the sender node's address in the MPR Selector table: 1. If the entry already exists: 1.1 if the MPR Sequence Number field of the HELLO message is greater than or equal to the MS_seq_num field of the entry in the table, then the MS_time is refreshed to NEIGHB_HOLD_TIME. 1.2 if the MPR Sequence Number field of the HELLO message is greater than the MS_seq_num field of that entry, the MS_seq_num field is updated to the value of MPR Sequence Number field of the HELLO message. 2. Otherwise, a new entry is recorded in the MPR Selector table, with: 2.1 MS_addr is set to the address of sender of the HELLO message 2.2 MS_seq_num is set to the MPR Sequence Number field of the HELLO message 2.3 MS_time is set to the value of NEIGHB_HOLD_TIME 2.4 MSSN is incremented to indicate that the MPR Selector table has been changed. If link layer information describing connectivity to neighboring nodes is available (i.e. loss of connectivity such as through absence of an acknowledgment), this MAY be used in addition to the information from the HELLO-messages to maintain the neighbor table and the MPR selector table. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 18] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 7.3. Multipoint relay selection Each node in the network selects independently its own set of multipoint relays. Multipoint relays are used to flood the control messages of that node into the network. The MPR set is calculated in a way such that it contains a subset of one hop neighbors which covers all the two hop neighbors. This means, that the union of the neighbor sets of all MPRs contains the entire two hop neighbor set. In order to build the list of the two hop nodes, make the union of N_2hop_lists of all neighbors (with Link Type SYM_LINK or MPR_LINK), then remove from this union the one-hop neighbors (with Link Type SYM_LINK or MPR_LINK), and finally remove the node itself. Multipoint relays of a given node are declared in the subsequent HELLOs transmitted by this node, so that the information reaches the multipoint relays themselves. These selected multipoint relays are indicated in the HELLO messages with a link status of "MPR". The multipoint relay set is re-calculated when: - a change in the neighborhood is detected, i.e. either a symmetric link with a neighbor is failed, or a new neighbor with a symmetric link is added; or - a change is detected in the two-hop neighborhood such that a symmetric link is either detected or broken between a two-hop neighbor and a neighbor. The MPR set needs not be optimal. However it SHOULD be small enough to achieve the benefit of the multipoint relays. The concept of multipoint relays is an optimization of a pure flooding mechanism. It is not essential that the multipoint relay set be minimal or optimal. But it is essential that all two-hop neighbors can be reached through the selected MPR's. By default, the multipoint relay set can coincide with the entire neighbor set. This will be the case at network initialization. Each node will manage a dedicated sequence number in order to track the changes in its multipoint relay set. This sequence number will also appear, along with the MPR list, in the HELLO messages. We propose a heuristic for the selection of multipoint relays [2]. We use the following terminology in describing this algorithm: MPR(x): Multipoint relay set of node x which is running this algorithm N(x): One hop neighbor set of node x (containing only symmetric neighbors) Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 19] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 N2(x): Two hop neighbor set of node x (containing only symmetric neighbors of nodes in N(x) ). The two hop neighbor set N2(x) of node x does not contain any one hop neighbor of node x D(x,y): Degree of one hop neighbor node y (where y is a member of N(x) ), is defined as the number of symmetric one hop neighbors of node y EXCLUDING the node x and all the symmetric one hop neighbors of node x, i.e., D(x,y) = number of elements of N(y) - {x} - N(x) The proposed heuristic is as follows: 1. Start with an empty MPR(x) 2. Calculate D(x,y), where y is a member of N(x), for all nodes in N(x) 3. First select as MPRs those nodes in N(x) which provide the "only path" to reach some nodes in N2(x) 4. While there still exist some nodes in N2(x) that are not covered by MPR(x): 4.1 For each node in N(x), calculate the number of nodes in N2(x) which are not yet covered by MPR(x) and are reachable through this one hop neighbor; 4.2 Select as a MPR that node of N(x) which reaches the maximum number of uncovered nodes in N2(x). In case of a tie, select that node as MPR whose D(x,y) is greater. 5. To optimize, process each node y in MPR(x), one at a time, and if MPR(x) - {y} still covers all nodes in N2(x) then remove y from MPR(x) After selecting the multipoint relays among the neighbors, the link status of the corresponding one hop neighbors is changed from SYM_LINK to MPR_LINK in the neighbor table. MPR_Seq_Num value in the Neighbor table is also incremented by one. 7.4. Multipoint relay information declaration 7.4.1. TC Message Broadcast In order to build the topology information database needed for routing the packets, each relay node broadcasts specific service messages called Topology Control (TC) messages. TC messages are Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 20] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 forwarded, like usual broadcast messages, to all nodes in the network and take advantage of multipoint relays. Multipoint relays enable a better scalability in the distribution of topology information [1]. A TC message is sent by a node in the network to declare its MPR Selector set. I.e., the TC message contains the list of neighbors which have selected the sender node as a multipoint relay. The sequence number (MSSN) associated with this multipoint relay selector set is also sent with the list. The list of addresses can be partial in each TC message (e.g. due to message size limitations, imposed by the network), but parsing of all TC messages describing a nodes MPR selector set MUST be complete within a certain refreshing period (TC_INTERVAL). The information diffused in the network by these TC messages will help each node to calculate its routing table. A node which has an empty MPR Selector set, i.e. nobody has selected it as a multipoint relay, MUST NOT generate any TC message. A node MAY transmit additional TC-messages to increase its reactiveness to link failures. I.e. when a change to the MPR selector set is detected and this change can be attributed to a link failure, a TC-message SHOULD be transmitted after a shorter interval than TC_INTERVAL. The proposed format of a TC message is 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Sequence Number | MSSN | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hop Count | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multipoint Relay Selector Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multipoint Relay Selector Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ This is sent as the data-portion of the general message format described in 6.1, with the "Message Type" set to TC_MESSAGE and the broadcast field set to BROADCAST. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 21] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 7.4.1.1. Description of the fields Message Sequence Number While generating the TC message, the "originator" node will assign a unique identification number to this message, and will put this number in the Sequence Number field. This sequence number will be different for all messages originated by that node, and will be used to recognize duplicate reception of messages. MPR Selector Sequence Number (MSSN) A sequence number is associated with the multipoint relay selector set. Every time a node detects a change in its multipoint relay selector set, it increments this sequence number. This number is sent in this MSSN field of the TC message to keep track of the most recent information. When a node receives a TC message, it can decide on the basis of this MPR Sequence Number, whether or not the received information about the multipoint relay selectors of the originator node is more recent than what it already has. Hop Count This field will contain the maximum number of hops a TC message can attain. Every time a TC message is re-transmitted, this field is decremented by 1. When this field reaches zero, the TC message is no more re-transmitted and is discarded. Reserved This field is reserved for future usage, and MUST be set to '000000000000000000000000' for compliance with this draft. Originator Address This field contains the address of the node, which has originally generated this TC message. This field MUST not be confused with the source read in the UDP header, which is changed each time to the address of the intermediate node which is "re-transmitting" this TC message. The Originator Address field is *never* changed in the retransmissions. Multipoint Relay Selector Address (MPR-S) This field contains the address of a node, which has selected the Originator node (of the TC message) as a multipoint relay. All addresses of the multipoint relay selectors of the Originator node are put in the TC message. If the maximum allowed message size (as imposed by the network) is reached Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 22] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 while there are still multipoint relay selector addresses which which have not been inserted into the TC-message, more TC messages will be generated until the entire MPR selector set has been sent. 7.4.2. TC Message Processing In the OLSR protocol, TC messages are broadcasted and are retransmitted by the multipoint relays in order to diffuse the messages in the entire network. In this process, a node MAY receive the same TC message more than once. To avoid re-processing of a TC message which was already received and processed, each node maintains a Duplicate table. In this table, the node records information about the most recently received TC messages. The information is recorded in the Duplicate table as Duplicate entries. The table may have the following format: 1. D_addr D_seq_num D_time 2. D_addr D_seq_num D_time 3. ,, ,, ,, Each entry in the table consists of D_addr, D_seq_num and D_time, which specifies that a TC message was received, originating from the node with address D_addr, having the message sequence number as D-seq_num. Each Duplicate entry also has an associated holding time D_time, upon expiration of which it is no longer valid and hence MUST be removed. Upon receiving a TC message, a node checks in its Duplicate table to see if it has already received the same message. If it finds a corresponding entry, the message is discarded. Otherwise, a new entry is recorded in the Duplicate table for this newly received TC message, and the message is processed. When a node receives a TC message from a neighbor node with which it has an asymmetric (or uni-directional) link, it neither registers the message in the Duplicate table nor it processes the message. Each node in the network maintains a topology table, in which it records the information about the topology of the network as obtained from the TC messages. Based on this information, the routing table is calculated. A node records information about the multipoint relays of other nodes in the network in its topology table as a topology entry, which may have the following format: Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 23] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 1. T_dest T_last T_seq T_time 2. T_dest T_last T_seq T_time 3. ,, ,, ,, ,, Each entry in the table consists of T_dest, T_last, T_seq, and T_time, which specifies that the node T_dest has selected the node T_last as a multipoint relay and that the node T_last has announced this information of its multipoint relay selector set with the sequence number T_seq. Therefore, the node T_dest can be reached in the last hop through the node T_last. Each topology entry has an associated holding time T_time, upon expiration of which it is no longer valid and hence MUST be removed. The entries in the topology table are recorded with the topology information that is exchanged through TC messages. After registering a TC message in the duplicate table, the following procedure is executed to record the information in the topology table: 1. If there exist some entry in the topology table whose T_last corresponds to the originator address of the TC message and whose T_seq is greater in value than the MSSN in the received message, then no further processing of this TC message is performed and it is silently discarded (case: message received out of order). 2. All entries in the topology table with T_last corresponding to the originator address of the TC message and whose T_seq is lesser in value than the MSSN in the received message, are removed. 3. For each of the MPR Selector address received in the TC message: 3.1 If there exist some entry in the topology table whose T_dest corresponds to the MPR Selector address and the T_last corresponds to the originator address of the TC message, then the holding time T_time of that topology entry is refreshed to TOP_HOLD_TIME. 3.2 Otherwise, a new topology entry is recorded in the topology table where: Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 24] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 - T_dest is set to this MPR Selector address, - T_last is set to the originator address of the TC message, - T_seq is set to the value of MSSN received in the TC message, - T_time is set to the value of TOP_HOLD_TIME. 7.5. Routing table calculation Each node maintains a routing table which allows it to route the messages for the other destinations in the network. The routing table is based on the information contained in the neighbor table and the topology table. Therefore, if any of these tables is changed, the routing table is re-calculated to update the route information about each destination in the network. The route entries are recorded in the routing table in the following format: 1. R_dest R_next R_dist 2. R_dest R_next R_dist 3. ,, ,, ,, Each entry in the table consists of R_dest, R_next and R_dist, which specifies that the node identified by R_dest is estimated to be R_dist hops away from the local node, and that the one hop neighbor node with address R_next is the next hop node in the route to R_dest. Entries are recorded in the table for each destination in the network for which the route is known. All the destinations for which the route is broken or partially known are not entered in the table. This routing table information is updated when a change is detected in the neighbor table, or the topology table. The update Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 25] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 of this routing table does not generate or trigger any messages to be transmitted, neither in the network, nor in the one-hop neighborhood. To construct the routing table of node X, a shortest path algorithm is run on the directed graph containing the arcs X -> Y where Y is any one hop neighbor of X (with Link Type SYM_LINK or MPR_LINK) and the arcs U -> V where there exists an entry in the topology table with V as T_dest and U as T_last. The following procedure is given as an example to calculate (or re-calculate) the routing table : 1. All the entries of the routing table are removed. 2. The new entries are recorded in the table starting with the one hop neighbors (h=1) as the destination nodes. For each neighbor entry in the neighbor table, whose Link Type is SYM_LINK or MPR_LINK, a new route entry is recorded in the routing table where R_dest and R_next are both set to the address of the neighbor and R_dist is set to 1. 3. Then the new route entries for the destination nodes h+1 hops away are recorded in the routing table. The following procedure is executed for each value of h, starting with h=1 and incrementing it by 1 each time. The execution will stop if no new entry is recorded in an iteration. 3.1 For each topology entry in the topology table, if its T_dest does not correspond to R_dest of any route entry in the routing table AND its T_last corresponds to R_dest of a route entry whose R_dist is equal to h, then a new route entry is recorded in the routing table where : - R_dest is set to T_dest; - R_next is set to R_next of the route entry whose R_dest is equal to T_last; and - R_dist is set to h+1. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 26] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 7.6 Link layer notification OLSR is designed to operate entirely alone, i.e. does not impose or expect any specific information from the link layer. However, if information from the link-layer is available, a node MAY use this as described in this section. If link layer information describing connectivity to neighboring nodes is available (i.e. loss of connectivity such as through absence of a link layer acknowledgment), this information is used in addition to the information from the HELLO-messages to maintain the neighbor table and the MPR selector table. Subsequently, detection of a link failure through a link-layer notification may trigger additional TC-messages to increase the protocols reactiveness to link failures. I.e. when a change to the MPR selector set is detected and this change can be attributed to a link failure, a TC-message SHOULD be transmitted. Thus, upon recieving a link-layer notification that the link between a node and any neighbor is broken, the following actions are taken: 1. if the link is broken to either a symetric or asymetric neighbor, the entry for that neighbor is removed from the neighbor table, 2. if the link is broken to a neighbor, which is selected as MPR, the entry for that neighbor is removed from the neighbor table and the MPR set is recalculated, 3. if the link is broken to a neighbor, which has selected this node as MPR, the Multipoint Selector Set is updated and a TC message SHOULD be generated. 8. Packet forwarding 8.1. Data packet forwarding Data packets are relayed on a hop by hop basis. In the source router and in any intermediate router, the next hop router is identified by the entry of the destination in the host routing table. Whenever a data packet is received to route to a destination and its TTL field (in IP header) is greater than zero, the node MUST examine the final destination field in the packet. If the route is known, i.e. an entry is found in the routing table in which R_dest corresponds to the final destination, then the packet is transmitted to the next hop node. Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 27] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 While forwarding a unicast packet, the originator address, and the final destination address of the packets are not changed. The packet traverses the intermediate source and destination pairs, hop by hop, until it reaches its final destination. 8.2. Topology Control message forwarding TC messages are relayed by the multipoint relays via the following rule: A node retransmits a TC message only when it is received from one of its multipoint relay selector AND it is registered in the duplicate table for the first time AND the hop count is greater than zero. Before retransmitting, the hop count is decremented by one. 9. Proposed values for the constants This section list the values for the constants used in the description of the protocol. HELLO_INTERVAL = 2 seconds TC_INTERVAL = 5 seconds TC_MIN_INTERVAL = 2 seconds NEIGHB_HOLD_TIME = 6 seconds TOP_HOLD_TIME = 15 seconds D_TIME = 30 seconds HELLO_PACKET = 1 TC_PACKET = 2 ASYM_LINK = 1 SYM_LINK = 2 MPR_LINK = 3 Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 28] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 10. References 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing reliability in cable free radio LANs: Low level forwarding in HIPERLAN. Wireless Personal Communications, 1996 2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An efficient technique for flooding in mobile wireless networks. INRIA research report RR-3898, 2000 3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN type 1, functional specifications ETS 300-652, ETSI, June 1996 4. Corson et al. Internet MANET Encapsulation Protocol. Internet draft, draft-ietf-manet-imep-spec-01.txt, Work in progress. 5. Perkins, C.E., Mobile Ad Hoc Networking Terminology, Internet draft, draft-ietf-manet-term-00.txt, work in progress. 6. Corson, S., MANET Routing Protocol Applicability Statement, Internet draft, draft-ietf-manet-appl-00.txt, Work in progress. 7. S. Bradner. Key words for use in RFCs to Indicate Requirement Levels. Request for Comments (Best Current Practice) 2119, Internet Engineering Task Force, March 1997. 8. Philippe Jacquet and Laurent Viennot, Overhead in Mobile Ad-hoc Network Protocols, INRIA research report RR-3965, 2000 Jacquet, Muhlethaler, Qayyum, Laouiti, Viennot and Clausen [Page 29] INTERNET-DRAFT Optimized Link State Routing 24 November 2000 12. Authors' Addresses Amir Qayyum Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le Chesnay Cedex, France Phone: +33 1 3963 5273 Email: Amir.Qayyum@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 Anis Laouiti Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le Chesnay Cedex, France Phone: +33 1 3963 5278 Email: Anis.Laouiti@inria.fr Laurent Viennot Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le Chesnay Cedex, France Phone: +33 1 3963 5278 Email: Laurent.Viennot@inria.fr Thomas Clausen Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le Chesnay Cedex, France Phone: +33 1 3963 5278 Email: Thomas.Clausen@inria.fr Jacquet, Muhlethaler, Qayyum et. al. Expires 18 May 2001 [Page 30]