ExOR (wireless network protocol)
Encyclopedia
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.
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.
Previously open source,
, 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. ExOR is valuable because it can operate available digital radios to use some previously impractical algorithmic optimizations.
, 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 circuit
s for 802.11) and transferred more data over larger distances, with fewer intermediate radios.
This protocol was prototyped on RoofNet
, and many authorities believe it is the media access protocol deployed by Meraki
to wire San Francisco.
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 byte
s 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.
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.
routing toolkit called click
. Experimental versions of the software were both simulated and installed on a rooftop network called "RoofNet" in Cambridge, Mass. This data was compared to published data for a similar network.
Routing protocol
A routing protocol is a protocol that specifies how routers communicate with each other, disseminating information that enables them to select routes between any two nodes on a computer network, the choice of the route being done by routing algorithms. Each router has a priori knowledge only of...
and media access control
Media Access Control
The media access control data communication protocol sub-layer, also known as the medium access control, is a sublayer of the data link layer specified in the seven-layer OSI model , and in the four-layer TCP/IP model...
for a wireless ad-hoc network
Wireless ad-hoc network
A wireless ad-hoc network is a decentralized type of wireless network. The network is ad hoc because it does not rely on a preexisting infrastructure, such as routers in wired networks or access points in managed wireless networks...
, invented by Sanjit Biswas
Sanjit Biswas
Sanjit Biswas is co-founder of Meraki, Inc. He and John Bicket started the company based on their work on Roofnet project as part of at MIT.Biswas has a bachelor's degree from Stanford and a master's degree from MIT....
and Robert Morris
Robert Tappan Morris
Robert Tappan Morris, , is an American computer scientist, best known for creating the Morris Worm in 1988, considered the first computer worm on the Internet - and subsequently becoming the first person convicted under the Computer Fraud and Abuse Act.He went on to co-found the online store...
of the MIT Artificial Intelligence Laboratory, and described in a 2005 Paper.
A very similar opportunistic routing scheme was also independently proposed by Zhenzhen Ye and Yingbo Hua from University of California, Riverside
University of California, Riverside
The University of California, Riverside, commonly known as UCR or UC Riverside, is a public research university and one of the ten general campuses of the University of California system. UCR is consistently ranked as one of the most ethnically and economically diverse universities in the United...
and presented in a paper in 2005.
Previously open source,
, 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. 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 ProtocolInternet Protocol
The Internet Protocol is the principal communications protocol used for relaying datagrams across an internetwork using the Internet Protocol Suite...
, so that it enables the maximum number of other services. At the time of invention, digital radios
WIFI
WIFI is a radio station broadcasting a brokered format. Licensed to Florence, New Jersey, USA, the station is currently operated by Florence Broadcasting Partners, LLC.This station was previously owned by Real Life Broadcasting...
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
Wireless ad-hoc network
A wireless ad-hoc network is a decentralized type of wireless network. The network is ad hoc because it does not rely on a preexisting infrastructure, such as routers in wired networks or access points in managed wireless networks...
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 circuit
Integrated circuit
An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...
s for 802.11) and transferred more data over larger distances, with fewer intermediate radios.
This protocol was prototyped on RoofNet
Roofnet
Roofnet is an experimental 802.11b/g mesh network currently under development at the Computer Science and Artificial Intelligence Laboratory of the Massachusetts Institute of Technology...
, and many authorities believe it is the media access protocol deployed by Meraki
Meraki
Meraki is a cloud networking company that provides hardware and software for building large scale wired and wireless networks. These networks are used by businesses, schools, and other organizations that need wireless access points, multi-site wired networks, or both. It uses a centralized...
to wire San Francisco.
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 byte
Byte
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
s 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 LinuxLinux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
routing toolkit called click
Click
-Computing:* Point-and-click, a gesture made with a computer input device such as a mouse* Apache Click, a web application framework* Klik, a computer programming method* Clik!, a disk drive-Film and television:...
. Experimental versions of the software were both simulated and installed on a rooftop network called "RoofNet" in Cambridge, Mass. This data was compared to published data for a similar network.
See also
- DSRDynamic Source Routing'Dynamic Source Routing' is a routing protocol for wireless mesh networks. It is similar to AODV in that it forms a route on-demand when a transmitting computer requests one...
, AODV and OLSR are leading conventional public-domain solutions to the same problem. DSDV was the original routing system used by RoofNet. - HSLSHazy Sighted Link State Routing ProtocolThe Hazy-Sighted Link State Routing Protocol is a wireless mesh network routing protocol being developed by the CUWiN Foundation. This is an algorithm allowing computers communicating via digital radio in a mesh network to forward messages to computers that are out of reach of direct radio contact...
provides a routing protocol that may complement the media access and transport layers provided by ExOR. - The Ad hoc routing protocol listAd hoc routing protocol listAn ad-hoc routing protocol is a convention, or standard, that controls how nodes decide which way to route packets between computing devices in a mobile ad hoc network ....
describes more protocols. - a tutorial for ExOR
- Backpressure RoutingBackpressure RoutingThis article describes backpressure routing forqueueing networks. It shows how the algorithm is derived and how its optimality is establishedusing concepts of Lyapunov drift....