Year

2012

Degree Name

Doctor of Philosophy

Department

School of Electrical, Computer and Telecommunications Engineering

Abstract

Delay Tolerant Networks (DTNs) are characterized by large delays, frequent dis- ruptions and lack of contemporaneous paths between nodes. Moreover, nodes may have limited computational power, storage, and battery capacity. Despite these challenges, DTNs have found applications in areas such as animal tracking, surveillance and facilitating education in remote areas. In these applications, a critical problem is routing or data dissemination. Indeed, any routing protocols must aim to transmit data efficiently and maximize data delivery. The chal- lenge, however, is that nodes are only connected intermittently, and do not have a contemporaneous path. Moreover, any established path may not remain valid after a transmission, and nodes may experience large delays before encounter- ing one another. As a result, existing routing protocols cannot be retrofitted to work in DTNs.

To date, a primary solution for routing in DTNs is epidemic-based routing protocols because of their simplicity, low delays and little to no reliance on spe- cific nodes. A key observation of past research on epidemic routing protocols is that they are not evaluated on a unified framework. Specifically, no work has compared the performance of epidemic routing protocols using both the Random Way Point (RWP) model and trace files. Henceforth, this thesis has conducted a comprehensive study that employs both RWP and trace files. In particular, this thesis is the first to compare the performance of epidemic-based routing protocols using a custom-built simulator that moves nodes according to a trace-file and the RWP model. Moreover, it compares these protocols using the same set of parameters; e.g., node numbers, load and buffer space. The extensive simulation studies reveal the following limitations: high buffer occu- pancy level, premature discard of bundles, inefficient use of immunity tables to purge redundant bundles, low delivery ratio at high loads, and poor adap- tivity to changing network parameters. This thesis also outlines three novel enhancements to address the limitations of epidemic-based protocols. First, it introduces a mechanism that adapts the Time to Live (TTL) of bundles dy- namically according to a node’s encounter interval. The intuition here is that bundles should be buffered according to the interval between two encounters. That is, when nodes experience long inter-contact intervals, bundles will have a large TTL value, whilst short intervals result in a small TTL value. Simu- lation results show that epidemic with dynamic TTL improves delivery ratio by more than 20%. The second enhancement combines Encounter Count (EC) with TTL to reduce buffer occupancy level and increase bundle delivery ratio. The resulting combination is able to reduce buffer occupancy level by 40%. More importantly, it dramatically improves the delivery ratio by at least 40% at high loads. The last enhancement uses immunity tables to carry cumulative acknowledgments. This has the effect of facilitating buffer management, and more importantly, allows a node to delete multiple bundles upon receiving one immunity table. This is an improvement over past approaches as nodes need to receive N immunity tables in order to delete N bundles. Extensive experi- ments using both the RWP model and trace-file confirm the superiority of these enhancements over existing epidemic routing protocols.

Epidemic-based routing protocols can also be used for transmitting multicast bundles. This thesis presents three key findings concerning the delivery ratio of epidemic-based multicast protocols. Specifically, (i) subscriber nodes must act as relays. Simulation results show that bundle delivery ratio is only 57% as com- pared to 100% when they act as relays, (ii) the use of anti-entropy contributes to a rise in delivery ratio to 100%, which is 57% higher than when nodes do not use anti-entropy, and (iii) higher number of relay nodes improve delivery ratio. From extensive simulation studies, it can be seen that when the number of relay nodes increases from 10 to 30, the delivery ratio increased from 43% to 98%. This thesis also presents new findings related to multicast group sizes and delivery ratios. The presented results show that the impact of multicast group size on bundle delivery ratio is dependent upon whether subscribers forward bundles - i.e., whether they are relays or sinks. Specifically, when subscribers work as sinks, epidemic with Time-to-Live (TTL), epidemic with immunity, epidemic with Encounter Count (EC) threshold, and epidemic with cumulative immunity, have poor bundle delivery ratio. On the other hand, for epidemic with immunity, it has a low bundle delivery ratio when subscribers act as relays. In regards to buffer occupancy level in multicast scenarios, simulation results show that multicast group size, anti-entropy session and subscribers forwarding policies have a significant impact on the buffer occupancy level of relay nodes. In particular, all protocols experience high buffer occupancy level. To address this problem, each bundle is assigned an EC quota. In other words, EC quota bounds the number of times in which a bundle is exchanged by relay nodes.

Lastly, this thesis focuses on routing requests and replies in DTN based infor- mation retrieval systems. Specifically, this thesis presents the first data centric information retrieval system called Distributed Data-Centric Information Re- trieval (DDC-IR) system. Nodes only process a query if its similarity value matches that of the query. This ensures only nodes that have a high proba- bility of resolving a query process and transmit the query. Experiment results show that DDC-IR is able to resolve 50% more queries and has 80% lower buffer occupancy level than prior work. More importantly, DDC-IR is able to support four query types: complex, unique, aggregated and continuous. This is a sig- nificant contribution over past approaches that only targeted one query type. Apart from that, DDC-IR supports a novel caching policy, in which nodes cache popular queries to improve the retrieval success ratio. This thesis also investi- gated the influence of the number of sub-queries and the number of querying nodes on query resolution time. When the number of querying nodes increases, the retrieval success rate reduces from 100% to 20%. When the number of sub- queries in a complex query increases from five to nine, DDC-IR requires 50% more time to resolve queries. In comparison, previous IR systems are unable to resolve any queries.

FoR codes (2008)

0805 DISTRIBUTED COMPUTING

Share

COinS
 

Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.