IEICE TRANS. COMMUN., VOL.E86–B, NO.10 OCTOBER 2003

2882

PAPER

IEICE/IEEE Joint Special Issue on Assurance Systems and Networks

Stability and Adaptability of Autonomous Decentralized
Flow Control in High-Speed Networks∗
Chisa TAKANO†a) and Masaki AIDA†† , Regular Members

SUMMARY This paper focuses on ﬂow control in high-speed
networks. Each node in a network handles its local traﬃc ﬂow on
the basis of only the information it is aware of, but it is preferable
that the decision-making of each node leads to high performanceof the whole network. To this end, we investigate the relationshipbetween the ﬂow control mechanism of each node and network
performance. We consider the situation in which the capacity of alink in the network is changed but individual nodes are not awareof this. Then we investigate the stability and adaptability of the
network performance, and discuss an appropriate ﬂow control
model on the basis of simulation results.
key words: autonomous decentralized system, flow control, diffusion, feedback

1.

Fig. 1

Eﬀect of large bandwidth-delay product.

Fig. 2

Example of bandwidth-delay product.

Introduction

In a high-speed network, propagation delay becomes
the dominant factor in the transmission delay because
the speed of light is an absolute constraint. Therefore, at any given time, a large amount of data is being
propagated on links in the network. Figure 1 shows
the situation where packets are transmitted in a lowspeed/high-speed network. In a low-speed network, adestination node may already receive a ﬁrst bit of apacket before the local node ﬁnishes transmitting allbits of the packet completely. In the high-speed network, on the other hand, there may be the case wheremost of those packets have not yet reached the destination node in spite of having transmitted many packets
from the local node. These packets mean that they are
just being transmitted on a link. The amount of suchdata is characterized by the bandwidth-delay product,i.e., the propagation distance multiplied by the transmission rate. Therefore, in high-speed and/or longdistance transmission, there is more data in transit on
the links than there is in the nodes [1].
Figure 2 shows an example of how much data there
can be on a link. Let us consider the situation involving data transmission between two nodes, a distance ofManuscript received March 7, 2003.
Manuscript revised May 15, 2003.
†
The author is with Traﬃc Engineering Division, NTT
Advanced Technology Corporation (NTT-AT), Musashinoshi, 180-0006 Japan.
††
The author is with NTT Information Sharing Platform
Laboratories, NTT Corporation, Musashino-shi, 180-8585
Japan.
a) E-mail: chisa@m.ieice.org∗
A part of this paper was presented at IEEE ICDCS
Workshop (ADSN 2002) [2] and at IEEE ISADS 2003 [3].

1 km apart with a link speed of 1 Mbps. If the transmission speed is increased to 1 Gbps, the amount ofdata on the link is equivalent to that on 103 km of a 1Mbps link. And, if the transmission speed is increased
to 1 Tbps, the data volume is equivalent to 106 km of a
1-Mbps link. This distance is about 2.5 times the distance between the earth and the moon. Consequently,
it is impossible to exert time-sensitive control based oncollecting global information about the network. If weallow to spend suﬃcient time to collect global information, the information so gathered is too old to apply
to time-sensitive control. So, in a high-speed network,
the frameworks of time-sensitive control are inevitablyautonomous decentralized systems [1]–[5].
This paper focuses on node-by-node ﬂow control
in networks, in which nodes handle their local traﬃc
ﬂow themselves based only on the information they
are aware of. It is, of course, preferable that the decision making of each node leads to high performancefor the whole network. In ﬂow control, we use the total
throughput of a network as a global performance measure [1]. We investigate the behavior of local packet
ﬂow and the global performance measure when a node
is congested, and discuss an appropriate ﬂow control
model on the basis of simulation results. In addition, weTAKANO and AIDA: STABILITY AND ADAPTABILITY OF AUTONOMOUS DECENTRALIZED FLOW CONTROL

2883

investigate the stability and adaptability of the network
performance when the capacity of a link is changed.
This paper is organized as follows: In Sect. 2, wediscuss related works, comparing them with our workby categorizing ﬂow control mechanisms. Section 3
presents a framework for our ﬂow control as an autonomous decentralized system. Section 4 describes two
diﬀerent ﬂow control models based on the frameworkdescribed in Sect. 3. Section 5 shows the simulation
model and conditions. Section 6 shows the simulation
results for the performance of the two diﬀerent ﬂow control models. Finally, we conclude this paper in Sect. 7.
2.

Related Works

In general, the mechanism used for ﬂow control forhigh-speed networks should satisfy the following requirements:• With regard to the collection of information: it
must be possible to collect the information used in
the control.
• With regard to the delay in applying control: thecontrol should take eﬀect immediately.
There are many other papers that study optimizationof ﬂow control problems in a framework of solving linear
programs [6]–[10]. Their works assume the collection of
global information about the network, but it is impossible to realize such a centralized control mechanism inhigh-speed networks. In addition, solving these optimization problems requires enough time to be available
for calculation, and so it is diﬃcult to apply them todecision-making in a very short time-scale.
Decentralized ﬂow control by end hosts including
TCP is widely used in the current networks, and there ismuch research in this area [9]–[11]. However, since theend-to-end or the end-to-node control does not apply todecision-making in a time-scale shorter than the roundtrip delay, it is insuﬃcient to apply to decision-making
in very short time-scale.
In this paper, we propose a simple and eﬀective
method of ﬂow control, which satisﬁes the two above
requirements. The concept of our autonomous decentralized control method is based on [4] and our method
gives a stable state of the whole network via local decision making at each node. Since the proposed control
method uses less information than the control methods
described in our previous studies [1], [5], the proposed
control is relatively simple.
3.

Preliminary Description of Flow Control

3.1 Performance Measure
Each packet in a network is either in a node or on alink. Since the packets currently stored in nodes are
not being transmitted over the network, it is natural to

Fig. 3

Interaction between nodes.

deﬁne the total throughput of the network as a global
performance measure as follows. We deﬁne the total
throughput of a network at time t as the amount of data
being propagated on the network [1]–[5], [12]. In otherwords, it is the number of packets being propagated on
all links in the network at time t.
On the other hand, the only packets we can control
are those stored in nodes, and not those being propagated. Thus, higher performance of the whole network
involves many uncontrollable packets being propagatedon links. Therefore, inappropriate ﬂow control cannot
produce a state that has high performance and stability.
3.2 Node Model
Figure 3 shows the interaction of our ﬂow control between nodes using the network model with a simple
1-dimensional conﬁguration. All nodes have two incoming links and two outgoing ones for a one-way
packet stream and feedback information, that is, nodei (i = 0, 1, 2, . . .) transfers packets to node i + 1 andnode i + 1 sends feedback information (node information) to node i. For simplicity, we assume that packets
have a ﬁxed length in bits.
All nodes are capable of receiving and sending
node information from/to adjacent downstream andupstream nodes, respectively. Each node i can receive
node information sent from the downstream node i + 1,
and can send its node information to the upstream nodei − 1.
When node i receives node information from downstream node i + 1, it determines the transmission rate
for packets to the downstream node i + 1 using the received node information and adjusts its transmission
rate towards the downstream node i + 1. The framework of node behavior and ﬂow control is summarized
as follows:• Each node i autonomously determines the transmission rate Ji based only on information it isaware of, i.e., the node information obtained fromthe downstream node i + 1 and its own node information.
• The rule for determining the transmission rate is
the same for all nodes.
• Each node i adjusts its transmission rate towards
the downstream 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 informa-

IEICE TRANS. COMMUN., VOL.E86–B, NO.10 OCTOBER 2003

2884

tion according to a predeﬁned rule and sends it tothe upstream node i − 1.
• The rule for creating the node information is thesame for all nodes.
• Packets and node information both experience thesame propagation delay.

continuous approximation. Then the propagation delay becomes di → 0 for all i and the packet ﬂow isexpressed as

As mentioned above, the framework of our ﬂow control model involves both autonomous decision-making
by each node and interaction between adjacent nodes.
There is no centralized control mechanism in the network. More precisely, it is impossible to achieve centralized control in a high-speed network environment.
Hereafter, we investigate the behavior of the total network performance driven by two diﬀerent ﬂow control
schemes, applied for diﬀerent processes used to determine the transmission rate.

and the temporal variation of the number of packets at
x is expressed as a diﬀusion type equation,

3.3 Packet Flow
In this paper, we focus on the stability and adaptabilityof ﬂow control in the congested state, and we consider
packet ﬂow in a heavy-traﬃc environment. The packet
ﬂow is deﬁned as the number of sent packets per unitof time, and it is the same as the transmission rate
toward the downstream node in a heavy-traﬃc environment. That is, we let the packet ﬂow be Ji (t) if thetransmission rate speciﬁed by node i is Ji (t). This isbecause node i has suﬃcient packets to transfer. Hereafter, we identify the packet ﬂow with the transmission
rate speciﬁed by the node.
The packet ﬂow Ji (t) should be controlled by
the behavior of node i in the framework described in
Sect. 3.2. This means the packet ﬂow can be expressedusing the node information obtained from the downstream node i + 1 and its own node information. We
deﬁne the packet ﬂow as
Ji (t) := α ri (t − di ) − D (ni+1 (t − di ) − ni (t)), (1)where ni (t) denotes the number of packets in node i attime t, ri (t−di ) is the target transmission rate speciﬁedby the downstream node i + 1 as node information, α(> 0) and D (≥ 0) are constants, and di denotes the
propagation delay between node i and node i + 1. In
addition, (ri (t − di ), ni+1 (t − di )) is notiﬁed from thedownstream node i + 1 with the propagation delay di .
The ﬁrst term on the right hand side of Eq. (1) reﬂects
the target rate speciﬁed by the downstream node, andthe second term, which is called the diﬀusion term, is
proportional to the gradient of the packet density. We
call α and D the ﬂow intensity multiplier and the diffusion coeﬃcient, respectively.
If there is no packet loss in the network, the temporal variation of ni (t) is expressed asni (t + ) − ni (t) =[Ji−1 (t − di−1 ) − Ji (t)] ,(2)

where > 0 is a small number. To estimate the temporal variation roughly, we replace i with x and applyJ(x, t) = α r(x, t) − D∂n(x, t),∂x∂r(x, t)∂ 2 n(x, t)∂n(x, t)
= −α
+D
,
∂t
∂x
∂x2

(3)

(4)

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

(5)

That is, our method aims to perform ﬂow control using
the analogy of a diﬀusion phenomenon. We can expectthat packets in the congested node to be distributed to
the whole network and normal network conditions to
be restored after some time.
Hereafter, we consider two types of ﬂow control
and compare them. One type handles the ﬁrst term
and the other controls the ﬁrst and second terms on
the right hand side of Eq. (1).
4.

Flow Control Models

4.1 Drift-Type Flow Control
In this subsection, we set D = 0 in Eqs. (1) and (3), andinvestigate the characteristics of a ﬂow control scheme
whose packet ﬂow is determined only by the ﬁrst termon the right hand side of Eq. (1).
Let the number of packets in the network be N . To
obtain higher network performance, ﬂow control should
enable a state in which many packets are being propagated on links. This state corresponds to a state inwhich there are fewer packets in nodes.
The simplest strategy for achieving this state is foreach node to attempt to decrease the number of packets
in it. Therefore, the temporal variation of ni (t) shouldbeni (t + ) − ni (t) < 0.

(6)

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

(7)

However, if all nodes use this strategy, then the total
throughput decreases with time as a result. Therefore,
the strategy described by Eq. (7) cannot be used continuously.
Conversely, if we use the rate speciﬁed to the upstream node as
ri−1 (t) > ri (t − di ),(8)

TAKANO and AIDA: STABILITY AND ADAPTABILITY OF AUTONOMOUS DECENTRALIZED FLOW CONTROL

2885

then ni (t) increases with respect to time (when there
are many packets in the upstream node). But the buﬀer
in each node has a ﬁnite capacity, so this strategy described by Eq. (8) cannot be used continuously either.
If we set the rate speciﬁed to the upstream nodeasri−1 (t) = ri (t − di ),(9)then ni (t) does not change with respect to time undera heavy traﬃc condition. This means that the strategy
described by Eq. (9) does not diminish the total performance of the network. However, when some node iscongested, its restoration requires a long time. Thus,
the strategy described by Eq. (9) can also not be used
continuously.
From the above considerations, we choose the following strategy. The rate speciﬁed from node i to the
upstream node i − 1 is determined according to thestate of node i. Let the objective of ni be ns . If
ni (t) > ns , then ri−1 (t) is speciﬁed by using Eq. (7);if ni (t) < ns , then ri−1 (t) is speciﬁed by using Eq. (8);and if ni (t) = ns , then ri−1 (t) is speciﬁed by using
Eq. (9).
Since the above ﬂow control uses the value of ni (t),we call it drift-type ﬂow control in this paper.
4.2 Diﬀusion-Type Flow Control
In this subsection, we set D > 0 in Eqs. (1) and (3),and investigate the characteristics of the ﬂow control
scheme whose packet ﬂow is determined by both drift
and diﬀusion terms.
In this control scheme, node i’s packet transmission rate to the downstream node i + 1 is determinedasJi (t) = α ri (t − di ) − D (ni+1 (t − di ) − ni (t)).
(10)
In addition, the node information of node i sent to the
upstream node i − 1 is determined asri−1 (t) = Ji (t).

(11)

In the framework of Eqs. (10) and (11), the node information of i speciﬁed to the upstream node i − 1 is apair of values (ri−1 (t), ni (t)).
In the case where D = 0 and α = 1, Eqs. (10)and (11) reduce to a drift-type ﬂow control speciﬁed by
Eq. (9). However, for D > 0, since we can control thediﬀusion term.
Since the above ﬂow control uses the diﬀusion
term, we call it the diﬀusion-type ﬂow control in thispaper.

5.

Simulation ModelIn this section, we consider a simple network modelwith a bottleneck link having a narrow bandwidth forcomparing the performance of the two diﬀerent ﬂow
control principles described in the previous sections.
5.1 Network Model
Figure 4 shows our network model, which is a
closed network with a 1-dimensional conﬁguration andtoroidal boundary. The network has a bottleneck link
and a corresponding congested node. All the othernodes and links are in the same condition. This model
simulates the situation when congestion occurs at a certain node. We are interested in the behavior of the local
congestion, that is, whether:• it causes deterioration of the total network performance through interaction among nodes, or• it diminishes with time.
Detailed conditions of our network model are listed
below.
• Number of nodes: m = 60. Each node speciﬁed byi (mod 60).
• Propagation delay between adjacent nodes: 1 (unittime)• Index of the congested node: i = 29
• Total number of packets in the network: N = 6000
• Maximum number of packets on a link (except thebottleneck link): Lc = 100• Maximum number of packets on the bottleneck
link (between nodes i = 29 and 30): Lb = 10,
25, 50, or 75(that is, 1/10, 1/4, 1/2, or 3/4 of the bandwidthof other links, and the same length)
To investigate the stability under congestion, in addition to the above conditions, we set the initial condition
for congested node i = 29 as follows.
• Number of packets in node i = 29 at time t = 0:400
• The other 5600 packets are randomly conﬁgured inother nodes and on other links.

Fig. 4

Network model with a bottleneck link.

IEICE TRANS. COMMUN., VOL.E86–B, NO.10 OCTOBER 2003

2886

5.2 Drift- and Diﬀusion-Type Flow Control Schemes
As a model for the drift-type ﬂow control, we set an
objective for the number of packets in a node to bens = 60, and set the following transmission rate andnode information.
Ji (t) = min(ri (t), Li ), Ji (t) − Li /10
Ji (t)
ri−1 (t) =Ji (t) + Li /10(12)(ni (t) > ns ),(ni (t) = ns ),(ni (t) < ns ),(13)

where Li denotes the link capacity between nodes i and
i + 1.
As a model for the diﬀusion-type ﬂow control,
Eqs. (10) and (11), we use the following ﬂow control
model. Since the packet ﬂow is restricted by the link
capacity, the diﬀusion-type ﬂow control is expressed asfollows:(14)
Ji (t) = min(max(J˜i (t), 0), Li ),ri−1 (t) = Ji (t),6.1 Stability and Adaptability in the Case of the Appearance of a Bottleneck Link
This subsection considers the case where the capacityof a link in the network is suddenly reduced to a narrow
bandwidth. No node is aware of the change of the linkstate and new capacity of the link. We investigate thestability and adaptability of the drift- and diﬀusiontype control models through the observation of the total
throughput of the network.
Figures 5, 6 and 7 show the total throughput for
drift- and diﬀusion-type (with α = 1.00 and 1.01) ﬂow
control models, respectively. The horizontal axis denotes the simulation time and the vertical axis denotes
the total throughput (i.e., the total number of packet
being propagated on links). Each line in these ﬁgures

(15)

where
J˜i (t) = α ri (t − di ) − D (ni+1 (t − di ) − ni (t)) (16)Lb ,(i = 29),(17)
Li =(otherwise),Lc ,α = 1.00 or 1.01,
D = 0.1.

(18)
(19)

The value of α (> 1) determines the increase speed of
the average rate of the packet ﬂow. If the value of α
becomes larger, recovery time of throughput will become much less when the capacity of a bottleneck link
is recovered. We want to investigate whether the total
throughput is recovered or not, even if the diﬀerence between the value of α and 1 is little, so we use the above
two values of α as the simulation model. The value of
D determines the speed of smoothing the distributionof the number of packets. If D takes a larger value,then the packet ﬂow of the whole network will smoothquickly, in an ideal situation. However, in an actual
situation, if we set a large value of D, the packet ﬂow isfrequently restricted by the capacity of the link throughmin operation in Eq. (14). In this case, diﬀusion phenomena do not appear in packet ﬂow behaviors. We set
comparatively small D, since we expect that behaviorsof the packet ﬂow simulate diﬀusion phenomena.
6.

Fig. 5 Temporal behavior and stability of the total throughputof the network for the drift-type ﬂow control scheme.

Fig. 6 Temporal behavior and stability of the total throughputof the network for the diﬀusion-type ﬂow control scheme (α =1.00, D = 0.1).

Simulation Results: Stability and Adaptability

From the simulation results for the drift- and diﬀusiontype control models, we compare the total throughputof the network. In addition, we discuss the stability
and adaptability of the both types of ﬂow control modelthrough the observation of the total throughput.

Fig. 7 Temporal behavior and stability of the total throughputof the network for the diﬀusion-type ﬂow control scheme (α =1.01, D = 0.1).

TAKANO and AIDA: STABILITY AND ADAPTABILITY OF AUTONOMOUS DECENTRALIZED FLOW CONTROL

2887

Fig. 8 Distribution of the number of packets stored in each node for the drift-type ﬂow
control scheme (Lb = 10, ns = 60).

Fig. 9 Distribution of the number of packets stored in each node for the diﬀusion-type
ﬂow control scheme (Lb = 10, α = 1.0, D = 0.1).

Fig. 10 Distribution of the number of packets stored in each node for the diﬀusion-type
ﬂow control scheme (Lb = 10, α = 1.01, D = 0.1).

shows the result in the case of the capacity of the bottleneck link, Lb = 10, 25, 50, or 75.
Figure 5 shows the drift-type ﬂow control scheme
achieves high total throughput in the cases where Lb =25, 50 and 75. However, in the other case where Lb =10, i.e., the capacity of the bottleneck link is small, thedrift-type fails to control the total throughput, whichfalls to zero with time.
From Figs. 6 and 7, on the other hand, thediﬀusion-type ﬂow control schemes achieve stable total throughput of the network. It is remarkable thatstability is achieved irrespective of the value of Lb .
The diﬀusion-type with α = 1.01 achieves higher total
throughput than that obtained from the diﬀusion-type
with α = 1.00 for all the values of Lb .
We discuss the results from a quantitative point ofview. Let us compare two types of ﬂow control schemesin the case where Lb = 10, i.e., 1/10 of the other link
capacities. For the drift-type control model, the total
throughput decreases with time. This means that theﬂow control model inappropriately inﬂuences the global
performance of the network. For the diﬀusion-type control models, on the other hand, the total throughput decreases with time but becomes stable around 270 (forα = 1.00) and 600 (for α = 1.01). From the link capacity of the bottleneck link Lb , the maximum value of thesustainable total throughput (the maximum number ofpackets being propagated stably on links) is 600, i.e., 10
packets/link × 60 links. Thus, the diﬀusion-type ﬂow
control model with α = 1.00 achieves only 45% of the
maximum value of the total throughput, but that with
α = 1.01 causes the almost 100% total throughput.

Next, in the case where the total throughput isdecreasing, we investigate the movement of packets inthe network model.
Figure 8 shows the simulation result for the drifttype ﬂow control model when Lb = 10. The horizontal
axis of each graph denotes node ID and the vertical axis
denotes the number of packets stored in the node. In
addition, t denotes the simulation time and initially t =0. For the drift-type ﬂow control model, the number ofpackets in the congested node i = 29 decreases withtime, but and the number of packets stored in eachnode is uneven at t = 1000.
Similarly, Figs. 9 and 10 show the simulation results for the diﬀusion-type ﬂow control model under
the same conditions as described for Fig. 8. We choseparameters as α = 1.00 and 1.01, respectively, and
D = 0.1. In both ﬁgures, the number of packets in congested node i = 29 decreases with time. For the diﬀusion ﬂow controls with both α = 1.00 and α = 1.01, thedistribution of the number of packets stored in nodes issmoothly distributed over the network at t = 1000.
If we can choose an appropriate value of the objective ns for the drift-type ﬂow control, the total throughput may be stable and adaptive. The case where
Lb = 25, 50 or 75 implies that this is feasible. However, the value of ns should depend on the bandwidthof the bottleneck link as recognized from Fig. 5. Since
nodes cannot be aware of information about the bandwidth in a high-speed network environment, the drifttype control cannot achieve high performance. On theother hand, in the diﬀusion-type control models bothfor α = 1.00 and 1.01, although no node is aware of theIEICE TRANS. COMMUN., VOL.E86–B, NO.10 OCTOBER 2003

2888

Fig. 11 Temporal behavior and stability of the total throughput of the network for thedrift-type ﬂow control scheme and three diﬀerent times at which the bottleneck is restored.

Fig. 12 Temporal behavior and stability of the total throughput of the network for thediﬀusion-type ﬂow control scheme (α = 1.00, D = 0.1) and three diﬀerent times at which
the bottleneck is restored.

Fig. 13 Temporal behavior and stability of the total throughput of the network for thediﬀusion-type ﬂow control scheme (α = 1.01, D = 0.1) and three diﬀerent times at which
the bottleneck is restored.

bandwidth of the bottleneck link, stable performance isachieved. Especially, the diﬀusion-type control modelwith α = 1.01 provides the higher total throughput
than that with α = 1.00.
6.2 Stability and Adaptability in the Case of Restoration of a Bottleneck Link
This subsection considers the situation where the capacity of the bottleneck link is suddenly restored. No
node is aware of the change of the link state and therestored capacity of the link. We investigate the stability and adaptability of both types of control throughobservation of the total throughput of the network.
Figures 11, 12 and 13 show the total throughput inthe case where the capacity of the bottleneck link Lb isrestored to 100 at time t = 100, 200, and 300 for thesemodels. These ﬁgures show the results for drift-typeand diﬀusion-types with α = 1.00 and 1.01. The horizontal axis denotes the simulation time and the verticalaxis denotes the total throughput. A broken line indicates the time when the capacity of the bottleneck l
ink is restored. The simulation conditions are the sameas the case for the previous subsection except for the
restoration of the bottleneck link. We show the cases offour diﬀerent capacities of the bottleneck link, Lb = 10,
25, 50, and 75.
In the cases where Lb = 25, 50 and 75, the drifttype ﬂow control restores high total throughput ofaround 6000 as shown in Fig. 11. It is independent of
the time when the restoration occurs. However, in thecase where Lb = 10, i.e., the initial capacity of the bottleneck link is small, for the drift-type ﬂow control the
total throughput falls to zero with time. There is nochange in the total throughput, even if the capacity ofthe bottleneck link is restored at time t = 300.
On the other hand, the diﬀusion-type ﬂow control
with α = 1.00 achieves stable total throughput of the
network in Fig. 12. However, although the capacity ofthe bottleneck link is restored, the total throughput is
not restored in any of the cases. This is because we
set the ﬂow intensity multiplier of α = 1.00 for thediﬀusion-type ﬂow control. This setting of the ﬂow intensity multiplier is derived from Eq. (9) for balancing
input and output ﬂows.
Figure 13 shows that the diﬀusion-type ﬂow control

TAKANO and AIDA: STABILITY AND ADAPTABILITY OF AUTONOMOUS DECENTRALIZED FLOW CONTROL

2889

Fig. 14 Temporal behavior and stability of the total throughput for the diﬀusion-type
ﬂow control scheme (α = 1.01, D = 0.1) when the capacity of the bottleneck is alternately
restricted and restored.

with α = 1.01 achieves stable total throughput of the
network and it is adaptively restored in all of the cases
when the link capacity is restored. This characteristic
is came from the ﬂow intensity multiplier of α > 1.
6.3 Stability and Adaptability in the Case where a
Bottleneck Appears and Recovers RepeatedlyThis subsection considers the situation where the capacity of the bottleneck link alternates between normal and restricted values. No node is aware of thechanges in the link state. We investigate the stability
and adaptability of the diﬀusion-type control with theﬂow intensity multiplier of α > 1 through observationof the temporal behavior of the total throughput of the
network.
Figure 14 shows the total throughput in case where
the bottleneck appears and recovers repeatedly for thediﬀusion-type control with α = 1.01. The capacitiesof the bottleneck links are Lb = 10, 25, 50, and 75,
respectively. The horizontal axis denotes the simulation
time and the vertical axis denotes the total throughput.
The period of the bottleneck link being alternatelychanged between appearance and restoration is 1000.
Simulation conditions are the same as the case for theprevious subsection except for the state of the bottleneck link. In all cases, the diﬀusion-type control with
α = 1.01 achieves the adaptable global performance ofthe network.
7.

Conclusions

This paper has presented a framework for ﬂow control
in high-speed networks as an autonomous decentralized
system. We have showed two typical node-by-node ﬂow
control models based on the framework. The drift-type
ﬂow control depends on the number of packets in anode and the diﬀusion-type ﬂow control depends onthe gradient of the number of packets in a node. For
both types of control, nodes handle their local traﬃc
ﬂow themselves based only on the information they areaware of.
To investigate the behavior of local packet ﬂow
and the global performance measure when a node
is congested, we compared two types of the models
through simulations. For comparison, we used the total
throughput as the ﬂow control performance measure.

Although the drift-type control cannot achieve
high performance adaptively, the diﬀusion-type does
achieve stable performance in congested situations. In
particular, the diﬀusion-type control with the ﬂow intensity multiplier of α > 1 achieves high performance
adaptively, even in a situation in which the congested
state changes dynamically.
We are interested in the appropriate values of the
ﬂow intensity multiplier and the diﬀusion coeﬃcients,
α and D. These issues will be the subject of further
study.
References[1] M. Aida and K. Horikawa, “Stability analysis for global
performance of ﬂow control in high-speed networks basedon statistical physics,” IEICE Trans. Commun., vol.E82-B,
no.12, pp.2095–2106, Dec. 1999.
[2] M. Aida and C. Takano, “Stability of autonomous decentralized ﬂow control schemes in high-speed networks,” Proc.
IEEE ICDCS 2002 Workshop (ADSN 2002), pp.63–68, July
2002.
[3] C. Takano and M. Aida, “Stability and adaptability of autonomous decentralized ﬂow control,” Proc. 6th International Symposium on Autonomous Decentralized Systems(ISADS 2003), pp.311–318, Pisa, Italy, April 2003.
[4] M. Aida and C. Takano, “Principle of autonomous decentralized ﬂow control and layered structure of network control with respect to time scales,” Supplement of the ISADS
2003 Conf. Fast Abstracts, pp.3–4, Pisa, Italy, April 2003.
[5] 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.
[6] Y. Bartal, J. Byers, and D. Raz, “Global optimization using
local information with applications to ﬂow control,” Proc.
38th Ann. IEEE Symp. on Foundations of Computer Science, Oct. 1997.
[7] 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.
[8] S.H. Low and D.E. Lapsley, “Optimization ﬂow controlI: Basic algorithm and convergence,” IEEE/ACM Trans.
Netw., vol.7, no.6, pp.861–874, 1999.
[9] S. Kunniyur and R. Srikant, “A decentralized adaptive
ECN marking algorithm,” Proc. IEEE GLOBECOM 2000,
pp.1719–1723, 2000.
[10] J. Mo and J. Walrand, “Fair end-to-end window basedcongestion control,” IEEE/ACM Trans. Netw., vol.8, no.5,
pp.556–567, Oct. 1999.
[11] R. Johari and D.K.H. Tan, “End-to-end congestion control
for the internet: Delays and stability,” IEEE/ACM Trans.
Netw., vol.9, no.6, pp.818–832, 2001.

IEICE TRANS. COMMUN., VOL.E86–B, NO.10 OCTOBER 2003

2890

[12] D. Mitra, “Optimal design of windows for high speed data
networks,” Proc. IEEE INFOCOM’90, pp.1156–1163, 1990.

Chisa Takano
received the B.E. degree in Telecommunication Engineeringfrom Osaka University, Japan, in 2000. In
2000 she joined Traﬃc Research Center,
NTT Advanced Technology Corporation(NTT-AT). She has been engaged in research and development of computer networks. She received the Young Investigators Award of IEICE in 2003.

Masaki Aida
received his B.Sc. and
M.Sc. degrees in Theoretical Physics from
St. Paul’s University, Tokyo, Japan, in
1987 and 1989, and received the Ph.D.
degree in Telecommunication Engineeringfrom the University of Tokyo, Japan, in
1999. Since joining NTT Laboratories in
1989, he has been mainly engaged in research on traﬃc issues in ATM networks
and computer communication networks.
From March 1998 to March 2001, he was amanager at 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 the Young Investigators Award of IEICE in 1996.
Dr. Aida is a member of the IEEE and the Operations ResearchSociety of Japan.