IEICE TRANS. COMMUN., VOL.E92–B, NO.10 OCTOBER 2009

3174

PAPER

Stability Analysis of XCP (eXplicit Control Protocol) with
Heterogeneous Flows
Yusuke SAKUMOTO†a) , Student Member, Hiroyuki OHSAKI†b) , and Makoto IMASE†c) , Members

SUMMARY
In this paper, we analyze the stability of XCP (eXplicit
Control Protocol) in a network with heterogeneous XCP flows (i.e., XCP
flows with diﬀerent propagation delays). Specifically, we model a networkwith heterogeneous XCP flows using fluid-flow approximation. We thenderive the conditions that XCP control parameters should satisfy for stable XCP operation. Furthermore, through several numerical examples andsimulation results, we quantitatively investigate eﬀect of system parametersand XCP control parameters on stability of the XCP protocol. Our findings
include: (1) when XCP flows are heterogeneous, XCP operates more stably than the case when XCP flows are homogeneous, (2) conversely, when
variation in propagation delays of XCP flows is large, operation of XCP
becomes unstable, and (3) the output link bandwidth of an XCP router is
independent of stability of the XCP protocol.
key words: XCP (eXplicit control protocol), stability, heterogeneous flows,
control theory, fluid-flow approximation

1.

Introduction

TCP (Transmission Control Protocol) is being widely usedin the Internet to carry data traﬃc [1]. There are various
versions of TCP, and the most popular ones are TCP version
Reno (TCP Reno) and its variants [2]. Several problems of
TCP Reno have been reported such as its inability to support
rapidly increasing speeds of recent networks [3]–[5].
One of the serious problems with TCP Reno is that alarge number of packets sent into the network are discarded.
This problem is caused by inability of source hosts to detectcongestion before some packets are lost, and large delay forsource hosts to detect congestion when the round-trip time
between end hosts is large. Since the scale and the speedof network is continuously increasing, it is expected that theperformance of TCP Reno would be further degraded due toan increased number of packet losses before source hosts’
congestion detection.
For solving such problems in a high-speed and widearea network, many transport-layer protocols using explicit
feedback from a router to end hosts are proposed [6]–[9].
Compared with TCP Reno, these protocols perform eﬃcient congestion control between end hosts with the aidof routers. Among those router-assisted congestion control
mechanisms, XCP (eXplicit Control Protocol) has been receiving attention [6], [10]. XCP is a sort of window-based
Manuscript received September 19, 2008.
Manuscript revised February 25, 2009.
†
The authors are with the Graduate School of Information Science and Technology Osaka University, Suita-shi, 565-0871 Japan.
a) E-mail: y-sakumt@ist.osaka-u.ac.jpb) E-mail: oosaki@ist.osaka-u.ac.jpc) E-mail: imase@ist.osaka-u.ac.jp
DOI: 10.1587/transcom.E92.B.3174

flow control mechanisms. An XCP router periodically calculates the amount of window size increase/decrease for asource host, and notifies source hosts of it as explicit feedback. With such explicit feedback, an XCP source host canquickly and appropriately respond to congestion status of
the network.
With simulation experiments, it has been reported that
XCP achieves better performance than TCP Reno does [6],[11]. However, characteristics of XCP as a feedback-based
control system, such as stability and transient performance,
have not been suﬃciently clarified.
A stability issue of XCP in a tandem network has been
pointed out in [12] through simulation experiments. In [12],the authors show that the operation of XCP may become
unstable in a tandem network. Due to the nature of thesimulation-based and subjective approach taken in [12], detailed characteristics of XCP protocol has not been clarified.
For better understanding the characteristics of the XCP protocol, analytic approaches are indispensable.
There exist a few analytical studies on XCP, all ofwhich used fluid-flow approximation [6], [13]–[15]. In [6],[13], by assuming an identical propagation delay for all
XCP flows, stability of XCP has been analyzed. The authors of [6] have derived a suﬃcient condition for XCP control parameters to stabilize XCP’s operation. By extending
the analytic model in [6], the authors of [13] have shownthat operation of XCP becomes unstable when the available bandwidth of an XCP router’s output link is varied.
The authors of [14] have analyzed stability of XCP usinga Lyapunov function. In [14], the authors mention possibility of extending their stability analysis to handle heterogeneous XCP flows, but the details are not presented. In [15],steady state performance of XCP in a tandem network (i.e., a
network with multiple routers and heterogeneous flows) has
been analyzed. Specifically, the authors of [15] have derived
throughput of XCP flows in steady state, and have shownthat fairness among XCP flows is significantly degraded unless control parameters of an XCP router are configured appropriately. Although multiple XCP flows are modeled in[15] for analyzing fairness among XCP flows, stability of
XCP has not been investigated.
In this paper, we analyze the stability of XCP in a
network with heterogeneous XCP flows (i.e., XCP flows
with diﬀerent propagation delays). Specifically, we modela network with heterogeneous XCP flows using fluid-flow
approximation. We then derive the conditions that XCP
control parameters should satisfy for stable XCP operation.

c 2009 The Institute of Electronics, Information and Communication Engineers
Copyright SAKUMOTO et al.: STABILITY ANALYSIS OF XCP (EXPLICIT CONTROL PROTOCOL) WITH HETEROGENEOUS FLOWS

3175

Through several numerical examples and simulation results,
we quantitatively investigate eﬀect of system parametersand XCP control parameters on stability of the XCP protocol. Our findings include: (1) when XCP flows are heterogeneous, XCP operates more stably than the case when
XCP flows are homogeneous, (2) conversely, when variationin propagation delays of XCP flows are large, operation of
XCP becomes unstable, and (3) the output link bandwidthof an XCP router is independent of stability of the XCP protocol.
The primary contribution of this paper is to mathematically reveal stability properties of the XCP protocol withheterogeneous flows. Diﬀerent from [12], [15], we explicitly model the dynamics of heterogeneous XCP flows for deriving the stability condition. Our stability analysis is basedon [16], which analyzes the stability of the DCCP protocol. We believe our findings are generic since our stability analysis is performed with reasonable assumptions (seeSect. 3), as well as valid since our stability analysis is validated through simulations in Sect. 5.
The organization of this paper is as follows. First, in
Sect. 2, the algorithm of XCP is briefly explained. In Sect. 3,
heterogeneous XCP flows and an XCP router are modeledusing fluid-flow approximation. Section 4 performs stability analysis of XCP. In Sect. 5, the eﬀect of system parameters and XCP control parameters on stability of the XCPprotocol is quantitatively evaluated through several numerical examples and simulation results. Finally, in Sect. 6, weconclude this paper and discuss future works.
2.

XCP (eXplicit Control Protocol)

In this section, the congestion control algorithm of XCP isbriefly summarized. Refer to [6] for details of the XCP algorithm.
In XCP, congestion information is exchanged between
a source host and a router using congestion header in apacket. An overview of the XCP congestion control using
the congestion header of a packet is illustrated in Fig. 1.

Fig. 1 Overview of XCP congestion control algorithm; a router calculates the amount of window size increase/decrease for a source host, and it
then notifies the source host of the calculated value as explicit feedback.

XCP is a sort of window-based flow control mechanisms. In XCP, a router calculates the amount of window
size increase/decrease for a source host, and it then notifies
the source host of the calculated value as explicit feedback.
The congestion header of a packet stores information on asource host and a router: e.g., the window size and the estimated round-trip time of the source host, and the amount of
window-size increase/decrease (i.e., feedback value) calculated by the router.
At the time of packet transmission, a source host storesits estimated round-trip time, its current window size, andthe initial value of the feedback value (i.e., the amount of
window size increase requested by the source host) in thecongestion header of the packet. This enables the XCProuter to know the status of the source host.
When the packet arrives at an XCP router, the routercalculates a feedback value based on the information stored
in the congestion header of the packet. The router overwrites
the feedback value in the congestion header of the packet
with the calculated feedback value, if the feedback value
stored in the congestion header is larger than the calculated
feedback value. The XCP router then forwards the packet toits downstream router.
Once the packet arrives at a destination host, the destination host returns an ACK (ACKnowledgement) packet tothe source host. At this time, the congestion header of thedata packet is copied to the congestion header of the ACK
packet. This makes it possible for the source host to know
the congestion information of XCP routers by way of thedestination host.
Finally, when the source host receives the ACK packet,
the feedback value stored in the congestion header of the
ACK packet is added to the current window size of thesource host.
In what follows, we explain how an XCP router calculates a feedback value (i.e., the amount of increase/decreaseof the window size of a source host).
The control mechanism of an XCP router is composedof eﬃciency controller, which tries to maximize utilizationof the router, and fairness controller, which tries to realize fairness among competing XCP flows. The eﬃciency
controller and the fairness controller are invoked every average round-trip time of all XCP flows. The eﬃciency controller calculates the total amount of rate increase/decrease
for all XCP flows. The fairness controller then calculates
the amount of rate increase/decrease for each XCP flow.
An XCP router calculates a feedback value based on theamount of rate increase/decrease calculated by the fairness
controller and information stored in the congestion headerof arriving packets. In what follows, algorithms of the eﬃciency controller and the fairness controller are briefly explained.
The eﬃciency controller calculates the aggregate feedback value φ (i.e., the total amount of rate increase/decrease
for all XCP flows) from the packet arrival rate at the XCProuter and the current queue length as

IEICE TRANS. COMMUN., VOL.E92–B, NO.10 OCTOBER 20093176

φ = α d S − β Q,

(1)where d is the average round-trip time of XCP flows accommodated in the XCP router, S is the available bandwidth ofthe link (i.e., the output link bandwidth excluding the current packet arrival rate), Q is the minimum queue length observed during the average round-trip propagation time, and
α and β are control parameters of the XCP router.
The fairness controller distributes the aggregate feedback value φ to all XCP flows. The fairness controller realizes fairness among XCP flows by performing an AIMD
(Additive Increase and Multiplicative Decrease) control.
Namely, if φ ≥ 0, the fairness controller allocates φ so thatthe increase in throughput of all XCP flows is the same. On
the contrary, if φ < 0, the fairness controller allocates φ sothat the decrease in throughput of a XCP flow is proportional
to its current throughput. Specifically, the fairness controller
calculates ξ p and ξn , which are used for calculating the feedback value.
ξp =dh + [φ]+N rttm sm
m=1

(2)

wm

h + [−φ]+
ξn =
dT

(3)

In the above equations, N is the number of packets arrived
at the XCP router during the average round-trip time, and T
is the total size of packets arrived during the average roundtrip time.
Also, wm and rttm are the window size and the estimated round-trip time stored in the congestion header of them-th packet of N packets arrived during the average roundtrip time, and sm is the packet size of the m-th packet. Notethat [x]+ ≡ max(x, 0).
In Eq. (3), h is called shuﬄe traﬃc, and is determined
by


(4)
h = γ T − |φ| + ,where γ is a control parameter of an XCP router.
Finally, an XCP router calculates the feedback value
H f eedback for the m-th packet as
H f eedback = ξ p3.

rttm2 sm
− ξn rttm sm .
wm(5)Modeling with Fluid-Flow Approximation

In this paper, we model a network with heterogeneous XCPflows with diﬀerent propagation delays (i.e., XCP flows
traversing links with diﬀerent propagation delays) sharing
the single bottleneck link as a discrete-time system (Fig. 2).
XCP flows are classified into flow classes, in which XCPflows have the identical propagation delay. In our analysis,
dynamics of transfer rates from XCP flows and the queue
length of an XCP router are modeled as discrete-time models with slot length of Δ. The definition of symbols usedthroughout our analysis is summarized in Table 1.

Fig. 2 Analytic model; heterogeneous XCP flows with diﬀerent
propagation delays share the single bottleneck.

Table 1

M
Ni
Δ
ri
τi
d
s
T
q
φ
h
A
C
α
β
γ

The definition of symbols.

the number of flow classes
the number of XCP flows in flow class i
slot lengthtransfer rate of XCP flows in flow class i
two-way propagation delay of XCP flows in flow class iaverage round-trip time of all XCP flows
packet length
the total size of packets arrived during the averageround-trip timecurrent queue length of XCP routeraggregate feedback of XCP router
shuﬄe traﬃc of XCP router
packet arrival rate at XCP router
output link bandwidth of XCP router
XCP control parameter
XCP control parameter
XCP control parameterIn this paper, we focus on the stability of XCP in a network with a single XCP router, rather than in a tandem network. We believe that it is possible to extend our analytic
approach to a tandem network with multiple XCP routers,
but it is beyond the scope of this paper. It should be notedthat the operation of XCP may become unstable in a tandem network when many XCP flows are frequently activatedand/or deactivated [12]. The main purpose of this paper is,
however, to investigate the eﬀect of heterogeneous flow on
the stability of the XCP protocol.
In what follows, using a fluid-based modeling approach, we derive a detailed model of a network with heterogeneous XCP flows.
First, we model dynamics of the transfer rate of an XCP
flow. In our analysis, we assume: (a) all XCP flows withthe same propagation delay synchronize, (b) all XCP source
hosts always have data to transfer, (c) sizes of all packets areequal, (d) the window size of a source host is changed only
by receiving the feedback value from XCP routers (i.e., effect of timeouts triggered by a large number of packet losses
are negligible), and (e) the round-trip time of an XCP flow
is equal to its two-way propagation delay.
Since an XCP router performs the same congestion
control for all XCP flows with the same round-trip time(see Eq. (5)), the assumption (a) is reasonable. Moreover,since XCP is mainly used for transferring a large amountof data in a high-speed network, assumptions (b) through(d) should be appropriate. The assumption (e) is reasonable
since the control objective of an XCP router is to minimize

SAKUMOTO et al.: STABILITY ANALYSIS OF XCP (EXPLICIT CONTROL PROTOCOL) WITH HETEROGENEOUS FLOWS

3177

its queue length, resulting negligible queuing delay at therouter buﬀer. Note that in our analysis, all XCP flows are
assumed to start their transmissions simultaneously from an
initial state. Hence, the queue length of the XCP router is
not likely to be overloaded, which validates the assumption(e).
The transfer rate and the two-way propagation delay of
XCP flows in flow class i are denoted by ri and τi , respectively. Moreover, the number of XCP flows in flow class i
is denoted by Ni . Then, the packet arrival rate A at an XCProuter and the average round-trip time d of all XCP flows
are given byA=M

Ni r i ,
i=1
M
Ni τi
.
d = i=1M
i=1 Ni(6)+h + [φ],Md2 i=1Nih + [−φ]+
ξn =
.
d2 A

(8)
(9)

In the above equations, the aggregate feedback value φ andthe shuﬄe traﬃc h are given by Eqs. (1) and (4) as
h = [γ d A − |φ|]+ ,φ = α d (C − A) − β q,

(10)
(11)

where q is the current queue length of the XCP router, andC is the output link bandwidth of the XCP router.
From Eqs. (8) and (9), the feedback value H f eedback i for
XCP flows in flow class i is given by
H f eedback i =h + [φ]+ τi s h + [−φ]+
τi s.
−

ri
d2 A
d2 M
j=1 N j−Δ

d2 A(k − τΔi ). (14)

Next, we model the dynamics of the queue length of an
XCP router. Letting q(k) be the current queue length of the
XCP router at slot k, the current queue length q(k + 1) at slot
k + 1 is approximately given byq(k) + Δ (A(k) − C) if q(k) > 0.
q(k + 1) 
q(k) + Δ [A(k) − C]+ if q(k) = 0(15)
4.

Stability Analysis

In what follows, using the fluid-flow model of XCP derived
in Sect. 3, we analyze the stability (local asymptotic stability) of XCP around its equilibrium point using the same analytic approach with [16]. In what follows, equilibrium values of the transfer rate ri (k) and the current queue lengthq(k) are denoted by ri∗ and q∗ , respectively. First, we linearize the fluid-flow model defined by Eqs. (14) and (15) at
its equilibrium point. The aggregate feedback value φ(k)and the current queue length q(k) are discontinuous at theequilibrium point (i.e., φ∗ = 0 and q∗ = 0). For alleviatingsuch a discontinuity problem, we introduce the following
approximation for a suﬃciently small Δ.
[ f (x + Δ)]+ − [ f (x)]+ 1 f (x + Δ) − f (x)

Δ
2
Δ

(16)

Thereby, Eqs. (14) and (15) can be approximated ash(k − τΔi ) + φ(k − τΔi )/2
d2 M
j=1 N jτi
τiri (k − Δ ) h(k − Δ ) − φ(k − τΔi )/2−Δ,
d2 A(k − τΔi )ri (k + 1)  ri (k) + Δ(12)Hence, at the time of ACK packet reception, the amount ofchange in the transfer rate of XCP flows in flow class i isgiven byH f eedback i
h + [φ]+ s h + [−φ]+
= M
−
s.
τi
d2 A
d2 j=1 N j rih(k − τΔi ) + [φ(k − τΔi )]+d2 M
j=1 N jri (k − τΔi ) h(k − τΔi ) + [−φ(k − τΔi )]+ri (k + 1)  ri (k) + Δ

(7)

N
M
Since m=1
rttm sm /wm  d i=1
Ni in Eq. (2) [15] andT  A d, ξ p and ξn (Eqs. (2) and (3)) are given byξp =transfer rate of XCP flows in flow class i at (k + 1)-th slot isgiven by

(17)

and
(13)

The transfer rate of XCP flows in flow class i and thecurrent queue length of the XCP router at slot k are denotedby ri (k) and q(k), respectively. Without loss of generality,
we assume that the propagation delay from a source host to
the XCP router is zero, and that the propagation delay fromthe XCP router to source hosts by way of the destination
hosts is τi . The information stored in the congestion headerof the ACK packet received by a source host at slot k is
k − τi /Δ slots old. Moreover, the number of ACK packets
that a source host receives during the slot length Δ can beapproximated by ri (k − τi /Δ) Δ/s. Thus, from Eq. (13), theq(k + 1)  q(k) +Δ (A(k) − C)
.
2

(18)

Equations (17) and (18) suggest that state variables atslot k + 1 are determined by state variables from k − ν (ν ≡max1≤i≤M τi /Δ) to slot k.
Furthermore, we linearize Eq. (17) around its equilibrium point asri (k + 1) νM ∂ri (k + 1)

∂rm (k − n)m=1 n=0+ν∂ri (k + 1)

∂q(k − n)n=0rm (k − n) − rm∗{q(k − n) − q∗ } .

(19)

IEICE TRANS. COMMUN., VOL.E92–B, NO.10 OCTOBER 20093178

We introduce a state vector x(k) that is composed ofdiﬀerences between each state variable at slot k, . . . , k − νand their equilibrium values.
⎛⎞
r1 (k) − r1∗ ⎟⎟
⎜⎜⎜
⎟⎟⎟
..
⎜⎜⎜⎜
⎟⎟⎟
⎜⎜⎜
.
⎟⎟
⎜⎜⎜
∗ ⎟
⎜⎜⎜ r1 (k − ν) − r1 ⎟⎟⎟⎟⎟
⎜⎜⎜
⎟⎟⎟
..
⎜⎜⎜
⎟⎟⎟
.
⎜⎜⎜
⎟
∗ ⎟
⎜⎜⎜
r M (k) − r M ⎟⎟⎟⎟⎟⎟⎟
x(k) = ⎜⎜⎜
(20)
..
⎜⎜⎜
⎟⎟⎟
.
⎜⎜⎜
⎟
⎜⎜⎜ r (k − ν) − r∗ ⎟⎟⎟⎟⎟
⎜⎜⎜ M
M ⎟
⎟
⎜⎜⎜
q(k) − q∗ ⎟⎟⎟⎟⎟
⎜⎜⎜
⎟⎟⎟
..
⎜⎜⎜
⎟⎟⎟
⎜⎜⎝
.
⎟⎠
∗
q(k − ν) − q
The relation between x(k) and x(k + 1) can be represented
using a state transition matrix B asx(k + 1) = B x(k).

(21)

Note that the state transition matrix B is independent of theslot k. If x(k) converges to the zero vector for k → ∞, thesystem is stable. Otherwise, the system is unstable. The
state transition matrix B determines the stability of the system. Let λi (1 ≤ i ≤ (M + 1) (ν + 1)) be the eigenvalues of thestate transition matrix B. The maximum absolute value of
eigenvalues (i.e., maximum modules) determines the stability around its equilibrium point. It is known that the systemis stable if the maximum modulus is less than unity [17].
Namely, if the maximum modulus is less than unity, x(k)converges to the zero vector for k → ∞.
5.

Numerical Examples and Simulation Results

5.1 Experimental Design
In this section, through several numerical examples and simulation results, we investigate the eﬀect of system parameters and XCP control parameters on stability of XCP protocol. Due to space limitation, in what follows, only results inthe case of two flow classes (M = 2 ) are shown. Unless explicitly stated, the parameter configuration shown in Table 2
is used. The slot length is set to Δ = min(τ1 , τ2 ).
After examining various numerical examples of ourstability analysis in Sect. 4, we found that the control parameter γ is hardly aﬀected stability of the XCP protocol.
In this paper, we therefore focus only on the eﬀect of con-trol parameters α and β† .
Also, we found that the output link bandwidth C of an
XCP router did not aﬀect stability of the XCP protocol. Although the proof is not shown in this paper due to space limitation, independence of the output link bandwidth C fromstability of the XCP protocol can be confirmed from the factthat expansion of Eq. (19) eliminates all C’s. This phenomenal finding will be confirmed through simulation experiments in Sect. 5.2.
5.2 Eﬀect of Propagation Delays
First, the eﬀect of propagation delays of XCP flows on stability of the XCP protocol is investigated. Figure 3 shows
stability regions of XCP control parameters (α β) for diﬀerent settings of two-way propagation delays: i.e., (τ1 , τ2 ) =(10, 10), (20, 20), (10, 20), and (10, 30) [ms]. The stability
region is a region surrounded by the boundary line in the figure, and the vertical and the horizontal axes. XCP operates
stably only when XCP control parameters (α, β) lie in thestability region. Note that in Fig. 3, boundary lines for (τ1 ,τ2 ) = (10, 10) and (20, 20) are almost identical.
In the following simulations, all XCP flows are activated simultaneously at t = 0. Note that staggered activation of XCP flows, instead of simultaneous activation, does
not aﬀect the stability of the XCP protocol if the activationinterval of consecutive XCP flows is larger than the averageround-trip time.
Figure 3 indicates that the stability region in a heterogeneous case (i.e., when two-way propagation delays
τ1 and τ2 are diﬀerent) is larger than that in the homogeneous case (i.e., when two-way propagation delays τ1 andτ2 are identical). This phenomenon can be explained byde-synchronization of XCP flows with diﬀerent propagation
delays; i.e., when XCP flows have diﬀerent propagation delays, variation in the transfer rate of an XCP flow is likely to
be canceled by those of other XCP flows. Moreover, Fig. 3
indicates that in homogeneous cases (i.e., when two-way

Table 2 The parameter configuration use in numerical examples andsimulation results.

C
τ1
τ2
N1
N2
γ

400 [Mbit/s]
10 [ms]20 [ms]10100.1

Fig. 3 Stability region of XCP control parameters (α β) for diﬀerent settings of two-way propagation delays (τ1 , τ2 ); the stability region in a heterogeneous case is larger than that in the homogeneous case.
†
Note that it is shown in [15] that the control parameter γ does
aﬀect eﬃciency of the XCP router and fairness among XCP flows.

SAKUMOTO et al.: STABILITY ANALYSIS OF XCP (EXPLICIT CONTROL PROTOCOL) WITH HETEROGENEOUS FLOWS

3179

propagation delays of all XCP flows are identical) the stability region is independent of two-way propagation delays
τ1 and τ2 .
From these observations, we conclude that when XCPflows are heterogeneous, XCP operates more stably than thecase when XCP flows are homogeneous.
We then examine the accuracy of our approximate analysis. We choose three settings of control parameters (α, β) :P1 = (0.9, 0.2), P2 = (1.2, 0.2), and P3 = (1.5, 0.2) as shownin Fig. 3. For each control parameters setting, we perform
simulation using ns-2 simulator for the same topology with
Fig. 2. These control parameters settings are chosen to examine validity of our approximate analysis. For instance,
if our stability analysis is valid, simulation results with P2
should be stable for (τ1 , τ2 ) = (10, 20), (10, 30) and unstable for (τ1 , τ2 ) = (10, 10), (20, 20). In all simulations,the packet size is 1,000 [byte] and the initial window size is
1 [packet]. In all simulations, all XCP flows are activated
at 0 [s], the initial window size is set to 1 [packet], and the
network topology shown in Fig. 2 is used.
Simulation results for control parameters settings P1 ,P2 , and P3 are shown in Figs. 4 through 6, respectively.
These figures show evolution of the window size of an XCPflow in flow class 1 for diﬀerent settings of two-way propagation delays: i.e., (τ1 , τ2 ) = (10, 10), (20, 20), (10, 20),and (10, 30). For each simulation result, stability of XCP isdetermined using a simple criterion — whether the window
size of an XCP flow at the end of simulation is within ± 5%
of its average value.
These simulation results are in agreement with our analytic results. For instance, the stability region shown in
Fig. 3 indicates that, with the control parameters of P2 =(1.2, 0.2), the operation of XCP flows is unstable for (τ1 ,τ2 ) = (10, 10) and (20, 20), and is stable for (τ1 , τ2 ) = (10,20) and (10, 30). Simulation results shown in Fig. 5 clearlyshow that the operation of XCP flows is unstable for (τ1 , τ2 )
= (10, 10) and (20, 20). Similar tendency can be observedfor other control parameters P1 = (0.9, 0.2) and P3 = (1.5,
0.2). From these observations, we confirm validity of ourapproximate analysis.
Figures 4 through 6 include simulation results for (τ1 ,τ2 ) = (10, 20) with a large output link bandwidth C =800 [Mbit/s]. One can find from these figures that stability of the XCP protocol is not aﬀected by the output link
bandwidth. As we have discussed in Sect. 5.1, these results
coincide with our finding; i.e., the independence of the output link bandwidth C from stability of the XCP protocol.
5.3 Eﬀect of Variation in Propagation Delays
Next, the eﬀect of variation in propagation delays of XCP
flows on stability of the XCP protocol is investigated. In
this paper, CV (Coeﬃcient of Variation) is used to measure
variation in propagation delays, which is defined byM21i=1 (τi − d)
.
(22)
CV =
M
d
i=1 NiFig. 4 Simulation results with the control parameters of P1 = (0.9, 0.2);
the window size of an XCP flow in flow class 1 is stable regardless of thetwo-way propagation delays (τ1 , τ2 ).

Fig. 5 Simulation results with the control parameters of P2 = (1.2, 0.2);
the window size of an XCP flow in flow class 1 is unstable for (τ1 , τ2 ) =(10, 10), (20, 20).

Fig. 6 Simulation results with the control parameters of P3 = (1.5, 0.2);
the window size of an XCP flow in flow class 1 is stable only when the
two-way propagation delays (τ1 , τ2 ) are set to (10, 30).

Figure 7 shows stability regions of XCP control parameters (α β) for diﬀerent numbers of XCP flows in each flowclass: i.e., (N1 , N2 ) = (5, 15), (10, 10), and (15, 5). In thisfigure, propagation delays of XCP flows, τ1 and τ2 , are set
to 10 [ms] and 20 [ms], respectively.

IEICE TRANS. COMMUN., VOL.E92–B, NO.10 OCTOBER 2009

3180

Fig. 7 Stability region of XCP control parameters (α β) for diﬀerent
numbers of XCP flows in each flow class (N1 , N2 ); the stability regionis smallest when (N1 , N2 ) = (15, 5).

Figure 7 shows that the stability region is smallest
when (N1 , N2 ) = (15, 5); i.e., when the number of XCP
flows in flow class 1 is larger than that in flow class 2. Thisphenomenon can be explained as follows. As explained in
Sect. 2, both the eﬃciency controller and the fairness controller are invoked every average round-trip time of XCP
flows. When there exist many XCP flows with a small propagation delay, the average round-trip time estimated by the
XCP router tends to be small. Since the XCP router invokes
its controllers every the average round-trip time, these controllers are invoked quite frequently. This results in aggressive control of the XCP router, leading unstable operation.
From these observations, we conclude that when variation in propagation delays of XCP flows is large, operationof XCP becomes unstable.
We then investigate the eﬀect of heterogeneity in XCPflows on stability of the XCP protocol. Figure 8 shows the
maximum modulus of eigenvalues of the state transition matrix B for diﬀerent numbers of XCP flows in flow class 1, N1 .
In this figure, the number of XCP flows in flow class 2, N2 ,is fixed at 1, and the propagation delay of XCP flows in flowclass 1, τ1 , is at 10 [ms]. Note that control parameters (α, β)are set to their recommended values, (0.4, 0.226) [6].
Figure 8 shows, for example, the operation of XCP becomes unstable when the number of XCP flows in flow class1, N1 , reaches around 100 (i.e., the maximum modulus becomes larger than 1.0) for τ2 = 200 [ms].
Finally, through simulation experiments, we confirm
the validity of our stability analysis and also investigate
how XCP operates unstably when the heterogeneity of XCP
flows is too large.
Figures 9 through 11 show evolution of the window
size of an XCP flow in each flow class, and the evolutionof the queue length of the XCP router. In these figures, thenumber of XCP flows in each flow class, (N1 , N2 ), are set to(99, 1). Also, the two-way propagation delay of each flowclass, (τ1 , τ2 ), are to either (10, 100) or (10, 200). Figure 9 isthe simulation result of XCP flows with a small propagation
delay. Figure 10 is the simulation result of XCP flows witha long propagation delay.

Fig. 8 Maximum modulus of eigenvalues of the state transition matrix B
for τ1 = 10 [ms], N2 = 1, and (α,β) = (0.4,0.226); the operation of XCP becomes unstable when the number of XCP flows in flow class 1, N1 , reaches
around 100 for τ2 = 200 [ms].

Fig. 9 Evolution of the window size of an XCP flow in flow class 1 forτ1 = 10 [ms] and (α, β) = (0.4, 0.226); XCP flows in flow class 1 are stable
regardless of the two-way propagation delay τ2 of flow class 2. Maximum
throughput are 4.00 [Mbit/s] for τ2 = 100 [ms] and 200 [ms].

Fig. 10 Evolution of the window size of an XCP flow in flow class 2 forτ1 = 10 [ms] and (α, β) = (0.4, 0.226); XCP flows in flow class 2 become
unstable when the two-way propagation delay τ2 of flow class 2 is large.
Maximum throughput are 4.00 [Mbit/s] for τ2 = 100 [ms] and 200 [ms].

Figures 10 and 11 indicate that, when the two-way
propagation delay τ2 of the XCP flow in flow class 2 is
200 [ms], its window size and the queue length of the XCPSAKUMOTO et al.: STABILITY ANALYSIS OF XCP (EXPLICIT CONTROL PROTOCOL) WITH HETEROGENEOUS FLOWS

3181

Fig. 11 Evolution of the queue length of the XCP router for τ1 = 10 [ms]and (α, β) = (0.4, 0.226); The XCP router becomes unstable when the twoway propagation delay τ2 of flow class 2 is large.

router show oscillatory behavior, leading low throughput.
Namely, when the variation in propagation delays of XCP
flows is large, the window size of the XCP flow and thequeue length of the XCP router become unstable, whichshows the validly of our stability analysis.
6.

Conclusion

In this paper, we have analyzed the stability of XCP in a
network with heterogeneous XCP flows (i.e., XCP flows
with diﬀerent propagation delays). Through several numerical examples and simulation results, we have investigatedthe eﬀect of system parameters and XCP control parameters on stability of the XCP protocol. Our findings include:(1) when XCP flows are heterogeneous, XCP operates morestably than the case when XCP flows are homogeneous, (2)conversely, when variation in propagation delays of XCP
flows is large, operation of XCP becomes unstable, and (3)the output link bandwidth of an XCP router is independentof stability of the XCP protocol.
As future work, we are planning to analyze the transient performance of XCP utilizing our fluid model of XCP.
In addition, we are planning to derive the optimal configuration of XCP control parameters, which maximizes the performance of XCP, based on our stability analysis and transient performance analysis. We are planning to clarify thestability of XCP in a network with frequent XCP flows.
Acknowledgements
We would like to thank Prof. Masayuki Murata for his fruitful suggestions. This research was partially supported by the
Ministry of Education, Science, Sports and Culture, Grantin-Aid for Young Scientists (A), 19680003, 2007.
References[1] J. Postel, “Transmission control protocol,” Request for Comments(RFC) 793, Sept. 1981.
[2] J. Padhye and S. Floyd, “On inferring TCP behavior,” ACM SIGCOMM Computer Communication Review, vol.31, no.4, pp.287–

298, Aug. 2001.
[3] S. Floyd, “Highspeed TCP for large congestion windows,” Request
for Comments (RFC) 3649, Dec. 2003.
[4] H. Bullot, R.L. Cottrell, and R. Hughes-Jones, “Evaluation of advanced TCP stacks on fast long-distance production networks,”
Proc. PFLDnet 2004, Feb. 2004.
[5] R. Wang, G. Pau, K. Yamada, M.Y. Sanadidi, and M. Geria, “TCP
startup performance in large bandwidth delay networks,” Proc. IEEE
INFOCOM 2004, pp.796–805, March 2004.
[6] D. Katabi, M. Handley, and C. Rohrs, “Congestion control for highbandwidth-delay product networks,” Proc. ACM SIGCOMM 2002,
pp.89–102, Aug. 2002.
[7] K. Ramakrishnan, S. Floyd, and D.B. Rosen, “The addition of explicit congestion notification (ECN) to IP,” Request for Comments(RFC) 3168, Sept. 2001.
[8] M. Welzl, “Scalable router aided congestion avoidance for bulk datatransfer in high speed networks,” Proc. PFLDnet2005, Feb. 2005.
[9] Y. Xia, L. Subramanian, I. Stoica, and S. Kalyanaraman, “One more
bit is enough,” Proc. ACM SIGCOMM 2005, pp.37–48, Aug. 2005.
[10] A. Falk and D. Katabi, “Specificaton for the explicit control protocol(XCP),” IETF Internet Draft: draft-falk-xcp-spec-01.txt, Oct.
2005.
[11] D. Katabi, “XCP’s performance in the presence of malicious flows,”
Proc. PFLDnet 2004, Feb. 2004.
[12] Y. Zhang, D. Leonard, and D. Loguinov, “Jetmax: Scalable max-min
congestion control for high-speed heterogeneous networks,” Proc.
IEEE INFOCOM 2006, pp.1–13, April 2006.
[13] Y. Zhang and M. Ahmed, “A control theoretic analysis of XCP,”
Proc. IEEE INFOCOM 2005, pp.2831–2835, March 2005.
[14] H. Balakrishnan, N. Dukkipati, N. McKeown, and C. Tomlin, “Stability analysis of explicit congestion control protocols,” IEEE Commun. Lett., vol.11, no.10, pp.823–825, Oct. 2007.
[15] S.H. Low, L.L.H. Andrew, and B.P. Wydrowski, “Understanding
XCP: Equilibrium and fairness,” Proc. IEEE INFOCOM 2005,
pp.1025–1036, March 2005.
[16] H. Hisamatsu, H. Ohsaki, and M. Murata, “Fluid-based analysisof network with DCCP connections and RED routers,” Proc. IEEE
SAINT 2006, pp.156–163, Jan. 2006.
[17] N.S. Nise, Control Systems Engineering, 4th ed., John Wiley &Sons, New York, 2003.

Yusuke Sakumotoreceived B.E. and M.E.
degrees in the Information and Computer Sciences from Osaka University in 2006 and 2008,
respectively. He is currently a Ph.D. candidate
Department of Information Networking, Graduate School of Information Science and Technology, Osaka University, Japan. His research work
is in the area of congestion control protocol. He
is a student member of IEEE and IPSJ.

IEICE TRANS. COMMUN., VOL.E92–B, NO.10 OCTOBER 2009

3182

Hiroyuki Ohsaki
received the M.E. degreein the Information and Computer Sciences from
Osaka University, Osaka, Japan, in 1995. Healso received the Ph.D. degree from Osaka University, Osaka, Japan, in 1997. He is currently
an associate professor at Department of Information Networking, Graduate School of Information Science and Technology, Osaka University, Japan. His research work is in the area oftraﬃc management in high-speed networks. He
is a member of IEEE.

Makoto Imasereceived his B.E. and M.E.
degrees in information engineering from Osaka
University in 1975 and 1977, respectively. He
received D.E. degree from Osaka University in1986. From 1977 to 2001, he was engaged
Nippon Telegraph and Telephone Corporation(NTT). He has been a Professor of Graduate
School of Information Science and Technology
at Osaka University since 2002. His research interests are in the area of information networks,
distributed systems and graph theory. He is amember of IPSJ and JSIAM.