In Manhattan, sturdy computer networks are taken for granted. In parts of the world where transmission opportunities are intermittent at best, Xiaolan “Ellen” Zhang, Ph.D., is helping to increase connectivity.
An assistant professor of computer and information science, Zhang finds ways to improve disruption-tolerant networks (DTNs). As their name suggests, DTNs are mobile networks that can sustain communications in the face of broken links and long delays.
DTNs have grown increasingly important as wireless networks are being relied upon in challenging environments, including rural areas in developing countries or disaster sites where relief teams need connectivity.
“In rural India and China, there is not a lot of wireless network coverage, but that doesn’t mean there isn’t a desire for connectivity,” Zhang said. “It’s very expensive to put down wire in a remote village. Still, there are efforts in these countries to get connectivity everywhere.”
A successful DTN, for instance, can deliver information from a sender to a receiver even when each of the network’s component parts—called “nodes”—are connected only 20 percent of the time.
Typically, networks establish a route that information will travel before the actual data is sent. This may not be possible in rural areas, due to the limits of wireless radio range, scarcity of nodes or inconsistent sources of power, among other factors.
In these challenging environments, when instantaneous end-to-end paths are impossible to establish, DTNs take a “store and forward” approach, Zhang said. In this way, nodes determine the path that information will travel based on its intended destination. Data is moved from node to node thanks to mobile Wi-Fi connections mounted on motorcycles, buses and even oxcarts.
For instance, as two buses near each other, their DTN nodes query each other to find out what other nodes each sees most frequently. If one of those other nodes is related to the final destination of a message, that message is handed off to the passing node while the buses are still close enough for the Wi-Fi connection. At some point, the message is eventually handed to the final destination.
Zhang pointed out an example from India, where “they get very creative in terms of how to provide Internet access,” she said.
In that country, buses and motorcycles traveling between cities and rural areas serve as relays for information. Users in rural communities conduct Web searches through non-real-time browsers. When a motorcycle carrying a node drives by, it collects the search queries and takes them to a wired server in a city, which then conducts the searches. The results are sent back to the users in a compressed form—again by buses and motorcycles—the next time they visit the rural communities.
As they are used more and more often, disruption-tolerant networks present increased challenges. Zhang is studying several of them, including:
• performance modeling of “epidemic-style routing,” by which many copies of a message are injected into a network for increased probability of delivery.
• the benefits of network coding, a technique where, instead of simply relaying pieces of information, known as “packets,” nodes will take several packets and combine them for transmission.
• mobility trace modeling, a process that analyzes the paths taken by devices that carry mobile nodes and then uses that data to create models for study.
Zhang’s latest project, which she worked on with colleagues from Suffolk University in Boston and NEC Laboratories in Princeton, focused on the “Impact of Source Counter on DTN Routing Under Resource Constraints.”
When transmission bandwidth is scarce, a key issue is optimizing performance by scheduling the transmission of packets most efficiently, she said.
“For example, I want to send information as soon as possible, even though it may take a long time to reach its destination. But I also want it to reach that destination in the shortest amount of time,” Zhang said. “We were looking for a balance between how much information can be sent and how much delay it will experience.”
In this project, Zhang focused on spray-and-wait protocols, by which a source node specifies the maximum number of copies of a packet that can be placed in the network. That protocol is composed of two phases: the spray phase and the wait phase. When a new message is created, a number is attached to that message indicating the greatest number of copies that can be distributed.
During the spray phase, the sender of the message is responsible for “spraying” one copy to the predetermined number of relays in the system. When each relay receives a copy, it enters the wait phase, where the relay simply holds that particular message until a proper destination is encountered.
Using various mathematical models and simulations, Zhang found that there is an optimal number of copies that can be distributed to achieve the minimum packet delay, depending on the number of nodes in the network.
“The more nodes in the network, the lower the delay will be because there are more nodes to help you out,” Zhang said. “The other parameter is how often two nodes encounter each other.”
There is more to explore. Zhang plans to address the challenge of modeling more complex transmission-scheduling schemes.
“There are many open questions,” she said. “Eventually, a DTN will be formed that we can fall back on if disaster strikes.”