Diffusion-Type Autonomous Decentralized Flow Control
for Open Networks
Chisa Takano† and 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.masaki@lab.ntt.co.jp

Abstract
In our previous studies, we have proposed diffusiontype ﬂow control for high-speed networks. The reason forproposing this type of control is that decision-making at
each node leads to high performance of the whole network
although each individual node handles its local trafﬁc ﬂow
only on the basis of the information it is aware of fromits immediately adjacent nodes. Our control method exhibits the desired stability and adaptability of network performance even when the network has an heterogeneous conﬁguration and the capacity of links is dynamically changed.
However, in order to make a comparison with other ﬂow
control methods under the same conditions, our evaluation used a closed network model, in which the number ofpackets was unchanged. This paper investigates the performance of our ﬂow control method using an open networkmodel, in order to show that our ﬂow control method is still
effective in more realistic networks. We identify the key issues associated with our ﬂow control in an open networkmodel, and demonstrate a solution.

1 Introduction
Delay in communication networks consists of processing
delay and propagation delay. Processing delay is the delay experienced prior to packet transmission and in waiting
for transmission at nodes. This is reduced if the processing
speed of the nodes is increased. Propagation delay is the delay experienced by a packet during propagation over a link
and is determined by the link length and the speed of light.
Unlike processing delay, the propagation delay is ﬁxed even
if the processing speed of the nodes is increased. So, if theprocessing speed of the nodes is high enough, propagation

delay becomes the dominant factor in the total delay.
In a high-speed network, it is impossible to implement
time-sensitive control based on collecting global information about the whole network because the state of a nodevaries rapidly in accordance with its processing speed although the propagation delay is constant. If we allow sufﬁcient time to collect network-wide information, the data sogathered is too old to apply to time-sensitive control. In thissense, each node in a high-speed network is isolated frominformation about the state of other nodes or of the overall
network.
In addition, when the propagation delay is dominant, at
any instant a large amount of data is being propagated overthe links in a high-speed network. Since we can only control
the packets stored in nodes, and not those being propagated,
high-speed networks contain many packets which cannot be
controlled because they are being propagated over links. In
this situation, since the control delay greatly affects the network performance, a very rapid control mechanism is required, in which the control delay is as short as possible.
This paper focuses on a ﬂow control mechanism forhigh-speed networks. From the above considerations, thetechnique used for our ﬂow control method should satisfy
the following requirements:• With regard to the collection of information, it must be
possible to collect the information used in the control
method.
• With regard to the delay in applying control, the control should take effect immediately.
There are many other papers reporting studies on the optimization of ﬂow control problems in a framework of solving linear programs [1, 2, 3, 4, 5]. These studies assume
the collection of global information about the network, but

Proceedings of the 24th International Conference on Distributed Computing Systems Workshops (ICDCSW’04)
0-7695-2087-1/04 $20.00 © 2004 IEEEit is impossible to realize such a centralized control mechanism in high-speed networks. In addition, solving these
optimization problems requires enough time to be available for calculation, and so it is difﬁcult to apply thesemethods to decision-making in a very short time-scale. So,
in a high-speed network, the principles adopted for timesensitive control are inevitably those of autonomous decentralized systems [6, 7].
Decentralized ﬂow control by end hosts, including TCP,
is widely used in current networks, and there is much research in this area [4, 5, 8]. However, since end-to-end or
end-to-node control cannot be applied to decision-making
in a time-scale shorter than the round-trip delay, it is inadequate for application to support decision-making in a very
short time-scale. In low-speed networks, a control delay ofthe order of the round-trip time (RTT) has a negligible effecton the network performance. However, in high-speed networks, the control delay greatly affects the network performance. This is because the RTT becomes large relative tothe unit of time determined by node’s processing speed, although the RTT is itself unchanged. This means that nodes
in high-speed networks experience a relatively larger RTT,
and this causes an increase in the sensitivity to control delay. To achieve rapid control in a shorter time scale thanthe RTT, it is preferable to apply control by the nodes rather
than by the end hosts.
We therefore have considered a control mechanism inwhich the nodes in a network handle their local trafﬁc ﬂows
themselves, based only on the information they are awareof. This mechanism can immediately detect a change in
the network state around the node and exert quick decisionmaking. However, decision-making at a local node leads toaction suitable for the local performance of the networks,
but it is not guaranteed that the action is appropriate for theoverall network-wide performance. So, the implementationof decision-making at each node cannot lead to optimum
performance for the whole network.
Bartal et al. [1] studied global optimization of ﬂow control using local information. The motivation for 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. Although this motivation is similar to that of our work, their study assumed thatthe distributed agents can obtain detailed information about
networks if we allow them sufﬁcient time to gather it. As
stated above, our standpoint is based on the fact that we cannot obtain detailed, useful and up-to-date information about
the whole network in a high-speed network environment.
In our previous studies, we investigated the behavior of
local packet ﬂows and the global performance when a node
is congested, and proposed a diffusion-type ﬂow control [9].
In addition, we investigated the stability and adaptability

temperature distribution

heat source

iron bar

Figure 1. Example of thermal diffusion phenomena.
of the network performance when the capacity of a linkis changed, by using network models with homogeneous[10] and inhomogeneous [11] conﬁgurations. Diffusiontype ﬂow control provides a framework in which the implementation of decision-making of each node leads to highperformance for the whole network. The principle of our
ﬂow control model can be explained through the following
analogy [12, 13].
When we heat a point on a cold iron bar, the temperature
distribution forms a normal distribution and heat spreads
through the whole as a diffusion phenomenon (Fig. 1). In
this process, the action in a minute segment of the iron bar
is very simple; heat ﬂows from the higher temperature side
towards the lower temperature side. The rate of heat ﬂow is
proportional to the temperature gradient. There is no communication between two distant segments of the iron bar.
Although each segment acts autonomously, based on its local information, the temperature distribution of the wholeiron bar exhibits orderly behavior. In diffusion-type ﬂow
control, each node controls its local packet ﬂow, which is
proportional to the difference between the number of packets in the node and those in an adjacent node. Then the
distribution of the number of packets in all the nodes in the
network becomes uniform over time. In this control mechanism, the state of the whole network is controlled indirectly
through the autonomous action of each node.
In our previous research on diffusion-type ﬂow control[9, 10, 11], we used a closed network model because withthis model the number of packets in the network is unchanged and it is appropriate for comparison with other control mechanism under the same conditions. In this paper, we
use an open network model for evaluation in order to showthat diffusion-type ﬂow control is applicable to more realistic networks. We identify the key issues in applying our
ﬂow control to an open network and show a solution forthem.

2 Preliminary Description of Diffusion-Type
Flow Control
We assume that a target ﬂow has a static route. In thecase of Internet-based networks, to guarantee end-to-end
Quality of Service (QoS) of a ﬂow, the QoS sensitive ﬂow
has a static route (e.g. RSVP). In addition, we assume allrouters in the network can employ per-ﬂow queueing for the
all target ﬂows.
Figure 2 shows the interactions between nodes (routers)

Proceedings of the 24th International Conference on Distributed Computing Systems Workshops (ICDCSW’04)
0-7695-2087-1/04 $20.00 © 2004 IEEE

packet stream
node
Ji-1
Ji
...
i+1
i
i-1
Fi
Fi-1
feedback...

Figure 2. Node interactions in our ﬂow control
model.
in our ﬂow control method, using a network model witha simple 1-dimensional conﬁguration. All nodes have two
incoming and two outgoing links, for a one-way packet
stream and for feedback information, that is, node i (i =1, 2, . . . ) transfers packets to node i + 1 and node i + 1
sends feedback information to node i. For simplicity, we
assume that packets have a ﬁxed length in bits.
All nodes are capable of receiving feedback information
from, and sending it to, adjacent downstream and up-stream
nodes, respectively. Each node i can receive feedback information sent from the downstream node i + 1, and can send
feedback information about node i itself to the upstream
node i − 1.
When node i receives feedback information from downstream node i + 1, it determines the transmission rate forpackets to the downstream node i + 1 using the received
feedback information, and adjusts its transmission rate towards the downstream node i + 1. The framework for node
behavior and ﬂow control is summarized as follows:

centralized control mechanism in the network. More precisely, it is impossible to realize centralized control in ahigh-speed network environment.
Next, we will explain the details of the diffusion-type
ﬂow control.
The transmission rate Ji (α, t) of node i at time t is determined by
Ji (α, t) = max(0, min(Li (t), J˜i (α, t))), and(1)˜Ji (α, t) = α ri (t − di ) − Di (ni+1 (t − di ) − ni (t)), (2)where Li denotes the value of the link capacity from node i
to node i + 1, ni (t) denotes the number of packets in node i
at time t, ri (t − di ) is the target transmission rate speciﬁedby the downstream node i + 1 as feedback information, anddi denotes the propagation delay between node i and nodei + 1.
In addition, ri (t − di ) and ni+1 (t − di ) are notiﬁed every
ﬁxed period τi+1 from the downstream node i + 1 with apropagation delay di . Parameters α (≥ 1) and Di (> 0)are constants and are the ﬂow intensity multiplier and the
diffusion coefﬁcient, respectively.
The diffusion coefﬁcient is chosen to be inversely proportional to the propagation delay [11] as follows:
Di = D1∝ (di )−1 ,di(3)• Each node i autonomously determines the transmission rate Ji based only on information it is aware of,that is, the feedback information obtained from thedownstream node i + 1 and its own feedback information.

where D is a positive constant.
The feedback information, Fi (t), created every ﬁxed period τi by node i consists of two quantities as follows:• The rule for determining the transmission rate is thesame for all nodes.

Node i notiﬁes this to the upstream node i − 1 with a periodof τi = di−1 . Here, the target transmission rate is determined as• 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 feedback information according to a predeﬁned rule and sends it to the
upstream node i − 1. Feedback information is createdperiodically with the ﬁxed interval τi .
• The rule for creating the feedback information is thesame for all nodes.
• Packets and feedback information both experience thesame propagation delay.
As mentioned above, the framework of our ﬂow control
model involves both autonomous decision-making by eachnode and interaction between adjacent nodes. There is no

Fi (t) = (ri−1 (t), ni (t)).

ri−1 (t) = Ji (1, t).

(4)

(5)

Moreover, the packet ﬂow Ji (t) in node i is renewed whenever feedback information arrives from the downstream
node i + 1 (with a period of τi+1 = di ).
To assist an intuitive understanding, we can brieﬂy explain the physical meaning of the diffusion-type ﬂow control. We replace i with x and apply continuous approximation. Then the propagation delay becomes di → 0 for all iand the packet ﬂow (2) is expressed as
˜ x, t) = α r(x, t) − D ∂n(x, t) ,
J(α,
∂x

(6)

and the temporal variation of the packet density n(x, t) may
be expressed as a diffusion-type equation,∂r(x, t)∂ 2 n(x, t)∂n(x, t)
= −α
+D
,
∂t
∂x
∂x2

Proceedings of the 24th International Conference on Distributed Computing Systems Workshops (ICDCSW’04)
0-7695-2087-1/04 $20.00 © 2004 IEEE(7)

node2

node30

node31

䊶䊶䊶

input

node59node60䊶䊶䊶Bottleneck link

outputFigure 3. Simulation Model˜ x, t)∂ J(α,∂n(x, t)
=−
.
∂t
∂x

(8)

That is, our method aims to perform ﬂow control using theanalogy of a diffusion phenomenon. We can expect excess
packets in a congested node to be distributed to the wholenetwork and normal network conditions to be restored aftersome time.

3 Applying Diffusion-Type Flow Control to
an Open Network Model
We have investigated the key issues involved in applying
the diffusion-type ﬂow control mechanism described in theprevious section to an open network model. Figure 3 shows
the open network model, with 60 nodes, which was used in
the simulations. Although the 1-dimensional model looks
simple, it represents a part of a network and describes thetarget end-to-end ﬂow for a path extracted from the wholenetwork. We represent the lengths of links as their delays,
and determine the length of each link according to a lognormal distribution, in advance, where the mean delay inthe network model is 1.0 [unit of time] and the variance is
5.2 [unit of time2 ].
The capacity of all normal links is Li = 100 [packets/unit of time] (i = 30) and the capacity of the bottleneck
link (between nodes 30 and 31) is L30 = 50 [packets/unitof time] (that is, this link has half the bandwidth of the otherlinks). To investigate the stability under congestion, in addition to the above conditions, we set the initial condition
for the congested node 30 as follows.
• Number of packets in node 30 at time t = 0: 400.
• The other 5600 packets are distributed randomly in theother nodes and on other links.
We set the values of parameters as:
D = 0.1, and αi = 1.0.

4000

2000

0

using the continuous equation(9)

At the ingress point of the network, the rate of packet ﬂow
is regulated by r0 (t) which is speciﬁed by node 1.
The left and right sides of Fig. 4 show the calculated results for the total number of packets being propagated on
all links and the total number of packets stored in all nodes

6000
Number of packets
stored in all nodes

node1

Number of packets
propagating on all links

6000

500

1000

1500
2000
unit time

4000

2000

0

500

1000

1500
2000
unit time

Figure 4. Total number of packets propagating on all links and stored in all nodes forthe diffusion-type ﬂow control described inSec.3.
of the network. The horizontal axes denote the simulation
time and the vertical axes denote the total number of packets
propagated on links and stored in nodes, respectively. The
total number of packets propagating on links indicates thetransmission efﬁciency of the network, and we call this thetotal throughput.
From the quantitative point of view, for the case where
the link capacity of the bottleneck links L30 = 50, the maximum value of the sustainable total throughput (the maximum number of packets propagated stably on the links)
is about 3000, i.e., 50 packets/link × 59 links. Thus,
the diffusion-type ﬂow control achieves about 100% of the
maximum value of the total throughput and its value is stable, but the total number of packets stored in nodes is large.
A large number of packets stored in nodes is undesirable
because it causes an increase in delay and packet loss.
This phenomenon was not observed in the closed network model. We can see from these results that it is necessary to regulate the packet ﬂow carefully, especially in the
open network model in which the total number of packets
in the network changes with time.

4 Diffusion-type Flow Control
Adapted to Open Network Model

Model

4.1 Extension of Flow Control model
In this section, we consider two extensions to the
diffusion-type ﬂow control model, to regulate the packet
ﬂow in the network. In the ﬁrst model, only the ingress
node uses its minimum value when calculating the packet
ﬂow rate. On the other hand, in the second model, all nodes
regulate the packet ﬂow rate less than or equal to the minimum value of link capacity among all the downstream links.
In both models, node i generates feedback information
Fi (t) asFi (t) = (ri−1 (t), ni (t), i (t)),(10)

and notiﬁes the information to the upstream node i − 1,
where i (t) denotes information about the maximum value

Proceedings of the 24th International Conference on Distributed Computing Systems Workshops (ICDCSW’04)
0-7695-2087-1/04 $20.00 © 2004 IEEE

J0 (α, t) = min(0 (t), r0 (t)).

(12)

Model 2 In Model 2, the packet transmission rate Ji (α, t)
and the feedback information ri−1 (t) are determined asJi (α, t) = max(0, min(i (t), J˜i (α, t))),ri−1 (t) = max(0, min(i (t), J˜i (1, t))) (i > 0),

(13)
(14)

where the transmission rate J0 (α, t) is determined as
Eq. (12).
A remarkable feature of Model 2 is that the maximum
values of Ji (α, t) and ri−1 (t) are bounded by i (t).
The difference between Model 1 and 2 is that the maximum values of Ji (α, t) and ri−1 (t) are bounded by i (t)at all nodes in the network in Model 2, although they arebounded by i (t) only at the ingress point in Model 1.

4.2 Evaluation for the two Extended Flow Control
Models
We compare the network performance of the diffusiontype ﬂow control models 1 and 2 described in Sec. 4.1 using the same network model as was used in Sec. 3, and we
discuss the stability of ﬂow control models in a high-speed
network environment.
Figures 5 and 6 show results for the ﬂow control models
1 and 2, where the horizontal axes denote the simulation
time and the vertical axes denote the total number of packets
in all links or nodes in the network.
We can see in Figs. 5 and 6 that the total number of packets in all links becomes stable at a high level of performancein both models.
However, there is a difference in the number of packets
stored in nodes. In Model 2, the total number of packets inall nodes is smaller than in the previous ﬂow control model
but become stable and does not decrease below 3000. In
Model 1, on the other hand, the total number of packets inall nodes decreases rapidly and falls to zero with time.

Number of packets
stored in all nodes

Model 1 When node i receives feedback informationfrom downstream node i + 1, it determines the transmission rate for packets to the downstream node i + 1, using
the received feedback information, and adjusts its transmission rate towards the downstream node i + 1. Then, thepacket transmission rate Ji (α, t) is determined by Eq. (1)and (2) in Model 1. The feedback information ri−1 (t) is
determined as Eq. (5).
This model calculates the transmission rate J0 (α, t) for
packets to ﬂow at the ingress to the network as follows:

6000

6000

4000

2000

0

500

1000

4000

2000

0

1500
2000
unit time

500

1000

1500
2000
unit time

Figure 5. Total number of packets propagating on links and stored in nodes for Model
1.
6000

6000
Number of packets
stored in all nodes(11)

Number of packets
propagating on all links

i (t) = min(Li , i+1 (t − di )).

Number of packets
propagating on all linksof available capacity as

4000

2000

0

500

1000

1500
2000
unit time

4000

2000

0

500

1000

1500
2000
unit time

Figure 6. Total number of packets propagating on links and stored in nodes for Model2.
Next, we compare the behavior of the packet distributionof the each node, in order to investigate the performance ofModel 1 and 2. Figures 7 and 8 show the simulation resultsfor Model 1 and Model 2, respectively. The horizontal axisof each graph denotes the node ID, the vertical axis denotes
the number of packets stored in the node, and t denotes thesimulation time (initially t = 0).
We can see from Fig. 7 that in Model 1 the number ofpackets stored in nodes decreases with time and is smoothly
distributed over the whole network. For Model 2, on theother hand, the number of packets stored in each node issmoothly distributed over a part of the network with timeand remains uneven over the whole network.
This difference arises because in Model 2 all nodes calculate the packet transmission rates using the minimum
value of link capacity from among the downstream links.
This restriction, which is imposed on calculating the rate,is too severe in Model 2. So, the transmission rates (determined by Eq. (13)) calculated in Model 2 differ greatly fromthe ideal rates (determined by Eq. (2)) which cause the diffusion phenomenon. Our results also show that the rule fordetermining the packet rate at a node, which is the most important feature of our ﬂow control, is crucially important forstability or adaptability of the whole network performance.

5 Conclusions
This paper has investigated the performance of diffusiontype ﬂow control applied to an end-to-end ﬂow. The
diffusion-type ﬂow control proposed in our previous studies
is an autonomous decentralized control, in which each nodein the networks handles its local trafﬁc ﬂow itself, based

Proceedings of the 24th International Conference on Distributed Computing Systems Workshops (ICDCSW’04)
0-7695-2087-1/04 $20.00 © 2004 IEEE

800

800

800

t=0
400
0

20

40

800

t=100
400
0

20

40

800

t=300
400
0

20

40

800

t=500
400
0

20

40

t=1000

t=700
400
0

400
20

40

0

20

40

Figure 7. Distribution of the number of packets stored in each node for Model 1.
800

800

800

t=0
400
0

20

40

800

t=100
400
0

20

40

800

t=300
400
0

20

40

800

t=500
400
0

20

40

t=1000

t=700
400
0

400
20

40

0

20

40

Figure 8. Distribution of the number of packets stored in each node for Model 2.
only on the information it is aware of. Our previous studies showed that, in the case of a closed network model, theaction of each node leads to desirable performance of thewhole network.
In order to show that our ﬂow control method is effective
for an end-to-end ﬂow as well, we simulated the applicationof our ﬂow control to an open network, and identiﬁed anissue. As a result of simulation, we found that regularizationof the ﬂow at the ingress to the network is important. Asa solution, we introduced an additional item of feedback
information and use it for ﬂow regularization at the ingresspoint, and simulated this using the two extended models.
Our results show that the rule for determining the packet
rate at a node, which is the most important feature of our
ﬂow control method, is also crucially important for the stability and adaptability of the whole network performance as
well.
In Model 1, the half-life period of the peak for the number of packets stored in nodes is about only 400 units oftime. For example, if the mean propagation delay of thelinks is 50 µs (corresponding to about 10 km in length), thestate of the whole network is completely restored in only 20
ms. As for the number of packets in a congested node, thehalf-life period of the peak is about 1.5 ms.
We are interested in the relationship between the lengthof the period for congestion restoration and the values ofparameters D and α in diffusion-type ﬂow control. Thisissue will be the subject of further study.

References[1] 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.
[2] S. H. Low and D. E. Lapsley,“Optimization
ﬂow control-I: basic algorithm and convergence,”
IEEE/ACM Transactions on Networking, vol. 7, no. 6,
pp. 861–874, 1999.
[3] K. Kar, S. Sarkar, and L. Tassiulas, “A simple rate
control algorithm for maximizing total user utility,” inProc. of IEEE INFOCOM 2001, pp. 133–141, 2001.

[4] J. Mo and J. Walrand, “Fair end-to-end window basedcongestion control,” IEEE/ACM Trans. Networking,vol. 8, no. 5, pp. 556–567, October 1999.
[5] S. Kunniyur and R. Srikant, “A decentralized adaptive
ECN marking algorithm,” in Proc. of IEEE GLOBECOM ’00, pp. 1719–1723, 2000.
[6] 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, vol. E82-B, no. 12,
pp. 2095–2106, December 1999.
[7] K. Horikawa, M. Aida, and T. Sugawara, “Trafﬁc control scheme under the communication delay of highspeed networks,” in Proc. of Int. Conf. on Multi-Agent
Systems (ICMAS) ’96, pp. 111–117, 1996.
[8] R. Johari and D. Tan, “End-to-end congestion control for the Internet: Delays and stability,” IEEE/ACM
Trans. Networking, vol. 9, no. 6, pp. 818–832, December 2001.
[9] 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), pp. 63–68, July 2002.
[10] C. Takano and M. Aida, “Stability and adaptability of
autonomous decentralized ﬂow control in high-speed
networks,” IEICE Transactions on Communications,vol. E86-B, no. 10, 2003.
[11] C. Takano, M. Aida and S. Kuribayashi, “On thestability of autonomous decentralized ﬂow control
in high-speed networks with asymmetric conﬁgurations,” in Proc. of IEEE ICDCS 2003 Workshop(ADSN 2003), pp. 56-62, Providence, RI, May 19,
2003.
[12] M. Aida and C. Takano, “Principle of autonomous decentralized ﬂow control and layered structure of network control with respect to time scales,” in Supplement of the ISADS 2003 Conference Fast Abstracts,
pp. 3-4, Pisa, Italy, April, 2003.
[13] M. Aida and C. Takano, “Principle of Diffusion-Type
Autonomous Decentralized Flow Control,” IEICE Society Conference, B-7-13, 2003.

Proceedings of the 24th International Conference on Distributed Computing Systems Workshops (ICDCSW’04)
0-7695-2087-1/04 $20.00 © 2004 IEEE