PATENT DOCUMENT

Abstract:
Disclosed is an Active Queue Management method and apparatus which uses traffic rate information for congestion control. Using a nonlinear fluid-flow model of Traffic Control Protocol, a proportional controller in a closed loop configuration with gain settings characterized for stable operation allows a matching of the aggregate rate of the active TCP connections to the available capacity. Further disclosed is a method for calculation of the regime of gains for which stable operation of a given network obtains. This approach allows for capacity matching while maintaining minimal queue size and high link utilization.

Full Description:
FIELD OF THE INVENTION 
   The present invention relates generally to network queue management, and more particularly to a technique for active queue management using proportional control and rate-based information. 
   BACKGROUND OF THE INVENTION 
   Congestion control in the Internet has primarily been the responsibility of the end-to-end congestion control mechanisms of TCP (Transmission Control Protocol). However, with the rapid growth of the Internet and the stringent requirements for quality of service (QoS) support, it has become clear that the Internet could not exclusively rely on the end hosts to perform the end-to-end congestion control. Mechanisms are needed in the intermediate network elements to complement the end hosts congestion control mechanisms. Recognizing this, the Internet Engineering Tasks Force (IETF) has advocated the deployment of active queue management (AQM) mechanisms at the intermediate network elements (routers, switches, etc.) as a means of congestion control. 
   To perform AQM, the network elements are equipped with the means to detect incipient congestion and to signal the traffic sources before congestion actually occurs. AQM mechanisms allow the network elements to send explicit/implicit feedback of congestion to the end hosts by marking/dropping packets. The end hosts in turn react to the packet marking/dropping by reducing their data transmission rates. The main goals of AQM are to reduce the average queue lengths in the network elements and thereby decrease the end-to-end delay experienced by end user traffic, and maximize the utilization of network resources by reducing the packet loss that occurs when queues overflow. 
   The traditional queue management mechanism is “drop tail” which is simple to implement and is widely deployed. With drop tail mechanism, packets are dropped only at buffer overflow at which point congestion signals are conveyed to the end hosts. This results in a significantly long time period between the instant when congestion occurs and the instant when the end hosts reduce their data transmission rates. During this time period, more packets may be sent by the end hosts which could be eventually dropped. Drop tail can lead to problematic global synchronization of the traffic sources (where the sources ramp their traffic rates and backoff at the same time) and periods of low link utilization. 
   A number of AQM schemes have been proposed which use either queue size information for congestion control (so-called queue-based schemes) or traffic rate information (so-called rate-based schemes). Queue-based AQM schemes adapt their marking/dropping probabilities in a manner that depends on the queue size at the link. With small buffers they tend to perform poorly. For example, studies have shown that a technique such as RED (Random Early Detection) described by S. Floyd and V. Jacobson in “Random Early Detection Gateway for Congestion Avoidance,”  IEEE/ACM Trans. Networking , Vol. 1, No. 4, August 1993, pp. 397-413 performs well only when the queuing capacity is greater than the bandwidth-delay product. Quite naturally the dependence of a queue-based scheme on queue size information for control will require that there be sufficient buffering for effective process tracking and control. 
   Very small buffers tend to complicate the control problem in this case. 
   A number of recent studies such as C. V. Hollot, V. Misra, D. Townsley, and W. B. Gong, “A Control Theoretic Analysis of RED,”  Proc. IEEE INFOCOM  2001, 2001, pp. 1510-1519, C. V. Hollot, V. Misra, D. Townsley, and W. B. Gong, “On Designing Improved Controllers for AQM Routers Supporting TCP Flows,”  Proc. IEEE INFOCOM  2001, 2001, pp. 1726-1734, Y. Chait, C. V. Hollot, and V. Misra, “Fixed and Adaptive Model-Based Controllers for Active Queue Management,”  Proc. American Control Conf ., Arlington, Va., June 25-27 2001, pp. 2981-2986, and V. Misra, W. B. Gong, and D. Townsley, “Fluid-based Analysis of a Network of AQM Routers Supporting TCP Flows with an Application to RED,”  Proc. ACM SIGCOMM  2000, 2000, pp. 151-160, have described queue-based AQM schemes which explicitly rely on dynamic modeling and feedback control principles. Central to these studies is the recognition that AQM schemes are essentially feedback control systems and that the principles of control theory can provide critical insight and guidance into the analysis and design of such schemes. The fluid flow analytical model of TCP described in “Fluid-based Analysis of a Network of AQM Routers Supporting TCP Flows with an Application to RED” by Misra et al. particularity expresses TCP dynamics in a form that allows control theoretic approaches to be applied for AQM design and analysis. 
   In view of the foregoing, it would be desirable to provide a technique for network queue management which overcomes the above-described inadequacies and shortcomings. 
   SUMMARY OF THE INVENTION 
   An object of the present invention is to provide an improved rate-based proportional control scheme for active queue management. 
   According to an aspect of the invention there is provided a method for controlling a data flow in a data network, starting with selecting a stable proportional controller gain k p . Next measuring a data arrival rate R(n) at time n. Next, calculating a normalized error signal e(n), according to the relation
 
 e ( n )=( T ( n )− R ( n ))/ x,  
 
where T(n) is an assigned capacity at time n, and x is a nominal packet size. Next, a mark/drop probability p(n) is computed according to the relation
 
 p ( n )=min { max [ k   p   ·e ( n ),0],  p   max }
 
where 0&lt;p max ≦1. Finally a packet mark/drop routine is executed based upon the calculated mark/drop probability p(n).
 
   Conveniently, the data arrival rate may be filtered by use of an exponentially weighted moving average scheme according to the relation
 
 R ′( n )=(1−β)· R ′( n− 1)+β· R ( n )
 
   where β is a filter gain parameter such that 0&lt;β&lt;1, 
   R′(n−1) is the filtered data arrival rate at time n−1, and 
   R′(n) is the desired filtered data arrival rate at time n. 
   According to another aspect of the invention, preceding the packet/mark drop routine may be a bypassing routine involving the steps of testing the data arrival rate R(n) against a rate threshold T L ; and if the data arrival rate R(n) is below or equal to the threshold T L  then bypassing the step of executing a packet mark/drop routine. 
   Conveniently, the packet mark/drop routine may be realized according to a random number generator mark/drop scheme. 
   Also conveniently, the stable proportional controller gain may be chosen from a pre-calculated regime of stable gains. A method for pre-calculating the regime may be as follows; starting with (1) obtaining for said network a value for said network a set of parameters k, d 0 , and τ, where k is a steady-state gain of said network, d 0  is a time delay of said network, and τ is a time constant of said network. Next step (2) determining the root z 1  in the interval 
                 (       π   2     ,   π     )     ⁢           ⁢   of   ⁢           ⁢     tan   ⁡     (     z   1     )         =       -     π     d   0         ⁢     z   1         ,         
and then computing the range of stable gains for k p  for this particular network as
 
   
     
       
         
           
             
               - 
               
                 τ 
                 
                   kd 
                   0 
                 
               
             
             ⁢ 
             
               
                 
                   z 
                   1 
                   2 
                 
                 + 
                 
                   
                     d 
                     0 
                     2 
                   
                   
                     τ 
                     2 
                   
                 
               
             
           
           &lt; 
           
             k 
             p 
           
           &lt; 
           
             
               1 
               k 
             
             . 
           
         
       
     
   
   In accordance with another other aspect of the present invention, there is provided an apparatus for controlling a data flow in a data network, the apparatus being configured according to the methods described above. 
   In accordance with another other aspect of the present invention, there is provided an article of manufacture carrying instructions for a method for controlling a data flow in a data network, and further there is provided a signal embodied in a carrier wave representing instructions for a method for controlling a data flow in a data network according to a proportional control scheme. 
   The present invention will now be described in more detail with reference to exemplary embodiments thereof as shown in the appended drawings. While the present invention is described below with reference to the preferred embodiments, it should be understood that the present invention is not limited thereto. Those of ordinary skill in the art having access to the teachings herein will recognize additional implementations, modifications, and embodiments, which are within the scope of the present invention as disclosed and claimed herein. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The invention will be further understood from the following detailed description of embodiments of the invention and accompanying drawings, in which: 
       FIG. 1  is a diagram of an Active Queue Management controller in an Intermediate Network Element according to an embodiment of the invention. 
       FIG. 2  is a diagram of a closed loop control system according to an embodiment of the invention. 
       FIG. 3  is a plot of a typical open loop response of the TCP/AQM plant according to an embodiment of the invention. 
       FIG. 4  is a plot of the two terms in Equation (29) for a general system. 
       FIG. 5  is a block diagram of a routine for determining the stable proportional gains for a closed-loop TCP/AQM system according to an embodiment of the invention. 
       FIG. 6  is a plot of the step response of an example closed-loop TCP/AQM system. 
       FIG. 7  is a block diagram of a mark/drop probability computation routine according to an embodiment of the invention. 
       FIG. 8  is a block diagram of a packet drop/mark routine according to an embodiment of the invention. 
       FIG. 9  is a block diagram of an overall control routine according to an embodiment of the invention. 
   

   DETAILED DESCRIPTION 
   A high level depiction of an implementation of the active queue management proportional-integral control scheme according to a possible embodiment is given in  FIG. 1 . 
   Users  100  communicate with End Network Elements  105  which pass packet data either directly or through Intermediate Network Elements  115 , to other End Network Elements  105 . End-to-end congestion control mechanisms under normal TCP (Transmission Control Protocol) rely upon Implicit/Explicit Feedback Signals  110 . Examples of Implicit/Explicit Feedback Signals  110  typically include duplicate TCP acknowledgement packets, timeouts, and marked packets. 
   In order to meet the stringent requirements for Quality of Service (QoS) of users, and the increases in data volume with the rapid growth of the Internet, it is advantageous to provide congestion control mechanisms at intermediate points to complement the end hosts congestion control mechanisms. According to one aspect of the invention, Intermediate Network Element  115  has been equipped with such a mechanism for congestion control. 
   Within Intermediate Network Element  115  are a Proportional Controller  120 , a queue means  130 , an arrival rate measurement means  122 , a target rate measurement means  126 , a packet mark/drop module  128 , and a mark/drop probability control means  124  by which the Proportional Controller  120  influences the packet mark/drop module  128  according to a scheme described hereafter. 
   A control system oriented depiction of the system of  FIG. 1  may be seen in  FIG. 2  where the closed-loop system is represented as having two main elements; TCP/AQM plant  210  and the control-function means  220 . The control system functions by comparing a desired Target-Rate “T”  226  with an Actual-Rate “R”  222  via a summer  240  which generates a control error “e”  250  by determining the difference between the two rates. This difference is used as an input to the control-function means  220  which generates a mark/drop probability threshold “p”  224 . Changes in the threshold for marking or dropping packets results in an eventual change in the Actual-Rate “R”  222  as the effects propagate through the system. As with all closed loop systems, the control-function means  220  must have a control function response chosen so as to render a stable closed-loop system response. If this condition is not met the resultant performance will be deleterious to the network operation, possibly to the point of causing performance degradation. 
   In order to be able to determine the stability requirements for the control-function means, the open loop transfer function for TCP/AQM plant  210  must be established. This may be done as follows. 
   A simplified rate-based fluid-flow model of a TCP source i assessing a single link is described by the following nonlinear differential equation: 
                       r   .     i     ⁡     (   t   )       =       1       d   i   2     ⁡     (   t   )         -     θ   ⁢           ⁢       r   i     ⁡     (   t   )       ⁢       r   i     ⁡     (     t   -       d   i     ⁡     (   t   )         )       ⁢     p   ⁡     (     t   -       d   i     ⁡     (   t   )         )                   (   1   )               
where {dot over (r)} denotes the time-derivative of r, r i  is rate of the TCP source (in packets per second), d i  is the round-trip time (RTT) of the TCP source (in seconds), p is the marking/dropping probability of a TCP packet at the link, and θ is a parameter characteristic of the type of TCP source. This model of TCP ignores the slow-start and the timeout behavior of TCP. Note that r i  and p are bounded, respectively, as follows; r i ε[0,C], pε[0,1], where C is the link capacity.
 
   Denoting p 0  as the steady-state (or operating point) of the marking/dropping probability of a TCP source and assuming a constant RTT d 0 , the steady-state throughput r 0  can be obtained as 
   
     
       
         
           0 
           = 
           
             
               
                 1 
                 
                   d 
                   0 
                   2 
                 
               
               - 
               
                 θ 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   r 
                   0 
                   2 
                 
                 ⁢ 
                 
                   p 
                   0 
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 or 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   r 
                   0 
                 
               
             
             = 
             
               
                 1 
                 
                   d 
                   0 
                 
               
               ⁢ 
               
                 
                   
                     1 
                     
                       θ 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         p 
                         0 
                       
                     
                   
                 
                 . 
               
             
           
         
       
     
   
   If the parameter θ takes on the value of ⅔, we get the steady-state throughput of TCP as 
   
     
       
         
           
             r 
             0 
           
           = 
           
             
               1 
               
                 d 
                 0 
               
             
             ⁢ 
             
               
                 
                   3 
                   
                     2 
                     ⁢ 
                     
                       p 
                       0 
                     
                   
                 
               
               . 
             
           
         
       
     
   
   Making the approximation relating data transmission rate and window size
 
 r   i ( t )≈ W   i ( t )/ d   i ( t )
 
and assuming d i (t)=d i =nt, we get
 
                   r   .     i     ⁡     (   t   )       ≈       ⅆ     ⅆ   t       ⁢     (         W   i     ⁡     (   t   )           d   i     ⁡     (   t   )         )         =           1     d   i       ⁢       ⅆ       W   i     ⁡     (   t   )           ⅆ   t         -           W   i     ⁡     (   t   )         d   i   2       ⁢       ⅆ     d   i         ⅆ   t           ≈       1     d   i       ⁢         ⅆ       W   i     ⁡     (   t   )           ⅆ   t       .               
With this, we see that making the approximation r i (t)≈W i (t)/d i (t) shows that the rate-based fluid-flow model of a TCP source is essentially equivalent to a window-based nonlinear fluid-flow TCP model.
 
   Assuming a constant RTT d 0 , we rewrite the initial equation as 
                   f   ⁡     (       r   i     ,       r     i   ,   d       ⁢   p       )       =           r   .     i     ⁡     (   t   )       =       1     d   0   2       -     θ   ⁢           ⁢       r   i     ⁡     (   t   )       ⁢       r     i   ,   d       ⁡     (   t   )       ⁢     p   ⁡     (     t   -     d   0       )                     (   2   )               
where
   r   i,d ( t )≐ r   i ( t−d   0 ) 
   Using Taylor series expansion, the small-signal linearization of
 
 f ( r   i   ,r   i,d   ,p )= {dot over (r)}   i ( t )
 
about an operating point (r 0 ,p 0 ) is given as
 
                     δ   ⁢           ⁢         r   .     i     ⁡     (   t   )         +       ∂   f       ∂     r   i           ⁢     ❘       r   0     ,     p   0         ⁢         δ   ⁢           ⁢       r   i     ⁡     (   t   )         +       ∂   f       ∂     r     i   ,   d             ⁢     ❘       r   0     ,     p   0         ⁢           δr     i   ,   d       ⁡     (   t   )       +       ∂   f       ∂   p         ⁢     ❘       r     0   ,       ⁢     p   0         ⁢     δ   ⁢           ⁢   p   ⁢           ⁢     (     t   -     d   0       )                   (   3   )               
where
 δ r   i ( t )= r   i ( t )− r   0    δ r   i,d ( t )= r   i,d ( t )− r   0    δ p ( t−d   0 )= p ( t−d   0 )− p   0    
and
 
   
     
       
         
           
             
               
                 
                   
                     
                       ∂ 
                       f 
                     
                     
                       ∂ 
                       
                         r 
                         i 
                       
                     
                   
                   ⁢ 
                   
                     ❘ 
                     
                       
                         r 
                         0 
                       
                       , 
                       
                         p 
                         0 
                       
                     
                   
                 
                 = 
                 
                   
                     
                       
                         ∂ 
                         f 
                       
                       
                         ∂ 
                         
                           r 
                           
                             i 
                             , 
                             d 
                           
                         
                       
                     
                     ⁢ 
                     
                       ❘ 
                       
                         
                           r 
                           0 
                         
                         , 
                         
                           p 
                           0 
                         
                       
                     
                   
                   = 
                   
                     - 
                     
                       θ 
                       
                         
                           r 
                           0 
                         
                         ⁢ 
                         
                           p 
                           0 
                         
                       
                     
                   
                 
               
             
           
           
             
               
                 
                   
                     
                       ∂ 
                       f 
                     
                     
                       ∂ 
                       p 
                     
                   
                   ⁢ 
                   
                     ❘ 
                     
                       
                         r 
                         0 
                       
                       , 
                       
                         p 
                         0 
                       
                     
                   
                 
                 = 
                 
                   
                     - 
                     θ 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     r 
                     0 
                     2 
                   
                 
               
             
           
         
       
     
   
   The linearized equation (3) then becomes
 
δ {dot over (r)}   i ( t )=−θ r   0   p   0 (δ r   i ( t )+δ r   i,d ( t ))−θ r   0   2   δp ( t−d   0 ).  (4)
 
   Making the approximation r i (t)≈r i,d (t) in (4), we get
 
δ {dot over (r)}   i ( t )=−2θ r   0   p   0   δr   i ( t )−θ r   0   2   δp ( t−d   0 )  (5)
 
   Let us assume that the link of capacity C is shared by a constant number N of TCP sources. The aggregate rate on the link R(t) is given by 
   
     
       
         
           
             
               
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       1 
                     
                     N 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       r 
                       i 
                     
                     ⁡ 
                     
                       ( 
                       t 
                       ) 
                     
                   
                 
                 = 
                 
                   
                     R 
                     ⁡ 
                     
                       ( 
                       t 
                       ) 
                     
                   
                   . 
                 
               
             
             
               
                 ( 
                 6 
                 ) 
               
             
           
         
       
     
   
   From (6), the equilibrium point of the system can be expressed as 
                       ∑     i   =   1     N     ⁢           ⁢     r   0       =       R   0     =     ρ   ⁢           ⁢   C         ,           (   7   )                   r   0     =       ρ   ⁢           ⁢   C     N       ,           (   8   )               
where ρε(0,1] is a target utilization factor. From (1) and (8), the equilibrium point of the marking/dropping probability can be expressed as
 
   
     
       
         
           
             
               
                 
                   p 
                   0 
                 
                 = 
                 
                   
                     1 
                     
                       
                         d 
                         0 
                         2 
                       
                       ⁢ 
                       θ 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         r 
                         0 
                         2 
                       
                     
                   
                   = 
                   
                     
                       
                         N 
                         2 
                       
                       
                         
                           θ 
                           ⁡ 
                           
                             ( 
                             
                               
                                 d 
                                 0 
                               
                               ⁢ 
                               ρ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               C 
                             
                             ) 
                           
                         
                         2 
                       
                     
                     . 
                   
                 
               
             
             
               
                 ( 
                 9 
                 ) 
               
             
           
         
       
     
   
   Defining δR(t)=R(t)−R 0  we know from (6) that 
   
     
       
         
           
             
               
                 
                   
                     
                       
                         δ 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           R 
                           ⁡ 
                           
                             ( 
                             t 
                             ) 
                           
                         
                       
                       = 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           N 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           δ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               r 
                               i 
                             
                             ⁡ 
                             
                               ( 
                               t 
                               ) 
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           and 
                         
                       
                     
                   
                   
                     
                       ( 
                       10 
                       ) 
                     
                   
                 
                 
                   
                     
                       
                         
                           
                             
                               δ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   R 
                                   . 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   t 
                                   ) 
                                 
                               
                             
                             = 
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 N 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 δ 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   
                                     
                                       r 
                                       . 
                                     
                                     i 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     t 
                                     ) 
                                   
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             = 
                             
                               
                                 
                                   - 
                                   2 
                                 
                                 ⁢ 
                                 θ 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   r 
                                   0 
                                 
                                 ⁢ 
                                 
                                   p 
                                   0 
                                 
                                 ⁢ 
                                 
                                   
                                     ∑ 
                                     
                                       i 
                                       = 
                                       1 
                                     
                                     N 
                                   
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     δ 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       
                                         r 
                                         i 
                                       
                                       ⁡ 
                                       
                                         ( 
                                         t 
                                         ) 
                                       
                                     
                                   
                                 
                               
                               - 
                               
                                 
                                   ∑ 
                                   
                                     i 
                                     = 
                                     1 
                                   
                                   N 
                                 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   θ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     r 
                                     0 
                                     2 
                                   
                                   ⁢ 
                                   δ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     p 
                                     ⁡ 
                                     
                                       ( 
                                       
                                         t 
                                         - 
                                         
                                           d 
                                           0 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             = 
                             
                               
                                 
                                   - 
                                   2 
                                 
                                 ⁢ 
                                 θ 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   r 
                                   0 
                                 
                                 ⁢ 
                                 
                                   p 
                                   0 
                                 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 δ 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   R 
                                   ⁡ 
                                   
                                     ( 
                                     t 
                                     ) 
                                   
                                 
                               
                               - 
                               
                                 N 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 θ 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   r 
                                   0 
                                   2 
                                 
                                 ⁢ 
                                 δ 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   p 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       t 
                                       - 
                                       
                                         d 
                                         0 
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       ( 
                       11 
                       ) 
                     
                   
                 
               
             
             
               
                   
               
             
           
         
       
     
   
   Substituting the equilibrium points (r 0 ,p 0 ) in (11), we get 
   
     
       
         
           
             
               
                 
                   δ 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       R 
                       . 
                     
                     ⁡ 
                     
                       ( 
                       t 
                       ) 
                     
                   
                 
                 = 
                 
                   
                     
                       - 
                       
                         
                           2 
                           ⁢ 
                           N 
                         
                         
                           
                             d 
                             0 
                             2 
                           
                           ⁢ 
                           ρ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           C 
                         
                       
                     
                     ⁢ 
                     δ 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       R 
                       ⁡ 
                       
                         ( 
                         t 
                         ) 
                       
                     
                   
                   - 
                   
                     
                       
                         
                           θρ 
                           2 
                         
                         ⁢ 
                         
                           C 
                           2 
                         
                       
                       N 
                     
                     ⁢ 
                     δ 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       p 
                       ⁡ 
                       
                         ( 
                         
                           t 
                           - 
                           
                             d 
                             0 
                           
                         
                         ) 
                       
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     or 
                   
                 
               
             
             
               
                 ( 
                 12 
                 ) 
               
             
           
           
             
               
                 
                   
                     
                       
                         
                           d 
                           0 
                           2 
                         
                         ⁢ 
                         ρ 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         C 
                       
                       
                         2 
                         ⁢ 
                         N 
                       
                     
                     ⁢ 
                     δ 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         R 
                         . 
                       
                       ⁡ 
                       
                         ( 
                         t 
                         ) 
                       
                     
                   
                   = 
                   
                     
                       
                         - 
                         δ 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         R 
                         ⁡ 
                         
                           ( 
                           t 
                           ) 
                         
                       
                     
                     - 
                     
                       
                         
                           θ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             d 
                             0 
                             2 
                           
                           ⁢ 
                           
                             ρ 
                             3 
                           
                           ⁢ 
                           
                             C 
                             3 
                           
                         
                         
                           2 
                           ⁢ 
                           
                             N 
                             2 
                           
                         
                       
                       ⁢ 
                       δ 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         p 
                         ⁡ 
                         
                           ( 
                           
                             t 
                             - 
                             
                               d 
                               0 
                             
                           
                           ) 
                         
                       
                     
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     
                       τδ 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         R 
                         ⁡ 
                         
                           ( 
                           t 
                           ) 
                         
                       
                     
                     + 
                     
                       δ 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         R 
                         ⁡ 
                         
                           ( 
                           t 
                           ) 
                         
                       
                     
                   
                   = 
                   
                     - 
                     
                       kδp 
                       ⁡ 
                       
                         ( 
                         
                           t 
                           - 
                           
                             d 
                             0 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 ( 
                 13 
                 ) 
               
             
           
           
             
               where 
             
             
               
                   
               
             
           
           
             
               
                 τ 
                 = 
                 
                   
                     
                       
                         
                           d 
                           0 
                           2 
                         
                         ⁢ 
                         ρ 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         C 
                       
                       
                         2 
                         ⁢ 
                         N 
                       
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     and 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     k 
                   
                   = 
                   
                     
                       
                         
                           θd 
                           0 
                           2 
                         
                         ⁢ 
                         
                           ρ 
                           3 
                         
                         ⁢ 
                         
                           C 
                           3 
                         
                       
                       
                         2 
                         ⁢ 
                         
                           N 
                           3 
                         
                       
                     
                     . 
                   
                 
               
             
             
               
                   
               
             
           
         
       
     
   
   Taking the Laplace transform of (13) we get
 
τ sR ( s )+ R ( s )=− ke   −d     0     s   P ( s ),  (14)
 
where R(s) is the Laplace transform of δR(t) and e −sd     0   P(s) is the Laplace transform of δp(t−d 0 ).
 
   We obtain the open-loop transfer function of the TCP/AQM plant from (14) as 
   
     
       
         
           
             
               
                 
                   G 
                   ⁡ 
                   
                     ( 
                     s 
                     ) 
                   
                 
                 = 
                 
                   
                     
                       ( 
                       s 
                       ) 
                     
                     
                       P 
                       ⁡ 
                       
                         ( 
                         s 
                         ) 
                       
                     
                   
                   = 
                   
                     
                       
                         kⅇ 
                         
                           - 
                           
                             
                               ⅆ 
                               0 
                             
                             ⁢ 
                             s 
                           
                         
                       
                       
                         
                           τ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           s 
                         
                         + 
                         1 
                       
                     
                     . 
                   
                 
               
             
             
               
                 ( 
                 15 
                 ) 
               
             
           
         
       
     
   
   In (15), −k represents the steady-state (or static) gain of the TCP/AQM plant, d 0  represents the time delay (or dead time), and τ represents the time constant of the plant. 
   The step response of the model (15) is
 
 R ( t )=− k (1− e   −(t−d     0     )/τ ).  (16)
 
   From (16), it follows that the average residence time is 
   
     
       
         
           
             
               
                 
                   T 
                   av 
                 
                 = 
                 
                   
                     
                       
                         ∫ 
                         0 
                         ∞ 
                       
                       ⁢ 
                       
                         
                           ( 
                           
                             
                               R 
                               ⁡ 
                               
                                 ( 
                                 ∞ 
                                 ) 
                               
                             
                             - 
                             
                               R 
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                           
                           ) 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           ⅆ 
                           t 
                         
                       
                     
                     
                       - 
                       k 
                     
                   
                   = 
                   
                     
                       τⅇ 
                       
                         
                           ⅆ 
                           0 
                         
                         ⁢ 
                         
                           / 
                           τ 
                         
                       
                     
                     ≈ 
                     
                       
                         d 
                         0 
                       
                       + 
                       τ 
                     
                   
                 
               
             
             
               
                 ( 
                 17 
                 ) 
               
             
           
         
       
     
   
   The ratio 
                 η   =         ⅆ   0         ⅆ   0     ⁢     +   τ         =       d   0       T   av                 (   18   )               
is called the normalized dead time and has the property 0≦η≦1. This quantity can be used to characterize the difficulty of controlling a process. It is sometimes called the controllability ratio. It has been observed that processes with small η are easy to control and that the difficulty in controlling the system increases as η increases. The parameters in the model (15) are represented graphically in  FIG. 3 . The parameter −k′ is simply the gain corresponding to the time distance d 0 +τ.
 
   The goal of the control system is to mark/drop packets such that the aggregate rate of the active TCP connections will match the available capacity while at the same time maintain minimal queue size and high link utilization. Having established an expression for the open loop transfer function for TCP/AQM plant  210 , it is now possible to consider an expression for the system as a whole. 
   Returning to  FIG. 2  and noting again that Target-Rate “T”  226  is the control target, Actual-Rate “R”  222  is the output of the plant (actual traffic arrival rate), mark/drop probability threshold “p”  224  is the control input, TCP/AQM plant  210  given by (15) as the plant to be controlled, and C(s), the control-function means  220  is to be a proportional controller. 
   The Laplace expression for the case of a proportional controller may be written as,
 
 C ( s )= k   p ,  (19)
 
where k p  is proportional gain of the controller.
 
   The closed-loop transfer function of the TCP/AQM plant is then given as 
   
     
       
         
           
             
               
                 
                   
                     G 
                     AQM 
                   
                   ⁡ 
                   
                     ( 
                     s 
                     ) 
                   
                 
                 = 
                 
                   
                     
                       
                         C 
                         ⁡ 
                         
                           ( 
                           s 
                           ) 
                         
                       
                       ⁢ 
                       
                         G 
                         ⁡ 
                         
                           ( 
                           s 
                           ) 
                         
                       
                     
                     
                       1 
                       + 
                       
                         
                           C 
                           ⁡ 
                           
                             ( 
                             s 
                             ) 
                           
                         
                         ⁢ 
                         
                           G 
                           ⁡ 
                           
                             ( 
                             s 
                             ) 
                           
                         
                       
                     
                   
                   = 
                   
                     
                       
                         
                           - 
                           
                             kk 
                             p 
                           
                         
                         ⁢ 
                         
                           ⅇ 
                           
                             - 
                             
                               
                                 ⅆ 
                                 0 
                               
                               ⁢ 
                               s 
                             
                           
                         
                       
                       
                         
                           τ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           s 
                         
                         + 
                         1 
                         - 
                         
                           
                             kk 
                             p 
                           
                           ⁢ 
                           
                             ⅇ 
                             
                               - 
                               
                                 
                                   ⅆ 
                                   0 
                                 
                                 ⁢ 
                                 s 
                               
                             
                           
                         
                       
                     
                     . 
                   
                 
               
             
             
               
                 ( 
                 20 
                 ) 
               
             
           
         
       
     
   
   The objective now is to determine the values of the parameter k p  for which the closed-loop system is stable. 
   Using an extension of the Hermite-Biehler Theorem applicable to quasipolynomials a detailed analytical characterization of the stabilizing feedback gains of the closed-loop TCP/AQM system may be performed as follows. 
   The characteristic equation of a control system with time delay can be expressed in the general form as
 
 F ( s )= d ( s )+ e   −sT     1     n   1 ( s )+ e   −sT     2     n   2 ( s )+ . . . + e   −sT     m     n   m ( s ),  (21)
 
where d(s), n i (s) for i=1, 2, . . . , m, are polynomials with real coefficients.
 
   Characteristic equations of the form (21) are also referred to as quasipolynomials. It can be shown that the so-called Hermite-Biehler Theorem for Hurwitz polynomials does not carry over to arbitrary functions f(s) of the complex variable s. However, a suitable extension of the Hermite-Biehler Theorem can be developed to study the stability of certain classes of quasipolynomials characterized as follows. 
   If the following assumptions are made in (21) 
   A1: deg[d(s)]=n and deg[n i (s)]≦n for i=1, 2, . . . , m; 
   A2: 0&lt;T 1 &lt;T 2 &lt; . . . &lt;T m , 
   then instead of (21), we can consider the quasipolynomial
 
 F *( s )= e   sT     m     F ( s )= e   sT     m     d ( s )+ e   s(T     m     −T     1   ) n   1 ( s )+ e   s(T     m     −T     2   ) n   2 ( s )+ . . . + n   m ( s ).  (22)
 
   Since e sT     m    does not have any finite roots, the roots of F(s) are identical to those of F*(s). The quasipolynomial F*(s), however, has a principal term, i.e., the coefficient of the term containing the highest powers of s and e s  is nonzero. It then follows that this quasipolynomial is either of the delay (i.e., retarded) or of the neutral type. From this, we can say that the stability of the system with characteristic equation (21) is equivalent to the condition that all the roots of F*(s) be in the open left-half plane. Equivalently, we will say that F*(s) is Hurwitz or stable. The theorem below gives necessary and sufficient conditions for the stability of F*(s):
         Theorem 1: Let F*(s) be given by (22), and write
 
 F *( j ω)= F   r (ω)+ jF   i (ω)
   where F r (ω) and F i (ω) represent the real and imaginary parts of F*(s), respectively. Under assumptions A1 and A2, F*(s) is stable if and only if   1) F r (ω) and F i (ω) have only simple real roots and these interlace   2) {dot over (F)} i (ω 0 )F r (ω 0 )−F i (ω 0 ){dot over (F)} r (ω 0 )&gt;0, for some ω 0  in (−∞,∞)   where {dot over (F)} r (ω) and {dot over (F)} i (ω) denote the first derivative with respect to ω of F r (ω) and F i (ω), respectively.       

   Using this theorem the set of all proportional gains that stabilize the first-order TCP/AQM plant with time delay described by (15) may be characterized. A key step in applying Theorem 1 to check stability is to ensure that F r (ω) and F i (ω) have only real roots. Such a property can be ensured by using the following result:
         Theorem 2: Let M and L denote the highest powers of s and e s , respectively, in F*(s). Let η be an appropriate constant such that the coefficients of the terms of highest degree in  r (ω) and F i (ω) do not vanish at ω=η. Then for the equations F r (ω)=0 or F i (ω)=0 to have only real roots, it is necessary and sufficient that in the intervals
 
−2 lπ+η≦ω≦ 2 lπ+η,l= 1,2,3, . . .
       

   F r (ω) or F i (ω) have exactly 4lL+M real roots starting with a sufficiently large l. 
   It is now possible to determine analytically the region in the k p  parameter space for which the closed-loop TCP/AQM plant is stable. 
   We first analyze the system given by (20) without time delay, i.e., d 0 =0. In this case, the closed-loop characteristic equation of the system is given by
 
 F ( s )=τ s+ 1− kk   p .  (23)
 
   We see that this first-order polynomial has a single root at 
   
     
       
         
           s 
           = 
           
             
               
                 
                   kk 
                   p 
                 
                 - 
                 1 
               
               τ 
             
             . 
           
         
       
     
   
   Given that τ&gt;0 and k&gt;0 are always true for the TCP/AQM plant, the closed-loop delay-free system is stable for the following condition 
   
     
       
         
           
             
               
                 
                   k 
                   p 
                 
                 &lt; 
                 
                   
                     1 
                     k 
                   
                   . 
                 
               
             
             
               
                 ( 
                 24 
                 ) 
               
             
           
         
       
     
   
   Next, let us consider the case where the time delay of the plant model is greater than zero, i.e., d 0 &gt;0. The closed-loop characteristic equation of the system is then
 
 F ( s )=− kk   p   e   −d     0     s +1+τ s.   (25)
 
   Theorem 1 can be invoked to determine the set of all stabilizing gains k p . Let us consider first the quasipolynomial F*(s) defined by
 
 F *( s )= e   d     0     s   F ( s )=− kk   p +(1+τ s ) e   d     0     s .  (26)
 
   Substituting s=jω, and using the relationship  e   d     0     jω =cos(d 0 ω)+j sin(d 0 ω), we have the following expression
 
 F *( j ω)= F   r (ω)+ jF   i (ω)
 
where
 
 F   r (ω)=− kk   p +cos( d   0 ω)−τω sin( d   0 ω)
 
 F   i (ω)=sin( d   0 ω)+τω cos( d   0 ω)
 
   For convenience of analysis, let us make the following change of variables, z=d 0 ω. Thus, we can rewrite the real and imaginary parts of F*(jω) as 
   
     
       
         
           
             
               
                 
                   
                     F 
                     r 
                   
                   ⁡ 
                   
                     ( 
                     z 
                     ) 
                   
                 
                 = 
                 
                   
                     - 
                     
                       kk 
                       p 
                     
                   
                   + 
                   
                     cos 
                     ⁡ 
                     
                       ( 
                       z 
                       ) 
                     
                   
                   - 
                   
                     
                       τ 
                       
                         d 
                         0 
                       
                     
                     ⁢ 
                     z 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       sin 
                       ⁡ 
                       
                         ( 
                         z 
                         ) 
                       
                     
                   
                 
               
             
             
               
                 ( 
                 27 
                 ) 
               
             
           
           
             
               
                 
                   
                     F 
                     i 
                   
                   ⁡ 
                   
                     ( 
                     z 
                     ) 
                   
                 
                 = 
                 
                   
                     sin 
                     ⁡ 
                     
                       ( 
                       z 
                       ) 
                     
                   
                   + 
                   
                     
                       τ 
                       
                         d 
                         0 
                       
                     
                     ⁢ 
                     z 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         cos 
                         ⁡ 
                         
                           ( 
                           z 
                           ) 
                         
                       
                       . 
                     
                   
                 
               
             
             
               
                 ( 
                 28 
                 ) 
               
             
           
         
       
     
   
   Theorem 1 requires us to check two conditions to ensure the stability of the quasipolynomial F*(s). 
   Check of Condition 2 of Theorem 1: We first check if
 
 E (ω 0 )= {dot over (F)}   i (ω 0 ) F   r (ω 0 )− F   i (ω 0 ) {dot over (F)}   r (ω 0 )&gt;0
 
for some ω 0  in (−∞,∞). Taking ω 0 =z 0 =0, for instance, gives F r (z 0 )=1−kk p  and F i (z 0 )=0. We also obtain
 
 {dot over (F)}   r ( z   0 )=0
 
and
 
   
     
       
         
           
             
               
                 
                   F 
                   . 
                 
                 i 
               
               ⁡ 
               
                 ( 
                 z 
                 ) 
               
             
             = 
             
               
                 
                   ( 
                   
                     1 
                     + 
                     
                       τ 
                       
                         d 
                         0 
                       
                     
                   
                   ) 
                 
                 ⁢ 
                 
                   cos 
                   ⁡ 
                   
                     ( 
                     z 
                     ) 
                   
                 
               
               - 
               
                 
                   τ 
                   
                     d 
                     0 
                   
                 
                 ⁢ 
                 z 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   sin 
                   ⁡ 
                   
                     ( 
                     z 
                     ) 
                   
                 
               
             
           
           , 
           
             
 
           
           ⁢ 
           
             
               ⇒ 
               
                 
                   
                     F 
                     . 
                   
                   i 
                 
                 ⁡ 
                 
                   ( 
                   
                     z 
                     0 
                   
                   ) 
                 
               
             
             = 
             
               1 
               + 
               
                 τ 
                 
                   d 
                   0 
                 
               
             
           
         
       
     
   
   From these we get 
   
     
       
         
           
             E 
             ⁡ 
             
               ( 
               
                 z 
                 0 
               
               ) 
             
           
           = 
           
             
               ( 
               
                 1 
                 + 
                 
                   τ 
                   
                     d 
                     0 
                   
                 
               
               ) 
             
             ⁢ 
             
               
                 ( 
                 
                   1 
                   - 
                   
                     kk 
                     p 
                   
                 
                 ) 
               
               . 
             
           
         
       
     
   
   Given that for the TCP/AQM plant the conditions τ&gt;0 and k&gt;0 hold true, we will require F r (z 0 )=1−kk p &gt;0 
           (       i   .   e   .     ,           ⁢       k   p     &lt;     1   k         )         
for E(z 0 )&gt;0. This result is consistent with that given in (24).
 
   Check of Condition 1 of Theorem 1: We now check the interlacing of the roots of F r (z) and F i (z). The roots of the imaginary part, i.e., F i (z)=0 can be determined from (28). This gives us 
   
     
       
         
           
             
               
                 
                   
                     
                       sin 
                       ⁡ 
                       
                         ( 
                         z 
                         ) 
                       
                     
                     + 
                     
                       
                         τ 
                         
                           d 
                           0 
                         
                       
                       ⁢ 
                       z 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         cos 
                         ⁡ 
                         
                           ( 
                           z 
                           ) 
                         
                       
                     
                   
                   = 
                   0. 
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 or 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     tan 
                     ⁡ 
                     
                       ( 
                       z 
                       ) 
                     
                   
                   = 
                   
                     
                       - 
                       
                         τ 
                         
                           d 
                           0 
                         
                       
                     
                     ⁢ 
                     z 
                   
                 
               
             
             
               
                 ( 
                 29 
                 ) 
               
             
           
         
       
     
   
   The roots of the imaginary part F i (z) are difficult to find and require an analytical solution of (29). However, a plot of the two terms in (29), (i.e., tan(z) and 
             -     τ     d   0         ⁢   z         
can be used to understand the nature of the real solution. In  FIG. 4  may be seen a plot of these two terms for arbitrarily selected values of k, τ and d 0 . The general nature of the plots, however, do not change with the use of other values. Arranged in increasing order of magnitude, we denote the positive real roots of (29) by z j , j=1, 2, 3, . . . In  FIG. 4 , we clearly see that the non-negative real roots of the imaginary part F i (z) satisfy
 
   
     
       
         
           
             
               
                 
                   
                     z 
                     0 
                   
                   = 
                   0 
                 
                 , 
                 
                   
                     z 
                     1 
                   
                   ∈ 
                   
                     ( 
                     
                       
                         π 
                         2 
                       
                       , 
                       π 
                     
                     ) 
                   
                 
                 , 
                 
                   
                     z 
                     2 
                   
                   ∈ 
                   
                     ( 
                     
                       
                         
                           3 
                           ⁢ 
                           π 
                         
                         2 
                       
                       , 
                       
                         2 
                         ⁢ 
                         π 
                       
                     
                     ) 
                   
                 
                 , 
                 
                   
                     z 
                     3 
                   
                   ∈ 
                   
                     ( 
                     
                       
                         
                           5 
                           ⁢ 
                           π 
                         
                         2 
                       
                       , 
                       
                         3 
                         ⁢ 
                         π 
                       
                     
                     ) 
                   
                 
                 , 
                 
                   
                     z 
                     4 
                   
                   ∈ 
                   
                     ( 
                     
                       
                         
                           7 
                           ⁢ 
                           π 
                         
                         2 
                       
                       , 
                       
                         4 
                         ⁢ 
                         π 
                       
                     
                     ) 
                   
                 
                 , 
                 … 
               
             
             
               
                 ( 
                 30 
                 ) 
               
             
           
         
       
     
   
   We now use Theorem 2 to check if F i (z) has only real roots. Let us substitute s 1 =d 0 s in the expression for F*(s) (in (26)). We see that the new quasipolynomial in s 1  gives us M=1 and L=1. We choose 
           η   =     π   4           
to satisfy the requirement that F i (z) does not vanish at ω=η, i.e., cos(η)≠0. From  FIG. 4 , we see that in the interval
 
               [     0   ,       2   ⁢   π     -     π   4         ]     =     [     0   ,       7   ⁢   π     4       ]       ,         
F i (z)=0 has 3 real roots including a root at the origin z 0 =0. It is seen that F i (z) is an odd function. It therefore follows that in the interval
 
             [       -       7   ⁢   π     4       ,       7   ⁢   π     4       ]     ,         
F i (z) will have 5 real roots. We also observe that F i (z) has two real root in
 
             (         7   ⁢   π     4     ,       15   ⁢   π     4       ]     .         
Thus, F i (z) has 4L+M=5 real roots in the interval
 
             [           -   2     ⁢   π     +     π   4       ,       2   ⁢   π     -     π   4         ]     .         
Furthermore, F i (z) has 2 real roots in each of the intervals
 
             [         2   ⁢   l   ⁢           ⁢   π     -     π   4       ,       2   ⁢     (     l   +   1     )     ⁢   π     -     π   4         ]     ⁢           ⁢     and   ⁢           [           -   2     ⁢     (     l   +   1     )     ⁢   π     +     π   4       ,         -   2     ⁢   l   ⁢           ⁢   π     +     π   4         ]           
for l=1, 2, 3, . . . . Hence it follows that F i (z) has exactly 4lL+M real roots in the interval
 
           [           -   2     ⁢   l   ⁢           ⁢   π     +     π   4       ,       2   ⁢   l   ⁢           ⁢   π     -     π   4         ]         
for l=1, 2, 3, . . . , which by Theorem 2 implies that F i (z) has only real roots.
 
   F r (z) can now be evaluated at the roots of the imaginary part F i (z). For z 0 =0, we obtained above F r (z 0 )=1−kk p . Now using (27), we obtain for z j , j=1, 2, 3, . . . , the following 
   
     
       
         
           
             
               F 
               r 
             
             ⁡ 
             
               ( 
               
                 z 
                 j 
               
               ) 
             
           
           = 
           
             
               - 
               
                 kk 
                 p 
               
             
             + 
             
               cos 
               ⁡ 
               
                 ( 
                 
                   z 
                   j 
                 
                 ) 
               
             
             - 
             
               
                 τ 
                 
                   d 
                   0 
                 
               
               ⁢ 
               
                 z 
                 j 
               
               ⁢ 
               
                 
                   sin 
                   ⁡ 
                   
                     ( 
                     
                       z 
                       j 
                     
                     ) 
                   
                 
                 . 
               
             
           
         
       
     
   
   Using (29) in the above equation, we get 
   
     
       
         
           
             
               
                 
                   
                     F 
                     r 
                   
                   ⁡ 
                   
                     ( 
                     
                       z 
                       j 
                     
                     ) 
                   
                 
                 = 
                 
                   
                     
                       
                         - 
                         
                           kk 
                           p 
                         
                       
                       + 
                       
                         cos 
                         ⁡ 
                         
                           ( 
                           
                             z 
                             j 
                           
                           ) 
                         
                       
                       + 
                       
                         
                           tan 
                           ⁡ 
                           
                             ( 
                             
                               z 
                               j 
                             
                             ) 
                           
                         
                         ⁢ 
                         
                           sin 
                           ⁡ 
                           
                             ( 
                             
                               z 
                               j 
                             
                             ) 
                           
                         
                       
                     
                     ⇒ 
                     
                       
                         F 
                         r 
                       
                       ⁡ 
                       
                         ( 
                         
                           z 
                           j 
                         
                         ) 
                       
                     
                   
                   = 
                   
                     
                       - 
                       
                         kk 
                         p 
                       
                     
                     + 
                     
                       1 
                       
                         cos 
                         ⁡ 
                         
                           ( 
                           
                             z 
                             j 
                           
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 ( 
                 31 
                 ) 
               
             
           
         
       
     
   
   Thus, we obtain
 
 F   r ( z   j )=− k[k   p   −a ( z   j )],  (32)
 
where
 
   
     
       
         
           
             
               
                 
                   a 
                   ⁡ 
                   
                     ( 
                     
                       z 
                       j 
                     
                     ) 
                   
                 
                 = 
                 
                   
                     1 
                     
                       k 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         cos 
                         ⁡ 
                         
                           ( 
                           
                             z 
                             j 
                           
                           ) 
                         
                       
                     
                   
                   . 
                 
               
             
             
               
                 ( 
                 33 
                 ) 
               
             
           
         
       
     
   
   From our previous results, we have F r (z 0 )=1−kk p &gt;0 (i.e., 
             (       i   .   e   .     ,           ⁢       k   p     &lt;     1   k         )     .         
Then interlacing of the roots of F r (z) and F i (z) is equivalent to F r (z 1 )&lt;0, F r (z 2 )&gt;0, F r (z 3 )&lt;0, and so on. Using this fact, our result F r (z 0 )=1−kk p &gt;0 and Equation (32), we get
 
   
     
       
         
           
             
               
                 
                   
                     
                       
                         F 
                         r 
                       
                       ⁡ 
                       
                         ( 
                         
                           z 
                           0 
                         
                         ) 
                       
                     
                     &gt; 
                     0 
                   
                   ⇒ 
                   
                     
                       k 
                       p 
                     
                     &lt; 
                     
                       1 
                       k 
                     
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     
                       
                         
                           F 
                           r 
                         
                         ⁡ 
                         
                           ( 
                           
                             z 
                             1 
                           
                           ) 
                         
                       
                       &lt; 
                       0 
                     
                     ⇒ 
                     
                       
                         k 
                         p 
                       
                       &gt; 
                       
                         a 
                         ⁡ 
                         
                           ( 
                           
                             z 
                             1 
                           
                           ) 
                         
                       
                     
                   
                   = 
                   
                     a 
                     1 
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     
                       
                         
                           F 
                           r 
                         
                         ⁡ 
                         
                           ( 
                           
                             z 
                             2 
                           
                           ) 
                         
                       
                       &gt; 
                       0 
                     
                     ⇒ 
                     
                       
                         k 
                         p 
                       
                       &lt; 
                       
                         a 
                         ⁡ 
                         
                           ( 
                           
                             z 
                             2 
                           
                           ) 
                         
                       
                     
                   
                   = 
                   
                     a 
                     2 
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     
                       
                         
                           F 
                           r 
                         
                         ⁡ 
                         
                           ( 
                           
                             z 
                             3 
                           
                           ) 
                         
                       
                       &lt; 
                       0 
                     
                     ⇒ 
                     
                       
                         k 
                         p 
                       
                       &gt; 
                       
                         a 
                         ⁡ 
                         
                           ( 
                           
                             z 
                             3 
                           
                           ) 
                         
                       
                     
                   
                   = 
                   
                     a 
                     3 
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 ⋮ 
               
             
             
               
                 ( 
                 34 
                 ) 
               
             
           
         
       
     
   
   The following observations can now be made (noting that for the TCP/AQM plant the τ&gt;0, d 0 ≧0 and k&gt;0 hold true):
         Observation 1: From (30), it is seen that z j  for odd values of j (1, 3, 5, . . . ), are in the second quadrant. Thus, for odd values of j, cos(z j )&lt;0 and from (33), we conclude that a(z j )&lt;0 for odd values of the parameters j.   Observation 2: Similarly, it is seen from (30) that z j  for even values of j, (2, 4, 6, . . . ) are in the fourth quadrant. Thus, for even values of j, cos(z j )&gt;0 and from (14), we conclude that a(z j )&gt;0 for even values of the parameters j.       

   All the set of inequalities obtained above can now be rewritten as 
   
     
       
         
           
             
               
                 
                   
                     max 
                     
                       
                         j 
                         = 
                         1 
                       
                       , 
                       3 
                       , 
                       5 
                       , 
                       … 
                     
                   
                   ⁢ 
                   
                     { 
                     
                       a 
                       j 
                     
                     } 
                   
                 
                 &lt; 
                 
                   k 
                   p 
                 
                 &lt; 
                 
                   
                     min 
                     ⁡ 
                     
                       [ 
                       
                         
                           1 
                           k 
                         
                         , 
                         
                           
                             min 
                             
                               
                                 j 
                                 = 
                                 2 
                               
                               , 
                               4 
                               , 
                               6 
                               , 
                               … 
                             
                           
                           ⁢ 
                           
                             { 
                             
                               a 
                               j 
                             
                             } 
                           
                         
                       
                       ] 
                     
                   
                   . 
                 
               
             
             
               
                 ( 
                 35 
                 ) 
               
             
           
         
       
     
   
   From (29) and the relationship 1+tan 2 (z j )=sec 2 (z j ), we have 
   
     
       
         
           
             
               
                 
                   cos 
                   ⁡ 
                   
                     ( 
                     
                       z 
                       j 
                     
                     ) 
                   
                 
                 = 
                 
                   
                     ± 
                     
                       
                         1 
                         
                           1 
                           + 
                           
                             
                               tan 
                               2 
                             
                             ⁡ 
                             
                               ( 
                               
                                 z 
                                 j 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   = 
                   
                     
                       ± 
                       
                         
                           d 
                           0 
                         
                         τ 
                       
                     
                     ⁢ 
                     
                       
                         1 
                         
                           
                             
                               z 
                               j 
                               2 
                             
                             + 
                             
                               
                                 d 
                                 0 
                                 2 
                               
                               
                                 
                                   τ 
                                   2 
                                 
                                 ⁢ 
                                 
                                     
                                 
                               
                             
                           
                         
                       
                       . 
                     
                   
                 
               
             
             
               
                 ( 
                 36 
                 ) 
               
             
           
         
       
     
   
   We know from above that z j , j=1, 2, 3, . . . , are solutions of (29). Now using the above expression, we can rewrite a(z j ) defined in (33) as 
                   a   ⁡     (     z   j     )       =       ±     τ     kd   0         ⁢           z   j   2     +       d   0   2       τ   2         ⁢                         (   37   )               
where according to Observations 1 and 2 above, the plus sign (+) is used for even values of j, and the minus sign (−) is used for odd values of j. With (37) we make the following observation:
         Observation 3: Since z 1 &lt;z 2 &lt;z 3 &lt;z 4 &lt; . . . , from (37) (and Observations 1 and 2), we see that a(z j ) is a monotonically decreasing function for odd values of j (1, 3, 5, . . . ), i.e., a(z 1 )&gt;a(z 3 )&gt;a(z 5 )&gt; . . . , and a(z j ) is a monotonically increasing function for even values of j (0, 2, 4, 6, . . . ), i.e., a(z 0 )&lt;a(z 2 )&lt;a(z 4 )&lt;a(z 6 )&lt; . . . We also see that       
               a   ⁡     (     z   0     )       =     1   k       ,         
z 0 =0.
 
   From this observation, the bounds for k p  in (35) can now be expressed as 
   
     
       
         
           
             
               
                 
                   
                     a 
                     ⁡ 
                     
                       ( 
                       
                         z 
                         1 
                       
                       ) 
                     
                   
                   &lt; 
                   
                     k 
                     p 
                   
                   &lt; 
                   
                     1 
                     k 
                   
                 
                 , 
                 
                   
                     z 
                     1 
                   
                   ∈ 
                   
                     
                       ( 
                       
                         
                           π 
                           2 
                         
                         , 
                         π 
                       
                       ) 
                     
                     . 
                   
                 
               
             
             
               
                 ( 
                 38 
                 ) 
               
             
           
         
       
     
   
   Thus, we conclude that for the interlacing property to hold we must have 
   
     
       
         
           
             
               
                 
                   
                     
                       - 
                       
                         τ 
                         
                           kd 
                           0 
                         
                       
                     
                     ⁢ 
                     
                       
                         
                           z 
                           1 
                           2 
                         
                         + 
                         
                           
                             d 
                             0 
                             2 
                           
                           
                             τ 
                             2 
                           
                         
                       
                     
                   
                   &lt; 
                   
                     k 
                     p 
                   
                   &lt; 
                   
                     1 
                     k 
                   
                 
                 , 
                 
                   
                     z 
                     1 
                   
                   ∈ 
                   
                     
                       ( 
                       
                         
                           π 
                           2 
                         
                         , 
                         π 
                       
                       ) 
                     
                     . 
                   
                 
               
             
             
               
                 ( 
                 39 
                 ) 
               
             
           
         
       
     
   
   Note that for the values of k p  in this range, the interlacing property and the fact that the root of F i (z) are all real can be used in Theorem 2 to guarantee that F r (z) also has only real roots. At this point, we see that all the conditions of Theorem 1 are satisfied. 
   It is possible to summarize the algorithm for determining the proportional controller parameters as shown in  FIG. 5 . The process initiates, at step  400 , by obtaining for a network a set of parameters k, d 0 , and τ, where k is a steady-state gain of said network, d 0  is a time delay of said network, and τ is a time constant of said network. Next, at step  410 , determining the root z 1  in the interval 
           (       π   2     ,   π     )         
of
 
               tan   ⁡     (     z   1     )       =       -     π     d   0         ⁢     z   1         ,         
Next at step  420 , computing the range of stable gains for k p  for this particular network as
 
   
     
       
         
           
             
               - 
               
                 τ 
                 
                   kd 
                   0 
                 
               
             
             ⁢ 
             
               
                 
                   z 
                   1 
                   2 
                 
                 + 
                 
                   
                     d 
                     0 
                     2 
                   
                   
                     τ 
                     2 
                   
                 
               
             
           
           &lt; 
           
             k 
             p 
           
           &lt; 
           
             
               1 
               k 
             
             . 
           
         
       
     
   
   As an example illustrating the use of the algorithm, consider the sample problem of characterizing the stabilizing proportional controller gains for a TCP/AQM system with nominal operating parameters of T=ρC=45 Mbps, N=800, and d 0 =55 m sec. We also select a small nominal packet size of 64 bytes which we use only for the computation of the stability region. A smaller packet size is selected for this purpose because of the fluid-flow model used in the TCP/AQM control problem. Note that in deriving the control parameters, T is the control target and the TCP parameter θ=⅔. Following the procedure described in  FIG. 5 , compute 
             z   1     ∈     (       π   2     ,   π     )           
satisfying (29) to obtain z 1 =1.7579. From this, it is possible to obtain the range of stable k p  gains as −5.1115×10 −6 &lt;k p &lt;9.5102×10 −7 .
 
   As a simple assessment of the region of gains obtained, the step response of a gain chosen from within the region may be examined. Set the controller gain k p  (inside the stabilizing range) as −1.789×10 −6 . With this, we obtain the step response of the closed-loop TCP/AQM system as shown in  FIG. 6 . We can see from this figure that the closed-loop system is stable and the system output R(t) tracks the step input signal T(t). 
   Choosing which gain is most appropriate for a given system is a decision of the system engineer. Increased proportional controller gain reduces error, but high gains may destabilize the system. Having available a range over which all gains are stable provides the advantage to the system engineer of being able to emphasize whichever aspect of controller performance is most desired, while at the same time ensuring that the system performance remains within bounds. 
   Once the stabilizing proportional controller gains have been determined (based upon a TCP/AQM model using small nominal packet size e.g. 64 byte packets), the proportional control algorithm can easily be constructed. The proportional controller output (19) is given in the s-domain as
 
 P   p ( s )= C   p ( s ). E ( s )= k   p   .E ( s ).
 
where E(s) is the Laplace transform of the control error e(t)=T−R(t).
 
   Denote t m , m=1, 2, 3, . . . as the sampling instants (i.e., the times the controller reads the input values). The P-term in the controller output can be written in the discrete time domain as
 
 p   p ( t   m )= k   p   e ( t   m )
 
   A flow chart for the control algorithm and the packet mark/drop routine are shown in  FIG. 7  and  FIG. 8 . In the figures, the discrete sampling instants are simply represented as n=0Δt,1Δt,2Δt,3Δt, . . . Note that no packet marking/dropping takes place when R(t)≦T L  in  FIG. 8 . The parameter T L  rate threshold is simply a rate threshold lower than or equal to the control target T during which no packets are marked/dropped even though the mark/drop probability p(t) can be greater than zero. This simple mechanism helps to further minimize oscillations in link utilization and keep the utilization around the control target. Given that the models used in the design of the control system are approximations of the real TCP/AQM plant (i.e., neglect TCP slow start, timeouts), additional mechanisms may be useful to enhance the performance. 
   It is also important to note that rate measurements are usually noisy and as a result will require some low pass filtering. A simple exponentially weighted moving average (EWMA) filter, for example, can be used for this. The EWMA filter can be expressed as
 
 {circumflex over (R)} ( t   m )=(1−β) {circumflex over (R)} ( t   m−1 )+β R ( t   m ),0&lt;β&lt;1.
 
   As shown in  FIG. 7  the process initiates, at step  600 , at discrete time n=0, by initializing certain parameters. The timer is set to Δt time units, and mark/drop probability p(0), and Rate signal R(0) are set to initial values. The initial mark/drop probability is used in the mark/drop routine until further samples are available. A nominal packet size of x is also chosen at step  600 . At step  610 , the timer is reset to Δt to advance to the next discrete time interval. Then at step  620  the data arrival rate R is measured. 
   At step  630  there is an optional step of pre-filtering the data arrival rate as described previously. 
   At step  640  the assigned capacity is determined. Typically this is a given for a particular network configuration, but may vary as circumstances warrant, for example if the network is modified. 
   At step  650  an error signal e(n) is calculated as the difference between the assigned capacity and the measured (and possibly filtered) data arrival rate The error signal is normalized by the nominal packet size x so that the measurements R and T will be consistent with the packet size x used in the computations of the stability gain. 
   At step  660 , a current mark/drop probability p(n) is calculated. 
   The mark/drop probability calculated at step  660  may be used as the mark/drop probability until the next measurement time as tracked by the timer, at which point a new mark/drop probability will be calculated. In addition, the filtered arrival rate R′(n) if filtering is used, is stored to be used at the next measurement time. 
   The process may then loop back to step  610  upon timer expiration for another iteration of the process. 
     FIG. 8  presents a flowchart of a random number generator mark/drop routine. The decision to accept or mark/drop an incoming packet in the routine is based upon the outcome of a comparison of a randomly generated number p r ε[0,1] and the mark/drop probability p(n). The procedure can be described as follows. 
   Upon a packet arrival at the queue, at step  700  a determination is made whether the arrival rate is less than a no-mark/drop rate threshold. If the rate is less than or equal to the rate threshold, then the incoming packet is queued at step  740 . If the rate is not less than or equal to the rate threshold, then the routine moves to step  710  where a random number p r ε[0,1] is generated. At step  720  a determination of whether the random number p r  is less than or equal to the calculated mark/drop probability p(n) is made. 
   If the probability p r  is less than or equal, then the packet is marked/dropped at step  730 . If not, the packet is queued at step  740 . 
     FIG. 9  provides a high-level description of the overall proportional control scheme according to an embodiment of the invention. At module  800  TCP/AQM parameters representative of the specific data network to be controlled are obtained. At module  810  these parameters are used to calculate a regime of stable gains for proportional gain k p  for a proportional controller. At module  810  a particular gain is selected from the regime calculated in the previous step. At module  825 , an ongoing mark/drop probability calculation occurs, using the previously selected gain from module  810 , and using a measured data arrival rate from module  815  and an assigned capacity T(n) and nominal packet size x. At module  830  a current mark/drop probability is calculated. The module  835  generates a random number in the range [0,1]. Module  840  utilizes the current mark/drop probability p(n) calculated by module  830 , and the random number calculated by module  835  to make a determination to mark/drop or queue an incoming packet. 
   While the invention has been described in conjunction with specific embodiments thereof, it is evident that many alternatives, modifications, and variations will be apparent to those skilled in the art in light of the foregoing description. Accordingly, it is intended to embrace all such alternatives, modifications, and variations as fall within the spirit and broad scope of the appended claims.