Researchers are creating mobile networks that can sustain communications even in the face of broken links and long delays.
The quest for such disruption-tolerant networks, or DTNs, is being driven by military, scientific and emergency-response wireless networks, which typically lack the connectivity, stability and predictability of conventional wired networks. Instead, researchers say, the hallmarks of a DTN are the very problems that quickly bring a conventional wireless network to its knees: frequent and unpredictable disconnects, changing nearby nodes and very long delays. The trade-off: it takes a lot longer to send and receive data over a DTN.
You can think of it as the “it’s better than nothing” approach to networking.
Breaking through breakdowns
Researchers at BBN Technologies, of Cambridge, Mass., have begun the second phase of a DTN project, funded by $8.7 million from the Department of Defense’s Defense Advanced Research Projects Agency (DARPA). Earlier this year, the researchers simulated a 20-node DTN. With each link available just 20% of the time, the network was able to deliver 100% of the packets transmitted.
“Using traditional [network] routing in the same scenario, and depending on the nature of the outages, there would be a very, very low percentage delivered, or none delivered,” says Stephen Polit, project manager for BBN’s DTN research, dubbed SPINDLE.
“Conventional routing protocols assume there is an end-to-end path, and this path is eventually [and fairly quickly] stable,” says Rajesh Krishnan, senior scientist with BBN’s Internetwork Research Group and a specialist in DTN. “Based on this, you compute routes and set your [router] forwarding tables.”
But all that breaks down when the network ruptures because of repeated disconnections and long delays. BBN has developed a network protocol and code that moves information from node to node as connections become available, and can hold information in persistent storage until a connection is available.
The BBN team is now pulling together a full reference implementation of its DTN routing protocol, called Bundle, and a hardware and software platform incorporating this implementation, for use by selected Department of Defense partners. Phase 2 also includes defining a set of APIs so that third parties can substitute their own code for some parts of the DTN system, and creating code that will let the DTN software elements run over different types of underlying network transports, such as Bluetooth, 802.11 WLAN and Ethernet. The goal is to have a working demonstration network by late 2007.
But you don’t have to wait that long to see a DTN in operation. Just take the bus at the University of Massachusetts Amherst.
DieselNet created by the university's Privacy, Internetworking, Security and Mobile Systems (PRISMS) Lab, consists of off-the-shelf single-board computers, GPS receivers and radios mounted in 40 UMass Transit System buses.
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 network destination of a message, that message is handed off to the passing node in the seconds they’re close enough together for the Wi-Fi connection. At some point, the message is handed to a node attached to the wired Internet.
“This is harder than normal routing,” says Brian Levine, associate professor in the Department of Computer Science, and one of PRISMS' DieselNet researchers. “You can’t query the net to determine what paths are available. Because there are none.”
At the start of DieselNet, in spring 2006, the median data transferred between buses was 1MB in 10 seconds, which was less than researchers had hoped for. But this fall, it’s been running about half that amount in 8 seconds, and Levine and colleague Mark Corner, an assistant professor, admit they haven’t figured out why.
They’ve been experimenting with a technique to improve throughput: stationary, stand-alone wireless nodes, called "throw boxes.” They’re powered by a combination of solar panels and batteries, and sit on buildings along the bus routes. They act rather like a transfer point in a subway: a bus throws a packet to the box, where it waits until another bus comes along that can carry the packet further toward its destination.
Wireless laptops on the buses can access cached information, such as the bus route and schedule, which almost never changes. Other information, such as news and weather update, changes more frequently, and DieselNet periodically broadcasts such information. The next step, says Corner, is to let users get information from the Web. “It will be a very different [user] experience, because delay is the penalty you pay [in a DTN],” Corner says. “You have to deliver the information before the people get off the bus.”
Information access and delivery is where things get really complicated in disrupted networks. And the SPINDLE team is working on this problem at several levels.
In conventional networks, if you want to search for information, you type into your Web browser the URL of your favorite search engine. Then an infrastructure, including the Domain Name Service and routers with up-to-the-second information about other routers and their IP addresses, ensures that your browser blossoms in seconds at most with the browser home page.
But in a disrupted network, that infrastructure either breaks down or is not available. To compensate, the BBN researchers are combining the new routing protocol with a technique called late binding. In a DTN, messages can be launched from a source node even though the final destination IP address can’t be known due to disruptions of name servers or routers. In effect, the message has blank spaces for the naming and address information. “The message makes its way through the network, and the blanks get filled in,” says BBN’s Krishnan. Eventually, the destination IP address binding takes place.
New caching model
At the same time, the BBN researchers are studying a new caching model for DTNs, to keep track of cached content and respond to information requests even though the conventional search-and-access capabilities are unavailable due to disruptions. Krishnan and Polit envision a DTN in which information requests (who wants to know what) move through the network and meet information advertisements (who knows what).
A recent presentation uses the example of a Boy Scout troop hiking through the woods, led by their scoutmaster, Chuck, who has a wireless PDA with maps of his planned route. But he still gets lost, and uses his PDA to request new maps from Google. If there’s no WAN connection, the request can’t go through. With one version of a DTN, the request goes to the wireless PDAs, iPods and Sony PlayStation Personals carried by the scouts, but can’t go any further because they don’t have a WAN connection either.
But with the kind of caching system described above, Chuck’s request goes to these same wireless clients, which then check to see if they can satisfy the request from their caches. Scout Billy has maps of the area stored in the browser cache of his PlayStation Personal, which returns the map to Chuck’s PDA.
“With a DTN, over space and time, as long as there is a path, you can move information forward and eventually you can communicate,” Krishnan says.