Stability and Adaptability of Autonomous Decentralized Flow Control
in High-Speed Networks
Chisa Takano

Masaki Aida

Trafﬁc Engineering Division
NTT Advanced Technology Corporation
2-4-15, Naka-cho, Musashino-shi 180-0006, Japanchisa@m.ieice.org

NTT Information Sharing Platform Laboratories
NTT Corporation
Musashino-shi 180-8585, Japanaida@m.ieice.org

Abstract

AAAAAAAAAAA
node
packethigh-speed
network

AAAAAAAAAAA
AAAAAAAAAAA
AAAAAAAAAAA
link
node
node

Figure 1. Effect of large delay-bandwidth
product
1 Mbps
1 km
node

node
Tokyo
1 Gbps

node

1 km

1 km

~
~
1000 kmnode

1 Introductionnode
1 Mbps

=
node

Seoul
1 Mbps=node

1 Tbpsnode

In a high-speed network, propagation delay becomes thedominant factor in the transmission delay because the speedof light is an absolute constraint. Therefore, at any given
time, a large amount of data is being propagated on links inthe network (Fig. 1). The amount of this data is characterized by the delay-bandwidth product, i.e., the propagation
distance multiplied by the transmission rate. Therefore, inhigh-speed and/or long-distance transmission, there is moredata in transit on the links than there is in the nodes.
Figure 2 shows an example of how much data there canbe on a link. Let us consider the situation involving datatransmission between two nodes, a distance of 1 km apartwith a link speed of 1 Mbps. If the transmission speed
is increased to 1 Gbps, the amount of data on the link isequivalent to that on 103 km of a 1-Mbps link. And, if thetransmission speed is increased to 1 Tbps, the data volume
is equivalent to 106 km of a 1-Mbps link. This distanceis about 2.5 times the distance between the earth and themoon. Consequently, it is impossible to exert time-sensitive

link

node

~
~

This paper focuses on ﬂow control in high-speed networks. Each node in a network handles its local trafﬁc ﬂow
only on the basis of the information it is aware of, but it
is preferable that the decision-making of each node leads
to high performance of the whole network. To this end, weinvestigate the relationship between the ﬂow control mechanism of each node and network performance. We consider
the situation in which the capacity of a link in the network
is changed but individual nodes are not aware of this. Then
we investigate the stability and adaptability of the network
performance when the capacity of a link is changed, anddiscuss an appropriate ﬂow control model on the basis ofsimulation results.

packetlow-speed
networknode

106 kmnode

5

3.8 x 10 km

earth

moon

Figure 2. Example of delay-bandwidth productcontrol based on collecting global information about the
network. If we allow to spend sufﬁcient time to collectglobal information, the information so gathered is too old
to apply to time-sensitive control. So, in a high-speed
network, the frameworks of time-sensitive control are inevitably autonomous decentralized systems [1, 2, 3].
This paper focuses on back-pressure type ﬂow control
in networks, in which nodes handle their local trafﬁc ﬂow
themselves based only on the information they are aware of.
It is, of course, preferable that the decision making of eachnode leads to high performance for the whole network. In
ﬂow control, we use the total throughput of a network as a
global performance measure [1]. We investigate the behavior of local packet ﬂow and the global performance measure
when a node is congested, and discuss an appropriate ﬂow
control model on the basis of simulation results. In addition,
we investigate the stability and adaptability of the network

Proceedings of the Sixth International Symposium on Autonomous Decentralized Systems (ISADS’03)
0-7695-1876-1/03 $17.00 © 2003 IEEE

Table 1. Classiﬁcation of ﬂow control mechanisms with respect to collecting information.
centralized control
decentralized control

low-speed NW
1-A
1-C

high-speed NW
1-B
1-D

Table 2. Classiﬁcation of decentralized ﬂow
control mechanisms with respect to control
delay requirement.
decision-making
controlled by end hosts(end-to-end, end-to-node)controlled by nodes(node-by-node)long time-scale

short time-scale

2-A

2-B

2-C

2-D

performance when the capacity of a link is changed.
This paper is organized as follows. In Section 2, we discuss related works, comparing them with our work by categorizing ﬂow control mechanisms. In Section 3, we describe a performance measure for the whole network andthe principle of our ﬂow control model. In Section 4, weshow two types of autonomous decentralized ﬂow control.
In Section 5, we describe two simulation models, and thecorresponding results is shown in Section 6. Finally, we
conclude this paper in Section 7.

2 Related Works
In general, the technique used for ﬂow control for highspeed networks should satisfy the following requirements:
1. With regard to the collection of information: it must be
possible to collect the information used in the control.
2. With regard to the delay in applying control: the control should take effect immediately.
In high-speed networks, we cannot collect global information about the network. So, let us classify the ﬂow control mechanisms with respect to collecting information asshown in Table 1.
Centralized control requires the collection of global information about the network, but this is impossible in highspeed networks. Therefore, class 1-B control mechanism
cannot be realized. In low speed networks, both classes 1-A
and 1-C are possible. There are many papers which consider these classes. They mainly study the optimization of
ﬂow control problems in a framework of solving linear programs. Techniques for addressing rate control, bandwidth
assignment, deadlock resolution, resource allocation or ﬂow
fairness problems for each source by optimizing some endto-end utility function have been studied in [4, 5, 6, 7, 8].

[9] studied the issue of to reducing the convergence time insolving optimization problems.
Our target is ﬂow control in a high-speed network, forwhich the framework is inevitably autonomous decentralized control. So, we focus on class 1-D.
We can again classify the decentralized ﬂow control
mechanisms, from the point-of-view of control delay requirement as shown in Table 2.
Flow control by end hosts including TCP is widely usedin the current networks, and there is much research in thisarea.
Based on the optimization problem, [10] introduces adecentralized marking mechanism for early notiﬁcation ofcongestion. For window-based ﬂow control, the optimization problems of some aggregated utility functions havebeen studied in [11]. Solving these optimization problems,
however, requires enough time to be available for calculation, and so it is difﬁcult to apply them to decision-making
in a very short time-scale.
Johari and Tan [12] studied stable end-to-end congestion control when the propagation delay is large relative tothe queueing delay. Each end system requires knowledge
only of its own round-trip delay. [13] studied rate control
and window control with feedback from nodes to end hosts.
Each feedback indicates the state of the buffer at the node
— whether it is above or below a threshold. Since the control by end hosts cannot be applied to decision-making in atime-scale shorter than the round-trip delay, it is inadequate
for application to decision-making in very short time-scale.
Therefore, these methods are categorized as class 2-A. In
high-speed networks, due to the fact that many packets areinﬂuenced by control delay, very short control delay is required. So class 2-B cannot be realized. Our target is nodeby-node control and is categorized as class 2-D.
Bartal et al. [4] studied global optimization of ﬂow control using local information. The motivation of their work
was to enable the distributed routers in high-speed networks
to make decisions on ﬂow control as quickly as possible,
and they studied the problem in a framework of solving linear programs by distributed agents. Though this motivation
is similar to that of our work, their study assumes the distributed agents can obtain detailed information about networks if we allow them to spend sufﬁcient time. As statedabove, our standpoint is based on the fact that we cannot
obtain detailed, useful and up-to-date information about thewhole network in a high-speed network environment, evenif we do not limit the time that we can take.
In our previous works, we have investigated the characteristics of autonomous decentralized ﬂow control in a highspeed network [1, 2, 3]. We proposed a simple and effective
method of ﬂow control in [2]. Since the proposed control
uses less information than the control methods describedin [1, 3], the proposed control is relatively simple. In thisProceedings of the Sixth International Symposium on Autonomous Decentralized Systems (ISADS’03)
0-7695-1876-1/03 $17.00 © 2003 IEEE

node
...
i-1

packet stream
Ji-1
Ji
i

feedback...

i+1

Figure 3. Network model
paper, by changing the capacity of a link, we compare autonomous decentralized ﬂow control mechanisms with respect to the stability and adaptability of the network performance.

3 Models
3.1 Performance Measure
Each packet in a network is either in a node or on a link.
Since the packets currently stored in nodes are not beingtransmitted over the network, it is natural to deﬁne the total
throughput of the network as a global performance measure
as follows. We deﬁne the total throughput of a network attime t as the amount of data being propagated on the network [1, 2, 3, 14]. In other words, it is the number of packets being propagated on all links in the network at time t.
On the other hand, the only packets we can control
are those stored in nodes, and not those being propagated.
Thus, higher performance of the whole network involves
many uncontrollable packets being propagated on links.
Therefore, inappropriate ﬂow control cannot produce a statethat has high performance and stability.

3.2 Network and Flow Control Models
Our network model has a simple 1-dimensional conﬁguration (Fig. 3). All nodes have two incoming links andtwo outgoing ones for a one-way packet stream and feedback information, that is, node i (i = 0, 1, 2, . . .) transfers
packets to node i + 1 and node i + 1 sends feedback information (node information) to node i. For simplicity, we
assume that packets have a ﬁxed length in bits.
All nodes are capable of receiving and sending node
information from/to adjacent downstream and upstream
nodes, respectively. Each node i can receive node information sent from the downstream node i + 1, and can send
its node information to the upstream node i − 1. When nodei receives node information from downstream node i + 1,
it determines the transmission rate for packets to the downstream node i + 1 using the received node information andadjusts its transmission rate towards the downstream nodei + 1. The framework of node behavior and ﬂow control issummarized as follows:• Each node i autonomously determines the transmission rate Ji based only on information it is aware of,i.e., the node information obtained from the downstream node i + 1 and its own node information.

• The rule for determining the transmission rate is thesame for all nodes.
• Each node i adjusts its transmission rate towards thedownstream node i + 1 to Ji .
(If there are no packets in node i, the packet transmission rate is 0.)• Each node i autonomously creates node informationaccording to a predeﬁned rule and sends it to the upstream node i − 1.
• The rule for creating the node information is the samefor all nodes.
• Packets and node information both experience thesame propagation delay.
As mentioned above, the framework of our ﬂow control model involves both autonomous decision-making by
each node and interaction between adjacent nodes. Thereis no centralized control mechanism in the network. Moreprecisely, it is impossible to achieve centralized control ina high-speed network environment. Hereafter, we investigate the behavior of the total network performance driven
by two different ﬂow control mechanisms, applied for different processes used to determine the transmission rate.

4 Preliminary Description of Flow Control
4.1 Packet Flow
In this paper, we focus on the stability and adaptability of
ﬂow control in the congested state, and we consider packet
ﬂow in a heavy-trafﬁc environment. In this situation, we let
the packet ﬂow be Ji if the transmission rate speciﬁed bynode i is Ji . This is because node i has sufﬁcient packets
to transfer. Hereafter, we identify the packet ﬂow with thetransmission rate speciﬁed by the node.
We deﬁne the packet ﬂow as
Ji (t) := α ri (t − di ) − D (ni+1 (t − di ) − ni (t)),(1)

where ni (t) denotes the number of packets in node i at timet, ri is the rate sent by the downstream node i + 1 as node
information, α (> 0) and D (> 0) are constants (we call α
and D the drift and diffusion coefﬁcients, respectively), anddi denotes the propagation delay between node i and nodei + 1. In addition, (ri (t − di ), ni+1 (t − di )) is notiﬁed fromthe downstream node i + 1 with the propagation delay di .
We call the ﬁrst and second terms on the right hand side ofEq. (1) the drift and diffusion terms, respectively.
If there is no packet loss in the network, the temporalvariation of ni (t) is expressed asni (t + ) − ni (t) =Proceedings of the Sixth International Symposium on Autonomous Decentralized Systems (ISADS’03)
0-7695-1876-1/03 $17.00 © 2003 IEEE

[Ji−1 (t − di−1 ) − Ji (t)] ,(2)

where > 0 is a small number.
To estimate the temporal variation roughly, we replace iwith x and apply continuous approximation. Then the propagation delay becomes di → 0 for all i and the packet ﬂow
is expressed as
J(x, t) = α r(x, t) − D∂n(x, t),∂x

(3)and the temporal variation of the number of packets at x is
expressed as a diffusion type equation,∂n(x, t)∂r(x, t)∂ 2 n(x, t)
= −α
+D
,
∂t
∂x
∂x2

(4)

by using the continuous equation∂n(x, t) ∂J(x, t)
+
= 0.
∂t
∂x

(5)

That is, our method aims to perform ﬂow control using theanalogy of a diffusion phenomenon.
Hereafter, we consider two types of ﬂow control andcompare them. One type handles the drift term and the othercontrols both the drift and diffusion terms.

each node has a ﬁnite capacity, so this strategy describedby Eq. (8) cannot be used continuously either.
If we set the rate speciﬁed to the upstream node as
ri−1 (t) = ri (t − di ),(9)then ni (t) does not change with respect to time under aheavy trafﬁc condition. This means that the strategy described by Eq. (9) does not diminish the total performanceof the network. However, when some node is congested,
its restoration requires a long time. Thus, the strategy described by Eq. (9) can also not be used continuously.
From the above considerations, we choose the following
strategy. The rate speciﬁed from node i to the upstream
node i − 1 is determined according to the state of node i.
Let the objective of ni be ns . If ni (t) > ns , then ri−1
is speciﬁed by using Eq. (7); if ni (t) < ns , then ri−1 isspeciﬁed by using Eq. (8); and if ni (t) = ns , then ri−1 isspeciﬁed by using Eq. (9).
Since the above ﬂow control does not use the diffusion
term, we call it drift-type ﬂow control in this paper.

4.3 Diffusion-Type Flow Control and Stability

4.2 Drift-Type Flow Control and Stability
In this subsection, we set D = 0 in Eqs. (1) and (3), andinvestigate the characteristics of a ﬂow control mechanism
whose packet ﬂow is determined only by the drift term.
Let the number of packets in the network be N . To obtain higher network performance, ﬂow control should enable a state in which many packets are being propagated on
links. This state corresponds to a state in which there arefewer packets in nodes.
The simplest strategy for achieving this state is for eachnode to attempt to decrease the number of packets in it.
Therefore, the temporal variation of ni (t) should beni (t + ) − ni (t) < 0.

Ji (t) = α ri (t − di ) − D (ni+1 (t − di ) − ni (t)),(10)

and the node information of node i sent to the upstream
node i − 1 is determined asri−1 (t) = Ji (t).

(11)

(6)

From Eq. (2) and D = 0, this strategy means that node i
notiﬁes a smaller rate to the upstream node i − 1 than therate notiﬁed by the downstream node,ri−1 (t) < ri (t − di ).

In this subsection, we set D > 0 in Eqs. (1) and (3),and investigate the characteristics of the ﬂow control mechanism whose packet ﬂow is determined by both drift anddiffusion terms.
In this control mechanism, node i’s packet transmission
rate to the downstream node i + 1 is determined as(7)

However, if all nodes use this strategy, then the total
throughput decreases with time as a result. Therefore, thestrategy described by Eq. (7) cannot be used continuously.
Conversely, if we use the rate speciﬁed to the upstream
node as(8)ri−1 (t) > ri (t − di ),then ni (t) increases with respect to time (when there aremany packets in the upstream node). But the buffer inIn the case where D = 0 and α = 1, Eqs. (10) and (11)reduce to a drift-type ﬂow control speciﬁed by Eq. (9). In
the framework of Eqs. (10) and (11), the node informationof i speciﬁed to the upstream node i − 1 is a pair of values(ri−1 (t), ni (t)).
Since the above ﬂow control uses the diffusion term, wecall it the diffusion-type ﬂow control in this paper.

5 Simulation ModelIn this section, we consider a simple network model witha bottleneck link having a narrow bandwidth and compare
the performance of the two different ﬂow control principles
described in the previous sections.

Proceedings of the Sixth International Symposium on Autonomous Decentralized Systems (ISADS’03)
0-7695-1876-1/03 $17.00 © 2003 IEEE

congested node...
0

narrow bandwidth

J28
28

J29
29

...
30

and set the following transmission rate and node information.

59

feedback: (r28 ,n29 ) ( r29 ,n30 )Figure 4. Network model with a bottleneck link

5.1 Network Model
Figure 4 shows our network model, which is a closed
network with a 1-dimensional conﬁguration and toroidal
boundary. The network has a congested node and a bottleneck link. All the other nodes and links are in the same
condition. This model simulates the situation when congestion occurs at a certain node. We are interested in the
behavior of the local congestion, that is, whether:• it causes deterioration of the total network performance through interaction among nodes, or• it diminishes with time.
Detailed conditions of our network model are listed below.
• Number of nodes: m = 60. Each node speciﬁed by i(mod 60).
• Propagation delay between adjacent nodes: 1 (unittime)

Ji = min(ri , Li ),
(ni > ns ), Ji × 0.9
Ji × 1.0(ni = ns ),ri−1 =
Ji × 1.1 · · · (ni < ns ),

(12)
(13)

where Li denotes the link capacity between nodes i and i +1.
As a model for the diffusion-type ﬂow control, we set
D = 0.1 in Eqs. (10) and (11), and use the following ﬂow
control model.
(J˜i > Li ), Li ,(14)Ji =0,(J˜i < 0), ˜Ji ,(otherwise),ri−1 = Ji ,(15)
where J˜i = α ri − D (ni+1 − ni ) and α is a constant.

6 Simulation Results: Stability and Adaptability
From the simulation results for the drift- and diffusiontype control models, we compare the total throughput of
the network. In addition, we discuss the stability and adaptability of the both types of ﬂow control model through theobservation of the total throughput.

• Index of the congested node: i = 29
• Total number of packets in the network: N = 6000
• Maximum number of packets on a link (except the bottleneck link): Lc = 100• Maximum number of packets on the bottleneck link
(between nodes i = 29 and 30): Lb = 25, 50, or 75(that is, 1/4, 1/2, or 3/4 of the bandwidth of other links,
and the same length)
To investigate the stability under congestion, in addition to
the above conditions, we set the initial condition for congested node i = 29 as follows.
• Number of packets in node i = 29 at time t = 0: 400• The other 5600 packets are randomly conﬁgured inother nodes and on other links.

5.2 Drift- and Diffusion-Type Flow Control
Mechanisms
As a model for the drift-type ﬂow control, we set an objective for the number of packets in a node to be ns = 60,

6.1 Stability and Adaptability in the Case of the
Appearance of a Bottleneck Link
This subsection considers the case where the capacity ofa link in the network is suddenly reduced to a narrow bandwidth. No node is aware of the change of the link state andnew capacity of the link. We investigate the stability andadaptability of the drift- and diffusion-type control models
through the observation of the total throughput of the network.
Figure 5 shows the simulation result for the drift-type
ﬂow control model when Lb = 50, i.e., a half of the otherlink capacities. The horizontal axis of each graph denotes
node ID and the vertical axis denotes the number of packets
stored in the node. In addition, t denotes the simulation timeand initially t = 0.
The number of packets in the congested node i = 29 decreases with time, and nodes that store packets have around
100 packets at t = 100 and 200. Each node has the objective ns = 60, so the strategy of each node is a failure as aresult.
Similarly, Fig. 6 shows the simulation result for the
diffusion-type ﬂow control model under the same conditions as described for Fig. 5. We chose parameters as

Proceedings of the Sixth International Symposium on Autonomous Decentralized Systems (ISADS’03)
0-7695-1876-1/03 $17.00 © 2003 IEEE

400

t=0

400

t=10

200

200
0

20

40

0

t=50

200
20

0

20

40

t=100

200
0

40

t=30

200

400

400

400

0

20

400

t=200

200
20

40

40

0

20

40

Figure 5. Temporal variation of the number of packets in each node for the drift-type ﬂow control
mechanism (ns = 60)
400

t=0
200

400

t=10
200

0

20

0

40

400

t=50

200

20

20

40

0

t=30

200
0

20

400

400

t=100

200

0

40

400

20

40

40

t=200

200
0

20

40

# of packets on links

Figure 6. Temporal variation of the number of packets in each node for the diffusion-type ﬂow control
mechanism (α = 1.0, D = 0.1)
6000

4000

Next, we discuss the results from a quantitative point ofview. Let us compare both types of control model in thecase where Lb = 50. This is the same condition as theresult shown in Figs. 5 and 6.

Lb =752000

0remarkable that stability is achieved irrespective of Lb .

drift-type
diffusion-type

Lb =50
Lb =25
200

400

600

time

800

1000

Figure 7. Temporal behavior and stability ofthe total throughput of the network for two
different ﬂow control mechanisms

α = 1.0 and D = 0.1. The number of packets in congested
node i = 29 decreases with time, and the distribution of
the number of the packets stored in nodes is smoothly distributed over the network at t = 200.
Figure 7 shows the total throughput for both types ofﬂow control model. The horizontal axis denotes the simulation time and the vertical axis denotes the total throughput(i.e., the total number of packet being propagated on links).
The simulation conditions are the same as for the cases illustrated in Figs. 5 and 6 and we show the cases of threedifferent capacities of the bottleneck link, Lb = 25, 50, and
75. In the case where Lb = 75, the drift-type ﬂow control
achieves higher total throughput than that obtained from thediffusion-type ﬂow control. However, in the other cases, thedrift-type fails to control the total throughput, which falls tozero with time. On the other hand, diffusion-type ﬂow control achieves stable total throughput of the network. It is

For the drift-type control models, the total throughput
decreases with time. This means that the ﬂow control model
inappropriately inﬂuences the global performance of the
network. If all nodes achieve their objective of ns = 60, thetotal throughput should be 2400 (total of 6000 packets; and(60 packets/node × 60 nodes) packets stored in the nodes).
On the other hand, for the diffusion-type control model,
the total throughput decreases with time but becomes stable around 2400. From the link capacity of the bottleneck
link Lb = 50, the maximum value of the sustainable total
throughput (the maximum number of packets being propagated stably on links) is 3000, i.e., 50 packets/link × 60
links. Thus, the diffusion-type ﬂow control achieves 80%of the maximum value of the total throughput and its value
is stable.
If we can choose an appropriate value of the objective ns
for the drift-type ﬂow control, the total throughput may bestable and adaptive. The case where Lb = 75 implies that
this is feasible. However, the value of ns should depend on
the bandwidth of the bottleneck link. Since nodes cannot beaware of information about the bandwidth in a high-speed
network environment, the drift-type control cannot achieve
high performance. In the diffusion-type control model, although no node is aware of the bandwidth of the bottleneck
link, stable and high performance is achieved.

Proceedings of the Sixth International Symposium on Autonomous Decentralized Systems (ISADS’03)
0-7695-1876-1/03 $17.00 © 2003 IEEE

200

400

2000

600

time

800

1000

0

200

400

diffusion-type
α =1.02000

Lb =75

400

600

time

800

800

1000

Lb=50

1000

0

Lb=75

400

600

4000

Lb=75

2000

Lb =50 drift-type
Lb =25

0

200

800

1000

4000

0

400

600

time

800

1000

diffusion-type
α =1.0

Lb =50 Lb =75

2000

Lb =25
200

6000

6000

diffusion-type
α =1.02000

Lb =25
200

600

4000

4000

Lb=50

drift-type

time

6000

6000

0

Lb =75
Lb =50
Lb =254000# of packets on links

0

6000

# of packets on links

2000

drift-type# of packets on links

4000

Lb =75
Lb =50
Lb =25# of packets on links# of packets on links# of packets on links

6000

Lb =25
200

400

600

800

1000

time

time

4000
2000

0

Lb =75
Lb =50diffusion-type
Lb =25α =1.01
200

400

600

time

800

1000

6000

Lb =75
Lb =50
Lb=25

4000
2000

diffusion-type
α =1.01
0

200

400

600

800

1000

# of packets on links

6000# of packets on links# of packets on links

Figure 8. Temporal behavior and stability of the total throughput of the network for two different ﬂow
control mechanisms and three different times (t = 100, 200, and 300) at which the bottleneck is
restored6000

Lb =75
Lb =50
Lb =25

4000
2000
0

time

diffusion-type
α =1.01
200

400

600

800

1000

time

Figure 9. Temporal behavior and stability of the total throughput for the diffusion-type ﬂow control
mechanism with α = 1.01 when the bottleneck is restored (t = 100, 200, and 300)

6.2 Stability and Adaptability in the Case of
Restoration of a Bottleneck Link
This subsection considers the situation where the capacity of the bottleneck link is suddenly restored. No node isaware of the change of the link state and the restored capacity of the link. We investigate the stability and adaptability of both types of control through observation of the total
throughput of the network.
Figure 8 shows the total throughput in the case where thecapacity of the bottleneck link Lb is restored to 100 at timet = 100, 200, and 300 for both models. The horizontal axis
denotes the simulation time and the vertical axis denotes thetotal throughput. The broken lines in these ﬁgures indicate
the time when Lb is restored. The top three ﬁgures show
the results for drift-type control and the bottom three thosefor diffusion-type control. The simulation conditions are
the same as the case for the previous subsection except for
the restoration of the bottleneck link. We show the cases ofthree different capacities of the bottleneck link, Lb = 25,
50, and 75.
In the case where Lb = 75, the drift-type ﬂow control
restores high total throughput of around 6000. It is independent of the time when the restoration occurs. However,for other initial capacities, the drift-type fails to control the
total throughput, which falls to zero.
On the other hand, the diffusion-type ﬂow control
achieves stable total throughput of the network. However,

although the capacity of the bottleneck link is restored, thetotal throughput is not restored in any of the cases. Thisis because we set the drift coefﬁcient of α = 1.0 for the
diffusion-type ﬂow control. This setting of the drift coefﬁcient is derived from Eq. (9) for balancing input and output
ﬂows.
In order to realize ﬂow control which has both stability and adaptability, we choose the diffusion-type control
with α > 1.0. Figure 9 shows the total throughput in thecase where the capacity of the bottleneck link is restored to
100 at time t = 100, 200, and 300 for the diffusion modelwith α = 1.01. From these ﬁgures, the diffusion-type control with α > 1.0 may be seen to have adaptability for the
restoration of the link capacity.

6.3 Stability and Adaptability in the Case where a
Bottleneck Appears and Recovers RepeatedlyThis subsection considers the situation where the capacity of the bottleneck link alternates between normal and restricted values. No node is aware of the changes in the linkstate. We investigate the stability and adaptability of the
diffusion-type control with the drift coefﬁcient of α > 1through observation of the temporal behavior of the total
throughput of the network.
Figure 10 shows the total throughput in case where
the bottleneck appears and recovers repeatedly for the
diffusion-type control with α = 1.01. The capacities of theProceedings of the Sixth International Symposium on Autonomous Decentralized Systems (ISADS’03)
0-7695-1876-1/03 $17.00 © 2003 IEEE

2000
0

reappearance ofthe bottleneck

4000

diffusion-type Lb =25
2000 time 4000

6000

6000

2000
0

recovery of
the bottleneck
diffusion-type Lb =50
4000
2000

time

6000

# of packets on links

4000

reappearance ofthe bottleneck
recovery of
the bottleneck# of packets on links# of packets on links

6000

6000
4000

reappearance ofrecovery of the bottleneck2000
the bottleneck0

diffusion-type Lb =75
2000
6000
4000

time

Figure 10. Temporal behavior and stability of the total throughput for the diffusion-type ﬂow control
mechanism with α = 1.01 when the capacity of the bottleneck is alternately restricted and restored
bottleneck links are Lb = 25, 50, and 75, respectively. The
horizontal axis denotes the simulation time and the verticalaxis denotes the total throughput.
The period of the bottleneck link being alternatelychanged between appearance and restoration is 1000. Simulation conditions are the same as the case for the previous
subsection except for the state of the bottleneck link. In allcases, the diffusion-type control with α = 1.01 achieves theadaptable global performance of the network.

7 Conclusions
This paper has presented a framework for ﬂow control inhigh-speed networks as an autonomous decentralized system. We have showed two typical back-pressure type ﬂow
control models based on the framework. The drift-type ﬂow
control handles the drift term of the packet ﬂow and the
diffusion-type ﬂow control handles both the drift and diffusion terms of the packet ﬂow. For both types of control,
nodes handle their local trafﬁc ﬂow themselves based only
on the information they are aware of.
To investigate the behavior of local packet ﬂow and theglobal performance measure when a node is congested, we
compared two models through simulations. For comparison, we used the total throughput as the ﬂow control performance measure.
Although the drift-type control cannot achieve high performance adaptively, the diffusion-type does achieve stable performance in congested situations. In particular, thediffusion-type control with a drift coefﬁcient of α > 1achieves high performance adaptively, even in a situationin which the congested state changes dynamically.
We are interested in the appropriate values of the drift
and diffusion coefﬁcients, α and D. These issues will be
the subject of further study.

References[2] M. Aida and C. Takano. Stability of autonomous decentralized ﬂow control schemes in high-speed networks. In Proc.
of IEEE ICDCS 2002 Workshop (ADSN 2002), pages 63–68,
2002.
[3] K. Horikawa, M. Aida, and T. Sugawara. Trafﬁc control
scheme under the communication delay of high-speed networks. In Proc. of Int. Conf. on Multi-Agent Systems (ICMAS) ’96, pages 111–117, 1996.
[4] Y. Bartal, J. Byers, and D. Raz. Global optimization using
local information with applications to ﬂow control. In Proc.
of the 38th Ann. IEEE Symp. on Foundations of Computer
Science, October 1997.
[5] B. Awerbuch and Y. Azar. Local optimization of global objectives: competitive distributed deadlock resolution and resource allocation. In Proc. of the 35th Ann. IEEE Symp. on
Foundations of Computer Science, pages 240–249, 1994.
[6] D. Lapsley and S. Low. An IP implementation of optimization ﬂow control. In Proc. of IEEE GLOBECOM ’98,
November 1998.
[7] S. H. Low and D. E. Lapsley. Optimization ﬂow control-I:
basic algorithm and convergence. IEEE/ACM Transactions
on Networking, 7(6):861–874, 1999.
[8] K. Kar, S. Sarkar, and L. Tassiulas. A simple rate control
algorithm for maximizing total user utility. In Proc. of IEEE
INFOCOM 2001, pages 133–141, 2001.
[9] B. Awerbuch and Y. Shavitt. Converging to approximatedmax-min ﬂow fairness in Logarithmic Time. In Proc. ofIEEE INFOCOM ’98, pages 1350–1377, March 1990.
[10] S. K. R. Srikant. A decentralized adaptive ECN marking
algorithm.
citeseer.nj.nec.com/487389.html[11] J. Mo and J. Walrand. Fair end-to-end window based congestion control. IEEE/ACM Trans. Networking, 8(5):556–
567, October 1999.
[12] R. Johari and D. Tan. End-to-end congestion control for theInternet: Delays and stability. 2001.
citeseer.nj.nec.com/johari01endtoend.html[13] F. Bonomi, D. Mitra, and J. B. Seery. Adaptive algorithms
for feedback-based ﬂow control in high-speed, wide-area
ATM networks. In IEEE Journal on Selected Areas in Communications, 13:1267–1283.
[14] D. Mitra. Optimal design of windows for high speed data
networks. In Proc. of IEEE INFOCOM ’90, pages 1156–
1163, 1990.

[1] M. Aida and K. Horikawa. Stability analysis for global performance of ﬂow control in high-speed networks based on
statistical physics. IEICE Transactions on Communications,
E82-B(12):2095–2106, December 1999.

Proceedings of the Sixth International Symposium on Autonomous Decentralized Systems (ISADS’03)
0-7695-1876-1/03 $17.00 © 2003 IEEE