2009 International Conference on Intelligent Networking and Collaborative Systems

A Study of Improving Fairness among Flowsin Ad hoc Networks
Chisa Takano

Kenji Ishida

Masaki Aida

Graduate School of Information Sciences, Graduate School of Information Sciences, Graduate School of System Design,
Hiroshima City University,
Hiroshima City University,
Tokyo Metropolitan University,
3-4-1 Ozuka-Higashi, Asa-Minami-Ku,
3-4-1 Ozuka-Higashi, Asa-Minami-Ku,
6-6 Asahigaoka, Hino-shi,
Hiroshima, 731-3194 Japan
Hiroshima, 731-3194 JapanTokyo 191-0065 Japan
Email: takano@hiroshima-cu.ac.jp
Email: ishida@hiroshima-cu.ac.jp
Email: maida@sd.tmu.ac.jp

Abstract—By development and the spread of a wireless technology, the mobile ad hoc network (Manet) that can be easily
constructed only with mobile nodes is getting much attention.
However, it is difficult to control the performance of the entire network appropriately, as a network consists of individual
communication nodes operating autonomously and there is nodevice that controls the entire network. Recently, a large amountof research have investigated the performance of TCP in Manet,and noted the problem of leading to a larger degree of unfairness.
We have proposed diffusion-type flow control (DFC) as a solution
for the extremely time-sensitive flow control required for highspeed “wired” networks. In this paper, we apply the approachof DFC to Manet, in which the exchange of information acrossthe entire network is limited, and show a wireless traffic control
scheme improving the fairness among TCP flows.

I. I NTRODUCTION
While TCP is a de facto standard protocol of the Internet that guarantees reliable delivery of data packets in
wired network, TCP is demanded in mobile ad hoc networks (Manets)[1], [2], recently. Manet can construct a selfconfiguring network of mobile systems connected by wirelesslinks without any communication infrastructure, and can offer
a flexible communication environment that is robust against
disasters and changes in event sites. However, there is no one
specific device responsible for managing Manet. In Manet, information exchange is fundamentally and structurally limited,and each node needs to execute traffic control, path control,and network resource management on the basis only of local
information.
Many techniques for Manet have been introduced, particularly with regard to the control of route selection [3],[4]. Routing algorithms that take account of security, power
consumption, and Quality of Service (QoS) have been proposed [5], [6]. In addition to routing algorithms, schedulingalgorithms aimed at improving the efficiency of networks
offering controlled QoS have been described [7], [8].
Wireless networks, however, face not only the problem ofrouting but also the presence of flow control; Many studies
have noted that Manet performance is severely degraded when
TCP is used [9], [10], [11], [12], [13]. TCP performs congestion control on an end-to-end basis and so its response topacket loss is rather slow. To compensate this response delay, it
978-0-7695-3858-7/09 $26.00 © 2009 IEEE
DOI 10.1109/INCOS.2009.19

341

dramatically cuts the throughput. In addition, significant TCP
unfairness has been reported when TCP is used on Manet.
The proposed control mechanism overcomes this weakness of
TCP.
Existing autonomous distributed control schemes focus on
optimizing network efficiency, i.e. optimum traffic control
management and network resource utilization (battery lifeetc.), only in limited regions and fail to address the entire network. We have proposed the use of diffusion-type flow control(DFC) to solve similar problems in high-speed fixed networks[14], [15], [16], in which each node acts autonomously on
the basis of just local information; the cumulative effect of
the local decisions made at each node leads to high performance of the network as a whole. In addition, we haveinvestigated the impact of DFC on the performance of highspeed networks. DFC uses only the information it is aware
to determine the transmission rate. DFC avoids packet loss
due to buffer overflow by ensuring that the density of packets
stored in each node is not unevenly distributed to certain
nodes, but is adequately diffused over the whole network.
The diffusion effect associated with DFC leads to steady datatransmission even in high-speed networks. Moreover, the costof the network can be reduced because the capacity of thestorage buffers in the nodes can be reduced.
This paper applies the framework of DFC to Manet, andinvestigates the feasibility of this in environments where information exchange is fundamentally and structurally limited. In
the DFC implementations described in the past, each node had
to know the propagation delay on the links to adjacent nodes.
However, in Manet it is difficult to know the propagation
delay in real time because the distance to the other hosts is
continually changing. Therefore, it is impractical to demand
knowledge of the link delay to adjacent hosts. In this paper, we
extend DFC so that it can be applied in a wireless environment
and introduce a control method that doesn’t depend on link
length. Then, we show that a combination of DFC and TCP
achieves higher network performance than TCP in Manet.
The remainder of this paper is organized as follows. Sec. II
describes the framework of DFC and the basic operation of
DFC for wired networks, and then proposes a DFC variant inwhich the control timing interval, that is the time interval at

Fig. 2.

Fig. 3.

Fig. 1.

Action at a distance and action through a medium.

which flow control is applied, is independent of the link length.
Conditions for simulating this new technique and simulation
results are described in Sec. III. Finally, Conclusions are drawn
in Sec. IV.
II. D IFFUSION -T YPE F LOW C ONTROL M ECHANISM
In this section, we describe the framework of DFC asapplied to high-speed wired networks.
A. DFC applying Action Through Medium
When thinking about the interaction between two objects
which are separated in space, there are two theories dependingon the action method; “action at a distance” and “action
through a medium”(Fig. 1). “Action at a distance” is the directinteraction of two objects that are not linked by any field or
medium. For example, Newton’s law of universal gravitationis on the basis of “action at a distance”, and the force Fof gravity acting between object A and object B is directly
proportional to the mass m1 and m2 of both interacting
objects, and inversely proportional to the square of the distancer between object A and B as follows:
m1 m2
F =G 2 ,r
where G is the gravitational constant. The function F isdecided by the mass of objects and the distance, that is to
say that it is necessary to know the values of the mass andthe distance. From the point of view of a network control, thisis same as the framework of the centralized control to require
the collection of global information about the network state.
In the case of “action through a medium”, on the other hand,variation of the physical value at a point of space is transmitted
to the adjacent point via the medium of the gravitational

342

Example of thermal diffusion.

Node interaction in our flow control model.

field at the limited speed.
A temporal variation in such agravitational field can be described as a partial differential
equation.
We use the following example to elucidate “action througha medium”. When we heat one end of an iron bar, thetemperature distribution follows a normal distribution and heatspreads through the whole bar by diffusion (Fig. 2). In thisprocess, the action in a minute segment of the iron bar is very
simple: heat flows from the hotter side towards the coolerside. 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, 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 numberin the adjacent node. The overall effect is that the distributionof the total number of packets in each node in the network
becomes uniform over time.
B. 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 fromdownstream node i + 1, it determines the transmission rate
for packets to the downstream node i + 1 using the received
feedback information, and it adjusts its transmission rate
towards the downstream node i+1 accordingly. Let us assume
that there are Mi flows sharing the link between node i andnode i + 1, and they are identified by j (j = 1, 2, . . . , Mi ).
Each node i autonomously determines the transmission rate Jijfor flow j on the basis of the feedback information obtained
from the downstream node i + 1 and its own information.
The transmission of packets and feedback information bothexperience the same propagation delay.
The transmission rate Jij (t) for flow j of node i at time t
is determined by
Jij (t) = max(0, min(Lji (t), J˜ij (t))),J˜j (t) = rj (t − di ) − Di (nj (t − di ) − nj (t)),
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 attime t, rij (t − di ) is the required rate for flow j derived
from the feedback information from the downstream nodei + 1 (hereafter called the “notified rate”), and di denotes the
propagation delay between nodes i and i+1. Di is a parameterused 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 weight Wij (t), that is,
Kij (t) = MiBi

k=1 1{k=active}

Wij (t) = Mi− Di (nji+1 (t − di ) − nji (t)),(3)

Kij (t)k
k=1 1{k=active} × Ki (t)Lji (t) = Wij (t) × Bi ,

,

(5)

(6)

When implementing DFC in a wired network, we assume
that the control timing interval is equal to the propagation
delay (τi = di−1 ). ji (t) is the information defining the
maximum available bandwidth. ji (t) and the notified ratejri−1(t) are limited by the available bandwidth Lji as follows.
ji (t) = min(Lji (t), ji+1 (t)),jri−1(t) = max(0, min(Lji (t)), J˜ij (t)).

(7)
(8)

C. Parameter design independent of the link propagationdelay
In some previous works, parameter Di was chosen to be
inversely proportional to the propagation delay as follows:
Di =

D
,
di

Simulation model.

(4)where 1{k=active} is the indicator function; it is equal to 1 ifflow k is active at time t, otherwise 0. This rule means thata flow with the larger second term of (2) can get a larger
transmission rate and can transmit a larger volume of traffic
to the downstream node.
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)).

Fig. 4.

(9)where D (> 0), which is a positive constant, is the diffusion
coefficient. As shown in [16], setting parameter Di in accordance with Eq.(9) allows the complexity of the network model
to be handled, and provides high performance and stability
even if the configuration of the network becomes complex.
Although we assumed di = τi+1 in the previous subsection,
the two parameters have different origins, and so we can regard
them as different (independent) items. Therefore, we show
that, for more general applicability, parameter Di should bedetermined by using the control timing interval τi (not the
propagation delay di) in accordance with [17] as follows.
Di =

D
τi+1

(10)

where the interval of DFC’s actions τi is unchanged and τi isindependent of di .
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,which is achieved by the following equation .
j∂n (x, t)J˜j (x, t) = rj (x, t) − κ
,
(11)
∂x
where κ is the diffusion coefficient of the physical diffusion
phenomenon (in the continuous space). We have Eq. (10) by
the relation D = κΔt/(Δx)2 which is already known from[16]. It is obvious from a consideration of the relationshipbetween κ and D. To guarantee the diffusion effect for any
conditions, it is necessary to adopt the value of D in the range
as follows[16]:10<D< .
(12)
2
III. S IMULATIONSIn this section, we apply the DFC approach to a Manetin which the hosts are moving, and show that overall Manet
performance can be optimized even though each node is operating autonomously and processing only local information. We
extend the simulation tool ns2 capability with the function of
DFC to investigate the performance of DFC when coexistingwith TCP.
A. Simulation Model
Figure 4 shows the network model used in the simulations,which includes 50 mobile hosts. Black circles denotes thesource and destination nodes in Manet, and black lines show

343

Fig. 6.

Fig. 5.

Throughput in the case of TCP without DFC.

Route of Flows.

the wireless links between nodes. The size of the area is about
1.2 km × 0.9 km, and each node is arranged at random as an
initial state. The migration speed of each host is 10 km/hour
and the migration angle is a random value between 0 and
2π . D is equal to 0.4. Each packet has a fixed length of
1, 500 Bytes and the link bandwidth is 4, 400 packets/s whichcorresponds to a link bandwidth of 54 Mbps.
The simulations described here assume a non-uniform network configuration, that is, links have different lengths. The
propagation delay of each link is determined by dividing link
length by the speed of light.
The basic simulation scenario is as follows. There are ten
flows; The first flow starts at simulation time t = 0 sec and theothers are added to Manet every five seconds. The simulation
end time is 50 sec. All flows are greedy, that is, the rate of eachflow is as large as possible. The maximum buffer capacity foreach flow at each host is 1,000 packets.
In DFC, all hosts use the same the control timing interval
50 msec. Parameter Di is set by Eq.(10). The maximum TCP
window size and the initial TCP window size of both flows are
10,000; this value was chosen as it is sufficiently larger thanthe bandwidth-delay product of RTT. The TCP implementation
used in the model is TCP Reno.
B. Evaluation of the fairness among flows
We investigate the characteristics of throughput for eachflow when (a) TCP flow control without DFC and (b) TCP
with DFC is used in Manet. In this paper, we use the shortest
hop algorithm which the route construction schemes of theexisting routing algorithms usually use in Manet. The route of
ten flow is shown in Fig. 5, and the maximum number of theflow in one link is three.
First, the result when only the TCP is used in Manet isshown in Fig. 6. The horizontal axes denote the simulation
time and the vertical axes denote the throughput (Mbit/sec)
for each flow. The ten lines in this figure denote the results forthe ten flows. Throughput is calculated as the amount (Mbit)

344

Fig. 7.

Throughput of flow 2, 3 and 4 (TCP without DFC).

of the packet that the destination node received per second.
The calculation granularity is assumed to be 0.1 sec.
In Fig. 6, the throughput of TCP without DFC is unstablefor each flow, and some flows have high throughput, but theothers do not. Figure 7 shows the results of flow 2 (blue), 3(red), and 4 (orange) extracted from Fig. 6. These flows sharesome link at simulation time 15 sec. Because three flows sharethe link having the link bandwidth of 54 Mbps, the bandwidth
which one flow can use becomes 18 Mbps if these flows are
fair. But we see from Fig.7 that the throughput of flow 4 ishigher than flow 2 and 3, while the throughput of flow 2 andflow 3 falls to zero. This is because the new traffic entering
Manet leads to packet losses of flow 2 and 3 and TCP reduces
its window size for flow 2 and 3. Such unfairness is caused
because flow 4 can use the remaining bandwidth that flow 2
and 3 do not use.
Figures 8 and 9 show the results obtained from TCP with
DFC. Simulation condition is same as Fig. 6 and Fig.7. We
can see from these figures that the throughput of each flow is
steady and the value of throughput for each flow reaches theideal value 18 Mbps. Because the number of packets stored at
nodes becomes uniform over the network through the diffusion
effect of DFC and packet losses can occur not, the throughput
of each flow are fair.
Next, we change the value of the link cost by way of

Fig. 8.

Throughput in the case of TCP with DFC.

Fig. 10.

Fig. 9.

Route of Flows. (random link cost)

Throughput of flow 2, 3 and 4 (TCP with DFC).

experiment, and we consider the situation in which more flows
share the link. The link cost is set to uniform random number
between (8,12). The route of flows is calculated by using theshortest hop algorithm. Under this condition, the maximum
number of the flow shared in one link is four (Fig. 10).
The result when only the TCP is used in Manet is shown in
Fig. 11. The horizontal axes denote the simulation time and thevertical axes denote the throughput (Mbit/sec) for each flow.
In Fig. 11, the throughput of TCP without DFC is unstable foreach flow, the same as Fig. 6. Here, we focus on four flows(flow 3, 6, 9 and 10) as shown in Fig. 11, where the value thevertical axes is between 45 sec and 50 sec. (Flow 10 starts
at 45 sec.) We see from this figure that unfairness is caused
among four flows.
On the other hand, Fig. 13 and 14 show results when TCP
with DFC is used. We can see from these figures that thethroughput of each flow is steady and the value of throughput
for each flow reaches the ideal value 13.5 Mbps (54 Mbps/4
flows).
IV. C ONCLUSION
We have proposed DFC to overcome the difficulty ofcontrolling high-speed networks. In this paper, we used DFC
to control Manet, and verified that DFC works well evenwhen the exchange of information across the entire network
is limited. We investigated the characteristics of throughput

345

Fig. 11.
model)

Throughput in the case of TCP without DFC. (random link costfor each flow when TCP flow control without DFC or TCP
with DFC is used in Manet. The simulation results showedthat unfairness is caused in the case of TCP without DFC.
This is because the congestion occurring in Manet leads tothe packet losses of some flow and TCP reduces its window
size. In addition, the other flows sharing the link with this flow
can use the remaining bandwidth.
Moreover, we investigated the performances of TCP with
DFC and we found that the throughput of each flow is steadyand the value of throughput for each flow reaches the ideal
value. These results indicate that the desirable characteristics
of DFC, including the cooperative behavior of nodes to avoid
packet loss and the ability to recover rapidly from congestion,
are also effective for a TCP controlled flow in Manet.
ACKNOWLEDGMENT
This work was partly supported by Grant-in-Aid for Young
Scientists (B) (21700086) from the Japan Society for the
Promotion of Science and the Ministry of Internal Affairs andCommunications of Japan under Grant-in-Aid for Strategic Information and Communications R&D Promotion Programme

Fig. 12. Throughput of flow 3, 6, 9 and 10 (TCP without DFC). (random
link cost model)

Fig. 13. Throughput in the case of TCP with DFC. (random link cost model)(SCOPE).

Fig. 14. Throughput of flow 3, 6, 9 and 10 (TCP with DFC). (random link
cost model)[12] Zhenghua Fu, Petros Zerfos, Haiyun Luo, Songwu Lu, Lixia Zhang,and Mario Gerla, “The impact of multihop wireless channel on TCP
throughput and loss, Proc. of 22th Annual Joint Conference of theIEEE Computer and Communications Societies, pp. 1744-1753, IEEE,San Francisco, USA, Mar. 2003.
[13] Li-Ping Tung, Wei-Kuan Shih, Te-Chung Cho, Yeali S. Sun, andMeng Chang Chen, “TCP Throughput Enhancement over Wireless Mesh
Networks, IEEE Communications Magazine, vol. 45, no. 11, pp. 64-70,
Nov. 2007.
[14] C. Takano and M. Aida, “Diffusion-type autonomous decentralized flow
control for end-to-end flow in high-speed networks,” IEICE Transactions
on Communications, vol.E88-B, no.4, pp.1559-1567, 2005.
[15] 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.
[16] C. Takano, K. Sugiyama and M. Aida, “Parameter Design for DiffusionType Autonomous Decentralized Flow Control,” IEICE Transactions on
Communications, vol. E91-B, no. 9, pp. 2828-2837, September 2008.
[17] C. Takano and M. Aida, “Autonomous decentralized flow control allowing control timing independent of link length,” IEEE ISADS 2009
Workshops (AHSP 2009), Athens, Greece, March 23-25, 2009.

R EFERENCES[1] http://www.ietf.org/html.charters/manet-charter.html[2] 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.
[3] E. Perkins, M. Belding-Royer and R. Das, “Ad hoc on-demand distancevector (AODV) routing,” Request for Comments 3561, July 2003.
[4] T. Clausen and P. Jacquet, “Optimized link state routing protocol(OLSR),” Request for Comments 3626, October 2003.
[5] Y. Hu, A. Perrig, and B. Johnson, “Ariadne: A Secure on-demand routing
protocol for ad hoc networks,” in Proceedings of ACM MobiCom 2002,
Sept. 2002.
[6] Y. Xu, J. Heidemann and D. Estrin, “Geography-informed energy conservation for ad hoc routing,” in Proceedings of ACM Mobile Computing
and Networking 2001, July 2001.
[7] X. Lin and N. B. Shro , “Joint rate control and scheduling in multihop
wireless networks,” in Proceedings of IEEE Conference on Decision andControl, Bahamas, 2004.
[8] 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.
[9] H. Balakrishnan, V. Padmanabhan, S. Seshan, and R. H. Katz. , “A Comparison of Mechanisms for Improving TCP Performance over Wireless
Links, IEEE/ACM Transactions on Networking, Dec. 1997.
[10] M. Gerla, R. Bagrodia, L. Zhang, K. Tang, and L. Wang, “TCP overWireless Multihop Protocols: Simulation and Experiments, IEEE ICC
1999.
[11] G. Holland and N. Vaidya, “Analysis of TCP Performance over Mobile
Ad Hoc Networks, ACM MOBICOM 1999.

346