Graduate School of Engineering Science, Osaka University
Japan
Hiroyuki Ohsaki (oosaki@ics.es.osaka-u.ac.jp)
Graduate School of Engineering Science, Osaka University
Japan
Masayuki Murata (murata@ics.es.osaka-u.ac.jp)
Graduate School of Engineering Science, Osaka University
Japan
- Abstract
- 1 Introduction
- 2 Analytic Model
- 3 Stability Analysis
- 4 Numerical Examples
- 5 Simulation Results
- 6 Conclusion and Future Work
- References
Abstract:
1. Introduction
A feedback-based congestion control mechanism is essential to realize an efficient data transfer services in packed-switched networks. TCP (Transmission Control Protocol), a sort of feedback-based congestion control mechanisms, has been widely used in the current Internet. In this paper, we are devoted to studying the functionality of a congestion control mechanism of TCP, which controls a congestion level of the network by regulating a window size of a source host according to feedback information obtained from the network (via the receiver host).
Recently, another version of TCP called TCP Vegas has been proposed by Brakmo et al., which can achieve better performance than TCP Reno [1]. TCP Vegas has following advantages over existing TCP Reno: (1) a new time-out mechanism, (2) an improved congestion avoidance mechanism, and (3) a modified slow-start mechanism. In particular, the congestion avoidance mechanism of TCP Vegas controls the number of on-the-fly packets in the network. More specifically, TCP Vegas measures an RTT (Round Trip Time), which is elapsed time from a packet transmission to the receipt of its corresponding ACK (ACKnowledgment) packet. It then uses the measured RTT as feedback information from the network. Namely, if the measured RTT is getting large, the source host of TCP Vegas conjectures that the network is falling into congestion. Then, the window size is throttled. If measured RTTs become small, on the other hand, the source host recognizes that the network is relieved from the congestion, and increases the window size again. In TCP Vegas, it is not necessary for the source host to wait a packet loss in the network to detect congestion. This is an advantage of TCP Vegas over other versions of TCP. With this mechanism, the window size of a source host is expected to converge to a constant value in steady state. The simulation and experimental results show that the congestion control mechanism of TCP Vegas leads to 37-71 % higher throughput than that of TCP Reno [1].
Dynamics of TCP Vegas has been analytically investigated by several researchers [2,3,4]. In those papers, the evolution of a window size has been approximated by a fluid model, and the throughput of each connection has been obtained. However, the analytic model used in those papers has focused only on a single connection [2,3], or two connections [4]. Therefore, those results are not applicable to a real network. In addition, in the above papers, stability of TCP Vegas has not been investigated at all. Since TCP Vegas is essentially a feedback congestion control, a stable operation of the control mechanism is very important, but the approach based on the fluid model cannot examine such an aspect.
One exception can be found in [5], where the authors explicitly derive the stability condition and optimal setting of control parameters by applying the control theory. Control parameters for best transient performance can also be investigated by their approach. Further, the analytic model considered in [5] allows multiple TCP connections. However, the authors assume a single bottleneck link, and a more important shortcoming is an assumption on the propagation delays; all connections have identical propagation delays. Since in the real network, each connection usually has a different propagation delay, and the difference of feedback delays must affect the stability and performance of TCP connections.
As a next step for making the control theoretic approach to be useful for the network using the feedback-based congestion control (i.e., the Internet), we consider a network where each connection is allowed to have a different propagation delay by extending a previous work [5]. First, we derive fixed points of the window size and the number of the packets in the router's buffer in steady state. Based on these results, we then derive throughput of each connection in steady state, and show that the throughput of each connection become fair regardless of its propagation delay if we set a control parameter that controls the number of on-the-fly packets equally. We also derive the stability condition of the window-based flow control mechanism. Then, we quantitatively show how the stability region of control parameters is affected by network parameters such as the processing speed of the router and the propagation delay.
Analyses of feedback-based congestion control mechanisms using control theoretic approaches can be found in the literature. In particular, several papers including [6,7,8] have analyzed a feedback-based congestion control mechanism for the network model where each connection has a different propagation delay. The authors of these papers have focused on a rate-based congestion control mechanism in ATM networks, and have designed a rate controller based on the optimal control theory. However, their approaches are not applicable to the window-based flow control mechanism since the behaviors of a rate-based and a window-based congestion control mechanisms are essentially different.
Organization of this paper is as follows. In Section 2, we describe the window-based flow control mechanism based on the congestion avoidance mechanism of TCP Vegas, followed by introduction of its analytic model. In Section 3, stability analysis of the window-based flow control mechanism is performed by applying control theory. In Section 4, the effect of control parameters on system stability is investigated by illustrating several numerical examples. The numerical results presented in Section 4 are validated by using simulation experiments in Section 5. In Section 6, we conclude this paper and discuss future works.
2. Analytic Model
The analytic model used in this paper is illustrated in
Fig. 1. In this figure, several TCP connections
are established through a single bottleneck router. There are M
groups of connections where connections in each group are assumed to
have an identical propagation delay. Let 
be the propagation
delay of connections in group m
.
We assume
without loss of
generality. We introduce an irreducible positive integer 
as the ratio of propagation delay ,
such that
By assuming that the waiting time of a packet at the router's buffer
is negligible, the ratio of RTTs for connections in group m is
given by .
In TCP Vegas, a source host changes its window
size once per RTT [1]. Therefore, the system can be
represented by a discrete-time model where its time slot is
.
In other words, connections in group m
change their window sizes every slots.
Let Nm be the number of connections in group m, and wm,n(k) be the window size of the source host n
in group m at slot k. Namely, the source host
n in group m is allowed to send wm,n(k) packets during
its RTT. We assume that all source hosts always have enough data to
transmit so that every connection always sends the number wm,n(k)
of packets during its RTT. Further,
let q(k) be the number of packets in the router's buffer at slot
k, and L be the capacity of the router's buffer. The router is
assumed to process incoming packets according to
FIFO (First-In First-Out) discipline.
The processing speed of the router is denoted by B.
By assuming the packet size to be fixed, we
use the unit of ``packet'' for the window size wm,n(k) and the
capacity of the router's buffer L, and ``packet/ms'' for the
processing speed of the router B.
Since the window-based flow control mechanism allows the source host
to emit the number wm,n(k) of packets per RTT, a connection in
group m sends the number
of packets per
slot on the average. Therefore, the number of packets in the router's
buffer at slot k + 1 is given by the following equation
where
is the length of a single slot.
In TCP Vegas, the source host measures its RTT and changes its window
size based on the observed RTT. More
specifically, source host n in group m calculates
from its measured RTT rm(k). Note that rm(k) is dependent on the number of packets in the router's buffer, and given by the sum of the propagation delay and the waiting time at the router's buffer. That is,
The source host changes its window size once every RTT according to
dm,n(k). Namely, the window size
is
changed as
where
and 
are control parameters that
determine the number of on-the-fly packets in the router's buffer. In
this paper, we modify Eq. (2) as
where
is a control parameter that determines the amount
of the window size change. The purpose of introducing
is not only for enabling application of a control theory, but also for
improving transient performance [9].
In [10], it has been reported that fairness
among connections cannot be satisfied when dm,n(k) lies in
[,
]. In our analytic model, we therefore
unify both
and
in
Eq. (2) into a single one,
,
as in
Eq. (3). With this modification, fairness among connections
can be improved [10]. Intuitively,
controls the number of on-the-fly packets in the network for each
connection.
3. Stability Analysis
In what follows, we assume that initial values of window sizes of all
source hosts are identical, and also assume that control parameters of
connections in the same group are identical. For brevity, the control
parameter of source hosts in group m is represented by
.
Provided that all source hosts change their window sizes according to
Eq. (3), the number of packets in the router's buffer at
slot k + 1 is given by
where
.
Let wm*, q* and dm* be the fixed points of wm(k), q(k)
and
in steady state,
respectively. By using
Eqs. (1), (3) and (4), wm*, q*
and dm* can be obtained easily. Let
be the
difference of the system state from its fixed points at slot k,
i.e.,
Since wm(k) is a non-linear equation, we linearize it around the fixed point. By letting
be the LCM (Lowest Common
Multiple) of 
,
,
,
can be written as
(5)where
is a state transition matrix. Stability and transient
behavior of the system around the fixed point is determined by
eigenvalues of the matrix .
More specifically, the fixed
point is locally asymptotically stable if and only if all roots
of the characteristic equation
D(s) = |sI - A| = 0
lie in the unit circle [11]. It can be easily
checked by using the Jury's criterion if the matrix
satisfies
this condition or not [11].
In the following, we discuss the case of M = 2 (i.e., two groups
of connections) for 
and 
(i.e., the
ratio of the propagation delays is 1:2) due to space limitation. For
the cases of M > 3 or other ratios of propagation delays, the same
approach can be easily applied.
In the case of M = 2, ,
and ,
the fixed
points of the system are given by
where
When the waiting time at the router's buffer is very small compared to propagation delays, wm* and q* can be approximated as
Equation (9) indicates that the fixed point of the window size wm* is proportional to the processing speed of the router B and the propagation delay
,
and is inversely proportional to the
number of connections N1 and N2. Equation (10)
indicates that the
fixed point of the number of the packets in the router's buffer q*
is the sum of 
's of all source hosts. Thus, the number of
packets in the router's buffer in steady state can be controlled by
appropriately choosing a control parameter
We then derive the throughput of each connection. The throughput
of connections in group m is given by
From Eq. (1), we find that dm* converges to
in steady state. Using Eq. (3) gives
Hence, the throughput
is obtained as
The above equation suggests that the ratio of throughput
of connections in groups 1 and 2 is simply determined by the ratio of
and 
.
It means that the ratio of throughput of
connections is dependent only on the control parameter
,
and
is independent of other parameters;
the propagation delay
and the number of
connections Nm. If we choose the control parameter appropriately,
the router would be fully utilized. In this case,
is given by
a simple equation.
Therefore, if
connections become identical, leading to a fair bandwidth
allocation among all connections. However, this sort of fairness can be
achieved only when there exists a single bottleneck router in the
network. We have shown that the throughput of TCP Vegas is determined
not only by a control parameter but also by the number of routers on
the path [12]. Therefore, in real networks, it is
insufficient to set
equally to all connections for
achieving a fair bandwidth allocation to connections. For example,
should be chosen according to the number of bottleneck
router's on the path. However, parameter tuning of
for
such network configuration is beyond the scope of this paper.
In the case of M = 2, ,
and ,
the matrix
becomes
where am and bm (m=1, 2) are defined as
4. Numerical Examples
In this section, we present several numerical examples and discuss
how the stability region is affected by a choice of control
parameters and system parameters. Figure 2 shows boundary
lines of the stability region on 
-
plane for
several values of processing speed of the router B.
In this figure, the following parameters
are used: the number of connections N1 = N2 = 10, the round-trip
propagation delay 
= 1 [ms] and 
= 2 [ms], and the control
parameter
=
= 3 [packet]. The processing speed
of the router B is changed from 2 to 2,000 [packet/ms]. This figure
means that the system becomes
stable when the point (,
)
lies inside the boundary
line. That is, for the window-based congestion control mechanism
to be stable, we should choose the point (,
)
in the region
surrounded by the boundary line and both x- and y- axes.
 |
One can find from the figure that the stability region heavily depends
on the processing speed of the router B. One can also find that the
maximum value of
for connections with a large propagation
delay is larger than the maximum value of
for connections
with a small propagation delay. This tendency becomes more noticeable
as the processing speed of the router B becomes large. For example,
when B = 2,000 [packet/ms], the maximum values of
and
for stable operation are 2 and 4, respectively. Note that
the ratio of
and
is equal to the ratio of their
propagation delays,
and .
This can be explained as
follows. In TCP Vegas, a source host changes its window size once per
RTT. Hence, a connection with a larger propagation delay changes its
window size less frequently so that it has less influence on system
stability. In other words, if a connection with a small propagation
delay changes its window size excessively, the system is likely to
become unstable. So if 
's of all connections are equal,
stability of the system is mostly determined by the connection with
the smallest propagation delay.
Figure 2 also indicates that when the processing speed of
the router B is small, the maximum value of
is almost
independent of the propagation delay. For example, when
B=2 [packet/ms], the system becomes stable if both
and
are set less than 2. This is because when the processing
speed of the router B is very small, the waiting time at the
router's buffer is much larger than the propagation delay. Namely,
the observed RTT of a connection is not so affected by its propagation
delay since the waiting time at the router's buffer is the dominant
part of its RTT. Consequently, frequency of the window size change
becomes almost same in all connections so that the maximum value of
becomes identical.
 |
Figure 3 shows the stability region for different values of
propagation delays
from 0.1 [ms] to 100 [ms]. In this
figure, values of control parameters and system parameters are equal
to those in Fig. 2, whereas the processing speed of the
router B is fixed at 20 [packet/ms]. In this figure, the ratio of
propagation delays is fixed at 1:2. Namely,
is always twice
of .
By comparing Figs. 2 and 3, one can
find that boundary lines in these figures are almost identical. Such a
correspondence can be easily explained from
Eqs. (6)-(8) and (12). Namely, all B's
and 's in these equations take the product form of
.
This suggests an interesting fact that the same
effect is obtained by increasing
the processing speed of the router B and by increasing the
propagation delay
in the window-based congestion control
mechanism.
Such a characteristic of the window-based flow control
mechanism indicates that the bandwidth-delay product,
,
is one of key factors that determine system
stability. Intuitively, the bandwidth-delay product,
,
represents the number of on-the-fly packets on
all transmission links. Our analytic results suggests that
the system becomes less stable as the number of on-the-fly
packets increases.
We next show the stability region for different numbers of connections
N1 and N2 in Figs. 4 and 5, respectively.
In these figures, the following parameters are used: the processing
speed of the router B=20 [packet/ms], the propagation delay
[ms],
[ms],
[packet]. In
Fig. 4, the number of connections N2 is fixed at 10 but
N1 is changed from 1 to 1,000. On the contrary, in
Fig. 5, N1 is fixed at 10 but N2 is changed from 1 to
1,000. These figures show that the maximum value of
for
stable operation becomes small as the number of connections becomes
large. For example, one can find that the maximum value of
becomes small as N1 becomes large in Fig. 4. This
phenomenon can be explained as follows. Since RTTs of connections in
a group are identical, these connections change their window sizes
synchronously. When the number of connections in a group increases,
the amount of the window size change becomes large. Therefore, the
system tends to become less stable so that
should be small
for avoiding unstable operation.
 |
[ms],
 |
However, Figs. 4 and 5 also show that when 
and 
,
the system is always stabilized regardless of
the number of connections. Since the number of active connections in
a real network changes frequently, and since it is difficult to
prospect, setting of control parameters of
and
would be desired for practical purposes. Moreover, it
is expected from Figs. 2 through 5 that there
exists a region where the system can always be stabilized for any
network parameters. By increasing the processing speed of the router
B, the number of connections Nm, the propagation delay
or the control parameter
to infinity, the
stability region for any network parameters can be easily found:
and .
However, to select the optimal point
of (,
), we should consider transient performance in
addition to system stability. The optimal (,
)
that
leads to the best transient behavior can be calculated by the same
method used in [5]. However, the consideration about
setting optimal (,
)
for the best transient behavior
is our future work.
Finally, we show the dynamics of the window-based flow control
mechanism in stable and unstable cases. We choose the processing
speed of the router B=20 [packet/ms], and
(,
)
=
(3.0, 4.0) in Fig. 6 (stable case) or
(,
)
= (4.0, 5.0) in Fig. 7 (unstable
case). The other parameters are identical to those used in
Fig. 2. In these figures, the evolutions of the window size
wm(k) and the number of the packets at the router's buffer q(k)
are plotted. These figures are obtained by numerically computing the
system state using Eq. (5). The initial values of the
window size wm(k) and the number of the packets at the router's
buffer q(k) are set to 80 % of the fixed points, w* and q*.
)
)
In the stable case (Fig. 6), the system becomes stable in 150 [ms] as expected. However, in the unstable case (Fig. 7), both the window size and the number of the packets at the router's buffer oscillate indefinitely.
5. Simulation Results
In this section, several simulation results are shown for validating
our analysis presented in Section 3. We use the following
parameters: the processing speed of the router B = 20 [packet/ms],
the number of connections N1 = N2 = 1, the propagation delay
[ms],
[ms], the control parameter
[packet]. For the control parameter
,
we use
(,
)
= (1.0, 3.0) as a stable case and (3.0, 1.0) as
unstable case. Figure 8 shows the stability region for
these parameters obtained from our analysis. Dynamics of the windows size
wm(k) and the number of packets at the router q(k) are plotted in
Figs. 9 (stable case)
and 10 (unstable case), respectively.
Using Eqs.(6)-(8), the fixed points, wm*
and q*, in this parameter setting should be
From Figs. 9 and 10, the fixed points in simulation experiments are
which shows close values to analytic ones. The difference between analytic and simulation results is possibly caused by our assumptions that the window size change is synchronous and the waiting time at the router's buffer is neglected.
By comparing Figs. 9 (stable case)
and 10 (unstable case), it can be found
that both the window size wm(k) and the number of packets at the
router q(k) oscillate excessively when
(,
)
is
out of the stability region. On the contrary, when (,
)
satisfies the stability condition, the dynamics of the
system becomes almost stable although there is slight oscillation in the
window size wm(k) and q(k).
,
)
,
)
6. Conclusion and Future Work
In this paper, we have focused on the window-based flow control
mechanism based on the congestion avoidance mechanism of TCP Vegas.
We have analyzed its behavior in steady state by applying a control
theory. We have considered a network model consisting of TCP
connections with different propagation delays. We have first derived
the fixed points of the window size and the number of packets in the
bottleneck router's buffer. We have shown that a fair bandwidth
allocation to all connections can be realized by setting
's
of all connections identically regardless of the difference of their
propagation delays. We have also derived the stability condition of
the window-based flow control mechanism, and have investigated the
relation between system stability and network parameters through
several numerical examples. We have found that the system can be
stabilized by choosing the control parameter of each connection
proportionally to its round-trip propagation delay. Simulation
results have also been presented for validating our analysis.
Our future work is to find the optimal setting of control parameters for achieving reasonable transient performance as well as stable operation of the system. Moreover, dynamics of the window-based flow control mechanism when a new connection is established should also be investigated. Our ongoing research is to analyze more generic network configurations where there exists more than two bottleneck routers in the network.
References
- 1
- L. S. Brakmo, S. W. O'Malley, and L. L. Peterson, ``TCP Vegas: New techniques for congestion detection and avoidance,'' in Proceedings of ACM SIGCOMM '94, pp. 24-35, October 1994.
- 2
- O. A. Hellal and E. Altman, ``Analysis of TCP Vegas and TCP Reno,'' in Proceedings of IEEE ICC '97, pp. 495-499, June 1997.
- 3
- A. Kumar, ``Comperative performance analysis of versions of TCP in a local network with a lossy link,'' IEEE/ACM Transactions on Networking, vol. 6, pp. 485-498, August 1998.
- 4
- J. Mo, R. J. La, V. Anantharam, and J. Walrand, ``Analysis and comparison of TCP Reno and TCP Vegas,'' in Proceedings of IEEE INFOCOM '99, March 1999.
- 5
- H. Ohsaki, M. Murata, T. Ushio, and H. Miyahara, ``Stability analysis of window-based flow control mechanism in TCP/IP networks,'' 1999 IEEE International Conference on Control Applications, pp. 1603-1606, August 1999.
- 6
- B.-K. Kim and C. Thompson, ``Optimal feedback control of ABR traffic in ATM networks,'' in Proceedings of IEEE GLOBECOM '98, pp. 844-848, 1998.
- 7
- H. Zhang and O. W. Yang, ``Design of robust congestion controllers for ATM networks,'' in Proceedings of IEEE INFOCOM '97, pp. 302-309, April 1997.
- 8
- A. Kolarov and G. Ramamurthy, ``A control theoretic approach to the design of closed-loop rate based flow control for high speed ATM networks,'' in Proceedings of IEEE INFOCOM '97, pp. 293-301, April 1997.
- 9
- H. Ohsaki, M. Murata, T. Ushio, and H. Miyahara, ``A control theoretical analysis of a window-based flow control mechanism in TCP/IP networks,'' submitted to IEEE Journal on Selected Areas in Communications QoS in the Internet, 1999.
- 10
- G. Hasegawa, M. Murata, and H. Miyahara, ``Fairness and stability of congestion control mechanism of TCP,'' in Proceedings of 11th ITC Special Seminar, pp. 255-262, October 1998.
- 11
-
R. Isermann, Digital control systems, Volume 1: fundamentails,
deterministic control.
Springer-Verlag Berlin Heidelberg, 1989. - 12
- K. Takagaki, H. Ohsaki, and M. Murata, ``Analysis of window-based flow control mechanism in heterogeneous network environment,'' in preparation, 2000.