3.5 The Averaging Principle (AP)

The discussion in Section 3.4 showed that to improve stability for the congestion control algorithm, the network needs to provide information about both the deviation from a target buffer occupancy and the derivative of the deviation. This puts the burden of additional complexity on the network nodes. In practice, this is more difficult to implement than when compared with adding additional functionality to the end systems instead. In this section, we will describe an ingenious way the source algorithm can be modified without touching the nodes, which has the same effect as using a PI-type AQM controller. This is done by applying the so-called Averaging Principle (AP) to the source congestion control rules [16].

The AP is illustrated in Figure 3.14. It shows a congestion control algorithm, in which the rate reacts to two factors:

$R_C\leftarrow \frac{R_C+R_T}{2}$

It can be shown that there exists an AQM controller of the type that was derived in Section 3.4, given by (see Figure 3.15)

$P(k)=0.5K{b}_{\delta }(k)+0.25K(b_{\delta }(k)-b_{\delta }(k-1))+P(k-1)$ (90)

(90)

such that the AP controller is exactly equivalent to this controller.

To prove this, consider the following two controllers shown in Figures 3.16 and 3.17. Both controllers map a sequence of sampled queue error samples $b_{\delta }(n)$ to an input signal P(n) that drives the congestion control rate determination function. Controller 1 is an AP controller, and the upper branch of controller 2 is the AQM controller from Figure 3.17. In the following, we will show that P(n)=U(n) and that the lower branch of controller 2 can be ignored, so that $P(n)\approx U_1(n)$.

The following equations describe the input-out relations for the two controllers.

Controller 1 (AP controller):

$P_1(n)=P_2(n-1)+K{b}_{\delta }(n)$ (91)

(91)

$P_2(n)=\frac{P_1(n)+P_2(n-1)}{2}$ (92)

(92)

$P(n)=\{\begin{array}{lll}{P}_1(n)\hfill & if\hfill & nS\le t<nS+\frac{S}{2}\hfill \\ P_2(n)\hfill & if\hfill & nS+\frac{S}{2}\le t<nS+S\hfill \end{array}$ (93)

(93)

Controller 2 (approximate PD controller):

$U_1(n)=U_1(n-1)+KQ(n)$ (94)

(94)

$Q(n)=0.5b_{\delta }(n)+0.25(b_{\delta }(n)-b_{\delta }(n-1))$ (95)

(95)

$U_2(n)=\{\begin{array}{ll}\frac{K}{4}{b}_{\delta }(n)\hfill & nS\le t<nS+\frac{S}{2}\hfill \\ -\frac{K}{4}{b}_{\delta }(n)\hfill & nS+\frac{S}{2}\le t<nS+S\hfill \end{array}$ (96)

(96)

$U(n)=U_1(n)+U_2(n)$ (97)

(97)

Define

$P_m(n)=\frac{P_1(n)+P_2(n)}{2}$ (98)

(98)

From equations 91 and 92, it follows that

$\begin{array}{ll}{P}_m(n)\hfill & =\frac{P_2(n-1)+K{b}_{\delta }(n)}{2}+\frac{P_1(n)+P_2(n-1)}{4}\hfill \\ \hfill & =\frac{P_2(n-1)}{2}+\frac{K{b}_{\delta }(n)}{2}+\frac{P_2(n-1)}{4}+\frac{K{b}_{\delta }(n)}{4}+\frac{P_2(n-1)}{4}\hfill \\ \hfill & =P_2(n-1)+\frac{3K}{4}{b}_{\delta }(n)\hfill \end{array}$ (99)

(99)

We now show that

$P_1(n)=P_m(n)+\frac{K}{4}{b}_{\delta }(n),\mathrm{and}$ (100)

(100)

$P_2(n)=P_m(n)-\frac{K}{4}{b}_{\delta }(n)$ (101)

(101)

To prove equation 100, note that from equations 99 and 91, it follows that

$P_m(n)=P_1(n)-K{b}_{\delta }(n)+\frac{3K}{4}{b}_{\delta }(n)=P_1(n)-\frac{K{b}_{\delta }(n)}{4}.$

To prove equation 101, first note from equations 99 and 92 that

$\begin{array}{ll}{P}_m(n)\hfill & =2P_2(n)-P_1(n)+\frac{3K}{4}{b}_{\delta }(n)\hfill \\ \hfill & =2P_2(n)-(2P_m(n)-P_2(n))+\frac{3K}{4}{b}_{\delta }(n)\hfill \\ \hfill & =3P_2(n)-2P_m(n)+\frac{3K}{4}{b}_{\delta }(n)\hfill \end{array}$

Comparing equations 100 and 101 with equations 96 and 97, it follows that if we can show U₁(n)=P_m(n), then it follows that U(n)=P(n), and the two controllers will be equivalent. This can be done by showing that U₁(n) and P_m(n) satisfy the same recursions.

From equations 99, 101, and 95, it follows that

$\begin{array}{ll}{P}_m(n)\hfill & =P_m(n-1)-\frac{K{b}_{\delta }(n-1)}{4}+\frac{3K}{4}{b}_{\delta }(n)\hfill \\ \hfill & =P_m(n-1)+KQ(n)\hfill \end{array}$ (102)

(102)

Comparing equations 102 and 94, it follows that P_m(n)=U₁(n) for all n, and as a consequence we get P(n)=U(n) (i.e., the two controllers are equivalent). Because the contribution of U₂(n) can be ignored [16], it follows that $P(n)\approx U_1(n)$, and the AQM and AP controllers are almost identical.

We will encounter congestion control protocols such a TCP BIC later in the book (see Chapter 5) that are able to operate in a stable manner in very high-speed networks even with traditional AQM schemes. These protocols may owe their stability to the fact that their rate control rules incorporate averaging of the type discussed here.

3.6 Implications for Congestion Control Algorithms

From the analysis in the previous few sections, a few broad themes emerge that have influenced the design of congestion control algorithms in recent years:

• AQM schemes that incorporate the first or higher derivatives of the buffer occupancy process lead to more stable and responsive systems. This was shown to be the case in the analysis of the PI controller. Also, because the first derivative of the buffer occupancy process can be written as

$\frac{db(t)}{dt}=C-\sum _i{R}_i$

it also follows that knowing the derivative is equivalent to knowing how close the queue is to its saturation point C. Some protocols such as QCN (see Chapter 8) feed back the value of db/dt directly, and others such as XCP and RCP (see Chapter 5) feed back the rate difference in the RHS of the equation.

• If the network cannot accommodate sophisticated AQM algorithms (which is the case for TCP/IP networks), then an AP-based algorithm can have an equivalent effect on system stability and performance as the derivative-based feedback. Examples of algorithms that have taken this route include the BIC and CUBIC algorithms (see Chapter 5) and QCN (see Chapter 8).

3.7 Further Reading

Instead of taking the dual approach to solving equations 7 and 8 it is possible to solve the primal problem directly by eliminating the rate constraint condition (equation 8) and modifying the objective function as follows [9]:

$U(r_1,\dots ,r_N)=\sum _{i=1}^N{U}_i(r_i)-\sum _{l=1}^L\underset{0}{\overset{Y_l(t)}{\int }}{f}_l(y)dy$ (103)

(103)

where U_i(r_i) are strictly concave functions and the increasing, continuous function f_l is interpreted as a congestion price function at link l and the convex function ${\int }_0^{Y_l(t)}{f}_l(y)dy$ is known as the barrier function. To impose the constraint that the sum of the data rates at a link should be less than the link capacity, the barrier function can be chosen in a way such that it increases to infinity when the arrival rate approaches the link capacity.

It follows that U(r₁,…,r_N) is a strictly concave function and it can be shown that the problem

$\underset{r_i\ge 0}{\max }U(r_1,\mathrm{..}.,r_N)$ (104)

(104)

decomposes into N separate optimization subproblems that can be solved independently at each of the sources. The solution to the optimization problem at each source node is given by

${U\prime }_i(r_i)=\sum _{l:l\in A_i}{f}_l\left(\sum _{s:s\in B_l}{r}_s\right)$ (105)

(105)

where A_i is the set of nodes that connection i passes through and B_l is the set of connections that pass through node l. This can be interpreted as a congestion feedback of $f_l\left(\sum _s{r}_s\right)$ back to the source from each of the nodes that the connection passes through, and is the equivalent of equation 11 for the dual problem.

Just as we used the gradient projection method to obtain an iterative solution to the dual problem (equation 13), we can also apply this technique to iteratively solve the primal problem, leading to the following expression for the optimal rates:

$\frac{d{r}_i}{dt}=k_i(r_i)\left({U\prime }_i(r_i)-\sum _{l:l\in A_l}{f}_l\left(\sum _{s:s\in B_l}{r}_s\right)\right)$ (106)

(106)

where k_r is any nondecreasing continuous function such that k_r(x)>0 for x>0. If k_r>0, then in equilibrium setting, dr_i/dt=0 leads back to equation 105. Equation 106 is known as the primal algorithm for the congestion control problem. For example, equation 33 for TCP Reno for small values of Q_i can be put in the form

$\frac{d{R}_i(t)}{dt}=\frac{2R_i^2(t)}{3}\left(\frac{3}{2T_i^2{R}_i^2(t)}-Q_i\right)$

which is in the form (106) with

$\begin{array}{ccc}{k}_i(r_i)=\frac{2r_i^2(t)}{3}& \mathrm{and}& {U\prime }_i\end{array}(r_i)=\frac{3}{2T_i^2{r}_i^2(t)}$ (107)

(107)

Equation 38 for the utility function can then be obtained using equation 107.

A very good description of the field of optimization and control theory applied to congestion control is given in Srikant’s book [9]. It has a detailed discussion of the barrier function approach to system optimization, as well as several examples of the application of the Nyquist criterion to various types of congestion control algorithms.

For cases when the system equilibrium point falls on a point on nonlinearity, the linearization technique is no longer applicable. In this case, techniques such as Lyapunov’s second theorem have been applied to study system stability.

Appendix 3.A Linearization of the Fluid Flow Model

The right-hand sides of the fluid flow model for TCP congestion control that analyzed Section 3.4 are as follows:

$\begin{array}{l}f(W,W_R,b,p)=\frac{1}{T(t)}-\frac{W(t)W^R(t)}{2T(t)}p(t-T(t))\hfill \\ g(W,b)=\frac{W(t)}{T(t)}N(t)-C\hfill \end{array}$ (A1)

(A1)

where $T(t)=\frac{b(t)}{C}+D$, W_R(t)=W(t−T(t)) and T_R(t)=T(t−T(t)).

We wish to linearize these equations about their equilibrium points

$W_0^2{P}_0=2\mathrm{and}{W}_0=\frac{C{T}_0}{N}.$

This can be done using the perturbation formula

$f_{\delta }(t)=\frac{\partial f}{\partial W}{W}_{\delta }+\frac{\partial f}{\partial W^R}{W}_{\delta }^R+\frac{\partial f}{\partial b}{b}_{\delta }+\frac{\partial f}{\partial p}{p}_{\delta }\mathrm{and}$ (A2)

(A2)

$g_{\delta }(t)=\frac{\partial g}{\partial b}{b}_{\delta }+\frac{\partial g}{\partial W}{W}_{\delta }.$ (A3)

(A3)

By using straightforward differentiation, it can be shown that

$\begin{array}{l}\frac{\partial f}{\partial W}=\frac{\partial f}{\partial W_R}=-\frac{N}{C{T}_0^2}\hfill \\ \frac{\partial f}{\partial b}=0\hfill \\ \frac{\partial f}{\partial p}=\frac{C^2{T}_0}{2N^2}\hfill \\ \frac{\partial g}{\partial b}=-\frac{1}{T_0}\hfill \\ \frac{\partial g}{\partial W}=\frac{N}{T_0}\hfill \end{array}$ (A4)

(A4)

Substituting equation A4 back into equations A2 and A3 and then into the original differential equation, we obtain the linearized equations

$\begin{array}{l}\frac{d{W}_{\delta }(t)}{dt}=-\frac{2N}{C{T}_0^2}{W}_{\delta }(t)-\frac{C^2{T}_0}{2N^2}{P}_{\delta }(t-T_0)\hfill \\ \frac{d{b}_{\delta }(t)}{dt}=\frac{N}{T_0}{W}_{\delta }(t)-\frac{1}{T_0}{b}_{\delta }(t)\hfill \end{array}$ (A5)

(A5)

Appendix 3.B The Nyquist Stability Criterion

The Nyquist criterion is used to study the stability of systems that can modeled by linear differential equations in the presence of a feedback loop. In Figure 3.B1, G(s) is the Laplace transform of the system being controlled, and H(s) is the Laplace transform of the feedback function. It can be easily shown that the end-to-end transform for this system is given by

$L(s)=\frac{Y(s)}{U(s)}=\frac{G(s)}{1+G(s)H(s)}$ (B1)

(B1)

To ensure stability, all the roots of the equation 1+G(s)H(s)=0, which in general are complex numbers, have to lie in the left half of the complex plane. The Nyquist criterion is a technique for verifying this condition that is often easier to apply than finding the roots, and it also provides additional insights into the problem.

Nyquist criterion: Let C be a close contour that encircles the right half of the complex plane, such that no poles or zeroes of H(s)G(s) lie on C. Let Z and P denote the number of poles and zeroes, respectively, of H(s)G(s) that lie inside C. Then the number of times M that $H(j\omega )G(j\omega )$ encircles the point (−1,0) in the clockwise direction, as $\omega$ is varied from $-\infty to+\infty$, is equal to Z – P.

Note that the contour C in the procedure described above is chosen so that it encompasses the right half of the complex plane. As $\omega$ is varied from $-\infty to+\infty$, the function $H(j\omega )G(j\omega )$ maps these points to the target complex plane, where it describes a curve. For the system to be stable, we require that Z=0, and because M=Z – P, it follows that:

Figure 3.B2 shows an example of the application of the Nyquist criterion to the function $G(j\omega )$ along with some important features. Note that curve for $G(j\omega )$ goes to $-\infty$ as $\omega \to 0$, and approaches 0 as $\omega \to 0$. We will use the notation $G(j\omega )=|G(j\omega )|e^{-j\text{arg}(G(j\omega ))}$, where $|G(j\omega )|$ is the length of the line going from the origin to $G(j\omega )$ and $\text{arg}(G(j\omega ))$ is the angle that this line makes with the real axis. Note the following features in the graph:

• The point (−a, 0) where the $G(j\omega )$ curve intersects with the real axis is called the phase crossover point because at this point $\text{arg}(G(j\omega ))=\pi$. The gain margin (GM) of the system is defined by the distance between the phase crossover point and the (−1, 0), i.e.,

$GM=1-a$ (B2)

(B2)

• As the Gain Margin decreases, the system tends towards instability.

• The point where the $G(j\omega )$ curve intersects with the unit circle is called the gain crossover point because at this point $|G(j\omega )|=1$. The phase margin (PM) of the system is defined by the angle between the crossover point and the negative real axis. Just as for the GM, a smaller PM means that the system is tending toward instability. Generally a PM of between 30 and 60 degrees is preferred.

In the applications of the Nyquist criterion in this book, we usually find a point ${\omega }_c$ such that $|G(j{\omega }_c)|\le 1$. This implies that the gain crossover point ${\omega }_{*}$ is such that $0\le {\omega }_{*}\le {\omega }_c$. Hence, if we can prove that $\text{arg}(G(j{\omega }_c))<\pi$, then the system will be stable.

Appendix 3.C Transfer Function for the RED Controller

In this appendix, we derive the expression for the transfer function of the RED controller [17], which is diagrammed in Figure 3.C1 and is given by

$V_{red}(s)=\frac{L_{red}}{\frac{s}{K}+1}\mathrm{where}$

$L_{red}=\frac{{\max }_p}{{\max }_{th}-{\min }_{th}}\mathrm{and}K=-\frac{\log (1-w_q)}{\delta }$

We start with the following equation that describes the operation of the queue averaging process

$x((k+1)\delta )=(1-w_q)x(k\delta )+w_{q}b(k\delta )$ (C1)

(C1)

where $b(k\delta )$ is instantaneous queue length at the sampling time $k\delta$ and $x(k\delta )$ is the average queue length at that time. Assume that this difference equation can be put in the form of the following differential equation

$\frac{dx}{dt}=Kx(t)+Lb(t)$

Then, in a sampled data system, x(t_k+1) can be written

$\begin{array}{ll}x(t_{k+1})\hfill & =e^{K(t_{k+1}-t_k)}x(t_k)+\underset{t_k}{\overset{t_{k+1}}{\int }}{e}^{K(t_{k+1}-\tau )}Lb(t_k)d\tau \hfill \\ \hfill & =e^{K\delta }x(t_k)-(1-e^{K\delta })\frac{Lb(t_k)}{K}\hfill \end{array}$ (C2)

(C2)

Comparing (C1) with (C2), it follows that L=−K and

$1-w_q=e^{K\delta }\mathrm{so}\mathrm{that}$

$K=\frac{{\log }_e(1-w_q)}{\delta }$

Hence, the differential equation for the averaging process is given by $\frac{dx}{dt}=Kx(t)-Kb(t)$, which in the transform space translates into

$\frac{X(s)}{b(s)}=\frac{K}{s+K}$

This signal is further passed through the thresholding process as shown in Figure 3.B1 before yielding the final output that is fed back to the source.

Note that K determines the responsiveness of the filter so higher the value of K, the faster it will respond to sudden change. However, too high a value for K will result in the situation in which the filter starts tracking the instantaneous value of the buffer size, resulting in continuous oscillations.

Appendix 3.D Convex Optimization Theory

Definition 1

A set C is said to be convex if the following property holds:

$ax+(1-a)y\in C,\forall x,y\in C,\alpha \in (0,1]$ (D1)

(D1)

Definition 2

Define the function $f:C\to R^n$, where $C\in R^n$ is a convex set. The function is said to be convex if

$f(ax+(1-a)y)\le af(x)+(1-a)f(y)\forall x,y\in C,\forall a\in [0,1].$ (D2a)

(D2a)

The function is said to be concave if

$f(ax+(1-a)y)\ge af(x)+(1-a)f(y)\forall x,y\in C,\forall a\in [0,1].$ (D2b)

(D2b)

The function is said to be strictly convex (concave) if the above inequalities are strict when $x\ne yanda\in (0,1]$.

Consider the following optimization problem:

$\underset{x}{\max }f(x)$ (D3a)

(D3a)

subject to

$\begin{array}{l}Px\le b\hfill \\ Qx=0\hfill \end{array}$ (D3b)

(D3b)

where f(x) is a differentiable concave function and P and Q are matrices. The values of x that satisfy the constraints (D3b) form a convex set.

The Lagrangian function L for this problem is defined by

$L(x,\lambda ,\mu )=f(x)-{\lambda }^T(Px-c)-{\mu }^{T}Qx$ (D4)

(D4)

where $\lambda \ge 0,\mu$ are called the dual variables or the Lagrangian multipliers for this problem.

Karush-Kuhn-Tucker theorem: x is a solution to the optimization problem (D3a–b) if and only if it satisfies the following conditions:

$\begin{array}{l}\mathrm{\Delta }f(x)-P^T\lambda -Q^T\mu =0\hfill \\ {\lambda }^T(Px-b)=0\hfill \\ Px\le b\hfill \\ Qx=0\hfill \\ \lambda \ge 0\hfill \end{array}$ (D5)

(D5)

Definition 3

Define the dual function $D(\lambda ,\mu )$ by

$D(\lambda ,\mu )=\underset{x\in C}{\max }L(x,\lambda ,\mu )$ (D6)

(D6)

where C is the set of all x that satisfy the constraints (D3b).

Strong Duality Theorem: Let $\hat{x}$ be the point that solves the constrained optimization problem (equations D3a and D3b). If the Slater constraint qualification conditions are satisfied, then

$\underset{\lambda \ge 0,\mu }{\inf }D(\lambda ,\mu )=f(\hat{x})$ (D7)

(D7)

Appendix 3.E A General Class of Utility Functions

Consider a network with K connections and define the following utility function for connection k [10], given by

$U_k(r_k)=w_k\frac{r^{1-{\alpha }_k}}{1-{\alpha }_k}\mathrm{k}=1,\dots ,\mathrm{K}$ (E1)

(E1)

for some ${\alpha }_k>0$, where r is the steady state throughput for connection k. Note that the parameters ${\alpha }_k$ controls the trade-off between fairness and efficiency. Consider the following special cases for $1\le k\le K$:

${\alpha }_k=0:U_k(r_k)=w_k{r}_k$ (E2)

(E2)

This utility function assigns no value to fairness and simply measures total throughput.

${\alpha }_k=1:U_k(r_k)=\underset{{\alpha }_k\to 1}{\lim }{w}_k\frac{r^{1-{\alpha }_k}}{1-{\alpha }_k}=w_k\log r_k$ (E3)

(E3)

This network resource allocation that minimizes this utility function is known as weighted proportionally fair. The logarithmic factor means that an algorithm that minimizes this function will cut down one user’s allocation by half as long as it can increase another user’s allocation by more than half. The TCP Vegas algorithm has been shown to minimize this utility function.

${\alpha }_k=2:U_k(r_k)=\frac{w_k}{r_k}$ (E4)

(E4)

The network resource allocation corresponding to this utility function is called weighted minimal potential delay fair, and as shown in this chapter, this is function TCP Reno minimizes. This metric seeks to minimize the total time of fixed-length file transfers.

${\alpha }_k=\alpha ,w_k=1\forall k:U_k(r_k)=\underset{\alpha \to \infty }{\lim }\frac{r_k^{1-\alpha }}{1-\alpha }$ (E5)

(E5)

Minimizing this metric is equivalent to achieving max-min fairness in the network [9].