# Multiple time-delays system modeling and control for router management

Yassine Ariba, Frédéric Gouaisbaut, Yann Labit

► To cite this version:

Yassine Ariba, Frédéric Gouaisbaut, Yann Labit. Multiple time-delays system modeling and control for router management. European Control Conference (ECC09), Aug 2009, Budapest, Hungary. hal-00357762

HAL Id: hal-00357762

https://hal.science/hal-00357762v1

Submitted on 2 Feb 2009

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Multiple time-delays system modeling and
control for router management

Yassine Ariba*†, Frédéric Gouaisbaut*† and Yann Labit*‡

October 2008

Abstract

This paper investigates the overload problem of a single congested router in TCP (*Transmission Control Protocol*) networks. To cope with the congestion phenomenon, we design a feedback control based on a multiple time-delays model of the set TCP/AQM (*Active Queue Management*). Indeed, using robust control tools, especially in the quadratic separation framework, the TCP/AQM model is rewritten as an interconnected system and a structured state feedback is constructed to stabilize the network variables. Finally, we illustrate the proposed methodology with a numerical example and simulations using NS-2 [11] simulator.

# 1 INTRODUCTION

In IP networks, active queue management (AQM), embedded in router, reports to TCP sources its processing load. The objective is to manage the buffer utilization as well as the queueing delay. This has motivated a huge amount of work aiming at understanding the congestion phenomenon and achieving better performances in terms of *Quality of Service* (QoS). As a matter of fact, there has been a growing recognition that the network itself must participate in congestion control and resource management [8], [26].

The AQM principle consists in dropping (or marking when ECN [34] option is enabled) some packets before buffer saturates. Hence, following the *Additive-Increase Multiplicative-Decrease* (AIMD) behavior of TCP, sources reduce their congestion window size avoiding then the full saturation of the router. Basically, AQM support TCP for congestion avoidance and feedback to the latter when traffic is too heavy. Indeed, an AQM drops/marks incoming packet with a given probability related to a congestion index (such as queue length or delays) allowing then a kind of control on the buffer occupation at routers. Various mechanisms have been proposed in the network community for the development of AQM such as Random Early Detection (RED) [14], Random Early Marking (REM) [2], Adaptive Virtual Queue (AVQ) [24] and many others [35]. Their performances have been evaluated [13], [35] and empirical studies [26] have shown the effectiveness of these algorithms.

As it has been highlighted in the literature (see for example [27], [17] and reference therein), AQM acts as a controller supporting TCP for congestion control and can

<footnote>*Université de Toulouse; UPS, 118 Route de Narbonne, F-31062 Toulouse, France.</footnote>

<footnote>†LAAS; CNRS; 7, avenue du Colonel Roche, F-31077 Toulouse, France.
{yariba,fgouaisb,ylabit}@laas.fr</footnote>
be reformulated as a feedback control problem. Then, a significant research has been devoted to the use of control theory to develop more efficient AQM. Using dynamical model developed by [29], some P (Proportional), PI (Proportional Integral) [17] have been designed. In the same framework, other tools have been used to extend this preliminary work such as a PID controller [35], [12] or robust control [33]. However, most of these papers do not take into account the delay and ensure the stability in closed loop for all delays which could be very conservative in practice.

The study of congestion problem in time delay systems framework is not new and has been successfully exploited. Nevertheless, most of these works have been dedicated to the stability analysis of networks composed of homogeneous sources (see for example [25], [31], [9], [28] and [37]). In this paper, networks with heterogeneous sources are considered introducing then several delays and increasing the model complexity. Regarding the AQM design problem, some works have already been done in [21] and [16]. In [16], the construction of the AQM required to invoke the Generalized Nyquist Theorem and [21] provides a delay dependent state feedback involving delay compensations with a memory feedback control. Or even in [3], delays are replaced by a Padé approximation which is known to be not so accurate. All these latter methodologies are interesting in theory but sorely suitable in practice. While these latter studies have considered the simplified model of TCP/AQM from [29], we use in this contribution a more accurate model presented in [27]. Indeed, contrary to [21], [3] and [16], both forward and backward delays are taken into account (that is, we do not neglect forward delays). Then, congestion control of networks consisting in heterogeneous TCP sources is transformed into a stabilization problem for multiple time delays systems. Using a robust analysis framework and especially quadratic separation approach developed for time-delay systems by [15], a stabilizing AQM is designed. The proposed control mechanism enables QoS in terms of RTT (Round Trip Time) and delay jitter which are relevant features for streaming and real-time applications over IP networks. Note that the approach employed in this paper allows the formulation of the problem into matrix inequalities [7] that provide systematic stability condition, easy to test.

The paper is organized as follows. The second part presents the mathematical model of a network composed of a single router and several heterogeneous sources supporting TCP. Section III is dedicated to the design of the AQM ensuring the stabilization of TCP. Section IV presents a numerical example and simulation results using NS-2.

## 2 NETWORK DYNAMICS

In this paper, we consider a network consisting of a single router and *N* heterogeneous TCP sources. By heterogeneous, we mean that each source is linked to the router with different propagation times (see Figure 1). Since the bottleneck is shared by *N* flows, TCP applies the congestion avoidance algorithm to cope with the network saturation [18].

Deterministic fluid-flow models have been widely used (see [27], [29], [20] and [36] and references therein) to describe congestion control and AQM schemes in IP networks. These models capture the mean behavior of the TCP dynamic. While many studies dealing with network control in the automatic control theory framework consider the model proposed by [29], we use in this paper the model introduced in [27] and described by (1). Contrary to the former, the model (1) takes into account
<figure><img src="image_2.png" /><figcaption>Figure 1: Network topology</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Figure 2: A single connection</figcaption></figure>

the forward and backward delays and does not make the simplifying assumption that $(W(t - \tau)/W(t))(1 - p(t - \tau^b)) = 1$ [21]. The model and notations are as follow:

$$ 
\left\{ 
\begin{aligned}
\dot{W}_i(t) &= \frac{W_i(t-\tau_i)}{\tau_i(t-\tau_i)} (1-p_i(t-\tau_i^b)) \frac{1}{W_i(t)} \\
&\quad - \frac{W_i(t-\tau_i)}{\tau_i(t-\tau_i)} \frac{W_i}{2} p_i(t-\tau_i^b) \\
\dot{b}(t) &= -C + \sum_N \eta_i \frac{W_i(t-\tau_i^f)}{\tau_i(t-\tau_i^f)} \\
\tau_i &= \frac{b(t)}{C} + T_{p_i} = \tau_i^f + \tau_i^b
\end{aligned}
\right.
\quad (1)
$$

where $W_i(t)$ is the congestion window size of the source $i$, $b(t)$ is the queue length of the buffer at the router, $\tau_i$ is the round trip time (RTT) perceived by the source $i$. This latter quantity can be decomposed as the sum of the forward and backward delays ($\tau_i^f$ and $\tau_i^b$), standing for, respectively, the trip time from the source $i$ to the router (the one way) and from the router to the source via the receiver (the return) (see Figure 2). $C$, $T_{p_i}$ and $N$ are parameters related to the network configuration and represent, respectively, the link capacity, the propagation time of the path taken by the connection $i$ and the number of TCP sources. $\eta_i$ is the number of sessions established by source $i$. The signal $p_i(t)$ corresponds to the drop probability of a packet.

In this paper, the objective is to develop a method which computes the appropriate dropping probability applied at the router in order to regulate the queue length of the buffer $b(t)$ to a desired level (Figure 3). Since control depends on the system state, it is required to have access to them. However, congestion windows $W_i$ are not measurable. So that, we propose to reformulate the model (1) such that state vector can be measured. To this end, rates of each flow $x_i$, expressed as $x_i(t) = \frac{W_i(t)}{\tau_i(t)}$, will be considered. Hence,
<figure><img src="image_4.png" /><figcaption>Figure 3: Network control</figcaption></figure>

the dynamic of this new quantity is of the form $\dot{x}_i(t) = \frac{d}{dt} \left( \frac{W_i(t)}{\tau_i(t)} \right) = \frac{\dot{W}_i(t) - x_i(t) \tau_i(t)}{\tau_i(t)}$.

Based on the expressions of $\dot{W}(t)$, $\dot{b}(t)$, $\tau_i(t)$ (see equation (1)) and $\dot{\tau}(t) = \frac{\dot{b}(t)}{C}$, a new model of the TCP behavior is derived

$$ \left\{ \begin{aligned} \dot{x}(t) &= \frac{x(t-\tau)}{x(t)\tau(t)^2} (1 - p(t-\tau^b)) - \frac{x(t-\tau)x(t)}{2} p(t-\tau^b) \\ &\quad + \frac{x(t)}{\tau(t)} - \frac{x(t)}{\tau(t)C} \sum_N \eta_i x_i (t - \tau_i^f) \\ \dot{b}(t) &= -C + \sum_N \eta_i x_i (t - \tau_i^f) \end{aligned} \right. . \quad (2) $$

**Remark 1** This model transformation allows us to use $x_i$ instead of $W_i$ which is more suitable to handle. Indeed, numerous works have developed tools that enable flow rates measurements, especially in anomaly detection framework (see for example [4], [22]). Besides, The measure of the aggregate flow has already been proposed and successfully exploited in [24] and [21] for the realization of the AVQ (Adaptive Virtual Queue) and a PID type AQM respectively.

Our work focuses on the congestion control of a single router with a static topology ($N$ and $\eta_i$ are constant). Moreover, for the mathematical tractability, we make the usual assumption [27], [17], [21] that all delays ($\tau_i$, $\tau_i^f$ and $\tau_i^b$) are time invariant when they appear as argument of a variable (for example $x_i(t - \tau_i(t)) \equiv x_i(t - \tau_i)$). This latter assumption is valid as long as the queue length remains close to its equilibrium value and when the queueing delay is smaller than propagation delays. Defining an equilibrium point

$$ \left\{ \begin{aligned} \tau_{i0} &= T_p + b_0/C \\ \dot{b}(t) &= 0 \Rightarrow \sum_N \eta_i x_{i0} = C \\ \dot{x}_i(t) &= 0 \Rightarrow p_{i0} = \frac{C}{2+(x_{i0} \tau_{i0})^2} \end{aligned} \right. , \quad (3) $$

model (2) can be linearized:

$$ \left[ \begin{matrix} \dot{x}_1(t) \\ \vdots \\ \dot{x}_N(t) \\ \dot{b}(t) \end{matrix} \right] = A \left[ \begin{matrix} \delta x_1(t) \\ \vdots \\ \delta x_N(t) \\ \delta b(t) \end{matrix} \right] + A_d \left[ \begin{matrix} \delta x_1(t - \tau_1^f) \\ \vdots \\ \delta x_N(t - \tau_N^f) \\ \delta b(t) \end{matrix} \right] + B \left[ \begin{matrix} \delta p_1(t - \tau_1^b) \\ \vdots \\ \delta p_N(t - \tau_N^b) \end{matrix} \right] \quad (4) $$
<figure><img src="image_5.png" /><figcaption>Figure 4: Implementation of an AQM</figcaption></figure>

where $\delta x_i \doteq x_i - x_{i_0}$, $\delta b \doteq b - b_0$ and $\delta p_i \doteq p_i - p_{i_0}$ are the state variations around the equilibrium point (3). Matrices of the equation (4) are defined by

$$A = \begin{bmatrix} a_1 & 0 & 0 & h_1 \\ 0 & \cdots & 0 & \vdots \\ 0 & 0 & a_N & h_N \\ 0 & 0 & 0 & 0 \end{bmatrix}, \quad B = \begin{bmatrix} e_1 & 0 & 0 \\ 0 & \cdots & 0 \\ 0 & 0 & e_N \\ 0 & 0 & 0 \end{bmatrix}$$

$$A_d = \begin{bmatrix} f_1 \eta_1 & \cdots & f_1 \eta_N & 0 \\ \vdots & \vdots & \vdots & 0 \\ f_N \eta_1 & \cdots & f_N \eta_N & 0 \\ \eta_1 & \cdots & \eta_N & 0 \end{bmatrix},$$

with $a_i = -\frac{1-p_{i_0}}{x_{i_0} \tau_i^2} - \frac{x_{i_0} p_{i_0}}{2}$, $h_i = -\frac{2(1-p_{i_0})}{c \tau_i^3}$, $f_i = -\frac{x_{i_0}}{\tau_i^2 c}$ and $e_i = -\frac{1}{\tau_i^2} - \frac{x_{i_0}^2}{2}$. Remark that a multiple time delays system (4) is obtained with a particular form since each component of the state vector is delayed by a different quantity related to the communication path. Thus, in Section 3 an appropriate modeling of (4) with a structured form (in quadratic separation framework) is proposed in order to formulate the stability condition.

The problem of regulation is tackled in Section 3 with the design of a stabilizing state feedback for multiple time delays systems in order to guarantee a QoS. Hence, the dropping probability $p_i$ associated to source $i$ will be computed at the router by

$$p_i(t) = p_{i_0} + k_1 \delta x_i(t - \tau_i^f) + k_2 \delta b(t) \quad (5)$$

with $k_1, k_2$ are components which have to be designed (see Figure 4). Note that the dropping probability $p_i$ perceived by the source $i$ will be delayed $p_i(t - \tau_i^b)$ because of the backward delay. Thus, a structured state feedback of the form (5) is proposed:

* to avoid unnatural signals with different delay combinations in the state feedback: $\delta x_i(t - \tau_i^f - \tau_j^b)$ for $i, j \in \{1, ..., N\}$ introducing then many additional delays,

* it provides light computations (with less operations) reducing then the processing time at router,
<figure><img src="image_6.png" /><figcaption>Figure 5: An interconnected system</figcaption></figure>

* it provides a decentralized control if the dropping strategy is performed at end hosts when emulating AQM [5].

Applying the structured state feedback type control law $p_i(t)$ to each source $i$, $\forall i \in \{1, \dots, N\}$, the following interconnected system is obtained

$$ 
\begin{bmatrix} 
\delta \dot{x}_1(t) \\ 
\vdots \\ 
\delta \dot{x}_N(t) \\ 
b(t) 
\end{bmatrix} = A 
\begin{bmatrix} 
\delta x_1(t) \\ 
\vdots \\ 
\delta x_N(t) \\ 
\delta b(t) 
\end{bmatrix} + A_d 
\begin{bmatrix} 
\delta x_1(t - \tau_1^f) \\ 
\vdots \\ 
\delta x_N(t - \tau_N^f) \\ 
\delta b(t) 
\end{bmatrix} 
+ BK_1 
\begin{bmatrix} 
\delta x_1(t - \tau_1) \\ 
\vdots \\ 
\delta x_N(t - \tau_N) 
\end{bmatrix} + BK_2 
\begin{bmatrix} 
\delta b(t - \tau_1^b) \\ 
\vdots \\ 
\delta b(t - \tau_N^b) 
\end{bmatrix} 
\quad (6) 
$$

where matrices gains $K_1$ and $K_2$ are structured as $K_1 = \text{diag}\{k_{11}, \dots, k_{1N}\}$ and $K_2 = \text{diag}\{k_{21}, \dots, k_{2N}\}$.

Equation (6) represents thus the mean behavior of TCP regulated by a structured state feedback type AQM around an equilibrium point. $K_1$ and $K_2$ can be derived from the stability analysis of the interconnection (6). To this end, we propose to design these latter gains by a suitable modeling of (6) applying then the quadratic separation principle [32], [15] for the stability condition.

## 3 STABILIZATION AND QoS GUARANTEE: DESIGN OF AN AQM

The stability of the interconnected system (6) depends on matrices $K_1$ and $K_2$. This section aims to develop a method that provides such stabilizing matrices. Thus, the quadratic separation framework is considered and the following theorem will be employed [32].

**Theorem 1** Given two possibly non-squared matrices $\mathcal{E}$, $\mathcal{A}$ and an uncertain matrix $\nabla$ belonging to a set $\Xi$. The uncertain system represented on Figure 5 is stable for all matrices $\nabla \in \Xi$ if and only if it exists a matrix $\Theta = \Theta^*$ satisfying conditions

$$ [ \mathcal{E} - \mathcal{A} ]^{\perp*} \Theta [ \mathcal{E} - \mathcal{A} ]^{\perp} > 0 \quad (7) $$

$$ [ 1 \quad \nabla^* ] \Theta \begin{bmatrix} 1 \\ \nabla \end{bmatrix} \le 0. \quad (8) $$

It is then required to transform the initial system (6) into a feedback system of the form of Figure 5 where a linear equation is connected to a linear uncertainty $\nabla$. The key idea (proposed by [15] for the single time-delay systems case) consists in associating the delay operator as an uncertainty which must be bounded. Hence, Theorem 1 may
be applied to the multiple time delays system (6) by rewriting it as an interconnected system (see Figure 5) with $\mathcal{E} = 1$,

$$ \overbrace{\begin{bmatrix} X(t) \\ \hat{x}^{\tau f}(t) \\ \hat{b}^{\tau b}(t) \\ \hat{x}^{\tau}(t) \end{bmatrix}}^{w} = \overbrace{\begin{bmatrix} s^{-1}1_4 & & & \\ & \mathcal{D}_{\tau f} & & \\ & & \mathcal{D}_{\tau b} & \\ & & & \mathcal{D}_{\tau} \end{bmatrix}}^{\nabla} \overbrace{\begin{bmatrix} \dot{X}(t) \\ \hat{x}(t) \\ \hat{b}(t) \\ \hat{x}(t) \end{bmatrix}}^{z} $$ (9)

and

$$ \mathcal{E} \begin{bmatrix} \dot{X}(t) \\ \hat{x}(t) \\ \hat{b}(t) \\ \hat{x}(t) \end{bmatrix} = \begin{bmatrix} A & \tilde{A}_d & BK_2 & BK_1 \\ E_1 & 0 & 0 & 0 \\ E_2 & 0 & 0 & 0 \\ E_1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} X(t) \\ \hat{x}^{\tau f}(t) \\ \hat{b}^{\tau b}(t) \\ \hat{x}^{\tau}(t) \end{bmatrix} \quad (10) $$

where

$$ \begin{align} \hat{b}(t) &= \begin{bmatrix} b(t) \\ \vdots \\ b(t) \end{bmatrix}, \hat{b}^{\tau b}(t) = \begin{bmatrix} b(t - \tau_1^b) \\ \vdots \\ b(t - \tau_N^b) \end{bmatrix}, \nonumber \\ \hat{x}^{\tau f}(t) &= \begin{bmatrix} x_1(t - \tau_1^f) \\ \vdots \\ x_N(t - \tau_N^f) \end{bmatrix}, \hat{x}^{\tau}(t) = \begin{bmatrix} x_1(t - \tau_1) \\ \vdots \\ x_N(t - \tau_N) \end{bmatrix}, \tag{11} \\ \hat{x}(t) &= \begin{bmatrix} x_1(t) \\ \vdots \\ x_N(t) \end{bmatrix}, \mathcal{D}_{\diamond} = \begin{bmatrix} e^{-\diamond 1s} & 0 \\ & \ddots \\ 0 & e^{-\diamond Ns} \end{bmatrix}, \nonumber \end{align} $$

$X(t) = [\hat{x}' \ b(t)]'$. The delay matrix operators $\mathcal{D}_{\diamond}$ ($\diamond$ represents $\tau^f$, $\tau^b$ or $\tau$) must be defined to create the delayed signals $\hat{x}^{\tau f}$, $\hat{x}^{\tau}$ and $\hat{b}^{\tau b}$ (11).

We aim at proving the stability (i.e. no poles in the right hand side of the complex plane for all values of the delay and for all values of the uncertainty $\nabla \in \Xi$) which problem can be recast in the present framework as the well-posedness of the feedback system for all $s \in \mathbb{C}^+$, for all values of the delays ($\tau_i$, $\tau_i^f$ and $\tau_i^b$, $i = \{1, \dots, N\}$) and all admissible uncertainties $\nabla \in \Xi$. Then a conservative choice of quadratic separator that fullfills (8) is of the form

$$ \Theta = \begin{bmatrix} 0 & 0 & 0 & 0 & -P & 0 & 0 & 0 \\ 0 & -Q^f & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & -Q^b & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & -Q & 0 & 0 & 0 & 0 \\ -P & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & Q^f & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & Q^b & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & Q \end{bmatrix}, \quad (12) $$

with $P \in \mathbb{R}^{N+1 \times N+1} > 0$ and $Q^{\diamond} = \text{diag}(q_1^{\diamond}, \dots, q_N^{\diamond})$ where $q_i^{\diamond}$ are positive scalars for all $i = \{1, \dots, N\}$ and for $\diamond = \{f, b, \emptyset\}$ (see [15] for a simpler case).

Then, it remains to test the first condition (7). Since this inequality does not depend
on delays, the derived condition is said to be *Independent Of Delays* (IOD). Consequently, this latter criterion provides state feedback gains that stabilize the system for all possible values of delays. It thus appears that this method is very conservative and it would be interesting to have a condition depending on delays.

We aim now at deriving a *Delay Dependent result* ( i.e. the well known DD approach which ensures the stability for all values of the delay between zero and an upper bound) with the same methodology. To do so note that the results were delay independent because operators $e^{-\diamond_i s}$, when $s \in C^+$, can only be characterized as uncertainties norm bounded by 1. To get delay dependent results it is therefore needed to have characteristics that depend on upper bounds of delays. This can be done noting that for all $s \in C^+$ and a given delay $h \in [0, \bar{h}]$ one has $|s^{-1}(1 - e^{-hs})| \le \bar{h}$ and this operator is such that $V(s) = s^{-1}(1 - e^{-hs})\dot{X}(s)$ where $V(s)$ and $\dot{X}(s)$ are the Laplace transforms respectively of $v(t) = x(t) - x(t-h)$ and $\dot{x}(t)$. Introducing this new operator for each delay $\tau_i$, $\tau_i^f$ and $\tau_i^b$, $i = \{1, \dots, N\}$ leads to write the delay dependent stability problem of (6) as a well-posedness problem of the system in Figure 5 with

$$ \mathcal{E} = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ E_1 & 0 & 0 & 0 & -1 & 0 & 0 \\ E_2 & 0 & 0 & 0 & 0 & -1 & 0 \\ E_1 & 0 & 0 & 0 & 0 & 0 & -1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}, w = \begin{bmatrix} X(t) \\ \hat{x}^{\tau^f}(t) \\ \hat{b}^{\tau^b}(t) \\ \hat{x}^{\tau}(t) \\ w_1(t) \\ w_2(t) \\ w_3(t) \end{bmatrix}, \quad (13) $$

$$ \mathcal{A} = \begin{bmatrix} A & \bar{A}_d & BK_2 & BK_1 & 0 & 0 & 0 \\ E_1 & 0 & 0 & 0 & 0 & 0 & 0 \\ E_2 & 0 & 0 & 0 & 0 & 0 & 0 \\ E_1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ E_1 & -1 & 0 & 0 & -1 & 0 & 0 \\ E_2 & 0 & -1 & 0 & 0 & -1 & 0 \\ E_1 & 0 & 0 & -1 & 0 & 0 & -1 \end{bmatrix}, z = \begin{bmatrix} \dot{X}(t) \\ \hat{x}(t) \\ \hat{b}(t) \\ \hat{x}(t) \\ \hat{x}(t) \\ \hat{b}(t) \\ \hat{x}(t) \end{bmatrix} $$

where $\bar{A}_d = A_d \begin{bmatrix} 1_N \\ 0_{1 \times N} \end{bmatrix}$, $E_1 = \begin{bmatrix} 1_N & 0_{N \times 1} \end{bmatrix}$, $E_2 = \begin{bmatrix} 0_N \end{bmatrix}$ and $w_1(t) = \hat{x}(t) - \hat{x}^{\tau^f}(t)$, $w_2(t) = \hat{b}(t) - \hat{b}^{\tau^b}(t)$, $w_3(t) = \hat{x}(t) - \hat{x}^{\tau}(t)$ and with the augmented uncertain operator

$$ \nabla = \mathrm{Diag} \left( s^{-1} 1_4, \mathcal{D}_{\tau^f}, \mathcal{D}_{\tau^b}, \mathcal{D}_{\tau}, \mathcal{I}_{\tau^f}, \mathcal{I}_{\tau^b}, \mathcal{I}_{\tau} \right) \quad (14) $$

where $\mathcal{I}_\diamond = \mathrm{diag}(\frac{1-e^{-\diamond_1 s}}{s}, \dots, \frac{1-e^{-\diamond_N s}}{s})$, $\diamond = \{f, b, \emptyset\}$. Delay operators $\mathcal{I}_\diamond$ are thus isolated as well as operators $\mathcal{I}_\diamond$ ensuring a better bound on each delays (delay dependent case, see [15]). Expressing the covering set on every block of $\nabla$, a conservative choice of separator satisfying the second inequality (8) of Theorem 1 is

$$ \Theta = \begin{bmatrix} \Theta_{11} & \Theta_{12} \\ \Theta'_{12} & \Theta_{22} \end{bmatrix} \quad (15) $$
with

$$
\begin{align}
\Theta_{11} &= \operatorname{diag}(0_{N+1}, -Q_0^f, -Q_0^b, -Q_0, -Q_1^f T^{f^2}, -Q_1^b T^{b^2}, -Q_1 T^2), \nonumber \\
\Theta_{12} &= \operatorname{diag}(-P, 0_{6N}), \nonumber \\
\Theta_{22} &= \operatorname{diag}(0_{N+1}, Q_0^f, Q_0^b, Q_0, Q_1^f, Q_1^b, Q_1), \nonumber \\
Q_0^{\diamond} &= \operatorname{diag}(q_{01}^{\diamond}, \dots, q_{0N}^{\diamond}), \nonumber \\
Q_1^{\diamond} &= \operatorname{diag}(q_{11}^{\diamond}, \dots, q_{1N}^{\diamond}), \nonumber \\
T^{\diamond} &= \operatorname{diag}(\tau_1^{\diamond}, \dots, \tau_N^{\diamond}), \tag{16}
\end{align}
$$

where $P \in \mathbb{R}^{N+1 \times N+1} > 0$ and $q_i^{\diamond}$ are positive scalars for all $i = \{1, \dots, N\}$ and for $\diamond = \{f, b, \emptyset\}$. Since, the inequality (8) is satisfied by definition of the operator bounds of the uncertain matrix $\nabla$, it remains to verify the first one (7). After some algebraic manipulations, it can be shown that this latter inequality can be expressed as

$$
\begin{bmatrix}
\Xi_1 & \Xi_2 Q_1 T & \Xi_2 Q_1^f T^f \\
* & Q_1 T & 0_N \\
* & * & Q_1^f T^f
\end{bmatrix} > 0 \quad (17)
$$

where

$$
\Xi_1 = N_1^T \Theta N_1 + N_2^T \Theta N_1 + N_1^T \Theta N_2, \\
\Xi_2 = \left[ \begin{array}{ccc} 0_{N \times 2N+1} & E_1 BK_2 & E_1 BK_1 \end{array} \right]^T,
$$

$$
N_1 = \begin{bmatrix}
A & \bar{A}_d & 0_{N+1 \times 2N} \\
E_1 & & \\
E_2 & 0_{3N \times 3N} & \\
E_1 & & \\
\hline
E_1 A & E_1 \bar{A}_d & 0_{N \times 2N} \\
0_{N \times N+1} & E_2 \bar{A}_d & 0_{N \times 2N} \\
E_1 A & E_1 \bar{A}_d & 0_{N \times 2N} \\
\hline
1_{4N+1} & & \\
E_1 & & \\
E_2 & -1_{3N} & \\
E_1 & &
\end{bmatrix}, \quad (18)
$$

$$
N_2 = \begin{bmatrix}
0_{N+1 \times 2N+1} & BK_2 & BK_1 \\
& 0_{3N \times 4N+1} & \\
& & 0_{N \times 2N+1} \\
& & 0_{N \times 4N+1} \\
& & \\
0_{N \times 2N+1} & E_1 BK_2 & E_1 BK_1 \\
& & 0_{7N+1 \times 4N+1} \\
& &
\end{bmatrix}.
$$

This latter condition gives the following theorem:

**Theorem 2** For given scalars $\tau_i$, $\tau_i^b$ and $\tau_i^f$ for $i = \{1, \dots, N\}$, if there exists a $N+1 \times N+1$ positive definite matrix $P$ and $N \times N$ diagonal positive matrices $Q_k^f$, $Q_k^b$, $Q_k$ with $k = \{0, 1\}$ and $K_1, K_2$ such that the inequality (17) is satisfied, then the system (6) is stable.

The state feedback gains $K_1$ and $K_2$ are thus derived solving the inequality (17) of
Theorem 2. Regarding the synthesis problem, since $K_1$ and $K_2$ are decision variables,
condition (17) is bilinear and a global optimal solution cannot be found. Nevertheless,
the feasibility problem can still be tested to provide a suboptimal solution:

▷ using a BMI solver as penbmi [23].

▷ using a relaxation algorithm [30]:

• step 0. Initialization: $K_1 = K_{1_0}$, $K_2 = K_{2_0}$.

• step 1. Run LMI computation (inequality (17) with fixed $K_1, K_2$) ⇒ backup
$P_0 = P$, $Q_{1_0} = Q_1$, $Q_{1_0}^f = Q_1^f$.

• step 2. Set $P = P_0$, $Q_1 = Q_{1_0}$, $Q_1^f = Q_{1_0}^f$ and $K_1, K_2$ are free, run LMI computation.

• step 3. If condition feasible: stop algorithm. Otherwise: return to step 0

It is worthy to note that the state feedback gains $K_1$ and $K_2$ is easily and routinely derived solving the matrix inequality (17) while many AQM such RED are well known to be difficult to tune as it has been stated in [10], [6].

4 NS-2 SIMULATIONS

In this section, we perform simulations with the network simulator NS-2 [11] (release
2.30) to validate the exposed theory. Throughout this part, the efficiency of the pro-
posed mechanism is evaluated and compared to few existing AQM. Consider the nu-
merical example of the Figure 6. So, the objective is to regulate the queue length of
the router to a desired level $b_0 = 100$ packets while the maximal buffer size is set to
400 packets. Propagation times are as illustrated on Figure 6. The link bandwidth is
fixed to 10Mbps, that is 2500 packet/s considering packet size of 500 bytes. Hence,
at the equilibrium the queueing delay is equal to 40ms. Each of the three sources uses
TCP/Reno and establishes 10 connections generating long lived TCP flows (like FTP
connections). Upon these latter specifications, the equilibrium point (3) is derived:
$b_0 = 100$ pkt, $\tau_{10} = 150$ ms, $\tau_{20} = 250$ ms, $\tau_{30} = 350$ ms, $x_{10} = x_{20} = x_{30} = 83.33$ pkt/s
 rate for each connections of the three sources) and $p_0 = 10^{-3}$ [9.508 3.444 1.760]'.

**Remark 2** It is worthy to note that the second equation in (3) enables to choose arbi-
trarily the rate assigned to each sources. This latter option allows us to make a service
differentiation between senders. In the previous example, we choose to assign the same
sending rate for all sources (and for each connections) ensuring then fairness.
<figure><img src="image_7.png" /><figcaption>Figure 6: Network topology: an example</figcaption></figure>

The interconnected system of the form (6) modeling a such network configuration is then written as

$$ 
\begin{bmatrix} \delta \dot{x}_1(t) \\ \delta \dot{x}_2(t) \\ \delta \dot{x}_3(t) \\ \dot{b}(t) \end{bmatrix} = \begin{bmatrix} -2.02 & 0 & 0 & -0.22 \\ 0 & -0.75 & 0 & -0.05 \\ 0 & 0 & -3.88 & -0.01 \\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} \delta x_1(t) \\ \delta x_2(t) \\ \delta x_3(t) \\ \delta b(t) \end{bmatrix} \\ 
+ \begin{bmatrix} -2.22 & -2.22 & -2.22 & 0 \\ -1.33 & -1.33 & -1.33 & 0 \\ -0.95 & -0.95 & -0.95 & 0 \\ 20 & 20 & 20 & 0 \end{bmatrix} \begin{bmatrix} \delta x_1(t-0.025) \\ \delta x_2(t-0.05) \\ \delta x_3(t-0.075) \\ \delta b(t) \end{bmatrix} \\ 
+ \begin{bmatrix} -912 & 0 & 0 \\ 0 & -884 & 0 \\ 0 & 0 & -876 \\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} \delta x_1(t-0.15) \\ \delta x_2(t-0.25) \\ \delta x_3(t-0.35) \end{bmatrix} \\ 
+ K_2 \begin{bmatrix} \delta b(t-0.125) \\ \delta b(t-0.2) \\ \delta b(t-0.275) \end{bmatrix} 
\begin{pmatrix} K_1 \\ K_2 \end{pmatrix} 
\begin{bmatrix} \delta x_1(t) \\ \delta x_2(t) \\ \delta x_3(t) \\ \delta b(t) \end{bmatrix} 
\end{aligned} 
\quad (19) 
$$

Then, we have to find matrices $K_1$ and $K_2$ such that the feedback system (19) is stable and the regulation around the equilibrium point is ensured. Applying Theorem 2 exposed in section 3, two stabilizing matrix gains

$$ K_1 = 10^{-3} \begin{bmatrix} -0.09 & 0 & 0 \\ 0 & 0.61 & 0 \\ 0 & 0 & 0.76 \end{bmatrix}, \quad K_2 = 10^{-3} \begin{bmatrix} 0.27 & 0 & 0 \\ 0 & 0.13 & 0 \\ 0 & 0 & 0.08 \end{bmatrix} \quad (20) $$

can be found. Considering the network of Figure 6, we have simulated the congestion phenomenon at a router applying the drop tail mechanism and different AQM. Effect of these latter dropping strategies on the queue length have been evaluated and are illustrated on Figure 7. Table 2 presents additional characteristics of the results. As expected, the drop tail mechanism maintains the queue size close to the buffer overflow (maximal buffer size: 400 *pkt* ) involving many uncontrolled dropped packets. Furthermore, a such large queue size implies a large queueing delay and also large oscillations providing an important delay jitter (see Table 2).

In order to maintain a controlled (and desired) queueing delay with a low jitter, the queue length at the router should be regulated. This issue is tackled with the use of AQM (adjustments of the different setting parameters are shown in table 1). On Figure
<table><caption>Table 1: Adjustment of parameter setting of each AQM</caption><tr><td>RED</td><td>min<sub>th</sub>=50,max<sub>th</sub>=300,w<sub>Q</sub>=5.99e-06,max<sub>p</sub>=0.1,f<sub>s</sub>=160Hz</td></tr><tr><td>REM</td><td>γ=0.003, Φ=1.001,q<sub>ref</sub>=100pkt</td></tr><tr><td>PI</td><td>a=1.483e-05,b=1.479e-05,q<sub>ref</sub>=100pkt,f<sub>s</sub>=160Hz</td></tr><tr><td>SF</td><td>gains K<sub>1</sub> and K<sub>2</sub> (20), equilibrium point (3)</td></tr></table>

7, control performances of AQM can be measured by two observations: the transient performance (in particular the speed of response) and the steady state error control. It can be observed that the state feedback (SF) (20) ensures an efficient control since the queue length matches its equilibrium faster than other cases. Secondly, SF provides a better regulation causing less oscillations and good precision. These characteristics can be verified in Table 2 which analyses each response from Figure 7. In the simulation, AQM was designed to regulate queue size at 100 pkt (equilibrium) avoiding severe congestion and ensuring then a stable queueing delay of 40 ms. First, in Table 2, the mean (and average queueing delay since the queueing delay is expressed by $b(t)/C$) shows the accuracy of each AQM according the desired prescribed queue length. Next, the standard deviation (and average delay jitter) shows the ability of each AQM to maintain the queue length (and queueing delay) close to the desired equilibrium providing then an efficient regulation. Note that REM has the lowest queueing delay, however the objective is to guarantee the queue length stability inducing then a queueing delay equals to 40 ms. If a lower queueing delay is required, one just has to change the equilibrium point (reducing the desired queue length).

Besides, the stability of the congestion phenomenon keeping a stable queue length (and thus a stable queueing delay), allows to control the RTT ($\tau_i$ for $i = \{1, ..., N\}$) for all sources to a desired value with low variations (see Figure 8). Thanks to the efficient regulation applied by SF, a QoS in terms of RTT and delay jitter is hence guaranteed. It provides thus an interesting feature which is relevant for streaming and real-time applications. Although RED performs a good regulation on the queue length and the RTT at the steady state, its response time is very slow which makes RED inefficient against short-lived traffic perturbations [1].

Table 3 presents statistics related to the packet arrival rates of each user when different AQM are implemented at the router and bears out the accuracy and the control efficiency of the proposed SF. The prescribed equilibrium rate for each connection (according to (3)) that establishes fairness is $x_{10} = x_{20} = x_{30} = 83.33 pkt/s$. As it can be seen, only SF is able to keep arrival rates comparatively close to the equilibrium value. Furthermore, based on the Jain's fairness index $\frac{(\sum x_i)^2}{n(\sum x_i^2)}$ [19] (the more the index is close to 1, the more the distribution of the resources is fair), we observe that SF applies a fair strategy.

# 5 CONCLUSION

In this paper the design of an AQM for congestion control of a single router has been presented. The considered topology consists in several TCP sources sending long-lived flows through a router to their respective receivers. To supply the TCP congestion control mechanism, an AQM must be implemented to the router. Based on a modified mathematical model of the protocol behavior, a such AQM has been developed with control theory tools. Indeed, in a time delay system framework, a control law has been
<figure><img src="image_8.png" /><figcaption>Figure 7: Evolution of the queue length b(t) (pkt): the desired size is 100pkts</figcaption></figure>

<table><caption>Table 2: Some statistics on the queue length for different AQM</caption><thead><tr><th></th><th>DT</th><th>RED</th><th>REM</th><th>PI</th><th>SF</th></tr></thead><tbody><tr><td>Mean pkt)</td><td>317.6</td><td>103.8</td><td>94.8</td><td>99.4</td><td>102.3</td></tr><tr><td>Stand.dev.(pkt)</td><td>84</td><td>21.7</td><td>70.7</td><td>35.1</td><td>23.3</td></tr><tr><td>Average<br>queueing delay(ms)</td><td>127</td><td>41.5</td><td>37.9</td><td>39.8</td><td>40.9</td></tr><tr><td>Average<br>delay jitter(ms)</td><td>33.6</td><td>8.7</td><td>28.3</td><td>14</td><td>9.3</td></tr></tbody></table>

<table><caption>Table 3: Some statistics on arrival rates for different AQM</caption><thead><tr><th></th><th colspan="3">RED</th><th colspan="3">REM</th><th colspan="3">PI</th><th colspan="3">SF</th></tr></thead><tbody><tr><td>users</td><td>1</td><td>2</td><td>3</td><td>1</td><td>2</td><td>3</td><td>1</td><td>2</td><td>3</td><td>1</td><td>2</td><td>3</td></tr><tr><td>Mean (pkt/s)</td><td>147</td><td>83</td><td>148</td><td>147</td><td>81</td><td>60</td><td>146</td><td>88</td><td>109</td><td>104</td><td>91</td><td>88</td></tr><tr><td>Stand. dev. (pkt/s)</td><td>61</td><td>36</td><td>372</td><td>56</td><td>34</td><td>23</td><td>66</td><td>35</td><td>335</td><td>41</td><td>30</td><td>40</td></tr><tr><td>Jain's fairness index</td><td colspan="3">0.9450</td><td colspan="3">0.8703</td><td colspan="3">0.9579</td><td colspan="3">0.9946</td></tr></tbody></table>
<figure><img src="image_9.png" /><figcaption>Figure 8: Evolution of the RTT of connections from source 3 (ms): the expected value is 350ms</figcaption></figure>
proposed and then the stability analysis of the feedback system has been performed. Consequently, the regulation of flows and the queue size of at the router is ensured. At last, a numerical example and simulations have shown the effectiveness of the proposed methodology.

## References

[1] Y. Ariba, Y. Labit, and F. Gouaisbaut. Design and performance evaluation of a state-space based aqm. In *IARIA International Conference on Communication Theory, Reliability, and Quality of Service*, pages 89–94, July 2008.

[2] S. Athuraliya, D. Lapsley, and S. Low. An enhanced random early marking algorithm for internet flow control. In *IEEE INFOCOM*, pages 1425–1434, December 2000.

[3] J. Aweya, M. Ouellette, and D. Y. Montuno. A simple mechanism for stabilizing network queues in tcp/ip networks. *Int. Journal of Network Management*, 17:275–286, 2007.

[4] P. Barford and D. Plonka. Characteristics of network traffic flow anomalies. In *In Proceedings of the ACM SIGCOMM Internet Measurement Workshop*, November 2001.

[5] S. Bhandarkar, A. L. Narasimha Reddy, Y. Zhang, and D. Loguinov. Emulating aqm from end hosts. In *ACM SIGCOMM '07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications*, pages 349–360, 2007.

[6] T. Bonald, M. May, and J.-C. Bolot. Analytic evaluation of red performance. In *IEEE INFOCOM*, volume 3, pages 1415–1424, March 2000.

[7] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan. *Linear Matrix Inequalities in System and Control Theory*. SIAM, Philadelphia, USA, 1994. in Studies in Applied Mathematics, vol.15.

[8] B. Braden, D. Clark, and J. Crowcroft. Recommendations on queue management and congestion avoidance in the internet. RFC 2309, April 1998.

[9] C.K. Chen, Y.C. Hung, T.L. Liao, and J.J. Yan. Design of robust active queue management controllers for a class of tcp communication networks. *Information Sciences.*, 177(19):4059–4071, 2007.

[10] M. Christiansen, K. Jeffay, D. Ott, and F. Smith. Tuning red for web traffic. In *ACM/SIGCOM*, pages 139–150, 2000.

[11] K. Fall and K. Varadhan. The ns manual. notes and documentation on the software ns2-simulator, 2002. URL: www.isi.edu/nsnam/ns/.

[12] Y. Fan, F Ren, and C. Lin. Design a pid controller for active queue management. In *IEEE International Symposium on Computers and Communication (ISCC)*, volume 2, pages 985–990, 2003.

[13] V. Firoiu and M. Borden. A study of active queue management for congestion control. In *IEEE INFOCOM*, volume 3, pages 1435 – 1444, March 2000.
[14] S. Floyd and V. Jacobson. Random early detection gateways for congestion avoidance. *IEEE/ACM Transactions on Networking*, 1:397–413, August 1993.

[15] F. Gouaisbaut and D. Peaucelle. A note on stability of time delay systems. In *5th IFAC Symposium on Robust Control Design (ROCOND'06)*, Toulouse, France, July 2006.

[16] H. Han, C. V. Hollot, Y. Chait, and V. Misra. Tcp networks stabilized by buffer-based aqms. In *IEEE INFOCOM*, pages 964–974, March 2004.

[17] C. V. Hollot, V. Misra, D Towsley, and W. Gong. Analysis and design of controllers for aqm routers supporting tcp flows. *IEEE Trans. on Automat. Control*, 47:945–959, June 2002.

[18] V. Jacobson. Congestion avoidance and control. In *ACM SIGCOMM*, pages 314–329, Stanford, CA, August 1988.

[19] R. Jain, D. Chiu, and W. Hawe. A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. Technical Report TR301, Digital Equipment Corp, 1984.

[20] F. P. Kelly, A. Maulloo, and D. Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. *Journal of the Operational Research Society*, 49:237–252, March 1998.

[21] K. B. Kim. Design of feedback controls supporting tcp based on the state space approach. In *IEEE Trans. on Automat. Control*, volume 51 (7), July 2006.

[22] Seong Soo Kim and A. L. Narasimha Reddy. Netviewer: a network traffic visualization and analysis tool. In *LISA'05: Proceedings of the 19th conference on Large Installation System Administration Conference*, pages 185–196. USENIX Association, 2005.

[23] M. Kocvara and M. Stingl. bilinear matrix inequalities: Penbmi. PENOPT GbR, http://www.penopt.com/.

[24] S. Kunniyur and R. Srikant. Analysis and design of an adaptive virtual queue (avq) algorithm for active queue management. In *ACM SIGCOMM*, pages 123–134, San Diego, CA, USA, aug 2001.

[25] Y. Labit, Y Ariba, and F. Gouaisbaut. On designing lyapunov-krasovskii based controllers for aqm routers supporting tcp flows. In *46th IEEE Conference on Decision and Control*, pages 3818–3823, New Orleans, USA, December 2007.

[26] L. Le, J. Aikat, K. Jeffay, and F. Donelson Smith. The effects of active queue management on web performance. In *ACM SIGCOMM*, pages 265–276, August 2003.

[27] H. S. Low, F. Paganini, and J.C. Doyle. *Internet Congestion Control*, volume 22, pages 28–43. IEEE Control Systems Magazine, Feb 2002.

[28] S. Manfredi, M. di Bernardo, and F. Garofalo. Robust output feedback active queue management control in tcp networks. In *IEEE Conference on Decision and Control*, pages 1004–1009, December 2004.
[29] V. Misra, W. Gong, and D Towsley. Fluid-based analysis of a network of aqm routers supporting tcp flows with an application to red. In *ACM SIGCOMM*, pages 151–160, August 2000.

[30] S.I. Niculescu. *Delay Effects on Stability. A Robust Control Approach*, volume 269 of *Lecture Notes in Control and Information Sciences*. Springer-Verlag, Heidelberg, 2001.

[31] A. Papachristodoulou. Global stability of a tcp/aqm protocol for arbitrary networks with delay. In *IEEE CDC 2004*, pages 1029–1034, December 2004.

[32] D. Peaucelle, D. Arzelier, D. Henrion, and F. Gouaisbaut. Quadratic separation for feedback connection of an uncertain matrix and an implicit linear transformation. *Automatica*, 43(5):795–804, 2007.

[33] P. F. Quet and H. Özbay. On the design of aqm supporting tcp flows using robust control theory. *IEEE Trans. on Automat. Control*, 49:1031–1036, June 2004.

[34] K. K. Ramakrishnan and S. Floyd. A proposal to add explicit congestion notification (ecn) to ip. RFC 2481, January 1999.

[35] S. Ryu, C. Rump, and C. Qiao. Advances in active queue management (aqm) based tcp congestion control. *Telecommunication Systems*, 4:317–351, 2004.

[36] R. Srikant. *The Mathematics of Internet Congestion Control*. Birkhauser, 2004.

[37] D. Wang and C. V. Hollot. Robust analysis and design of controllers for a single tcp flow. In *IEEE International Conference on Communication Technology (ICCT)*, volume 1, pages 276–280, April 2003.