Autonomous Decentralized Flow Control Allowing
Control Timing Independent of Link Length
Chisa Takano† and Masaki Aida‡† Graduate School of Information Sciences, Hiroshima City University,

3-4-1 Ozuka-Higashi, Asa-Minami-Ku, Hiroshima, 731-3194 Japan
TEL: +81 82-830-1673
takano@hiroshima-cu.ac.jp‡ Graduate School of System Design, Tokyo Metropolitan University,

6-6 Asahigaoka, Hino-shi, Tokyo 191-0065 Japan
TEL: +81 42-585-8627
maida@sd.tmu.ac.jp

Abstract
We have proposed diffusion flow control (DFC) as a technique for controlling a network, using an analogy of the diffusion phenomenon. In DFC, although each node in a network handles its local traffic flow only on the basis of theinformation it is aware of, the diffusion effect of DFC distributes the packet density in a network, so avoiding packet
loss. In our previous work, we have assumed that each node
knows the lengths of the links adjacent to it and we used
control timing depending on the link length. In this paper,
we describe an extension of the DFC in which the control
timing is independent of the link length so allowing DFC to
be used in a mobile ad hoc network.
Keywords autonomous decentralized control, diffusion
equation, traffic control, wireless network

1 Introduction
We have previously proposed the use of autonomous decentralized technology, in which each sub-system in a network operates autonomously on the basis of only the information directly available to it, as a technique which canlead to optimal performance for the whole network. The
technical reasons why such a technology is necessary are as
follows.
Autonomous decentralized control is suitable for highspeed networks
In high-speed networks, since at any instant a large
number of packets are in transit on links, any delay
in applying control greatly affects the network performance. To address this problem, it is necessary to

use time-sensitive control which operates on the basisof only partial information, without waiting to collectinformation from the whole network.
Autonomous decentralized control can operate under anenvironment where the information exchange is limited
Examples of autonomous decentralized networks aremobile ad hoc networks and P2P networks, where
it is difficult to collect information about the wholenetwork because of architectural issues. In such anenvironment, a control mechanism based on only
partial information is needed in order to be able to act
efficiently and effectively.
To solve the technical problem concerning high-speed
networks, we have proposed the use of diffusion type flow
control (DFC) [1], in which each node in a network acts autonomously on the basis only of local information but the
cumulative effect of the local decision-making at each nodeleads to high performance of the network as a whole. In
addition, we have investigated aspects of network performance of DFC for high-speed networks [2, 3, 4, 5]. DFC isa flow control which determines the transmission rate based
only on information it is aware of. DFC allows packet loss
due to buffer overflow to be avoided by ensuring that thedensity of packets stored in each node is not unevenly distributed in certain nodes, but is rapidly diffused over thewhole network. The diffusion effect associated with DFC
leads to steady data transmission in even high-speed networks. Moreover, the cost of the network can be reduced
because the capacity of the storage buffers in the nodes canbe reduced.
In this paper, we consider the solution of the technical issue in the mobile ad hoc network, where the link lengths areFigure 1. Application of the DFC to the wireless ad hock network

Figure 2. Example of thermal diffusion phenomena.
not known, so as to establish how autonomous decentralized control under the environment where the informationexchange is even more limited than the cases considered
before.
A mobile ad hoc network is an autonomous decentralized
network and is composed of wireless systems having a relay
function. For ad hoc network technology, many techniques
have been introduced concerning, especially, the control ofroute selection [7, 8]. Routing algorithms that take accountof security, low power consumption, and Quality of Service(QoS) have been proposed in [9, 10]. In addition to routing
algorithms, scheduling algorithms aimed at improving theefficiency of networks offering controlled QoS have been
described [11, 12].
In this paper, we apply the framework of DFC, which has
been proposed for the solution of the high-speed network
issues, to mobile ad hoc networks, and investigate the realizability of DFC in networks where information exchange isfundamentally and structurally limited. In the DFC implementations described in the past, each node had to know thevalue of the propagation delay of the links to the adjacentnodes. However, in a mobile ad hoc network it is difficult
to know the propagation delay in real time because the distance to the other hosts is continually changing. Therefore,
a control technique that requires knowledge of the link delay to adjacent hosts is not useful (Fig. 1). In this paper, we
extend DFC so that it can be applied even to a wireless environment and establish a control method that doesn’t dependon the link length.
The remainder of this paper is organized as follows.
Sec. 2 describes the basic operation of the previously described type of DFC in wired networks. In Sec. 3 we propose a new type of DFC in which the control timing interval,that is the time interval at which flow control is applied, is
independent of the link length. Conditions for simulating
this new technique are described in Sec. 4 and the simulation results are given in Sec. 5. Finally, conclusions are
made in Sec. 6.

Figure 3. Node interactions in our flow control
model.

2 Diffusion-Type Flow Control Mechanism
In this section, we describe the framework of DFC asapplied to high-speed wired networks.

2.1 Aim of Diffusion-Type Flow Control Mechanism
The most remarkable characteristic of DFC is that it provides a framework in which the implementation of local
decision-making at each node leads to high and stable performance for the whole network. To explain the basis of
this mechanism, we show the principle of this flow control
model through the following analogy [3].
When we heat a point on a cold iron bar, the temperature
distribution follows a normal distribution and heat spreads
through the whole bar by diffusion (Fig. 2). In this process,the action in a minute segment of the iron bar is very simple:
heat flows from the hotter side towards the cooler side. The
rate of heat flow is proportional to the temperature gradient.
Although each segment acts autonomously, based on its local information, the temperature distribution of the wholeiron bar exhibits orderly behavior. In DFC in a network,
each node controls its local packet flow to an adjacent node,so that it is proportional to the difference between the number of packets in that node and the number in the adjacentnode. The overall effect is that the distribution of the total number of packets in each node in the network becomes
uniform over time.

2.2 Behavior of Diffusion-Type Flow Control
Mechanism
Figure 3 shows the interactions between nodes (routers)in DFC, using a network model with a simple 1-dimensional
configuration. In DFC, node i (i = 1, 2, . . . ) transfers

packets to node i + 1, and node i + 1 sends feedback information Fi+1 to node i. When node i receives feedback
information from downstream node i + 1, it determines
the transmission rate for packets to the downstream nodei + 1 using the received feedback information, and it adjusts
its transmission rate towards the downstream node i + 1.
Let us assume that there are Mi flows sharing the link between node i and node i + 1, and they are identified byj (j = 1, 2, . . . , Mi ). Each node i autonomously determines the transmission rate Jij for flow j on the basis of the
feedback information obtained from the downstream nodei + 1 and its own information. The transmission of packets
and feedback information both experience the same propagation delay.
The transmission rate Jij (t) for flow j of node i at time t
is determined by

Figure 4. Correspondence between discreteand continuous network models.

Jij (t) = max(0, min(Lji (t), J˜ij (t))),J˜j (t) = rj (t − di ) − Di (nj (t − di ) − nj (t)),

Parameter Di is chosen to be inversely proportional tothe propagation delay as follows:

i

i

i+1

i

(1)
(2)

where Lji (t) denotes the available bandwidth for flow j of
the link from node i to node i + 1 at time t, nji (t) denotes
the number of packets belonging to flow j in node i at timet, rij (t − di ) is the required rate for flow j derived fromthe feedback information from the downstream node i +1 (hereafter called the “notified rate”), and di denotes the
propagation delay between nodes i and i + 1. Di is theparameter used by DFC.
Let the bandwidth of the link from node i to node i+1 be
Bi , and Lji (t), the available bandwidth for flow j , is derived
by assuming that the bandwidth Bi is shared by the different
flows according to a weight J˜ij (t) [4], that is,Lji (t) = Bi × PMi

J˜ij (t)˜k
k=1 1{k=active} × Ji (t),(3)

where 1{k=active} is the indicator function which is equal to
1 if flow k is active at time t, and otherwise is equal to 0.
The feedback information for flow j created at fixed intervals τi by node i consists of three quantities, as follows:jFji (t) = (ri−1(t), nji (t), `ji (t)).

(4)

For DFC applied to a wired network, we assumed thatthe control timing interval is equal to the propagation delay(τi = di−1 ). `ji (t) is the information defining the maximumj(t) areavailable bandwidth. `ji (t) and the notified rate ri−1jlimited by the available bandwidth Li as follows.
`ji (t) = min(Lji (t), `ji+1 (t)),jri−1(t) = max(0, min(Lji (t)), J˜ij (t)).

(5)
(6)

Di =

D
,
di

(7)

where D (> 0), which is a positive constant, is the diffusion
coefficient. As shown in [2], setting parameter Di in accordance with Eq.(7) allows the complexity of the networkmodel to be absorbed, and provides high performance andstability even if the configuration of the network becomescomplex.

3 Extension of DFC to allow the control timing to be independent of the link propagation delay
Although we assumed di = τi+1 in the previous section,
the two parameters have different origins, and so we can regard them as different (independent) items. In this section,
we show that, for more general applicability, parameter Di
should be determined by using the control timing inverval
τi (not the propagation delay di) as follows.
Di =

D
τi+1

(8)

Here, the interval of DFC’s actions ∆t (= τi ) is unchanged. ∆t is independent of di . To introduce a single
discrete space reflecting an entire 1-dimensional network
structure, we divide the continuous 1-dimensional space
into lengths of ∆x which are also independent of di .
Next, we consider the continuous values, J˜j (x, t),jr (x, t) and nj (x, t) as continuous approximations ofJ˜ij (t), rij (t) and nji (t) in order to confirm the relationshipbetween the discrete space and the continuous space. If

Figure 5. Simulation Model.
jn (x, t) is the packet density at time t in discrete space x,
we obtain the following relation:nji (t) = nj (x, t) ∆x + o(∆x).

To appropriately associate the number of packets nji (t)in a discrete space with the packet density nj (x, t) in a continuous space, Eq.(2) needs to be modified for the continuous case, and may be approximated by the following equation .
j@n (x, t)J˜j (x, t) = rj (x, t) − ∑
,
@x

(9)

where ∑ is a diffusion coefficient in the physical diffusion
phenomenon (in the continuous space).
The relationship between the discrete space and the continuous space is shown in Fig. 4. First, we take the limit ofthe distance between the adjacent nodes as di → 0. The second panel in Fig. 4 shows this situation. Here, the intervalof DFC’s actions, ∆t is unchanged. Next, taking the limitof ∆x to be 0, we obtain a continuous approximation of
the 1-dimensional network. Note that ∆t should approach
0 concurrently with ∆x → 0. The relationship between thepacket density n(x, t) and the number of packets stored ina node ni (t) is also shown in Fig. 4.
After taking the limit as di → 0, we compare the second
term on the right hand side of (2) with that of (9) and get
the following relation.
∑@nj (x, t)nj (x + ∆x, t) − nj (x, t)= ∑ lim∆x→0@x∆x
nji+1 (t) − nji (t)= ∑ lim
∆x→0
(∆x)2
j

This denotes that parameter Di is set in inverse proportion
to the propagation delay.
The object of this paper is the determination of parameter Di independent of link length. We have discussed previously how the network performance is improved comparedwith other methods in [1, 2, 3, 4].

5 Simulation Resultsj∆t ni+1 (t) − ni (t)= ∑ lim.
∆x→0 (∆x)2∆t

Figure 5 shows the network model used in the simulation, with 30 mobile hosts. Although this 1-dimensionalmodel looks simple, it represents a part of a network anddescribes a path of the target end-to-end flow extracted
from the whole network. Each packet has a fixed lengthof 1, 500 Bytes and the link bandwidth is 4, 400 packets/s
which corresponds to a link bandwidth of 54 Mbps.
The simulations described here assume a non-uniform
network configuration, that is, the lengths of the links aredifferent. In this model, the propagation delay di is specified by a probability distribution with the mean d = 0.5µsec, which corresponds to a mean link length of about 100
m. The propagation delay of each link is determined in advance. The delay consists of a fixed component of 0.25
µsec and a variable component that obeys an exponential
distribution with a mean of 0.25 µsec. D is equal to 0.4.
The simulation scenario is as follows. There are two UDP
flows (the target and background flows). The target flow is
between host 1 and host 30, while the background flow is
between host 15 and host 30. The target flow and the background flow start at simulation time t = 0 sec and t = 1 sec,
respectively. Both flows have greedy traffic, that is, the rateof each flow is as large as possible. For each simulation,
the values of the control timing interval of all hosts are thesame (5, 10, 50, 100, 500 or 1,000 msec). Parameter Di is
set by Eq.(8) or the following scheme for the performancecomparison.
µ
∂
D
d
Di =
×
(11)
di
τi+1

(10)

We have Eq. (8) by the relation D = ∑∆t/(∆x)2 whichis already known from [5].

4 Simulation
By means of simulation, we show that setting the parameter Di in accordance with Eq. (8) leads to the diffusion
effect of DFC, even if information about the propagation
delay is unknown. For the performance comparison, we set
the value of the parameter Di in inverse proportion to the
propagation delay. Simulations were made by using ns2
simulator.

We investigate the effectiveness of setting Di as described in Eq. (8). Figure 6 shows the results for the behavior of the packet distribution among individual hosts for
DFC when Di is set as in Eq. (8). The different rows in
Fig. 6 show the results for DFC having a control timing interval τ = 5, 10, 50, 100, 500 and 1, 000 msec, respectively,
while the different panels refer to different times after thestart of the simulation. The horizontal axis of each graphdenotes the host ID, the vertical axis denotes the numberof packets stored in the host, and simulation time (sec) isshown in each graph. It can be seen that once the background traffic starts entering the simulation network (after
1 s), DFC control at each host in the network prevents thenumber of stored packets building up at a certain host. We

Figure 6. Temporal evolution of distribution of packets stored in each host. (Di is inversely proportional to τ )Figure 9. Temporal evolution of the total number of packets that are stored in hosts. (Di isinversely proportional to di )Figure 7. Temporal evolution of the total number of packets that are stored in hosts, for different values of control timing interval. (Di isinversely proportional to τ )can see from Fig. 6 that as the control timing interval increases, the number of packets (the value of the verticalaxis) stored in the hosts increases, because the effectiveness of DFC works more slowly through the whole network.
In all the results, regardless of the control timing interval,
the packets do not become concentrated at the potentiallycongested host 15 and the number of packets stored in thehosts becomes smoothly distributed over the network anddecreases with time.
Panels in Fig. 7 show the temporal evolution of the total number of packets stored in hosts, when the values of
the control timing interval τ are equal to 5, 10, 50, 100, 500
and 1000 msec, respectively. The horizontal axis denotes

the simulation time (sec) and the vertical axis denotes thetotal number of packets that are stored in hosts, and thecontrol timing interval is shown on each graph. These results also show that after the total number of total packets
initially grows once congestion starts at t = 1 sec, the total number of packets then decreases almost linearly withtime and approaches 0 as a result of the diffusion effect of
DFC. Moreover, the maximum value of the total number ofpackets stored in hosts increases in proportion to the control
timing interval τ and the elapsed time until the total numberof packets returns to 0 is larger in proportion to the control
timing interval.
Next, Figs. 8 and 9 show the results when Di is set to
be inversely proportional to the propagation delay. Eachpanel in Fig. 8 shows the distribution of the number of packets stored in the host in case of the control timing intervalτ = 5, 50 or 500 msec. In this case, the distribution of
the packets is not smoothly diffused, as can be seen whencompared with the results (Fig. 6) for the case that Di wasFigure 8. Temporal evolution of distribution of packets stored in each host. (Di is inversely proportional to di )inversely proportional to τ . Figure 9 shows the temporal
evolution of the total number of packets stored. Comparedwith Fig. 7, the time interval until the total number of packets converges to 0 is very large. This means that cooperative
action between hosts doesn’t perform well in this case andthe diffusion effect of DFC is not realized.

6 Concluding Remarks
In this paper, our target is the application of DFC to amobile ad hoc network, and the extension of DFC to situations where the control timing is independent of link length.
Our results have showed that the diffusion effect of DFC isachieved when the parameter Di is inversely proportional
to the control timing interval even if the propagation delay
is unknown. Future work will include verifying the performance of DFC by using a network model whee the distance
between each host changes dynamically.

Acknowledgement
This research was partially supported by the National
Institute of Information and Communications Technology(NiCT) and the Grant-in-Aid for Scientific Research (S)No. 18100001 (2006–2010) from the Japan Society for the
Promotion of Science.

References[1] C. Takano and M. Aida, “Stability and adaptability of
autonomous decentralized flow control in high-speed
networks,” IEICE Transactions on Communications,
vol.E86-B, no.10, pp.2882–2890, 2003.
[2] C. Takano, M. Aida, and S. Kuribayashi, “Autonomous decentralized flow control in high-speed
networks with inhomogeneous configurations,” IEICE
Transactions on Communications, vol.E87-B, no.6,
pp.1551–1560, 2004.

[3] C. Takano and M. Aida, “Diffusion-type autonomous
decentralized flow control for end-to-end flow in highspeed networks,” IEICE Transactions on Communications, vol.E88-B, no.4, pp.1559-1567, 2005.
[4] C. Takano and M. Aida, “Diffusion-type autonomous
decentralized flow control for multiple flows, IEICE
Transactions on Communications, vol. E90-B, no. 1,
pp. 21-30, January 2007.
[5] C. Takano, K. Sugiyama and M. Aida, “Parameter Design for Diffusion-Type Autonomous Decentralized
Flow Control, IEICE Transactions on Communications, vol. E91-B, no. 9, pp. 2828-2837, September
2008.
[6] E. Royer and C.-K. Toh, “A review of current routing
protocols for ad hoc wireless networks, IEEE Personal Communications, pp. 46-55, April 1999.
[7] E. Perkins, M. Belding-Royer and R. Das, “Ad hoc ondemand distance vector (AODV) routing, Request forComments 3561, July 2003.
[8] T. Clausen and P. Jacquet, “Optimized link state routing protocol (OLSR), Request for Comments 3626,
October 2003.
[9] Y. Hu, A. Perrig, and B. Johnson, “Ariadne: A Secure
on-demand routing protocol for ad hoc networks, inProceedings of ACM MobiCom 2002, Sept. 2002.
[10] Y. Xu, J. Heidemann and D. Estrin, “Geographyinformed energy conservation for ad hoc routing,in Proceedings of ACM Mobile Computing and Networking 2001, July 2001.
[11] X. Lin and N. B. Shro , “Joint rate control and scheduling in multihop wireless networks, in Proceedings ofIEEE Conference on Decision and Control, Bahamas,
2004.
[12] L. Bui, A. Eryilmaz and R. Srikant, “Joint
Asynchronous Congestion Control and Distributed
Scheduling for Multi-Hop Wireless Networks, in Proceedings of IEEE INFOCOM 2006, Apr. 2006.