ExOR (wireless network protocol)

Extremely Opportunistic Routing (ExOR) is a combination of routing protocol and media access control for a wireless ad hoc network, invented by Sanjit Biswas and Robert Morris of the MIT Artificial Intelligence Laboratory, and described in a 2005 paper. ^[1] A very similar opportunistic routing scheme was also independently proposed by Zhenzhen Ye and Yingbo Hua from University of California, Riverside and presented in a paper in 2005.^[2] Previously open source,^[3] ExOR was available in 2005 but is no longer obtainable. The broadcast and retransmission strategies used by the algorithm were already described in the literature.^{[4][5][6][7][8][9]} ExOR is valuable because it can operate available digital radios to use some previously impractical algorithmic optimizations.

History

The algorithm is designed to convey packets of the Internet Protocol, so that it enables the maximum number of other services. At the time of invention, digital radios had widely replaced wireline internet services for portable devices. Specialized integrated circuits were widely available at low costs.

MIT at that time (2005) was involved with the One Laptop per Child project, an attempt to make an inexpensive low-power computer to help educate impoverished children. The advantages were thought to be reduced costs for digital copies of books and consumables like paper, with possible pedagogic improvements from the interactivity and flexibility. One of the crucial features of the laptop was to be a wireless ad hoc network that would permit the laptops to cooperate to provide more resources than an individual computer could afford. A practical but superior network algorithm would directly help educate more children by reducing the cost and power needed by the laptop. A wireless ad hoc network would cost less and use less power if it used standard radios (i.e. with integrated circuits for 802.11) and transferred more data over larger distances, with fewer intermediate radios.

This protocol was prototyped on RoofNet, and many authorities^[who?] believe it is the media access protocol deployed by Meraki to wire San Francisco.

Algorithm

The starting radio, the source, broadcasts a batch of packets. As timers in intermediate radios expire, radios further from the destination retransmit the packets that no closer radio has yet retransmitted.

Most of the complexity is to support this basic scheme. The timers in intermediate radios are set to an estimate of the transmission time that closer radios will need in order to transmit packets. The estimate is calculated based on the number of packets in the batch, and the probabilities of a correct transmission from each intermediate radio.

ExOR uses a conventional routing protocol "RRTc" to collect information about the probability of a successful transmission between each pair of digital radios in the network.

The authors were concerned that retransmitting packets could use up too much of the available radio time. ExOR therefore tries to reduce retransmissions of packets to the minimum possible. This accounts for ExOR's high efficiency.

First, from the routing information, the sending radio constructs a list of radios that might be able to forward data from the sending radio to the destination. The radios' numbers are placed in a list sorted by distance to the destination, from closest to furthest. The destination radio is at the head of the list. Also, the source radio starts a list of the packets in the batch in order to measure packets' progress. This "batch map" is an array of radio numbers, one per packet. Each radio number is the radio that transmitted that packet, and was closest to the destination radio. Each data packet has the list of radios, and packets placed in the front. The list saves space in each packet by using radio numbers rather than IP addresses. Then, the sending radio broadcasts the first batch of data packets. It starts a timer. Radios that receive a packet but are not in the list in the packet ignore the data packets. These radios throw away the packets as soon as the packets are received. Radios that are in the packet's list of radios save the data packets that they receive. They also update their batch map. When a radio times out, it transmits the packets that no radio closer to the destination has retransmitted. These packets include the radio's best available information about the progress of the packets in the batch (i.e. its batch map). In particular, each packet's batch map contains the retransmitter's radio number for each packet that it retransmits. When a radio receives a packet sent from a radio that is closer to the destination, it erases its own copy of that packet. There's no need for it to retransmit that packet. However, it also updates its batch map about the progress of the packets in the batch. In this way, the information about the progress of the packets flows backward toward the source as radios farther from the destination update their batch maps by eavesdropping on retransmissions.

Since the retransmissions closer to the source radio occur later, the packet progress information flows back to the source radio, even though no acknowledge packets are ever transmitted. At the end, there are usually a few packets that didn't go anywhere. These are sent by the most reliable route, without gambling on unreliable routes.

ExOR is more efficient with large blocks of data. These give more chances for a batch to find alternative routes. However, the batchmaps get larger, too. So, blocks of data more than 100,000 bytes are broken into groups of data packets called batches. Smaller messages are just sent by the most reliable route.

Since the major internet protocol TCP sends a stream of data, ExOR uses local proxy data servers to accumulate blocks of data.

Advantages and disadvantages

Each packet is retransmitted a minimal number of times, and covers the longest possible distance on each transmission. Some time is wasted by having the receiver broadcast packet information, but this is far less than the normal routing schemes, which can retransmit when an acknowledge message is lost.

There are no acknowledge packets, and no collisions with them. This saves radio time.

The authors say that the protocol is roughly twice as efficient as normal routing protocols with fixed "optimal" routing. (See "testing", below for methods used to determine this).

The authors say that the variation in delivery times is 1/4 of other ad hoc networks, and ascribe this to the algorithm's use of best available delivery times.

The authors arranged the test so that the protocol accumulates large blocks of data for transmission. The data shows a trade-off between the speed of the network's response and the efficiency of the radio system.

Response time in some games might be affected by larger amounts of buffering in high efficiency networks.

Testing

ExOR's efficiency estimates are based on a real implementation with a Linux routing toolkit called click. Experimental versions of the software were both simulated and installed on a rooftop network called "RoofNet" in Cambridge, Massachusetts. This data was compared to published data for a similar network.^[10]

See also

• DSR, AODV and OLSR are leading conventional public-domain solutions to the same problem. DSDV was the original routing system used by RoofNet.
• Hazy Sighted Link State Routing Protocol (HSLS) provides a routing protocol that may complement the media access and transport layers provided by ExOR.
• The list of ad hoc routing protocols describes more protocols.
• A tutorial for ExOR
• Backpressure routing

References

1. ExOR: Opportunistic Multi-Hop Routing for Wireless Networks Sanjit Biswas, Robert Morris, Presented at SIGCOMM '05, 2005, Copyright ACM, Philadelphia, Penn. 2005, ACM No. 1-59593-009-4/05/0008
2. On link layer policies of data forwarding over wireless relays Zhenzhen Ye, Yingbo Hua, Presented at IEEE MILCOM '05, 2005, Copyright IEEE, Atlantic City, NJ, October 2005
3. [1]^{[permanent dead link]}
4. "Exploiting Distributed Spatial Diversity in Networks," J. N. Laneman, G. Wornell; Analyzes some information-theoretic cooperative diversity schemes, but the radios use special techniques to share spectrum. ExOR adapts the time-slot scheme to a longer time-scale that can be implemented in software using commodity radios.
5. "Selection Diversity Forwarding in a Multihop Packet Radio Network with Fading Channels and Capture," P. Larsson, SIGMOBIL Mob. Comm. Rev. 5(4):47-564, 2001
6. "OAR, Opportunistic Media Access for Multirate Networks," B. Sadeghi, V. Kanodia, A. Sabharwal, and E. Knightly; Proceedings of ACM Mobicom 2002, Sep. 2002
7. "Exploiting Path Diversity in the Link Layering Wireless Ad-Hoc Networks," Proc. of the 6th IEEE WoWMoM Symposium, June 2005
8. "MAC Layer Anycasting in Wireless Networks," R. Roy Chowdhury and N. Vaidya, Second Workshop on Hot Topics in Networks (HotNets II), November 2003
9. "Geographic Random Forwarding (GeRaf)," M. Zorzi, R. Rao, IEEE Transactions on Mobile Computing, 2(4), October 2003
10. "Link Level Measurements from an 802.11b Mesh Network," D. Aguayo, J. Bicket, S. Biswas, G. Judd, and R. Morris; ACM SIGCOMM 2004, August 2004