Stability of Autonomous Decentralized Flow Control Schemesin High-Speed Networks
Masaki Aida
NTT Information Sharing Platform LabsNTT Corporation
Musashino-shi 180-8585, Japanaida@mieice.org

Chisa Takano
Traffic Research Center
NTT Advanced Technology Corporation
2-4-15, Naka-cho, Musashino-shi 180-0006, Japanchisa@m.ieice.org

Abstract
This paper focuses on flow control in high-speed networks. Each node in the networks handles its local traffic
flow only on the basis of the information it knows, but it
is preferable that the decision-making of each node leads
to high performance of the whole network. To this end, weinvestigated the behavior of packet flow when a node is congested, and show an appropriate flow control model throughsimulation results.

1. Introduction
In a high-speed network, propagation delay becomes thedominant factor in the transmission delay because the speedof light is a non-scaling factor and is an absolute constraint.
Therefore, at a given time, a large amount of data is being
propagated on links in the network (Fig. 1). The amountof this data is characterized by the delay-bandwidth product, i.e., the propagation distance times transmission rate.
Therefore, in high-speed and/or long-distance transmission,
there is more data on links than in nodes.
Figure 2 shows an example of how much data can be ona link. Let us consider the situation involving data transmission between two nodes, a distance of 1 km apart with a linkspeed of 1 Mbps. If the transmission speed is increased to
1 Gbps, the amount of data on the link is equivalent to thaton 103 km of a 1-Mbps link. And, if the transmission speed
is increased to 1 Tbps, the data amount is equivalent to 106
km of a 1-Mbps link. This distance is about 2.5 times the
distance between the earth and the moon. Consequently, it
is impossible to exert time-sensitive control based on collecting global information about the network. So, in a highspeed network, the frameworks of time-sensitive control areinevitably autonomous decentralized systems [1, 2, 3].
This paper focuses on back-pressure type flow control

packetlow-speed
network

AAAAAAAAAA
node

link

node
packethigh-speed
network

AAAAAAAAAA
AAAAAAAAAA
link
nodeAAAAAAAAAA
node

Figure 1. Large delay-bandwidth product.

in networks in which nodes handle their local traffic flow
themselves based only on the information they know. It is,of course, preferable that the decision making of each nodeleads to high performance of the whole network. In flow
control, we use the total throughput of a network as a global
performance measure. We investigate the behaviors of local
packet flow and the global performance measure when anode is congested, and show an appropriate flow control
model through simulation results.
Related issues on global optimization of flow control byusing local information have been studied. For windowbased flow control, the optimization problems of some aggregated utility function have been studied in [5, 6]. For theconnection-oriented networks, bandwidth assignment problems for each source by optimizing some end-end utility
function have been studied in [2, 4]

2. Models
2.1. Performance Measure
Each packet in a network is either in a node or on a link.
Since the packets stored in nodes at the present are not beingtransmitted by the networks, it is natural to define the total
throughput of the network as a global performance measurestream node i + 1, it determines the transmission rate forpackets to downstream node i + 1 using the obtained node
information and adjusts its transmission rate to downstream
node i + 1. The framework of node behaviors and flow control is summarized as follows:

1 Mbps
node

node

1 km

node

node

1000 km
1 Mbps

=
node

Seoul
1 Mbps=node

1 Tbps
1 km

Tokyo

~
~

1 Gbps

node

~
~

node

1 km

6

node

10 km

node

5

3.8 x 10 km

moon

earth

Figure 2. Example of delay-bandwidth product.

packet stream...

JJAAA AAAAA
AAAAA
AA
AA
AA
AAAi-1AAAAA i AA
AAAAAi+1
AA
AA
i-1

i

...

feedback

Figure 3. Network model.

as follows. We define the total throughput of a network attime t as being the amount of data being propagated on the
network [1, 3, 5]. 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 areones stored in nodes and not ones being propagated. Thus,
higher performance of all the networks involves many uncontrollable packets being propagated on links. Therefore,
inappropriate flow control cannot produce the state that has
high performance and stability.

• Each node i autonomously determines the transmission rate Ji based only on information it knows, 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 predefined 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 flow 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 flow control schemes, applied for different
processes used to determine the transmission rate.

3. Preliminary Description of Flow Control
2.2. Network and Flow Control Models
3.1. Packet Flow
Our network model has a simple 1-dimensional configuration (Fig. 3). All nodes have two incoming links and twooutgoing ones for a one-way packet stream and feedback,that is, node i (i = 1, 2, 3, . . .) transfers packets to nodei + 1 and node i + 1 sends feedback information (node information) to node i. For simplicity, we assume that packets
have a fixed length in bits.
All nodes are capable of receiving and sending node
information from/to adjacent downstream and upstream
nodes, respectively. Node information is sent from downstream node i + 1 to upstream node i. In addition, eachnode i can send its node information to the upstream nodei − 1.
When node i receives node information from down-

In this paper, we focus on the stability of flow control in
the congested state, and we consider packet flow in a heavytraffic environment. In this situation, we let the packet flow
be Ji if the transmission rate specified by node i is Ji . Thisis because node i has sufficient packets to transfer. Hereafter, we identify the packet flow with the transmission rate
specified by the node.
We define the packet flow as
Ji := ri − D (ni+1 − ni ),(1)

where ni (t) denotes the number of packets in node i at timet, ri is the rate sent by downstream node i + 1 as node information, and D (D ≥ 0) is a constant. In addition, we callthe first and second terms of the right hand side of Eq. (1)drift and diffusion terms, respectively.
If there is no packet loss in the network, the temporalvariation of ni (t) is expressed asni (t + 1) − ni (t) = Ji−1 (t − 1) − Ji (t).

(2)

Here, we let the propagation delay between adjacent nodes
be 1, for simplicity.
To estimate the temporal variation roughly, we replace iby x and apply continuous approximation. The packet flow
is expressed as∂n,(3)
J = r(x) − D∂xand the temporal variation of the number of packets at x is
expressed as
∂n
∂r
∂2n
=−
+D 2,
(4)
∂t
∂x
∂x
by using the continuous equation
∂n ∂J
+
= 0.
∂t
∂x

(5)

That is, our method aims at performing a flow control by
the analogy of a diffusion phenomenon.
Hereafter, we consider two types of flow control andcompare them. One type handles the drift term and the othercontrols the diffusion term of Ji ,3.2. Drift-Term Driven Flow Control and Stability

Conversely, if we use the rate specified to the upstream
node as(8)ri−1 > ri ,then ni (t) increases with respect to time (when there aremany packets in the upstream node). But the buffer ineach node has a finite capacity, so this strategy describedby Eq. (8) cannot be used continuously either.
If we set the rate specified to the upstream node as
ri−1 = ri ,(9)then ni (t) does not change with respect to time under theheavy traffic 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) cannot be used continuously either.
From the above considerations, we choose the following
strategy. The rate specified from node i to the upstream
node i − 1 is determined by according to the state of nodei. Let the objective of ni be ns . If ni > ns , then ri−1 isspecified by using Eq. (7); if ni < ns , then ri−1 is specified
by using Eq. (8); and if ni = ns , then ri−1 is specified byusing Eq. (9).
Since the above flow control do not use the diffusion
term, we call it drift-term driven flow control in this paper.

3.3. Diffusion-Term Driven Flow Control and Stability

In this subsection, we set D = 0 in Eqs. (1) and (3), andinvestigate the characteristics of the flow control scheme
whose packet flow is determined only by the drift term.
Let the number of packets in the network be N . To obtain higher network performance, flow control should enable the state in which many packets are being propagatedon links. This state corresponds to the state that has fewer
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 be

In this subsection, we set D > 0 in Eqs. (1) and (3), andinvestigate the characteristics of the flow control scheme
whose packet flow is determined by both drift and diffusion
terms.
From the stability of the drift-term driven flow control,
we set(10)ri−1 = Ji ,ni (t + 1) − ni (t) < 0.

Applying the continuous approximation to this equation, we
have
∂n
∂2n
= D 2.
(12)∂t∂xThis is the diffusion equation. It implies the feasibility of
the following flow control. In the drift-type control D = 0,
the flow control described by Eq. (9) cannot change ni (t)and it is difficult to recover from congestion. However, for
D > 0, since we can control the diffusion term, we expect
packets in the congested node to be distributed to the wholenetwork and normal network conditions to be restored aftersome time.

(6)

From Eq. (2) and D = 0, this strategy means that node i
notifies a smaller rate to the upstream node i − 1 than therate notified by the downstream node,ri−1 < ri .

(7)

However, if all nodes use this strategy, then the total
throughput decreases with respect to time as a result. Therefore, the strategy described by Eq. (7) cannot be used continuously.

as in Eq. (9). Then, Eq. (2) is written asni (t + 1) − ni (t) = D (ni+1 − 2ni + ni−1 ).

(11)congested
nodenarrow
bandwidth

AA
AAAA
AA

...

1

29

30

31

400

t=0

300

...

200

60
100

Figure 4. Network model with a bottlenecked
link.

0
1

5

9

13

17

21

25

29

33

37

41

45

49

53

57

49

53

57

49

53

57

49

53

57

53

57

400

t = 10300

In this control scheme, node i’s packet transmission rate
to the downstream node i + 1 is determined as
Ji = ri − D (ni+1 − ni ),(13)

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

(14)

In this framework, node information of i specified to the
upstream node i − 1 is a pair of values (ri−1 , ni ).
Since the above flow control uses the diffusion term, wecall it the diffusion-term driven flow control in this paper.

200

100

0
1

5

9

13

17

21

25

29

33

37

41

45

300

t = 30
200

100

0
1

5

9

13

17

21

25

29

33

37

41

45

t = 80

200

100

0
1

4. Evaluations

5

9

13

17

21

25

29

33

37

41

45

t = 120100

In this section, we consider a simple network model witha bottlenecked link and compare the performance of the twodifferent flow controls described in the previous sections.

4.1. Simulation Model
Figure 4 shows our network model, which is a closed
network with a 1-dimensional configuration and toroidal
boundary. The network has a congested node and a bottlenecked 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, 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
• Propagation delay between adjacent nodes: 1 (unittime)• Index of the congested node: i = 30

0
1

5

9

13

17

21

25

29

33

37

41

45

49

Figure 5. Temporal variation of the number ofpackets in each node for a drift-term driven
flow control scheme.

• Total number of packets in the network: N = 6000
• Maximum number of packets on a link (except the bottlenecked link): 100• Maximum number of packets on the bottlenecked link
(between nodes i = 30 and 31): 50(that is, half the capacity of other links and the same
distance)
To investigate the stability under congestion, in addition to
the above conditions, we set the initial condition for congested node i = 30 as follows.
• Number of packets in node i = 30 at time t = 0: 400• The other 5600 packets are randomly configured inother nodes and on other kinks.

Total throughput (number of packets on links)

400

t=0

300

200

100

0
1

5

9

13

17

21

25

29

33

37

41

45

49

53

57

300

5000
drift-term driven control
diffusion-term driven control

4000

3000

2000

1000

t = 10
200

0
0
100

20

40

60

80

100

120

140

160

180

200

Time t

0
1

5

9

13

17

21

25

29

33

37

41

45

49

53

57

49

53

57

49

53

57

Figure 7. Temporal behavior and stability ofthe total throughput of the network for two
different flow control schemes.

200

t = 30
100

0
1

5

9

13

17

21

25

29

33

37

41

45

t = 80100

4.3. Diffusion-Term Driven Flow Control Scheme

0
1

5

9

13

17

21

25

29

33

37

41

45

t = 120

100

0
1

5

9

13

17

21

25

29

33

37

41

45

49

53

57

Figure 6. Temporal variation of the numberof packets in each node for a diffusion-term
driven flow control scheme.

4.2. Drift-Term Driven Flow Control Scheme
As a model for the drift-term driven flow control, we
set an objective for the number of packets in a node to bens = 60, and set the following transmission rate and node
information.
Ji = min(ri , Li ), Ji × 0.9
Ji × 1.0
ri−1 =
Ji × 1.1(15)(ni > ns ),(ni = ns ),(ni < ns ),We set D = 0.1 in Eqs. (13) and (14), and use the following flow control model.
 Li , (ri − D (ni+1 − ni ) > Li ),0, (ri − D (ni+1 − ni ) < 0),
(17)
Ji =

ri − D (ni+1 − ni ), (otherwise),ri−1 = Ji .
(18)
Figure 6 shows the simulation result for the diffusion-term
driven flow control model using the same initial condition
as described in Fig. 5. The horizontal axis of each graphdenotes the node id and the vertical axis denotes the numberof packets stored in the node.
The number of packets in congested node i = 30 decreases with time, and most of the nodes have fewer packets
than in the drift-term driven flow control model at t = 120.

4.4. Stability of Flow Control and Network Performance(16)

where Li denotes the link capacity between nodes i and i +1.
Figure 5 shows the simulation result for the drift-term
driven flow control model. The horizontal axis of eachgraph denotes node id and the vertical axis denotes the number of packets stored in the node. In addition, t denotes thesimulation time and initially t = 0.
The number of packets in congested node i = 30 decreases with time, and all nodes have around 100 packets
at t = 120. Each node has the objective ns = 60, so thestrategy of each node is a failure as a result.

From the simulation results for the drift- and diffusionterm driven control models, we compare the total throughput of the network. Figure 7 shows the total throughput for
both models. The horizontal axis denotes the simulation
time and the vertical axis denotes the total throughput (thetotal number of packet being propagated on links).
For the drift-term driven control models, the total
throughput decreases with time. This means that the flow
control model inappropriately influences the global performance of the network. If all nodes achieve their objective of
Ns = 60, the total 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-term driven control
models, the total throughput decreases with time but becomes stable around 2400. From the link capacity of thebottlenecked link, the maximum value of the sustainable total throughput (the number of packets being propagated on
links stably) is 3000, i.e., 50 packets/link × 60 links. Thus,
the drift-term driven flow control achieves 80total throughput and its value is stable.
If we can choose an appropriate value of the objective
ns for the drift-term driven flow control, the total throughput maybe stable. However, the value should depend on
the bandwidth of the bottlenecked link. Since nodes cannot know information about the bandwidth in a high-speed
network environment, the drift-term driven control cannot
achieve high performance. In the diffusion-term driven control model, although no nodes know the bandwidth of thebottlenecked link, high performance is achiieved.

5. Conclusions
This paper presented a framework for flow control inhigh-speed networks as an autonomous decentralized system. We showed two typical back-pressure type flow control models based on the framework. The drift-term driven
flow control handles the drift term of the packet flow andthe diffusion-term driven flow control handles the diffusion
term of the packet flow. For both controls, nodes handle
their local traffic flow themselves based only on the information they know.

To investigate the behaviors of local packet flow and theglobal performance measure when a node is congested, we
compared two models through simulations. For comparison, we useed the total throughput for the flow control performance measure. The diffusion-term driven flow control
adaptively achieves high performance and it is stable in congested situations.

References[1] M. Aida and K. Horikawa. Stability analysis for global performance of flow control in high-speed networks based on
statistical physics. IEICE Transactions on Communications,
E82-B(12):2095–2106, December 1999.
[2] Y. Bartal, J. Byers, and D. Raz. Global optimization using
local information with applications to flow control. In Proc.
of the 38th Ann. IEEE Symp. on Foundations of Computer
Science, October 1997.
[3] K. Horikawa, M. Aida, and T. Sugawara. Traffic 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] S. H. Low and D. E. Lapsley. Optimization flow control-i:
basic algorithm and convergence. IEEE/ACM Transactions
on Networking, 7(6):861–874, 1999.
[5] D. Mitra. Optimal design of windows for high speed data
networks. In Proc. of INFOCOM ’90, pages 1156–1163.
[6] J. Mo and J. Walrand. Fair end-to-end window based congestion control. IEEE/ACM Trans. Networking, 8(5):556–567,
October 1999.