Peer-to-peer networks and mobile ad hoc networks are emerging
distributed networks that share several similarities. Fundamental
among these similarities is the decentralized role of each
participating node to route messages on behalf of other nodes, and
thereby, collectively realizing communication between any pair of
nodes. Messages are routed on a topology graph that is determined by
the peer relationship between nodes. Although routing is fairly
straightforward when the topology graph is static, dynamic variations
in the peer relationship that often occur in peer-to-peer and mobile
ad hoc networks present challenges to routing.
In this thesis, we examine the interplay between routing messages and
network topology design in two classes of these networks --
unstructured peer-to-peer networks and sparsely-connected mobile ad
hoc networks.
In unstructured peer-to-peer networks, we add structure to overlay
topologies to support file sharing. Specifically, we investigate the
advantages of designing overlay topologies with small-world properties
to improve (a) search protocol performance and (b) network
utilization. We show, using simulation, that "small-world-like"
overlay topologies where every node has many close neighbors and few
random neighbors exhibit high chances of locating files close to the
source of file search query. This improvement in search protocol
performance is achieved while decreasing the traffic load on the links
in the underlying network.
In the context of sparsely-connected mobile ad hoc networks where
nodes provide connectivity via mobility, we present a protocol for
routing in space and time where the message forwarding decision
involves not only where to forward (space), but also when to forward
(time). We introduce space-time routing tables and develop methods to
compute these routing tables for those instances of ad hoc networks
where node mobility is predictable over either a finite horizon or
indefinitely due to periodicity in node motion. Furthermore, when the
node mobility is unpredictable, we investigate several forwarding
heuristics to address the scarcity in transmission opportunities in
these sparsely-connected ad hoc networks. In particular, we present
the advantages of fragmenting messages and augmenting them with
erasure codes to improve the end-to-end message delivery performance.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/7219 |
| Date | 19 July 2005 |
| Creators | Merugu, Shashidhar |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Language | en_US |
| Detected Language | English |
| Type | Dissertation |
| Format | 862333 bytes, application/pdf |
Page generated in 0.0021 seconds