idnits 2.17.1 draft-ietf-manet-rdmar-00.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: ---------------------------------------------------------------------------- ** 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. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 15 longer pages, the longest (page 10) being 94 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 16 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** 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 are 92 instances of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 378 has weird spacing: '... during the R...' == Line 629 has weird spacing: '...ure are alway...' == Line 660 has weird spacing: '...n terms of r...' == Line 661 has weird spacing: '...based on whi...' == Line 662 has weird spacing: '... be the most...' == (4 more instances...) == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: When a node receives a RREQ or RREP packet it checks the source IP address, the RREQ_ID/RREP_ ID value and the destination IP address of the packet. The node first checks whether it is the intended destination of the packet. If so, the node proceeds and sends a Route Reply back to the source of the RREQ, according to the rules described in section 3.2.2. If, however, the node is not the destination of the RREQ, it checks to see whether the broadcast packet has already been received in the past, and thus whether it has already transmitted the broadcast packet. If there is no existing list entry in its RREQ Table containing the same IP source address, RREQ_ID/RREP_ID value and the destination IP address of the packet the node retransmits the broadcast packet. If there is such a list entry with matching source IP address , RREQ_ID/RREP_ID value and the destination IP address of the packet the node MUST not propagate any copies of it after the first, avoiding the overhead of forwarding additional copies that reach this node along different paths. -- 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.) -- Couldn't find a document date in the document -- date freshness check skipped. 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. 'DVMRP' ** Downref: Normative reference to an Informational RFC: RFC 2501 (ref. 'MANET') -- Possible downref: Non-RFC (?) normative reference: ref. 'PNNI' -- Possible downref: Non-RFC (?) normative reference: ref. 'QoS' Summary: 7 errors (**), 0 flaws (~~), 11 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Mobile Ad Hoc Networking Working Group George Aggelou 2 INTERNET DRAFT University of Surrey, UK 3 13 September 1999 Rahim Tafazolli 4 University of Surrey, UK 6 Relative Distance Micro-discovery Ad Hoc Routing (RDMAR) Protocol 7 draft-ietf-manet-rdmar-00.txt 9 Status of This Memo 11 This document is a submission by the Mobile Ad Hoc Networking Working 12 Group of the Internet Engineering Task Force (IETF). Comments should 13 be submitted to the manet@itd.nrl.navy.mil mailing list. 15 Distribution of this memo is unlimited. 17 This document is an Internet-Draft and is in full conformance with 18 all provisions of Section 10 of RFC2026. Internet-Drafts are working 19 documents of the Internet Engineering Task Force (IETF), its areas, 20 and its working groups. Note that other groups may also distribute 21 working documents as Internet-Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six 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/ietf/1id-abstracts.txt 30 The list of Internet-Draft Shadow Directories can be accessed at: 31 http://www.ietf.org/shadow.html. 33 Abstract 35 This document describes the Relative Distance Micro-discovery Ad 36 Hoc Routing (RDMAR) protocol for use in mobile ad hoc networks 37 (MANETs). The protocol is highly adaptive, bandwidth-efficient 38 and scaleable. A key concept in its design is that protocol 39 reaction to link failures is typically localised to a very small 40 region of the network near the change. This desirable behaviour is 41 achieved through the use of a novel mechanism for route discovery, 42 called Relative Distance Micro-discovery (RDM). The concept behind 43 RDM is that a query flood can be localised by knowing the relative 44 distance (RD) between two terminals. To accomplish this, every 45 time a route search between the two terminals is triggered, an 46 iterative algorithm calculates an estimate of their RD, given an 47 average nodal mobility and information about the elapsed time since 48 they last communicated and their previous RD. Based on the newly 49 calculated RD, the query flood is then localised to a limited 50 region of the network centred at the source node of the route 51 discovery and with maximum propagation radius that equals to the 52 estimated relative distance. This ability to localise query flooding 53 into a limited area of the network serves to increase scalability 54 and minimise routing overhead and overall network congestion. 56 Contents 58 Status of This Memo i 60 Abstract . . . . . . . . . . . . . . . i 62 1. Introduction . . . . . . . . . . . . . 1 64 2. RDMAR Terminology . . . . . . . . . . . . 2 66 2.1 Specification Language . . . . . . . . 3 68 3. Protocol Overview . . . . . . . . . . . . 3 70 3.1 Packet Formats . . . . . . . . . . 4 72 3.1.1 Route Request (RREQ) Message Format . . 5 74 3.1.2 Route Reply (RREP) Message Format . . 6 76 3.1.3 Failure Notification (FN) Message . . 7 78 3.2 Route Discovery . . . . . . . . . . 7 80 3.2.1 Generating and Forwarding Route Requests . 7 82 3.2.2 Generating Route Replies . . . . . 9 84 3.3 Packet Forwarding And Route Maintenance . . 10 86 4. Quality Of Service . . . . . . . . . . . . 11 88 5. Optimizations . . . . . . . . . . . . 12 90 6. Multicasting . . . . . . . . . . . . 14 92 7. Configuration Parameters 14 94 8. Security Considerations 14 96 References 14 98 Chair's Address 15 100 Author's Address 15 102 1. Introduction 104 The Relative Distance Micro-discovery Ad hoc Routing (RDMAR) 105 protocol is designed for operation in mobile ad hoc networks [MANET]. 106 In mobile ad hoc networks (MANETs), nodes are free to move around 107 randomly and organise themselves arbitrarily; thus, the network's 108 wireless topology may change rapidly and unpredictably. In many 109 packet-radio networks the packet radios do not have direct radio 110 links to all other packet radios in the network and thus 111 store-and- forward routing of the packets is required. 112 Therefore, nodes are acting also as routers (also called Mobile 113 Routers) and dynamically establishing routing patterns among 114 themselves to form an infrastructure-less network. 116 RDMAR is a source-initiated on-demand routing protocol and allows 117 nodes to maintain routes to destinations that are in active 118 communication. One distinguishing feature of RDMAR is its use of an 119 optimised route discovery mechanism, called Relative Distance 120 Micro-discovery (RDM). According to this mechanism, the routing 121 protocol limits the range of route searching in order to save the 122 cost of flooding a route request message into the entire wireless 123 area. Thus, in contrast to pure flooding mechanism where a route 124 query would reach every node that is reachable in the wireless 125 network, in RDMAR a query is propagated only to a limited region of 126 the network for the successful discovery of the destination terminal. 128 This is achieved by estimating the relative distance between the 129 source and destination of the route search, thus restricting the 130 range of route discovery within an area centred at the source node 131 of the route discovery and with maximum radius that equals to the 132 estimated relative distance. Another feature of RDMAR is that the 133 maintenance of active paths (i.e., paths that carry active calls) 134 is a distributed operation that exploits the spatial relationship 135 of nodes when a failure along an active route occurs. Depending on 136 the relative distance of the node that reports the failure from the 137 calling and called nodes, two heuristics are considered: 138 a) if its relative distance from the called node is smaller or equal 139 to this from the calling node, then RDM is to be applied to localise 140 the repair of the failed route on the region of the network where 141 the failure occurs; otherwise, 142 b) the node proceeds and informs the calling node about the failure 143 to deliver the call through this path. 145 RDMAR offers a number of potential advantages over other routing 146 protocols for mobile ad hoc networks. First, RDMAR uses no periodic 147 beaconing to keep routing tables updated thus significantly reducing 148 network bandwidth overhead, conserving battery power and reducing 149 the probability of packet collision. In addition, in RDMAR nodes 150 do not make use of their routing caches to reply to route queries. 151 Using other nodes' cashes results to a storm of route replies and 152 repetitive updates in hosts' caches, yet early query quenching can 153 not stop the propagation of all query messages which are flooded all 154 over the network. Furthermore, RDMAR does not rely on any specific 155 location aided technology in order to compute routing patterns and 156 to limit the query flood to a restriction region. 157 Finally, in the presence of asymmetrical links traditional link-state 158 or distance vector protocols may compute routes that do not work. 159 Several factors such as interference, shadowing, differing radio or 160 antenna capabilities, may turn a link to function asymmetrically. 161 RDMAR, however, has been designed to compute correct routes even in 162 the presence of asymmetric links. 164 2. RDMAR Terminology 166 Node 167 A device in the ad hoc network willing to participate in the 168 routing protocol. 170 link 171 A communication facility or medium over which nodes can 172 communicate at the link layer, such as an Ethernet (simple 173 or bridged). A link is the layer immediately below IP. 175 packet 176 An IP header plus payload. 178 active route 180 A routing table entry with an unexpired Lifetime and a finite 181 metric. A routing table may contain entries that are not 182 active. Only active entries can be used to forward data 183 packets. 185 Route Discovery 187 The mechanism in RDMAR where a node S discovers a 188 route to some node D when one is needed. 190 Route Maintenance 192 The mechanism in RDMAR whereby a node is able to detect, 193 while using a route, if the network topology has changed 194 such that it can no longer use this route. 196 2.1 Specification Language 198 This protocol specification uses conventional capitalised keywords 199 such as "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 200 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and 201 "OPTIONAL" which are to be interpreted as described in RFC 2119 [RFC]. 203 3. Protocol Overview 205 In RDMAR, calls are routed between the stations of the network 206 by using routing tables which are stored at each station of 207 the network; each node is treated as a host as well as a 208 store-and-forward node. Each routing table lists all available 209 destinations, and the number of hops to each. Therefore, the 210 routing table of each node is a column vector of maximum (N - 1) 211 row entries, where N is the set of participating nodes in the 212 network. Apart from the available destination addresses, additional 213 information is maintained for each destination address D. This 214 includes: the "Default Router" field that indicates the next hop 215 node through which the current node can reach D, the 216 "RD" field which shows an estimate of the relative distance (RD) 217 (in hops) between the node and D, the "Time_Last_Update" (TLU) 218 field that indicates the time elapsed since the node last received 219 routing information for D, a "RT_Timeout" field which records 220 the remaining amount of time before the route is considered 221 invalid, and a "Route Flag" field which declares whether the 222 route to D is active. 224 Each mobile node maintains two data structures, in addition to 225 the routing table, wherein all routing and management information, 226 learned during protocol operation, is kept; namely these are: the 227 Data Re-transmission Table and the Route Request Table. 229 When a source node S wishes to send a data packet to some 230 destination D, it first examines if it has a route to this 231 destination. If so, it keeps a copy of the packet in its Data 232 Re-transmission table and then proceeds and transmits the 233 packet over its network interface to the next hop identified in 234 its routing table. The Data Re-transmission Buffer, therefore, 235 is a queue of data packets that are awaiting the receipt of an 236 explicit acknowledgement from their destination. Each 237 intermediate node (IN) upon reception of a data packet, first 238 acknowledges (link-level acknowledgement) its correct reception 239 to the previous hop, and forwards it to the next hop, if a path 240 to destination is available. If an IN is unable to forward the 241 packet, it starts the Route Maintenance Phase, as described in 242 section 3.3 244 On the other hand, if the source, S, of the data packet does not 245 have a route to destination (either because S did not have 246 previous information for the destination node, D, or because S 247 had a valid route for D but the lifetime associated with this route 248 expired and hence erased from its Routing Table), the node buffers 249 the packet and attempts to discover one using the Route Discovery 250 procedure, as described in section 3.2. All information 251 related to the most recent Route Discovery, is stored in the Route 252 Request Table. Finally, the node transmits the original packet 253 once the route is learned from route discovery. 255 3.1 Packet Formats 257 Route Requests (RREQs), Route Replies (RREPs), and FN (Failure 258 Notification) are the three message types defined by RDMAR. These 259 messages carry all the control information needed for the correct 260 operation of RDMAR. 262 3.1.1 Route Request (RREQ) Message Format 264 This packet is used during the route discovery phase. It is a 265 fixed length packet. The various fields contained in this 266 packet are: 268 0 1 2 3 269 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 270 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 271 | Type |E| Reserved | RD | 272 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 273 | RREQ_ID | 274 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 275 | Destination address | 276 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 277 | Source IP address | 278 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 279 | Source Sequence Number | 280 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 282 The format of the Route Request message is illustrated above, and 283 contains the following fields: 285 Type Indicates which control packet is sent. 287 E Emergency flag; set to '1' when a microdiscovery 288 procedure (RDM) is triggered as a result of a 289 failure of an intermediate node to forward a call, 290 according to the rules described in Section 3.3. 291 Otherwise, the flag is set to '0'. 293 Reserved Sent as 0; ignored on reception. 295 Relative Distance (RD) 297 The number of hops from the Source IP Address to 298 the node handling the request. 300 RREQ_ID 302 A sequence number uniquely identifying the 303 particular RREQ when taken in conjunction with the 304 source and destination node's IP address. 306 Destination Address 308 The address of the destination for which a route is 309 desired. 311 Source IP Address 313 The IP address of the node which originated the 314 Route Request. 316 Source Sequence Number 318 The current sequence number to be used for route 319 entries pointing to (and generated by) the source 320 of the route request. 322 3.1.2 Route Reply (RREP) Message Format 324 This packet is used during the route discovery phase and is sent 325 by the destination node of a RREQ in response to the RREQ control 326 packet. It is a fixed length packet. The various fields contained 327 in this packet are: 329 0 1 2 3 330 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 331 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 332 | Type |E| Reserved | RD | 333 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 334 | RREP_ID | 335 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 336 | Destination address | 337 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 338 | Source IP address | 339 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 340 | Lifetime | 341 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 343 The format of the Route Reply message is illustrated above, and 344 contains the following fields: 346 Type Indicates which control packet is sent. 348 E Emergency flag; set when the RREP is a response of 349 a RREQ that had the 'E' bit set. 351 Reserved Sent as 0; ignored on reception. 353 Relative Distance (RD) 355 The number of hops from the receiver of the packet 356 to the Source IP Address. 358 RREP_ID 359 A sequence number uniquely identifying the 360 particular RREP when taken in conjunction with the 361 source and destination node's IP address. 363 Destination IP Address 365 The IP address of the node that requested the a 366 route. 368 Source IP Address 369 The IP address of the node for which a route is 370 desired. 372 Lifetime 373 The time for which nodes receiving the RREP 374 consider the route to be valid. 376 3.1.3 Failure Notification (FN) Message 378 This Failure Notification (FN) packet is invoked during the Route 379 Maintenance phase and is sent by an immediate neighboring node 380 that has detected a link or nodal failure along an active path. Its 381 packet length is fixed and it has the following format: 383 0 1 2 3 384 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 385 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 386 | Type | Reserved | 387 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 388 | Source Address | 389 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 390 | Destination Address | 391 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 392 | Dependent_List.Node | 393 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 395 The format of the Failure Notification message is illustrated above, 396 and contains the following fields: 398 Type Indicates which control packet is sent. 400 Reserved Sent as 0; ignored on reception. 402 Source Address 404 The IP address of the destination of the data packet. 406 Destination Address 408 The IP address of the source of the data packet. 410 Dependent_List.Node 412 The IP address of the node (neighbor) listed in the 413 Dependent_List (see section 3.3). 415 3.2 Route Discovery 417 3.2.1 Generating and Forwarding Route Requests 419 When an incoming call arrives at node S for destination node D 420 and there is no route available to route the packet to D, S initiates 421 a route discovery phase. Here, S has two options; either to flood 422 the network with a route query in which case the route query packets 423 are broadcast into the whole network, or instead, to limit the 424 discovery in a smaller region of the network, if some kind of 425 location prediction model for D can be established. 427 The former case is straightforward. In the latter case, the 428 source of the route discovery, S, refers to its routing table 429 in order to retrieve information on its previous relative distance 430 with D and the time elapsed since S last received routing 431 information for D. Let us designate this time as Tm. Based on this 432 information and assuming a moderate velocity, Micro_Velocity, node S 433 is then able to estimate its new relative distance to destination 434 node D in terms of actual number of hops. 436 To accomplish this, a stochastic model, called relative distance 437 estimation (RDE) algorithm, has been developed [RDMAR_MODEL] to 438 estimate the minimum relative distance for the successful location 439 of the destination terminal based on the previous relative distance 440 of the terminals and the elapsed time since they last communicated 441 (i.e., Tm). In this model, the total cost is defined as the total 442 network resources spent during the route discovery procedure and 443 RDE is then used to determine the optimal relative 444 distance (in terms of hops) that results in the minimum cost. 446 Thereafter, node S limits the distribution for route queries by 447 inserting the normalized hop-wise value of their RD in the 448 Time-to-Live (TTL) [IP] field in the header of the route request 449 (RREQ) packet. As TTL decreases at every node that forwards the 450 packet, the range of broadcast is eventually restricted in a small 451 area of the network with maximum radius from the source of the 452 broadcast equal to RD hops. In the worst case, the newly calculated 453 RD is equal to the radii of the network; that is, pure flooding. 454 This procedure is called Relative-Distance Microdiscovery (RDM). 456 After broadcasting a RREQ, a node waits for a RREP. If the RREP 457 is not received within RREP_WAIT_TIME milliseconds, the node MAY 458 rebroadcast the RREQ, up to a maximum of RREQ_RETRIES times. Each 459 rebroadcast MUST increment the RREQ_ID field. 461 Data packets waiting for a route (i.e., waiting for a RREP after 462 RREQ has been sent) SHOULD be buffered at the source node. The 463 buffering SHOULD be FIFO. If a RREQ has been rebroadcast 464 RREQ_RETRIES times without receiving any RREP, all data packets 465 destined for the corresponding destination SHOULD be dropped from 466 the buffer. 468 When a node (source of RREQ or any intermediate node) receives a 469 RREP and the node has a valid (in the sense not expired) pending 470 RREQ, the node keeps a record in its routing table of the correct 471 value of its RD to the source of the RREP control packet (i.e., 472 destination of RREQ). 474 A Route Discovery for a destination SHOULD NOT be initiated unless 475 the initiating node has a packet in the Data Re-transmission 476 Buffer requiring delivery to that destination. A Route Discovery 477 for a given target node MUST NOT be initiated unless permitted by 478 the rate-limiting information contained in the Route Request Table. 480 A node that receives a RREQ packet which is not destined for it, the 481 node SHOULD NOT retransmit the packet, SHOULD NOT request explicit 482 RDMAR acknowledgement from the next hop, SHOULD NOT expect a passive 483 acknowledgement, and SHOULD NOT place the packet in the RREQ table 484 for retransmission. 486 3.2.2 Generating Route Replies 488 As the RREQ is propagated hop-by-hop outward, each intermediate 489 node that receives the RREQ packet creates a reverse route to the 490 source of the RREQ in its routing table with next hop set to the 491 address of the previous hop included in the RREQ packet. 493 When a node receives a RREQ or RREP packet it checks the source IP 494 address, the RREQ_ID/RREP_ ID value and the destination IP address 495 of the packet. The node first checks whether it is the intended 496 destination of the packet. If so, the node proceeds and sends a 497 Route Reply back to the source of the RREQ, according to the rules 498 described in section 3.2.2. 499 If, however, the node is not the destination of the RREQ, it checks 500 to see whether the broadcast packet has already been received in 501 the past, and thus whether it has already transmitted the broadcast 502 packet. If there is no existing list entry in its RREQ Table 503 containing the same IP source address, RREQ_ID/RREP_ID value and 504 the destination IP address of the packet the node retransmits the 505 broadcast packet. If there is such a list entry with matching 506 source IP address , RREQ_ID/RREP_ID value and the 507 destination IP address of the packet the node MUST not propagate 508 any copies of it after the first, avoiding the overhead of 509 forwarding additional copies that reach this node along different 510 paths. 512 A Route Reply (RREP) packet MUST be generated in response to a RREQ 513 only by the destination node for which the RREQ is sent for. The 514 route is made available by unicasting a RREP back to the source of 515 the RREQ packet. 517 If a new route for some destination D is offered to a mobile 518 station, then if the mobile station has already a route to D it 519 compares the hop count (i.e., the "RD" field in the RREP message) 520 of the new route to the RD for the route that already exists in its 521 table. If the new route carries a smaller RD than the RD of the 522 pending route, then the new route will be selected. If, however, 523 the node does not have a route for the destination, it "blindly" 524 adds the newly coming route. This is because in RDMAR a RREP is 525 always generated from the destination node of a RREQ. Hence, it 526 is highly impossible for nodes to receive stale routing 527 information. 529 Finally, an intermediate node that receives a new RREP to forward, 530 it SHOULD send replies not only to the destination node listed in 531 this RREP, but also to all nodes that have previously sent RREQ to 532 the source of the RREP and no reply has been forwarded to them yet. 534 In conclusion, in RDMAR route decision MUST be performed at the 535 destination node and only the best selected route will be 536 valid while all other possible routes remain passive; therefore 537 avoid stale routes and packet duplicates. 539 3.3 Packet Forwarding and Route Maintenance 541 An intermediate node K, upon reception of a data packet, first 542 processes the routing header and then forwards the packet to 543 the next hop. In addition to that, node K SHOULD send an explicit 544 message to the previous node on an attempt to examine whether 545 bi-directional link can be established with the node where the 546 packet is received from. 548 RDMAR, therefore, does not assume bi-directional links but in 549 contrast nodes SHOULD exercise the possibility of having 550 bi-directional links. In this way, nodes that forward a data packet 551 will always have routing information to send the future 552 acknowledgement back to the source. 554 If node K is unable to forward the packet because there is no route 555 available or a forwarding error occurs along the data path as a 556 result of a link or node failure, K MAY attempt a number of 557 additional re-transmissions of the same data packet, up to a 558 maximum number of retries MAX_DATA_RETRIES. The reason for 559 multiple attempts is that this failure could have been caused by 560 temporary factors such as noise bursts, moving node was in a radio 561 shadow area etc. If, however, the failure persists, node K 562 initiates the Route Maintenance Phase. 564 During the Route Maintenance procedure, node K exploits the 565 spatial relation between itself and the source and destination nodes 566 of the data packet. Depending on its relative position from the 567 source and destination nodes of the packet, K may optionally 568 initiate an RDM procedure or notify instead the source of the 569 active call. This results from the relative distance of K from 570 the source and destination nodes of a data packet. If K is close 571 to the destination of the packet at the time of the failure 572 (referring to its routing table), it SHOULD proceed and initiate an 573 RDM procedure (to distinguish this RDM phase from the one that is 574 triggered from a data source node, let us designate this as RM_RDM); 575 otherwise, if K is close to the source of the data 576 packet it SHOULD proceed and notify the source about the failure 577 to deliver the packet through this path. 578 The latter case is called Failure Notification (FN) phase. 580 The RREQ traffic generated during the RM_RDM phase MUST have the 'E' 581 flag set to '1', so as the recipients of this traffic to prioritize 582 the traffic. This can be achieved by assigning queue priorities ( 583 e.g., by emulation of Priority Queue Discipline [QoS]) so that this 584 traffic is always transmitted ahead of other types of traffic. 586 The reasons for prioritizing this control traffic are twofold. On 587 one hand, an intermediate node that triggers the RM_RDM should 588 receive a RREP fast so that a fast re-routing is performed in a 589 manner seamless to data source; seamless in terms of the 590 application's performance perspective and the graceful degradation 591 of real-time traffic. On the other hand, data packets destined to 592 the node for which a route discovery is in progress, keep 593 accummulating on the input buffer of the node while the discovery 594 is in progress (i.e., a RREP has not been received yet). Therefore, 595 unless a route is received fast, the resources (buffers) of the 596 source node of the RM_RDM will saturate and local congestion 597 problems may arise at this node. Congestion in turn leads to the 598 dropping of packets which causes big delays and intermittent 599 application disruptions. 601 After broadcasting a RREQ, a node waits for a RREP. If the RREP 602 is not received within RREP_WAIT_TIME_MICRO milliseconds, the node 603 MAY rebroadcast the RREQ, up to a maximum of RREQ_RETRIES times. 604 Each rebroadcast MUST increment the RREQ_ID field. 606 During the FN phase, each node K, that receives a packet for 607 forwarding (i.e., the node is not the intended destination of 608 the packet), keeps a list of all the neighbours that use this 609 node as their default router to reach a destination D. 610 We call this list of nodes as "Dependent List" (similar to 611 the concept of Dependent Downstream Routers, described 612 in [DVMRP]). The importance of 613 this list is that the need of broadcasting is eliminated 614 by sending FN messages only to the nodes that actually use 615 the failed path. In this way, nodes that currently need a 616 route to the destination are notified to search for a 617 new path, if one still needed. The FN message propagates 618 upwards towards the source of the data packet. 620 Each node, upon receipt of a FN message, MUST remove from 621 its routing table the route associated with the destination 622 of the data packet, if the next hop to reach this destination 623 is the one through which the FN message is 624 received. Additionally, to secure the propagation of error 625 messages, nodes that receive a FN message but have an empty 626 "Dependent List" (thus being unable to forward the error 627 message), MUST use their routing caches to forward the message 628 to its destination. In this way, we ensure that 629 the affected data sources from the path failure are always 630 notified. 632 Nodes MUST NOT ptrigger the Route Maintenance phase for control 633 packets (i.e., RREQ, RREP and FN) or for Acknowledgement packets. 635 A node that receives a FN packet SHOULD NOT retransmit the 636 packet, SHOULD NOT request explicit RDMAR acknowledgement from the 637 next hop and SHOULD NOT expect a passive acknowledgement. 639 4. Quality of Service 641 RDMAR currently provides some minimal controls to 642 enable mobile nodes in an ad hoc network to specify, as part 643 of a Route Discovery, certain Quality of Service parameters that 644 a route to a destination must satisfy. In particular, a RREQ MAY 645 include a diverse of QoS Metrics such as Delay or Bandwidth bounds. 647 If, after establishment of such a route, any node along the 648 path detects that the requested Quality of Service parameters 649 can no longer be maintained, that node MUST trigger Route 650 Maintenance phase and re-discover a QoS route. 652 Although the RDMAR protocol is not designed to support QoS 653 guaranteed, the 'QoS Metrics' in RDMAR route discovery and 654 selection procedure can be customized in accordance to application 655 QoS requirements. The RDMAR route selection algorithm presented 656 earlier considers routes with the highest degree of stability and 657 overall network resource consumption as the more important QoS 658 metrics, followed by minimum-hop routes and minimum aggregate delay. 660 In RDMAR, there exists flexibility in terms of route selection 661 based on which QoS parameter is viewed to be more important 662 than others. Path stability is chosen to be the most 663 important factor to be considered first since it determines 664 how long the other QoS paramters can be maintained before 665 the route is invalidated by mobile hosts' movements. 667 5. Optimizations 669 A number of optimizations can be added to the basic 670 operation of Route discovery and Route Maintenance as 671 described in Sections 3.2 and 3.3, respectively, that can 672 improve load balancing, efficient bandwidth utilisation and 673 enhance the quality of the routes used. 675 Optimisations on the basic RREP mechanism are also proposed: 677 * Coping with transient network connectivity - Urgent_RREP (U_RREP) 679 A crucial effect on the performance of a 680 dynamic routing protocol is the motion pattern of 681 mobile stations. For example no one of the existing routing 682 protocols works within a network where all participating 683 nodes are moving always outside of the hearing range 684 of each other. However, we are interested in the case 685 where occasionally a node becomes partitioned (in the sense, 686 the node is completely disconnected) from the rest of the 687 networking topology. 689 Let us study the case where a query flood is in transit 690 while the destination of this request is effectively partitioned. 691 In this situation, all RREQ packets that are "in-flight" are 692 completely unproductive. In this case, upon timeout of the 693 recently sent RREQ packet, the source of the RREQ will continue 694 to generate RREQ packets until it receives a RREP or the number 695 of retransmission exceeds the maximum allowed retransmission 696 threshold. For the latter case we employ an exponential 697 backoff delay to limit the rate at which the new 698 route request targeted to the same host may be initiated, 699 after the maximum retransmission threshold has been reached. 700 However, as the partitioned node (say DST) is approaching the 701 ad hoc vicinity and a MANET terminal realises 702 that its new neighbour is the one that a request is in 703 progress (i.e., DST), this terminal immediately proceeds and 704 sends a RREP to all nodes that need a route to DST. This technique, 705 called Urgent Route Reply (U_RREP), therefore serves to increase 706 protocol adaptivity in the phase of transient 707 connectivity such as the one described here. 709 * Extensions for Load Balancing Support 711 In RDMAR, load balancing could be effectively 712 realised during the route discovery phase where the source 713 of the route discovery receives a number of paths from 714 destination and picks one according to the traffic 715 conditions at the time where the reply arrives. That is, 716 for a certain path, if the IP layer is responsible for 717 the monitor of the traffic load for each port interface 718 of the nodes along this path, the objective of the route 719 discovery is to search for the least-congested routes 720 (instead of the shortest-path routes), and to 721 report to the source of the RREQ an aggregate of the 722 traffic conditions along the newly discovered paths. 723 Furthermore, it is evident for all the MANET routing 724 schemes proposed so far, that an active path usually 725 remains unchanged during the call lifetime if no 726 failure occurs along the path. 728 Hence, if a session runs for sufficiently long period, 729 the batteries of the intermediate hosts may be drained 730 out, since the battery power consumed is essentially 731 proportional to the size of the data packets sent. 732 To deal with the situation, we propose that the source, 733 the destination and the intermediate nodes of a route 734 should keep track how long the route has been used 735 for the same call without route reconstruction. When 736 this time exceeds some predefined limit the route must 737 be rediscovered. This approach leads to the conclusion 738 that one important parameter that impacts the relative 739 behaviour of every MANET routing protocol, is the number 740 of connection requests an intermediate node is allowed 741 to accept for call forwarding. Due to resource constraints, 742 a node can accept a reasonable amount of connection requests 743 for forwarding other nodes' packets. None of the currently 744 proposed protocols, however, examines this concern. 746 * Optimised Handling of Route Errors - Failure Crankback 748 In our attempt to optimise the handling of error messages, 749 we use a technique similar to one proposed in PNNI 750 specification [PNNI], called crankback. We refer to 751 the modified version of crankback used in RDMAR, as Failure 752 Crankback technique. According to this, a node K that 753 receives a data packet to forward, it first keeps a 754 temporary copy of this packet before forwarding. If 755 K receives an error message for this packet from some 756 subsequent node as the packet traverses the path towards 757 its destination, K may proceed and retransmit the packet 758 through an alternate path, if one exists, instead of 759 forwarding the error message to its destination (i.e., 760 source of data packet). 762 The impact of this technique on the overall performance, 763 is that when a node receives a FN message and meanwhile 764 the node has received a new route to send the packet 765 (i.e., next hop of the route is not the hop from where 766 the FN came from), it proceeds and sends a new copy of 767 the data packet through the new route. In this way, 768 protocol makes full use of data caching and distributed 769 routing, yet there is no need to let unnecessary error 770 messages propagate up to the source of packet, especially 771 in case where the distance from the failure to the 772 senders is relatively high. 774 * Increasing Protocol Robustness 776 We are making experiments on the case where a node K that 777 receives a data packet for destination S and the next hop J 778 to reach D is unreachable, to send FN messages to all data 779 source nodes that currently have active calls routed 780 through J for every destination node that turns to be also 781 unreachable due to the failure of link K-J, and not 782 necessarily the source nodes of the active calls for D. 784 6. Multicasting 786 RDMAR has so far addressed only unicast ad hoc routing with a 787 strong emphasis on network resource consumption and discovery 788 of stable shortest-path routing patterns. However, a lot of 789 multimedia collaborative applications today involve multiparty 790 sessions and thus it is important for a routing protocol to 791 support multicasting. We recently began experimentation with 792 ways to customise the reactive route query process in order to 793 support route querying for multiple destinations and multicast 794 groups. 796 7. Configuration Parameters 798 This section gives default values for some important values 799 associated with RDMAR protocol operations. 801 Parameter Name Value 802 ---------------------- ----- 803 ACTIVE_ROUTE_TIMEOUT 3 sec 804 RREP_WAIT_TIME 2*ESTIMATED_TTL+DELAY_OFFSET 805 RREP_WAIT_TIME_MICRO 2*ESTIMATED_TTL+DELAY_OFFSET_MICRO 806 RREQ_RETRIES 3 808 ESTIMATED_TTL is the hop-wise distance estimated from 809 the RDE algorithm. DELAY_OFFSET and DELAY_OFFSET_MICRO 810 is an estimate of the average additional latency that 811 should be added onto the ESTIMATED_TTL to allow for 812 queuing delays, interrupt processing times and transfer times, 813 during the RDM and RM_RDM phase, respectively. 815 8. Security Considerations 817 Currently, RDMAR does not address any security concerns. 818 It is assumed, however, that security issues are adequately 819 address by IPSec authentication headers with the necessary 820 key management to distribute keys to the members of the 821 ad hoc network using RDMAR. 823 References 825 [DVMRP] S. Deering. Multicast Routing in Internetworks and 826 Extended LANs, Stanford University, Department of 827 Computer Science Technical Report: STAN-CS-88-1214, 828 July 1988 830 [IP] J.Postel. Internet Protocol, RFC 791, Septembet 1981 832 [MANET] Scott Corson and Joseph Macker. Mobile Ad Hoc 833 Networking (MANET): Routing Protocol Performance 834 Issues and Evaluation Considerations. RFC 2501, 835 January 1999. 837 [PNNI] The ATM Forum Technical committee. Private Network-to 838 -Network Interface Specification ver. 1.0, March 1996 840 [QoS] P. Ferguson, G. Huston. Delifering QoS on the Internet 841 and in Corporate Networks, Wiley Computer Publishing, 1998 843 [RDMAR_MODEL] G.Aggelou, R. Tafazolli. A Model for the 844 Route Discovery Mechanism of the RDMAR protocol, 845 Submitted for Publication 847 [RFC] S. Bradner. Key Words for Use in RFCs to Indicate 848 Requirement Levels, RFC 2119, March 1997 849 Chair's Address 851 The Working Group can be contacted via its current chairs: 853 M. Scott Corson 854 Institute for Systems Research 855 University of Maryland 856 College Park, MD 20742 857 USA 859 Phone: +1 301 405-6630 860 Email: corson@isr.umd.edu 862 Joseph Macker 863 Information Technology Division 864 Naval Research Laboratory 865 Washington, DC 20375 866 USA 868 Phone: +1 202 767-2001 869 Email: macker@itd.nrl.navy.mil 871 Author's Address 873 Questions about this memo can be directed to: 875 George Aggelou 876 University of Surrey 877 Centre for Communications Systems Research 878 Surrey, GU2 5XH 879 UK 880 +44 (0) 1483 300800 ext. 3468/2292 881 +44 (0) 1483 259504 (fax) 882 G.Aggelou@ee.surrey.ac.uk 884 Rahim Tafazolli 885 University of Surrey 886 Centre for Communications Systems Research 887 Surrey, GU2 5XH 888 UK 889 +44 (0) 1483 259834 890 +44 (0) 1483 259504 (fax) 891 R.Tafazolli@ee.surrey.ac.uk