An Efficient Unstructured P2P Overlay for File Sharing Over MANETs Using Underlying Reactive Routing 1

An Efficient Unstructured P2P Overlay for File Sharing over MANETs

Using Underlying Reactive Routing
Nadir Shah, Depei Qian, Rui Wang
State Key Laboratory of Software Development Environment, Sino-German Joint Software Institute, Beihang University
China
Nadirshah82@gmail.com, depeiq@buaaa.edu.cn, rui.wang@jsi.buaa.edu.cn

Abstract P2P applications have been deployed over the Internet [11-
13].
In a traditional unstructured P2P file sharing network, Mobile and wireless technology has achieved great
each peer establishes connections with certain number of progress in recent years. Today’s cell phones, PDAs
randoma chosen other peers to ensure the connectivity and other handheld devices have larger memory, higher
of the P2P overlay. This paper explains how this random processing capability and richer functionalities. The user
overly leads to redundant traffic and P2P network partition can store more audio, video, text and image data with
in mobile ad hoc network (MANET). We propose an handheld devices. These devices are also equipped with
approach to construct an efficient unstructured P2P overlay low radio range technology, like Bluetooth [14] and Wi-Fi
over MANET using underlying reactive routing. Instead [15]. By means of the low radio range technology, they can
of having redundant links among the peers in the P2P communicate with each other without using communication
network, we introduce a root-peer connecting all peers. infrastructure (e.g., cellular infrastructure) and form a
Each peer maintains connection with closest peers such that mobile ad hoc network (MANET). Each node in MANET
it can reach the root-peer. A peer constructs a minimum- works as both a host (for sending/receiving the data) and a
spanning tree consisting of itself, its directly connected router (forwarding the data for other nodes). It is deployed
neighbor peers and 2-hop away neighbor peers to indentify in the places where infrastructure is either not available,
far away peers and builds the overlay closer to the physical for example disaster scenario, or too expensive. Due to
network. Due to limited radio range and mobility of nodes high capability of the mobile devices, P2P networks can be
in MANET, the physical network partition and merging can deployed over MANET composed of mobile devices. There
occur. This can also lead to the P2P network partition and are various P2P applications over this kind of MANET. For
merging. This paper also proposes a cross-layer approach example, the users equipped with the cell phones, PDAs
to detect and merge P2P networks as soon as the P2P or other handheld devices, communicating through low
networks become physically connected. For this, we extend radio range, can form a P2P network for sharing audio/
ODACP (an address auto-configuration protocol) to detect video clips, pictures, files and other information. Possible
that P2P networks have connected in physical in order to file sharing application scenarios can be found at airport
start the merging of P2P networks. We propose an approach lounges, music concerts, bus stops, railway stations and
to merge P2P networks such that physically closer peers cafeteria.
of the P2P networks participate in the merging process The existing approaches for P2P over Internet cannot
reducing redundant traffic. We can show by simulation that be directly applied to the ones over MANETs due to
our approach performs better in comparison to the existing the unique characteristics of MANETs, such as nodes’
approach. mobility, scarce of power energy, limited memory and
infrastructure less nature. Recently, several schemes have
Keywords: P2P, MANET, Client/Server system. been proposed for P2P over MANETs. Majority of them
are only modification of the existing P2Ps over Internet
1 Introduction [16-28] while a few have adopted new approaches [29-
39]. The existing approaches for unstructured P2P system
Peer-to-peer (P2P) network is an alternative of the over MANET also consider that the physical network
client/server systems for sharing resources like CPU, is connected. Therefore they ignore the P2P network
memory, files etc. It is a robust, distributed and fault partition and merging. Network partition is the breakdown
tolerant network architecture. A number of approaches for of a connected topology into two or more disconnected
P2P over wired network (Internet) have been proposed [1-9]. topologies. The node in one topology cannot access the
These approaches can be roughly classified into structured, node in other topology. The merging of networks means
unstructured and hybrid architectures [10]. Each of them that they get connected by coming into radio range of each
has its own applications and advantages. Many important other. In our scenario, when multiple physical network

*Corresponding author: Nadir Shah; E-mail: Nadirshah82@gmail.com

2 Journal of Internet Technology Volume 12 (2011) No.3

partitions merge, we can explore more peers and thus a The approaches for unstructured P2P file sharing over
large portion of shared files can be accessed by merging MANET in [33-35] do not maintain overlay network among
their respective P2P networks. the peers. The file-lookup request is flooded in the whole
We are interested in the unstructured P2P file sharing network similar to the route request of AODV [40]. But this
over MANET using underlying reactive routing. Our is content-based, i.e., it returns not only the ID of the source
approach is targeting at the MANET’s scenarios where not peer but also the route to the source peer. Flooding-based
all the nodes are to share and access the files, i.e., some approaches are inefficient and do not scale well [43].
nodes are peers and others are non-peers. We define a node In [17], the authors evaluate the performance of
that joins the P2P network for sharing/accessing the files Gnutella using various underlying reactive and proactive
as a peer. Non-peer nodes are called normal nodes. This routing protocols. They also do not consider the
scenario is common over the Internet and MANET. optimization of Gnutella over MANETs. Their finding is
Our approach builds up an efficient overlay for that Gnutella over reactive routing protocol AODV [40]
unstructured P2P file sharing over MANET using performs better as compared to other routing protocol. That
underlying reactive routing protocol AODV [40] instead is why we also select AODV [40] as an underlying routing
of cluster-based routing as in our previous paper [41]. The protocol.
contribution of this paper includes: Diego et al. [18] improves the unstructured P2P over
(1) Proposing the efficient use of expanding-ring-search MANET using Gossiping [44] approach of MANET routing
(ERS) algorithm [42] to find the physically closer protocol. They compute the forwarding probability of a link
surrounding neighbor peers for a peer during its joining based on the network load. Thus the packet is forwarded on
and recovery process. the lower load link. Keeping in view the findings of [17],
(2) Introducing a root-peer in the P2P network to connect they also use AODV [40] as an underlying routing protocol
all peers. Each peer maintains connection with and do not attempt to construct an efficient P2P overlay.
physically closest peers such that it can reach the root- Macro et al. [16] proposes a cross-layer approach
peer. called XL-Gnutella for Gnutella [11] over MANETs using
(3) Building a minimum-spanning tree (MST) at peer proactive routing protocol OLSR [45]. In this approach, a
P which consists of P itself, P’s directly connected new control message, called Optional Information (OI), is
neighbor peers and P’s 2-hop away (logically) neighbor introduced for advertising and exchanging peer’s credential
peers. This MST is used by the peer to remove in the same way as other control messages of routing
redundant far away links. protocol are exchanged among the nodes. Though this
(4) Proposing a cross-layer approach to detect and merge approach tries to build up an overlay network in which a
the P2P networks as soon as the P2P networks become peer prefers to contact closer peer in the physical network,
connected in physical network. it does not establish overall an efficient overlay.
The simulation results show that our approach The above mentioned approaches do not consider the
outperforms random overlay approach adopted by Gnutella P2P network partition and merging.
[18] in term of routing overhead, average file-discovery There are various algorithms proposed in literature to
delay and false-negative (FN) ratio. detect/avoid physical network partition in MANETs e.g., in
We present the related work in Section 2. The [46-50]. These approaches could detect physical network
limitations of random P2P overlay are discussed in Section partition but are not suitable to detect merging of networks.
3. The detailed description of our approach is presented in Since it is a must for every node to have a valid and
Section 4. Section 5 presents the simulation and results. unique address in order to communicate with other nodes.
Finally, Section 6 concludes the paper. The address auto-configuration for MANET can detect
network partition and merging. Therefore we extend
2 Related Work the address auto-configuration protocol to handle P2P
network partition and merging. The previous approaches
Previously proposed approaches for the unstructured for P2P over MANET assumed that the nodes are priori
P2P file sharing over MANET are based on two types of configured with unique address, ignoring the address auto-
underlying routing, reactive and proactive routing protocols. configuration.
Reactive routing protocol finds the route on demand, i.e., it Main approaches for address auto-configuration in
finds the route to a destination when the data is to be sent MANETs are [51-56]. Each of these approaches has its
to that destination. Proactive routing protocols periodically own advantages and disadvantages depending upon the
update routing information to all nodes regardless of application scenario. Yuan et al. [56] presents a leader-
whether or not the data is to be sent to those nodes. based approach for address auto-configuration in MANET,
 An Efficient Unstructured P2P Overlay for File Sharing Over MANETs Using Underlying Reactive Routing 3

called Optimized Dynamic address configuration protocol P5

(ODACP). Each partition in ODACP has an address
authority (AA) and is identified by unique partition ID. AA
P1 N1 P2 P3 N2 N3
is responsible to detect network partitioning and merging.
AA also has the list of allocated addresses in the partition.
It is shown through the simulation results in ODACP [56] P4 N5 P6
that ODACP approach could perform better in comparison
to other approaches with both reactive and proactive Peer Non-peer Communication link

routing protocols. Therefore we extend ODACP to handle

(a) A Part of P2P Network
P2P network partitioning and merging for our approach as
discussed in Section 4.7.
P4
P1 P4
3 Limitations of Random Overlay P3

P1
P2
P3 P5
The above mentioned approaches either use flooding P6
based approaches or construct a random overlay for
P2
unstructured P2P file sharing over MANET. The flooding- P6 P5
based approaches are inefficient and do not scale well.
While the random overlay for unstructured P2P over (b) (c)
MANET has the following limitations.
P4
3.1 Unnecessary Redundant Traffic in Overlay P3
To maintain a connected overlay topology in Gnutella P1
P2
[11] [18], a peer maintains connection with neighbor peers
P6
according to the values of lower bound (LB) and upper
bound (UB). It leads to redundant traffic in the overlay
N3 P5
topology. Take the part of a P2P network structure in Figure
1(a) as an example. When the value of LB and UB is 4
(d)
and 8 respectively, the overlay structure of Figure 1(a) is
Figure 1 To Show Redundant Traffic of A Random Overlay
shown in Figure 1(b). We can see in Figure 1(b) that the
peer P1 has P2, P3, P4 and P5 as neighbor peers and P4 has
P1, P2, P3, P6 and P5 as neighbor peers. P1 sends its file- on link P1-N1, two transmissions on link N1-P2, and one
lookup request to its neighbors P2, P3, P4 and P5 for file transmission on each link P1-P4, N1-P5 and P2-P3, will be
discovery purpose. Then peer P4 forwards the same file- sent. These transmissions are shown through thin arrows
lookup request to its neighbors P2, P3, P5 and P6 excluding in Figure 1(a). Then P4 will forward the same file-lookup
P1. As a result, both P1 and P4 send the same file-lookup request to its neighbor peers P2, P3, P6 and P5 producing
request to P2, P3 and P5. We can learn from the above eleven more transmissions in the physical network. The
scenario that both P1 and P4 send redundant probe (ping) distribution of these transmissions is four transmissions
messages to their neighbor peers P2, P3 and P5 in order on link P4-N1, three transmissions on link N1-P2, two
to maintain connectivity. Thus random P2P overlay over transmissions on link P2-P3 and one transmission on each
MANET produces redundant traffic in both file-discovery link N1-P5 and P6-P3. These transmissions are shown
and connection maintenance process. through bold arrows in the Figure 1(a). In MANET, these
redundant transmissions would consume a lot of bandwidth
3.2 Redundant Traffic in Physical Network and energy.
We show that the random overlay of Gnutella over
MANET [11] [18] can lead to redundant traffic not only in 3.3 P2P Network Partition
overlay but also in the physical network. Take the Figure Though, in Gnutella over MANET [18], each peer
1(a) and 1(b) as an example, P1 sends the file-lookup maintains neighbor connection with certain number of peers
request to its neighbor peers P2, P3, P4 and P5 for file- to ensure the connectivity of P2P overlay topology. A P2P
discovery purpose. To deliver the file-lookup request from network partition may still occur while the physical network
P1 to P2, P3, P4 and P5, it will produce eight transmissions is connected. For example, the overlay network among the
in the physical network as follows. Three transmissions peers is established as shown in Figure 2(a), taking 4 as the
maximum size of neighbor list of a peer according to [18].
4 Journal of Internet Technology Volume 12 (2011) No.3

The distance of the links in the physical network is shown and 5, respectively, the overlay structure of Figure 1(a) is
as the weight of the links. When P6 leaves P2P network, shown in Figure 1(c). Now node N3 wants to join the P2P
the topology becomes the one as shown in Figure 2(b). This network, it cannot establish the connection with closer
is because that a peer receives early response for a request peers in the physical network, i.e., with the peers P2 and
from the physically closer neighbor peers. P2P network P3. This is because P2 and P3 are in full-state, each of them
partition exists though the underlying physical network is has maximum five connections, and the new peer N3 is not
fully connected and each peer maintains connection with closer than their current closest neighbor peers. Therefore
maximum number of neighbor peers according to [18]. N3 has to connect with far away peers (P5, P6 and P1) as
In this scenario, the file-lookup query from one partition shown in Figure 1(d), leading to mismatch between overlay
would not be able to reach other partition. and physical topologies. This topology mismatch would
increase redundant traffic in network and the file-discovery
P5 1 delay. Take Figure 1(d) as an example, N3 sends the file-
P9
1 1 3 P11 1
lookup request to P5, P1 and P6 for file-discovery purpose.
1 This file-lookup request will pass through P3 in the physical
P4 1 P6 1
P10
P1
4
2 1 network. Then P6 will forward the same file-lookup request
1
1
P8 2 2 to P3 and to its other neighbor peers. That is, the file-lookup
1 1
1
2 request initiated by N3 will be received by P3 after passing
1 1 2
P2 P3
P12 through P6 in the physical network, though P3 is closer in
physical network to N3 than P6. This produces not only
(a) When P6 is Member of P2P Network redundant traffic in the physical network but also increases
the latency of file-discovery if the matching-file resides on
P5 1
1 P3.
P9
1 2 3 P11 1
1
P4 1 P6 1
1 3.5 Tradeoff between Redundant Traffic and P2P
4 P10
P1 2
1
Network Partition
1 1
P8 2 2 The redundant traffic and P2P network partition in the
1 1
1
2 random overlay adopted by Gnutella over MANET [16-
1 1 2
P2 P3
P12 18] depends on the number of neighbor peers that a peer
can have, which is also called size of the neighbor list of a
(b) peer. There is a tradeoff between redundant traffic and P2P
network partitions on the size of neighbor list in Gnutella
Peer Communication link in physical network over MANET. A P2P scenario having larger neighbor
Non-peer
list would produce more redundant traffic in the network
Overlay link
and have less chances of P2P network partition. A P2P
Figure 2 An Example to Show P2P Network Partition in Gnutella scenario having smaller neighbor list would produce less
redundant traffic in network and have more chances of P2P
3.4 Mismatch between Overlay and Physical Topology network partition. The selection of the neighbor list size is
Diego et al. [18] does not consider the optimization influenced by the distribution of peers and the peers ratio in
for P2P overlay over MANET to take the advantage of the network. It is difficult to get an optimum neighbor list
cross-layer mechanism of MANET routing protocol. XL- size for the P2P network over MANET due to the dynamic
Gnutella [16] takes the advantage of cross-layer mechanism nature of both P2P network and MANET.
in which a peer prefers to contact closer peer in the
physical network. That is, in full-state, having connection 3.6 Bootstrapping Using Reactive Routing
with maximum number (UB) of neighbor peers, a peer When a node wants to join a P2P network, it finds
P establishes connection with or accepts the incoming the existing peers in the network to establish connection
connection from a new peer P1 provided P1 is closer than with them. This process is called bootstrapping. Due to
the closest current neighbor peers of P. In this case the peer the broadcast nature of wireless medium, in unstructured
P will drop the farthest connection. But still XL-Gnutella P2P over MANET, a node prefers to establish connection
[16] does not guarantee that a peer will always establish with its physically closest surrounding peers in the network
neighbor connection with physically closer peers in the during bootstrapping process. This is an attempt to have a
network. Take the part of a P2P network structure in Figure P2P overlay closer to physical network to reduce redundant
1(a) as an example. When the value of LB and UB is 3 traffic. To get the closest surrounding peers by a peer,
 An Efficient Unstructured P2P Overlay for File Sharing Over MANETs Using Underlying Reactive Routing 5

there are two mechanisms adopted for the bootstrapping in and increase the file-discovery latency as discussed in
unstructured P2P over MANET. First, when a node wants Section 3.4.
to join a P2P network, the node broadcasts the joining
request to the entire network and establishes connection 3.7 P2P Network Merging Due to Physical Network
with the peers whose reply is received early as in [18]. Merging
This approach would produce heavy routing traffic in the Due to limited radio range and mobility of nodes,
network and does not scale well. Second, a node uses there can occur physical network partition and merging in
the ERS [42] algorithm during bootstrapping process MANET. This can also lead to P2P network partition and
as discussed in [16]. In this approach, a node sends the merging. There are two parts to handle the merging of P2P
join request with increased TTL value till it establishes networks when they become connected in the physical
connections with minimum number of peers. This approach network. First is to detect that the P2P networks become
attempts to control flooding but cannot avoid the mismatch connected in the physical network. The second step is to
between P2P overlay and physical network. For example merge P2P networks so that less routing traffic is produced
a part of P2P network as shown in Figure 3(a) has its P2P in the network. However, the following feature of Gnutella
overlay as in Figure 3(b), taking 3 and 5 as the values of LB over MANET can have the chance to merge the P2P
and UB respectively. When node N3 wants to join the P2P networks when they become physically connected. When
network, it will send the join request using ERS algorithm. the number of neighbor peers of a peer falls less than LB
N3 will receive the join reply from the peer P2, P3 and value, the peer broadcast the query to find new neighbor
P4. Then N3 will stop to send join request and establish peers to connect with them and fulfill LB condition. During
connection with them, and the resulting P2P overlay will be this phase in Gnutella, there are chances that the peer of
as shown in Figure 3(c). This P2P overlay is not matching one P2P network connects with the peer of another P2P
with the physical network because N3 is closer to P1 than network. Other than this, Gnutella over MANET does not
P2, i.e., the file-lookup request initiated by N3 would be have an explicit mechanism to detect that the P2P networks
received on P1 after passing through P2 and P3 in the become connected in the physical network. Gnutella over
physical network. This mismatch between P2P overlay and MANET also lacks the approach to merge P2P networks
physical network would generate more redundant traffic when they become connected in the physical network. Due
to this, Gnutella over MANE cannot explore large portion
P4 of data items which become available when P2P networks
P3
become physically connected.
N1 N2 P2

4 Proposed Algorithm
P1 N3

Our system has a root-peer connecting all peers in

(a) A Part of P2P Network
the P2P network. The process is illustrated as follows.
When two peers, say peer A and peer B, establish neighbor
P4 relationship, the root-peer is used as a reference point to
designate one of them to be responsible to maintain the
P1
P3 neighbor relationship. Peer A sets its neighbor B’s state as
NBIND if A is closer to the root-peer or has the lowest ID
P2
in case of tie (when both A and B are at the equal distance
(b) An Overlay before N3 Joins the P2P Network from the root-peer). Otherwise, peer B’s state will be set to
BIND and A’s state is set to NBIND. A peer periodically
P4
sends probe messages to the neighbor peers with a BIND
state to maintain neighbor relationship, and receives probe
P1 P3 messages from neighbor peers with a NBIND state. Each
peer (except the root-peer) connects to at least one other
P2
N3 peer with a BIND state to ensure the connectivity of the
P2P network. Upon receiving the updated information
(c) An Overlay After N3 Joins the P2P Network of the P2P topology, a peer P constructs an undirected,
weighted connected graph consisting of P, P’s directly
Non-peer Communication link connected neighbor peers and P’s 2-hop away (logically)
neighbor peers. The weight of the link between two
Figure 3 An Example to Show Bootstrapping Process
6 Journal of Internet Technology Volume 12 (2011) No.3

logically linked peers in the graph is the number of hops reverse route which is established during the request phase
between the two logically linked peers in the physical as in AODV [40]. The CRPLY also contains similar fields
network. Using this graph, the peer executes minimum as in CRQST. Due to on-demand nature of the underlying
spanning- tree (MST) algorithm with itself as a source routing algorithm and ERS algorithm, a peer may not get
vertex to identify redundant links. Then the redundant links the route and its distance to the root-peer from its routing
are removed and an efficient overlay is built up which is agent. In this case the peer calculates its distance to the
closer to the physical network. In our system, each peer root-peer as the total minimum distance from itself to its
maintains a peer-routing table that stores the information of directly connected neighbor peer plus the distance from that
the root-peer and neighbor peers, as shown in Figure 4(b). neighbor peer to the root-peer, as shown below
Each peer also maintains a local repository which contains
index of its stored files. The detail description of the basic Dp = minn (Dp-Q + DQ) (1)
operations of our approach is given as follows.
Where n is the number of directly connected neighbor peers
4.1 Peer-Join of P, Q is a directly connected neighbor peer of P, DP is the
During bootstrapping process, instead of broadcasting distance from peer P to the root-peer, DP-Q is the distance
the joining request to the entire network as in [18] or from peer P to peer Q. The neighbor relationship between
using traditional ERS algorithm as in [16], the peer in our two peers is adjusted as discussed above. The peer P builds
approach gets its physically closer surrounding peers in the an undirected weighted connected graph consisting of P,
network as follows. First, the join peer informs its routing P’s directly connected neighbor peers and P’s 2-hops away
agent so that the routing agent can inform the peer of the (logically) neighbor peers. Using this graph, the peer P
P2P traffic passed through. Then the join peer sends the executes minimum-spanning-tree (MST) algorithm with
joining request (JRQST) using ERS algorithm to find the itself as a source to identify redundant links. The peer
closest online peer of the P2P network. Receiving JRQST, a drops the connection of a directly connected neighbor peer
peer sends the join reply message (JRPLY) to the requesting to which it does not have direct link in MST. The peer
peer. The JRPLY is sent to the requesting peer through establishes neighbor connection with a new peer which is
reverse route which is established during the request phase not previously directly connected neighbor peer but has a
as in AODV [40]. A non-peer node receiving JRQST will direct link in MST.
forward it further provided the request message’s time-to- To illustrate the joining process of a peer through an
live (TTL) is greater than zero. Sending JRQST is stopped example, a part of P2P network is shown in Figure 4(a)
when the join peer either receives JRPLY from at least one with P1 as the root-peer. Now node N3 wants to join the
other peer or when the TTL reaches maximum threshold P2P network. It sends the JRQST using the ERS algorithm
value, which is one of following two cases. and receives JRPLY from P2. Thus N3 comes to know that
yyThe time-to-live (TTL) value of the ERS algorithm its surrounding peers are P1 and P2. Then N3 broadcasts
reaches the maximum threshold and the join peer does CRQST to establish neighbor relationship with these
not receive any JRPLY. The join peer assumes that there surrounding peers. To control flooding, the TTL in the
is no other peer in the network and itself becomes the CRQST is set to the maximum distance of the surrounding
root-peer. peer from the sending peer so that the CRQST can reach
yyThe join peer receives JRPLY from at least one other to every surrounding peer. Due to on-demand nature of
closest peer. JRPLY from peer P contains P’s directly underlying routing protocol, N3 can get from its routing
connected neighbor peers, the root-peer, and their agent the distance of P2 but the distance of P2’s neighbor,
distance from P. This means that the senders of JRPLY i.e., the distance between P1 and N3, may not be available
and their directly connected neighbor peers are the at the routing agent of N3. In this case, N3 must calculate
physically closer surrounding peers of the join peer. the distance from itself to P1 as follows.
After receiving JRPLY, the join peer broadcasts
a connect-request (CRQST) to establish the neighbor DN3-P1 = DN3-P2 + DP2-P1 (2)
relationship with its surrounding peers. To control flooding,
the TTL in CRQST is set to the maximum distance of the After exchanging CRQST and CRPLY, the resulting
surrounding peer from the join peer. CRQST also contains physical topology is shown in Figure 4(b). The
fields similar to JRPLY. Upon receiving CRQST, a peer corresponding overlay of Figure 4(b) is shown in Figure
stores the information of the sending peer in its peer- 4(c). The connected graph of P1 is shown in Figure 4(d).
routing table and replies with a connection reply (CRPLY). After executing the MST algorithm, the resulting minimum
The CRPLY is also sent to the requesting peer through the spanning tree of P1 is shown through bold lines in Figure
 An Efficient Unstructured P2P Overlay for File Sharing Over MANETs Using Underlying Reactive Routing 7

Peer-routing table on P1 4(d). Then P1 will identify that its previous neighbor peer
Root Its distance
P2 is no longer its direct neighbor in MST while the new
P1 0
Neighbor Its distance Its status Its neighbors Their distance
join peer N3 is. So it will drop its connection with P2 and
P2 4 NBIND _ _ maintain its connection with N3. The resulting final overlay
Peer-routing table on P2 topology is shown in Figure 4(e) and its corresponding
Root Its distance
physical network is given in Figure 4(f).We can tell that
P1 4
Neighbor Its distance Its status Its neighbors Their distance
this is a more efficient overlay with a topology closer to
P1 4 BIND - - the physical network.

P1 N1 N2 N3 P2 4.2 Update
Each peer periodically sends out probe messages to
(a) A Part of P2P Network before N3 Joins the P2P Network its directly connected neighbor peers with BIND state to
Peer routing table of N3 maintain connectivity. Upon receiving the probe message,
Root its distance
P1 4 a peer also replies to the sender of the probe message. The
Neighbor
P2
Its distance Its status Its neighbors Their distances
1 NBIND P1 4
probe message from peer P contains root-peer, P’s directly
P1 3 BIND P2 4 connected neighbor peers, the distance of root-peer from P
and the distance of P’s directly connected neighbor peers
P1 N1 N2 N3 P2 from P. Since connectivity among the nodes may change
due to nodes’ mobility, therefore the peer-routing table is
Peer routing table of P1 updated accordingly. Any update in the peer-routing table
Root its distance
P1 0 triggers to execute MST algorithm.
neighbor Its distanceIts status Its neighbors Their distances
P2 4 NBIND - _
N3 3 BIND P2 1 4.3 Peer-Leave
Root
Peer routing table of P2
its distance
When a peer wants to leave the P2P file-sharing
P1 4 network, it can invoke peer-leave operation to inform
neighbor Its distanceIts status Its neighbors Their distances
P1 4 BIND - - its neighbor peers about its leaving. The neighbor peers
N3 1 BIND P1 3 receiving that information invoke a recovery operation.
(b) The P2P Network After N3 Joining and before the Normally, a peer does not inform its neighbor peers about
Execution of MST Algorithm its leaving. The absence of a peer can be detected by its
3
P1
3
N3
3 neighbor peers by the built-in keep-alive mechanism.
P1 N3 P1 N3

1
4 1
4 1
4.4 Recovery
P2 P2
When a peer P detects that one of its neighbor peers,
P2

(c) (d) (e) say P1, with a state of BIND is disconnected, it invokes
Peer routing table of N3 the recovery procedure. The disconnection of peer P1
Root It s dist ance
may be caused by nodes’ mobility or the peer P1 has left
P1 3
Neighbor It s dist ance It s st at us It s neighbors T heir the P2P network or has been switched off. In any case,
P2 1 NBIND _
dist ance
_ peer P broadcasts the recovery request message (RRQST)
P1 3 BIND _ _ using ERS algorithm. RRQST contains the disconnected
peer P1. The initial TTL of ERS algorithm is set to the
P1 N1 N2 N3 P2
distance between the disconnected peer P1 and peer P
Peer routing table of P2 plus one. Upon receiving RRQST, a peer sends recovery
Root It s dist ance
reply message (RRPLY) to the requesting peer provided
P1 4
Neighbor It s dist ance It s st at us It s neighbors T heir either the receiving peer is the disconnected peer or the
dist ance
N3 1 BIND P1 3 disconnected peer is one of directly connected neighbor
Peer routing table of P1 peer of the receiving peer. RRPLY contains the similar
Root It s dist ance
P1 0
fields as in probe message. RRPLY is forwarded to the
Neighbor It s dist ance It s st at us It s neighbors T heir
dist ance
requesting peer through reverse route established during
N3 3 NBIND P2 1 the recovery request phase. Sending RRQST is stopped
when the requesting peer P receives RRPLY either from
(f) The P2P Network after the Joining of N3 and After the
the disconnected peer or from all of the directly connected
Execution of MST Algorithm by the Peers
neighbor peers of the disconnected peer. Receiving RRPLY,
Figure 4 To Show the Joining Process of a Peer the requesting peer P broadcasts CRQST to the senders
8 Journal of Internet Technology Volume 12 (2011) No.3

of RRPLY to establish connection with them. Then the partitions, the change of address configuration is handled
requesting peer P executes the MST algorithm to remove as in ODACP [56] with the modification that the change
the redundant links. The absence of a peer P1 can be of addresses is done in the partition having less number of
detected by a peer P through probe messages or from the nodes. This would reduce the routing overhead during the
routing agent of P. If the disconnected neighbor peer is the merging of network partitions. However the P2P network
root-peer and has left the P2P network, one of the closest at the application layer has to perform additional task to
directly connected neighbor peers of the disconnected root- handle the merging of P2P network partitions as follows.
peer announces itself as the new root-peer. In case of tie, When two partitions are merged and their address
the one having the lowest ID is elected as the new root- conflict is resolved then the address authority (AA)
peer. Then the new root-peer is announced to the other having less number of nodes changes its network ID to
peers in the P2P network by broadcasting change root- the one of new partition and announces this to its nodes
peer message (CROOT) in the same way as the file-lookup by broadcasting the message change node ID (CNID) in
query is sent. Receiving CROOT, the peer changes its root- its partition. CNID contains the old AA ID and new AA
peer to the one in CROOT. ID. We further propose that every node, forwarding CNID
to its neighbor nodes, also piggybacks its new node-ID
4.5 File-Discovery (provided its node-ID has been changed due to merging).
As our approach is based on unstructured P2P network, Upon receiving CNID, a node examines for change of its
therefore we use keyword-based searching to find a file in neighbors’ node ID and replaces the old node ID with new
the network. When a peer wants to retrieve a file, it sends one but the old one is also retained for some time. In this way
out the file-lookup query (FRQST) to all of its directly the nodes come to know about the new ID of its neighbors.
connected neighbor peers. Upon receiving FRQST, a Receiving CNID at routing layer, a peer P notifies the P2P
peer examines its local repository for matching file. If a at application layer using cross-layer mechanism about the
matching is found in the local repository, the receiving peer occurrence of merging in physical network provided P’s
sends the file-lookup reply (FRPLY) to the requesting peer. AA has been replaced by the new AA in the CNID. Thus
Otherwise, the receiving peer forwards the FRQST to its after this the P2P network merging starts. We propose that
directly connected neighbor peers excluding the one from the peers near to new partition participate in P2P network
which the FRQST is received. When the requesting peer merging as follows. This would reduce the routing overhead
receives the reply for a file-lookup request, it invokes the as well as the delay for P2P network merging because only
file-access operation. If the requesting peer does not receive some suitable peers participate and the topology of P2P
any reply for a file-lookup request within certain period of network in this partition would be stable.
time, it resends the file-lookup request provided the number In this approach, receiving the CNID preceded by
of retries does not exceed the maximum threshold value. the merging detection, the peer P waits for random time
and then initiates the merging operation by broadcasting
4.6 File-Access P2P merging request (PMRQST) message in the physical
The requesting peer may receive replies for a file- network using ERS algorithm. This time the starting TTL
lookup request from multiple source peers. It retrieves the value of ERS is the distance of new partition from P.
file from a source peer having shortest distance. Due to The random waiting time at a P is an order of physical
on-demand nature of AODV, the requesting peer may not closeness of P to the new AA. PMRQST from peer P
have the route to the source peer in its routing agent. In this contains the P’s old AA, P’s new AA and P’s distance to the
case the requesting peer retrieves the file from the source new AA. Receiving PMRQST, a non-peer node forwards
peer following the route in overlay network. A scheduling PMRQST further provided the TTL value of PMRQST is
algorithm like [33] can be implemented, for the sake of not expired. Receiving PMRQST from peer P, the receiving
simplicity, to retrieve the file from the source peer. peer P1 does the following actions.
yyIf P’s old AA and P1’s old AA are same and P1 has
4.7 P2P Network Partitioning and Merging greater distance to the new AA than P’s distance to the
The P2P network partition is handled by our approach new AA, P1 discards PMRQST and P1 also discards its
using the recovery operation as discussed in Section 4.4. own merging operation.
That is, when a peer P detects the disconnection of its yyIf P1’s old AA is not equal to the P’s old AA, P1 sends
neighbor peer P1, the peer P invokes recovery operation for reply P2P merging message (PMRPLY) to the requesting
the disconnected neighbor peer P1. To detect the merging peer.
of P2P networks when the two physical network partitions
merge, we propose the following approach.
Upon detection of the merging of physical network
 An Efficient Unstructured P2P Overlay for File Sharing Over MANETs Using Underlying Reactive Routing 9

Receiving PMRPLY from P1, the requesting peer P Table 1 Simulation Environment
establishes the connection with physically closer new peers Parameter Value
of the new partition by sending CRQST. Then the peer P MAC layer IEEE 802.11
announces its root-peer ID by broadcasting changing root
Transmission range 100m
message (CROOT) in the P2P network in the similar way
as file-lookup query is sent. Receiving CROOT, the peer Total number of nodes 100
changes its root-peer ID to the one in CROOT. Then the Bandwidth 2MB
peer executes MST algorithm to remove far away redundant Simulation area 1000X1000
links. Mobility Model RandomWayPoint
Propagation Model TwoRayGround
5 Simulation Number of file retries 2
We consider the network joining by a node different LB 4
and separate from its joining of P2P network. The former UB 8
one is to join the network by getting valid and unique Ping/probe interval 8 seconds
address (node-ID). The later is the process that an existing
member node of the physical network wants to join a
The evaluation is carried out by varying peers ratio in
P2P network. We assume that ODACP [56] is used as the
the network and the maximum moving speed of nodes.
address auto-configuration algorithm in the network.
From Figure 5, it is shown that Gnutella in comparison
We modify Gnutella [18] by adding the following
to our approach has higher routing overhead at all peers
optimization of XL-Gnutella [16]. A peer P in the full-
ratio and maximum moving speed of nodes. These figures
state, i.e., having connection with maximum number of
also show that with the increase of peers ratio, the routing
neighbor peers, establishes connection with or accepts the
overhead of both approaches increases. It is because
incoming connection from a new peer P1 provided P1 is
more connections among the peers are established with
closer than closest current neighbor peers of P. In this case
the increase of peers ratio resulting more routing traffic.
the peer P will drop the farthest connection. We use 4 and
It is also shown from these figures that with the increase
8 as the values of LB and UB, respectively, for Gnutella
of maximum speed of nodes, the routing overhead of
[18]. We use ns-2 [57] to conduct simulation to compare
both approaches also increases. This phenomenon can
our approach with Gnutella [18]. The specification of the
be explained by the fact that with the increase of nodes’
simulation environment is given in Table 1. Each node
moving speed the physical topology changes more
monitors the outgoing link failure from the feedback of
frequently which causes more frequently the execution
the IEEE 802.11 MAC layer. In our scenario the nodes
recovery and network merging operations. However, our
randomly join/leave a P2P file-sharing network while
approach still has lower routing overhead as compared to
maintaining the specified ratio of peers among all nodes.
Gnutella in all cases of nodes’ maximum moving speed.
The file-discovery is randomly initiated for total 100
These figures also show that the difference of routing
random files by the peers in the network. We study the
overhead between Gnutella and our approach is larger when
performance metrics for peer discovery, file-lookup
the number of peers ratio is high due to following reason. In
and overlay maintenance of the resulting overlays. The
Gnutella, when the peers ratio is very high in the network,
following metrics are used for comparison,
every peer has connection with the maximum number of
yyRouting overhead: The total number of packets
other peers (i.e., number of neighbor peers of a peer reaches
transmitted at routing layer.
UB) resulting more redundant connections.
yyAverage file-discovery delay: The average time elapsed
Reducing traffic overhead in MANET reduces the
from the moment when a file-lookup query is sent to the
chances of packet collision and consumption of energy and
moment when the first reply is received.
bandwidth which would result in the increased performance
yyFalse-negative (FN) ratio: The ratio between the numbers
of network and increased network longevity. Thus, by
of unresolved file-lookup queries for the files that exist
reducing traffic overhead, our approach would increase the
and accessible in P2P network and the total number of
network performance and network longevity.
initiated file-lookup queries.
Gnutella maintains redundant links among the peers
and our approach avoids redundant links, therefore one can
expect shorter average file-discovery delay in Gnutella. But
from the Figure 6, our approach has shorter average-file
discovery delay. It is because of the following three reasons.
10 Journal of Internet Technology Volume 12 (2011) No.3

(a) (b) (c)

(d) (e)
Figure 5 The Comparison of Rouitng Overhead between Gnutella and Our Approach

(a) (b) (c)

(d) (e)
Figure 6: The Comparison of Average File-discovery Delay between Gnutella and Our Approach

First, Gnutella has higher routing overhead increasing moving speed of nodes, the average file-discovery delay of
the contention delay to access the medium. Second, our both approaches increases. It is because, traffic overhead
approach builds up an overlay which has a topology closer increases with the increase of nodes’ mobility and peers
to the physical network. Therefore, in our approach, the ratio in the network resulting in the increased contention
file-lookup query is forwarded along the shortest path delay to access the medium and more packet collision in
in the physical network. Third, Gnutella does not ensure the network.
that a peer always establish connection with physically As P2P network partition may occur in Gnutella [18]
closer neighbor peers in the physical network, as discussed over MANET, therefore we investigate two types of false-
in Section 3.4. The figures also show that by increasing negative: false-negative due to P2P network partition
peers ratio in the network and/or increasing the maximum (FNP) and false-negative due to packet collision (FNC).
 An Efficient Unstructured P2P Overlay for File Sharing Over MANETs Using Underlying Reactive Routing 11

Figure 7 shows that FNP in Gnutella increases with 6 Conclusion

the increase of peers ratio due to following reasons. In
Gnutella, the chances of P2P network partition increases This paper presents an approach to construct an efficient
with the increase of peers ratio in the network as discussed unstructured P2P overlay over MANET using underlying
in Section 3.5. Since network partition never occurs in our reactive routing. Instead of having redundant links among
approach, only false-negative due to packet collision exists the peers in the P2P network, we introduce a root-peer to
in our approach. These figures also show that the number connect all peers. Each peer maintains connection with its
of FNC is larger than the number of FNP in Gnutella due closest peers so that it can reach the root-peer. To build up
to following reason. We use uniform random function to the P2P overlay closer to the physical network, each peer
select a file to be searched in the P2P network. And we also constructs a minimum-spanning tree (MST) consisting
use random uniform function to select a peer to initiate of itself, its directly connected neighbor peers and 2-hop
the file-discovery operation. The false-negative ratio is away (logically) neighbor peers. Redundant connections
smaller in our approach as compared to Gnutella. This is are removed according to the resulting MST. P2P networks
because of following reasons. First, Gnutella has higher merging could occur in MANET due the nodes’ mobility
traffic overhead as compared to our approach. The higher and limited radio range. This paper also proposes a cross-
routing traffic results in more packet collisions. Second, layer approach to detect and merge P2P networks as soon
Gnutella lacks a mechanism to merge the P2P networks as as the P2P networks become physically connected. The
soon as the P2P networks become physically connected. simulation results show that our approach outperforms the
While our approach has a cross-layer approach to detect random overlay approach adopted by Gnutella [18] in term
and merge the P2P networks as soon as the P2P networks of routing overhead, average file-discovery delay and false-
become physically connected. We can also learn from the negative ratio.
figures that the FN ratio of both approaches increases with We would like to further investigate the approach to
the increase of both peers ratio and the maximum nodes’ build up an efficient overlay for structured P2P file-sharing
moving speed. This is because, with the increase of peers over MANET. In addition, the design of unstructured P2P
ratio, the routing traffic increases causing larger contention overlay over other types of underlying routing protocols of
delay and more packet collisions in the network. With the MANET will be addressed in the future.
increase of maximum moving speed, the topology changes
more frequently which causes more traffic and more
chances of packet collision in the network.

(a) (b) (c)

(d) (e)
Figure 7 The Comparison of FN Ratio between Gnutella and Our Approach
12 Journal of Internet Technology Volume 12 (2011) No.3

Acknowledgements Journal of Internet Protocol Technology, Vol.4, No.2,

2009, pp.79-90
This work is supported by Project (No.SKLSDE- [9] C. Topal and C. Akinlar, Enabling Peer-to-Peer
2010ZX-0X) of the State Key Laboratory of Software Communication for Hosts in Private Address Realms
Development Environment under contract NO.SKLSDE- Using Ipv4 LSRR Option and Ipv4+4 Addresses, IET
2010ZX-14, and by grants from National High- Tech Communications, Vol.3, No.4, 2009, pp.512-519.
Program of China (863 program) under the contracts [10] Elena Meshkova, Janne Riihijrvi, Marina Petrova
2009AA01Z144, and by grant from Program of and Petri Mhnen, A Survey on Resource Discovery
International Science & Technology Cooperation of China Mechanisms, Peer-to-Peer and Service Discovery
under contracts No.2010DFA11670, 2009DFA12110. Frameworks, Computer Networks, Vol.52, No.11,
2008, pp.2097-2128.
Reference [11] Patrick Kirk, SOURCEFORGE.NET, 2009, http://
rfcgnutella.sourceforge.net/src/rfc-0_6-draft.html
[1] Ion Stoica, Robert Morris, David Karger, M. [12] KaZaA, 2009, http://www.kazaa.com/us/help/
Frans Kaashoek and Hari Balakrishnan, Chord: glossary/p2p.htm
A Scalable Peer-to-Peer Lookup Service for [13] OpenNap, 2009, http://opennap.sourceforge.
Internet Applications, Proc. ACM SIGCOMM 2001 net/#status
Conference, San Diego, CA, August, 2001, pp.149- [14] Bluetooth, 2009, http://www.bluetooth.com
160. [15] WiFi, 2009, http://www.wi-fi.org/
[2] Antony Rowstron and Peter Druschel, Pastry: [16] Marco Conti, Enrico Gregori and Giovanni Turi, A
Scalable, Decentralized Object Location and Routing Cross Layer Optimization of Gnutella for Mobile
for Large-Scale Peer-to-Peer Systems, Proc. IFIP/ Ad hoc Networks, Proc. ACM MobiHoc Symposium,
ACM International Conference on Distributed Urbana-Champain, IL, May, 2005, pp.343-354.
Systems Platforms (Middleware), Heidelberg, [17] Leonardo B. Oliveira, Isabela G. Siqueira and
Germany, November, 2001, pp.329-350. Antonio A. F. Loureiro, On the Performance of
[3] B. Pourebrahimi, K. L. M. Bertels and S. Vassiliadis, Ad Hoc Routing Protocols Under a Peer-to-Peer
A Survey of Peer-to-Peer Networks, Proc. 16th Application, Journal of Parallel and Distributed
A n n u a l Wo r k s h o p o n C i rc u i t s , S y s t e m s a n d Computing, Vol.65, No.11, 2005, pp.1337-1347.
Signal Processing, ProRisc 2005, Veldhoven, The [18] Diego N. da Hora, Daniel F. Macedo, Leonardo B.
Netherlands, November, 2005. Oliveira c, Isabela G. Siqueira, Antonio A. F. Loureiro,
[4] Matei Ripeanu, Adriana Iamnitchi and Ian Foster, Jos M. Nogueira and Guy Pujolle, Enhancing Peer-to-
Mapping the Gnutella Network: Properties of Large- Peer Content Discovery Techniques over Mobile Ad
Scale Peer-to-Peer Systems and Implications for Hoc Networks, Computer Communications, Vol.32,
System Design, IEEE Internet Computing, Vol.6, No.13-14, 2009, pp.1445-1459.
No.1, 2002, pp.50-57. [19] Dewan Tanvir Ahmed and Shervin Shirmohammadi,
[5] Ching-Hsien Hsu, Yun-Chiu Ching, Laurence T. Multi-Level Hashing for Peer-to-Peer System
Yang and Frode Eika Sandnes, An Effcient Peer in Wireless Ad Hoc Environment, Proc. IEEE
Collaboration Strategy for Optimizing P2P Services International Conference on Pervasive Computing
in BitTorrent-Like File Sharing Networks, Journal of and Communications Workshop
Internet Technology, Vol.11, No.1, 2010, pp.79-88. [20] Raphal Kummer, Peter Kropf and Pascal Felber,
[6] Chao-Tung Yang, Fang-Yie Leu and Ming-Feng Distributed Lookup in Structured Peer-to-Peer
Yang, A Peer-to-Peer Video File Resource Sharing Ad-Hoc Networks, Proc. OTM Conferences (2),
System for Mobile Devices, Journal of Internet Montpellier, France, October, 2006, pp.1541-1554.
Technology, Vol.11, No.1, 2010, pp.69-78. [21] Gang Ding and Bharat Bhargava, Peer-to-Peer File-
[7] Yu-Wei Chan, Tsung-Hsuan Ho, Po-Chi Shih and Sharing over Mobile Ad Hoc Networks, Proc. Second
Yeh-Ching Chung, Malugo: A Peer-to-Peer Storage IEEE Annual Conference on Pervasive Computing
System, International Journal of Ad Hoc and and Communications Workshops, Orlando, Florida,
Ubiquitous Computing, Vol.5, No.4, 2010, pp.209- March, 2004, pp.104-108.
218. [22] Diego N. da Hora, Daniel F. Macedo, Jos Marcos
[8] Ibrahim Kamel, Zaher Al Aghbari and Ahmed Nogueira and Guy Pujolle, Optimizing Peer-to-Peer
Mustafa, Efficient Range Queries in Spatial Content Discovery over Wireless Mobile Ad Hoc
Databases over Peer-to-Peer Networks, International Networks, Proc. Ninth IFIP International Conference
 An Efficient Unstructured P2P Overlay for File Sharing Over MANETs Using Underlying Reactive Routing 13

on Mobile and Wireless Communications Networks Sharing in Mobile Applications, Proc. 2nd IEEE
(MWCN), Cork, Ireland, September, 2007, pp.86-90. Conference on Peer-to-Peer Computing (P2P 2002),
[23] Himabindu Pucha, Saumitra M. Das and Y. Charlie Linköping, Sweden, September, 2002, pp.71-83.
Hu, Ekta: An Efficient DHT Substrate for Distributed [33] Alexander Klemm, Christoph Lindemann and Oliver
Applications in Mobile Ad Hoc Networks, Proc. Sixth P. Waldhorst, A Special-Purpose Peer-to-Peer
IEEE Workshop on Mobile Computing Systems and File Sharing System for Mobile Ad Hoc Networks,
Applications (WMCSA 2004), Lake District National Proc. Workshop on Mobile Ad Hoc Networking and
Park, UK, December, 2004, pp.163-173. Computing (MADNET 2003), Sophia-Antipolis,
[24] Bin Tang, Zongheng Zhou, Anand Kashyap and France, March., 2003, pp.41-49.
Tzi-cker Chiueh, An Integrated Approach for P2P [34] Ahmet Duran and Chien-Chung, Mobile Ad Hoc P2P
File Sharing on Multi-hop Wireless Networks, Proc. File Sharing, Proc. Wireless Communications and
IEEE International Conference on Wireless and Networking Conference, Atlanta, GA, March, 2004,
Mobile Computing, Networking and Communication pp.114-119.
(WIMOB 05), Montreal, Canada, August, 2005, [35] Ahmed Abada, Li Cui, Changcheng Huang and
pp.268-274. Hsiao-Hwa Chen, A Novel Path Selection and
[25] Oliveira Rodolfo, Bernardo Lus and Pinto Paulo, Recovery Mechanism for MANETs P2P File Sharing
Flooding Techniques for Resource Discovery on High Applications, Proc. Wireless Communications and
Mobility MANETs, Proc. International Workshop on Networking Conference, Hong Kong, March, 2007,
Wireless Ad-hoc Networks (IWWAN 05), London, pp.3472-3477.
UK, May, 2005, pp.1451-1466. [36] M e i L i , Wa n g - C h i e n L e e a n d A n a n d
[26] Rüdiger Schollmeier, Ingo Gruber and Florian Sivasubramaniam, Efficient Peer-to-Peer Information
Niethammer, Protocol for Peer-to-Peer Networking in Sharing over Mobile Ad Hoc Networks, Proc. 2nd
Mobile Environment, Proc. IEEE 12th International Workshop on Emerging Applications for Wireless and
Conference on Computer Communications and Mobile Access (MobEA 2004), New York, May, 2004,
Networks (ICCCN), Dallas, TX, October, 2003, pp.1-6
pp.121-127. [37] Siddhartha K. Goel, Manish Singh, Dongyan
[27] Min Li, Enhong Chen and Phillip C-Y Sheu, A Xu and Baochun Li, Efficient Peer-to-Peer Data
Chord-Based Novel Mobile Peer-to-Peer File Sharing Dissemination in Mobile Ad-Hoc Networks, Proc.
Protocol, Proc. APWeb 2006, Harbin, China, January, International Conference On Parallel Processing
2006, pp.806-811 Workshops. Vancouver, Canada, August, 2002,
[28] Andrew Ka-Ho Leung and Yu-Kwong Kwok, On pp.152-158.
Topology Control of Wireless Peer-to-Peer File [38] Pan Hui, J’er’emie Leguay, Jon Crowcroft, James
Sharing Networks: Energy Efficiency, Fairness and Scotty, Timur Friedmanz and Vania Conan,
Incentive, Proc. 6th IEEE International Symposium Osmosis in Pocket Switched Networks, Proc. First
on a World of Wireless Mobile and Multimedia International Conference on Communications and
Networks, Taormina, Italy, June, 2005, pp.318-323. Networking in China, Beijing, China, October, 2007,
[29] Ren-Hung Hwang and Cheng-Chang Hoh, Cross- pp.1-6.
Layer Design of P2P File Sharing over Mobile Ad [39] Uichin Lee, Joon-Sang Park, Seung-Hoon Lee, Won
Hoc Networks, Telecommunication Systems, Vol.42, W. Ro, Giovanni Pau and Mario Gerla, Efficient
No.1-2, 2009, pp.47-61. Peer-to-Peer File Sharing Using Network Coding in
[30] Hasan Sozer, Metin Tekkalmaz and Ibrahim MANET, Journal of Communications and Networks,
Korpeoglu, A Peer-to-Peer File Search and Download Vol.10, No.4, 2008, pp.437-443.
Protocol for Wireless Ad Hoc Networks, Computer [40] Charles E. Perkins, Elizabeth M. Royer and Ian D.
Communications, Vol.32, No.1, 2009, pp.41-50. Chakeres, Ad hoc on-demand distance vector (AODV)
[31] M. Papadopouli and H. Schulzrinne, Effects of Power routing, July, 2003. RFC 3561.
Conservation, Wireless Coverage and Cooperation [41] Nadir Shah and Depei Qian, An Efficient Overlay for
on Data Dissemination among Mobile Devices, Proc. Unstructured P2P File Sharing over MANET Using
ACM International Symposium. On Mobile Ad Hoc Underlying Cluster-Based Routing, KSII Transactions
Networking & Computing (MobiHoc 2001), Long on Internet and Information Systems, Vol.4, No.5,
Beach, CA, October, 2001, pp.117-127. 2010, pp.799-818.
[32] Christoph Lindemann and Oliver P. Waldhorst, A [42] Jing Deng and Sergei Zuyev, On Search Sets of
Distributed Search Service for Peer-to-Peer File Expanding Ring Search in Wireless Networks, Ad
14 Journal of Internet Technology Volume 12 (2011) No.3

Hoc Networks, Vol.6, No.7, 2008, pp.1168-1181. Vol.23, No.3, 2005, pp.507-519.
[43] Ahmed Helmy, Saurabh Garg, Nitin Nahata [55] Tinghui Xu and Jie Wu, Quorum Based IP Address
and Priyatham Pamu, CARD: A Contact-Based Auto-configuration in Mobile Ad Hoc Networks,
Architecture for Resource Discovery in Ad Hoc Proc. 27th International Conference on Distributed
Network, Mobile Networks and Applications, Vol.10, Computing Systems Workshop, Toronto, Canada,
No.1-2, 2005, pp.99-113. 2007.
[44] Sandra M. Hedetniemi, Stephen T. Hedetniemi and [56] Yuan Sun and Elizabeth M. Belding-Royer, A Study
Arthur L. Liestman, A Survey of Gossiping and of Dynamic Addressing Techniques in Mobile Ad
Broadcasting in Communication Networks, Networks, Hoc Networks, Wireless Communications and Mobile
Vol.18, No.4, 1988, pp.319-349. Computing, Vol.4, No.3, 2004, pp.315-329.
[45] T. Clausen and P. Jacquet, Optimized link-state [57] ISI, 2009, ww.isi.edu/nsnam/ns
routing protocol, October, 2003. IETF RFC 3626.
[46] Hartmut Ritter, Rolf Winter and Jochen Schiller, Biographies
A Partition Detection System for Mobile Ad-Hoc
Networks, Proc. First IEEE Communications Society Nadir Shah is a PhD student of Sino-
Conference on Sensor and Ad Hoc Communications German Joint Software Institute at
and Networks (SECON 2004), Santa Clara, CA, Beihang University, Beijing, China.
October, 2004, pp.489-497. He earned MS in Computer Science
[47] Abdelouahid Derhab, Nadjib Badache and from International Islamic University,
Abdelmadjid Bouabdallah, A Partition Prediction Islamabad, Pakistan in 2007. He earned
Algorithm for Service Replication in Mobile Ad BS and MS in Computer Science from Peshawar University,
Hoc Networks, Proc. Second Annual Conference on Peshawar, Pakistan in 2002 and 2005 respectively. He was
Wireless On-demand Network Systems and Services, a Lecturer at Department of Computer Science, COMSATS
St. Moritz, Switzerland, January, 2005, pp.236-245. Institute of Information Technology, Abbottabad, Pakistan
[48] Karen H. Wang and Baochun Li, Efficient and between August 2007 and June 2008. His current research
Guaranteed Service Coverage in Partitionable interests include mobile ad hoc networks, peer-to-peer
Mobile Ad-hoc Networks, Proc. IEEE INFOCOM network, and delay/disruption tolerant networks. He has
2002, New York, June, 2002, pp.1089-1098. published about 13 papers in international conferences and
[49] Michaël Hauspie, Jean Carle and David Simplot, journals.
Partition Detection in Mobile Ad Hoc Networks
Using Multiple Disjoint Paths Set, Proc. of 2nd IFIP Depei Qian professor at State Key
Mediterranean Ad Hoc Networking Workshop (MED- Laboratory of Software Development
HOC-NET), Mahdia, Tunisia, June, 2003, pp.25-27 Environment, Beihang University,
[50] Bratislav Milic, Nikola Milanovic and Miroslaw Beijing, China. His current research
Malek, Prediction of Partitioning in Location- interests include high performance
Aware Mobile Ad Hoc Networks, Proc. 38th Annual computer architecture and implementation
Hawaii International Conference on System Sciences technology, distributed systems, and network performance
(HICSS’2005), Big Island, HI, January, 2005. measurement. He has published more than 100 papers.
[51] Charles E. Perkins, Jari T. Malinen, Ryuji Wakikawa,
Elizabeth M. Belding-Royer and Yuan Sun, Ip Rui Wang received the BS and MS
Address Autoconfiguration for Ad Hoc Networks, degrees from Xi’an Jiaotong University,
IETF Draft, November, 2001. Xi’an, China, in 2000 and 2003,
[52] M. Fazio, M. Villari and A. Puliafito, AIPAC: respectively, and the PhD degree from
Automatic IP Address Configuration in Mobile Ad Beihang University, Beijing, China, in
Hoc Networks, Computer Communications, Vol.29, 2009, all in computer science. Since 2009, he has been
No.8, 2006, pp.1189-1200. with the School of computer science and engineering at
[53] Abhishek Prakash Tayal and L. M. Patnaik, An the Beihang University, where he is currently an Assistant
Address Assignment for the Automatic Configuration Professor. His research interests are in the area of P2P
of Mobile Ad Hoc Networks, Personal and Ubiquitous networks and multimedia social network.
Computing, Vol.8, No.1, 2004, pp.47-54.
[54] K i l i a n We n i g e r, PA C M A N : P a s s i v e A u t o -
Configuration for Mobile Ad Hoc Networks, IEEE
Journal on Selected Areas in Communications,