Internet Draft T. X Brown Expires: 23 December 2003 S. Bhandare S. Doshi University of Colorado, Boulder 23 June 2003 The Energy Aware Dynamic Source Routing Protocol Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Comments on this draft may be sent directly to the authors. Abstract The energy aware dynamic source routing (EADSR) protocol is an extension to the dynamic source routing (DSR) protocol for mobile ad hoc networks. It retains the features and benefits of DSR while it incorporates new features for energy limited nodes. The EADSR features include (1) a DSR header option so that link power costs can be passed with source routes; (2) an extended route discovery protocol to find lower energy routes than minimum hop routes; and (3) an additional route maintenance mechanism that allows the source node to respond to link changes without route disruption. The protocol is able to find routes with minimum total transmit power cost. It is able to track changes in link power on a route, choose between routes based on cost, and notify the source of new lower cost routes as they become available. This document specifies the EADSR header option and operation changes to DSR. Brown, Bhandare, Doshi Expires 23 December 2003 [Page i] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 Table of Contents: Status of This Memo i Abstract i Table of Contents ii 1. Introduction 1 2. Assumptions 2 3. EADSR Protocol Overview 4 3.1. EADSR Route Discovery . . . . . . . . . . . . . . . . . . . 4 3.1.1 Route Request . . . . . . . . . . . . . . . . . . . . . 4 3.1.2 Gratuitous Replies . . . . . . . . . . . . . . . . . . 5 3.1.3 Operational Example . . . . . . . . . . . . . . . . . . 6 3.2. Additional Route Discovery Mechanism . . . . . . . . . . . 6 3.3. EADSR Route Maintenance . . . . . . . . . . . . . . . . . . 7 4. Conceptual Data Structures 9 4.1. Energy Aware Link Cache . . . . . . . . . . . . . . . . . 10 4.2. Acknowledgement Table . . . . . . . . . . . . . . . . . . 10 5. EADSR Header Format 11 5.1. Fixed Portion of EADSR Header . . . . . . . . . . . . . . 13 5.2. Energy Aware Route Request Option . . . . . . . . . . . . 13 5.3. Energy Aware Route Reply Option . . . . . . . . . . . . . 13 5.4. Route Error Option . . . . . . . . . . . . . . . . . . . . 13 5.5. Acknowledgement Request Option . . . . . . . . . . . . . . 13 5.6. Acknowledgement Option . . . . . . . . . . . . . . . . . 13 5.7. Energy Aware Source Route Option . . . . . . . . . . . . . 13 5.8. Pad1 Option . . . . . . . . . . . . . . . . . . . . . . . 14 5.9. PadN Option . . . . . . . . . . . . . . . . . . . . . . . 14 6. Detailed Operation 14 6.1. General Packet Processing . . . . . . . . . . . . . . . . 14 6.1.1. Originating a Packet . . . . . . . . . . . . . . . . 14 6.1.2. Adding a DSR Options Header to a Packet . . . . . . . 15 6.1.3. Adding an EADSR Source Route Option to a Packet . . . 15 6.1.4. Processing a Received Packet . . . . . . . . . . . . 15 6.1.5. Processing a Received DSR Source Route Option . . . . 16 6.1.6. Handling an Unknown DSR Option . . . . . . . . . . . 16 6.2. Route Discovery Processing . . . . . . . . . . . . . . . . 17 6.2.1. Originating a Route Request . . . . . . . . . . . . . 17 6.2.2. Processing a Received Route Request Option . . . . . 17 6.2.3. Generating a Route Reply using the Route Cache . . . 18 6.2.4. Originating a Route Reply . . . . . . . . . . . . . . 18 Brown, Bhandare, Doshi Expires 23 December 2003 [Page ii] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 6.2.5. Processing a Received Route Reply Option . . . . . . 18 6.3. Route Maintenance Processing . . . . . . . . . . . . . . . 19 6.3.1. Using Link-Layer Acknowledgements . . . . . . . . . . 19 6.3.2. Using Passive Acknowledgements . . . . . . . . . . . 19 6.3.3. Using Network-Layer Acknowledgements . . . . . . . . 19 6.3.4. Originating a Route Error . . . . . . . . . . . . . . 19 6.3.5. Processing a Received Route Error Option . . . . . . 19 6.3.6. Salvaging a Packet . . . . . . . . . . . . . . . . . 20 6.3.7. Processing a Received Data Packet . . . . . . . . . . 21 6.3.8. Promiscuous mode operation . . . . . . . . . . . . . 21 6.4. Multiple Interface Support . . . . . . . . . . . . . . . . 21 6.5. Fragmentation and Reassembly . . . . . . . . . . . . . . . 21 6.6. Flow State Processing . . . . . . . . . . . . . . . . . . 21 7. Protocol Constants and Configuration Variables 21 8. Security Considerations 21 Acknowledgements 22 Appendix A. Implementation and Evaluation Status 22 References 22 Chair's Address 24 Authors' Addresses 25 Brown, Bhandare, Doshi Expires 23 December 2003 [Page iii] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 1. Introduction The Energy Aware Dynamic Source Routing (EADSR) protocol [3,4] serves to extend the Dynamic Source Routing (DSR) protocol [1,2] by providing for energy conservation. In EADSR, the nodes in the network select minimum energy routes to forward packets to each other using dynamic transmit power control to transmit packets on the medium. As topology changes occur, new minimum energy routes are formed and these routes are automatically discovered and maintained by EADSR. The EADSR protocol allows nodes to dynamically discover source routes to any destination in the ad hoc network along with the minimum recommended transmit powers (MRTP) required for successful communication for each link in the route. The data packet sent by a node includes in its header the complete sequence of nodes that will forward the packet to the destination. The header also includes link energy information (LEI), such as the MRTP, for each link in the route to the destination. Each node in the route transmits the packet at the specified MRTP over the medium to the next node in the sequence of the route. Due to the inclusion of the source route and LEI in the header of each data packet, other nodes forwarding or overhearing any of these packets can save this information for subsequent use. The current version of DSR does not discover the minimum energy routes as described in [3]. Energy savings that can be obtained by employing the dynamic transmit power control in multi-hop routes is not exploited by DSR. This is the motivation of having an energy aware extension for the DSR protocol. EADSR has been designed to achieve energy savings in low mobility scenarios by the discovery and maintenance of minimum energy routes within the network keeping the overhead incurred in discovery and maintenance of these routes at the same level as that of DSR. The EADSR protocol is composed of three mechanisms that allow the discovery and maintenance of energy aware routes in the ad hoc network: - The EADSR header option includes LEI along with DSR source routes in Data, Route Request, and Route Reply packets. - Energy Aware Route Discovery is similar to the Route Discovery procedure in DSR with the ability to discover additional routes that are minimum energy routes. - Energy Aware Route Maintenance is the mechanism by which a source node is able to maintain minimum energy routes. This is an Brown, Bhandare, Doshi Expires 23 December 2003 [Page 1] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 extension to the Route Maintenance mechanism used in DSR and also involves detection of newly formed minimum energy routes due to topology changes in the network and tracking the energy cost of the links in the route. Similar to the DSR mechanisms, Energy Aware Route Discovery and Energy Aware Route Maintenance each operate entirely "on demand". The overhead incurred due to these mechanisms scales well for stationary and low mobility scenarios. As communication patterns change, the routing packet overhead of DSR automatically scales to only that needed to track the routes currently in use. Using the Energy Aware Route Discovery mechanism, a node MAY learn and cache multiple routes to any destination along with the minimum transmit powers for each route. This provides a choice of routes when the minimum energy route that is being used fails. The EADSR protocol currently supports only bi-directional links. This is unlike DSR that has a mechanism to support uni-directional links as well as asymmetric routes. This document specifies the operation of the EADSR protocol for routing unicast IPv4 packets in multi-hop wireless ad hoc networks. Advanced, optional features, such as Quality of Service (QoS) support and efficient multicast routing, and operation of DSR with IPv6 [6], are covered in other documents. The specification of EADSR in this document provides a compatible base on which such features can be added, either independently or by integration with the EADSR operation specified here. EADSR requires minimal addition to the DSR protocol. In a mixed DSR and EADSR node scenario, it is expected that DSR nodes will maintain full DSR functionality while EADSR nodes will maintain their energy aware functionality to the extent that other EADSR nodes are in the ad hoc network. This interoperabilty is not specified here, but, the EADSR specification is designed for this feature to be added. The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [4]. 2. Assumptions The assumptions specified in the DSR draft hold true for the EADSR protocol with the following additions. The node MUST have the ability to measure the received signal strength of each packet. The nodes SHOULD have the capability of Brown, Bhandare, Doshi Expires 23 December 2003 [Page 2] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 dynamic transmit power control on a per packet basis. The nodes SHOULD know the maximum transmit power, minimum transmit power, and receiver sensitivity of their interfaces. If these values are not known and generic defaults are used, correct operation can not be guaranteed. A node MAY have a single transmit power level in which case its maximum and minimum transmit powers would be the same. Nodes SHOULD be able to operate in so-called promiscuous mode that allows them to receive any packet including packets directed to other nodes. In case this feature is NOT supported, the functionality of energy aware route discovery and energy route maintenance mechanisms will be limited. The underlying MAC layer SHOULD support bi-directional links. In particular, a computed MRTP that allows packets to be received in one direction of a link is assumed to allow packets to be received in the opposite direction. If this is not the case, then correct operation can not be guaranteed. The design assumes that the EADSR protocol will be implemented in scenarios where the nodes in the network are either static or low mobility scenarios at pedestrian speeds. In particular, the link changes are slow and the topology is stable over the time scale of many end-to-end round trip times. Medium speed scenarios with topology changes on the order of several end-to-end round trip times, will function but with a large fraction of packets devoted to route discovery and maintenance. High-speed scenarios with topology changes faster than the end-to-end round trip time will deliver few packets. The energy aware route maintenance mechanism of the EADSR protocol is proactive in a limited manner. When a packet is sent, other nodes will notify the source with any better routing information for use in future packets sent to the same destination. In order for this information to be useful it is assumed that most packets are one of multiple packets sent to the same destination. This draft assumes energy use is proportional to the transmit power used by the radio interface. This assumption is valid when link distances are large and transmit power dominates all other signal processing, computing, and receiving power. In general whenever other power drains are small compared to transmit power this is valid. The EADSR specification allows for more sophisticated definitions of energy aware to be defined in future releases. These alternate definitions would affect the ranking of different routes. But, the primary EADSR function of route discovery, setting transmit powers for each hop in a route, and route maintenance would remain unchanged. Brown, Bhandare, Doshi Expires 23 December 2003 [Page 3] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 The EADSR operation specified here is relative to the April 2003 Version 9 of DSR. For ease of comparison and reference, numbering of subsections parallels the numbering in DSR. 3. EADSR Protocol Overview This section describes the main route discovery and maintenance features of EADSR. Details of the internal data structures, packet header formats, and detailed operational descriptions are given in later sections. 3.1. EADSR Route Discovery When some source node originates a new packet addressed to some destination node, the source node places in the header of the packet a source route giving the sequence of hops along with the minimum transmit powers at which the packet is transmitted for each hop. The node will look up in its cache to select the minimum energy route to the destination. If no route is found in the cache, it will initiate route discovery similar to the route request flooding process carried out in the DSR protocol. This is only guaranteed to find a minimum hop route. Additional route refinement mechanism to find minimum energy routes is implemented with a gratuitous route reply mechanism. 3.1.1 Route Request To discover a route, a route request packet is broadcast over the medium at the maximum power of the interface. This is to maximize the connectivity of the route request packet in the network. The route request packet contains a source route (with only the source so far), the link energy information for each link in the source route, and the power that the route request packet will be transmitted (the maximum power of the interface). Nodes that receive this packet compute the MRTP based on the transmit power and the receiver sensitivity of the node interface: MRTP = Ptx - RSSI + T + M (MRTPequation) where: MRTP = minimum recommended transmit power (in dBm) Ptx = power the previous node transmitted the packet (in dBm) RSSI = power the current node received the packet (in dBm) T = receiver sensitivity of the receive interface (in dBm) M = added margin to ensure successful communication (in dB) Brown, Bhandare, Doshi Expires 23 December 2003 [Page 4] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 This information and any LEI in the route request packet can be stored in a link cache for future use. The packet is further processed. If the node is the target destination for the route discovery, it sends a "Route Reply" to the initiator of the route request packet in which it includes the entire source route from the initiator to the destination and the minimum transmit powers for each hop. The route reply route is found by reversing the source route in the route request and sending the packet with this source route. Each node on the route forwards the packet to the next node and transmits at the MRTP power computed for the link during the route request. In this way the source learns a source route and the LEI for each link on the route. If the node is not the target of the route discovery it follows the a similar procedure as the DSR Route Discovery procedure. If it has already seen this route request, it discards the packet. Otherwise, it adds itself to the source route, adds the LEI values for the link from the previous node and adds the power that the route request will be forwarded. The node then re-broadcasts the route request. The interfaces used can have bounded range and discrete power levels. Since these values are transmitter specific, the receiver may not know them when it computes (MRTPequation). For this reason the computed MRTP is forwarded as is during the route request. The transmitting nodes bound or quantize the MRTP and reinsert it into the LEI during the route reply. The MRTP value is modified as follows. If the computed MRTP is below the minimum transmit power of the interface it is set to the minimum power value. If the computed MRTP is above the maximum transmit power of the interface it is set to the maximum power value. If the interface has discrete power levels the MRTP is rounded up to the next available power level. After initiating a route discovery, the sending node saves a copy of the original packet in a local buffer called "Send Buffer". The structure and operation of the Send Buffer is the same as described in Section 4.2 of the DSR draft. 3.1.2 Gratuitous Replies The EADSR route discovery process so far is equivalent to the DSR route discovery process in that they will find the same set of routes. EADSR will use power control to save energy and may choose a different lower energy route than DSR. But, it may not find routes that have significantly lower energy costs. For this reason EADSR Brown, Bhandare, Doshi Expires 23 December 2003 [Page 5] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 implements the following additional mechanism. Each node listens to the unicast route replies using the "promiscuous" mode and estimates the minimum transmit power value from itself to the transmitting node using (MRTPequation). It then looks up its cache to check if there exists a route from itself to the next hop of the route reply packet whose total transmit power is less than the power at which the packet is currently being transmitted by the transmitting node. If such a route exist, the node creates a gratuitous reply with the lower power route and corresponding minimum transmit powers. This is sent to the initiator of the route discovery. As in 3.1.1, each node in the route reply checks the MRTP computed for them by receivers and bound or quantize the value as appropriate for their interface. The modified value is inserted into their LEI in the EADSR header of the gratuitous reply. 3.1.3 Operational Example Consider the example in the figure where the source node A wishes to communicate to destination node D. The figure shows the packets transmitted by each node over time with one time line for each node. Node A initiates a route discovery by broadcasting a route request packet at maximum power, M. Node B and node C receive this packet and re-broadcast the same after adding themselves and the minimum transmit power values from node A to the route request packet. Node B and node C do not re-broadcast the route request that are broadcast by them as each node will broadcast a route request at most once. Node D receives route requests from node B and node C and sends route replies A-C-D and A-B-D with the respective transmit powers as shown in the figure. Node B now listens to the route reply A-C-D and discovers that it lies on a minimum power route A-B-C-D. It then sends a gratuitous reply to node A informing it about this lower power route. Node A, now has three routes, A-B-D, A-C-D, and A-B-C-D. Since A-B-C-D is the lowest energy it chooses this route to transmit data packets to destination node D. This is an example of EADSR listening to the unicast route reply messages and discovering additional low power routes that would never be discovered using the DSR protocol. 3.2 Additional Route Discovery Mechanism DSR optionally allows non-destination nodes to generate Route Brown, Bhandare, Doshi Expires 23 December 2003 [Page 6] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 --- ---- |Rqb| |DB | |A | |ABCD| |M | |vzy | A---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---> t --- --- ---- -- ---- |Rqb| |RRA| |GRA | |AA| |DC | |AB | |ABD| |ABCD| |- | |ABCD| |vM | |vx | |v5y | |M | |vzy | B---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---> t --- --- -- ---- |Rqb| |RRA| |AB| |DD | |AC | |ACD| |- | |ABCD| |wM | |wy | |M | |vzy | C---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---> t --- --- -- |RRB| |RRC| |AC| |ABD| |ACD| |- | |vx | |wy | |M | D---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---> t Legend --- |RRA| = Packet type [route reply sent to A] |ACD| = Source route [A->C->D] |wy | = Per hop MRTP [w=power(A->C), y=power(C->D)] --- Packet types Rqb = Route Request broadcast RRX = Route Reply sent on next hop to node X DX = Data packet sent on next hop to node X AX = Route level Ack packet reply to data packet from node X GRX = Grat reply sent on next hop to node X Replies from cached values. EADSR requires fresh routes in the network to be optimal in minimum energy routing. Hence, route discovery is carried out till the destination node replies with the entire route instead of propagating stale routes in the cache by replying from the cache. In EADSR the route replies from cache option is disabled. 3.3 EADSR Route Maintenance The source route header includes the list of intermediate nodes and Brown, Bhandare, Doshi Expires 23 December 2003 [Page 7] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 the MRTP for each link. The data packet is now transmitted by each node in the route at the power level specified by the MRTP value in the header. On each forwarding link, the transmitting node expects a network layer ACK in return. In case the ACK is not received within a certain time interval, the node removes that link from the cache. As in DSR, if it is not the source of the packet, it generates a route error message specifying the link that is broken and sends the route error packet to the source of the data packet. In any case, the source chooses an alternate route or initiates a new route discovery. A node listens to DATA/ACK exchanges not directed to itself using "promiscuous" mode and looks up its cache for a lower energy route through itself to the next hop of the packet. If a lower energy route is present, the node generates gratuitous reply with the route and the minimum transmit powers, and sends it to the source node of the data packet. Energy Aware Route maintenance additionally involves tracking the energy costs of the route. At every link in the route of a data packet, the nodes compute the new estimate of MRTP for the link and compares the value to the value specified in the header. In case there is a substantial difference specified by a margin, a flag is set in the source route header. The destination node checks this flag when it receives the data packet and generates a gratuitous route reply with the changed powers and sends it to the source of the data packet. Brown, Bhandare, Doshi Expires 23 December 2003 [Page 8] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 +-----+ t=t1 | B | P1 +-----+ | v +-----+ t=t2 | B | P2 +-----+ | v +-----+ +-----+ +-----+ | A | t=t3 | B | P3 | C | +-----+ +-----+ +-----+ | v +-----+ t=t4 | B | P4 +-----+ | v +-----+ t=t5 | B | P5 +-----+ For example, node A and node C are exchanging data at controlled power. Node B is a mobile node that moves from position P1 through P5 at times t=t1 through t=t5. Node B listens to the DATA/ACK packet exchange between node A and node C and estimates the energy cost of the route ABC compared to the current route AC. At P1 the ABC route has higher cost than AC and so node B takes no action. At P2, the ABC route is lower cost so node B sends a gratuitous reply to node A. Node A uses the new route. At P3, node B senses that power on the AB link is significantly lower and so it sets the MRTP to the new lower power and sets the link change flag in the header. Node C upon seeing the flag set, sends a gratuitous reply to the source with the new power information. Similarly at P4, node B senses that the power on the AB link is significantly higher and it sets the new MRTP and the link change flag. At P5, the power is again significantly higher and Node B sets the new MRTP and the link change flag. Node A upon receiving the information about the new higher power, determines that the AC route is the lowest power and uses route AC. Note that throughout this mobility the routing is proactive and no route error is created. 4.Conceptual Data Structures Brown, Bhandare, Doshi Expires 23 December 2003 [Page 9] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 The DSR Send Buffer and Route Request Table Data structures are as described in the DSR draft. EADSR adds two new structures. 4.1 Energy Aware Link Cache This data structure stores individual links in the system in the form of a neighbor table. It also stores the LEI of each link that can be used to compute the energy cost metric for that link. The LEI definition and how a cost is computed are in Section 5. LEI SHOULD be added to the Link Cache every time the node receives a Route Request, Route Reply, Gratuitous Reply, Data and ACK packets. Each time information is added to the Link Cache, the node SHOULD look up the Send Buffer to check if any outstanding packets can be sent. To search for a route to some destination node, the link metrics are computed using the cached LEI information. The source node MAY use the Dijkstra's minimum-cost algorithm as the graph search algorithm. When the node receives a Route Error packet, the corresponding link entry is removed from the Link Cache. Every entry in the Link Cache SHOULD be associated with a timeout. If the link is not used within this timeout value, the entry MAY be deleted from the cache. 4.2. Acknowledgement Table In order to implement a network layer ACK mechanism on a link by link basis, an ACK table is required. This is used to store the ACK request entries that includes the ACK id, along with the copy of the data packet sent out on the medium. Each entry is also associated with a timeout value. If the ACK packet is not received within this timeout value, the link is declared as invalid and this link SHOULD be removed from the Link Cache. If the ACK packet is received within the timeout value, the ACK entry is removed from the ACK table. Each entry in the ACK table contains the following fields: - The Acknowledgement identifier of the acknowledgement request in the data packet. - The time at which the entry was added to the ACK table - The copy of the data packet that is sent out on the wireless Brown, Bhandare, Doshi Expires 23 December 2003 [Page 10] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 medium. This entry is deleted by the node either IF the ACK packet is received for that entry or the timeout value expires. As in DSR a retransmit mechanism MAY be implemented. 5. EADSR header format The EADSR protocol uses all the options that are used by the DSR protocol in addition to a special option denoted the EADSR option. This optional header consists of the fields that carry energy aware information. The format of the optional header is as follows: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Opt Data Len | Version | Version Length| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Energy Information[1] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Energy Information[2] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Energy Information[n] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ EADSR fields: Option Type 8. Nodes not understanding this option will ignore this option as specified in 6.1 of the DSR draft. Option Data Length 8-bit unsigned character. The length is given by the following equation: (Version Length) * (Hop Count) + 2 Version 8-bit unsigned character. The current implementation of EADSR is Version 1. Version Length 8 bit unsigned character. This length specifies the length of the LEI field in octets. Brown, Bhandare, Doshi Expires 23 December 2003 [Page 11] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 Link Energy Information Field This is a variable length field whose length is specified by the Version length of the EADSR option. (The above diagram shows a 4 octet LEI, but it could be any length as defined by the Version and Version Length). The LEI field MAY have different definitions in different versions. The first octet of every field in every version SHOULD be the MRTP as defined below for Version 1. LEI[1] corresponds to the source to first node link in the source route. LEI[2] corresponds to the first nodes to second node link, etc. LEI[n] in every packet except Route Requests corresponds to the link to the destination. In Route Requests, LEI[n] corresponds to the node that is forwarding the Route Request. The full LEI[n] field in a Route Request MAY depend on the version number, but, the first byte MUST be the power that the Route Request is being transmitted. In Version 1 of EADSR, the Version Length is 1 octet. The LEI field is an 8-bit signed integer indicating the MRTP in dBm for the corresponding link. On Route Request packets, LEI[n] is the power that the route request packet is transmitted in dBm. The receiving node MUST compute the MRTP for this hop according to (MRTPequation) and replace LEI[n] with this computed MRTP. On Data packets, the MRTP value MUST be the power that the packet is actually transmitted on the link. If for any reason a node chooses to change the transmit power for hop i, then it MUST set the MRTP value in LEI[i] to the actual transmit power. If the new power differs by more than M_Delta then the Link Flag is set as described in Section 6.3.7. On Route Reply packets, a node MAY transmit at a power different than the MRTP in the LEI field. Route Replies are reversing a route and the MRTP on the forward link may not be appropriate when the link is reversed. The node that would transmit on hop i of a source route MUST bound and quantize the LEI[i] MRTP to match its capabilities as described in Section 3.1.1. The energy cost of a route is the sum of the absolute MRTP values. The MRTP values MUST be converted from dBm to absolute values for this computation. The EADSR option MAY be inserted either before or after the DSR Brown, Bhandare, Doshi Expires 23 December 2003 [Page 12] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 options. It SHOULD be present for the protocol to be identified as the EADSR protocol. 5.1 Fixed Portion of EADSR header This is the same as the DSR fixed portion of the header. The EADSR options are the same as the DSR options. The EADSR header option as described in the previous section is required with some DSR options. The options are defined in the following sections. The DSR Flow State Extension is NOT supported by EADSR. It MAY be supported in future versions. 5.2 Energy Aware Route Request Option The Energy Aware Route Request option in EADSR is the same as described in Section 6.2 of the DSR Draft with the addition of the EADSR header option. 5.3 Energy Aware Route Reply Option The Energy Aware Route Reply option in EADSR is the same as described in Section 6.3 of the DSR Draft with the addition of the EADSR header option. 5.4 Route Error Option This option remains the same as described in Section 6.4 of the DSR draft. 5.5 Acknowledgement Request Option This option remains the same as described in Section 6.5 of the DSR draft. It is required on all Data packets in EADSR. 5.6. Acknowledgement Option This option remains the same as described in Section 6.6 of the DSR draft. 5.7 EADSR Source Route Option The Energy Aware Source Route option in EADSR is the same as described in Section 6.7 of the DSR draft with the addition of the EADSR header option and the following modification. The right-most bit of the Reserved field in the Source Route option header is replaced by the Link Flag in the EADSR Source Route option. Brown, Bhandare, Doshi Expires 23 December 2003 [Page 13] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Option Type | Opt Data Len |F|L|Rsvd |f|Salvage|Segs Left | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The following fields are added to the existing DSR Source Route option. LinkFlag (f) This flag indicates if the energy cost of any of the links in the route have changed. This flag is set by a forwarding node if the change in the cost of the link is greater or equal to a margin M_Delta. The value of the flag is looked up by the destination node when it receives a packet and if set, the destination sends a gratuitous reply to the source node indicating the changed energy cost value of the route. 5.8 Pad1 Option This option remains the same as discussed in Section 6.8 of the DSR draft. 5.9 PadN Option This option remains the same as discussed in Section 6.9 of the DSR draft. 6. Detailed Operation To simplify the description only modifications to the DSR draft are listed here. Within the DSR draft, references to within Section 8 MUST be interpreted as references to the corresponding section within Section 6 of this draft so as to incorporate all modifications here. Thus Section 8.1.1 in the DSR draft refers to Section 8.1.2. This is interpreted as Section 8.1.2 in the DSR draft with the modifications listed in Section 6.1.2 of this draft. 6.1 General Packet Processing 6.1.1 Originating a Packet This processing is the same as that described in Section 8.1.1 in DSR with the following modifications: - When multiple routes are possible, the route with the lowest Brown, Bhandare, Doshi Expires 23 December 2003 [Page 14] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 energy cost SHOULD be chosen. - If the Route Request option is present then the packet MUST be transmitted at the maximum power of the interface. - Otherwise, the packet MUST be transmitted at the MRTP as specified in the first octet of LEI[1] in the EADSR header. The ACK request option described in Section 6.3 MUST be included. 6.1.2. Adding a DSR Options Header to a Packet The process of adding a DSR options header remains the same as that described in Section 8.1.2 of the DSR draft. 6.1.3. Adding a EADSR Source Route Option to a Packet The process of adding a DSR Source Route option remains the same as that described in Section 8.1.3 of the DSR draft. In addition, the EADSR header option is added according to the following sequence of steps: - The node creates a EADSR option as described in Section 5, and appends it to the DSR Options header. - The number of LEI fields to include in the EADSR option (n) is the number of hops in the source route. - The LEI for the links along the source route are copied into sequential LEI[i] fields in the EADSR option, for i = 1, 2, ..., n. 6.1.4. Processing a Received Packet The processing of a received packet remains the same as that described in Section 8.1.4 of the DSR draft with the following modifications: - If the DSR Options header contains an EADSR option, the node SHOULD extract the energy information from the EADSR option and add this information to its Link Cache. The energy information is the sequence of link energy information fields LEI[1], LEI[2], ..., LEI[n] where LEI[i] corresponds to the i-th hop in the source route which is derived as described in Section 8.1.4 of the DSR draft. The value n here is the number of LEI fields in the EADSR option, or Brown, Bhandare, Doshi Expires 23 December 2003 [Page 15] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 (Opt Data Len - 2)/(Version Length). - The Received Signal Strength (RSSI) is computed for the received packet. The current hop, i, can be computed with each header option described in 8.1.4. Extract the transmit power, Ptx, from the first octet of LEI[i]. The MRTP is computed according to (MRTPequation). 6.1.5. Processing a Received DSR Source Route Option The processing of a received DSR Source Route Option remains the same as that described in Section 8.1.5 of the DSR draft with the following modifications: - Route Shortening SHOULD NOT be performed. - When a node receives a packet containing a DSR Source Route Option, this packet could be either a packet that is overheard due to the promiscuous mode operation, or it could be a normal packet addressed to this node. If it is a normal packet, the node SHOULD check the packet to determine if it is the final destination. If so, - If the Link Flag is set, it SHOULD perform Energy Aware Route Maintenance on the packet as discussed in Section 6.3.7. - The node then strips the EADSR headers, and sends the packet to the higher layers for processing. If the node is NOT the final destination, - It SHOULD perform Energy Aware Route Maintenance discussed in Section 6.3.7. - The node SHOULD look up the next hop address using the procedure mentioned in DSR Source Route Processing of Section 8.1.5 of the DSR draft, and look up the corresponding transmit power value for that hop. The packet SHOULD be transmitted at the controlled power. If the packet is overheard due to the "promiscuous" mode, the packet is processed as discussed in Section 6.3.8. 6.1.6. Handling an Unknown DSR Option This sections is the same as that described in Section 8.1.5 of the DSR draft. Brown, Bhandare, Doshi Expires 23 December 2003 [Page 16] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 6.2. Energy Aware Route Discovery Processing Energy Aware Route Discovery is the mechanism by which a node S wishing to send a packet to a destination node D obtains a minimum energy source route with a list of minimum transmit powers to D. Energy Aware Route Discovery is initiated only when the "initiator" node S attempts to send a packet to "target" node D and does not already know a route to D. The process of Energy Aware Route Discovery is entirely on demand. The Energy Aware Route Discovery procedure utilizes two types of messages, a Route Request (Section 5.2) and a Route Reply (Section 5.3), to actively search the ad hoc network for a route to the desired destination. These DSR messages MAY be carried in any type of IP packet, through use of the DSR header as described in Section 5. The condition for initiating Energy Aware Route Discovery are the same described in Section 8.2 of the DSR draft. 6.2.1. Originating a Route Request This section is the same as that discussed in Section 8.2.1 of the DSR draft with the following modification. The EADSR header option is added according to the following sequence of steps: - The node creates an EADSR option as described in Section 5, and appends it to the DSR Options header. - A single LEI field is included in the EADSR option. - The first octet of the LEI field is set to the maximum transmit power in dBm of the interface. - The packet is transmitted at the maximum transmit power of the interface. 6.2.2. Processing a Received Route Request Option This section is the same as that discussed in Section 8.2.2 of the DSR draft with the following modifications if the node further processes the Route Request. - The node SHOULD NOT reply with a route from its own cache. - Set the first octet of LEI[n] in the EADSR option to the computed Brown, Bhandare, Doshi Expires 23 December 2003 [Page 17] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 MRTP for the previous hop. - Append this nodes maximum transmit power to the LEI[i] list in the EADSR option, and increase the value of the Opt Data Len field in the EADSR option by Version Length. 6.2.3. Generating a Route Reply using the Route Cache EADSR SHOULD NOT generate Route replies from its Link Cache. 6.2.4. Originating a Route Reply This section is the same as that discussed in Section 8.2.4 of the DSR draft with the following modifications: - The EADSR header option is added according to the following sequence of steps: o The node creates an EADSR option as described in Section 5, and appends it to the DSR Options header. o The LEI fields are copied from the Route Request packet. o The first octet of the LEI[n] field is set to the MRTP computed from the last hop. - The packet SHOULD be sent at the power represented by the first octet of LEI[n]. - The condition of bi-directional links SHOULD exist for Energy Aware Route Replies. - The node SHOULD send a unicast Route Reply to every Route Request packet it receives for which it is a target node. 6.2.5. Processing a Received Route Reply Option This section is the same as that discussed in Section 8.2.4 of the DSR draft with the following modifications: - If the node is on the source route specified on the route reply, it SHOULD check that the computed MRTP that it would transmit at on the route is achievable. If not it SHOULD bound and/or quantize the value as specified in Section 3.1.1. - If the node forwards the Route Reply Option, it SHOULD transmit the packet at the MRTP listed in the EADSR header. Brown, Bhandare, Doshi Expires 23 December 2003 [Page 18] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 6.3. Route Maintenance Processing This section is the same as that discussed in Section 8.3 of the DSR draft. Note that EADSR requires a network-layer acknowledgement of every packet. 6.3.1. Using Link-Layer Acknowledgements This section is the same as that discussed in Section 8.3.1 of the DSR draft. 6.3.2. Using Passive Acknowledgements This section is the same as that discussed in Section 8.3.2 of the DSR draft. 6.3.3. Using Network-Layer Acknowledgements This section is the same as that discussed in Section 8.3.3 of the DSR draft. With the following modifications: - Each data packet that is originated by a node, SHOULD request a network-layer acknowledgement from the next-hop node. - The network-layer ACK packets SHOULD be transmitted at the maximum power level supported by the interface. - If the maximum transmit power supported by node interfaces is not generally known, then an EADSR option SHOULD be added to the packet according to the following sequence of steps: o The node creates an EADSR option as described in Section 5, and appends it to the DSR Options header. o A single LEI field is created. o The first octet of the LEI field is set to the maximum transmit power of the interface. 6.3.4. Originating a Route Error This section is the same as that discussed in Section 8.3.4 of the DSR draft. 6.3.5. Processing a Received Route Error Option This section is the same as that discussed in Section 8.3.5 of the DSR draft. Brown, Bhandare, Doshi Expires 23 December 2003 [Page 19] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 6.3.6. Salvaging a Packet This section is the same as that discussed in Section 8.3.6 of the DSR draft. 6.3.7 Processing a Received Data packet Each node along a source route SHOULD check the difference between the MRTP just computed for the received packet and the MRTP in the EADSR option for this hop. If the following equation holds, the Link Flag SHOULD be set and the minimum transmit power advertised SHOULD be overwritten by the new estimated value of the minimum transmit power. |P(tx) - P(cmp)| > M_Delta where P(tx) is the power the packet was transmitted as listed in the EADSR option and P(cmp) is the MRTP computed for the received packet. If the destination address specified in IP header of the Data packet matches the node's address, It SHOULD check the Link Flag in the Source Route option. If the flag is set, it SHOULD create a gratuitous reply as discussed in Section 8.1.5 of the DSR draft. If the Link Flag is not set, it strips the EADSR headers, and sends the packet to the higher layers for processing. 6.3.8 Promiscuous Mode Operation If the data packet is overheard due to the "promiscuous" mode, - The snooping node extracts the source route and the source powers and saves the same in the Link Cache as described in Section 6.1.4. - This node estimates the power required to route packets through itself i.e. it computes the cost of routing packets from the source node to itself, and from itself to the next node. Let's consider the case where source node A communicates with destination node C and node B is an intermediate node that overhears the data/ack exchange between nodes A & C. Let's assume that the cost from the node A to node C is given by P(PrevHop) and from node C to the node B is P(NextHop). Let P(tx) be the power to transmit between node A and node B. If the following equation holds Brown, Bhandare, Doshi Expires 23 December 2003 [Page 20] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 P(PrevHop) + P(NextHop) + Margin < P(tx), the node creates a gratuitous reply with the new source route initiator, ..., transmitting node, current node, next hop node, ..., destination and the new LEI fields corresponding to this source route. 6.4. Multiple Interface Support This section is the same as that discussed in Section 8.4 of the DSR draft with the following modification. The energy cost of links between interfaces on the same device are zero. 6.5. Fragmentation and Reassembly This section is the same as that discussed in Section 8.4 of the DSR draft. 6.6. Flow State Processing The optional DSR flow state extension is not supported in EADSR. 7. Protocol Constants and Configuration Variables Any EADSR implementation MUST support all the Protocol Constants as defined in the DSR draft with the following EADSR modifications: NetworkLayerAckTimeout 1000 milliseconds M 6 dB M_Delta 4 dB T -85 dBm The value of the threshold T depends on the wireless interface sensitivity. We used Cisco 350 Aironet Series wireless ethernet cards that had a sensitivity of -85 dBm. 8. Security Considerations This document does not specifically address security concerns. However, this document assumes that every node participating in the EADSR protocol function co-operatively without any malicious intent. In mission-oriented environments where all the nodes participating in the DSR protocol share a common goal that motivates their participation in the protocol, the communications between the nodes can be encrypted at the physical channel or link layer to Brown, Bhandare, Doshi Expires 23 December 2003 [Page 21] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 prevent attack by outsiders. Acknowledgements The protocol described in this draft has been designed and developed within the Pervasive Communications Laboratory, a research project at University of Colorado at Boulder that deals with research problems such as densely interconnected networks, power management, and communications link. The work was funded by NSF Grant ANI-0082998 We would like to acknowledge the work carried out by Dave Johnson et. al. on DSR upon which our work is based. We would like to thank Jean Tourrilhes, Javier Achirica, and Peter K. Lee for their help in modifying the device driver for the Cisco 350 Aironet Series card and the Wireless Tools used. Appendix A. Implementation and Evaluation Status The initial design of the EADSR protocol, including EADSR's basic Route Discovery and Route Maintenance mechanisms, was first published in July 2002 [3] followed by a comparison of DSR and EADSR in 2003 [4]. The hardware test-bed that was used to carry out the testing of the protocol is described in [5]. The EADSR protocol has been implemented on laptops running Red Hat Linux with Cisco 350 Series wireless Ethernet cards. The protocol has been extensively tested on the NS2 simulator and the hardware test-bed and the results have been published in [3] and [4]. We are also working on implementing the EADSR protocol on Compaq iPAQs. We have implemented the EADSR protocol using the Click Modular Router on Linux 2.4.18 kernel running on Intel x86 platforms. This protocol is kernel-independent and requires the Click Modular Router running on any 2.4.X kernel with a kernel tap running. We designed and implemented an Emulated Wireless Ad hoc Networking (EWAN) test-bed [5]. References [1] David B. Johnson. Routing in Ad Hoc Networks of Mobile Hosts. In Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, pages 158--163, December 1994. [2] David B. Johnson and David A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In Mobile Computing, edited by Tomasz Brown, Bhandare, Doshi Expires 23 December 2003 [Page 22] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 Imielinski and Hank Korth, chapter 5, pages 153--181. Kluwer Academic Publishers, 1996. [3] S. Doshi, S. Bhandare, and T. X. Brown, An On-demand Minimum Energy routing protocol for a wireless ad hoc network, Mobile Computing and Communications Review, vol. 6, pp. 5066, 2002. [4] S. Bhandare, S. Doshi, T. X. Brown, and S. Sanghani, Comparison of two ad hoc wireless routing protocols on a hardware test-bed, IEEE WCNC, March 2003. [5] S. Sanghani, T. X. Brown, S. Bhandare, and S. Doshi, EWANT: Emulated wireless ad hoc network test-bed, IEEE WCNC, March 2003. Brown, Bhandare, Doshi Expires 23 December 2003 [Page 23] Internet-Draft Energy Aware Dynamic Source Routing 23 June 2003 Chair's Address The MANET Working Group can be contacted via its current chairs: M. Scott Corson Phone: +1 908 947-7033 Flarion Technologies, Inc. Email: corson@flarion.com Bedminster One 135 Route 202/206 South Bedminster, NJ 07921 USA Joseph Macker Phone: +1 202 767-2001 Information Technology Division Email: macker@itd.nrl.navy.mil Naval Research Laboratory Washington, DC 20375 USA Authors' Addresses: Questions about this document can be directed to the authors: Timothy X Brown Phone: +1 303 492-1630 Electrical and Computer Engineering Fax: +1 303 492-1112 Interdisciplinary Telecommunications Email: timxb@colorado.edu University of Colorado Boulder, CO 80309-0530 USA Shweta D. Bhandare Phone: +1 303 735-3664 Interdisciplinary Telecommunications Fax: +1 303 492-1112 University of Colorado Email: bhandare@colorado.edu Boulder, CO 80309-0530 USA Sheetalkumar R. Doshi Phone: +1 303 492-2759 Electrical and Computer Engineering Fax: +1 303 492-2758 University of Colorado Email: doshi@colorado.edu Boulder, CO 80309-0425 USA Brown, Bhandare, Doshi Expires 23 December 2003 [Page 24]