Patent Publication Number: US-2007115847-A1

Title: Method and apparatus to estimate link performance in a packetized communication network

Description:
FIELD OF THE INVENTION  
      The present invention relates generally to communication networks; and in particular to link performance estimation mechanisms within packetized communication networks.  
     BACKGROUND  
      Within the growing communications industry, networks utilizing packet switching protocols are becoming more and more prevalent. Packet switching refers to protocols in which messages are divided into packets before they are sent. Each packet is then transmitted individually and can even follow different routes to its destination. Once all the packets forming a message arrive at the destination, they are recompiled into the original message.  
      Many of today&#39;s Wide Area Network (WAN) protocols, including Transmission Control Protocol/Internet Protocol (TCP/IP), X.25, and Frame Relay, are based on packet-switching technologies. Packet switching is more efficient and robust than traditional circuit-switching technology for data that can withstand some delays in transmission, such as e-mail messages and Web pages.  
      In recent years, a type of mobile communications network known as an “ad-hoc” network has been developed. In this type of network, each mobile node is capable of operating as a base station or router for the other mobile nodes, thus eliminating the need for a fixed infrastructure of base stations. As can be appreciated by one skilled in the art, network nodes transmit and receive data packet communications in a multiplexed format, such as time-division multiple access (TDMA) format, code-division multiple access (CDMA) format, or frequency-division multiple access (FDMA) format.  
      More sophisticated ad-hoc networks are also being developed which, in addition to enabling mobile nodes to communicate with each other as in a conventional ad-hoc network, further enable the mobile nodes to access a fixed network and thus communicate with other mobile nodes, such as those on the public switched telephone network (PSTN), and on other networks such as the Internet.  
      As can be appreciated by one skilled in the art, since certain nodes of the ad-hoc network are mobile, it is necessary for the network to maintain connectivity with those nodes. Transmitted data packets typically “hop” from mobile device to mobile device, creating a transmission path, or route, until reaching a final destination. However, transmission paths between mobile devices are often subject to change as devices move, therefore ad-hoc network communication must be able to adapt to achieve optimum performance while addressing the limited capabilities and capacities of mobile individual devices.  
      In order to optimize network performance, techniques have been developed which enable nodes to select optimum links via which to send data packets between each other. Some techniques estimate link reliability based on signal strength. Unfortunately, signal strength does not necessarily provide an accurate measure of link reliability.  
      Link quality measurements can also be based on an assessment of the number of errors encountered in a wireless communication channel. Such assessments do not accurately determine the impact of failures, especially of control packet failures.  
    
    
     BRIEF DESCRIPTION OF THE FIGURES  
      The accompanying figures, where like reference numerals refer to identical or functionally similar elements throughout the separate views and which together with the detailed description below are incorporated in and form part of the specification, serve to further illustrate various embodiments and to explain various principles and advantages all in accordance with the present invention.  
       FIG. 1  is a block diagram of an example communication network employing a system and method in accordance with an embodiment of the present invention.  
       FIG. 2  is a block diagram illustrating an example of a communication device employed in the communication network shown in  FIG. 1  in accordance with an embodiment of the present invention.  
       FIGS. 3 through 5  illustrate exemplary system parameters that may be stored in a memory of the communication device of  FIG. 2 .  
       FIG. 6  is a flowchart illustrating one embodiment of the operation of a link performance estimator within the communication device of  FIG. 2  in accordance with the present invention.  
       FIGS. 7 through 13  illustrate exemplary communications within the communication network of  FIG. 1 . 
    
    
      Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of embodiments of the present invention.  
     DETAILED DESCRIPTION  
      Before describing in detail embodiments that are in accordance with the present invention, it should be observed that the embodiments reside primarily in combinations of method steps and apparatus components related to a method and apparatus to estimate link performance in a packetized communication network. Accordingly, the apparatus components and method steps have been represented where appropriate by conventional symbols in the drawings, showing only those specific details that are pertinent to understanding the embodiments of the present invention so as not to obscure the disclosure with details that will be readily apparent to those of ordinary skill in the art having the benefit of the description herein.  
      In this document, relational terms such as first and second, top and bottom, and the like may be used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. The terms “comprises,” “comprising,” or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. An element proceeded by “comprises . . . a” does not, without more constraints, preclude the existence of additional identical elements in the process, method, article, or apparatus that comprises the element.  
      It will be appreciated that embodiments of the invention described herein may be comprised of one or more conventional processors and unique stored program instructions that control the one or more processors to implement, in conjunction with certain non-processor circuits, some, most, or all of the functions of a method and apparatus to estimate link performance in a packetized communication network described herein. The non-processor circuits may include, but are not limited to, a radio receiver, a radio transmitter, signal drivers, clock circuits, power source circuits, and user input devices. As such, these functions may be interpreted as steps of a method to estimate link performance in a packetized communication network. Alternatively, some or all functions could be implemented by a state machine that has no stored program instructions, or in one or more application specific integrated circuits (ASICs), in which each function or some combinations of certain of the functions are implemented as custom logic. Of course, a combination of the two approaches could be used. Thus, methods and means for these functions have been described herein. Further, it is expected that one of ordinary skill, notwithstanding possibly significant effort and many design choices motivated by, for example, available time, current technology, and economic considerations, when guided by the concepts and principles disclosed herein will be readily capable of generating such software instructions and programs and ICs with minimal experimentation.  
      As will be appreciated by those of ordinary skill in the art, in traditional packet completion rate (PCR)-based link quality calculation, the penalty for a lost Request to Send (RTS) is the same as for a lost packet. This ensures that broken links are properly detected and dealt with. However, numerous RTS errors are caused by hidden node problems which are common with traditional Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) Media Access Controls (MACs). Such errors are expected, and in most conditions (i.e. about two or three RTS retries per packet sent) the impact on performance is minimal. Since the route metric (and by extension, the Link Quality values) is representative of the performance, the penalty that is applied for RTS retries should not be as drastic. Preferably, it should be representative of the actual capacity of the link.  
      The present invention as described herein comprises a method and apparatus to estimate link performance in a packetized communication network. The described invention estimates link performance in a packetized communication network by identifying one or more system parameters of the packetized communication network; obtaining transaction feedback of one or more packetized communications within a communication link of the packetized communication network; and estimating performance of the communication link using the identified system parameters and obtained transaction feedback.  
       FIG. 1  is a block diagram illustrating an example of a communication network  100  employing an embodiment of the present invention. For illustration purposes, the communication network  100  comprises an adhoc wireless communications network. For example, the adhoc wireless communications network can be a mesh enabled architecture (MEA) network or an 802.11 network (i.e. 802.11a, 802.11b, or 802.11g) It will be appreciated by those of ordinary skill in the art that the communication network  100  in accordance with the present invention can alternatively comprise any packetized communication network. For example, the communication network  100  can be a network utilizing packet data protocols such as TDMA (time division multiple access), GPRS (General Packet Radio Service) and EGPRS (Enhanced GPRS).  
      As illustrated in  FIG. 1 , the communication network  100  includes a plurality of mobile nodes  102 - 1  through  102 - n  (referred to generally as nodes  102  or mobile nodes  102  or mobile communication devices  102 ), and can, but is not required to, include a fixed network  104  having a plurality of access points  106 - 1 ,  106 - 2 , . . .  106 - n  (referred to generally as nodes  106  or access points  106 ), for providing nodes  102  with access to the fixed network  104 . The fixed network  104  can include, for example, a core local access network (LAN), and a plurality of servers and gateway routers to provide network nodes with access to other networks, such as other ad-hoc networks, a public switched telephone network (PSTN) and the Internet. The communication network  100  further can include a plurality of fixed routers  107 - 1  through  107 - n  (referred to generally as nodes  107  or fixed routers  107  or fixed communication devices  107 ) for routing data packets between other nodes  102 ,  106  or  107 . It is noted that for purposes of this discussion, the nodes discussed above can be collectively referred to as “nodes  102 ,  106  and  107 ”, or simply “nodes” or alternatively as “communication devices.” 
      As can be appreciated by one skilled in the art, the nodes  102 ,  106  and  107  are capable of communicating with each other directly, or via one or more other nodes  102 ,  106  or  107  operating as a router or routers for packets being sent between nodes. As illustrated in  FIG. 1 , each node communicates with other neighboring nodes using a transmitting link and a receiving link associated with the node and each of the neighboring nodes. For example, node  102 -N, as illustrated, communicates with node  107 -N using a transmitting link  110 -A and a receiving link  120 -A, communicates with node  106 -N using a transmitting link  110 -B and a receiving link  120 -B, and communicates with node  102 - 7  using a transmitting link  110 -C and a receiving link  120 -C. Associated with each communication link (i.e. each transmitting link  110  and each receiving link  120 ) are one or more transaction feedback of one or more packetized communications. The transaction feedback can include, for example, one or more success ratios, packet size information, data rate information, signal-to-noise ratio, signal quality, noise, bit-error rate, frequency channel, time-slot, antenna information and signal strength estimation information. The success ratios, for example, can include one or more data packet success ratios and one or more control packet success ratios. The packet success ratio is the fraction of packets that are correctly delivered prior to expiration of their deadlines. For MAC methods that use control packets to perform a handshake protocol to coordinate the transmission of the actual data, the overall packet success ratio depends on the control packet success ratio and the data packet success ratio.  
      As will be appreciated by those of ordinary skill in the art, the communication network  100  has one or more system parameters associated therewith. The system parameters, for example, can include system overhead information. The overhead information, for example, can include information pertaining to at least one of signaling time, acknowledgement (ACK) processing time, ACK time, ACK time-out, back-off time, fairness time and congestion time relating to the communications between the nodes. The one or more system parameters can further include packet size information, data rate information, signal-to-noise ratio, signal quality, noise, bit-error rate, frequency channel, time-slot, antenna information and signal strength estimation information. a data rate, a data size, a header, a request to send, a clear to send, a frame size, a channel access, a back-off timer, a duration of a successful message transmission, a duration of a successful data packet transmission, a duration of a successful control packet transmission, a time period required if a data packet transmission fails, and a time period required if a control packet transmission fails. When the communication network  100  is an 802.11 network, the one or more system parameters can include a slot time, a Short InterFrame Space (SIFS) time, a Distributed Interframe Space (DIFS) time, a minimum contention window, a maximum contention window, a Physical Layer Convergence Protocol (PLCP) preamble duration, and a PLCP header duration. When the communication network  100  is a MEA network, the system parameters can include a request to send transmission time, a clear to send processing sign, a clear to send transmission time, a data processing time, a data retune time, a data transmission time, an acknowledgement processing time, and an acknowledgement transmission time.  
       FIG. 2  is an electronic block diagram of one embodiment of a communication device  200  in accordance with the present invention. The communication device  200 , for example, can exemplify one or more of the nodes  102 ,  106 , and  107  of  FIG. 1 . As illustrated, the communication device  200  includes an antenna  205 , a transceiver (or modem)  210 , a controller  215 , a user notification means  225 , and a memory  220 .  
      The antenna  205  intercepts transmitted signals from one or more nodes  102 ,  106 ,  107  within the communication network  100  and transmits signals to the one or more nodes  102 ,  106 ,  107  within the communication network  100 . The antenna  205  is coupled to the transceiver  210 , which employs conventional demodulation techniques for receiving and transmitting communication signals, such as packetized signals, to and from the communication device  200  under the control of the controller  215 . The packetized data signals can include, for example, voice, data or multimedia information, and packetized control signals, including node update information. When the transceiver  210  receives a command from the controller  215 , the transceiver  210  sends a signal via the antenna  205  to one or more devices within the communication network  100 . In an alternative embodiment (not shown), the communication device  200  includes a receive antenna and a receiver for receiving signals from the communication network  100  and a transmit antenna and a transmitter for transmitting signals to the communication network  100 . It will be appreciated by one of ordinary skill in the art that other similar electronic block diagrams of the same or alternate type can be utilized for the communication device  200 .  
      Coupled to the transceiver  210 , is the controller  215  utilizing conventional signal-processing techniques for processing received messages. It will be appreciated by one of ordinary skill in the art that additional processors can be utilized as required to handle the processing requirements of the controller  215 .  
      In accordance with the present invention, the controller  215  includes a link performance estimator  230  for estimating the performance of the various links in which the communication device  200  is connected within the communication network  100 . It will be appreciated by those of ordinary skill in the art that the link performance estimator  230  can be hard coded or programmed into the communication device  200  during manufacturing, can be programmed over-the-air upon customer subscription, or can be a downloadable application. It will be appreciated that other programming methods can be utilized for programming the link performance estimator  230  into the communication device  200 . It will be further appreciated by one of ordinary skill in the art that the link performance estimator  230  can be hardware circuitry within the communication device  200 . In accordance with the present invention, the link performance estimator  230  can be contained within the controller  215  as illustrated, or alternatively can be an individual block operatively coupled to the controller  215  (not shown).  
      To perform the necessary functions of the communication device  200 , the controller  215  is coupled to the memory  220 , which preferably includes a random access memory (RAM), a read-only memory (ROM), an electrically erasable programmable read-only memory (EEPROM), and flash memory. The memory  220 , in accordance with the present invention, includes storage locations for the storage of one or more link transaction feedback  235 , one or more system parameters,  240 , and the like.  FIGS. 3 through 5  illustrate exemplary system parameters  240  that may be stored in the memory  220  for an 802.11b network, an 802.11a network, and am 802.11g network respectively.  
      It will be appreciated by those of ordinary skill in the art that the memory  220  can be integrated within the communication device  200 , or alternatively, can be at least partially contained within an external memory such as a memory storage device. The memory storage device, for example, can be a subscriber identification module (SIM) card. A SIM card is an electronic device typically including a microprocessor unit and a memory suitable for encapsulating within a small flexible plastic card. The SIM card additionally includes some form of interface for communicating with the communication device  200 .  
      Preferably, the user notification means  225  is coupled to the controller  215 . The user notification means  225 , for example, can be a visual notification on a display. The display can be, for example, a liquid crystal display utilized to display text and graphics. It will be appreciated by one of ordinary skill in the art that other similar displays such as cathode ray tube displays, organic light emitting diodes, LEDs, or plasma displays can be utilized for the display. Alternatively, the user notification means  225  can be an alert using, for example, a speaker with associated speaker drive circuitry capable of playing melodies and other audible alerts, a vibrator with associated vibrator drive circuitry capable of producing a physical vibration, or one or more LEDs (not shown) with associated LED drive circuitry capable of producing a visual alert. It will be appreciated by one of ordinary skill in the art that other similar notification means as well as any combination of the audible, vibratory, and visual alert outputs described can be used for the user notification means  225 .  
       FIG. 6  is a flowchart illustrating one embodiment of the operation of the link performance estimator  230  in accordance with the present invention. Specifically,  FIG. 6  illustrates an operation of estimating link performance in a packetized communication network. As illustrated, the process begins with Step  600  in which the link performance estimator  230  identifies one or more system parameters of the packetized communication network in which the communication device  200  is operating. The system parameters, for example, can be retrieved from the memory  220  as described previously herein. Next, in Step  605 , the link performance estimator  230  identifies a link in which performance information is required/desired. The link, for example, can be a communication link within the packetized communication network in which the communication device is receiving or transmitting messages.  
      Next, in Step  610 , the link performance estimator  230  obtains one or more transaction feedback  235  of one or more packetized communications within the identified communication link of the packetized communication network. In one embodiment, the transaction feedback  235  can be stored in the memory  220  of the communication device  200 . For example, when the transaction feedback  235  includes one or more transmit success counts, the success ratios can be calculated using, for example, using the methods described in U.S. patent application No. 20040260808 entitled “Method to provide a measure of link reliability to a routing protocol in an ad hoc wireless network”, filed on Jun. 7, 2004, and assigned to the assignee of the present invention, the entire content of which being incorporated herein by reference.  
      Next, in Step  615 , the link performance estimator  230  estimates performance of the communication link using the identified system parameters and the obtained transaction feedback. Step  615 , for example can include calculating the link performance at a particular hop using the following equation:  
       G   =     L       T   d     +     T   q     +     T     w   ⁢           ⁢   0               
         T   d     =         t   sd       pcr   d       +       t   sc         pcr   d     ⁢     pcr   c         +         t   e     ⁡     (     1   -       pcr   d     ⁢     pcr   c         )           pcr   d     ⁢     pcr   c               
 
      where:  
      G is the effective throughput (goodput)  
      T d  is the average message transmission delay  
      T q  is the average queuing delay  
      T W0  is the average initial channel contention delay  
      L is the average packet size  
      pcr d (h) is the data packet success ratio  
      pcr c (h) is the control packet success ratio  
      t sc (h) is the duration of successful control packet transmissions  
      t sd (h) is the duration of successful data packet transmissions  
      t e (h) is the extra time required if the packet transmission fails  
      The benefits of selecting a route using a link performance estimation that takes into account system parameters as well as feedback from a lower layer component (such as the Physical Layer or the Medium Access Controller) are threefold. Firstly, the link performance estimation is directly related to the maximum performance that is possible to attain using a communication link. In a communication network, it is preferable to estimate the performance of the link before new traffic is being sent over it, because localized failures may lead to generalized network instability. Secondly, the link performance estimation described in the current invention only requires a minimum amount of feedback to operate: namely the count of successful and failed transmission. Thirdly, the operations described can be implemented using a comparatively small amount of memory in a microprocessor, making an embedded implementation especially attractive if the number of neighbors one node must keep track of is comparatively large.  
      For an implementation in a multihopping wireless network, the metric M is defined by considering the link performance metric G(h) which is based on the effective throughput (goodput) at each hop h:  
       {     M   =     α   ·       ∑     h   =   1     H     ⁢     G   ⁡     (   h   )                 
 
 where a is an arbitrary scaling factor. The usefulness of the link performance indicator will be illustrated by assuming that G=L/T d  (and therefore, that T q  and T w0  are comparatively small). The metric can therefore be written as  
       M   =         α   L     ·       ∑     h   =   1     H     ⁢     (                 t   sc     ⁡     (   h   )       +         t   sd     ⁡     (   h   )       ·       pcr   c     ⁡     (   h   )         +                 t   e     ⁡     (     1   -         pcr   d     ⁡     (   h   )       ·       pcr   c     ⁡     (   h   )           )                   pcr   d     ⁡     (   h   )       ·       pcr   c     ⁡     (   h   )           )         =       α   L     ·       ∑     h   =   1     H     ⁢         t   s     ⁡     (   h   )         LQ   ⁡     (   h   )                   
     where     
         LQ   ⁡     (   h   )       =           t   s     ⁡     (   h   )       ·       pcr   d     ⁡     (   h   )       ·       pcr   c     ⁡     (   h   )               t   sc     ⁡     (   h   )       +         t   sd     ⁡     (   h   )       ·       pcr   c     ⁡     (   h   )         +       t   e     ⁡     (     1   -         pcr   d     ⁡     (   h   )       ·       pcr   c     ⁡     (   h   )           )               
 
 Since t s (h) is the transmission time in the event that there is no error, LQ(h) is a true measure of the link&#39;s performance, irrespective of the traffic load. LQ(h) of 1 indicates a flawless link, while LQ(h) of 0.5 indicates that the link can only achieve 50% (fifty percent) of its nominal capacity. Such an indicator can be efficiently used in a wireless network because it can compare routes with one another and detect link failures. 
 
      To exemplify the present invention, an example wherein the communications network  100  is an 802.11 network is described below.  
      802.11 Networks: 802.11b, 802.11g and 802.11a use the same MAC protocol. The following section describes the MAC overhead for 802.11 networks.  
      Assumptions:  
      1) The message transmission consists of two parts: control packets transmission (RTS/CTS) and data packets transmission (DATA/ACK). pcr c  corresponds to the successful transmissions of RTS and CTS while pcr d  corresponds to the successful transmissions of DATA (only data failure is considered, ACK failure is ignored).  
      2) A packet is subject to three delays: a) queueing delay; b) initial channel contention delay; c) packet transmission delay including retries.  
      3) The final computation is done by assuming an infinite retry limit.  
      4) The same transmission parameters are used for the retries of the same packet. The aim is to find total time required for successful transmission of a packet with a selected rate.  
      5) The threshold below which there is no RTS/CTS exchange is set to an arbitrarily low value (i.e. below the minimum packet size). The overhead computation can be extended to accomodate two sets of overhead, one for packets smaller than the RTS/CTS threshold, another for packets larger than the RTS/CTS threshold. If no RTS/CTS exchange occurs, the corresponding times should be subtracted from the overall delay computation. Similarly, if a group acknowledgment is used, the fragmentation computation should be modified accordingly. The formulations presented in this document can be easily changed for this purpose.  
      6) Propagation delays in the wireless medium are ignored.  
      The table below describes each of the symbols to be used in the equations herein.  
                                   Symbol   Description                  T failure     Transmission time in the event of a failure       t s     Transmission time in the event of a success       T success     Transmission time in the event of a success       t sd     Transmission time of data part in the event of a           success       t sc     Transmission time of control part in the event of           a success       CWmin   Minimum contention window       CWmax   Maximum contention window       L   Packet length in bytes       R   Data rate       R b     Control packet rate (RTS and CTS)       R′ b     Control packet rate (ACK)       aSlotTime   Slot duration       T bckoff     Average backoff time       I   Number of consecutive transmission failures       t rts     RTS duration       t cts     CTS duration       t data     Data packet duration       aDIFSTime   DIFS duration       aSIFSTime   SIFS duration       T failure     —   data   Transmission time in the event of a data failure       t ack     Transmission time of an acknowledgment       t csma     Waiting time due to the contention in the shared           medium       t ed     Extra time required for transmission when data           packet&#39;s transmission fails       T failure     —   control   Transmission time in the event of a control failure       t ack     —   tout   Acknowledgment timeout duration       R Sb     OFDM bits per symbol for control packet       R s     OFDM bits per symbol for data packet       tPLCPPreamble   PLCP Preamble duration       tPLCPHeader   PLCP header duration       t ec     Extra time required for transmission when control           packet&#39;s transmission fails       t e     Extra time required for transmission whem           message transmission fails       L   Packet size       T d     Average packet delay       T q     Average queuing delay       T w0     Initial waiting delay before first transmission           attempt       pcr c     Control packet completion rate       pcr d     Data packet completion rate       G   Goodput (Effective throughput)       T success     —   control   Transmission time of control part in the event of           a success       t fragment     Fragment packet duration       L f     Fragment packet size       t fr     Average time to transmit a fragment and           associated ACK       T success     —   data   Transmission time of data part in the event of a           success       t cts     —   tout   CTS timeout duration       T d     Average time to transmit a packet       pcr df     Fragment packet completion rate                  
 
       FIG. 7  illustrates an exemplary successful transmission in an 802.11 network.  FIG. 8  illustrates a transmission failure due to a reception in error at the receiver.  FIG. 9  illustrates a transmission failure due to a data failure.  FIG. 10  illustrates a transmission failure due to a CTS Timeout. Note that the backoff durations after failures are incremented as described below. T failure  depends on the number of retries. The average backoff time after i consecutive unsuccessful transmission attempts is:  
           T   bkoff     ⁡     (   i   )       =     {                   2   i     ⁢     (       CW   ⁢           ⁢   min     +   1     )       -   1     2     ⁢   aSlotTime           0   ≤   i   &lt;   6                   CW   ⁢           ⁢   max     2     ⁢   aSlotTime           i   ≥   6                 
  T   success ( L,R,R   b   ,R′   b )= t   rts ( R   b )+ aSIFS Time+ t   cts ( R   b )+ aSIFS Time+ t   data ( L,R )+ aSIFS Time+ t   ack ( R′   b )+ aD      t   s ( L,R,R   b   ,R′   b )= T   success ( L,R,R   b   ,R′   b )= t   sd ( L,R,R′   b )+ t   sc ( R   b )  where    t   sd ( L,R,R′   b )= t   data ( L,R )+ aSIFS Time+ t   ack ( R′   b )+ aDIFS Time+ T   bkoff (0)  and    t   sc ( R   b )= t   rts ( R   b )+ aSIFS Time+ t   cts ( R   b )+ aSIFS Time    T   failure     —     data ( L,R,R   b   ,j )= t   rts ( R   b )+ aSIFS Time+ t   cts ( R   b )+ aSIFS Time+ t   data ( L,R )+ t   ack     —     tout   +aDIFS Time+ T   bkoff ( j )+ t   csma      T   failure     —     control ( R   b   ,j )= t   rts ( R   b )+ t   cts     —     tout   +aDIFS Time+ T   bkoff ( j )+ t   csma    
 T failure  can be written in terms of T success  as: 
   T   faiiure     —     data ( L,R,R   b   ,j )= T   success ( L,R,R   b   ,R′   b )+ t   ed   =t   s     —     d ( L,R,R′   b )+ t   s     —     c ( R   b )+ t   ed   +t   csma    where    t   ed   =t   ack     13      tout ( R   b )− aSIFS Time− t   ack ( R′   b )+ T   bkoff ( j )− T   bkoff (0)+ t   csma    
 Similarly for the control channel: 
   T   failure     —     control ( R   b   ,j )= T   success     —     control ( R   b )+ t   ec   =t   sc ( R   b )+ t   ec   +t   csma    where    t   ec   =t   cts     —     tout   +aDIFS Time+ T   bkoff ( j )− aSIFS Time− t   cts ( R   b )− aSIFS Time+ t   csma   =t   cts     —     tout   −t   cts ( R   b )− aSIFS Time+2SlotTime+ T   bkoff ( j )+ t   csma    and  
 t csma =waiting time due to the contention in the shared medium 
 
      The parameters used in the computation of transmission time are described for 802.11b, g and a in the following sections.  
      For 802.11b: 
 
 t   data   =tPLCP Preamble+ tPLCP Header+( L )*8 /R   1  
 
    1  28 bytes of MAC header are included in L.  
 
 t   ack   =tPLCP Preamble+ tPLCP Header+(14)*8 /R   b  
 
      For 802.11a and 802.11g: 
 
 t   data   =tPLCP Preamble+ tPLCP Header+┌( L+ 22/8)*8 /R   S   ┐t   s  
 
 t   ack   =tPLCP Preamble+ tPLCP Header+┌(14+22/8)*8 /R   Sb   ┐t   s  
 
 R s  and R Sb  are the bits per symbol for data bits and acknowledgement packets respectively, while t s  is the symbol duration. The RTS is 20 bytes long while CTS is 14 bytes long. They are both transmitted at the base rates. 
 
      For 802.11b: 
 
 t   rts   =tPLCP Preamble+ tPLCP Header+20*8 /R   b  
 
 t   cts   =tPLCP Preamble+ tPLCP Header+14*8 /R   b  
 
      For 802.11a and 802.11g: 
 
 t   rts   =tPLCP Preamble+ tPLCP Header+┌(20+22/8)*8 /R   Sb   ┐t   s  
 
 t   cts   =tPLCP Preamble+ tPLCP Header+┌(14+22/8)*8 /R   Sb   ┐t   s  
 
 R Sb  is the bits per symbol while t s  is the symbol duration. 
 
 When the limit of the number of transmissions per packet approaches infinity and averaging T_bkoff(j) to (CWmin+Cwmax)/2, T d  can be approximated as 2 :    2  For simplicity, arguments of the functions are omitted (e.g. pcr c (R b )=pcr c ).   
         T   d     =       ∑     n   =   1     ∞     ⁢       ∑     m   =   1     ∞     ⁢           (     m   +   n   -   2     )     !           (     m   -   1     )     !     ⁢       (     n   -   1     )     !         ⁢     pcr   c   m     ⁢         pcr   d     ⁡     (     1   -     pcr   c       )         n   -   1       ⁢       (     1   -     pcr   d       )       m   -   1       ⁢     (       m   ⁢           ⁢     t             ⁢   sd         +       (     n   +   m   -   1     )     ⁢     t             ⁢   sc         +       (     m   -   1     )     ⁢     t             ⁢   ed                       
 
 By using series approximations, the following equation is derived:  
         T   d     =         t   sd       pcr   d       +       t   sc         pcr   d     ⁢     pcr   c         +         t   ed     ⁡     (     1   -     pcr   d       )         pcr   d       +         t   ec     ⁡     (     1   -     pcr   c       )           pcr   d     ⁢     pcr   c               
         If   ⁢           ⁢     t   ed       ≈     t   ec     ≡     t   e         
         T   d     =         t   sd       pcr   d       +       t   sc         pcr   d     ⁢     pcr   c         +         t   e     ⁡     (     1   -       pcr   d     ⁢     pcr   c         )           pcr   d     ⁢     pcr   c               
 
 For a given signal strength, the effective throughput can be computed as:  
       G   =     L       T   d     +     T   q     +     T     w   ⁢           ⁢   0               
 
      A tagged packet that is successfully transmitted has three delay components: waiting delay (T q ) in the queue, initial channel access delay (T w0 ) and transmission delay (T d ) including the retransmission attempts. T d  can be computed by adding airtime and overhead using techniques known to one skilled the art. An example for the computation of T d  is presented herein. The average queuing delay T q  can be computed from the average queue size and packet delay T d +T w0  since a new packet is enqueued, it has to wait for the packets that are already in the queue. There may be limitations in lifetime of packets, however dropping packets due to the lifetime or exceeding a certain number of retries should be infrequent and shouldn&#39;t change the average value. The initial channel access delay T w0  for the packet that becomes head of the queue can be approximated as t csma ·t csma  can be measured using channel monitoring times (e.g. CCA/NAV busyness).  
      Fragmentation  
       FIG. 11  illustrates a successful transmission of fragments in 802.11 networks (which use an immediate ACK policy).  FIG. 12  illustrates a transmission failure due to the failure of the first fragment.  FIG. 13  illustrates a transmission failure due to the failure of the second fragment which is retransmitted.  
      In addition to the assumptions described above, it is assumed that every fragment has the same packet completion rate and data length.  
      As described in the previous section, the total time as a function of successful and failure times can be written as 
 
 t   sc ( R   b )= t   rts ( R   b )+ aSIFS Time+ t   cts ( R   b )+ aSIFS Time+ aDIFS Time+ T   bkoff (0) 
 
 t   fr ( L   f   ,R, R′   b )= t   fragment ( L   f   ,R )+2  aSIFS Time+ t   ack ( R′   b ) 
 
      For 802.11b: 
 
 t   fragment ( L   f   ,R )= tPLCP Preamble+ tPLCP Header+( L   f )*8 /R   3  
 
 t   ack ( R′   b )= tPLCP Preamble+ tPLCP Header+(14)*8 /R′   b  
 
      For 802.11a and 802.11g: 
 
 t   fragment ( L   f   ,R )= tPLCP Preamble+ tPLCP Header+┌( L   f +22/8)*8 /R   S   ┐t   s  
 
 t   ack ( R′   b )== tPLCP Preamble+ tPLCP Header+┌(14+22/8)*8 /R   Sb   ┐t   s  
 
 t rts , t cts  and mean_bkoff are computed as described in the previous section. 
 
 t   fr ( L   f   ,R,R′   b )= t   fragment ( L   f   ,R )+2 aSIFS Time+ t   ack ( R′   b ) 
 
 when n fragments are transmitted successfully: 
 
 T   success     —     data ( n,R,R   b )= T   sc ( R   b )+ n t   fr ( L   f   ,R, R′   b )= t   sc ( R   b )+ n t   fr ( L   f   ,R,R′   b ) 
 
T failure  can be written in terms of T success  as the following when the n th  fragment fails: 
 
 T   failure     —     data ( n,R,j,R   b )= T   success     —     data ( n,R,R   b )+ t   ed   +t   csma   =t   sc ( R   b )− T   bkoff (0)+ T   bkoff ( j )+ t   ack     —     tout −2 aSIFS Time− t   ack ( R′   b )+ n t   fr ( L   f   ,R,R′   b ) 
 
where 
 
 t   ed   =T   bkoff ( j )− T   bkoff (0)+ t   ack     —     tout −2 aSIFS Time− t   ack ( R′   b )+ t   csma  
 
 where 
 
 t csma =waiting time due to the contention in the shared medium 
 
 and 
 
 T   failure     —     control ( R   b   ,j )= t   rts ( R   b )+ t   cts     —     tout   +aDIFS Time+ T   bkoff ( j )+ t   csma  
 
 T   failure     —     control ( R   b   ,j )= T   sc ( R   b )+ t   ec   =t   sc ( R   b )+ t   ec   =t   sc ( R   b )+ t   ec  
 
where 
 
 t   ec   =t   cts     —     tout   −t   cts ( R   b )+ T   bkoff ( j )− T   bkoff (0)−2 aSIFS Time+ t   csma  
 
 where t csma =waiting time due to the contention in the shared medium 
 
 The average time to transmit a fragmented packet can then be computed as:  
         T   d     =       ∑     n   =   1     ∞     ⁢       ∑     m   =   1     ∞     ⁢           (     m   +   n   -   2     )     !           (     m   -   1     )     !     ⁢       (     n   -   1     )     !         ⁢         (       ∑     k   =   0     N     ⁢     …   ⁢       ∑     j   =   x     N     ⁢       ∑     i   =   j     N     ⁢     (     N   -   i     )             )     ︸         (     m   -   1     )     ⁢   times       ⁢     pcr   c   m     ⁢         pcr   df   N     ⁡     (     1   -     pcr   c       )         n   -   1       ⁢         (     1   -     pcr   df       )       m   -   1       ⁡     [               (     N   +   m   -   1     )     ⁢     t   sd       +       (     n   +   m   -   1     )     ⁢     t   sc       +                   (     m   -   1     )     ⁢     t             ⁢   ed         +       (     n   -   1     )               ⁢     t             ⁢   ec                   ]                 
     where     
               ∑     k   =   0     N     ⁢     …   ⁢       ∑     j   =   x     N     ⁢       ∑     i   =   j     N     ⁢     (     N   -   i     )             ︸         (     m   -   1     )     ⁢   times       =         Pochhammer   ⁡     [     N   ,     m   -   1       ]           (     m   -   1     )     !       =       1       (     m   -   1     )     !       ⁢       ∏     i   =   0       m   -   2       ⁢     (     N   +   i     )               
 
 By using series approximations, the following equation is derived:  
         T   d     =         N   ⁢           ⁢     t   sf         pcr   df       +         t   sc     ⁡     (       pcr   df     +     N   ⁡     (     1   -     pcr   df       )         )           pcr   df     ⁢     pcr   c         +               ⁢       t             ⁢   ed       ⁢           ⁢   N   ⁢           ⁢     (     1   ⁢           -           ⁢     pcr   df       )                   ⁢     pcr             ⁢   df           +               ⁢       t             ⁢   ec       ⁢     (     1   ⁢           -           ⁢     pcr   c       )     ⁢           ⁢     (           ⁢       pcr   df     ⁢           +           ⁢     N   ⁢     (     1   ⁢           -           ⁢     pcr   df       )         )                   ⁢       pcr   df     ⁢           ⁢     pcr   c                 
 
 If t ed ≈t ec ≡t e :  
         T   d     =         N   ⁢           ⁢     t   sf         pcr   df       +         t   sc     ⁡     (       pcr   df     +     N   ⁡     (     1   -     pcr   df       )         )           pcr   df     ⁢     pcr   c         +               ⁢       t             ⁢   e       ⁢     (           ⁢         pcr   df     ⁢     (     1   ⁢           -           ⁢     prc   c       )       ⁢           +           ⁢     N   ⁢     (     1   ⁢           -           ⁢     pcr   df       )         )                   ⁢       pcr   df     ⁢           ⁢     pcr   c                 
 
 It can be shown that for N=1 where t sf =t sd  and pcr df =pcr d , T d  is the same as derived in previous section:  
         T   d     =         t   sd       pcr   d       +       t   sc         pcr   d     ⁢     pcr   c         +         t   e     ⁡     (     1   -       pcr   d     ⁢     pcr   c         )           pcr   d     ⁢     pcr   c               
 
 For a given signal strength, the effective throughput (goodput) can be computed as:  
       G   =     L       T   d     +     T   q     +     T     w   ⁢           ⁢   0               
 
      In the foregoing specification, specific embodiments of the present invention have been described. However, one of ordinary skill in the art appreciates that various modifications and changes can be made without departing from the scope of the present invention as set forth in the claims below. Accordingly, the specification and figures are to be regarded in an illustrative rather than a restrictive sense, and all such modifications are intended to be included within the scope of present invention. The benefits, advantages, solutions to problems, and any element(s) that may cause any benefit, advantage, or solution to occur or become more pronounced are not to be construed as a critical, required, or essential features or elements of any or all the claims. The invention is defined solely by the appended claims including any amendments made during the pendency of this application and all equivalents of those claims as issued.