The 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.
Read more about this topic: Ex OR (wireless Network Protocol)