Regulation of queue length in router based on an optimal scheme.

1. Introduction

Active Queue Management (AQM), as a class of packet dropping/marking mechanism in the router queue, has been recently proposed in order to convey congestion notification early enough to the senders, so that the senders are able to reduce the transmission rates before the queue overflows and any sustained packet loss occurs [1]. There are three typical kinds of AQM algorithms: One is heuristic algorithms, such as RED (Random Early Detection) [2], BLUE [3]; One is the utility function optimal model based on economics, like REM (Random Exponential Marking) [4], AVQ (Adaptive Virtual Queue) [5]; The other one is based on the sourcing and queuing dynamic model, as PI [6] and VRC (Virtual Rate Control) [7]. The advantage of the latter two algorithms is that the design of controller is based on explicit model, so the stability analysis and parameters modulation can be given theoretically.

TCP/AQM dynamics have time varying roundtrip times (RTTs) and uncertainties, which requires more robustness for the designed schemes. This paper focus on the source algorithm which Kelly [8] proposed based on economic utility function through an optimization framework. It is well known that sliding mode control (SMC) is an effective method of robustness control, and sliding mode control systems possess strong robustness against parameter perturbations and external disturbances [9], which is very suitable for time varying network system. In the recent years, many studies have been focus on the domain [10-12]. In these papers, they proposed robust sliding mode control algorithms. Because the three controllers are insensitive to variance of the network parameters, they are suitable for time-varying network systems. However, one of the representative characteristics of the three controllers is that the convergence of the system states to the equilibrium point is asymptotical but not in finite time, which means the queue length in buffer, can not converge to the desired value in finite time. In addition, there still exists chattering when system motion is in steady state. Recently, the terminal sliding mode control (TSMC) has been developed [13, 14], which can guarantee the finite reaching time to the sliding surface from initial states and the finite reaching time to the equilibrium point.

Kelly et al. [8] have studied the convergence in the presence of communication delays [4,15] through an optimization framework, which is a new and effective method to analyze the performance of congestion control for the Internet. So in this paper we propose an AQM algorithm based on Kelly's scheme by using sliding mode control. The structure of the paper are as follows: in Section 2 we analyze the Kelly's method, in Section 3 and 4, we design the linear and terminal sliding mode AQM controller respectively to study the convergence of the queue, the conclusion is given in the last section.

2. Kelly's Optimal Scheme

In this section we briefly describe the rate allocation problem in the Kelly's optimization framework.

Consider a network with a set L of resources and a set 1 of users. Let [C.sub.i] denote the finite capacity of resource 1 [member of] L. Each user i [member of] I has a fixed route [r.sub.i], which is a set of resources traversed by user is packets. We define a zero-one matrix A, where [A,sub.i,l] = I if l [member of] [r.sub.i] and [A,sub.i,l] = 0 otherwise. When its rate is [x.sub.i], user i receives utility [U.sub.i] ([x.sub.i]). We take the view that the utility functions of the users are used to select the desired rate allocation among the users. The utility [U.sub.i] ([x.sub.i]) is an increasing, strictly concave and continuously differentiable function of [x.sub.i] over the range [x.sub.i] [greater than or equal to] 0. Under this setting, the rate allocation problem of interest can be formulated as the following optimization problem [15]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

where C = ([C.sub.l], l [member of] L) The first constraint is the capacity constraint which states that the sum of the rates of all users utilizing resource should not exceed its capacity [C.sub.l].

Each user i adjusts its rate according to the following differential equation.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

where [k.sub.i] and [[omega].sub.i], are positive constants, [k.sub.i] is the gain parameter [[omega].sub.i] shows the users' willingness to pay per unit time. [p.sub.l] (*) is an increasing function of the aggregate rate of the users going through it, and it can also be seen as the packet loss function that similar to ECN possibility function [16].

The simplified dynamic model is

[??](t) = k([omega]-r(t)p(t)), (3)

where r(t) is the user's sending rate at time t, p(t) is the marker probability of ECN, k and w are the corresponding parameters.

Assume the network model is single user and single link. The dynamic buffer length at bottleneck is that

[??](t) = r(t) - C, (4)

where q(t) is the instantaneous queue length in buffer, C is link capacity.

Let [x.sub.1](t) = q(t) - [q.sub.d], [x.sub.2](t)=r(t) - C, (3) and (4) can be described as

[[??].sub.1](t) = [x.sub.2](t), (5)

[[??].sub.2](t) = k [[omega] - ([x.sub.2](t) +C)p(t)], (6)

where [q.sub.d] is the reference queue length.

The AQM algorithms based on control theory treat the queue length in router as a controllable state, and through a feedback mechanism adjust the probability of traffic drop or marker. In order to maintain the queue length at the desired value, then the system can get high link utilization and low time delay.

Our control objective is through design of the marker probability p(t) with 0[less than or equal to] p(t) [less than or equal to] 1, obtain higher link utilization, low packet loss rate and small queue fluctuations.

3. Design of Sliding Mode Control Algorithm

There are mainly two steps in the design of sliding mode control systems. One is the design of sliding surface, on which the system should get desired quality, such as asymptotically stable; The other is designing the sliding mode controller, which should guarantee the arriving condition.

3.1. Sliding Surface Design

First choose a sliding surface as conventional

S (t) - [cx.sub.1] (t) + [x.sub.2] (t). (7)

The objective of sliding mode control is to make the state slide to origin along the sliding surface in a finite time. That means the error of queue length is zero, and the sending rate and link capacity are totally matching.

When arrive at the sliding surface, S(t) = 0, so

[cx.sub.1] (t) + [x.sub.2] (t) = 0 . (8)

Substituting (8) into (5), we can obtain the sliding mode dynamics as follows

[[??].sub.2] (t) = -[cx.sub.1] (t), (9)

[x.sub.i] (t) = [x.sub.i] ([t.sub.0])[e.sup.-c(t-[t.sub.0])] (10)

where [t.sub.0] means the initial time. So the system motion on the sliding surface (7) can converge to the origin point in finite time if c > 0 .

3.2. Sliding Mode Controller Design

Let S(t) = 0, we can get the equivalent control law

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

Apparently, this controller can make the system (5) (6) stable, but it can not satisfy the physical meaning of the marker probability 0 [less than or equal to] [p.sub.eq] [less than or equal to] 1. However (11) is helpful for us to design a more reasonable AQM controller

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

Theorem 1: If the control law (12) is used for system (5) and (6), the reaching condition is satisfied if [alpha] [greater than or equal to] 1, [beta] > 0.

Proof When S(t) > 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

So if S(t) > 0, choose [alpha] [greater than or equal to] 1, [beta] > 0 and the reaching condition S(t)S(t) < 0 is satisfied. When S(t) < 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

So if S(t) < 0, choose [alpha] [greater than or equal to] 1, [beta] > 0 and the reaching condition S(t)S(t) < 0 is satisfied too.

Theorem 2: The sliding mode dynamics (9) can converge to origin point after the time

[t.sub.max] = |[cx.sub.1](0) + [x.sub.2](0)|/[k[beta]r.sub.min] (13)

where [r.sub.min] is the lowest sending rate.

Proqf Choose a Lyapunov function candidate for (9) as follows

V(x,t)= 1/2 [S.sup.2](t), (14)

then the time derivative of V (t) along (9) is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

From Theorem l we can get [alpha] [greater than or equal to] 1, [beta] 0, so

[??] < - |S|k[beta]r(t) < - |S|[k[beta]r.sub.min] (16)

By (14), we have

|S| = [square root of 2V]. (17)

Substituting (17) into (16), we can obtain the following inequality

[??] < - [square root of 2V]([k[beta]r.sub.min]), (18)

then

V(x,t)< [([k[beta]r.sub.min]/[square root of 2] + [square root of V(0)]).sup.2]. (19)

So we can get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (20)

3.3. Simulation Results

In this section we validate the effectiveness and performance of the controller proposed in this paper by simulations. We consider the dumbbell network topology with a single bottleneck link in Figure 1.

Choose the parameters of network as follows: the maximum buffer of each router is 500 packets and the link capacity is C = 1250packets/s . The desired queue length [q.sub.d] is 200 packets. The initial queue length is 400 packets. The PSMC-AQM controller parameters are [alpha] = 1, [omega] = 10 , [beta] = 0.05, k = 15, c = 12. In order to reduce the chattering problem, a saturation function is used. The RED (Random Early Detection) algorithm is also simulated under the same network condition for the purpose of comparison. In addition, we use the parameters minimum 80packets and maximum 320packets.

[FIGURE 1 OMITTED]

Queue length, link utilization and data dropping between RED-AQM and PSMC-AQM are compared. Figure 2 and Figure 3 demonstrate that the PSMC-AQM controller considers not only the queue length but also the matching condition of the assemble rate and the link capacity, so it reflects the network condition better than RED. Both of the algorithms can control the queue length near the desired 200 packets, and PSMC-AQM get less data loss rate, so it makes higher link utilization rate. The results are showed in Table l.

[FIGURE 2 OMITTED]

[FIGURE 3 OMITTED]

4. Design of Terminal Sliding Mode Control Algorithm

Last section introduces sliding mode control into the optimization based internet congestion control model, and designs a linear sliding surface, and then validates the effectiveness of the algorithm in simulation. But the sliding mode along the sliding surface is asymptotically stable, that means the converging time could be quite long. For speediness is so important for a router algorithm, a special nonlinear sliding surface named terminal sliding surface is proposed in this section. The terminal sliding surface guarantees the finite reaching time to the sliding surface from initial states and the finite reaching time to the origin point. So the converging time is limited, and the speed of the sliding mode control system is enhanced, further the congestion control performance is improved.

4.1. Design of Terminal Sliding Surface

We design a nonlinear terminal sliding surface as follows:

S(t) = [d.sub.1][x.sub.1](t)+ [d.sub.2][x.sub.2] (t) + [d.sub.3][([x.sub.1](t)).sup.q/p], (21)

where [d.sub.1] >0, [d.sub.2] >0, [d.sub.3] >0, p and q are odd positive integers and they satisfy q<p<2q. The sliding surface S(t) corresponds to a combination of the queue length error, the error between incoming traffic rate and link capacity.

When the system state trajectories are on the terminal sliding surface, S(t) satisfies S(t) = 0. So we can obtain the following equality

[x.sub.2](t) =_-[d.sub.2.sup.-1] [[d.sub.1][x.sub.1](t) + [d.sub.3][([x.sub.1](t)).sup.q/p]] (22)

Substituting (22) into (5), we can obtain the sliding mode dynamics as follows:

[[??].sub.1](t) =-[d.sub.2.sup.-1] [[d.sub.1][x.sub.1](t) - [d.sub.2.sup.-1][d.sub.3][([x.sub.1](t)).sup.q/p]]. (23)

In order to prove that (23) can converge to the equilibrium point in finite time, we introduce a lemma as follows

Lemma 1 [13]: Assume that a continuous, positive definite function V (t) satisfies the following differential inequality

[??](t) [less than or equal to] -[alpha][V.sup.[eta]](t), [for all]t [greater than or equal to] 0, V(0) [greater than or equal to] 0, (24)

where [alpha] > 0, 0 < [eta] < 1 are constants. Then V(t) satisfies the following inequality:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (25)

and

V (t) = 0, [for all]t [greater than or equal to] [t.sub.r] (26)

with [t.sub.r] given by

[t.sub.r] = [V.sup.1-[eta]](0)/[alpha](1-[eta]). (27)

Theorem 3: The sliding mode dynamics (23) can converge to the equilibrium point after the time [t.sub.r] and [t.sub.r] satisfies

[t.sub.r] = [||[x.sub.1](0)||.sup.2(1-[eta])]/[2.sup.(1-[eta])][alpha](1-[eta]), (28)

where [x.sub.1](0) is the initial value of [x.sub.1](t) and [alpha] = [2.sup.[eta]][d.sub.2.sup.-1][d.sub.3], [eta] = q/p + 1/2

Proof. Choose a Lyapunov function candidate for the system (23) as follows:

V(t) = 1/2 [x.sub.1.sup.T] (1)[x.sub.1] (t) (29)

then the time derivative of V(t) along (23) is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (30)

By (29), we have

||[x.sub.1](t)|| = [square root of 2V(t)] (31)

Substituting (31) into (30), we can obtain the following inequality

[??](t) [less than or equal to] - [alpha][V.sup.[eta]](t) (32)

where [alpha] = [2.sup.[eta]][d.sub.2.sup.-1][d.sub.3], [eta] = q/p + 1/2

According to Lemma 1, we know that the sliding mode dynamics (23) can converge to the equilibrium point after the time [t.sub.r] and [t.sub.r] satisfies the following equality

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (33)

So the system motion on the terminal sliding surface (21) can converge to the equilibrium point in finite time.

4.2. Design of Terminal Sliding Mode Controller

In the subsection, we design a robust terminal sliding mode controller to satisfy the reaching condition. We consider the following control structure of the form

p(t) = [P.sub.eq](t) + [P.sub.N] (1) (34)

Theorem 4: If the control law is used for system (5) and (6) as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (35)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (36)

then the controller can satisfy the reaching condition

[??](t) = -[epsilon][S.sup.2] sgn(S(t)) - kS(t). (37)

Proof : Recall (2 l), the time derivative of S(t) along the trajectory of (5) and (6) under the control (34) is given as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (38)

Substitute (34) into (38), we can get

S(t) = -[k.sub.v]S(t) - [epsilon][S.sup.2] sgn(S(t)).

So the controller (34) can satisfy the reaching condition (37). That is to say, the controller can force system state trajectories toward the terminal sliding surface infinite time and maintain them on the sliding surface after then. Meanwhile, the reaching rate is fast and chattering is low.

4.3. Simulation Results

In this section the effectiveness and performance of the terminal sliding mode controller (TSMC) is validated by simulations. Common sliding mode controller (SMVS, Sliding Mode Variable Structure) is also simulated for the purpose of comparison with suggested parameter values [alpha] =0.96 , [beta] = -0.96, w = 2 given in [15]. We consider the same dumbbell network topology with a single bottleneck link as Figure 1.

The network parameters are chosen the same as Part C of Section 3: the maximum buffer of each router is 500 packets and the link capacity is C =1250packets/s . The desired queue length [q.sub.d] is 200 packets. The initial queue length is 400 packets. And the parameters of TSMC-AQM controller are chosen as [d.sub.1] = 1, [d.sub.2] = 1, [d.sub.3] = 1000, q = 3,p = 5, k = 5, [epsilon] = 0.1. From Theorem 3 we can calculate [t.sub.r] = 0.5506 s.

The simulation is operated under variable network conditions. The link capacity C and the roundtrip time R are varied through the process. Figure 4 and Figure 5 show that the two controllers are insensitive to different TCP loads and link capacity, but TSMC has shorter regulating time and better steady performance than SMVS controller.

5. Conclusions

In this paper, we combine the Kelly's optimization scheme and the sliding mode control algorithm to analyze the convergence of the queue. We design two sliding mode algorithm: the linear and the terminal ones. The simulation results show that both of the algorithms can converge to the equilibrium point in finite time. Obviously, the terminal sliding mode control can obtain faster transients and less oscillatory responses under dynamic network conditions, which translates into higher link utilization, low packet loss rate and small queue fluctuations. And the proposed controller has better stability and robustness than common sliding mode controller, which would be meaningful for the congestion control of the Internet.

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

Received July 12, 2008; revised January 20, 2009; accepted March 5, 2009

6. References

[1] B. Braden and D. Clark, "Recommendations on queue management and congestion avoidance in the Internet," RFC 2309, 1998.

[2] S. Floyd and V. Jacobson, "Random early detection gateways for congestion avoidance," IEEE/ACM Transaction on Networking, Vol. I, pp. 397-413, 1993.

[3] W. C. Feng, Kang G. Shin, D. D. Kandlur, et al., "The blue active queue management algorithms," IEEE/ACM 'transactions on Networking, Vol. 10, No. 4, pp. 513-528, 2002.

[4] S. Athuraliya, S. H. Low, V. H. Li, et al., "REM: Active queue management," IEEE Network, Vol. 15, No. 3, pp. 48-53.2001.

[5] S. Srisankar, Kunniyur, and R. Srikant, "An adaptive virtual queue (AVQ) algorithm for active queue management," IEEE/ACM 'transactions on Networking. Vol. 12, No. 2, pp. 266-289, 2004.

[6] C. V. Hollot, V. Misra, D. Towsley, and W. Gong, "On designing improved controllers for AQM routers supporting TCP flows," Proceedings of IEEE INFOCOM, Anchorage, Alaska, USA, IEEE Communications Society, pp. 1726-1734, 2001.

[7] 11. Lim, K. J. Park, and C. 11. Choi. "Virtual rate control algorithm for active queue management in TCP networks" IEEE Electronics Letters, Vol. 38, No. 16. pp. 873-874,2002.

[8] F. Kelly, A. Maulloo, and D. Tan, "Rate control for communication networks: Shadow prices, proportional fairness and stability," Journal of the Operational Re search Society, Vol. 49, No. 3, pp. 237-252, March 1998.

[9] Y. 11. Rob and J. 11. Oh, "Robust stabilization of uncertain input-delay systems by sliding mode control with delay compensation." Automatica. Vol. 35, pp. 1861-1865, 1999.

[10] F. Y. Ren, C. Lin. and X. H. Yin, "Design a congestion controller based on sliding mode variable structure control," Computer Communications, Vol. 28, pp. 1050 1061, 2005.

[11] P. Yan, Y. Gao, and 11. AOzbay, "A variable structure control approach to active queue management for TCP with ECN," IEEE 'transactions on Control Systems Technology, Vol. 13, pp. 203-215, 2005.

[12] F. J. Yin, G. M. Dimirovski, and Y. W. Jing, "Robust stabilization of uncertain input delay for Internet congestion control," Proceedings of the American Control Conference, Minneapolis, Minnesota, USA, pp. 5576-5580, 2006.

[13] Y. Tang, "Terminal sliding mode control for rigid robots," Automatica, Vol. 34, pp. 51-56, 1997.

[14] S. H. Yu, X. H. Yu, B. Shirinzadeh, and Z. H. Man, "Continuous finite-time control for robotic manipulators with terminal sliding mode," Automatica, Vol. 41, pp. 1957-1964,2005.

[15] F. Paganini, Z. Wang, J. C. Doyle, and S. H. Low, "Congestion control for high performance, stability, and fairness in general networks," IEEE/ACM Transaction on Networking. Vol. 13, No. I, pp. 43-56, 2005.

[16] R. Thommes and M. J. Coates. "Deterministic packet marking for congestion price estimation," In Proceeding of IEEE INFOCOM, I long Kong, pp. 12-23, 2004.

Nannan ZHANG

Key Laboratory of Integrated Automation of Process Industry, Northeastern University, Shenyang, China

Email: [e-mail]

Table 1. Comparison between RED and PSMC.

performance         RED     PSMC

rate of link
utilization         99.67   99.86
rate of data loss   2.35    0.09