ROLL Anni. Wei Internet-Draft Huawei Technologies Intended status: Informational August 7, 2009 Expires: February 8, 2010 A routing method based on detection frames over LLNs draft-wei-roll-rmdf-00.txt Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on February 8, 2010. Copyright Notice Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Wei Expires February 8, 2010 [Page 1] Internet-Draft routing method based on detection frames August 2009 Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Abstract This document presents a routing method through sending detection frames including address of destination node to the neighbor nodes to reduce delay of data transmission because of the dormant nodes will increase data transmission delay in low power and lossy networks(LLNs). When receives the response from the neighbor nodes, the sending node can select a neighboring node as the next hop node to sent data, which has the lower cost parameter than the cost parameter between the sending node and the destination node stored in the routing table of sending node. This routing method finds a route in real-time by broadcasting detection frames. As long as any neighbor node that can reach the destination is active, data can be sent and then the data transmission delay will be reduced. Wei Expires February 8, 2010 [Page 2] Internet-Draft routing method based on detection frames August 2009 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology used in this document . . . . . . . . . . . . . . . 4 3. Problem statement and analysis . . . . . . . . . . . . . . . . 4 4. Proposed Solutions . . . . . . . . . . . . . . . . . . . . . . 5 5. Security Considerations . . . . . . . . . . . . . . . . . . . . 7 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 7 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . 7 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 7 8.1. Normative References . . . . . . . . . . . . . . . . . . . 7 8.2. Informative References . . . . . . . . . . . . . . . . . . 7 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 8 Wei Expires February 8, 2010 [Page 3] Internet-Draft routing method based on detection frames August 2009 1. Introduction This document presents a routing method based on detection frame. Transmission of each hop does not need to wait for a specific node to wake up. As long as there is a node who wakes up and has lower routing metrics to reach destination node, it can be used to forward data. This method increases the robustness of the network and reduces the demand for routing repair. 2. Terminology used in this document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. 3. Problem statement and analysis In the communication network, each routing node will set up a routing table. Such as AODV routing algorithm, in the initial establish of routing table, routing node broadcast route discovery order which contains address of destination node to the nodes around. The nodes that receive the route discovery order would check the address of destination node and compare with their own address. If the addresses are the same, the nodes send back the routing information to the routing node establishing the routing along the reverse path; If not, it can record the reverse path to the note initiating the route discovery order, forward the broadcast of route discovery order until the order reach the destination node, and then return the routing information to the node establishing the routing along the reverse path. In the route discovery process, the feedback of routing information from the destination node may be more than one. The node can select a routing who has the minimum routing metrics stored in the routing table in a certain selection principle based on a number of network performance parameters which referred to as the "routing metrics". In the process of date transmission, the routing node can handle address information in the packets and be in the role of transferring data. When receives a data packet, the routing node checks the address of destination node. If the address is in the routing table, transmit the data packet to the next hop stored in the routing table; if not, it has to decide whether to star the route discovery process according to business requirement. Low-power routing node has not only the characteristics of common routing node, but also the characteristic of long-term hibernation, i.e. a low-power routing node is not keep in the state of working, but regularly sleeps in order to maintain a state of lower energy Wei Expires February 8, 2010 [Page 4] Internet-Draft routing method based on detection frames August 2009 consumption. When transmits data in LLNs, if adopts the existing routing, such as AODV, it needs to wait for next hop to wake up to send data packets, which will result in more delay. Such as in building automation routing, sensing devices will, in some cases, utilize battery power or energy harvesting techniques for power and will operate mostly in a sleep mode to maintain power consumption within a modest budget. The routing protocol MUST take into account device characteristics such as power budget. If such devices provide routing, rather than merely host connectivity, the energy costs associated with such routing needs to fit within the power budget. If the mechanisms for duty cycling dictate very long response times or specific temporal scheduling, routing will need to take such constraints into account. Typically, batteries need to be operational for at least 5 years when the sensing device is transmitting its data (e.g. 64 octets) once per minute. This requires that sleeping devices MUST have minimal link on time when they awake and transmit onto the network. Moreover, maintaining the ability to receive inbound data MUST be accomplished with minimal link on time [I-D.ietf-roll-building-routing-reqs]. In addition, the wake-up interval of a sleeping node MUST be less than one second in home rooting[I-D.ietf-roll-home-routing-reqs]. 4. Proposed Solutions Based on the issues above, this document presents a routing method based on routing metrics . Transmission of each hop does not need to wait for a specific node to wake up. As long as there is a node who wakes up and has lower routing metrics to reach destination node, it can be used to forward data. This is a greedy algorithm, which in fact, has lower average delay and better robustness. When routers communicate in LLNs, the sender need to send detection frames, and the receiver return response frames after receiving detection frames. When the sender receives response frame, it can know that the receiver is in active state. Then it sends data packet to the receiver. If not receives response frame in the specified time, this date sending is failed. In broadcast communication, the sender needs to send consecutive detection frames, even more than the longest sleep cycles of all neighbor nodes, to ensure that all neighbor nodes wake up, and then broadcast data. The following is the specific analysis. The cost parameters of nodes can be determined in the process of Wei Expires February 8, 2010 [Page 5] Internet-Draft routing method based on detection frames August 2009 route discovery. The cost parameter could be the number of hop and / or cumulative link-quality-assessment function, as well as power consumption or time delay. Take AODV as an example. In the process of route discovery, the nodes on the different path stored the cost parameters to the destination node. In order to form a multi-path, the destination node needs to return a number of routing response along different path. The destination node returns routing response by broadcast. The nodes receiving the broadcast have to determine if they are source, or whether the cache has route discovery information reached the destination node. If is the source node, cumulates the cost of this section and record the total cost, and then no longer be dealt with. If it is not the source node, but the cache has the route discovery information reached the destination node, the cumulate cost of this paragraph, and re-broadcast routing response order. If it is not the source node and the route discovery information reached destination node does not in the cache found the, then discards the routing response order. Another to form a multi- path is" Many to One" route discovery, i.e. the destination node initiates the broadcast of route discovery orders, node who is the first time to receive the order, then cumulates the cost of this section and records the total cost to the destination node, and re- broadcasts route discovery order, if not the first time to receive the order, compares with the cost record, if the radio cost just received is lower, then makes the record update to be the lower cost and re-broadcast route discovery order, otherwise discards the broadcast order received, that is, only record and forward the route discovery order of lower cost. So that the cost parameters to destination node finally be recorded in each node. In the process of data transmission, the routing table corresponding to each destination node's address does not need to specify a specific next hop address, but the record of the cost parameters, which choose next hop based on real-time path. The sender sends detection frames which include the address of detection nodes and the cost parameters. The receiver checks routing table after receipt of detection frame. If there is the address of corresponding destination node with a lower cost parameter, or if it is the destination node, then returns a response with the cost parameter. After receiving a response, the sender selects the node with the lowest cost parameter as the next hop to send data. Therefore, when sending data, it does not need to wait special next hop node to wake up. The neighbor nodes who is first to wake up can be used to send data .So the transmission delay in LLNs can be reduced. Assume that period of sleep time of routers in LLNs is S, the active time is A, the cost parameters is indicated by hops. Each hop, if can only be forwarded through a specific router, then the average waiting time of each hop to send data is S^2/[2(S+A)]. If we adopt Wei Expires February 8, 2010 [Page 6] Internet-Draft routing method based on detection frames August 2009 this method, assume that there are two links for each hop to reach the destination node. Data can be sent each time as long as there is any active neighbor node. So the average waiting time of each hop is S^3/[3(S+A)^2] . It shows that delay time has been reduced. If each hop has more neighbor nodes to reach the destination node, then the average delay can be reduced much more. Reducing of the average delay time means that the router can reduce the waiting time for the next hop node to wake up time, reduce the sending of wake-up detection frame, and thus reduce energy consumption and interference to the outside. Also as each hop may have several options links, which increase the robustness of the network and reduce the demand for routing repair. 5. Security Considerations TBD 6. IANA Considerations TBD 7. Acknowledgments TBD 8. References 8.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 8.2. Informative References [I-D.ietf-roll-building-routing-reqs] Martocci, J., Riou, N., Mil, P., and W. Vermeylen, "Building Automation Routing Requirements in Low Power and Lossy Networks", draft-ietf-roll-building-routing-reqs-05 (work in progress), February 2009. [I-D.ietf-roll-home-routing-reqs] Porcu, G., "Home Automation Routing Requirements in Low Power and Lossy Networks", Wei Expires February 8, 2010 [Page 7] Internet-Draft routing method based on detection frames August 2009 draft-ietf-roll-home-routing-reqs-06 (work in progress), November 2008. Author's Address Anni Wei Huawei Technologies Huawei Building, Xinxi Road No.3 Haidian District, Beijing 100085 P. R. China Phone: +86-10-82836297 Email: weianni@huawei.com Wei Expires February 8, 2010 [Page 8]