IEICE TRANS. COMMUN., VOL.E87–B, NO.6 JUNE 2004

1551

PAPER

Autonomous Decentralized Flow Control in High-Speed Networks
with Inhomogeneous Configurations
Chisa TAKANO†a) , Masaki AIDA††b) , and Shin-ichi KURIBAYASHI†††c) , Members

SUMMARY
Recent growth in computer communications has led to anincreased requirement for high-speed backbone networks. In such highspeed networks, the principle adopted for a time-sensitive flow control
mechanism should be that of autonomous decentralized control. In thismechanism, each node in a network manages its local traﬃc flow only
on the basis of the local information directly available to it, although it
is desirable that the individual decisions made at each node lead to highperformance of the network as a whole. In our previous studies, we haveinvestigated the behavior of local packet flows and the global performanceachieved when a node is congested, and proposed the diﬀusion-type flow
control model. However, since we used a simple and homogeneous network model in the evaluation, the results cannot be generalized. In thispaper, we propose an extension of the diﬀusion-type flow control model inorder to apply it to networks with inhomogeneous configurations. We show
simulation results for two cases: diﬀerent propagation delays and multiple
bottlenecks. Both results show that the proposed diﬀusion-type flow control achieves high and stable performance even if the network is congested.
key words: autonomous decentralized system, flow control, diﬀusion, feedback

1.

Introduction

In recent years, the increase in traﬃc transferred through the
network has been further augmented by the spread of broadband access and broadband applications. To convey sucha large amount of traﬃc, a very high-speed backbone network is required. In high-speed networks, such as gigabit
or terabit/second networks, propagation delay becomes thedominant factor in the transmission delay because the speedof light provides an absolute constraint. Therefore, at any
given time, a large amount of data is in the state of being
propagated on links in the network (Fig. 1). The amount ofsuch data is characterized by the bandwidth-delay product,i.e., the propagation distance multiplied by the transmission
rate. Therefore, in high-speed and/or long-distance transmission, there is more data in transit on the links than there
is waiting in the nodes.
Since the performance of modes is strongly dependent
on their throughput capacity, but the propagation delay is
Manuscript received March 24, 2003.
Manuscript revised December 5, 2003.
†
The author is with Traﬃc Engineering Division, NTT Advanced Technology Corporation (NTT-AT), Musashino-shi, 1800006 Japan.
††
The author is with NTT Information Sharing Platform Laboratories, NTT Corporation, Musashino-shi, 180-8585 Japan.
†††
The author is with Seikei University, Musashino-shi, 1808633 Japan.
a) E-mail: chisa@mitaka.ntt-at.co.jpb) E-mail: aida.masaki@lab.ntt.co.jpc) E-mail: kuribayashi@apm.seikei.ac.jp

Fig. 1

Eﬀect of large bandwidth-delay product.

constant, it is impossible to impose time-sensitive control
based on collecting global information about the network.
If we allow suﬃcient time to collect global information, thedata so gathered is too old to apply to time-sensitive control.
So, in a high-speed network, the principles adopted for timesensitive control are inevitably those of autonomous decentralized systems [1]–[5].
This paper focuses on flow control implemented as anautonomous decentralized system. In our model, each individual network node manages the handling of its local traﬃcflow itself, based only on the information directly available
to it. Since time-sensitive control in high-speed networks
cannot collect global information about the network, nodes
can use only restricted local information. We assume that
it is only possible for each node to be aware of the following information: the distance between the node and adjacent nodes, the number of packets stored in the node at thepresent moment, and the feedback information that is received from the adjacent nodes. It is, of course, desirable
that the decisions made at each node should lead to highperformance of the whole network. In flow control, we use
the total throughput of a network as a global performancemeasure.
In our previous studies, we investigated the behaviorof local packet flows and the global performance measure
when a node is congested, and demonstrated an appropriate
flow control model through simulation results [3], [4]. In
addition, we investigated the stability and adaptability of the
network performance when the capacity of a link is altered[4], [5].
However, since we used a simple and homogeneous
network model with uniform link delays and a single bottleneck in the evaluation, the results cannot be generalized.
In this paper, we propose an extension of the diﬀusion-typeflow control model in order to apply it to networks with inhomogeneous configurations and to demonstrate the performance of the proposed control method by using more realistic network models in the evaluation.

IEICE TRANS. COMMUN., VOL.E87–B, NO.6 JUNE 2004

1552

The remainder of this paper is organized as follows.
In Sect. 2, we discuss related studies, comparing them with
our work by categorizing the flow control mechanisms.
In Sect. 3, we describe the framework of our flow control
method, including the measure of performance, the nodemodel and the packet flow, before explaining our flow control mechanism. In Sect. 4, we propose an extension of thediﬀusion-type flow control mechanism, to make it applicable to links with diﬀerent delays. This mechanism is applied
to the framework outlined in Sect. 3. In Sect. 5, we describe
the performance of the proposed flow control mechanism
for network models with diﬀerent link delays and a single
bottleneck. Then, in Sect. 6, we describe the performance ofthe proposed flow control mechanism for network models
with multiple bottlenecks in a situation where the network
is shared by multiple flows. Finally, Sect. 7 provides a conclusion to this paper.
2.

Related Studies

In general, the technique used for flow control for highspeed networks should satisfy the following requirements:
1. It must be possible to collect the information required
for used in the control mechanism.
2. The required control must be applied with minimum
delay, so that it is virtually instantaneous.
As explained earlier, in high-speed networks, we cannot collect global information about the network. So, we may classify the flow control mechanisms with respect to the collecting of information as shown 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 1A and 1-C are possible, and there are many papers which
consider these classes. They mainly relate to optimizationof flow control problems in the framework of solving linear programs. Techniques for addressing rate control, bandwidth assignment, deadlock resolution, resource allocation
or flow fairness problems for each source by optimizing
some end-to-end utility function have been reported in [6]–[10]. Reference [11] considers the issue of reducing the convergence time in solving optimization problems.
Our target is flow control in a high-speed network, forwhich the framework is inevitably autonomous decentralized control, so we are focusing on class 1-D.
We can also classify the decentralized flow control
mechanisms from the point-of-view of the control delay requirement, as shown in Table 2.
Flow control by end hosts including TCP is widelyused in current networks, and there is much research in thisarea.
Based on the optimization problem, [12] introduces
a decentralized marking mechanism for early notificationof congestion. For window-based flow control, the optimization problems of some aggregated utility functions have

Table 1 Classification of flow control mechanisms with respect tocollecting information.

centralized control
decentralized control

low-speed NW
1-A
1-C

high-speed NW
1-B
1-D

Table 2 Classification of decentralized flow control mechanisms withrespect 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

been explored in [13]. Solving these optimization problems,
however, requires enough time to be available for calculation, and so it is diﬃcult to apply them to decision-making
in a very short time-scale.
Johari and Tan [14] 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. [15] reports an investigation of rate control and window control with feedback fromnodes to end hosts. Each feedback message indicates thestate of the buﬀer at the node—whether it is above or below
a threshold. Since control by end hosts cannot be applied
to decision-making in a time-scale shorter than the roundtrip delay, it is not satisfactory for application to decisionmaking in a very short time-scale. Therefore, these methods
are categorized as class 2-A. In high-speed networks, due tothe fact that many packets are influenced by control delay,
a very short control delay is required, and so class 2-B cannot be realized. Our target is node-by-node control and iscategorized as class 2-D.
Bartal et al. [6] studied global optimization of flow control using local information. The motivation for their work
was to enable the distributed routers in high-speed networks
to make decisions on flow control as rapidly as possible,
and they studied the problem in the framework of solving
linear programs using 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 suﬃ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 taken to collect data.
In our previous studies, we investigated the characteristics of autonomous decentralized flow control in a highspeed network [1]–[5]. We proposed a simple and eﬀective
method of flow control in [3]–[5]. Since the proposed control method uses less information than the control methods
described in [1], [2], it is relatively simple.

TAKANO et al.: AUTONOMOUS DECENTRALIZED FLOW CONTROL IN HIGH-SPEED NETWORKS

1553

node behavior and flow control is summarized as follows:3.

Preliminary Description of Flow Control

We assume that a target flow has a static route. In the case ofInternet-based networks, to guarantee the end-to-end Quality of Service (QoS) of a flow, QoS sensitive flows use astatic route (e.g. RSVP). In addition, we assume all routersin the network can employ per-flow queueing for the all target flows.
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 define the total
throughput of the network as a global performance measure
as follows. We define the total throughput of a network attime t as the amount of data being propagated on the network [1]–[5], [16], that is the total number of packets being
propagated on all links in the network at time t.
On the other hand, the only packets we can control arethose stored in nodes, and not those being propagated. Thus,
high performance of the whole network involves many uncontrollable packets being propagated on links. Therefore,
inappropriate flow control cannot produce a condition characterized by both high performance and stability.
3.2 Node Model
Figure 2 shows the interaction of our flow control method
between nodes using a network model with a 1-dimensional
configuration. Although this model looks simple, it illustrates how a part of a network may be extracted from thewhole network along the route of the specific flow.
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 (node information) to node i. For simplicity, we assume that packets havea fixed length in bits.
All nodes are capable of receiving node information
from, and sending it to, adjacent downstream and upstream
nodes, respectively. Each node i can receive node information sent from the downstream node i + 1, and can send thenode information about node i itself to the upstream nodei − 1.
When node i receives node information from downstream node i + 1, it determines the transmission rate forpackets to the downstream node i + 1 using the received
node information and adjusts its transmission rate towards
the downstream node i + 1 accordingly. The framework of

Fig. 2

Interaction between nodes.

• Each node i autonomously determines the transmission
rate Ji based only on the information available to it, thatis, 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 the same
propagation delay.
As mentioned above, the framework of our flow control
model involves both autonomous decision-making by eachnode and interaction between adjacent nodes. There is nocentralized control mechanism in the network, since, as described earlier, it is impossible to realize centralized control
in a high-speed network environment.
3.3 Packet Flow
In this paper, we focus on the stability of flow control in thecongested state, and consider packet flow in a heavy-traﬃcenvironment. The packet flow is defined as the number ofpackets sent per unit of time, and in a heavy-traﬃc environment it is the same as the transmission rate towards thedownstream node. That is, if the transmission rate specified
by node i is Ji (t), we let the packet flow be Ji (t). This is because node i has suﬃcient packets to transfer. Hereafter, we
identify the packet flow with the transmission rate specified
by the node.
The packet flow Ji (t) should be controlled by the behavior of node i in the framework described in Sect. 3.2.
This means that the packet flow from a node can be expressed using the node information obtained from the downstream node i + 1 and information its about the node itself.
So, we consider the packet flow determined through a certain function, F, as
Ji (t) = F(ni (t), di , ri (t − di ), ni+1 (t − di )),(1)

where ni (t) denotes the number of packets in node i at time t,
di denotes the propagation delay between node i and node i+
1, and ri (t−di ) is the target transmission rate specified by thedownstream node i+1 as node information. In addition, ri (t−di ) and ni+1 (t − di ) are notified from the downstream nodei + 1 with the propagation delay di . The interval between
two successive notifications from the downstream node i + 1
is constant and is denoted by τi+1 .
If there is no packet loss in the network, the temporal
evolution of ni (t) is expressed as a continuous equation,

IEICE TRANS. COMMUN., VOL.E87–B, NO.6 JUNE 2004

1554

ni (t + ) − ni (t) =  [Ji−1 (t − di−1 ) − Ji (t)] ,(2)

where  > 0 is a small number.
4.

Flow Control Models

In this section, we propose an extension of the diﬀusiontype flow control described in [3]–[5], in order to apply it to
networks which include diﬀerent link lengths.

this flow control, we consider that the propagation delay is
generally constant in this evaluation. The following is a description of the flow control method, which determines thetransmission rate such that the diﬀerence between the number of packets in one node and that in the downstream node
becomes smaller.
To provide a rough estimate the temporal evolution, we
replace i with x and apply continuous approximation. Thenthe propagation delay becomes di → 0 for all i and in thelimit, the packet flow (3) is expressed as

4.1 Diﬀusion-Type Flow Control
Node i’s packet transmission rate to the downstream nodei + 1 is defined asJi (α, t) = α ri (t − di ) − Di (ni+1 (t − di ) − ni (t)).

(3)

The first term on the right hand side of Eq. (3) reflects thetarget rate specified by the downstream node, and the second
term, which is called the diﬀusion term, is proportional to
the rate of change of the packet density. We call α (≥ 1)
and Di (> 0) the flow intensity multiplier and the diﬀusion
coeﬃcient, respectively. Here, we choose Di = D/di where
D is a constant; in the previous studies, [3]–[5], Di was aconstant and independent of i.
In addition, the node information of node i sent to the
upstream node i − 1 is determined every fixed period τi as
ri−1 (t) = Ji (1, t).

(4)

To implement this flow control, we use the following
flow control model. Since the packet flow is restricted by
the link capacity Li , the flow control is expressed as follows:
Ji (α, t) = min(max( J˜i (α, t), 0), Li ),ri−1 (t) = Ji (1, t),

(5)
(6)

where
J˜i (α, t) = α ri (t − di ) − Di (ni+1 (t − di ) − ni (t)).

J(x, t) = α r(x, t) − D∂n(x, t).
∂x

(8)

The temporal evolution of the number of packets at x may
be expressed as a diﬀusion type equation,∂n(x, t)∂r(x, t)∂2 n(x, t)
= −α
+D
,
∂t
∂x
∂x2

(9)

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

(10)

Equation (9) is a sort of diﬀusion equation. That is, ourmethod aims to perform flow control using the analogy ofa diﬀusion phenomenon. We can expect packets in a congested node to be redistributed over the whole network andnormal network conditions to be restored after some time.
Note that, to obtain the limit (8) from Eq. (3), it is necessary to choose
Di ∝

1
,
di

(11)

and the flow intensity multiplier α is independent of di .
4.2 Drift-Type Flow Control(7)

In the framework of Eqs. (5)–(7), the feedback informationof i passed to the upstream node i − 1 is a pair of values(ri−1 (t), ni (t)). Feedback information is created periodically,and τi denotes the time interval between successive notifications of feedback information from node i to the upstream
node i − 1. We choose τi ∝ di−1 ; in the previous studies[3]–[5], τi was constant and independent of i. In the rest of
this paper, we choose τi = di−1 , that is one set of feedback
data information is always being transmitting on the link.
Moreover, the packet flow Ji (t) in node i is revised wheneverfeedback information arrives from the downstream node i+1(with a period of τi+1 = di ).
The propagation delay di−1 may vary on account of achange in network topology. In this case, each node needs
to be aware of the new propagation delay for the adjacentlink and to update the time interval τi . However, since thetime interval between changes in network topology is very
long in comparison with the time scale of the behavior ofIf we cannot use the information of ni+1 (t − di ) specified
by the downstream node, diﬀusion-type flow control cannot
determine the packet flow. So, we consider a flow control
model in which ni+1 (t − di ) in Eq. (1) is replaced with theconstant threshold n s (≥ 0). Since the packet flow is restricted by the link capacity Li , this flow control is expressed
as follows:J˜i (α, t) = α ri (t − di ) − Di (n s − ni (t)),
n s = constant (≥ 0).
5.

(12)
(13)

Evaluation for Network with a Single Bottleneck

In this section, we use a simulation to show the importanceof feedback information and the importance of selecting anappropriate diﬀusion coeﬃcient. In our simulation study, we
consider the case where the capacity of a link in the network
is suddenly reduced to a narrow bandwidth. This situation

TAKANO et al.: AUTONOMOUS DECENTRALIZED FLOW CONTROL IN HIGH-SPEED NETWORKS

1555

Fig. 3

Example of a bottleneck link.

and is independent of the output process, but the input
packet rate is equivalent to the output one so that themean number of packets is kept constant).
• Bandwidth of each link except the bottleneck link: Li =100 [packets/unit time] (i  30).
• Bandwidth of the bottleneck link (between nodes i =30 and 31): L30 = 25, 50, or 75 [packets/unit time](that is, 1/4, 1/2, or 3/4 of the bandwidth of other links).
To investigate the stability under congestion, in addition to
the above conditions, we set the initial condition for congested node i = 30 as follows.

Fig. 4

Network model with a bottleneck link.

occurs when, for example, there is fault on a link, or background traﬃc occupies bandwidth. For example, Fig. 3 illustrates a change in available bandwidth influenced by traffic in a diﬀerent flow. In high-speed networks, no node is
directly aware of the change in the state of the link resulting
in a new capacity.
First, we compare network performance for the two different flow control mechanisms described in Sect. 4 by using
a simple and homogeneous network model having a single
bottleneck and equal propagation delays between adjacentnodes. We show that the diﬀusion-type flow control mechanism provides high network performance irrespective of thecapacity of the bottleneck link.
Next, we consider network models with diﬀerent propagation delays between the adjacent nodes and investigate
the performance of the diﬀusion-type flow control using
these models. We show that the diﬀusion-type flow control
absorbs the complexity of the network model, and achieves
high performance and stability even if the link delays in the
network are diﬀerent.
5.1 Network Model and Simulation Conditions
Figure 4 shows our network model, which is an open network with a 1-dimensional configuration. The network has
a bottleneck link and a corresponding congested node. All
the other nodes and links are in the same condition as eachother. This model simulates the situation when congestion
occurs at a certain node. We are interested in the behaviorof the local congestion, that is, whether:• it causes deterioration in the total network performancethrough interaction among nodes, or• it diminishes with time.

• Number of packets in node i = 30 at time t = 0: 400.
• The other 5600 packets are randomly configured inother nodes and on other links.
• Propagation delays between adjacent nodes (threemodels):model 1: All distances between adjacent nodes are thesame: 1 (unit time).
model 2: The distance between any node and the adjacent node can be one of two values, short orlong, (that is, it has a small or large propagation
delay), where the ratio of the length of the shortlinks to that of the long links is 1:50. Each link
value appears with the probability 1/2. So, wechoose about 0.04 or 1.96 for the propagation delays of the 59 links so that the mean propagation
delay is 1.0 and the variance is 0.94.
model 3: The length of each link is determined according to a log-normal distribution, where the mean
delay in the network model is 1.0 and the varianceis 5.2.
The values of the parameters used in our flow control
models for the evaluation are as follows:(0.1 × d1i , di−1 ),(0.1, 1),
(14)
(Di , τi ) =  (0.1 × di , 1 ),di−1αi = 1.01,
n s = 0, or 60 (for drift-type control).

(15)
(16)

The first combination of values for (Di , τi ) in Eq. (14) corresponds to our flow control as described in Sect. 4. The
second one corresponds to the flow control shown in ourprevious studies [3]–[5]. In addition, we consider the thirdcombination in order to compare it with the other two. Notethat these three pairs of parameters provide the same control
mechanism in a network model having the equal link delays.

Detailed conditions of our network model are listed be-

5.2 Simulation Results for Model 1: Total Throughput andStability• Number of nodes: m = 60. Each node specified by i(i = 1, 2, . . . , 60).
• Index of the congested node: i = 30.
• Mean number of total packets in the network: N =6000 (the packet input process is the Bernoulli process

We compare the total throughput of the network for the diffusion and drift type flow control models described in theprevious section by using model 1, and discuss the stabilityof the flow control models in a high-speed network environment. Note that the three variations of Eq. (14) for thelow.

IEICE TRANS. COMMUN., VOL.E87–B, NO.6 JUNE 2004

1556

Fig. 5

Total throughput of the network in model 1 (diﬀusion-type).

Fig. 6

Total throughput of the network in model 1 (drift-type n s = 0).

Fig. 7

Total throughput of the network in model 1 (drift-type n s = 60).

diﬀusion-type flow control are the same in this evaluation(di = 1 (constant)).
Figures 5, 6 and 7 show the results of the total throughput for the diﬀusion-type and two variations of the drift-type(n s = 0 and 60) flow control models, respectively. The horizontal axis denotes the simulation time and the vertical axis
the total throughput (i.e., the total number of packet being
propagated on links). The three lines in these figures shows
the results for the cases where the capacity of the bottleneck
link L30 = 25, 50, and 75.
We discuss the results from a quantitative point of view.
Figure 5 shows that the total throughput decreases with time
but becomes stable at around 1500, 3000, or 4500 corresponding to a capacity of the bottleneck link L30 = 25, 50, or
75, respectively. For a given capacity of the bottleneck link
L30 , the maximum value of the sustainable total throughput(the maximum number of packets being propagated stably
on links) should be L30 packets/link × 59 links. Thus, thediﬀusion-type flow control achieves about 100% of the maximum value of the total throughput (in other words, transfer
eﬃciency is about 100%) irrespective of the value of L30 . In

the diﬀusion-type control model, although no node is awareof the bandwidth of the bottleneck link, stable and high performance is achieved.
Figure 6 shows that for drift-type flow control with thevalue of n s = 0, the total throughput is also high and stableirrespective of the value of L30 . In this case also, the drifttype flow control provides about 100% transfer eﬃciency.
In Fig. 7, on the other hand, when n s is large such as n s =60, the values of total throughput are in all cases small andunstable.
Next, we investigate the distribution of packets in theindividual nodes for these flow control models. Figures 8–
10 show the simulation result for flow control models when
the capacity of the bottleneck link L30 is 50. The horizontal
axis of each graph denotes node ID and the vertical axis thenumber of packets stored in the node, i.e., the queue length
in the node. In addition, t denotes the simulation time andinitially t = 0.
As mentioned above, both the diﬀusion-type and thedrift-type control with the value of n s = 0 provide stable
and high total throughput. However, Fig. 9 shows that forthe drift-type flow control with the value of n s = 0, there isa drastic increase in the queue length of the congested nodei = 30, while for the diﬀusion-type flow control, the distribution of the number of packets stored in nodes is distributed
smoothly over the network with time. Since a large queue
length causes packet loss, the drift-type flow control withthe value of n s = 0 is not appropriate. For drift-type control with the value of n s = 60, the number of packets in thecongested node i = 30 decreases with time, but the distribution of the number of packets is uneven and the maximum
number of packets in a node is very large.
If we can choose an appropriate value for the threshold n s for the capacity of the bottleneck link L30 , the total
throughput may be stable and adaptive for drift-type flow
control. However, drift-type control cannot achieve highperformance, since nodes cannot be aware of information
about the bandwidth of the bottleneck link in a high-speed
network environment.
We can recognize from the above results that ni+1 (t−di )used in the diﬀusion-type flow control is essential for providing the superior performance from the point of view oftransfer eﬃciency, stability, and the avoidance of congestion.
Hereafter, focusing on the diﬀusion-type flow control,
we will evaluate the network performance when the networkmodel is more complicated.
5.3 Simulation Results for Models 2 and 3:
Throughput and Stability

Total

We discuss the performance and stability of the diﬀusiontype flow control model for model 2 and model 3, throughevaluation of the total throughput.
In this discussion, the value of the diﬀusion coeﬃcient
Di shown in Sect. 4.1 is justified.
Figure 11 shows the total throughput for model 2 andTAKANO et al.: AUTONOMOUS DECENTRALIZED FLOW CONTROL IN HIGH-SPEED NETWORKS

1557

Fig. 8 Temporal evolution of the number of packets in each node for diﬀusion-type flow control inmodel 1.

Fig. 9 Temporal evolution of the number of packets in each node for drift-type flow control (n s = 0)
in model 1.

Fig. 10 Temporal evolution of the number of packets in each node for drift-type flow control (n s = 60)
in model 1.

performance than the case for Di = 0.1/di .
The values of total throughput achieved by the modelwith Di ∝ 1/di shown in Fig. 11 are almost the same as
those for the cases where the capacity of the bottleneck linkis 25, as shown in Fig. 5. This means the appropriate settingof the diﬀusion coeﬃcient Eq. (11) allows the complexity of
the network model to be absorbed, and provides high performance and stability even if the configuration of the network
becomes complex.
Next, we consider the temporal evolution of the distribution of packets stored in nodes, the results being shownin Figs. 12–17. The first three figures show the results formodel 2 and the last three show those for model 3. For eachmodel the figures show the cases for Di = 0.1/di , 0.1, and
0.1 × di , respectively.
In both models, the case of Di = 0.1/di exhibits asmooth diﬀusion of the packet distribution over the network.
Fig. 11 Total throughput of the network (model 2 and model 3) (in thecase where the delays between the adjacent nodes are diﬀerent).

model 3, where the horizontal axis denotes the simulation
time and the vertical axis denotes the total throughput. The
capacity of the bottleneck link i = 30 is L30 = 25. The
three lines in this figure show the results from the diﬀusiontype flow control model with Di = 0.1/di , 0.1, and 0.1 ×
di . We can see in Fig. 11 that the total throughput becomesstable at a higher level of performance in the cases where Di
is inversely proportional to the propagation delay, for bothmodel 2 and model 3. These results imply that Eq. (11) isappropriate for providing high performance and stability in
networks with inhomogeneous configurations.
Although other combinations of (Di , τi ) are possible
in principle, they have no physical meaning and give lower

6.

Evaluation for Network with Multiple Bottlenecks

In this section, we consider the performance of the diﬀusiontype flow control in a situation where there are many flows
sharing links on the route of the target flow.
We consider a one-dimensional network model with 60
nodes (Fig. 18). As in Fig. 4, this model shows a part of a
network extracted from the whole network along the routeof a specific flow. The bandwidth of all links is 100 packets/unit time, and link delays are determined by a log-normal
distribution, as in Sect. 5.3. Background flows, which sharethe links on the route of the target flow, are generated according to a Poisson process. These generated flows selecttwo diﬀerent nodes in the network model at random andshare the links between the two selected nodes. The lifetime of the background flow follows an exponential distribution. The packets generated by each background flow are

IEICE TRANS. COMMUN., VOL.E87–B, NO.6 JUNE 2004

1558

Fig. 12 Temporal evolution of the number of packets in each node for diﬀusion-type flow control(with Di = 0.1/di ) in model 2.

Fig. 13 Temporal evolution of the number of packets in each node for diﬀusion-type flow control(with Di = 0.1) in model 2.

Fig. 14 Temporal evolution of the number of packets in each node for diﬀusion-type flow control(with Di = 0.1 × di ) in model 2.

Fig. 15 Temporal evolution of the number of packets in each node for diﬀusion-type flow control(with Di = 0.1/di ) in model 3.

Fig. 16 Temporal evolution of the number of packets in each node for diﬀusion-type flow control(with Di = 0.1) in model 3.

Fig. 17 Temporal evolution of the number of packets in each node for diﬀusion-type flow control(with Di = 0.1 × di ) in model 3.

also regulated by the diﬀusion-type flow control. Nodes in
the network employ per-flow queueing and round robin fairscheduling.
If at most N flows share a link, the maximum sustainable total throughput for the target flow is 100/N × 59. Figures 19 and 20 show the maximum sustainable total throughput and the total throughput obtained from simulation. The
horizontal axis denotes the simulation time and the verticalaxis denotes the total throughput. Figure 19 shows the casewhere the mean interval between the occurrence of background flows is 1000 units of time, and the mean lifetime of
a flow is 2000 units of time, while Fig. 20 shows similar re-sults with flow arrival and lifetime values of 3000 and 3000.
Here, we choose Di = 0.1/di and α = 1.01.
From both figures, the diﬀusion-type flow control canbe seen to achieve high performance, but adapting to the
network conditions.
7.

Conclusions

This paper has presented the performance and stability ofthe diﬀusion-type flow control mechanism in the frameworkof an autonomous decentralized system capable of supporting high-speed networks. In this framework, nodes handle

TAKANO et al.: AUTONOMOUS DECENTRALIZED FLOW CONTROL IN HIGH-SPEED NETWORKS

1559

Fig. 18

Network model with multiple bottlenecks.

work are diﬀerent.
Finally, we briefly discuss the qualitative characteristics of the values of α and D. The previous studies [4],[5] showed that the diﬀusion-type flow control with α > 1achieves rapid recovery of the total throughput when the bottleneck link is restored. However, a larger value of α may
cause instability in the total throughput. If we can choose alarge value of D, the instability caused by α may be limited.
If we determine the transmission rate using Eq. (3), alarger value of D is appropriate because the corresponding
diﬀusion equation exhibits rapid diﬀusion and so the packet
density is reduced quickly. However, since there is the constraint on the bandwidth Li , we determine the transmission
rate by Eq. (5) instead of Eq. (3). A large value of D causes alarge diﬀerence between Eq. (3) and Eq. (5). Since the transmission rate determined by Eq. (3) is essential for the diﬀusion eﬀect, the diﬀerence prevents the smooth diﬀusion of
the packet distribution.
The issue of the optimal values of α and D is for further
study.
References

Fig. 19 Total throughput of network (mean interval of flow arrival =1000 units of time; mean lifetime of flow = 2000 units of time).

Fig. 20 Total throughput of network (mean interval of flow arrival =3000 units of time; mean lifetime of flow = 3000 units of time).

their local traﬃc flows themselves based only on the information immediately available to them.
We have proposed an extension of the diﬀusion-typeflow control model in order to apply it to networks withinhomogeneous link delays. The extension is based on an
investigation of the appropriate value of the diﬀusion coeﬃcient, Di , in our flow control model, and we found thecondition Di ∝ 1/di by comparison with the diﬀusion equation.
We have shown simulation results for two cases: different propagation delays and multiple bottlenecks. Bothresults have shown that the proposed diﬀusion-type flow
control achieves high and stable performance even when the
network is congested.
In particular, if we choose the diﬀusion coeﬃcient as
Di ∝ 1/di , the diﬀusion-type flow control copes with increased complexity in the network model, and achieves highperformance and stability even if the link delays in the net-

[1] M. Aida and K. Horikawa, “Stability analysis for global performance of flow control in high-speed networks based on statisticalphysics,” IEICE Trans. Commun., vol.E82-B, no.12, pp.2095–2106,
Dec. 1999.
[2] K. Horikawa, M. Aida, and T. Sugawara, “Traﬃc control scheme
under the communication delay of high-speed networks,” Proc.
Int. Conf. on Multi-Agent Systems (ICMAS’96), pp.111–117, Dec.
1996.
[3] M. Aida and C. Takano, “Stability of autonomous decentralized flow
control schemes in high-speed networks,” Proc. IEEE ICDCS 2002
Workshop (ADSN 2002), pp.63–68, July 2002.
[4] 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.
[5] C. Takano and M. Aida, “Stability and adaptability of autonomous
decentralized flow control,” Proc. 6th International Symposium on
Autonomous Decentralized Systems (ISADS 2003), pp.311–318,
Pisa, Italy, April 2003.
[6] 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 (FOCS), pp.303–312,
Oct. 1997.
[7] B. Awerbuch and Y. Azar, “Local optimization of global objectives: Competitive distributed deadlock resolution and resource allocation,” Proc. 35th Ann. IEEE Symp. on Foundations of Computer
Science, pp.240–249, 1994.
[8] D. Lapsley and S. Low, “An IP implementation of optimization flow
control,” Proc. IEEE GLOBECOM’98, Nov. 1998.
[9] 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.
[10] K. Kar, S. Sarkar, and L. Tassiulas, “A simple rate control algorithm
for maximizing total user utility,” Proc. IEEE INFOCOM 2001,
pp.133–141, 2001.
[11] B. Awerbuch and Y. Shavitt, “Converging to approximated maxmin flow fairness in logarithmic time,” Proc. IEEE INFOCOM’98,
pp.1350–1377, March 1990.
[12] S. Kunniyur and R. Srikant, “A decentralized adaptive ECN marking
algorithm,” Proc. IEEE GLOBECOM’00, pp.1719–1723, 2000.
[13] J. Mo and J. Walrand, “Fair end-to-end window based congestion

IEICE TRANS. COMMUN., VOL.E87–B, NO.6 JUNE 2004

1560

control,” IEEE/ACM Trans. Netw., vol.8, no.5, pp.556–567, Oct.
1999.
[14] R. Johari and D. Tan, “End-to-end congestion control for the Internet: Delays and stability,” IEEE/ACM Trans. Netw., vol.9, no.6,
pp.818–832, Dec. 2001.
[15] F. Bonomi, D. Mitra, and J.B. Seery, “Adaptive algorithms for
feedback-based flow control in high-speed, wide-area ATM networks,” IEEE J. Sel. Areas Commun., vol.13, no.7, pp.1267–1283,
Sept. 1995.
[16] D. Mitra, “Optimal design of windows for high speed data networks,” Proc. INFOCOM’90, pp.1156–1163, 1990.

Chisa Takano
received the B.E. in Telecommunication Engineering from Osaka University,
Japan, in 2000. In 2000 she joined the Traffic Research Center, NTT Advanced Technology Corporation (NTT-AT). She has been engaged in research and development of computer
networks. She received IEICE’s Young Investigators Award in 2003 and Information Network
Research Award in 2004.

Masaki Aida
received his B.Sc. and M.Sc.
in Theoretical Physics from St. Paul’s University, Tokyo, Japan, in 1987 and 1989, and received the Ph.D. in Telecommunication Engineering from the University of Tokyo, Japan,
in 1999. Since joining NTT Laboratories in
1989, he has been mainly engaged in researchon traﬃc issues in ATM networks and computercommunication networks. From March 1998 to
March 2001, he was a manager at the Traﬃc Research Center, NTT Advanced Technology Corporation (NTT-AT). He is currently a Senior Research Engineer at NTT
Information Sharing Platform Laboratories. His current interests include
traﬃc issues in communication systems. He received IEICE’s Young Investigators Award in 1996, and Information Network Research Awards of
IEICE in 2001, 2002, 2003, and 2004. Dr. Aida is a member of the IEEEand the Operations Research Society of Japan.

Shin-ichi Kuribayashi
received his B.E.,
M.E., and Ph.D. in engineering from Tohoku
University, Sendai, in 1978, 1980, and 1988 respectively. He joined the NTT Electrical Communications Labs in 1980. He has been engaged in the design and development of DDX
and ISDN packet switching, ATM, PHS, and the
IMT2000 and IP-VPN systems. He researched
distributed communication systems at Stanford
University from December 1988 through December 1989. He participated in international
standardization on the ATM signaling and IMT2000 signaling protocols at
the ITU-T SG11 from 1990 through 2000. He received Information Network Research Award in 2004. Since April 2004, he has been a Professor in
Department of Applied Physics, Faculty of Engineering, Seikei University.