IEICE TRANS. COMMUN., VOL.E91–B, NO.9 SEPTEMBER 2008

2828

PAPER

IEICE/IEEE Joint Special Section on Autonomous Decentralized Systems Theories and Application Deployments

Parameter Design for Diﬀusion-Type Autonomous Decentralized
Flow Control
Chisa TAKANO†a) , Keita SUGIYAMA†† , and Masaki AIDA†† , Members

SUMMARY
We have previously proposed a diﬀusion-type flow control mechanism as a solution for severely time-sensitive flow control required for high-speed networks. In this mechanism, each node in a network manages its local traﬃc flow using the basis of only the local information directly available to it, by using predetermined rules. In addition,
the implementation of decision-making at each node can lead to optimal
performance for the whole network. Our previous studies show that our
flow control mechanism with certain parameter settings works well in highspeed networks. However, to apply this mechanism to actual networks, itis necessary to clarify how to design a parameter in our control mechanism. In this paper, we investigate the range of the parameter and derive its
optimal value enabling the diﬀusion-type flow control to work eﬀectively.
key words: flow control, autonomous decentralized control, diﬀusion equation, high-speed networks

1.

Introduction

A high-speed network has been constructed with rapid
spread of the Internet and expanding demand for services inrecent years. In such a high-speed network, the fast and flexible network control is required so that various application
users can be provided with stable Quality of Service (QoS)
and the limited network resource can be used eﬀectively.
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. This is because
the propagation delay is constrained by the speed of lightand is the same as in slower networks although the processing speed of each node is high in high-speed networks. If
we allow suﬃcient time to collect network-wide information, the data so gathered is too old to use for time-sensitive
control. In this sense, each node in a high-speed network isisolated from up-to-date information about the state of othernodes or that of the overall network.
This paper focuses on a flow control mechanism forhigh-speed networks. From the above considerations, thetechnique used for our flow control method should satisfy
the following requirements: (i) it must be possible to collectthe information required for the control method, and (ii) thecontrol should take eﬀect immediately.
Manuscript received December 28, 2007.
Manuscript revised April 18, 2008.
†
The author is with the Graduate School of Information Sciences, Hiroshima City University, Hiroshima-shi, 731-3194 Japan.
††
The authors are with the Graduate School of System Design,
Tokyo Metropolitan University, Hino-shi, 191-0065 Japan.
a) E-mail: takano@hiroshima-cu.ac.jp
DOI: 10.1093/ietcom/e91–b.9.2828

Fig. 1

Example of thermal diﬀusion phenomena.

There are many other papers reporting studies on flow
control optimization in a framework of solving linear programs [1]–[5]. These studies assume the collection of
global information about the network, but it is impossible toachieve such a centralized control mechanism in high-speed
networks. In addition, solving these optimization problems
requires enough time to be available for calculation, so it
is diﬃcult to apply these methods to decision-making ona very short timescale. Therefore, in a high-speed network, the principles adopted for time-sensitive control areinevitably those of autonomous decentralized systems.
For the time-sensitive autonomous decentralized flow
control, we considered a new control mechanism, diﬀusiontype flow control (DFC) [6]–[9] in which the nodes in a network handle their local traﬃc flows themselves, based only
on the local information directly available to them. In thismechanism, each node can immediately detect a change in
the network state around the node and apply quick decisionmaking.
The most remarkable characteristic of DFC is that itprovides a framework in which the implementation of thedecision-making of each node leads to high and stable performance for the whole network. To explain the basis of
this framework, we show the principle of our flow control
model through the following analogy [8]. When we heat apoint on a cold iron bar, the temperature distribution follows
a normal distribution and heat spreads through the whole bar
by diﬀusion (Fig. 1). In this process, the action in a minutesegment of the iron bar is very simple: heat flows from thehotter side towards cooler side. The rate of heat flow 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 whole ironbar exhibits orderly behavior. In DFC, each node controls
its local packet flow, which is proportional to the diﬀerence
between the number of packets in the node and that in an
adjacent node. Thus, the distribution of the total number ofpackets in a node 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 eachc 2008 The Institute of Electronics, Information and Communication Engineers
Copyright TAKANO et al.: PARAMETER DESIGN FOR DIFFUSION-TYPE AUTONOMOUS DECENTRALIZED FLOW CONTROL

2829

node.
Our previous studies show that our flow control mechanism with certain parameter settings works well in highspeed networks. However, to apply DFC to actual networks,
it is necessary to clarify how to design parameters in ourcontrol mechanism. This is one of central issues to be solved
for applying DFC to actual networks. In this paper, we investigate the range of the parameter and derive its optimalvalue enabling the DFC to work eﬀectively. This paper isorganized as follows. In Sect. 2, we show the aim of the
DFC in layered structure of network control with respect totimescale. In Sect. 3, we briefly summarize the mechanismof DFC. In Sect. 4, we clarify how to design the parameter in our control mechanism. The validity of the parameter
design is verified in Sect. 5 by using simulation studies. Finally, Sect. 6 shows conclusions.
2.

Fig. 2 Classification of various control mechanisms with respect to theireﬀective timescales.

Aim of Diﬀusion-Type Flow Control Mechanism

Network control mechanisms in networks can be categorized by the timescales on which an individual control takes
eﬀect and they form a layered structure with respect to thetimescales. Individual control mechanisms work well on
their appropriate timescales and they cooperate with eachother. Figure 2 shows the comparison of diﬀerent types ofcontrol according to such a classification. For example, therouting and signaling (e.g. session initiation protocol (SIP))
respectively fall into the long and medium timescales. Individual control mechanisms work well for their appropriate
timescales and they cooperate with each other for supportinguser applications. TCP is a typical decentralized flow control by end hosts [10], and is widely used for reliable communications in current networks. Window flow control such
as TCP acts in the timescale of the round-trip time (RTT).
End-to-end or end-to-node control cannot be applied
to decision-making on a timescale shorter than the RTT. Indeed, in low-speed networks, a control delay on the orderof the RTT has a negligible eﬀect on the network performance. However, in high-speed networks, the control delay
greatly aﬀects the network performance. This is because the
RTT becomes large relative to the unit of time determinedby node’s processing speed, although the RTT is itself unchanged. This means that nodes in high-speed networks experience a larger RTT, and this causes an increase in the sensitivity to control delay. This is a significant reason that theperformance of TCP should be sensitive with respect to network condition, and a lot of extensions of TCP have been
proposed for high-bandwidth or long-distance connections[11]–[16].
Let us consider the network conditions that the bandwidth and/or the distance of communications become(s)larger. If the performance characteristics concerning packet
loss of its bearer network are little aﬀected by this condition, we can expect that TCP would not enter the congestion
avoidance phase and that high network performance would
be achieved. To achieve such a stabilization mechanism,
it is necessary to implement a time-sensitive control mecha-

Fig. 3Layered structure of behaviors with respect to timescales.

nism in the bearer network and to make the network have robust performance characteristics. Since end-to-end or endto-node control cannot be applied to decision-making on atimescale shorter than the RTT, it is inadequate to support
decision-making on a very short timescale.
To achieve rapid control on a shorter timescale than the
RTT, it is preferable to apply control by the nodes rather
than by the end hosts. DFC is a node-by-node control and its
target is a timescale shorter than the RTT. The aim of DFC
is not direct guarantee of user QoS, but DFC serves stablenetwork behaviors to other controls of the longer timescales.
In this sense, DFC brings its ability in the background ofother controls of the longer timescales. In other words, DFC
enables other controls of the longer timescales to work welleven if the speed of the networks becomes high.
Figure 3 shows a sequence of human behavior as ananalogy. When an accident occurs, we immediately act
to guard ourselves. This action is time-sensitive and isachieved by a spinal reflex. After that, essential treatment is performed through cerebration on a relatively longtimescale. As well as the relation of the cerebrationand spinal reflex, network control mechanisms of diﬀerent
timescales act on their own timescales and, as a result, they
cooperate with each other to support user applications.
3.

Preliminary

3.1 Diﬀusion-Type Flow Control Mechanism
In the case of Internet-based networks, to guarantee end-toend QoS of a flow, the QoS-sensitive flow has a static route(e.g., RSVP). Thus, we assume that a target flow has a static
route. In addition, we assume all routers in the network can
employ per-flow queueing for all the target flows† . All flows
are in the same priority class and it is desirable that all active
flows share the link bandwidth fairly.
In DFC, each node controls its local packet flow au-

IEICE TRANS. COMMUN., VOL.E91–B, NO.9 SEPTEMBER 2008

2830
j
j
j
Ji (t) = max(0, min(Li (t), J˜i (t))), andJ˜j (t) = r j (t − di ) − Di (n j (t − di ) − n j (t)),
iFig. 4

Node interactions in our flow control model.

tonomously. Figure 4 shows the interactions between nodes(routers) in our flow control method, using a network modelwith a simple 1-dimensional configuration. 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 Fi+1 to node i. For simplicity,
we assume that packets have a fixed length in bits.
All nodes are capable of receiving feedback information from the adjacent downstream nodes, and sending it to
the adjacent upstream nodes. Each node i can receive feedback information sent from the downstream node i + 1 andcan send feedback information about itself to the upstream
node i − 1.
When node i receives feedback information fromdownstream node i + 1, it determines the transmission rate
for packets to the downstream node i + 1 using the received
feedback information, and it adjusts its transmission rate towards the downstream node i + 1.
Assume that there are Mi flows sharing the link between node i and i + 1, and they are identified by j ( j =1, 2, . . . , Mi ). The framework for node behavior and flow
control for flow j is summarized as follows:• Each node i autonomously determines the transmission
rate Jij for flow j on the basis of only the local information directly available to it, that is, the feedback information obtained from the downstream node i + 1 andits own feedback 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 Jij .
(If there are no packets for flow j in node i, the packet
transmission rate is 0.)• Each node i autonomously creates feedback information according to a predefined rule and sends it to the
upstream node i − 1. Feedback information is createdperiodically with a fixed interval τi .
• The rule for creating the feedback information is thesame for all nodes.
• Packets and feedback information both experience thesame propagation delay.

i

i+1

i

(1)
(2)

where Lij (t) denotes the available bandwidth for flow j of
the link from node i to node i + 1 at time t, nij (t) denotes
the number of packets belonging to flow j in node i at timet, rij (t − di ) is the notified rate for flow j by using feedback
information from the downstream node i + 1, and di denotes
the propagation delay between nodes i and i + 1.
The way to determine Lij (t) is explained. Let the bandwidth of the link from node i to node i + 1 be Bi , and Lii (t),the available bandwidth for flow j is to assume that the bandwidth Bi is shared by flow with a weight J˜ij (t) [17], that is,J˜j (t)Lij (t) = Bi  M i j .
i˜
j=1 Ji (t)(3)

This rule means that a flow with larger J˜ij (t) can get alarger transmission rate and can transmit a larger volume of
traﬃc to the downstream node. Thus, the transmission rates
of other flows are regulated to be smaller.
j(t − di ) are reported from
In addition, rij (t − di ) and ni+1
the downstream node i + 1 as feedback information withpropagation delay di . Parameter Di is chosen to be inversely
proportional to the propagation delay [7] as follows:
Di =

D
,
di

(4)

where D (> 0), which is a positive constant, is the diﬀusion
coeﬃcient.
The feedback information for flow j created every fixed
period τi by node i consists of the following two quantities:j
Fij (t) = (ri−1(t), nij (t)).

(5)

Node i reports this to the upstream node i − 1 with a periodof τi = di−1 . Here, the target transmission rate for flow j isdetermined asjri−1(t) = Jij (t).

(6)

Moreover, the transmission rate Jij (t) for flow j in node i
is renewed whenever feedback information arrives from thedownstream node i + 1 (with a period of τi+1 = di ).
To enable an intuitive understanding, we briefly explain
the physical meaning of DFC. We replace i with x and apply
a continuous approximation. Then the propagation delay
becomes di → 0 for all i and the transmission rate (2) forflow j is expressed as∂n (x, t),J˜j (x, t) = r j (x, t) − κ∂xj

As mentioned above, the framework of our flow control
model involves both autonomous decision-making by eachnode and interaction between the adjacent nodes. There isno centralized control mechanism in the network.
Next, we explain the details of DFC. The transmission
rate Jij (t) for flow j of node i at time t is determined by(7)

where κ is a diﬀusion coeﬃcient corresponding to D in DFC.
†
The assumption of per-flow queueing is for simplicity of explanations of DFC mechanism. The requirement of “per-flow” canbe relaxed to “per input-port” of a router.

TAKANO et al.: PARAMETER DESIGN FOR DIFFUSION-TYPE AUTONOMOUS DECENTRALIZED FLOW CONTROL

2831

Since κ has an important meaning, a later section explains
this parameter. The temporal evolution of the packet density
n j (x, t) may be represented by a diﬀusion-type equation,∂r j (x, t)∂2 n j (x, t)∂n j (x, t)
=−
+κ
,
∂t
∂x
∂x2

(8)

using the continuous equation∂n j (x, t)∂ J˜j (x, t)
=−
.
∂t
∂x

(9)

As explained in Sect. 1, our method aims to perform
flow control using the analogy of diﬀusion. We can expect
excess packets in a congested node to be distributed over thewhole network and expect normal network conditions to berestored after some time.
In addition to the above framework, we consider theboundary condition of the rule for determining the transmission rate in the DFC.
Here we consider the situation where nodes and/or end
hosts in other networks do not support the DFC mechanism.
We call the nodes and/or end hosts that are connected directly to the ingress node in our network external nodes. We
only assume that the external nodes have a traﬃc shaping
function, that can adjust the transmission rate by queueing
to the requested rate reported by the downstream node. Thatis, an external node 0 cannot calculate the transmission rate
J0j (t) for flow j using (2), but can adjust its transmission rate
to r0j (t − d0 ) for flow j, which was reported by node 1.
We consider a rule for determining r0j (t) as a boundary
condition. Node 1 can calculate J0j (t) if we assume that the
number of packets stored in the external node is i = 0. The
target rate r0j (t) for flow j, reported by node 1, is created as
J˜0j (t) with the above assumption. That is,
r0j (t) := J˜0j (t + d0 ) = J1j (t) − D0 n1j (t).

(10)

This quantity can be calculated just from information known
to node 1.
It is worth to note that the packet rate of (2) is “nonwork-conserving,” in general. If each node acts as “workconserving,” many packets are concentrated at congested
nodes and it causes packet losses. Although each node autonomously determines its packet rate, DFC nodes cooperate to work to avoid the concentration of packets. Noticethat “non-work-conserving” does not mean the degradationof the utilization of networks. Even if a node transmits thepackets at “work-conserving” rate, they are stored at thecongested node but are not transferred to their destinations.
4.

Parameter Design

4.1 Approach
In DFC, there is a important parameter, the diﬀusion coeﬃcient D. The diﬀusion coeﬃcient governs the speed ofdiﬀusion. In physical diﬀusion phenomenon, larger κ in (8)causes faster diﬀusion. If DFC model is completely corresponding to physical diﬀusion phenomenon, a large valueof D is suitable for fast recovery from congestion. Unfortunately, DFC is not completely corresponding to physicaldiﬀusion and too large value of D in DFC prevents diﬀusion phenomenon in networks. Conversely, too small valueof D causes very slow diﬀusion, and this means that stolid
congestion recovery wastes much time.
In this section, we determine an appropriate value of
D. Our approach to design a value of D is simple. We takea larger value of D in the range of values in which diﬀusion
can occur in networks.
In the subsequent subsections, we discuss the following
issues in order to determine the appropriate range of D.
• To determine the range of κ in which diﬀusion eﬀect
can occur for discrete space and discrete time.
• To determine the range of D in which diﬀusion can occur in networks, under the situation that all the links in
networks have same length.
• To verify the above range of D is applicable to generalsituations that the length of links in networks diﬀerent,in general.
For the first issue, we introduce the diﬀerence equation,
which is corresponding to the diﬀusion equation with the parameter κ, and consider the range of κ. Next, for the second
issue, we consider the close relation between the range of κand the range of D. For the last issue, deriving the dimensionless property of D, we show the range of D is independent of the link length.
4.2 Range of Diﬀusion Coeﬃcient under Homogeneous
Network Configurations
The partial diﬀerential Eq. (8) describes temporal evolutionof packet density in continuous approximation of networks.
The first term on the right-hand side in (8) describes a stationary packet flow, and this is not concerned to diﬀusion.
The second term is essential in diﬀusion. Thus, we consider
the following partial diﬀerential equation,∂2 n j (x, t)∂n j (x, t)
=κ
,
∂t
∂x2

(11)

where this is the ordinary diﬀusion equation.
Of course, the structure of networks are not continuous.
In addition, timing of control actions is not continuous. The
behavior of DFC is described by a diﬀerence equation rather
than the diﬀerential equation. In other words, DFC makenetworks solve a diﬀerence equation with discrete space x
and discrete time t.
To introduce a discrete space reflecting the network
structure, we divide the continuous 1-dimensional space intoa length of Δx. In addition, for simplicity, we assume all thelinks in networks have same length. Since we set di = τi+1 ,this means the interval of DFC’s actions is the same for allnode, and we denote it as Δt. The diﬀerence equation corresponding to (11) is as follows:IEICE TRANS. COMMUN., VOL.E91–B, NO.9 SEPTEMBER 20082832

n j (x, t + Δt) − n j (x, t)Δtn j (x + Δx, t) − 2 n j (x, t) + n j (x − Δx, t)
=κ
.
(Δx)2

(12)

If the solution of (12) exhibits similar behavior to that of(11), DFC appropriately works and diﬀusion of packet density occurs. Our issue is to find appropriate value of D in
which the solution of (12) exhibits diﬀusion phenomenon.
Let node position in 1-dimensional configuration be xk(xk+1 − xk = Δx; k = 0, 1, . . . , S ), and time of DFC’s action
be t (t+1 − t = Δt;  = 0, 1, . . . , T ). We take the boundary
condition,n j (x0 , t) = n j (xS , t) = 0.

(13)

If behavior of n j (xk , t ) exhibits a diﬀusion eﬀect with time,
lim n j (xk , t ) = 0,

(14)

→∞

for all k.
In general, n j (xk , t ) satisfying (13) is represented as
the following Fourier series,n j (xk , t ) =∞

nmj (xk , t ),jnmj (xk , t ) = Am,
sin


kmπ
,
S

(15)

(16)

j
is a time-dependent coeﬃcient. If (14) is valid
where Am,in any cases,

lim nmj (xk , t ) = 0

→∞

(17)
4.3 Parameter Design of DFC and Dimensional Analysis

for all non-negative integers m. By substituting (16) into
(12), we have
4 κ Δt 2 m π
j
j
,
(18)
= Am,sin
1−Am,+12S(Δx)2jand then, Am,can be obtained from Am,0 as
4 κ Δt 2 m π
jjAm,
= Am,0
sin
.
1−
2S
(Δx)2

(19)

Therefore,
nmj (xk , t )




kmπ
4 κ Δt 2 m π
j= Am,0 1 −
sin
sin
.
2S
S
(Δx)2
From (14), κ should satisfy1 − 4 κ Δt sin2 m π  < 1

2S 
(Δx)2
and we obtain the range of the diﬀusion coeﬃcient κ,

1 (Δx)2.
(22)
2 Δt
Note that the reason that the inequality (21) does not include
the equality comes from conditions (14) and (17). If bothconditions are not equal to 0 but finite, the left-hand side of
inequality (21) is less than or equal to 1. This constraint of
κ is the same as the constraint that appears in solving (11)by discrete space-time computations. In order to obtain therange of the diﬀusion coeﬃcient κ, it is necessary to consider the relationship between κ and D. It is shown in thenext subsection.
0<κ<

m=0

and

Fig. 5 Correspondence between discrete and continuous networkmodels.

(20)

(21)

In this subsection, we consider the actual value of D bydimensional analysis. We consider the value of the diffusion coeﬃcient expressed in the ordinary MKS (Meter/Kilogram/Second) unit system.
In order to consider the relationship between κ and D,
let us reconsider the meaning of related parameters and refine a continuous approximation of the network. Although
we assumed di = τi+1 , which means the link delay is equal tothe interval of DFC’s actions, they are diﬀerent notion originally. So, we regard them, in this subsection, as diﬀerent(independent) quantities. In accordance with the modification, we redefine
Di =

D
,
τi+1

(23)

instead of (4).
The relationship between the discrete space and thecontinuous space are shown in Fig. 5. First, we take the limitof the distance between the adjacent nodes as di → 0. The
second panel in Fig. 5 shows this situation. Here, the interval of DFC’s actions Δt is unchanged. Next, taking the

TAKANO et al.: PARAMETER DESIGN FOR DIFFUSION-TYPE AUTONOMOUS DECENTRALIZED FLOW CONTROL

2833

limit of Δx to be 0, we obtain a continuous approximationof the 1-dimensional network. Note that Δt should approach
0 concurrently with Δx → 0. The relationship between thepacket density n(x, t) and the number of packet stored in anode ni (t) is also shown in Fig. 5.
After taking the limit as di → 0, we compare the second term on the right hand side of (2) with that of (7),jj(n (t) − ni (t))∂n j (x, t)= D lim i+1
,
κ
Δt→0
∂x
Δt

(24)

where we use (23) and Δt = τi+1 . These quantities in bothsides in (24) are parts of packet rate and have a dimensionof packet/s. Note that n j (x, t) denotes the packet density andits dimension is packet/m. From Fig. 5,
n j (t) − nij (t),n j (x + Δx, t) − n j (x, t) = i+1
Δxwhere i = x/Δx + 1.
Therefore, we haveκ∂n j (x, t)n j (x + Δx, t) − n j (x, t)= κ lim
Δx→0
∂x
Δx
j
ni+1
(t) − nij (t)= κ lim
Δx→0
(Δx)2
j

j

Δt ni+1 (t) − ni (t).
= κ limΔt→0 (Δx)2
Δt

(25)

In the last equality, Δx should approach 0 concurrently withΔt in order to remain Δt/(Δx)2 a constant. Since Δt = di andby comparing (25) with (24), we obtain
D=κ

Δt
.
(Δx)2

(26)

Since κ has the dimension of [m2 /sec] from (22), D is adimensionless parameter. From this result and (22), we havethe range of the diﬀusion parameter D as
0<D<

1
.
2

(27)

We assumed homogeneous network configurations in
the above considerations. Next, we consider the condition
that links have diﬀerent length, in general. Since the diﬀusion parameter D is dimensionless, we can expect that D isinvariant even if the length of link is changed. If links havediﬀerent length, the intervals of DFC’s actions are diﬀerent.
Let the interval of DFC’s action for node k be Δtk . Then,(22) can be generalized as
0 < κ(k) <1 (Δx)2
,
2 Δtk

(28)

and the diﬀusion coeﬃcient κ(k) depends on node positionk, that is, link length. On the other hand, (26) can be generalized as
D = κ(k)

Δtk
,
(Δx)2

(29)

therefore, (27) is valid even in the situation where links havediﬀerent length.
Our design policy of D is to take a larger value of D in
the range (27).
5.

Simulation Studies

In this section, we show simulation studies about the performance of DFC with diﬀerent values of the diﬀusion coeﬃcient D in order to verify the range (27) and our design
policy of D. Simulations were made by using ns2 simulator[18]. We extended the simulation tool ns2 capability withthe function of DFC.
5.1 Simulation
The purpose of our simulation studies is to verify that therange (27) derived from theoretical analysis is applicable
also to actual networks. To this end, it is important to evaluate the response of a single congestion event. The reasonsare as follows. DFC is based on a linear diﬀerential equation (11) or more specifically a linear diﬀerence equation(12). In such linear systems, in general, the response withrespect to an impulse input is important and it is frequently
called the Green function. If we have the Green function,
we can obtain general solutions by superposing the Greenfunction. In our case, the impulse input corresponds to asingle congestion event. If the range (27) is applicable tosimulation scenarios having a single congestion event, therange (27) is applicable also to other simulation scenarios
under more complex and general traﬃc conditions. Thus,
we evaluate the range of D by using the following simple
simulation model.
Figure 6 shows our network model with 30 nodes,
which is used in the simulations. Although this 1dimensional model looks simple, it represents a part of a
network and describes a path of the target end-to-end flow
extracted from the whole network. The capacity of buﬀer at
each node is 1800 packets. A packet has a fixed length of1500 Bytes and the link bandwidth is 1,000,000 packets/s.
This means the link bandwidth is 12 Gbps. Both flows havegreedy traﬃc, that is, the rate of each flow is as large as
possible.
This paper uses inhomogeneous network configurations, that is, the length of links are diﬀerent. The lengthof link is described by the propagation delay, and it obeys aprobability distribution with the mean of 0.1 ms. Since thespeed of light in optical fiber is about 2/3 of the speed in thevacuum (300,000 km/s), this model assumes the link lengthof about 20 km. The propagation delay of each link is determined in advance. The delay consists of a fixed componentof 0.05 ms and the variable component that obeys an exponential distribution with the mean of 0.05 ms.
The simulation scenario is as follows. There are two
TCP Reno flows. The target flow is between node 1 andnode 30, while the background traﬃc flows between node 15
and node 30. The maximum TCP window size and the initial

IEICE TRANS. COMMUN., VOL.E91–B, NO.9 SEPTEMBER 2008

2834

Fig. 6

Fig. 7

Simulation model.

Temporal evolution of distribution of packets stored in each node.

TCP window size of both flows are 10,000 and it is chosen
as suﬃciently larger than the bandwidth-delay product of
RTT.
The reasons why we combine TCP and DFC in our
simulation model are as follows. Since TCP performanceis strongly influenced by the network QoS, we can clarify
the stability of network performance by DFC by observing

TCP performance. We can detect decreases of the throughput by a reduction of the TCP window size when packet loss
occurs. However, we use only a part of TCP functions. We
assume that the ingress node has the shaping mechanism in
DFC. This DFC shaping controls the volume of traﬃc between the application layer and the TCP layer. The excessive traﬃc cannot enter the network even if TCP window

TAKANO et al.: PARAMETER DESIGN FOR DIFFUSION-TYPE AUTONOMOUS DECENTRALIZED FLOW CONTROL

2835

Fig. 8

Temporal evolution of the total number of packets that are stored in nodes.

Fig. 9Temporal evolution of the total number of packets that are in transit on links.

size is very large. If the number of packets stored in nodes
is smoothly distributed over the network by DFC, there will
be no packet loss in setting the appropriate buﬀer size. In
our simulation, we are interested in not the characteristic of
TCP itself, but the eﬀect of avoidance of packet losses by
DFC. It is worth noting that since the functions of DFC are
independent of TCP, existence of TCP is not essential to the
behavior of DFC itself.
The target flow and the background flow start at simulation time t = 0 s and t = 0.1 s, respectively. After the
background flow traﬃc entered the network, the link fromnode 15 to 16 became a bottleneck, and traﬃc of both flows
was regulated by predefined rules for DFC. For DFC, thevalues of transmission rate from external nodes in the othernetwork to node 1 and node 15 is adjusted (shaped) to r01 andr02 as shown in (10). After congestion occurred, we investigated the temporal evolution of the network state.

In [7], we evaluated the performance of the DFC in asituation where there were many flows whose lifetime followed an exponential distribution. These flows were generated by two diﬀerent nodes selected in the network modelat random. In addition, we complemented DFC and TCP(TCP Tahoe, Reno, NewReno, Vegas) with respect to thenumber of hops in the other paper [9]. We confirmed that
DFC achieved high performance and adapted to the network
conditions.
5.2 Simulation Results
To demonstrate the diﬀusion eﬀect by DFC and to verify theeﬀect of the value of D, we show temporal evolution of thenumber of stored packet in each node.
Figure 7 shows the results obtained from our simulations with D = 0.01, 0.1, 0.4, 0.5, 1 and 3.0, respectively.

IEICE TRANS. COMMUN., VOL.E91–B, NO.9 SEPTEMBER 2008

2836

The horizontal axes denote node ID (1–29) and the verticalaxes denote the number of stored packet at each node. Here,
we omit node 30 since it has no stored packets. Simulation
time is shown in each graph. Since the speed of diﬀusioneﬀect strongly depends on the value of D, only two casesthat D = 0.4 and 0.5, are displayed at the same timing.
After the time when the background traﬃc enters thesimulation network (after 0.1 s), each node in the network
prevents the stored packets centralizing at a certain node by
DFC. From the results for D = 0.01, 0.1, 0.4 and 0.5, the distributions of the number of packets exhibit orderly behavior.
Incidentally, if DFC was not applied, all stored packets areat node 15 [17]. This causes packet losses and the reductionof TCP window size. By introducing DFC, each node cooperatively acts to avoid packet losses even though decisionmaking of each node is based only on the local information.
On the other hand, the results for D = 1 and 3 do not showorderly behavior of the packet distribution.
In general, the speed of diﬀusion eﬀect increases whenthe value of D increases, but extremely large value of D prevents the diﬀusion eﬀect. In these cases, although the valueof D = 0.5 is out of the range of (27), the diﬀusion eﬀects
are observed.
Panels in Fig. 8 show the temporal evolution of the total number of packets, when the values of D are equal to0.01, 0.1, 0.4, 0.5, 1 and 3, respectively. The horizontal axes
denote simulation time and the vertical axes denote the total
number of packets that are stored in nodes. These results
also indicates the speed of diﬀusion eﬀect increases whenthe value of D increases, but extremely large value of D prevents the diﬀusion eﬀect.
Next, we investigate how much packets are transmitted
in the network. The volume of the target flow packet transmission at time t can be represented by the total number of
the target flow packets in transit on links of the network.
This quantity can represent amount of network performanceat the present time, dedicated for the target flow. Panels in
Fig. 9 show the results in cases D = 0.01, 0.1, 0.4, 0.5, 1 and
3, respectively. The horizontal axes denote simulation time
and the vertical axes denote the total number of packets thatare in transit on links.
Since the maximum number of packets in transit on alink at a moment was an average of 100, and the backgroundflow passed through about half of links of the target flow, themaximum total number of target flow’s packets in transit on
links was about 2, 900 when t ≤ 0.1 and was about 1, 450
when t > 0.1. On the other hand, the maximum total numberof background flow’s packets in transit on links was about
750 after t = 0.1.
From the first four panels for D = 0.01, 0.1, 0.4, and
0.5 in Fig. 9, the numbers of packets in transit on links forboth flows reached almost their maximums in a short time
and these results mean that they fairly share the link bandwidth. In the cases of D = 1 and 3 out of the range of (27),oscillation eﬀects are observed. The reason of the oscillations is a trade-oﬀ between fast recovery and stability. For
D > 0.5, it prefers too fast change of network state and pre-vents stable network performance as a result.
In these results, the value of D = 0.5 shows good performance but this is out of the range (27). The range (27)is derived from the suﬃcient condition that the diﬀusion effect appears. Thus, the value of D = 0.5 may exhibit good
performance in some cases. However, in order to guarantee the diﬀusion eﬀect for any conditions, it is necessary toadopt the value of D in the range (27). For example, we canchoose D = 0.499.
We can say the range (27) is not a necessary condition
but a suﬃcient condition for the guarantee of the diﬀusioneﬀect in any network environment.
6.

Conclusions

To overcome the diﬃculty in control of high-speed networks, we have proposed DFC. In this control mechanism, the state of the whole network is controlled indirectly
through the autonomous action of each node; each nodemanages its local traﬃc flow on the basis of only the local
information directly available to it, by using predetermined
rules. By applying DFC, the distribution of the total number of packets in each node in the network becomes uniform
over time, and it exhibits orderly behavior. This property issuitable for fast recovery from congestion.
One of important issues in design of DFC is how tochoose the value of diﬀusion parameter. This is the central
issue for enabling DFC to make diﬀusion eﬀects of packet
density in networks.
We determined the range of the diﬀusion parameter D
by applying the condition for discrete space-time computations of the diﬀusion equation to DFC. In addition, we considered the actual value of D by dimensional analysis.
Simulation results verified the range of D. Even if
the value is in the range, too small value of D causes very
slow diﬀusion, and this means that stolid congestion recovery makes to waste much time. Consequently, to make fast
diﬀusion, we should take a value of D as large as possible inthis range.
Acknowledgement
This research was partially supported by the National Institute of Information and Communications Technology(NiCT) and the Grant-in-Aid for Scientific Research (S)No. 18100001 (2006–2010) from the Japan Society for the
Promotion of Science.
References[1] Y. Bartal, J. Byers, and D. Raz, “Global optimization using local information with applications to flow control,” Proc. 38th Ann.
IEEE Symp. on Foundations of Computer Science, pp.303–312, Oct.
1997.
[2] S.H. Low and D.E. Lapsley, “Optimization flow control-I: Basic algorithm and convergence,” IEEE/ACM Trans. Netw., vol.7, no.6,
pp.861–874, 1999.
[3] K. Kar, S. Sarkar, and L. Tassiulas, “A simple rate control algorithm

TAKANO et al.: PARAMETER DESIGN FOR DIFFUSION-TYPE AUTONOMOUS DECENTRALIZED FLOW CONTROL

2837

for maximizing total user utility,” Proc. IEEE INFOCOM 2001,
pp.133–141, 2001.
[4] S. Kunniyur and R. Srikant, “A decentralized adaptive ECN marking
algorithm,” Proc. IEEE GLOBECOM’00, pp.1719–1723, 2000.
[5] J. Mo and J. Walrand, “Fair end-to-end window based congestion
control,” IEEE/ACM Trans. Netw., vol.8, no.5, pp.556–567, Oct.
1999.
[6] C. Takano and M. Aida, “Stability and adaptability of autonomous
decentralized flow control in high-speed networks,” IEICE Trans.
Commun., vol.E86-B, no.10, pp.2882–2890, Oct. 2003.
[7] C. Takano, M. Aida, and S. Kuribayashi, “Autonomous decentralized flow control in high-speed networks with inhomogeneous configurations,” IEICE Trans. Commun., vol.E87-B, no.6, pp.1551–
1560, June 2004.
[8] C. Takano and M. Aida, “Diﬀusion-type autonomous decentralized
flow control for end-to-end flow in high-speed networks,” IEICE
Trans. Commun., vol.E88-B, no.4, pp.1559–1567, April 2005.
[9] C. Takano, K. Muranaka, K. Sugiyama, and M. Aida, “Mutual complementarity of diﬀusion-type flow control and TCP,” IEICE Trans.
Commun., vol. E89-B, no.10, pp.2850–2859, Oct. 2006.
[10] J.B. Postel, “Transmission control protocol,” Request for Comments
793, Sept. 1981.
[11] S. Floyd, “HighSpeed TCP for large congestion windows,” Request
for Comments 3649, Dec. 2003.
[12] T. Kelly, “Scalable TCP: Improving performance in highspeed wide
area networks,” ACM SIGCOMM Computer Communication Review, vol.32, April 2003.
[13] L. Xu, K. Harfoush, and I. Rhee, “Binary increase congestion control for fast long-distance networks,” Proc. IEEE INFOCOM 2004,
March 2004.
[14] C. Jin, D.X. Wei, and S.H. Low, “FAST TCP: Motivation, architecture, algorithms, performance,” Proc. IEEE INFOCOM 2004, March
2004.
[15] I. Rhee and L. Xu, “CUBIC: A new TCP-friendly highspeed TCP
variant,” Proc. PFLDnet 2005, Feb. 2005.
[16] K.T. J. Song, Q. Zhang, and M. Sridharan, “Compound TCP: A scalable and TCP-friendly congestion control for high-speed networks,”
Proc. PFLDnet 2006, Feb. 2006.
[17] C. Takano and M. Aida, “Diﬀusion-type autonomous decentralized
flow control for multiple flows,” IEICE Trans. Commun., vol.E90-B,
no.1, pp.21–30, Jan. 2007.
[18] The Network Simulator — ns-2. http://www.isi.edu/nsnam/ns/

Chisa Takano
received the B.E. degree in
Telecommunications Engineering from Osaka
University, Japan, in 2000, and received the
Ph.D. in Information Network Engineering from
Tokyo Metropolitan University, Japan, in 2008.
In 2000 she joined the Traﬃc Engineering Center, NTT Advanced Technology Corporation(NTT-AT). She has been an Associate Professor of the Graduate School of Information Sciences, Hiroshima City University since April
2008. Her current interests include research anddevelopment of computer networks.

Keita Sugiyama
received his M.E. degree inManagement Systems Engineering from Tokyo
Metropolitan University, Japan, in 2008.

Masaki Aida
received his B.S. and M.S.
degrees in Theoretical Physics from St. Paul’s
University, Tokyo, Japan, in 1987 and 1989, andreceived the Ph.D. in Telecommunications Engineering from the University of Tokyo, Japan,
in 1999. In 1989, he joined NTT Laboratories.
In April 2005 to March 2007, he was an Associate Professor of the Faculty of System Design,
Tokyo Metropolitan University. He has been a
Professor of the Graduate School of System Design, Tokyo Metropolitan University since April
2007. His current interests include traﬃc issues in computer communication networks. He is a member of the IEEE and the Operations ResearchSociety of Japan.