IEICE TRANS. COMMUN., VOL.E88–B, NO.4 APRIL 2005

1559

PAPER

Diﬀusion-Type Autonomous Decentralized Flow Control for
End-to-End Flow in High-Speed Networks
Chisa TAKANO†a) and Masaki AIDA††b) , Members

SUMMARY
We have proposed diﬀusion-type flow control as a solution for the extremely time-sensitive flow control required for high-speed
networks. In our method of flow control, we design in advance simple andappropriate rules for action at the nodes, and these automatically result instable and eﬃcient network-wide performance through local interactions
between nodes. Specifically, we design the rules for the flow control actionof each node that simulates the local interaction of a diﬀusion phenomenon,
in order that the packet density is diﬀused throughout the network as soon
as possible. However, in order to make a comparison with other flow control methods under the same conditions, the evaluations in our previous
studies used a closed network model, in which the number of packets was
unchanged. This paper investigates the performance of our flow control
method for an end-to-end flow, in order to show that it is still eﬀective inmore realistic networks. We identify the key issues associated with our flow
control method when applied to an open network model, and demonstrate
a two-step solution. First, we consider the rule for flow control action at
the boundary node, which is the ingress node in the network, and propose
a rule to achieve smooth diﬀusion of the packet density. Secondly, we introduce a shaping mechanism, which keeps the number of packets in the
network at an appropriate level.
key words: flow control, diﬀusion, autonomous decentralized control, highspeed network

1.

Introduction

We have previously proposed diﬀusion-type flow control(DFC) as a solution for the extremely time-sensitive flow
control required for high-speed networks [1], [2]. The motivation of our work on flow control is to introduce a newframework of time-sensitive network control for high-speed
networks.
Delay in communication networks consists of processing delay and propagation delay. Processing delay is the delay experienced by a packet while waiting at nodes for transmission. This may be reduced if the processing speed of thenodes is increased. Propagation delay is the packet delay
experienced during propagation on links and is determinedby the link length and the speed of light. Unlike processing
delay, the propagation delay is fixed even if the processing
speed of the nodes is increased. So, if the processing speedof the nodes is made high enough, propagation delay beManuscript received May 12, 2004.
Manuscript revised October 29, 2004.
†
The author is with Traﬃc Engineering Division, NTT Advanced Technology Corporation (NTT-AT), Musashino-shi, 1800006 Japan.
††
The author is with the Faculty of System Design, Tokyo
Metropolitan University, Hino-shi, 191-0065 Japan.
a) E-mail: chisa@m.ieice.orgb) E-mail: aida@m.ieice.org
DOI: 10.1093/ietcom/e88–b.4.1559

Fig. 1

Eﬀect of large bandwidth-delay product.

comes the dominant part of the total delay.
In a high-speed network, it is impossible to implement
time-sensitive control based on collecting global information about the whole network because the state of a nodevaries rapidly, depending on its processing speed, while thepropagation delay is constant. If we allow suﬃcient time tocollect network-wide information, the gathered data is too
old to apply to time-sensitive control. In this sense, eachnode in a high-speed network is isolated from information
about the state of other nodes or of the overall network [3],[4]. In addition, when the propagation delay is dominant, at
any instant a large amount of data exists on the links. Figure 1 shows situations where packets are transmitted in lowspeed and in high-speed networks. In a low-speed network,
a destination node may receive the first bit of a packet before the local node has completely finished transmitting all
the bits of that packet. In a high-speed network, on the other
hand, there may be situations where most of the packets arein transit on links, that is they may not yet have reached thedestination node even though many other packets have since
been transmitted from the local node. The amount of suchdata in transit on links is characterized by the bandwidthdelay product, i.e., the propagation distance multiplied by
the transmission rate. Since the only packets we can control
are those the packets stored in nodes, high-speed networks
contain many packets which cannot be controlled. In thissituation, since the delay in applying control greatly aﬀects
the network performance, a very rapid control mechanism
is required, in which the control delay should be as short as
possible. So, in high-speed networks, the framework used
for time-sensitive control is inevitably that of autonomous
decentralized systems [2]–[4].
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:• It must be possible to collect the information used in

c 2005 The Institute of Electronics, Information and Communication Engineers
Copyright IEICE TRANS. COMMUN., VOL.E88–B, NO.4 APRIL 2005

1560

the control method.
• The control which is applied should take eﬀect immediately.
There are many other papers which report studies on
the optimization of flow control problems in a frameworkof solving linear programs [5]–[8]. These studies assume
the collection of global information about the network, but
it is impossible to realize such a centralized control mechanism in high-speed networks. In addition, solving these
optimization problems requires enough time to be available
for calculation, and so it is diﬃcult to apply these methods
to decision-making in an extremely short time-scale. Since
these control schemes are forms of centralized control, theycannot be adopted for high-speed networks.
Decentralized flow control by end hosts, including
TCP, is widely used in current networks, and there is muchresearch in this area [7]–[9]. However, since end-to-end or
end-to-node control cannot be applied to decision-making
in a time-scale shorter than the round-trip delay, it is inadequate for application to decision-making in an extremely
short time-scale. In low-speed networks, a control delay ofthe order of the round-trip time (RTT) has a negligible effect on the network performance. However, in high-speed
networks, such a control delay greatly aﬀects the network
performance.
Bartal et al. [10] studied the global optimization of flow
control using local information. The motivation for theirwork was to enable the distributed routers in high-speed
networks to make appropriate decisions on flow control asquickly as possible, and they studied the problem in a framework of solving linear programs by means of distributed
agents. Though this motivation is similar to that of our work,
their study assumed that the distributed agents can obtain detailed information about networks if we allow suﬃcient time
to gather it. As stated above, our standpoint is based on thefact that it is not possible to obtain detailed, useful, and upto-date information about the whole network in a high-speed
network environment.
In our previous studies, we investigated the behaviorof local packet flows and the network-wide performance
when a node is congested, and proposed DFC [1], [2]. In
addition, we investigated the stability and adaptability of
the network-wide performance when the network has inhomogeneous configurations with respect to link length [11].
DFC provides a framework in which the implementation ofdecision-making at each node leads to high performance forthe whole network. We used a closed network model forthe evaluation in this research because the number of packets in the network is unchanged in a closed network modeland it permits comparison with other control mechanisms
under the same conditions. To apply DFC to real networks,
there are some technical issues to be overcome. Particularly
important issues are:• applying DFC to an end-to-end flow (an open network),• compatibility and complementarity with other control
mechanism (e.g. TCP), and• applying DFC to multiple flows.
This paper discusses the application of DFC to an open network model. We identify the key issues in applying our flow
control to an open network and show a solution for them.
2.

Preliminary Description of Diﬀusion-Type Flow
Control

2.1 Diﬀusion-Type Flow Control Mechanism
Figure 2 shows the interactions between nodes in our flow
control method, using a network model with a simple 1dimensional configuration, which represents a part of a network along a flow path.
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, . . . , N) transfers packets to nodei + 1 and node i + 1 sends feedback information (consistingof information about node i + 1) to node i. For simplicity,
we assume that all packets have a fixed length in bits.
All nodes are capable of receiving and sending feedback information. Each node i can receive feedback information sent from the downstream node i + 1, and can send
feedback information about node i itself to the upstream
node i − 1.
When node i receives feedback information from thedownstream node i + 1, it determines the transmission rate
for packets to the downstream node i + 1 using the received
feedback information, and adjusts its transmission rate towards the downstream node i + 1. The framework for node
behavior and flow control may be summarized as follows:• When the feedback information (details are statedlater) from the downstream node i + 1 is received, eachnode i autonomously determines the transmission rate,
based only on information available to the node i itself.
The available information is feedback information obtained from the downstream node i+1 and node i’s own
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 the transmission rate
(If there are no packets 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. The interval for generating feedback information is proportional to the propagation delay, di−1 , between nodes i − 1 and i.

Fig. 2

Node interactions in our flow control model.

TAKANO and AIDA: DIFFUSION-TYPE AUTONOMOUS DECENTRALIZED FLOW CONTROL FOR END-TO-END FLOW

1561

• The rule for creating the feedback information is thesame for all nodes.
• Packets and feedback information both experience thesame propagation delay.
As mentioned above, the framework of our flow control
model involves both autonomous decision-making by eachnode and interaction between adjacent nodes. There is nocentralized control mechanism in the network.
Next, let us look at the details of DFC. The transmission rate Ji (α, t) of node i at time t is determined by
Ji (α, t) = max(0, min(Li (t), J˜i (α, t))),(1)J˜i (α, t) = α ri (t − di ) − Di (ni+1 (t − di ) − ni (t)),

(2)

and

where Li (t) denotes the value of link capacity between nodei and i+1 at time t, ni (t) denotes the number of packets stored
in node i at time t, ri (t − di ) is the target transmission rate
specified by the downstream node i+1 as feedback information, and di denotes the propagation delay between nodes i
and i + 1. In addition, ri (t − di ) and ni+1 (t − di ) are notified
from the downstream node i + 1 with a propagation delay di .
Parameter α (≥ 1) is a constant and is called the flow intensity multiplier. Parameter Di (> 0) is chosen to be inversely
proportional to the propagation delay [11] as follows:
Di = D1∝ (di )−1 ,di(3)where D is a positive constant and is called the diﬀusion
coeﬃcient.
The feedback information, Fi (t), created by node i consists of two quantities as follows:
Fi (t) = (ri−1 (t), ni (t)).

(4)

Node i notifies this to the upstream node i − 1. Here, thetarget transmission rate is determined asri−1 (t) = Ji (1, t).

(5)

2.2 Principle of Diﬀusion-Type Flow Control
There are phenomena in nature where local interactions on
the micro-scale produce symmetry on the macro-scale. For
example, local interactions among water molecules lead tohighly symmetrical snow flakes. By applying the proposedmechanism, although time-sensitive control on a short timescale can not make use of global information about the network, we may be able to control the network-wide performance through local decision making at the nodes.
In the framework of our control method, networkwide performance is controlled indirectly, but immediately,
through the application of a predefined rule for local decision making at nodes. Nodes at distant locations do not

Fig. 3

Example of thermal diﬀusion phenomenon.

communicate with each other. However, in spite of the constraint of the speed of light, appropriate control of networkwide performance may be achieved quickly. Since centralized control cannot implement performance control quickly
due to the constraint of the speed of light, our control may
actually appear to take eﬀect faster than the speed of light.
The principle of our flow control model can be explained through the following analogy [12], [13].
When we heat a point on a cold iron bar, the temperature distribution forms a normal distribution, and heatspreads through the whole bar as a diﬀusion phenomenon(Fig. 3). In this process, the action in a minute segment of
the iron bar is very simple; heat flows from the higher temperature side towards the lower temperature side. The rate ofheat flow is proportional to the temperature gradient. Thereis no direct communication between two distant segmentsof the iron bar. Although each segment acts autonomously,
based only on information available to it locally, the temperature distribution of the whole iron bar exhibits orderly
behavior.
Our flow control is based on the diﬀusion-type equation and we expect that any congestion in the network will
be dissipated with time, like diﬀusion phenomena. In ourframework, by designing an appropriate rule for decisionmaking at nodes, we can get the flow control mechanism
to work eﬀectively as an autonomous decentralized system.
The network-wide state of the network becomes the solutionof a certain temporal evolution equation. Although the behavior of each node obeys a predefined rule and its decision
is based only on local information, we can expect the performance of the whole network to exhibit an orderly patternof behavior.
In DFC, each node controls its local packet flow to a
locally-derived value; one term in the expression giving thisvalue is proportional to the diﬀerence between the numberof packets stored in the node and the number stored in theadjacent node and is inversely proportional to the distance
between these nodes (refer to the second term in Eq. (2)).
As a result the distribution of the number of packets stored
in the diﬀerent nodes in the network becomes uniform overtime. Using this control mechanism, the state of the wholenetwork is controlled indirectly through the autonomous action of each node.
Let us consider an example using continuous approximation for simplicity. After replacing i with x and di → 0,
the packet flow J(x, t) in our framework may be written as
J(x, t) = α r(x, t) − D∂n(x, t),∂x(6)where r(x, t) and n(x, t) denote the drift component of theIEICE TRANS. COMMUN., VOL.E88–B, NO.4 APRIL 2005

1562

flow and the number of packets, respectively, at position x
and time t. As each node handles the flow, it requires not
full, global information but only local information relating
to x and its immediate vicinity. So, autonomous decentralized control applies eﬀectively to this framework. The temporal evolution of the number of packets at x may be writtenas∂n(x, t)∂r(x, t)∂2 n(x, t)
.
= −α
+D
∂t
∂x
∂x2

(7)

Equation (7) is obtained by combining the continuous equation ∂n(x, t)/∂t = −∂J(x, t)/∂x and Eq. (6). Equation (7) isa diﬀusion-type equation and it will lead to a diﬀusion phenomenon with respect to the number of packets.
3.

Issues for Applying Diﬀusion-Type Flow Control to
an Open Network Model

This section investigates the key issues involved in applying the DFC mechanism described in the previous section
to an open network model. Figures 4 and 5 show the open
network models, each with 60 nodes, which were used in
the simulations. Although each 1-dimensional model looks
simple, it represents a part of a network and describes a pathof the target end-to-end flow extracted from the whole network. We represent the lengths of links by their delays, andthe lengths of the individual links are determined randomly,in advance, as they follow a log-normal distribution with amean of 1.0 [unit of time] and a variance of 5.2 [unit of
time2 ].
Our simulation scenario is to investigate the stability
under congestion caused by the presence of a bottleneck
link. The packet transmission rate of all links is Li = 100[packets/unit of time] except for the bottleneck link. We
consider two cases, corresponding to diﬀerent locations of
the bottleneck link; in case A (Fig. 4) the bottleneck link is
between nodes 30 and 31, and L30 = 50 [packets/unit oftime], while in case B (Fig. 5) it is between nodes 1 and 2,
and L1 = 50 [packets/unit of time].
There are 5700 packets in the network at t = 0, and all
the packets are distributed randomly on the links. We set
the values of the parameters as D = 0.1 and α = 1.0. At
the ingress point of the network, the rate of packet flow isregulated by r0 (t) which is specified by node 1.
Figures 6 and 7 show the results for cases A and B, respectively. The horizontal axis of each graph denotes node
ID and the vertical axis denotes the number of packets stored
in the node, i.e., the queue length in the node. In addition,

Fig. 4

Network configuration model (case A).

Fig. 5

Network configuration model (case B).

Fig. 6 Temporal evolution of distribution of packets stored in each node
for Case A.

Fig. 7 Temporal evolution of distribution of packets stored in each node
for Case B.

TAKANO and AIDA: DIFFUSION-TYPE AUTONOMOUS DECENTRALIZED FLOW CONTROL FOR END-TO-END FLOW

1563

Fig. 8 Total numbers of packets in transit on links (left) and stored in nodes (right) for DFC describedin Sect. 3.

Fig. 9 Total numbers of packets in transit on links (left) and stored in nodes (right) for centralized
control.

t denotes the simulation time and initially t = 0. In caseA, where the initially congested node is node 30, the distribution of the number of packets stored in nodes becomessmoothly distributed over the part of the network before thebottleneck link, and the number of stored packets decreases
with time. In case B, on the other hand, the number of packets stored in the congested node 1 does not decrease withtime, and the distribution of the number of packets does not
become uniform over time.
Next, we investigate the temporal evolution of the number of packets in transit on the links and stored in the nodes
for case A in which the link between nodes 30 and 31 is
the bottleneck link. The simulation conditions are same as
before. The left and right sides of Fig. 8 show the results
for the total number of packets in transit on links and thetotal number of packets stored in nodes in the network, respectively. The horizontal axes denote the simulation time
and the vertical axes denote the number of packets. The total number of packets in transit on links indicates the transmission eﬃciency of the network, and we call this the total throughput. From the quantitative point of view, for thecase where the link capacity of the bottleneck link L30 = 50,
the maximum value of the sustainable total throughput (themaximum number of packets that can be transmitted stably on the links) is about 3000, i.e., 50 packets/link × 59
links. Thus, DFC achieves about 100% of the maximum
value of the total throughput and its value is stable. On theother hand, the right side of Fig. 8 shows that there are many
packets stored in nodes. A large number of packets stored in
nodes is undesirable because it causes an increase in delay
and packet loss.

These phenomena were not observed in the evaluationof the closed network model. We can see from these resultsthat it is necessary to regulate the packet flow carefully, especially in the open network model in which the total number of packets in the network changes with time.
From the results mentioned above, the issues to be considered when applying DFC to an open network model may
be summarized as follows:• The nature of the boundary condition for determining
the packet rate at the ingress node in order to the number of packets to diﬀuse smoothly over the network.
• Traﬃc shaping to prevent excessive traﬃc input fromthe ingress node.
These will be discussed later.
At this point, to demonstrate a feature of DFC as anautonomous decentralized system, we may compare Fig. 8
with results obtained from a centralized flow control model
under the same simulation conditions. For centralized control, we consider the following model. Each node sends its
feedback information Fi (t) to the source node. The source
node calculates the packet transmission rate Ji (α, t) for eachnode from the collected feedback information and sends itback to the corresponding node. Both the collection of Fi (t)and the distribution of Ji (α, t) incur propagation delay. Figure 9 shows the results of the total number of packets in transit on links and the total number of packets stored in nodes,
obtained using from centralized control. The total numberof packets in transit on links is unstable and many packets
are stored in nodes. This comparison indicates that it is inappropriate to apply such a centralized control mechanism

IEICE TRANS. COMMUN., VOL.E88–B, NO.4 APRIL 2005

1564

ri−1 (t) = max(0, min(i (t), J˜i (1, t))),i (t) = min(Li , i+1 (t − di )).

to high-speed networks.
4.

Diﬀusion-Type Flow Control Model Adapted forOpen Networks

4.1 Packet Rate at the Boundary Nodes
In this subsection, we consider the boundary condition of therule for determining the packet rate in DFC, which applies
at the ingress to the network.
Here we consider the situation where nodes in othernetworks and/or end hosts 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 assume that the external nodes only have a traﬃc shaping function which is able to adjust the packet rate to the requested rate notified from the downstream node. That is, anexternal node 0 cannot calculate the packet rate J0 (α, t) using Eq. (2), but can adjust its packet rate to r0 (t − d0 ), which
is notified from node 1.
We consider a rule for determining r0 (t) as a boundary
condition. Node 1 can calculate J0 (α, t) if we assume thenumber of stored packets in the external node is 0. The target rate r0 (t), notified from node 1, is created as J˜0 (α, t) withthe above assumption. That is,
r0 (t) := J˜0 (α, t + d0 ) = α J1 (1, t) − D0 n1 (t).

(8)

This quantity can be calculated from information that isavailable for node 1.

and

(11)
(12)

Note that the calculation of ri−1 (t) uses α = 1, and i (t)means the minimum value of link capacity of all the downstream links. A remarkable feature of Model 1 is that the
maximum values of Ji (α, t) and ri−1 (t) are bounded by i (t).
(2)

Model 2

Node i’s packet transmission rate to the downstream nodei + 1 is determined asJi (α, t) = max(0, min(Li (t), J˜i (α, t))).

(13)

In addition, node i generates feedback information Fi (t) as
Fi (t) = (ri−1 (t), ni (t), i (t)),(14)

and notifies this information to the upstream node i − 1. The
feedback information is expressed as:
ri−1 (t) = Ji (1, t), andi (t) = min(Li , i+1 (t − di )).

(15)
(16)

The diﬀerence between Models 1 and 2 is that the maximum
values of Ji (α, t) and ri−1 (t) are bounded by Li in Model 2,
while they are bounded by i (t) in Model 1.
Both flow control models calculate the transmission
rate J0 (α, t) for packets to flow at the ingress to the network
as follows:
J0 (α, t) = min(0 (t), r0 (t)).

(17)

4.2 Packet Shaping
In this subsection, we consider two extensions to the DFC
model in order to regulate the packet flow at the ingress ofthe network.
In the first model, all nodes regulate the packet flowrate so that it is less than or equal to the minimum value oflink capacity of all the downstream links. In contrast, in thesecond model, only the ingress node uses its minimum value
when calculating the packet flow rate.
(1)

Model 1

When node i receives feedback information from the downstream node i + 1, it determines the transmission rate forpackets to the downstream node i + 1, and adjusts its transmission rate towards the downstream node i + 1. Then, thepacket transmission rate is determined asJi (α, t) = max(0, min(i (t), J˜i (α, t))),(9)where i (t) denotes information about the maximum valueof available capacity. In addition, node i generates feedback
information Fi (t) as
Fi (t) = (ri−1 (t), ni (t), i (t)),(10)

and notifies this information to the upstream node i − 1.
The feedback information is determined as

4.3 Evaluation Using the Extended Flow Control Models
First, we examined the eﬀectiveness of the boundary condition described in Sect. 4.1. We chose the parameter values
as D = 0.1 and α = 1.0. Figure 10 shows the temporal
evolution of the distribution of packets stored in each nodewith respect to DFC with the boundary condition applied.
The network model is case B, where the bottleneck link is
between nodes 1 and 2. This figure shows the packet distribution is diﬀused appropriately even if the ingress node iscongested.
Next, we compared the network performance of the
DFC Models 1 and 2 described in Sect. 4.2. The networkmodel used is case A.
Figures 11 and 12 show the results for the flow control
Models 1 and 2, where the horizontal axes denote the simulation time and the vertical axes denote the total number ofpackets in transit on links or stored in nodes.
We can see from Figs. 11 and 12 that the total numbersof packets in transit on links becomes stable in both models.
However, there is a diﬀerence with regard to the number ofpackets stored in nodes. In Model 1, the total number ofpackets stored in nodes is smaller than in DFC describedin Sect. 3 and, while it becomes stable, it does not decrease
below 3000. In Model 2, on the other hand, the total number

TAKANO and AIDA: DIFFUSION-TYPE AUTONOMOUS DECENTRALIZED FLOW CONTROL FOR END-TO-END FLOW

1565

Fig. 10 Temporal evolution of distribution of packets stored in each node for DFC using the boundary
condition.

Fig. 11 Total numbers of packets in transit on links (left) and stored in nodes (right) for DFC(Model 1).

Fig. 12 Total numbers of packets in transit on links (left) and stored in nodes (right) for DFC(Model 2).

of packets stored in nodes decreases rapidly and falls to zerowith time.
Next, we compared the behavior of the packet distribution among individual nodes, in order to investigate theperformance of Models 1 and 2. Figures 13 and 14 show thesimulation results for Model 1 and Model 2, respectively.
The horizontal axis of each graph denotes the node ID, thevertical axis denotes the number of packets stored in thenode, and t denotes the simulation time (initially t = 0).
We can see from Fig. 13 that in Model 1 the number ofpackets stored in each node becomes smoothly distributed
over the network but a number of stored packets remain in
the network. For Model 2, on the other hand, the number ofpackets stored in nodes becomes smoothly distributed overthe network and decreases with time.
This diﬀerence arises because in Model 1 all nodes
calculate the packet transmission rates using the minimum
value of link capacity of all the downstream links. This restriction, which is imposed on calculating the rate in Model
1, is too severe. So, the transmission rates calculated inModel 1 diﬀer greatly from the ideal rates, which are determined by Eq. (2) and govern the diﬀusion phenomenon. Our
results also show that the rule for determining the packet rate

at a node, which is the most important feature of our flow
control, is crucially important for the stability and adaptability of the whole network performance.
5.

Conclusions

In this paper, we have identified the key issues associatedwith the application of DFC to an open network model,
and demonstrated a solution. The first issue relates to theboundary condition for determining the packet rate. By introducing an assumption that an external node has no stored
packets, we can have an appropriate boundary condition thatenables smooth diﬀusion of packet distribution even if theingress node is congested. The second issue is the shaping
mechanism required to control the number of packets in the
network appropriately. We have studied two diﬀerent shaping mechanisms, Models 1 and 2, and compared them. Our
results show that the shaping mechanism of Model 2 not
only provides about 100% link utilization but also results inonly a small number of packets stored in nodes.
The two issues for applying DFC to the open networkmodel have been solved by introducing two mechanisms:
the boundary condition (described in Sect. 4.1) and packet

IEICE TRANS. COMMUN., VOL.E88–B, NO.4 APRIL 2005

1566

Fig. 13

Temporal evolution of distribution of packets stored in each node (Model 1).

Fig. 14

Temporal evolution of distribution of packets stored in each node (Model 2).

Fig. 15 Classification of various control mechanisms with respect totheir eﬀective timescales, with and without packet shaping.

shaping (described in Sect. 4.2). Finally, we have restructured the relationships between the proposed two mechanisms and the previous DFC (described in Sect. 3).
Various controls in the network can be classified fromthe point of view of their particular time-scale of control operation. Figure 15 shows a comparison of diﬀerent typesof control according to such a classification. For example, routing and call admission control fall into the long andmedium time scales, respectively. Individual control mechanisms work well for their appropriate time-scales and they
cooperate with each other. Window flow control such as
TCP acts in the time scale of the round-trip delay. In highspeed networks, since a lot of packets are being transmitted
on links, control delay greatly aﬀects the performance. Our
target is a time-scale shorter than the RTT. The left and righthand sides of Fig. 15 show appropriate classification, withand without packet shaping, respectively. Determination of
the packet rate at the boundary node, based only on the information available for the node, can be applied to decisionmaking in a time-scale as short as that achieved by DFC.
Moreover, this application of this rule is essential in achieving appropriate diﬀusion of packet density. Therefore, theboundary condition for determining the packet rate should
be included in the framework of DFC.

The packet shaping mechanism requires knowledge ofthe minimum link bandwidth, 0 (t), along a flow. Since thisrequires global information about the network, it does not sit
comfortably in the framework of DFC, which is based only
on local network information. Consequently, the packet
shaping mechanism should be classified into a higher layer.
If other control mechanisms (e.g. TCP) are applied and they
regulate the number of packets in the network appropriately,
applying packet shaping is not mandatory and we expect the
combination of DFC and other control mechanisms also towork well.
This paper has not addressed the use of TCP flow control for the end-to-end flow, and we should verify the compatibility and complementarity of DFC with TCP or otherhigher-layer protocols. In addition, another residual issue
for applying DFC to real networks is its applicability to multiple flows. This paper has focused on issues resulting froma single flow, but we should take the existence of other traffic into consideration. Combining fair queueing mechanismwith DFC might be a promising approach to solve this issue.
The issues are areas for further study in extending theapplication of DFC.
References[1] 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.
[2] 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.
[3] 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.
[4] K. Horikawa, M. Aida, and T. Sugawara, “Traﬃc control scheme
under the communication delay of high-speed networks,” Proc.

TAKANO and AIDA: DIFFUSION-TYPE AUTONOMOUS DECENTRALIZED FLOW CONTROL FOR END-TO-END FLOW

1567

Int. Conf. on Multi-Agent Systems (ICMAS’96), pp.111–117, Dec.
1996.
[5] 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.
[6] 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.
[7] 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.
[8] S. Kunniyur and R. Srikant, “A decentralized adaptive ECN marking
algorithm,” Proc. IEEE GLOBECOM’00, pp.1719–1723, 2000.
[9] 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.
[10] 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.
[11] C. Takano and M. Aida, and S. Kuribayashi, “Autonomous decentralized flow control in high-speed networks with inhomogeneousconfigurations,” IEICE Trans. Commun., vol.E87-B, no.6, pp.1551–
1560, June 2004.
[12] M. Aida and C. Takano, “Principle of autonomous decentralized
flow control and layered structure of network control with respect
to time scales,” Supplement of the ISADS 2003 Conference Fast
Abstracts, pp.3–4, Pisa, Italy, April, 2003.
[13] M. Aida and C. Takano, “Principle of diﬀusion-type autonomous
decentralized flow control,” Proc. Commun. Conf. IEICE 2003, B7-13, 2003.

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

Masaki Aida
received his B.Sc. and M.Sc.
in Theoretical Physics from St. Paul’s University, Tokyo, Japan, in 1987 and 1989 respectively, and received the Ph.D. in Telecommunications Engineering from 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 computer communication networks. From 1998 to 2001, he
was a manager at the Traﬃc Research Center,
NTT Advanced Technology Corporation (NTTAT). Since April 2005, he has been an Associate Professor at the Facultyof System Design, Tokyo Metropolitan University. His current interests include traﬃc issues in communication systems. Dr. Aida received the IEICE
Young Investigators Award in 1996. He is a member of the IEEE and the
Operations Research Society of Japan.