manet Anni. Wei Internet-Draft Huawei Technologies Intended status: Informational July 13, 2009 Expires: January 14, 2010 Routing algorithm based on the flow sensing parameter draft-wei-manet-rafsp-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 January 14, 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 January 14, 2010 [Page 1] Internet-Draft rafsp July 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 The packet loss rate of each path between the source node and destination node can be obtained through two methods, one is direct measurement, another approach is proposed in this document calculating the packet loss rate based on the flow sensing parameter. The core idea of the calculating approach is the flow sensing parameter, which can be used to calculate the packet loss rate of each path between the source node and destination node and select the path whose packet loss rate is smallest to be the data transmission path. Wei Expires January 14, 2010 [Page 2] Internet-Draft rafsp July 2009 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology used in this document . . . . . . . . . . . . . . 4 3. Problem statement and analysis . . . . . . . . . . . . . . . . 4 4. Proposed solution . . . . . . . . . . . . . . . . . . . . . . 5 4.1. overview . . . . . . . . . . . . . . . . . . . . . . . . . 5 4.2. Traffic flow of node . . . . . . . . . . . . . . . . . . . 5 4.3. Packet error probability . . . . . . . . . . . . . . . . . 9 4.4. Packet collision probability . . . . . . . . . . . . . . . 9 4.5. Packet loss rate . . . . . . . . . . . . . . . . . . . . . 10 5. packet-loss-rate-aware routing . . . . . . . . . . . . . . . . 11 6. Security Considerations . . . . . . . . . . . . . . . . . . . 11 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 12 9. Normative References . . . . . . . . . . . . . . . . . . . . . 12 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 12 Wei Expires January 14, 2010 [Page 3] Internet-Draft rafsp July 2009 1. Introduction In order to enhance data communications performance of Mobile Ad hoc Network, the routing algorithm based on the link quality is needed. In other words, the routing algorithm needs not only to be able to select the end-to-end network paths, but also to pick up the path whose performance of data communication is optimal among them. The selection of the path with optimal performance of data communication depends mainly on packet loss rate of each path between the source node and destination node which can be obtained through two methods, one is direct measurement, another approach is proposed in this paper calculating the packet loss rate based on the flow sensing parameter. In the document, the packet loss rate based on the flow sensing parameter calculates the packet loss rate of each path between the source node and destination node through the identification of the flow sensing parameter. The flow sensing parameter is including channel random bit error rate, inter-node interference flow and so on. The selection process generally includes the following two steps: First, route discovery, and the second is path measurement. The steps for routing discovery can take different ways such as the source routing program or each link program, and the step of path measurement can use complete path performance measurement or each link performance measurement approach. Taking into account the importance of end-to-end performance of the mobile data communications in Mobile Ad hoc Network, the document select the source routing program, and calculated the entire path between the source node and destination node. Also, considering packet loss rate in Mobile Ad hoc Network, we take the packet loss rate due to channel random bit error rate and node flow interference into account. 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]. random bit error rate: The bit error induced by the random radio noise. 3. Problem statement and analysis There are two main factors significantly impact on the quality of link in Mobile Ad hoc Network: First, packet loss due to bit error rate as noise interference in the wireless environment; second is due to the failure of sending the packet as data packets between the Wei Expires January 14, 2010 [Page 4] Internet-Draft rafsp July 2009 wireless nodes collide. 4. Proposed solution 4.1. overview As mentioned before, the program is based on the flow sensing parameter, calculates the packet loss rate of each path of the source node and destination node and selects path which have the smallest packet loss rate to be data transmission path. The Flow sensing parameter includes: channel random bit error rate and interference flow between nodes. The specific steps of calculation of the packet loss rate of each path between the source node and destination node are: 1. calculate the packet error probability due to channel random bit error rate in single link of each path; 2. Calculate the packet collision probability due to interference flow between nodes in single link of each path; 3. Calculate the packet loss rate of each path between the source node and destination node according to the packet error probability and the probability of packet collisions on single link. 4.2. Traffic flow of node In wireless mesh networks, there will be interference between nodes near each other as a result of the wireless channel is shared by a number of nodes, which reflected in the quality of service or the performance of the link, are higher error rate, packet collision, more delay and so on. In routing selection, in order to obtain end- to-end routing of high-performance, it is necessary to avoid region with a large of traffic. To achieve this goal, it needs to measure and obtains the interference flow of each options path, which is used for performance assessment. In wireless mesh networks, there are "exposed node" and "hidden nodes". These two types of nodes have different effects on data transmission in wireless link. The concept of "exposed node" and the "hidden node" are described respectively in figures 1 and figures 2. Wei Expires January 14, 2010 [Page 5] Internet-Draft rafsp July 2009 /-------------------\ | /--------+-----------\ | | | | | a<-----+--b c--+-------->d | | | | | \----------+--------/ | \--------------------/ Figure 1 exposed node /-------------------\ | /--------+-----------\ | | | | | a------+->b c--+-------->d | | | | | \----------+--------/ | \--------------------/ Figure 2 hidden nodes Figure 1 shows that the node b and node c is in the wireless coverage range of each other. When node b sends data to node a, node c can detect that the channel is busy, and node c will not be able to send data to node d. vice versa. Node b and node c is each other's exposed node. figure 2 shows that node a is not in the wireless coverage area of node c. When node a sends a packet, the node c detect that the channel is idle. If node c sends data at the same time, it will result in the occurrence that packet sent by node a will collided at node b, resulting in transmission failure. Node c is the "hidden node" of node a . Exposed nodes and hidden nodes have different effects on data transmission on one link. In the process of performance evaluation of link, it is essential to measure the impact of traffic flow of exposed nodes and hidden node respectivly on this link. The flow of each node consists of two parts: traffic flow of exposed node and hidden node . Method of flow measurement: each node records the data traffic of neighbor node by monitoring the communication situation of neighbor nodes in promiscuous mode; collects the flow information of neighbor nodes within 2-hop though information exchange between neighbor nodes; calculates the traffic flow of exposed nodes and hidden node according to the information above. Wei Expires January 14, 2010 [Page 6] Internet-Draft rafsp July 2009 We illustrate the flow measurement method of each node in Figure 3. Node a1,node a2,node a3 and node j are in the wireless coverage area and are 1-hop neighbor nodes of node i as shown in Figure 3. Node i will be placed in promiscuous wireless communication module, and monitor data of 1-hop neighbor nodes in real-time, record and update the flow information 1-hop neighbor nodes periodically. The results of flow information will be stored in a "1-hop neighbor node flow Table "(NLT1). Flow table of 1-hop neighbor node is as shown in table 1. Data flow of 1-hop neighbor nodes is the average flow of the traffic period with each cycle length T. In a cycle of a 1-hop neighbor nodes, a total data transmission capacity is B, then the data flow of 1-hop neighbor nodes is f=B/T. /-------------------\ | | c1<-------+--a1 /--------+-----------\ | | | b1---+------>d1 | |i---->j | | | | | | c2<-----+-a2 | a3 | | \----------+----|---/ b2--+----->d2 \----|---------------/ | V c3 Figure 3 detection of node's traffic flow +-------------+-----------+----------------+------------+ |serial number|source node|destination node|traffic flow| +-------------+-----------+----------------+------------+ | 1 | a1 | c1 | f(a1,c1) | +-------------+-----------+----------------+------------+ | 2 | a2 | c2 | f(a2,c2) | +-------------+-----------+----------------+------------+ | 3 | a3 | c3 | f(a3,c3) | +-------------+-----------+----------------+------------+ | ... | ... | ... | ... | +-------------+-----------+----------------+------------+ Table 1 "1-hop neighbor node flow Table "(NLT1)of node i Nodes in wireless mesh network periodically broadcast its NLT1.Each Wei Expires January 14, 2010 [Page 7] Internet-Draft rafsp July 2009 row of NLT1, i.e. flow information of each link is corresponding to a data domain in packet broadcasted. Structure of data domain is shown in figure 4. 31 15 0 +---------------------------------+ | address of source node | +---------------------------------+ | address of destination node | +---------------------------------+ | traffic flow | +---------------------------------+ Figure 4 Structure of data domain For each node, it can receive the "1-hop neighbor node flow table" of all of its 1-hop neighbor nodes , which means that it can obtain the flow information of all 2-hop neighbor nodes. Take figure 3 as an example. Node i receives the "1-hop neighbor node flow table" of node j broadcast by node j. As b1 and b2 are 1-hop neighbors of node j, node i can get the flow information of node b1 and b2, and b1 and b2 is node i's 2-hop neighbors. Similarly, the node i can get the "1-hop neighbor node flow table" of a1, a2 and a3. So that node i will be able to obtain the flow information of all of its 2-hop neighbors, i.e. "2-hop neighbor node flow table" of node i will be realized. "2-hop neighbor node flow table" of node i is shown in table 2. +-------------+-----------+----------------+------------+ |serial number|source node|destination node|traffic flow| +-------------+-----------+----------------+------------+ | 1 | b1 | d1 | f(b1,d1) | +-------------+-----------+----------------+------------+ | 2 | b2 | d2 | f(b2,d2) | +-------------+-----------+----------------+------------+ | ... | ... | ... | ... | +-------------+-----------+----------------+------------+ Table 2 "2-hop neighbor node flow Table "(NLT2)of node i In figure 3, it is assumed that node i sends message to its neighbor node j, then flows of node i's exposed nodes is the sum of all the link flows in NLT1 ,which can be calculated as formula(1): f_exposed(i)= f(a1,c1)+f(a2,c2)+...+f(m,n) (1) here,(m,n)is included Wei Expires January 14, 2010 [Page 8] Internet-Draft rafsp July 2009 in NLT1. Node b1 and b2 are hidden nodes of node i. Therefore, the hidden nodes of node i is the nodes in the 1-hop neighbor node of node j (node i!(R)s destination node )except 1-hop neighbor nodes of node i. Flow of hidden nodes can be calculated as formula(2) f_hidden(i)= f_expose(j)-sum of f(m,n) (2) here,(m,n)must be included both in NLT1(i) and NLT1(j),such as (a3,c3). Table 2 "2-hop neighbor node flow Table "(NLT2)of node i 4.3. Packet error probability The calculation of the packet error probability due to the channel random bit error rate: begin with the calculation of packet loss rate on single link, and then come to end-to-end path packet loss rate referred to packet loss rate on single link. Assuming the channel random bit error rate of a single link (i, j) is p(0), the link bandwidth is B, the packet length is L. While packets are sending from node i to node j, for the node i, the total flow of the exposed node is f_exposed , the total flow of the hidden node is f_hidden . Therefore, for the packet whose length is L, the packet error probability due to channel random bit error rate can be calculated by the formula (3): p(e)=1-(1-p(0))^L (3) Among them,p(e)is single link packet error probability,p(0)is channel random bit error rate of the single link, L is the length of the packet. 4.4. Packet collision probability The calculation of packet collision probability due to interference flow between nodes: while sending the packet from node i to node j, packets sent by the hidden nodes and packets from node i may collide, resulting in packet loss. The probability of packet collisions is closely related to the data flow of the hidden nodes. The greater Data flow, the greater collision probability .In addition, the probability of packet collisions is closely related to MAC layer algorithm of wireless mesh network, different MAC layer (Medium Access Control, MAC) channel access mechanisms will produce different probability of packet collisions. In this document, the probability of packet collisions was calculated Wei Expires January 14, 2010 [Page 9] Internet-Draft rafsp July 2009 based on CSMA/CA (Carrier Sensor Multiple Access with Collision Avoidance) MAC layer algorithm. In CSMA/CA mechanism, if node i found any other node around sending data, then it will wait for idle channel to send data; If the detected channel is idle, node i start sending data. Thus, there are two conditions for the collision when packets send by node i: First, node i is in an idle channel, and the other is the hidden node of node i is sending data at the same time. Based on the analysis, we can see that the physical meaning of node i's packet collision probability is in fact the ratio of interference time of hidden node on channel and data distribution time window of node i. Here, we use the normalized method to calculate the probability of packet collisions. The total channel time of Node i is "1", the time window node i can send data need to exclude the time when the exposed nodes are sending the data. According to f_exposed which is assumed the total data flow of the exposed nodes, the time for exposed nodes sending the data is f_exposed/B, the corresponding node i's time window for data distribution is 1-f_exposed/B , and interference time of the hidden node is f_hidden/B. Therefore, the packets collision probability between the node i and node j can be calculated by formula (4): p(c)=f_hidden/(B-f_exposed),if 0<=f_hidden/(B-f_exposed)<=1 (4) p(c)=1,else 4.5. Packet loss rate On the basis of the packet error probability and the packet collisions probability of single link, calculate the packet loss rate of each path between the source node and destination node. Based on the above steps calculated the packet error probability and the packet collisions probability, the probability of one success of packet sending between node i and node j can be calculated in accordance with the formula (5): p(s)=(1-p(e))*(1-p(c)) (5) Then, taking into account with the limited packet retransmit times mechanism of MAC layer protocol, the number of retransmitting packets is recorded as LRL (Long Retry Limit), then after LRL packet retransmission ,the packets missing probability is as follows: p(link)=(1-p(s))^(LRL-1) (6) Wei Expires January 14, 2010 [Page 10] Internet-Draft rafsp July 2009 p(link)is the single link packet loss rate of the path between the source node and destination node, p(s) is the probability of one success of packet sending on the single link, LRL is the time to retransmit packets. Based on the single link packet loss rate, the packet loss rate of an end-to-end path can be calculated. N is the path length for the jump, the packet loss rate on every single link is expressed as p(link)^i, the end-to-end packet loss rate can be calculated by the formula (7): p(path)=1-[(1-p(link)^1)(1-p(link)^2)...(1-p(link)^N)] (7) So, through the above-mentioned process, the packet loss rate of each path between the source node and destination node can be calculated. The path with smallest packet loss rate between the source node and destination node may be selected as the data transmission path. 5. packet-loss-rate-aware routing To enable the packet-loss-rate-aware routing mechanism, each node in the network needs to maintain a packet loss rate table. Each entry in the table is the link quality between this node and its every neighbor, obtained through the computed or measured method. Concerning the route discovery procedure, since currently most of the routing protocols used in MANET are distance vector based protocols, a feasible way to implement the packet-loss-rate-aware routing is as following: 1. The source node broadcast the RREQ packet, which should provide extra fields to allow the recording of the path and the current path cost. The path cost could be the accumulated link packet loss rate alone or some function which takes the link packet loss rate as a parameter. 2. When a node receives the RREQ packet, it should put its address into the RREQ packet, and modify the path cost by adding the cost of the current link. 3. When specified count of RREQ packets reached the destination node, the latter can choose a path which has the minimum path cost as the discovered route, and use the reverse routing to notify the source node the discovered route. 6. Security Considerations The document does not mandate any specific security measures. Wei Expires January 14, 2010 [Page 11] Internet-Draft rafsp July 2009 7. IANA Considerations There have been no IANA considerations so far in this document. 8. Acknowledgments TBD 9. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 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 January 14, 2010 [Page 12]