Internet DRAFT - draft-wei-manet-rafsp

draft-wei-manet-rafsp





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]