ExOR: Opportunistic Multi-Hop Routing for Wireless Networks
url show details
You need to log in to add tags and post comments.
| papers | collections | search | login | register | forgot password? |
|
| papers | collections | search | login | register | forgot password? |
|
This paper presents ExOR, which is an integrated routing and MAC protocol for increasing the throughput of large file transfers, consisting of batches of packets, in multi-hop wireless networks. An interesting aspect of ExOR is that a packet’s next hop is determined after it has been transmitted. ExOR essentially broadcasts packets to more than one node per hop; the list of nodes that will be responsible to forward each packet further towards the destination is selected after ExOR figures out which nodes actually received which packets. This technique increases the probability that packets will make progress, which makes ExOR well-suited for long-distance lossy wireless links. If multiple nodes successfully receive a packet the ExOR protocol makes sure that the primary node to forward the packet further is the one that is closest to the final destination.
ExOR achieves higher throughput that traditional routing protocols for two reasons. Firstly, because each transmitted packet has many candidate receiving nodes increasing the probability that it will be forwarded. In traditional routing for each transmitted packet there is only one single valid receiving node. Secondly, because it takes advantage of transmissions that reach unexpectedly far or fall unexpectedly short. In traditional routing if a portion of the sent packets are received by nodes that are farther away they will be simply dropped.
The design of ExOR needs to address four main issues. First, when sending a batch of packets, the receiving nodes must agree on which sub-set of the packets they have each received. This is solved by having the nodes exchange special messages called “batch maps”, which specify what packets each node has actually received. Second, among the nodes that have received a packet, the one closest to the final destination must be chosen to do the forwarding. ExOR solves this by using a metric similar to ETX, which we saw in the previous paper. Third, dense networks should avoid having too many potential forwarders. ExOR deals with this by keeping network-wide knowledge of inter-node loss rates, which is periodically updated through a flooding scheme. Fourth, ExOR must avoid simultaneous transmission to avoid collisions, which is achieved by prioritizing the forwarders and having them send in order.
Results were obtained by conducting real experiments on Roofnet, which, as we saw in a previous paper, is a roof-top 802.11b network consisting of 38 nodes. Compared to traditional routing schemes, ExOR performs 2-4 times better in terms of throughput. Another positive result of ExOR is that it minimizes the throughput variation that traditional routing algorithms experience.
Comments/Issues:
- ExOR seems to have large buffer space requirements, since packets are transferred in batches that might have to be stored in multiple receiving nodes. The authors do not seem to address the case where many concurrent transfers are taking place, which would require large dedicated buffers for each batch of packets. In addition to potentially prohibitive buffer space requirements, multiple concurrent transfers will also use a disproportionally large amount of network resources, because each transmitted packet affects many receiving nodes.
- ExOR interacts badly with TCP’s window mechanism. Although the authors claim that this can be solved by using a proxy, this makes ExOR a bit less attractive for massive deployment.
- ExOR requires that each packet carries an augmented header, which leads to an overhead of 12%. In networks that have relatively reliable links this can even lead to reduction of throughput when compared to traditional routing.
- In the evaluation section the authors mention that all of their experiments were conducted using a bit-rate of 1 Mbps and claim that a higher bit-rate would provide higher throughput. It would be more convincing if the paper had actual experimental results backing this up.
I agree with the previous posts: it is likely that ExOR requires large buffers and that it will cause more overhead .
On the other hand, they have tested ExOR on a real Roofnet in the presence of real use traffic and they got good results.The main idea presented in the paper is very attractive and their claim that throughput can improve because the chances of packets being delivered is higher seems to hold. There is still much work to do but I would say this is the direction to go since this kind of routing seems to outperform traditional routing.
Taking advantage of "lucky" transmissions is certainly an interesting idea. While the results seem to be very good (especially for longer routes), I would have liked to see some extended investigation involving:
1) ExOR in a heavilly loaded network with many other ExOR sources or many other "traditional" sources. The paper states that ExOR "inherits the fairness of 802.11", but I'm not sure what this means in practice.
2) How often are nodes confused about what packets need to be sent? If two intermediate nodes could hear the source but not each-other's batch maps this could result in many duplicate transmissions.
The opportunistic forwarding method described in this paper seems to be a very good idea for the type of wireless networks that the paper focuses on. (I.e., where packets must traverse multiple hops over wireless links.) However, I wonder if these types of networks will realistically occur in practice. Today, it seems that most wireless links are from mobile devices talking to a wired access point or talking directly to another mobile device. In these types of networks, where most communication traverses only one wireless link, it seems that ExOR would not be very advantageous.
Also, Samir has a good point regarding VoIP and other latency-sensitive applications: By bundling packets together into a batch and then losing up to 10% of the transmitted packets, ExOR can introduce undesirable latency. It would have been nice for the paper to compare latency as well as throughput.
It is a novel idea to improve network throughputs in wireless networks, but I'd like to see how this scheme influences per-packet transmission delays in the network.
Also, I'm wondering what is a rationale for picking "90%" for setting the point where batch transmission completes (section 3.7). Is it an optimized value in terms of some metrics?
As almost everyone has pointed out, these batch maps / headers and flooding should cause more overhead traffic. The 2-4 times improvement in throughput is surprising. But other than the overhead traffic, it's nice there shouldn't be any more collision than the standard multi-hop routing protocols.
Also, it seems like either Roofnet has "created" a bunch of cool papers or has been a good "real" testbed for these papers... from MIT anyway :)
I like the idea of making routing decisions based on actual packet reception instead of probability of success, so the progress of some lucky long distance transmission could improve the throughput. But I think the delay might not be improved at the same time due to the overhead. Anyway, the improvement of the throughput on the roofnet is impressive. But as many have pointed out, is roofnet really a representative example of the wireless networks nowadays?
I really liked the idea of deferring the decision until after the packet has been sent.
This, along with the other paper, really underscores how different wireless networks are from wired ones. It seems that thinking of the network as a graph and communications as point-to-point flows over edges is a really misleading abstraction when it comes to wirless networks, so a lot of n/w protocols which work under such an abstraction need to be rethought/redesigned.
Also, while it might be the case that in the current scenario, most wireless networks don't operate this way, it shouldn't be a big negative for this paper. It is possible that such improvements will make the cost/benefit of roofnet-like networks more attractive in the future and thereby change the 'typical' setting.
The idea of the paper to make use of transmission that reach unexpectedly far or short is interesting. I also agree with the other that major negative points of the protocol are a potential of large buffer and latency which make it not suitable for delay-sensitive data. Also there are several number that seems to come out from nowhere e.g. 5-packet transmission, 90% setting point of a batch of packets, etc.
The EXOR is a very novel system that helps to improve the throughput when loss rate is high. I am wondering is it the same case when loss rate is low?
This idea is cute and sounds reasonable - try your luck to see how far you can transmit a packet. But I am concerned about the efficiency of the discovery and agreement on the subset of nodes. If the overhead is acceptable, I believe this mechanism has made full use of the wireless channel, without coding.
Question: is it possible to make the protocol 'less opportunistic', to reduce the overhead?