Abstract:
The invention concerns a method for admission control of connections made up of one or several flows to a shared wireless medium. It applies criteria for each new connection to determine whether resources can be provided for this connection. The criteria include the steps of: calculating a number (R) of retransmissions of frames which are needed, depending on: a target application PDU error rate (ε i ); a data link layer mean error rate (BER); and a maximum size (L) of the transmitted frames; calculating the achievable quality of service parameters (T′ i ) based on the calculated number (R) of retransmissions with the target application PDU error rate (ε i ), and determining if resources can be provided for the connection depending on the achievable quality of service parameter (T′ i ).

Description:
BACKGROUND OF THE INVENTION 
   The present invention concerns an admission control method of connections made up of one or several flows to a shared wireless medium, each connection requiring a predetermined target application Protocol Data Unit error rate and at least an additional quality of service requirement, the transmission on the shared wireless medium being adapted for transmitting frames of a predetermined maximum size, with a data link layer mean error rate, the method applying a criteria for each new connection to determine whether resources can be provided for this connection. We assume an ARQ (Automatic Repeat reQuest) algorithm to be implemented at the data link layer level. 
   Such a method is used for Admission Control of connections with Quality of Service requirements. 
   By connection we mean the route, established between two different network devices, dedicated to the transmission of one or several data flows. When a connection transports several flows, each data link layer Protocol Data Unit (PDU) may include data issued from different flows. 
   To reach the Quality of Service requirements, the admission control method accepts to establish a new connection only if the load associated with this new connection is lower than the remaining admissible capacity on each shared link. Given C is the total capacity of a link and ρ is its admissible load, the admissible capacity of this link is ρ×C. Assume there are k connections that are already established on the link, and connection i uses a bandwidth equal to D′ i , then the remaining admissible capacity equals 
   
     
       
         
           
             ρ 
             × 
             C 
           
           - 
           
             
               ∑ 
               
                 i 
                 = 
                 1 
               
               k 
             
             ⁢ 
             
               
                 D 
                 i 
                 ′ 
               
               . 
             
           
         
       
     
   
   Each connection may have 0, 1 or several quality of service requirements which are necessary for satisfying each user after reception of his flow. 
   For example, if an application generates a flow with a minimum throughput requirement, the data link layer shall provide a bandwidth at least equal to this throughput. 
   In addition, some frames can be erroneous. These frames have to be retransmitted by the ARQ algorithm in order to reach a target application PDU error rate. 
   In the known Admission Control Methods, no means is provided in order to be sure that the shared link capacity is sufficient to enable all the retransmissions necessary for each connection sharing the link to reach its target application PDU error rate. 
   SUMMARY OF THE INVENTION 
   The aim of the invention is to provide a method for improving the management of the resources available on a link. 
   Accordingly, the subject of the invention is a method for admission control of connections on a shared wireless medium, characterized in that said criteria includes the steps:
         calculating a number of retransmissions of frames which are needed in order to reach the target application error rate and the or each quality of service requirement, the number of retransmissions depending on:   the target application error rate;   the data link layer mean error rate; and   the maximum size of the transmitted frames;   calculating the achievable quality of service parameters based on the calculated number of retransmissions with the target application error rate, and   determining if resources can be provided for the connection depending on the or each achievable quality of service parameter.       

   According to particular embodiments, the method comprises the features of one or more sub-claims. 

   
     DESCRIPTION OF THE DRAWINGS 
     The invention will be better understood on reading the description which follows, given merely by way of example and while referring to the drawings in which: 
       FIG. 1  illustrates a network which aggregates several application PDU into a long frame; 
       FIG. 2  is a flowchart of an admission control method according to a first implementation of the invention; 
       FIG. 3  is a flowchart of an admission control method according to a second implementation of the invention; 
       FIG. 4  illustrates a network which segments each application PDU into several short frames; 
       FIG. 5  is a flowchart of an admission control method according to a third implementation of the invention, and 
       FIG. 6  is a flowchart of an admission control method according to a fourth implementation of the invention. 
   

   DETAILED DESCRIPTION 
     FIG. 1  shows a wireless telecommunication network  10  comprising a sending entity  12  adapted to communicate over an air interface with a receiving entity  14 . This network can for example be an IEEE 802.11 WLAN. 
   The sending entity  12  comprises an emitter  16  which is adapted for sending long frames (LF) of maximum size L bytes to the receiving entity  14 . The data link layer is assumed to have a mean bit error rate (BER). 
   The sending entity  12  includes several types of services  18   a ,  18   b ,  18   c  and  18   d  linked to the emitter  16 . Each type of service may provide one or several flows to the emitter  16  in order to be sent to the receiving entity  14 . The type of service  18   d  is dedicated to best-effort services. In this case, no guarantee is provided to the users, and the present invention does not apply. 
   Each flow which type of service is either  18   a ,  18   b  or  18   c  has to be received by the receiving entity  14  with a maximum application PDU error rate ε i  in order to satisfy the user. 
   In order to reach the maximum application PDU error rate ε i , the data link layer is adapted for re-transmitting the erroneous frames, when they are detected by the receiving entity. When an erroneous frame is received, the full frame is retransmitted according to the data link layer protocol. 
   In addition, one or several quality of service requirements has to be reached for each connection. 
   For example, for a voice service, the end-to-end transmission delay has to be lower than a maximum tolerated delay D i . 
   For a videoconference service, the bandwidth allocated to the connection has to guarantee a minimum throughput T i  at the application level. 
   Depending on the services, throughput or delay requirements may have to be reached in addition to the target application PDU error rate ε i . 
   The quality of service requirements D i , T i  and the target application PDU error rate ε i  have to be satisfied at the output of the receiving entity. 
   To ensure that the maximum application PDU error rate ε i  and a quality of service requirement D i  and/or T i  are reached, the emitter  16  comprises an admission control unit  20  which is in charge of implementing an admission control method as disclosed below. 
   It is assumed that an application outputs PDU TS of maximum size T bytes. 
   In case of long frames, the application PDUs are aggregated by the emitter  16  in order to make new frames LF of maximum size L bytes as shown on  FIG. 1 . The maximum size L of each new aggregated frame LF is higher than the maximum size T of each output application PDU TS plus all intermediate layers headers. 
   A first implementation of the admission control method is disclosed on  FIG. 2 . The method enables a minimum throughput T i  to be reached together with a maximum transmission application PDU error rate ε i . 
   At first stage  100 , the number R of retransmissions needed for reaching the target application PDU error rate ε i  is calculated as follows: 
             R   =     ⌈         ln   ⁡     (     ɛ   i     )         ln   ⁡     (     1   -       (     1   -     φ   ⁡     (   BER   )         )       8   ⁢   L         )         -   1     ⌉       ,         
where φ is a function. It can for example be φ(x)=x, ∀x or φ(x)=αx, ∀x, with αεR.
 
   Let κ i  be the traffic induced while crossing intermediate layers. 
   At step  102 , the bandwidth T′ i  to reserve at the data link layer level in order to reach the quality of service requirement(s) is determined based on the application throughput T i , the number of retransmissions R and the parameter κ i . 
   The bandwidth T′ i  is defined as:
 
 T′   i =(1 +R )×( T   i +κ i ).
 
   In case application PDU are emitted according to a periodic profile (P i  seconds between two consecutive application PDUs), and H i  represent the size of intermediate layers headers in bits, κ i  can be computed as 
   
     
       
         
           
             κ 
             i 
           
           = 
           
             
               
                 H 
                 i 
               
               
                 P 
                 i 
               
             
             . 
           
         
       
     
   
   At step  104 , it is checked whether the remaining link capacity is sufficient to allocate bandwidth T′ k+1  to the new connection. For example, if C is the capacity of the link from the emitter  16  to the receiver  14  and ρ is the admissible load on this link, it is determined, at step  104 , enough admissible capacity left to reserve bandwidth T′ k+1  to the new connection. Assuming that each connection i needs a bandwidth T′ i , the remaining admissible capacity equals 
             ρ   ×   C     -       ∑     i   =   1     k     ⁢       T   i   ′     .             
Thus it is checked if
 
   
     
       
         
           
             T 
             
               k 
               + 
               1 
             
             ′ 
           
           &lt; 
           
             
               ρ 
               × 
               C 
             
             - 
             
               
                 ∑ 
                 
                   i 
                   = 
                   1 
                 
                 k 
               
               ⁢ 
               
                 
                   T 
                   i 
                   ′ 
                 
                 . 
               
             
           
         
       
     
   
   If the capacity is sufficient, the new connection is established at step  106 , otherwise the connection is refused at step  108 . 
     FIG. 3  shows the algorithm of the method enabling an end-to-end transmission delay requirement D i  to be reached together with a maximum transmission application PDU error rate ε i . 
   As previously disclosed, the number R of needed retransmissions is calculated at step  200  as a function of ε i , BER and L. 
   At step  202 , the transmission duration induced by the retransmission is estimated as: D′ i =(R+1)×RTT where RTT is the Round Trip Time, that is to say the end to end time transmission delay from emitter to receiver and for the reverse path, including processing and waiting times, for each LF frame. 
   The admission control method determines at step  204  if the new calculated end-to-end transmission delay D′ i  is lower than the required maximum end-to-end transmission delay D i . If D′ i &lt;D i , the connection is established at step  206 , otherwise, the connection is refused at step  208 . 
   Two different quality of service requirements are disclosed in the algorithms of  FIGS. 2 and 3 , each requirement being reached separately. In fact, both requirements may be needed and in this case the admission control method allows a connection to be established only if both requirements are met. 
     FIG. 4  shows another wireless telecommunication network which segments application PDU. It can be for example an HiperLAN2 WLAN. 
   On  FIG. 4 , the same reference numerals refer to the same units as on  FIG. 1 . 
   In case of segmentation, the data link layer PDU are short frames denoted by SF. Their maximum size in bytes is denoted by S and is lower than the maximum size T of the application PDU denoted TS. Consequently, each application PDU TS plus intermediate layers headers are segmented by the emitter  16  in n short frames SF. 
   In case of segmentation, the number R of retransmissions is shared out between the n short frames SF that make up the TS application PDU. 
   Define α(n, R) by 
               α   ⁡     (     n   ,   R     )       =       ∑     i   =   1       inf   ⁡     (     n   ,   R     )         ⁢       C   n   i     ⁢     C     R   -   1       i   -   1             ,         
∀n, R≧1, and LER by LER=1−(1−φ(BER)) 8.S , where φ is a function. It can for example by φ(x)=x, ∀x or φ(x)=αx, ∀x, with αεR.
 
   Let E r  be the event “the application PDU TS is erroneous after r SF retransmissions”. 
   The probability IP(E r ) is computed by induction as follows: 
   
     
       
         
           
             IP 
             ⁡ 
             
               ( 
               
                 E 
                 r 
               
               ) 
             
           
           = 
           
             { 
             
               
                 
                   
                     1 
                     - 
                     
                       
                         ( 
                         
                           1 
                           - 
                           LER 
                         
                         ) 
                       
                       n 
                     
                   
                 
                 
                   
                     
                       if 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       r 
                     
                     = 
                     0 
                   
                 
               
               
                 
                   
                     
                       IP 
                       ⁡ 
                       
                         ( 
                         
                           E 
                           
                             r 
                             - 
                             1 
                           
                         
                         ) 
                       
                     
                     - 
                     
                       
                         α 
                         ⁡ 
                         
                           ( 
                           
                             n 
                             , 
                             r 
                           
                           ) 
                         
                       
                       ⁢ 
                       
                         LER 
                         r 
                       
                       × 
                       
                         IP 
                         ⁡ 
                         
                           ( 
                           
                             E 
                             0 
                           
                           ) 
                         
                       
                     
                   
                 
                 
                   
                     ∀ 
                     
                       r 
                       ≥ 
                       1. 
                     
                   
                 
               
             
           
         
       
     
   
   To compute the number of retransmissions needed to reach an application PDU error rate target value, IP(E r ) is computed by induction until R=inf {r ε N:IP (E r )≦ε i } is reached, where inf{} is a lower bound of a set of numbers and N is the set of natural numbers. The number of retransmitted SF is given by R, whereas the total number of transmitted SF equals R+n. 
   An implementation of the admission control is disclosed in  FIG. 5 . The method enables a maximum throughput T i  to be reached together with a maximum transmission application PDU error rate ε i . 
   At step  300 , the number R of retransmissions needed is calculated as explained above as a function of ε i , BER, n and S. 
   In order to reach the required throughput T i , the bandwidth to reserve T′ i  is calculated in that case at step  302  as 
               T   i   ′     =       (     1   +     R   n       )     ×     (       T   i     +     κ   i       )         ,         
where κ i  is the traffic induced while crossing intermediate layers. In case application PDU are emitted according to a periodic profile (P i  seconds between two consecutive application PDUs), and H i  represent the size of intermediate layers headers in bits, this parameter can be computed as
 
   
     
       
         
           
             κ 
             i 
           
           = 
           
             
               
                 H 
                 i 
               
               
                 P 
                 i 
               
             
             . 
           
         
       
     
   
   A checking step  304  and a connexion step  306  or a connexion refusal step  308  corresponding to steps  104 ,  106  and  108  of  FIG. 2  are then implemented. 
   A rough upper bound of delay may be calculated as in the previous case described in  FIG. 3  where D′ i  is computed as D′ i =(1+R) RTT. 
     FIG. 6  shows an alternative algorithm of the method enabling an end-to-end transmission delay requirement D i  to be reached together with a maximum transmission application PDU error rate ε i . In that case, D′ i  is computed more accurately by using probability theory. 
   A stage  400 , the number R of needed retransmissions is calculated as a function of ε i , BER, n and S. 
   At stage  402 , D′ i  is calculated as a probability distribution function. 
   In this case, we have: 
                   IP   ⁡     (       D   i   ′     ≤   d     )       =       ⁢       ∑     i   =   0       inf   ⁡     (     n   ,   R     )         ⁢       ∑     k   =   i     R     ⁢       ∑         r   1     +   …   +     r   i       =   k       ⁢     1   ⁢       I     [       max   ⁢     {       r   1     ,   …   ⁢           ,     r   i       }     ×   RTT     ,     +     ∞   [             ⁡     (   d   )       ×                           ⁢       C   n   i     ⁢         LER   k     ⁡     (     1   -   LER     )       n                   
where 1I A (x) is a characteristic function of a set and 1I A (x)=1 if and only if x lies in the subset A.
 
   At step  404 , a maximum delay D δ  is calculated according to an allowed margin of error denoted δ. 
   D δ  is chosen such that
 
 IP ( D′   i   ≧D   δ )≦δ.
 
   At step  406 , a test is carried out so that the new connection is accepted at step  408  provided its required delay D i  is lower than or equal to D δ . Otherwise, the connection is refused at step  410 . 
   According to a particular embodiment, a computer program product is provided for the admission control unit, including a set of instructions which, when loaded into the admission control unit, causes the admission control unit to carry out the method as described above.