Leveraging structure for communication in human-centric DTNs

Nelson, Samuel C., V

Permalink

https://hdl.handle.net/2142/24285 Copy

Description

Title

Leveraging structure for communication in human-centric DTNs

Author(s)

Nelson, Samuel C., V

Issue Date

2011-05-25T15:01:41Z

Director of Research (if dissertation) or Advisor (if thesis)

Kravets, Robin H.

Doctoral Committee Chair(s)

Kravets, Robin H.

Committee Member(s)

• Abdelzaher, Tarek F.
• Caesar, Matthew C.
• Hu, Yih-Chun
• Ramanathan, Ram

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• delay/disruption tolerant network (DTN)
• Human-Centric
• Communication
• Routing
• Manycast
• Anycast
• Delay Tolerant Networks
• Disruption Tolerant Networks
• Mobility Model
• ad hoc networks

Abstract

Current delay- and disruption-tolerant networks are human-centric in nature, in that mobility and communication tend to follow human-based characteristics, such as certain high-level mobility patterns, the development of groups, clustering, and variance in popularity. These networks do not rely on infrastructure and hence are critical to supporting many environments including emergency response, pocket-switched, vehicular, military, and community networks. Unfortunately, there is currently a lack of communication protocols that work well in these environments, where resources can be heavily constrained and malicious nodes may be present. Therefore, the goal of our work is to allow effective, efficient, and robust communication in human-centric DTNs, which we show possible by taking advantage of inherent structure found in these networks. To accomplish this goal, and progress the state-of-the-art, we identify two categories of research that must be enhanced: (1) supporting tools and (2) routing protocols. Supporting tools are used for the understanding, development, and support of routing protocols, and we consider two components for this category. First, in order to design routing protocols for human-centric DTNs, it is critical to properly understand the environment and challenges posed by these networks. Therefore we develop a high-level mobility model for a typical human-centric DTN: a disaster recovery network. This model integrates the concept of different classes of nodes, referred to as roles, reacting differently to external events. This highly-parametrized model allows exploration of many different graph-theoretic properties of human-centric DTNs and provides a better understanding of how DTN routing protocols can best transmit data throughout the network. Furthermore, it acts as a useful mobility tool for protocol simulation. Second, in order to utilize the potential of group-based communication, we develop a local and robust group-management protocol, called MembersOnly. This protocol allows nodes to quickly and accurately transmit group membership information throughout the network, and is robust to malicious nodes attempting to disrupt the process. Through analysis and simulation, it is shown that MembersOnly can withstand multiple types of attacks, with only very limited periods of vulnerability. The second category, routing protocols, directly allows applications to transmit data throughout the network. Here, we consider three components. Like most networks, unicast is a fundamental and necessary form of communication for human-centric DTNs. Therefore, we develop a highly efficient and effective unicast protocol, called Encounter-based Routing (EBR). EBR is an intentionally resource-friendly protocol that excels in the resource-constrained environments of human-centric DTNs through intelligent replication based on inherent network structure. We show that EBR can achieve up to a 40% improvement in message delivery over current state-of-the-art, while achieving up to a 145% increase in goodput. Next, due to structure inherent in many human-centric DTNs, group-based communication can be a natural and powerful form of communication. Therefore, to support group-based communication, we present an overarching, protocol-independent way to enhance current unicast protocols, giving them the ability to perform anycast. This enhancement can be done in a thin shim beneath the routing layer, allowing the unicast protocols to run unmodified. Through evaluation, we show how different parameters and network conditions affect anycast performance, and how these differ from unicast. Finally, to allow highly flexible group-based communication, we explore manycast in DTNs. First, we thoroughly analyze the difficulty of varying manycast requests, deepening our understanding of how replication should change as the request becomes more or less difficult. Second, we show via simulation that an effective manycast protocol must dynamically change its replication strategy on a per-message basis. Third, we present a manycast metaprotocol, which dynamically selects an appropriate low-level protocol based on the current request and network conditions.

Graduation Semester

2011-05

Permalink

http://hdl.handle.net/2142/24285

Copyright and License Information

Copyright 2011 Samuel C. Nelson

Owning Collections