idnits 2.17.1 draft-ietf-manet-olsr-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-03-29) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 16 longer pages, the longest (page 2) being 59 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There is 1 instance of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (18 November 1998) is 9263 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '1' on line 303 looks like a reference Summary: 11 errors (**), 0 flaws (~~), 2 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Draft Philippe Jacquet 2 IETF MANET Working Group Paul Muhlethaler 3 Expiration : 18 May 1999 Amir Qayyum 4 INRIA Rocquencourt, France 5 18 November 1998 7 Optimized Link State Routing Protocol 8 draft-ietf-manet-olsr-00.txt 10 Status of this Memo 12 This document is an Internet-Draft. Internet-Drafts are working 13 documents of the Internet Engineering Task Force (IETF), its areas, 14 and its working groups. Note that other groups may also distribute 15 working documents as Internet-Drafts. 17 Internet-Drafts are draft documents valid for a maximum of six months 18 and may be updated, replaced, or obsoleted by other documents at any 19 time. It is inappropriate to use Internet-Drafts as reference 20 material or to cite them other than as ``work in progress." 22 To view the entire list of current Internet-Drafts, please check the 23 ``1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 24 Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe), 25 munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or 26 ftp.isi.edu (US West Coast). 28 Distribution of this memo is unlimited. 30 Abstract 32 This document describes a routing protocol for mobile ad hoc 33 networks. The protocol is based on the link state algorithm. It 34 uses the multi-point relays to calculate the route towards any 35 destination in the network. The protocol is particularly suitable 36 to the large dense networks with high nodal mobility and 37 topological changes. 39 Internet draft Optimized Link State Routing 18 November 1998 41 1. Introduction 43 This routing protocol is developed to work with the IMEP protocol. 44 It uses the different functionalities provided by IMEP, like link 45 status sensing with neighbors, multi-point relay forwarding, etc. 47 The protocol exchanges topology information with other nodes of the 48 network at regular intervals. It uses the multi-point relays to do 49 efficient flooding of its control messages in the network. These 50 are only the multi-point relays which are used to form the route 51 towards any destination in the network. 53 Multi-point relays are selected among the one hop neighbors with 54 "symmetric" i.e. bi-directional link. Therefore, selecting the 55 route through multi-point relays automatically avoids the problems 56 associated with data packet transfer on uni-directional links; like 57 the problem of getting the ACKnowledgement for the data packets at 58 each hop, which cannot be received if there is a uni-directional 59 link in the selected route. 61 Internet draft Optimized Link State Routing 18 November 1998 63 2. Terminology 65 connection 67 A communication channel or medium *on the same physical 68 interface*, over which the nodes can communicate with each 69 other. 71 link 73 A logical communication channel between two nodes over which 74 they can communicate with each other. 76 node 78 A MANET router that implements this Link State Routing 79 protocol. 81 multi-point relay (MPR) 83 A node which is selected by its one-hop neighbor node X to 84 "re-transmit" all the broadcast packets that it will receive 85 from X, provided that the same packet is not already received, 86 and the hop count field of the packet is greater than zero. 88 asymmetric link 90 A uni-directional *link* (not connection) between two neighbor 91 nodes, i.e. node X can hear node Y, but node Y can not hear node 92 X. So the link X-Y is asymmetric from node X's perspective, and 93 this link does not exist from node Y's perspective (as Y is not 94 hearing X). 96 symmetric link 98 A bi-directional *link* (not connection) between two neighbor 99 nodes, i.e. node X and node Y, both can hear each other. This 100 bi-directional link can be a union of two oppositely-directed 101 uni-directional connections using different interfaces. 103 holding time 105 The lifetime associated to an entry in any table. That entry is 106 kept in the table for a period equal to its holding time. If the 107 entry is not refreshed during this period, it is removed from 108 the table when its holding time expires. 110 Internet draft Optimized Link State Routing 18 November 1998 112 refreshing an entry 114 The holding time of the entry in the table is updated to a 115 specified value _HOLDING_TIME. 117 3. Applicability Section 119 This section dictates the characteristics of the OLSR protocol, as 120 specified in the Applicability Statement draft. 122 3.1 Networking Context 124 The protocol is best suited to the large "dense" networks, as the 125 optimization done using the multi-point relays works well in this 126 context. More the network is dense and large, more optimization 127 is achieved as compared to the normal link state algorithm. The 128 thing which may restrict here is the size of the topology table 129 which is O(N**2), where N is the number of nodes in the network. 130 (Although we have developed an algorithm which reduces its size 131 to O(N) only). 133 This protocol is suited for the networks where the traffic is 134 random and sporadic between "several" nodes (and NOT between a 135 small specific set of nodes) of the network, and still better if 136 these pairs change with time. (These changes 137 will initiate enormous traffic (Query flooding) in case of source 138 routing, but nothing in OLSR, as the routes are maintained for each 139 destination all the time). 141 3.2 Protocol Characteristics and Mechanisms 143 * Does the protocol provide support for unidirectional links? (if so, 144 how?) 146 No. It uses only bi-directional "links", but these links may be 147 composed of oppositely directed uni-directional "connections". 149 * Does the protocol require the use of tunneling? (if so, how?) 151 No. 153 * Does the protocol require using some form of source routing? (if 154 so, how?) 156 No. The protocol uses hop-by-hop routing. 158 Internet draft Optimized Link State Routing 18 November 1998 160 * Does the protocol require the use of periodic messaging? (if so, 161 how?) 163 Yes. Periodically, all nodes in the network send a message 164 containing the addresses of its multi-point relays. This 165 information helps other nodes to build routes to that node 166 through these multi-point relays. 168 * Does the protocol require the use of reliable or sequenced packet 169 delivery? (if so, how?) 171 No. As the TC packet is sent periodically, it needs not to be 172 sent reliably. TC packet also contains the sequence number of 173 the "most-recent-information" (MPR SEQ NUM), so UN-sequenced 174 delivery of packets will also not create any problem. 176 * Does the protocol provide support for routing through a multi- 177 technology routing fabric? (if so, how?) 179 Yes. It provides support for routing through a multi-technology 180 routing fabric by using Router IDs (see IMEP draft). RID may be 181 associated with more than one IP addresses, representing 182 different physical interfaces. 184 * Does the protocol provide support for multiple hosts per router? 185 (if so, how?) 187 Yes. As mentioned in the preceding question, RID may be 188 associated with more than one IP addresses, and these IP address 189 may represent different hosts associated to that router. 191 * Does the protocol support the IP addressing architecture? (if so, 192 how?) 194 The OLSR protocol uses RIDs, but the mapping of RIDs to IP 195 addresses is provided by IMEP through its NARP service. So in 196 this sense, OLSR supports the IP addressing architecture. 198 * Does the protocol require link or neighbor status sensing (if so, 199 how?) 201 Yes. The protocol requires the link status sensing. It needs to 202 be notified when a bi-directional link fails with a neighbor, or 203 when a neighbor with a bi-directional link is added. This 204 service is provided by IMEP to OLSR. 206 Internet draft Optimized Link State Routing 18 November 1998 208 * Does the protocol have dependence on a central entity? (if so, 209 how?) 211 No. All the routers in the network have their own routing tables 212 and does not depend on any specific node (source, etc). 214 * Does the protocol function reactively? (if so, how?) 216 No. But it decreases and increases the interval (within certain 217 limits) of sending the TC packet periodically, depending upon 218 the rate of link changes in its neighborhood. 220 * Does the protocol function proactively? (if so, how?) 222 Yes. It periodically sends the information about its multi-point 223 relay set, which helps other nodes to build routes to it. 225 * Does the protocol provide loop-free routing? (if so, how?) 227 As the protocol uses link state algorithm, so implicitly, the 228 routing is loop-free. 230 * Does the protocol provide for sleep period operation? (if so, how?) 232 Yes, it can provide support for sleep period operation. To 233 enable this feature, the protocol should select its multi-point 234 relays from only among the "p-supporters" (power conservation 235 supporters) i.e. the nodes which can (or agree to) store its 236 packets while it is in sleep mode. 238 * Does the protocol provide some form of security? (if so, how?) 240 No, not itself. But it uses IMEP which provides authentication 241 and security. 243 * Does the protocol provide support for utilizing multi-channel, 244 link-layer technologies? (if so, how?) 246 Yes. 248 Internet draft Optimized Link State Routing 18 November 1998 250 4. Protocol Overview 252 This protocol is developed to work with the IMEP protocol. It uses 253 various functionalities of the IMEP, specially the link status 254 information with the neighbors, multi-point relays selection and 255 forwarding, etc. It needs from the IMEP protocol to provide the 256 information about 258 - its neighbors with which the status of the link is symmetric 259 i.e. bi-directional 260 - the list of multi-point relays along with the sequence number 261 of their selection. 263 This information is kept in the Neighbor Table, and is updated 264 accordingly whenever the up to date information is passed from IMEP 265 to this routing protocol (OLSR). 267 The protocol is pro-active in nature, and by periodic exchange of 268 messages, it establishes its routing table in which it stores the 269 information of the route to each destination node in the network. 270 This information is updated when 272 - a change in the neighborhood is detected concerning a 273 symmetric link; or 274 - a route to any destination is expired (because the 275 corresponding topology entry is expired) or 276 - a better (shorter) route is found for a destination. 278 The protocol relies on the multi-point relays, and calculates the 279 routes towards each destination through these nodes. To implement 280 this, each node in the network periodically broadcast the 281 information of its multi-point relays. Upon receipt of this MPR 282 information, each node calculates (or updates) the route towards 283 each destination. So these are the multi-point relays which form 284 the route towards any destination. 286 The protocol does not do the source routing, instead it performs 287 hop by hop routing. 289 Internet draft Optimized Link State Routing 18 November 1998 291 5. Multi-point relays 293 The idea of multi-point relays is to minimize the flooding of 294 broadcast messages in the network by reducing/optimizing the 295 duplicate re-transmissions in the same region. Each node in the 296 network selects a set of nodes in its neighborhood, who will 297 re-transmit its packets. This set of selected neighbor nodes is 298 called the multi-point relays of that node. Each node selects its 299 multi-point relay set in a manner to cover all the nodes that are 300 two hop away from it. The neighbors which are not in the MPR set, 301 do read and process the packet but *do not* re-transmit this 302 broadcast message. For more details about the multi-point relays, 303 refer to the IMEP protocol [1], where the multi-point relays 304 selection and forwarding is implemented. 306 6. Interface with IMEP 308 6.1 OLSR registration 310 To be operational, OLSR will be registered with IMEP, as specified 311 by the IMEP protocol, with the protocol type value equal to OLSR, a 312 handle to receive objects from IMEP (implementation dependent), an 313 epitaph object as null (for the time being) and the Link-level mode 314 of IMEP signaling support. It also request IMEP protocol to provide 315 LCSS (Link Connection Status Sensing) and MPR (Multi Point Relay) 316 support. 318 6.2 IMEP Signalling Support 320 For OLSR to perform its task of calculating the routes to any 321 destination in the network, it does not require to know if a link 322 is composed of bi-directional connections on the same physical 323 interface or it is using two (or more) oppositely directed 324 uni-directional connections on different interfaces to form a 325 symmetric link between two one-hop neighbor nodes. All it requires 326 to know is whether a link with a neighbor node is asymmetric or 327 symmetric. So at the time of registration, the "Link-level" 328 signaling support will be indicated to IMEP, and OLSR will take the 329 advantage of the links composed of multiple interface connections. 331 6.3 Connection Notification mode 333 OLSR is sensitive only to the symmetric links with its one-hop 334 neighbors. OLSR computes the routes using the multi-point relays, 335 which are selected among the one hop neighbors with symmetric link 336 only. So the UNI-directional connection notification mode will be 337 demanded from IMEP. 339 Internet draft Optimized Link State Routing 18 November 1998 341 6.4 Broadcast signaling modes 343 OLSR will select Multiple Interface (MI) mode, in order to be able 344 to establish route to/through the nodes having different physical 345 interfaces or technologies, but are operating in the same MANET. 347 6.5 Neighbor Broadcast Reliability 349 OLSR will request BROADCAST (implicit) delivery for its control 350 packets (TC packets) as it does not need the reliable mode. The TC 351 packets are sent periodically so if a packet is lost, the 352 information is assumed to be passed in the successive packets. 354 7. Information data bases 356 To perform the task of routing the packets, each node manages some 357 tables. Each node maintains four tables: Duplicate table, Neighbor 358 table, Topology table and Routing table. 360 7.1 Duplicate Table 362 In the duplicate table, each node records the information about the 363 packets it has already received. This information helps the node to 364 identify the already received packets, so that it does not waste 365 time in processing again the packet, and silently discards the 366 packet. The information is recorded in the duplicate table as a 367 duplicate entry. 369 The duplicate table has the following format to record these entries: 371 1. D_addr D_seq D_time 372 2. D_addr D_seq D_time 373 3. ,, ,, ,, 375 Each entry in the table consists of D_addr, D_seq and D_time, which 376 specifies that the packet with sequence number D_seq is already 377 received from the node with the address D_addr. If the same packet 378 is received again during the time D_time, this "duplicate" packet 379 will be silently discarded without any processing. The D_time is 380 the holding time of the entry in the table, upon expiry of which 381 the entry is no longer valid and hence removed. This life time of 382 the entries helps to keep the size of the table limited, by 383 discarding the old entries about the packets which are less likely 384 to be received again, after keeping these entries for a sufficient 385 time. 387 Internet draft Optimized Link State Routing 18 November 1998 389 7.2 Neighbor Table 391 In the neighbor table, each node records the information about its 392 one-hop neighbors, and the status of the link with these neighbors. 393 This table is constructed from the information given by IMEP 394 through Connection-notification and MPR information. The 395 information is recorded in the Neighbor table as a neighbor entry. 396 The neighbor table has a following format to record these entries: 398 --- N_MPR_seq --- 400 1. N_addr N_status 401 2. N_addr N_status 402 3. ,, ,, 404 Each entry in the table consists of N_addr and N_status, which 405 specifies that the node with address N_addr is a one-hop neighbor 406 to this local node and the status of the link between them is 407 N_status. N_status can be asymmetric, symmetric or MPR. The link 408 status as MPR specifies that the link status with the neighbor node 409 N_addr is "symmetric" *AND* further more, this N_addr is also 410 selected as a multi-point relay by this local node. 412 Neighbor table also keeps a sequence number value N_MPR_seq which 413 specifies that the local node keeping this neighbor table has 414 selected its most recent MPR set with the sequence number 415 N_MPR_seq. The nodes in the MPR set are indicated in the neighbor 416 table with their N_status equal to MPR. Every time a node selects 417 or updates its multi-point relay set, this N_MPR_seq is incremented 418 to a higher value. This multi-point relay set is re-calculated each 419 time when: 421 - a change in the neighborhood is detected when either a 422 symmetric link with a neighbor is failed, or a new neighbor 423 with a symmetric link is added; or 424 - a change in the two-hop neighbor set (with either symmetric or 425 asymmetric link) is detected. 427 The selection of MPRs is done by IMEP, and OLSR just uses that 428 information as such. 430 Internet draft Optimized Link State Routing 18 November 1998 432 7.3 Topology Table 434 In the topology table, each node records the information about the 435 topology of the network, and on the basis of this, the routing 436 table is calculated. 438 A node records the information about each of the multi-point relays 439 of other nodes in the network in its topology table as a topology 440 entry. The topology entries are recorded in the topology table in 441 the following format: 443 1. T_dest T_last T_seq T_time 444 2. T_dest T_last T_seq T_time 445 3. ,, ,, ,, ,, 447 Each entry in the table consists of T_dest, T_last, T_seq, and 448 T_time which specifies that the node T_dest has selected the node 449 T_last as a multi-point relay in the multi-point relay set with the 450 sequence number T_seq. Therefore, the node T_dest can be reached in 451 the last hop through the node T_last. 453 Each topology entry has an associated holding time T_time, upon 454 expiry of which it is no longer valid and hence removed. 456 7.4 Routing table 458 On the basis of the information contained in the topology table 459 and the neighbor table, a routing table is calculated. The route 460 entries are recorded in the routing table in the following format: 462 1. R_dest R_next R_dist 463 2. R_dest R_next R_dist 464 3. ,, ,, ,, 466 Each entry in the table consists of R_dest, R_next and R_dist, 467 which specifies that the node identified by R_dest is estimated to 468 be R_dist hops away from the local node, and that the one hop 469 neighbor node with address R_next in the next hop node in the route 470 to R_dest. 472 The routing table is re-calculated each time the neighbor table or 473 the topology table or both are changed. 475 Internet draft Optimized Link State Routing 18 November 1998 477 8. Multi-point Relay Information Declaration 479 A message is sent by each node in the network at regular intervals 480 to declare its multi-point relay set. This message is called TC 481 (Topology Control) packet. The information diffused in the network 482 by these TC packets will help each node to calculate its routing 483 table. The interval between the transmission of two TC packets 484 depends upon whether the MPR set is changed or not, since the last 485 TC packet transmitted. If no change occur in the MPR set, the TC 486 packet will be sent after MAX_TC_PKT_INTERVAL. When a change occur 487 in the MPR set, the next TC packet will be sent after the 488 MIN_TC_PKT_INTERVAL. Then the default value for the interval again 489 becomes MAX_TC_PKT_INTERVAL, until the MPR set is changed again. 491 The proposed format of a TC packet is 493 0 1 2 3 494 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 495 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 496 | Destination Address | 497 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 498 | Source Address | 499 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 500 | Packet Length | Packet Type | Hop Count | 501 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 502 | Packet Sequence Number | MPR Sequence Number | 503 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 504 | Originator Address | 505 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 506 | Multi-point Relay Address | 507 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 508 | Multi-point Relay Address | 509 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 510 | ... | 511 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 512 | ... | 513 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 515 8.1 Description of the fields 517 Destination address 519 For all the TC packets, this 4-bytes address field is always 520 set to the broadcast address of the network, so that when this 521 packet is diffused in the network, every node get this 522 information and hence update its topology table. 524 Internet draft Optimized Link State Routing 18 November 1998 526 Source address 528 It is set to the address (Router ID) of the node *transmitting* 529 this TC packet. This field should not be confused with the 530 Originator Address of the TC packet. Whenever a node 531 "re-transmit" the TC packet, this field is updated to that 532 transmitter node's address (RID). 534 Packet Length 536 This field contains the length of the whole TC packet in bytes, 537 starting from the Destination Address field. 539 Packet Type 541 The Packet Type field is set to the TC_PACKET value. 543 Hop Count 545 This field will contain the maximum number of hops a TC packet 546 can attain. Every time when the TC packet is re-transmitted, 547 this field is decremented by 1. When this field reaches zero, 548 the TC packet is no more re-transmitted and is destroyed. 550 Sequence Number 552 While generating the TC packet, the "originator" node will 553 assign a unique identification number to this packet, and will 554 put this number in the Sequence Number field. This sequence 555 number will be different for all the packets originated by that 556 node, which will help to recognize the duplicate reception of 557 the packets. 559 Originator Address 561 This field contains the address of the node which has originally 562 generated this TC packet to declare its multi-point relay set. 563 This field should not be confused with the Source Address field, 564 which is changed each time to the address of the intermediate 565 node which is "re-transmitting" this TC packet, while the 566 Originator Address field in never changed. 568 Internet draft Optimized Link State Routing 18 November 1998 570 Multi-point Relay Sequence Number 572 A sequence number is associated with the multi-point relay set 573 and every time a node selects/updates its multi-point relay set, 574 it increments this sequence number. This number is sent in this 575 MPR Sequence Number field of the TC packet to keep track of the 576 most recent information. When a node receives a TC packet, it 577 can decide on the basis of this MPR Sequence Number field, 578 whether the information about the multi-point relays of the 579 originator node is more recent than that it already have, or not. 581 Multi-point Relay Address (MPR) 583 This field contains the address of the node which is selected as 584 a multi-point relay by the Originator node (of the TC packet). 585 All the node addresses of the multi-point relays of the 586 Originator node are put in the TC packet, one after another. If 587 the maximum allowed size of the TC packet (MAX_TC_PKT_SIZE) is 588 attained and there are still some multi-point relay addresses 589 which remain in the MPR set, then more TC packets will be 590 generated, with different "Packet Sequence Number" but having 591 the same "MPR Sequence Number", until all addresses in the 592 multi-point relay set are transmitted. 594 Note: This protocol is designed to work with IMEP protocol with 595 multi-point relay mode "enabled". Nevertheless, if it is not 596 enabled in the IMEP protocol (for what so ever reason), then 597 instead of multi-point relays, a node will declare all its 598 neighbors with a symmetric link, in the TC packet. Nothing else 599 will be required to change in this protocol to calculate its 600 routes. 602 9 Information recording in the tables 604 9.1 Duplicate table 606 Each time a packet is received by OLSR, the protocol checks if this 607 packet is already received earlier. If the Originator Address of 608 the packet corresponds to D_addr of an entry in the duplicate 609 table, and the value of the Sequence Number field of the packet is 610 the same as the corresponding D_seq of the duplicate entry, then 611 the packet is silently discarded and no further processing is done. 613 Internet draft Optimized Link State Routing 18 November 1998 615 Otherwise, a new duplicate entry is recorded in the duplicate table 616 with : 618 - D_addr is set to the Originator Address of the packet, 619 - D_seq is set to the Sequence Number of the packet, and 620 - D_time is set to the holding time of the duplicate entries, 621 which is a pre-specified value DUPLICATE_HOLD_TIME. 623 The packet is then processed further. 625 9.2 Neighbor table 627 This table is updated with the information provided by the IMEP 628 protocol through Link/Connection notification and MRA packets. 629 Hence the entries will contain the one hop neighbors as N_addr 630 along with the link status N_status as asymmetric, symmetric or 631 MPR. To keep this information up to date, IMEP is supposed to 632 update this information whenever a change occur in its neighborhood 633 (concerning a symmetric link only) or its MPR set. 635 9.3 Topology table 637 The entries in the topology table are recorded with the routing 638 information that is exchanged among the network nodes through TC 639 packets. On the receipt of a TC packet, the following procedure is 640 executed to record the information in the topology table: 642 Step 1: 644 If the Originator Address of the received TC packet corresponds 645 to T_dest of a topology entry in the topology table, then 647 If T_seq of that topology entry is higher in value than the 648 MPR Sequence Number field of the received TC packet, no 649 further processing of the TC packet is done, and it is 650 silently discarded. 652 If T_seq of that topology entry precedes the value of the 653 sequence number field of the received TC packet, that 654 topology entry is removed. 656 Step 2: 658 For each MPR address in the received TC packet 660 If the MPR Address corresponds to the T_last of the topology 661 entry whose T_dest corresponds to the Originator Address of 662 the TC packet, then the holding time T_time of that entry is 663 updated to TOPOLOGY_HOLD_TIME. 665 Internet draft Optimized Link State Routing 18 November 1998 667 If the MPR address does not corresponds to T_last of any 668 topology entry whose T_dest corresponds to the Originator 669 Address of the TC packet, then 671 a new topology entry is recorded in the topology table 672 with: 674 - T_dest is set to the Originator Address of the TC 675 packet, 676 - T_last is set to the MPR address, 677 - T_seq is set to the value of MPR Sequence Number in 678 the TC packet, 679 - T_time is set to the TOPOLOGY_HOLD_TIME 681 9.4 Routing table 683 Each node maintains a routing table with it which allows it to 684 route the packets for the other destinations in the network. The 685 routing table is based on the information contained in the neighbor 686 table and the topology table. Therefore, if any of these tables is 687 changed, the routing table is re-calculated to update the route 688 information about each destination in the network. 690 The following procedure is executed to calculate (or re-calculate) 691 the routing table in case of a change in the neighbor table or the 692 topology table or both: 694 1. All the entries of the routing table are removed. 696 2. Then new entries are recorded in the table for each destination 697 in the network for which the route is known. All the 698 destinations for which the route is broken or partially known 699 are not entered in the table. This information is recorded in 700 the following manner: 702 2.1 The new entries are recorded in the table starting with 703 the one hop neighbors as the destination nodes. 705 For each neighbor entry in the neighbor table, whose link 706 status is symmetric (or MPR), a new route entry is 707 recorded in the routing table where R_dest and R_next are 708 both set to the address of the neighbor and R_dist is set 709 to 1. 711 2.2 Then the new route entries for the destination nodes k+1 712 hops away, where k>0, are recorded in the routing table. 714 Internet draft Optimized Link State Routing 18 November 1998 716 For each topology entry in the topology table, if its 717 T_dest does not correspond to R_dest of any route entry 718 *AND* its T_last corresponds to R_dest of a route entry 719 whose R_dist is k, then a new route entry is recorded in 720 the routing table where R_dest is set to T_dest, R_next 721 is set to R_next of the route entry whose R_dest is 722 T_last, and R_dist is set to k+1. 724 3. After calculating the routing table, the topology table entries 725 which are not used in calculating the routes may be removed, if 726 there is a need to save memory space. Otherwise, these entries 727 may provide redundant routes. 729 10. References 731 1. Corson et al. Internet MANET Encapsulation Protocol. Internet 732 draft, draft-ietf-manet-imep-spec-01.txt, August 21, 1998 734 11. Authors' Addresses 736 Philippe Jacquet 737 Project HIPERCOM 738 INRIA Rocquencourt 739 BP 105 740 78153 Le Chesnay Cedex, France 741 Phone: +33 1 3963 5263 742 Email: Philippe.Jacquet@inria.fr 744 Paul Muhlethaler 745 Project HIPERCOM 746 INRIA Rocquencourt 747 BP 105 748 78153 Le Chesnay Cedex, France 749 Phone: +33 1 3963 5278 750 Email: Paul.Muhlethaler@inria.fr 752 Amir Qayyum 753 Project HIPERCOM 754 INRIA Rocquencourt 755 BP 105 756 78153 Le Chesnay Cedex, France 757 Phone: +33 1 3963 5273 758 Email: Amir.Qayyum@inria.fr