idnits 2.17.1 draft-ietf-manet-fsr-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 6) 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. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 429 has weird spacing: '...nly the effec...' == Line 459 has weird spacing: '...ination has a...' == Line 607 has weird spacing: '...y table entry...' == Line 620 has weird spacing: '... if the infor...' -- 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 (June 17, 2002) is 7983 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) -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' -- Possible downref: Non-RFC (?) normative reference: ref. '7' Summary: 4 errors (**), 0 flaws (~~), 6 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 IETF MANET Working Group Mario Gerla, UCLA 3 INTERNET-DRAFT Xiaoyan Hong, UCLA 4 Expiration: December 17, 2002 Guangyu Pei 5 Rockwell Scientific Company 6 June 17, 2002 8 Fisheye State Routing Protocol (FSR) for Ad Hoc Networks 10 12 Status of This Memo 14 This document is an Internet-Draft and is subject to all provisions 15 of Section 10 of RFC2026. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note 19 that other groups may also distribute working documents as 20 Internet-Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six 23 months 24 and may be updated, replaced, or obsoleted by other documents at 25 any time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "work in progress". 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/1id-abstracts.txt 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 This Internet-Draft is a submission to the IETF Mobile Ad Hoc 35 Networks (MANET) Working Group. Comments on this draft may be sent 36 to the Working Group at manet@itd.nrl.navy.mil, or may be sent 37 directly to the authors. 39 Abstract 41 The Fisheye State Routing (FSR) algorithm for ad hoc networks 42 introduces the notion of multi-level "scope" to reduce routing 43 update overhead in large networks. A node stores the Link State 44 for every destination in the network. It periodically broadcasts 45 the Link State update of a destination to its neighbors with a 46 frequency that depends on the hop distance to that destination 47 (i.e., the "scope" relative to that destination). State updates 48 corresponding to far away destinations are propagated with lower 49 frequency than those for close by destinations. From state updates, 50 nodes construct the topology map of the entire network and compute 51 efficient routes. The route on which the packet travels becomes 52 progressively more accurate as the packet approaches its 53 destination. FSR resembles Link State routing in that it propagates 54 Link State updates. However, the updates are propagated as 55 aggregates, periodically (with period dependent on distance) instead 56 of being flooded individually from each source. FSR leads to major 57 reduction in link O/H caused by routing table updates. It enhances 58 scalability of large, mobile ad hoc networks. 60 Contents 62 Status of This Memo . . . . . . . . . . . . . . . . . . . . . . . . 1 64 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 68 2. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 70 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 4 71 3.1. General Terms . . . . . . . . . . . . . . . . . . . . . 4 72 3.2. Specification Language . . . . . . . . . . . . . . . . . 4 74 4. Protocol Applicability . . . . . . . . . . . . . . . . . . . . 5 76 4.1. Networking Context . . . . . . . . . . . . . . . . . . . 5 77 4.2. Protocol Characteristics and Mechanisms . . . . . . . . 5 79 5. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . . 7 81 6. Fisheye Technique . . . . . . . . . . . . . . . . . . . . . . . 7 82 6.1. Fisheye Scope . . . . . . . . . . . . . . . . . . . . . . 8 83 6.2. Fisheye State Routing Exchange Scheme . . . . . . . . . . 8 85 7. Protocol Operation . . . . . . . . . . . . . . . . . . . . . . 9 86 7.1 Contents of Tables . . . . . . . . . . . . . . . . . . . . 9 87 7.1.1 Neighbor List . . . . . . . . . . . . . . . . . . 9 88 7.1.2 Topology Table . . . . . . . . . . . . . . . . . . 10 89 7.1.3 Routing Table . . . . . . . . . . . . . . . . . . 10 90 7.2. Link State Message . . . . . . . . . . . . . . . . . . . 10 91 7.2.1. Description of the fields . . . . . . . . . . . . 11 92 7.3. Link State Message Processing . . . . . . . . . . . . . . 12 93 7.3.1 Originating Link State Message . . . . . . . . . . 12 94 7.3.2 Receiving Link State Message . . . . . . . . . . 12 95 7.4. Link Breakage . . . . . . . . . . . . . . . . . . . . . . 13 96 7.5. Routing Table Calculation . . . . . . . . . . . . . . . . 13 98 8. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 14 100 9. Considerations about Routing Inaccuracy . . . . . . . . . . . 14 102 10. Configuration Parameters . . . . . . . . . . . . . . . . . . . 15 104 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 15 106 References . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 108 Chair's Address . . . . . . . . . . . . . . . . . . . . . . . . . 16 110 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 16 112 1. Introduction 114 This document describes the Fisheye State Routing Protocol (FSR) 115 [1,2] developed by the Wireless Adaptive Mobility (WAM) 116 Laboratory [7] at University of California, Los Angeles. Fisheye 117 State Routing is a table-driven routing protocol which is adapted 118 to the wireless ad hoc environment. It provides an implicit 119 hierarchical routing structure. Through updating link state 120 information with different frequencies depending on the fisheye 121 scope distance, FSR scales well to large network size and keeps 122 overhead low without compromising route computation accuracy when 123 the destination is near. The routing accuracy of FSR is comparable 124 with an ideal Link State scheme. By retaining a routing entry for 125 each destination, FSR avoids the extra work of "finding" the 126 destination (as in on-demand routing) and thus maintains low single 127 packet transmission latency. As mobility increases, routes to 128 remote destinations become less accurate. However, when a packet 129 approaches its destination, it finds increasingly accurate routing 130 instructions as it enters sectors with a higher refresh rate. As a 131 results, FSR is more desirable for large mobile networks where 132 mobility is high and the bandwidth is low. By choosing proper 133 number of scope levels and radius size, FSR proves to be a flexible 134 solution to the challenge of maintaining accurate routes in ad hoc 135 networks. 137 The following properties of FSR highlight its advantages. 139 * Simplicity 141 * Usage of up-to-date shortest routes 143 * Robustness to host mobility 145 * Exchange Partial Routing Update with neighbors 146 * Reduced Routing Update Traffic 148 2. Changes 150 Major changes from version 02 to version 03: 152 - Added descriptions of operations on the lastHeardTime variable 153 in the topology table. 155 - Editorial changes. 157 Major changes from version 01 to version 02: 159 - Added operations to exclude those entries whose propagation 160 will not cause topology update at its neighbors. 162 - Editorial changes. 164 Major changes from version 00 to version 01: 166 - Update of "Status of This Memo". 168 3. Terminology 170 3.1. General Terms 172 This section defines terminology used in FSR. 174 node 176 A MANET router that implements this Fisheye State Routing 177 protocol. 179 neighbor 181 Nodes that are within the radio transmission range. 183 fisheye scope 185 A zone that is bounded by hop distances. 187 3.2. Specification Language 189 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 190 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 191 document are to be interpreted as described in RFC 2119 [8]. 193 4. Protocol Applicability 195 4.1. Networking Context 197 FSR is best suited for large scale mobile ad hoc wireless networks, 198 as the scope update scheme has larger advantages in reducing routing 199 update packet size and achieve high date packet to routing packet 200 ratio. Moreover, the fact that the route error is weighted by 201 distance obviously reduces the sensitivity to network size. 203 FSR is also suited for high mobility ad hoc wireless networks. This 204 is because in a mobility environment, a change on a link far away 205 from the source does not necessarily cause a change in the routing 206 table at the source. 208 4.2. Protocol Characteristics and Mechanisms 210 * Does the protocol provide support for unidirectional links? 211 (if so, how?) 213 Yes, since FSR is link state based routing protocol and 214 directional link states can be included in the FSR update 215 messages. 217 * Does the protocol require the use of tunneling? (if so, how?) 218 No. 220 * Does the protocol require using some form of source routing? (if 221 so, how?) 223 No. 225 * Does the protocol require the use of periodic messaging? (if so, 226 how?) 228 Yes. The FSR periodically exchanges partial link state 229 information with its neighbors 231 * Does the protocol require the use of reliable or sequenced packet 232 delivery? (if so, how?) 234 No. As the packets are sent periodically, they need not be 235 sent reliably. 237 * Does the protocol provide support for routing through a multi- 238 technology routing fabric? (if so, how?) 240 Yes. It is assumed that each node's network interface is 241 assigned a unique IP address. 243 * Does the protocol provide support for multiple hosts per router? 244 (if so, how?) 245 Yes. The router that has multiple hosts can use network ID of 246 these hosts as the address to participate FSR. 248 * Does the protocol support the IP addressing architecture? (if so, 249 how?) 251 Yes. Each node is assumed to have a unique IP address (or 252 set of unique IP addresses in the case of multiple interfaces). 253 The FSR references all nodes/interfaces by their IP address. 255 This version of the FSR also supports IP network addressing 256 (network prefixes) for routers that provide access to a 257 network of non-router hosts. 259 * Does the protocol require link or neighbor status sensing (if so, 260 how?) 262 No. 264 * Does the protocol have dependence on a central entity? (if so, 265 how?) 267 No. 269 * Does the protocol function reactively? (if so, how?) 271 No. 273 * Does the protocol function proactively? (if so, how?) 275 Yes. The FSR proactively maintains routing information at each 276 node. 278 * Does the protocol provide loop-free routing? (if so, how?) 280 Yes. As the protocol uses link state algorithm, so the 281 routing is loop-free in a stable state. In mobile 282 environment, each link state entry is destination sequenced 283 which can prevent loop in routing. 285 * Does the protocol provide for sleep period operation?(if so, how?) 287 Yes. However, this requires TDMA MAC layer support. The router 288 can be scheduled to sleep during the idle period. 290 * Does the protocol provide some form of security? (if so, how?) 292 No. 294 * Does the protocol provide support for utilizing multi-channel, 295 link-layer technologies? (if so, how?) 296 Yes, in fact the multi-channel can be used to separate routing 297 messages from user data packets. 299 5. Protocol Overview 301 Fisheye State Routing is a table-driven or proactive routing 302 protocol. It bases on link state protocol and has the ability of 303 immediately providing route information when needed. The fisheye 304 scope technique allows exchanging link state messages at different 305 intervals for nodes within different fisheye scope distance, which 306 reduces the link state message size. Further optimization allows 307 FSR only broadcast topology message to neighbors [4] in order to 308 reduce the flood overhead. With these optimizations, FSR 309 significantly reduces the topology exchange overhead and scales 310 well to large network size. 312 FSR routes each data packet according to locally computed routing 313 table. The routing table uses most recent topology information. 314 The fisheye scope message updating scheme will not lose routing 315 accuracy for inner scope nodes. For outer scope nodes, 316 information in routing entries may blur due to longer exchange 317 interval, but the extra work of "finding" the destination (as in 318 on-demand routing) is not necessary. Thus low single packet 319 transmission latency can be maintained. At a mobile environment, 320 this inaccuracy for remote nodes will increase. However, when a 321 packet approaches its destination, it finds increasingly accurate 322 routing instructions as it enters sectors with a higher refresh rate. 324 FSR does not trigger any control messages when a link failure is 325 reported. Thus it is suitable for high topology change environment. 326 The broken link will not be included in the next fisheye scope link 327 state message exchange. Sequence number and table refreshment 328 enables the FSR to maintain the latest link state information and 329 loop-free in a unreliable propagation media and highly mobile 330 network. 332 The protocol works independently with the IP format of packets and 333 is a distributed protocol. It can be implemented either in network 334 layer or in application layer. It only deals with routing table 335 management of the network system. 337 6. Fisheye Technique 339 FSR uses the "fisheye" technique proposed by Kleinrock and 340 Stevens [3], where the technique was used to reduce the size of 341 information required to represent graphical data. The eye of a fish 342 captures with high detail the pixels near the focal point. 343 The detail decreases as the distance from the focal point increases. 344 In routing, the fisheye approach translates to maintaining accurate 345 distance and path quality information about the immediate 346 neighborhood of a node, with progressively less detail as the 347 distance increases. 349 6.1. Fisheye Scope 351 The fisheye scope is defined as the set of nodes that can be 352 reached within a given number of hops. An example of a fisheye 353 scope (at node A) of hop 2 is shown below. 355 +-----------------------------------------+ 356 | +---+ | +---+ 357 | +---+ ---| F |-------|-------| H | 358 +---+ | +---+ --| C |--/ +---+ +---+ | +---+ 359 | G |-----| D |--/ +---+ | E | | 360 +---+ | +---+ | +---+ +---+ | 361 | +---+ ---| B |-------| | 362 | | A |--/ +---+ | 363 | +---+ | 364 +-----------------------------------------+ 365 Fisheye Scope at Node A of Hop 2 367 Note that in this example node E can be reached through B from A 368 with 2 hops and through F with 3 hops. Since the minimum path 369 length is 2, E are within the fisheye scope of node A. By setting 370 multiple hop radius, multiple level of scopes will cover the 371 entire network. 373 6.2. Fisheye State Routing Exchange Scheme 375 FSR is functionally similar to Link State Routing (LS) in that 376 it maintains a topology map at each node. The key difference is 377 the way in which routing information is disseminated. In LS, the 378 update message could consume considerable amount of bandwidth, 379 which depends on the update period. In order to reduce the 380 size of update messages without seriously affecting routing 381 accuracy, FSR uses the Fisheye technique. Entries in routing 382 table corresponding to nodes within the smallest scope are 383 propagated to the neighbors with the highest frequency. The 384 rest of the entries are sent out with lower frequencies. As a 385 result, a considerable fraction of link state entries is 386 suppressed in a typical update, thus reducing the message size. 387 Thus by using different exchange periods for different entries 388 in routing table, routing update overhead is reduced. 390 This strategy produces timely updates from near stations, but 391 creates large latencies from stations afar. However the imprecise 392 knowledge of the best path to a distant destination is 393 compensated by the fact that the route becomes progressively more 394 accurate as the packet gets closer to destination. As the 395 network size grows large, a "graded" frequency update plan must 396 be used across multiple scopes to keep the overhead low. 398 Link state packets are generated and flooded into the network 399 periodically or whenever a node detects a topology change. 400 In FSR, link state packets are not flooded. Instead, they are 401 exchanged periodically with their local neighbors only. The 402 periodic updates act also as neighbor discovering. Each node, 403 after hearing its neighbor's broadcast message, adds/updates 404 its neighbor list and topology table. A node maintains a 405 link state table based on the up-to-date information 406 received from neighboring nodes. Sequence numbers are used for 407 entry replacements. The sequenced periodic table update resembles 408 the vector exchange in Destination-Sequenced Distance-Vector 409 Routing (DSDV [5]) where the distances are updated according to 410 the time stamp or sequence number assigned by the node 411 originating the update. However, in FSR link states rather than 412 distance vectors are propagated. Moreover, like in LS, a full 413 topology map is kept at each node and shortest paths are computed 414 using this map. 416 In a wireless environment, a radio link between mobile nodes may 417 experience frequent disconnects and reconnects. The LS protocol 418 releases a link state update for each such change, which floods 419 the network and causes excessive overhead. FSR avoids this 420 problem by using periodic, instead of event driven, exchange of 421 the topology map, greatly reducing the control message overhead. 423 The entries to be included in the periodic broadcast message 424 are selected according to the rule that their propagation should 425 cause an update in topology tables of its neighbors. The 426 benefit of this operation is large in a dense network where 427 a node may find that all its neighbors have the same freshness 428 of the information about another node. By excluding such 429 entries, only the effective entries are included in the 430 link state update message which leads to reduction in the 431 size of the message. 433 7. Protocol Operation 435 This section discusses the operation of FSR routing protocol. 436 The sending and receiving of routing packets are in the proactive 437 nature. And the routing packets are processed separately from 438 ordinary data packets. 440 7.1 Contents of Tables 442 Each node running FSR is required to maintain following tables. 443 The required tables and suggested fields are listed below. 445 7.1.1 Neighbor List 447 When a node receives a link state message, it records/updates the 448 sender's link state information in its neighbor list. If the node 449 does not receive link state updates from a neighbor for a 450 NEIGHBOR_TIMEOUT interval, the entry for that neighbor will be 451 deleted from the neighbor list. The following 452 information is maintained in the list for each neighbor node: 453 - Neighbor ID 454 - Latest time receiving from the neighbor 456 7.1.2 Topology Table 458 Topology table records the topology information obtained from the 459 link state message. Each destination has an entry in the table. 460 The entry contains three parts: the destination information, its 461 link state information and variables for selecting effective 462 entries. Based on this table, the routing table is calculated. 463 The distance information is maitained in the routing table 464 and is used to classified the node to a fisheye scope. The 465 topology table has following fields for every link state entry: 466 - Destination Address 467 - Destination sequence number 468 - Last heard time 469 - A list of its neighbors 470 - Previous sequence number 471 - A flag for "NeedToSend" 473 7.1.3 Routing Table 475 The routing table of FSR provides the next hop information to 476 forward the packets for the other destinations in the network. 477 The entries are updated when topology table is changed. The 478 routing table has the following fields: 479 - Destination Address 480 - Next hop address 481 - Distance 483 Initially when a FSR router is powered up, it knows nothing about 484 the network except routing information about all interfaces and 485 hosts that are directly attached to the router. 487 7.2. Link State Message 489 Periodically, nodes broadcast the effective portion of the 490 topology tables to their neighbors. By listening to these 491 broadcastings, each node builds up its neighbor list. 492 As the source address (the address originating this message) 493 and destination address(broadcast address of the network) are 494 already included in the IP header, the link state message 495 given here only contains packet size and topology table 496 entries. At very beginning, this broadcast contains only 497 itself with empty topology table. 499 The proposed format of a Link State Message (assume the link cost 500 is measured in hop distance and is 1 for each neighbor, therefore 501 the link cost is not included) is as follows. 503 0 1 2 3 504 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 505 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 506 | Packet Length | Reserved | 507 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 508 | Destination Address 1 | 509 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 510 | Destination Sequence Number 1 | N_neighbors 1 | 511 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 512 | Neighbor Address 1 | 513 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 514 : . . . : 515 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 516 | Neighbor Address N_neighbors 1 | 517 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 518 | Destination Address 2 | 519 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 520 | Destination Sequence Number 2 | N_neighbors 2 | 521 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 522 | Neighbor Address 1 | 523 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 524 : . . . : 525 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 526 | Neighbor Address N_neighbors 2 | 527 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 528 : . . . : 529 : : 530 (etc) 532 7.2.1. Description of the fields 534 Packet Length 536 The length (in bytes) of the packet. 538 Reserved 540 The bits are set to '0' and are ignored on reception. 542 Destination Address 1 543 The first destination address in the topology table. 545 Destination Sequence Number 1 546 The last sequence number received for the first destination 547 in the past by the source of the message. 549 N_neighbors 1 550 The number of neighbors of the first destination. 552 Neighbor Address 1, ..., Neighbor Address N_neighbors 1 553 The list of neighbors of the first destination. The number is 554 indicated in the field N_neighbors 1. 556 Destination Address 2 557 The second destination address in the topology table. 559 These fields are repeated for each entry in the topology table. 560 The length of link state message is limited to the maximum IP 561 packet size. In that case, multiple packets may required to 562 broadcast all the topology entries. 564 7.3. Link State Message Processing 566 7.3.1 Originating Link State Message 568 Each node broadcasts the latest link state information to its 569 neighbors. FSR uses different update intervals for different 570 entries in the table according to their distance from the node. 571 To be precise, entries corresponding to nodes that are nearby 572 (within a predefined scope) are propagated to the neighbors more 573 frequently than entries of nodes that are far away. When it is 574 the time for broadcasting a node's topology table (for any 575 broadcast frequencies), the node first times out its topology 576 table. The lastHeardTime variable in the entries corresponding 577 to the frequency is checked, stale entries are timed out. The 578 time-out interval is set to be three times of the update interval. 579 For inner scope broadcasting, timing-out is performed after the 580 node refreshes its own entry. Then at the time for updating 581 fisheye scope-i's topology information, the node scans the 582 topology table to pick up corresponding nodes. The nodes 583 whose distance to the current node is within the range of 584 scope-i will be included in the update message if it is an 585 effective entry. The update interval of fisheye scope level i 586 is UpdateInterval_i. If the current node will be included in 587 the link state message, its sequence number is increased by one. 589 To select the effective portion of the scope-i link state 590 message, an entry corresponding to scope-i is chosen if its 591 flag of "NeedToSend" is true. After the message is sent, 592 all the flags of entries of scope-i are reset to false, 593 and the previous sequence numbers are copied with the current 594 sequence number. 596 7.3.2 Receiving Link State Message 598 When a node receives a link state message, it first checks its 599 neighbor link state list for the sender. If the sender is a new 600 neighbor, it will insert the sender into the list. Otherwise, 601 it will update the timestamp of the sender in the neighbor list. 602 The node then processes the link state information contained 603 in the update message. For each link state entry in the packet, 604 the following situations are considered. 606 (1) If it is a new destination to the current node, a new 607 topology table entry will be created and filled with 608 corresponding information. The "NeedToSend" flag sets 609 to true. 611 (2) Otherwise, only the most up to date destination is 612 copied to the local topology table. That is, if any entry 613 in the incoming message has a larger sequence number 614 regarding to destination j comparing with the ones stored 615 in the node's topology table, the local entry will be 616 replaced by the incoming one. The "NeedToSend" flag sets 617 to true. 619 (3) For a incoming destination not fitting into the previous 620 two cases, if the information is older than the one 621 stored in current node, i.e., its destination sequence 622 number is less than the previous sequence number of the 623 stored entry, the entry in the current node's topology 624 table needs to be sent in next link state update. The 625 "NeedToSend" flag of the entry sets to true. 627 In all the cases, when a topology entry is inserted or updated, 628 the time is stamped in the lastHeardTime variable. After all 629 incoming entries are examined, if there are any changes in the 630 topology table, routing table is recomputed. 632 7.4 Link Breakage 634 In a mobile ad hoc network, link breakage is a frequent incident. 635 Each node uses soft state to detect link breakage, i.e., each node 636 considers a link to be broken if it does not receive link state 637 messages from the neighbor after a NEIGHBOR_TIMEOUT interval. 638 The node then deletes the neighbor from neighbor list and remove 639 it from its link state entry in topology table. 641 FSR does not rely on feedback from MAC. If MAC can provide 642 Feedback in case of link failure, FSR will use the report to update 643 the neighbor table and provide more up-to-date routing information. 644 The operation is the same as above. This faster discovery can 645 result in a better performance. 647 7.5. Routing Table Calculation 649 Whenever there are changes in the topology table, the routing table 650 will be recomputed. The topology table is checked to remove stale 651 entries prior to the calculation. Based on the latest topology 652 table, the Dijkstra's algorithm [6] is performed to find the 653 shortest paths from current node to all the destinations known 654 to it, i.e., in the topology table. Old routing table is replaced 655 completely by the newly computed next hop information. 657 FindSP(i) is the algorithm used to create a shortest path tree 658 rooted at i. In this documentation, the procedure is based on the 659 Dijkstra's algorithm with modifications so that the next hop 660 (denoted as table NEXTi()) and the distance (denoted as table Di()) 661 are computed in parallel with the tree reconstruction. 663 At node i, FindSP(i) initiates with P = {i}, then it iterates until 664 P = V, where V is the set of all nodes. In each iteration, 665 it searches for a node j such that node j minimizes the value of 666 (Di(k) + weight(k,j)), for all j and k, where j belongs to {V - P}, 667 k belongs to nodes in topology table and weight(k,j) does not equal 668 to infinite. Once node j is found, P is augmented with j, D(j) is 669 assigned to D(k) + weight(k,j) and NEXTi(j) is assigned to NEXTi(k). 670 That is, as the shortest path from i to j has to go through k, 671 the successor for i to j is the same successor for i to k. 673 A weight function, weight(), is used to compute the distance of 674 a link. Since minimum hop shortest path is considered in this 675 stage, this weight function simply returns 1 if two nodes have 676 direct connection, otherwise, it returns 0. This weight function 677 may also be replaced with other functions for routing with different 678 metrics. For instance, a bandwidth function can be used to realize 679 a QoS routing. 681 8. Data Packet Forwarding 683 As the routing table is calculated in background, hop by hop data 684 packet forwarding is very straight forward. The source node or 685 any intermediate nodes retrieve the destination from the data 686 packet, and look at their routing tables. If the route is known, 687 i.e., there is an entry for the destination, the data packet is 688 sent to the next hop node. This procedure repeats until the 689 packet finally reaches the destination. 691 9. Considerations about Routing Inaccuracy 693 FSR only has inaccurate routing information about remote nodes. 694 This inaccuracy is affected by the route update interval. 695 The longer the update interval, the less accurate the routing 696 information. However, several features of FSR reduces the routing 697 inaccuracy. For large network size, as the route error is weighted 698 by distance, the sensitivity to network size is largely reduced. 699 Thus, receiving updates about far away nodes at low frequency will 700 not significantly affect the routing accuracy. The same mechanism 701 applies to mobility, i.e., the progressive accurating of the routing 702 path reduces the impact from mobility. 704 Also, increasing the scope radius will improve the accuracy. But 705 using larger radii will increase the routing update packets which 706 causes more control overhead. 708 10. Configuration Parameters 710 This section gives default values for some important parameters 711 associated with the FSR protocol operations. Readers should take 712 these values as an example for the design of their own network 713 scenario. Different values of these parameters may affect the 714 performance of the protocol. The following values define a network 715 with two level fisheye scopes. The inner scope is bounded by hop 716 distance 2. Two different update frequencies are used for the 717 scopes, they are called IntraScope_Interval and InterScope_Interval 718 for inner and outer scope respectively. 720 Parameter Name Value 721 ----------------------------- ---------------- 722 Number of Scope 2 723 IntraScope_Interval 5 second 724 IntreScope_Interval 15 seconds 725 NEIGHBOR_TIMEOUT 15 seconds 727 Acknowledgments 729 This work was supported in part by NSF under contract ANI-9814675, 730 in part by DARPA under contract DAAB07-97-C-D321. 732 References 734 [1] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing: 735 A Routing Scheme for Ad Hoc Wireless Networks", Proceedings of 736 ICC 2000, New Orleans, LA, Jun. 2000. 738 [2] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing in 739 Mobile Ad Hoc Networks", Proceedings of Workshop on Wireless 740 Networks and Mobile Computing, Taipei, Taiwan, Apr. 2000. 742 [3] L. Kleinrock and K. Stevens, "Fisheye: A Lenslike Computer 743 Display Transformation," Technical report, UCLA, Computer Science 744 Department, 1971. 746 [4] T.-W. Chen and M. Gerla, "Global State Routing: A New Routing 747 Scheme for Ad-hoc Wireless Networks," In Proceedings of IEEE ICC'98, 748 Atlanta, GA, Jun. 1998, pp. 171-175. 750 [5] C.E. Perkins and P. Bhagwat, "Highly Dynamic Destination- 751 Sequenced Distance-Vector Routing (DSDV) for Mobile Computers," 752 In Proceedings of ACM SIGCOMM'94, London, UK, Sep. 1994, 753 pp. 234-244. 755 [6] R. Sedgewick,Weighted Graphs, chapter 31, Addision-Wesley, 1983. 757 [7] UCLA Wireless Adaptive Mobility (WAM) Laboratory. 758 http://www.cs.ucla.edu/NRL/wireless 760 [8] S. Bradner. Key words for use in RFCs to Indicate 761 Requirement Levels. RFC 2119, March 1997. 763 Chair's Address 765 The MANET Working Group can be contacted via its current chairs: 767 M. Scott Corson 768 Flarion Technologies, Inc. 769 Bedminster One 770 135 Route 202/206 South 771 Bedminster, NJ 07921 772 USA 774 Phone: +1 908 947-7033 775 Email: corson@flarion.com 777 Joseph Macker 778 Information Technology Division 779 Naval Research Laboratory 780 Washington, DC 20375 781 USA 783 Phone: +1 202 767-2001 784 Email: macker@itd.nrl.navy.mil 786 Authors' Addresses 788 Questions about this document can also be directed to the authors: 790 Mario Gerla 791 3732F Boelter Hall 792 Computer Science Department 793 University of California 794 Los Angeles, CA 90095-1596 795 USA 797 Phone: +1 310 825-4367 798 Fax: +1 310 825-7578 799 Email: gerla@cs.ucla.edu 801 Xiaoyan Hong 802 3803F Boelter Hall 803 Computer Science Department 804 University of California 805 Los Angeles, CA 90095-1596 806 USA 808 Phone: +1 310 825-4623 809 Fax: +1 310 825-7578 810 Email: hxy@cs.ucla.edu 812 Guangyu Pei 813 Rockwell Scientific Company 814 1049 Camino Dos Rios 815 P.O. Box 1085 816 Thousand Oaks, CA 91358-0085 817 USA 819 Phone: +1 805 373-4639 820 Fax: +1 805 373-4383 821 Email: gpei@rwsc.com