ExOR (wireless network protocol)

Last updated

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.

Contents

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

Related Research Articles

The Transmission Control Protocol (TCP) is one of the main protocols of the Internet protocol suite. It originated in the initial network implementation in which it complemented the Internet Protocol (IP). Therefore, the entire suite is commonly referred to as TCP/IP. TCP provides reliable, ordered, and error-checked delivery of a stream of octets (bytes) between applications running on hosts communicating via an IP network. Major internet applications such as the World Wide Web, email, remote administration, and file transfer rely on TCP, which is part of the Transport Layer of the TCP/IP suite. SSL/TLS often runs on top of TCP.

Automatic repeat request (ARQ), also known as automatic repeat query, is an error-control method for data transmission that uses acknowledgements and timeouts to achieve reliable data transmission over an unreliable communication channel. ARQ is appropriate if the communication channel has varying or unknown capacity. If the sender does not receive an acknowledgment before the timeout, it re-transmits the message until it receives an acknowledgment or exceeds a predefined number of retransmissions.

Link-state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the others being distance-vector routing protocols. Examples of link-state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS).

<span class="mw-page-title-main">Wireless mesh network</span> Radio nodes organized in a mesh topology

A wireless mesh network (WMN) is a communications network made up of radio nodes organized in a mesh topology. It can also be a form of wireless ad hoc network.

<span class="mw-page-title-main">Optimized Link State Routing Protocol</span> IP routing protocol optimized for mobile ad hoc networks

The Optimized Link State Routing Protocol (OLSR) is an IP routing protocol optimized for mobile ad hoc networks, which can also be used on other wireless ad hoc networks. OLSR is a proactive link-state routing protocol, which uses hello and topology control (TC) messages to discover and then disseminate link state information throughout the mobile ad hoc network. Individual nodes use this topology information to compute next hop destinations for all nodes in the network using shortest hop forwarding paths.

Transmission Control Protocol (TCP) uses a congestion control algorithm that includes various aspects of an additive increase/multiplicative decrease (AIMD) scheme, along with other schemes including slow start and congestion window (CWND), to achieve congestion avoidance. The TCP congestion-avoidance algorithm is the primary basis for congestion control in the Internet. Per the end-to-end principle, congestion control is largely a function of internet hosts, not the network itself. There are several variations and versions of the algorithm implemented in protocol stacks of operating systems of computers that connect to the Internet.

Retransmission, essentially identical with automatic repeat request (ARQ), is the resending of packets which have been either damaged or lost. Retransmission is one of the basic mechanisms used by protocols operating over a packet switched computer network to provide reliable communication.

Delay-tolerant networking (DTN) is an approach to computer network architecture that seeks to address the technical issues in heterogeneous networks that may lack continuous network connectivity. Examples of such networks are those operating in mobile or extreme terrestrial environments, or planned networks in space.

Packet loss occurs when one or more packets of data travelling across a computer network fail to reach their destination. Packet loss is either caused by errors in data transmission, typically across wireless networks, or network congestion. Packet loss is measured as a percentage of packets lost with respect to packets sent.

Roofnet was an experimental 802.11b/g mesh network developed by the Computer Science and Artificial Intelligence Laboratory at the Massachusetts Institute of Technology (MIT). Research included link-level measurements of 802.11, finding high-throughput routes in the face of lossy links, link adaptation, and developing new protocols which take advantage of radio’s unique properties (ExOR). The software developed for this project is available free as open source.

A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers or wireless access points. Instead, each node participates in routing by forwarding data for other nodes. The determination of which nodes forward data is made dynamically on the basis of network connectivity and the routing algorithm in use.

<span class="mw-page-title-main">B.A.T.M.A.N.</span> Routing protocol for multi-hop mobile ad hoc networks

The Better Approach to Mobile Ad-hoc Networking (B.A.T.M.A.N.) is a routing protocol for multi-hop mobile ad hoc networks which is under development by the German "Freifunk" community and intended to replace the Optimized Link State Routing Protocol (OLSR).

Geographic routing is a routing principle that relies on geographic position information. It is mainly proposed for wireless networks and based on the idea that the source sends a message to the geographic location of the destination instead of using the network address. In the area of packet radio networks, the idea of using position information for routing was first proposed in the 1980s for interconnection networks. Geographic routing requires that each node can determine its own location and that the source is aware of the location of the destination. With this information, a message can be routed to the destination without knowledge of the network topology or a prior route discovery.

The Wireless Routing Protocol (WRP) is a proactive unicast routing protocol for mobile ad hoc networks (MANETs).

Karn's algorithm addresses the problem of getting accurate estimates of the round-trip time for messages when using the Transmission Control Protocol (TCP) in computer networking. The algorithm, also sometimes termed as the Karn-Partridge algorithm was proposed in a paper by Phil Karn and Craig Partridge in 1987.

Routing in delay-tolerant networking concerns itself with the ability to transport, or route, data from a source to a destination, which is a fundamental ability all communication networks must have. Delay- and disruption-tolerant networks (DTNs) are characterized by their lack of connectivity, resulting in a lack of instantaneous end-to-end paths. In these challenging environments, popular ad hoc routing protocols such as AODV and DSR fail to establish routes. This is due to these protocols trying to first establish a complete route and then, after the route has been established, forward the actual data. However, when instantaneous end-to-end paths are difficult or impossible to establish, routing protocols must take to a "store and forward" approach, where data is incrementally moved and stored throughout the network in hopes that it will eventually reach its destination. A common technique used to maximize the probability of a message being successfully transferred is to replicate many copies of the message in hopes that one will succeed in reaching its destination.

Multipath routing is a routing technique simultaneously using multiple alternative paths through a network. This can yield a variety of benefits such as fault tolerance, increased bandwidth, and improved security.

MORE, which stands for MAC independent Opportunistic Routing, is an opportunistic routing protocol designed for wireless mesh networks. The protocol removes the dependency that other opportunistic routing protocols, such as ExOR and SOAR have on the MAC layer. Both of these protocols make use of a scheduler, to co-ordinate transmission among the nodes. Only one node transmits at a given point of time and all the other nodes listen to this. The nodes that listen remove the packets which they have queued for retransmission. This ensures that the same packet is not redundantly retransmitted by different nodes.

A mobile wireless sensor network (MWSN) can simply be defined as a wireless sensor network (WSN) in which the sensor nodes are mobile. MWSNs are a smaller, emerging field of research in contrast to their well-established predecessor. MWSNs are much more versatile than static sensor networks as they can be deployed in any scenario and cope with rapid topology changes. However, many of their applications are similar, such as environment monitoring or surveillance. Commonly, the nodes consist of a radio transceiver and a microcontroller powered by a battery, as well as some kind of sensor for detecting light, heat, humidity, temperature, etc.

Associativity-based routing is a mobile routing protocol invented for wireless ad hoc networks, also known as mobile ad hoc networks (MANETs) and wireless mesh networks. ABR was invented in 1993, filed for a U.S. patent in 1996, and granted the patent in 1999. ABR was invented by Chai Keong Toh while doing his Ph.D. at Cambridge University.

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. ↑ [ 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
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.