MAC-Layer Anycasting in Ad Hoc Networks Romit Roy Choudhury and Nitin Vaidya. ACM SIGMCOMM Computer Communications Review, Vol. 34, number 1, Jan. 2004.
This is a paper I should have read a long time ago about multi-hop wireless mesh networks. It is deceiptively simple: the idea is to create a set of equivalent paths from the source to the destination using the route table information (the paper assumes a table-driven routing protocol) using a hop-count metric. If the metric is such tat no routes are strictly equivalent, routes could also be ordered and the set created from the list of routes satisfying a given criteria, say within some factor of the best path according to that metric.
Anyhow, once the route set is created at the network layer, the packet is given to the MAC layer with a list of potential candidates. The MAC layer then chooses which candidate to use based on the information available at the MAC layer. So if there are two possible candidates to send the packets to, the MAC chooses the one with the best condition (for example, availability, if one has sent a CTS and the other has not; or link rate and link conditions).
So the packet's route is not set a priori, but it is evolving as the packet moves along. The packet is not duplicated, there is still only one copy forwarded at each hop, but it makes use of the diversity available at each hop at this point in time.
A few notes: the benefit is not evaluated at all in this paper, which is a huge surprise to me. It is typically a requirement from any reviewer I have encountered. I am sure there is a subsequent performance evaluation somewhere, I just haven't looked for it.
But it would actually be interesting to see the performance improvement. On a short path, there would not be any. And the performance of long path is degraded by the fact that the multiple path are long. It might improve on a basic routing protocol, but it would improve on poor performance in the first place. Anyhow, I should look for that performance evaluation follow-up which must be somewhere.
The paper discusses using reactive protocols, such as DSR, but the solution is actually rather convoluted: instead of collecting a route, the RREQ-RREP exchange must collect a whole tree routed at the destination (for the uplink) so that each node can know the place of its neighbor in the relaying structure toward the destination. So that means that each RREQ-RREP must be broadcast more than strictly necessary, and extra-flooding is usually viewed as a bad thing.
Anyhow, this is really light reading. It is only the description of the idea, with no analysis nor performance evaluation, so it is a quick and easy and interesting read.
Showing posts with label wireless mesh networks.. Show all posts
Showing posts with label wireless mesh networks.. Show all posts
Wednesday, February 21, 2007
On the Placement of Web Server Replicas
On the Placement of Web Server Replicas, L. Qiu, V. Padmanabhan, G. Voelker, IEEE Incofom 2001, 1587-96.
This paper is definitely the inspiration for this one or the other way around. One is a journal paper from 2002 and the other a conference paper from 2001, so I would have to see which one came out when.
Anyway, it covers much of the same ground: placing web server replicas to form a Content Distribution Network (CDN) is a problem which is hard, and the paper presents some heuristic algorithms to solve the problem using an AS topology (and other topologies).
The goal is to improve on the result of a paper which proves the optimal placement on a tree topology (B. Li, M. Golin, G. Ialiano, X. Deng, "on the optimal placement of web proxies on the internet", infocom 1999): the internet is a mesh, not a tree, so using the tree optimal placement result in a sub-optimal internet placement.
The heuristics are similar to here: random, greedy (pick the best spot for a replica that minimize the cost, then iterate taking into account the already place replicas), hot spot (put the replicas near the sites which generate the most traffic) and super-optimal algorithm (which is super-optimal not because it is really super-duper, but because it might not feasible, thus might perform better than the optimal; it is solved using some Lagrangian relaxation of the integer programming problem defined by the problem).
There is a neat evaluation section, over a lot of different topologies and which shows that the greedy algorithm behaves pretty good. One really cool link from the paper is the NP problem compendium web page. I mean, once you think to add the tilde to the reference provided in the paper.
This paper is definitely the inspiration for this one or the other way around. One is a journal paper from 2002 and the other a conference paper from 2001, so I would have to see which one came out when.
Anyway, it covers much of the same ground: placing web server replicas to form a Content Distribution Network (CDN) is a problem which is hard, and the paper presents some heuristic algorithms to solve the problem using an AS topology (and other topologies).
The goal is to improve on the result of a paper which proves the optimal placement on a tree topology (B. Li, M. Golin, G. Ialiano, X. Deng, "on the optimal placement of web proxies on the internet", infocom 1999): the internet is a mesh, not a tree, so using the tree optimal placement result in a sub-optimal internet placement.
The heuristics are similar to here: random, greedy (pick the best spot for a replica that minimize the cost, then iterate taking into account the already place replicas), hot spot (put the replicas near the sites which generate the most traffic) and super-optimal algorithm (which is super-optimal not because it is really super-duper, but because it might not feasible, thus might perform better than the optimal; it is solved using some Lagrangian relaxation of the integer programming problem defined by the problem).
There is a neat evaluation section, over a lot of different topologies and which shows that the greedy algorithm behaves pretty good. One really cool link from the paper is the NP problem compendium web page. I mean, once you think to add the tilde to the reference provided in the paper.
Tuesday, February 20, 2007
ROMER: Resilient Opportunistic Mesh Routing for Wireless Mesh Networks.
ROMER: Resilient Opportunistic Mesh Routing for Wireless Mesh Networks. Y. Yuan, H. Yang, S. Wong, S. Lu, W. Arbaugh, WiMesh workshop, IEEE SECON 2005.
This paper I saw being presented at the 1st WiMesh workshop in Santa Clara in 2005, but I just re-read it recently. I might even have chaired the session it was in. The workshop was consisting of invited papers I believe, and the chairs selected right.
Anyhow, the crux of the paper is: give a packet an amount of credit which is equal to the cost C(S) of transmission times a constant. The cost C(S) is the cost to route from the source S to the destination. At each hop, pick K relays to forward the packet, so that each relay satisfies a credit/cost, where credit is the updated credit (ie. credit minus the cost used up to this point) and cost is the remaining cost at the node to the destination.
The K relays ensure the resilience, as you have a lot of packets going forward. As for the opportunism, it comes in the form of picking the K best relays according to the current conditions, that is: among the potential candidates, pick the K ones with the hight instantaneous rate conditions.
There are some good ideas, and some stuff that I don't necessarily agree with. The credit-based system is simple, but needs nodes to have a cost to each destination, which seems a bit un-scalable. Actually, it depends on how you define the credit and the cost, as a hop-count-based cost is scalable in some situations.
The K-resiliency would seem to me a strange way to optimize the use of the air interface. For instance, the paper does not specify how the K candidates receive the packet. Is it K unicast communications? In which case it is pretty sub-optimal. If it is one broadcast, how do you indicate the K recipients. How do they acknowledge. It runs into the same issues as ExOR basically, without providing the answer.
And then, this K-relaying introduces some race conditions to compete with the channel, between the 2nd transmission of the packet to the 2nd best neighbor, and the 1st neighor transmission of the same packet, but one hop downward. Again, solutions have been proposed (staggered Acks and re-tx) but this would need to be solved explicitly before an actual implementation.
Anyway, this is an interesting read, it triggers lots of good questions and ideas. I did not expect much from the WiMesh workshop as it was a new meeting, but I now have been to the two editions, and it is pretty good everytime.
This paper I saw being presented at the 1st WiMesh workshop in Santa Clara in 2005, but I just re-read it recently. I might even have chaired the session it was in. The workshop was consisting of invited papers I believe, and the chairs selected right.
Anyhow, the crux of the paper is: give a packet an amount of credit which is equal to the cost C(S) of transmission times a constant. The cost C(S) is the cost to route from the source S to the destination. At each hop, pick K relays to forward the packet, so that each relay satisfies a credit/cost, where credit is the updated credit (ie. credit minus the cost used up to this point) and cost is the remaining cost at the node to the destination.
The K relays ensure the resilience, as you have a lot of packets going forward. As for the opportunism, it comes in the form of picking the K best relays according to the current conditions, that is: among the potential candidates, pick the K ones with the hight instantaneous rate conditions.
There are some good ideas, and some stuff that I don't necessarily agree with. The credit-based system is simple, but needs nodes to have a cost to each destination, which seems a bit un-scalable. Actually, it depends on how you define the credit and the cost, as a hop-count-based cost is scalable in some situations.
The K-resiliency would seem to me a strange way to optimize the use of the air interface. For instance, the paper does not specify how the K candidates receive the packet. Is it K unicast communications? In which case it is pretty sub-optimal. If it is one broadcast, how do you indicate the K recipients. How do they acknowledge. It runs into the same issues as ExOR basically, without providing the answer.
And then, this K-relaying introduces some race conditions to compete with the channel, between the 2nd transmission of the packet to the 2nd best neighbor, and the 1st neighor transmission of the same packet, but one hop downward. Again, solutions have been proposed (staggered Acks and re-tx) but this would need to be solved explicitly before an actual implementation.
Anyway, this is an interesting read, it triggers lots of good questions and ideas. I did not expect much from the WiMesh workshop as it was a new meeting, but I now have been to the two editions, and it is pretty good everytime.
Anti-Packets in Wireless Multi-Hop Network
The Anti-Packets Can Increase the Achievable Throughput of a Wireless Multi-Hop Network, by Petar Popovski and Hiroyuki Yomo, of Aalborg University, ICC'06.
The idea is very simple, and it is one of the few applications that I have seen of the field of network coding, which may actually work. Surprisingly enough, the authors don't seem to know what network coding is. At least, they don't mention it.
This paper came at about the same time as the COPE paper from Dina Katabi's group at MIT which presents the same idea with a slightly different approach (COPE is more general). I would guess that, due to the MIT reputation and the publication forum, the citation count for COPE will outnumber the number of citations for this paper by a factor 100, even though both had the same idea at about the same time.
Assume a multi-hop wireless network with 3 nodes, A, B and C. A needs to send a packet AC to C, and C a packet CA to A (both packets of same length and errorless transmissions). The current way of doing it is in 4 time slot: 1-AC from A to B; 2-CA from C to B; 3-AC from B to C; 4-CA from B to A.
The idea of the paper is to combine 3 and 4, and to use the fact that since A and C both hear B, the last step can be: 3-B transmits ACA = XOR(AC,CA) to both B and A.
A, using ACA and AC, can recover CA, and similarly C can recover AC. The gain in bandwidth is 33%.
The throughput can be doubled in an analog manner: if A and C transmit at the same time (slot 1), then B hears a signal composed of both A and C components, A+C. Assuming B hears them both with the same power, then it can just replay the signal it heared in slot 1 in slot 2. It acts only as an amplificator. A hears A+C and can substract its own component to recover the packet from C, and C similarly. Bandwidth gain is 100%.
There are a lot of implementation issues and assumptions that should be debated (it requires symmetric traffic from A to C and C to A, at least bit-wise; synchronization; error recovery mechanisms look more complicated; etc) but the main idea is quite sexy.
The idea is very simple, and it is one of the few applications that I have seen of the field of network coding, which may actually work. Surprisingly enough, the authors don't seem to know what network coding is. At least, they don't mention it.
This paper came at about the same time as the COPE paper from Dina Katabi's group at MIT which presents the same idea with a slightly different approach (COPE is more general). I would guess that, due to the MIT reputation and the publication forum, the citation count for COPE will outnumber the number of citations for this paper by a factor 100, even though both had the same idea at about the same time.
Assume a multi-hop wireless network with 3 nodes, A, B and C. A needs to send a packet AC to C, and C a packet CA to A (both packets of same length and errorless transmissions). The current way of doing it is in 4 time slot: 1-AC from A to B; 2-CA from C to B; 3-AC from B to C; 4-CA from B to A.
The idea of the paper is to combine 3 and 4, and to use the fact that since A and C both hear B, the last step can be: 3-B transmits ACA = XOR(AC,CA) to both B and A.
A, using ACA and AC, can recover CA, and similarly C can recover AC. The gain in bandwidth is 33%.
The throughput can be doubled in an analog manner: if A and C transmit at the same time (slot 1), then B hears a signal composed of both A and C components, A+C. Assuming B hears them both with the same power, then it can just replay the signal it heared in slot 1 in slot 2. It acts only as an amplificator. A hears A+C and can substract its own component to recover the packet from C, and C similarly. Bandwidth gain is 100%.
There are a lot of implementation issues and assumptions that should be debated (it requires symmetric traffic from A to C and C to A, at least bit-wise; synchronization; error recovery mechanisms look more complicated; etc) but the main idea is quite sexy.
Cooperative Communication in Wireless Networks
Cooperative Communication in Wireless Networks, Aria Nosratinia, Todd E. Hunter, Ahmadreza Hedayat, IEEE Communications Magazine, October 2004. Authors with UT Dallas, and Nortel Networks.
The paper is a survey of the field on cooperative networks. Surprisingly enough, it is a short survey, meaning the field is still very new. It has only 11 references. This survey cites the origin of cooperative network in the paper of Cover and El-Gamal (capacity theorems for the relay channel, IEEE Trans. Info Theory, 1979).
The survey categorizes four different types of cooperation: detectand forward; amplify and forward; decode and forward; coded cooperation.
Performance is strongly improved by cooperation in terms of block error rate.
Paper is low level technical reading (no complex analysis or concepts) and clearly presented. It'd be interesting to know what applications --if any-- Nortel has in mind for this work.
The paper is a survey of the field on cooperative networks. Surprisingly enough, it is a short survey, meaning the field is still very new. It has only 11 references. This survey cites the origin of cooperative network in the paper of Cover and El-Gamal (capacity theorems for the relay channel, IEEE Trans. Info Theory, 1979).
The survey categorizes four different types of cooperation: detectand forward; amplify and forward; decode and forward; coded cooperation.
- The first one pairs nodes in a pair, and each partner's node attempts to detect the partner's bits and then retransmits the detected bits.
- Amplify and forward is more of an analog version of the first one: the partner receives a signal, and amplifies it. The receiver then decodes based on the signal received fromt the source and from the source's partner.
- Decode and forward is a variation of the first one, in which the partner encodes the packet from the source differently, so that the receiver has to different encoding to reconstruct the packet from (similar to the sensys paper by Dubois-Ferriere here, where I found this reference.)
- Coded cooperation: each user sneds different portion of each user's code word via two independent fading paths. I guess at the simplest, it is the decode-and-forward above.
Performance is strongly improved by cooperation in terms of block error rate.
Paper is low level technical reading (no complex analysis or concepts) and clearly presented. It'd be interesting to know what applications --if any-- Nortel has in mind for this work.
Characterisation of the Performance of Cooperative Networks in Ricean Fading Channels
J. Adeane, M. R. D. Rodrigues and I. J. Wassell, Characterisation of the performance of cooperative networks in Ricean fading channels, Proceedings of the International Conference on Telecommunications, Cape Town, South Africa, May 2005.
Another paper on my list of cooperative network channels. This ones looks at the performance in Ricean fading channels, and consider a simple network topology with two cooperating nodes trying to send data to a single destination, ie. the source-relay-destination triad.
Benefits of cooperation depends on the channel quality between the source and destination and between the source and relay. The paper actually shows a spot in which there is a degradation of the performance created by the cooperation (ie. the information provided by the relay to the destination does not improve that provided by the source, but even interferes with it or contradicts it).
Paper is relatively simple and results are relatively straight-forward, but a good read nonetheless.
Another paper on my list of cooperative network channels. This ones looks at the performance in Ricean fading channels, and consider a simple network topology with two cooperating nodes trying to send data to a single destination, ie. the source-relay-destination triad.
Benefits of cooperation depends on the channel quality between the source and destination and between the source and relay. The paper actually shows a spot in which there is a degradation of the performance created by the cooperation (ie. the information provided by the relay to the destination does not improve that provided by the source, but even interferes with it or contradicts it).
Paper is relatively simple and results are relatively straight-forward, but a good read nonetheless.
Two papers on ad hoc routing
These two papers were suggested by a reviewer of a paper of mine regarding opportunistic routing. They associated these papers with my results, which means I should have differentiated the results better, as it is pretty obvious to me they have little in common.
Anyhow, I have now read the papers:
AODV-BR: Backup Routing in Ad Hoc Networks, Sung-Ju Lee and Mario Gerla, in Proceedings of IEEE WCNC 2000.
On-Demand Multipath Distance Vector Routing in Ad Hoc Networks, Mahesh Marina, Samir Das, in Proceedings of IEEE ICNP, November 2001.
AODV-BR: Backup Routing in Ad Hoc Networks, Sung-Ju Lee and Mario Gerla, in Proceedings of IEEE WCNC 2000.
This paper introduces an extension of AODV which allows for graceful recovery when a link breaks. It uses the query-reply mechanism to build additional back-up routes at nodes adjacent to the route in the path.
Once a link on the route breaks, it can be temporarily recovered using the alternate path, while a route error is sent to the source and a new route discovery is triggered.
The idea is simple and practical, and works fine. It does bring improvement over AODV. The key difference with opportunistic routing is that the alternate is used after a broken link, and is not used otherwise. This means that if the route is reliable, but better links appear later on, these are ignored.
On-Demand Multipath Distance Vector Routing in Ad Hoc Networks, Mahesh Marina, Samir Das, in Proceedings of IEEE ICNP, November 2001.
This is similar to the previous paper, except that it computes link disjoint paths between source and destination. Same as above, the query-reply mechanism of the route discovery is used to set up the multiple link disjoint paths (as opposed to just associated nodes along the path as in the previous paper). In case of link failure, the traffic fails over to another path.
Again, it obviously outperforms AODV. Again, it does not make use of the promiscuous nature of the air interface to forward packets further.
Anyhow, I have now read the papers:
AODV-BR: Backup Routing in Ad Hoc Networks, Sung-Ju Lee and Mario Gerla, in Proceedings of IEEE WCNC 2000.
On-Demand Multipath Distance Vector Routing in Ad Hoc Networks, Mahesh Marina, Samir Das, in Proceedings of IEEE ICNP, November 2001.
AODV-BR: Backup Routing in Ad Hoc Networks, Sung-Ju Lee and Mario Gerla, in Proceedings of IEEE WCNC 2000.
This paper introduces an extension of AODV which allows for graceful recovery when a link breaks. It uses the query-reply mechanism to build additional back-up routes at nodes adjacent to the route in the path.
Once a link on the route breaks, it can be temporarily recovered using the alternate path, while a route error is sent to the source and a new route discovery is triggered.
The idea is simple and practical, and works fine. It does bring improvement over AODV. The key difference with opportunistic routing is that the alternate is used after a broken link, and is not used otherwise. This means that if the route is reliable, but better links appear later on, these are ignored.
On-Demand Multipath Distance Vector Routing in Ad Hoc Networks, Mahesh Marina, Samir Das, in Proceedings of IEEE ICNP, November 2001.
This is similar to the previous paper, except that it computes link disjoint paths between source and destination. Same as above, the query-reply mechanism of the route discovery is used to set up the multiple link disjoint paths (as opposed to just associated nodes along the path as in the previous paper). In case of link failure, the traffic fails over to another path.
Again, it obviously outperforms AODV. Again, it does not make use of the promiscuous nature of the air interface to forward packets further.
Opportunistic Multi-Hop Routing for Wireless Networks
This are some old notes, but I am consolidating here.
Opportunistic Multi-Hop Routing for Wireless Networks, Sanjit Biswas, Robert Morris, SIGCOMM 2005. Best Paper Award.
This is a continuation upon the work of Biswas and Morris, Opportunistic Routing in Multi-Hop Wireless Networks in HotNets-II, 2003. The previous work is the one which triggered my own work on opportunistic routing, which is basically to adapt Biswas and Morris's to dynamic network using an adapted version of AODV.
The paper presents an extension of the opportunistic routing from the previous paper. However, it seems that there were issues in applying the protocol to the RoofNet network, a mesh network based on 802.11 APs deployed by Morris's group in Cambridge, MA, as the protocol presented here is vastly different from the previous protocol (given also that this came out in 2005, while the previous paper was presented in 12/2003).
One issue is that: all packets end up not being accounted for, and the new paper proposes the opportunistic routing on a batch of paper, and default back to traditional routing once a 90% threshold has be attained for delivery. This is a bit cumbersome, and especially means that no real-life live traffic can be used using this. Heavy file transfers only.
Also, the MAC protocol from the earlier paper (with a RTS/CTS mechanism designed for opportunistic routing) is replaced by a different scheduled MAC, with no specific RTS/CTS. A ExOR header is added which contains information pertaining to the potential relays. This information is based on measurement and probes performed beforehand.
The node which forwards the packet is the closest to destination using an ETX (expected retransmission) metric, ie. a path is chosen not on the number of hops but on how many times the packet would be re-tx-ed to get to the destination. The fewer the re-tx, the closer.
Main issues/challenges regarding my own work: this is highly static. ETX requires to have a good knowledge of the routes a priori, which works if stuff does not move. Then sending a large batch and wait until 90% is transmitted implies that you have massive re-ordering. And some time on your hand, which again means static.
Concern: are the changes to the original protocol (hotnet-II 2003) made because the MAC layer was not accessible in their off-the-shelf 802.11 testbed, or was it made because of performance. The changes move everything up at the network level, so implementation could have driven it.
Performance evaluation of my own protocols will tell...
Opportunistic Multi-Hop Routing for Wireless Networks, Sanjit Biswas, Robert Morris, SIGCOMM 2005. Best Paper Award.
This is a continuation upon the work of Biswas and Morris, Opportunistic Routing in Multi-Hop Wireless Networks in HotNets-II, 2003. The previous work is the one which triggered my own work on opportunistic routing, which is basically to adapt Biswas and Morris's to dynamic network using an adapted version of AODV.
The paper presents an extension of the opportunistic routing from the previous paper. However, it seems that there were issues in applying the protocol to the RoofNet network, a mesh network based on 802.11 APs deployed by Morris's group in Cambridge, MA, as the protocol presented here is vastly different from the previous protocol (given also that this came out in 2005, while the previous paper was presented in 12/2003).
One issue is that: all packets end up not being accounted for, and the new paper proposes the opportunistic routing on a batch of paper, and default back to traditional routing once a 90% threshold has be attained for delivery. This is a bit cumbersome, and especially means that no real-life live traffic can be used using this. Heavy file transfers only.
Also, the MAC protocol from the earlier paper (with a RTS/CTS mechanism designed for opportunistic routing) is replaced by a different scheduled MAC, with no specific RTS/CTS. A ExOR header is added which contains information pertaining to the potential relays. This information is based on measurement and probes performed beforehand.
The node which forwards the packet is the closest to destination using an ETX (expected retransmission) metric, ie. a path is chosen not on the number of hops but on how many times the packet would be re-tx-ed to get to the destination. The fewer the re-tx, the closer.
Main issues/challenges regarding my own work: this is highly static. ETX requires to have a good knowledge of the routes a priori, which works if stuff does not move. Then sending a large batch and wait until 90% is transmitted implies that you have massive re-ordering. And some time on your hand, which again means static.
Concern: are the changes to the original protocol (hotnet-II 2003) made because the MAC layer was not accessible in their off-the-shelf 802.11 testbed, or was it made because of performance. The changes move everything up at the network level, so implementation could have driven it.
Performance evaluation of my own protocols will tell...
Opportunistic Packet Scheduling and Media Access Control for Wireless LANs and Multi-Hop Ad Hoc Networks.
Opportunistic Packet Scheduling and Media Access Control for Wireless LANs and Multi-Hop Ad Hoc Networks. J. Wang, H. Zhai and Y. Fang, WCNC 2004.
This paper proposes to perform a scheduling similar to proportional fairness in multi-hop networks, by sending a CTS to a list of potential relays (those whose packets are waiting for transmission in the output buffer of the node), receiving the RTS with an indication of current signal strength, and picking the "best" node, according to a metric similar to that of proportional fair (based on the achieved throughput to each node up to this time).
The idea is straight-forward, but quite good actually (by which I mean: this should be a better-than-WCNC paper). It should be obvious that, as soon as several packets are awaiting transmission at any node, then the node has the choice to pick which one to transmit based on instantaneous conditions.
Performance gains shown, obviously. Little analysis, simulation only.
This paper proposes to perform a scheduling similar to proportional fairness in multi-hop networks, by sending a CTS to a list of potential relays (those whose packets are waiting for transmission in the output buffer of the node), receiving the RTS with an indication of current signal strength, and picking the "best" node, according to a metric similar to that of proportional fair (based on the achieved throughput to each node up to this time).
The idea is straight-forward, but quite good actually (by which I mean: this should be a better-than-WCNC paper). It should be obvious that, as soon as several packets are awaiting transmission at any node, then the node has the choice to pick which one to transmit based on instantaneous conditions.
Performance gains shown, obviously. Little analysis, simulation only.
The Critical Transmitting Range for Connectivity in Sparce Wireless Ad Hoc Networks
This paper: The Critical Transmitting Range for Connectivity in Sparce Wireless Ad Hoc Networks P. Santi, D. Blough, IEEE Trans on Mobile Computing, Vol.2,No.1,Jan-Mar 2003, is excellent.
It computes the asymptotic relation between the range r, the length l and the number n of nodes uniformly (randomly) distributed in a square area of side length l with connectivity range r. It establish the value for r for which the graph is connected with high probability, or disconnected with high probability.
The main result is: in one dimension, rn > 2l log(l) ensures connectivity, rn < (1-epsilon) l log(l) ensures disconnectivity.
In higher dimension (2 and 3), connectivity is assured for r^d n > k l^d log(l), with k a constant which depends on the dimension. If r^d n < l^2, then the graph is disconnected.
There is a gap in dimension 2 and 3 wrt the asymptotes. Also, paper conjectures that in dim 1, rn < 2l log(l) should ensure disconnectedness.
Most of the proofs come from a pigeon-hole argument, which is relatively simple and elegant.
It computes the asymptotic relation between the range r, the length l and the number n of nodes uniformly (randomly) distributed in a square area of side length l with connectivity range r. It establish the value for r for which the graph is connected with high probability, or disconnected with high probability.
The main result is: in one dimension, rn > 2l log(l) ensures connectivity, rn < (1-epsilon) l log(l) ensures disconnectivity.
In higher dimension (2 and 3), connectivity is assured for r^d n > k l^d log(l), with k a constant which depends on the dimension. If r^d n < l^2, then the graph is disconnected.
There is a gap in dimension 2 and 3 wrt the asymptotes. Also, paper conjectures that in dim 1, rn < 2l log(l) should ensure disconnectedness.
Most of the proofs come from a pigeon-hole argument, which is relatively simple and elegant.
Monday, February 19, 2007
A High Throughput Path Metric for Multi-Hop Wireless Routing.
Douglas DeCouto, Daniel Aguayo, John Bicket, Robert Morris, Wireless Networks 11, 419-34, 2005.
I had read a version of this paper a little while ago, but some reviewing duty sent me back to it to confirm a thing or two. It introduces the ETX measure, which is an additive measure to find the path between two nodes on a wireless mesh network which minimizes the number of retransmission.
That it is additive is a good thing, and it does not have the issues of other metric: shortest hop count might find long links with bad quality and the actual performance of shortest path is demonstrated in the paper to be quite poor. Using a product of delivery ratio (which is additive too if you take the logs) or the minimal PDR (again, additive in a (max,+) algebra) will favor multi-hop links with good PDR over a single link with lesser PDR, but the relaying interference of the multi-hop path will divide the bandwidth of the path by two, so it is not a good metric either.
ETX computes the delivery rate of a link in each direction and is computed as the inverse of the product of these rates. The higher the ETX count, the more the expected the number of re-transmission, so the routing should choose the path with the lowest cumulative ETX. Performance is actually improved, especially as path are longer.
What is nice about the paper: it is very nicely explained. It is thinner in technical content than I remembered (basically it is the idea of the ETX metrics which matters) but each choice is very nicely argued and motivated, and each decision made very clear. So it is a very nice read.
The main thing I am now taking from the paper is that the performance of the metric is the invert of the packet delivery in both directions. However, one direction is the ACK direction, and this can be improved by sending mutliple ACKs, or by adding enough redundancy in the ACK to decode it successfully every time. Then your ETX drop. For instance, if you have 1/2 pdr in each direction, your ETX is 4. If you add enough coding redundancy so as to decode the Ack succesfully every time, then your ETX drops to 2. That's a pretty major gain. It is obvious, but the paper does not suggest doing it.
I had read a version of this paper a little while ago, but some reviewing duty sent me back to it to confirm a thing or two. It introduces the ETX measure, which is an additive measure to find the path between two nodes on a wireless mesh network which minimizes the number of retransmission.
That it is additive is a good thing, and it does not have the issues of other metric: shortest hop count might find long links with bad quality and the actual performance of shortest path is demonstrated in the paper to be quite poor. Using a product of delivery ratio (which is additive too if you take the logs) or the minimal PDR (again, additive in a (max,+) algebra) will favor multi-hop links with good PDR over a single link with lesser PDR, but the relaying interference of the multi-hop path will divide the bandwidth of the path by two, so it is not a good metric either.
ETX computes the delivery rate of a link in each direction and is computed as the inverse of the product of these rates. The higher the ETX count, the more the expected the number of re-transmission, so the routing should choose the path with the lowest cumulative ETX. Performance is actually improved, especially as path are longer.
What is nice about the paper: it is very nicely explained. It is thinner in technical content than I remembered (basically it is the idea of the ETX metrics which matters) but each choice is very nicely argued and motivated, and each decision made very clear. So it is a very nice read.
The main thing I am now taking from the paper is that the performance of the metric is the invert of the packet delivery in both directions. However, one direction is the ACK direction, and this can be improved by sending mutliple ACKs, or by adding enough redundancy in the ACK to decode it successfully every time. Then your ETX drop. For instance, if you have 1/2 pdr in each direction, your ETX is 4. If you add enough coding redundancy so as to decode the Ack succesfully every time, then your ETX drops to 2. That's a pretty major gain. It is obvious, but the paper does not suggest doing it.
Sunday, February 18, 2007
Little Tom Thumb Went Straight Home.
C. Westphal, Little Tom Thumb Went Straight Home, in Proc. of Infocom 07, Anchorage, Alaska.
Content and Service Replication Strategies in Multi-hop Wireless Mesh Networks.
by Shudong Jin, Limin Wang. MSWiM'05, Oct. 10-13, Montreal, Quebec. Paper here.
The paper studies the impact of the replication of content in a wireless mesh networks. They show that in a 2-d mesh network, the optimal number of replicas of an object is $p^(2/3)$, where $p$ is the access probability of the object.
The result is pretty, as it is a bit counter-intuitive (a replication rate proportional to the access probability is what would seem natural), and the derivation is actually rather simple and straightforward.
The paper also opens research questions into: how to account for the wireless physical layer. In the paper, it is abstracted as a way to define the connectivity, and thus the topology, of the network, but the actual impact of the wireless interface on the placement of the replicated content could have some other implications. An interesting idea to look into.
The paper studies the impact of the replication of content in a wireless mesh networks. They show that in a 2-d mesh network, the optimal number of replicas of an object is $p^(2/3)$, where $p$ is the access probability of the object.
The result is pretty, as it is a bit counter-intuitive (a replication rate proportional to the access probability is what would seem natural), and the derivation is actually rather simple and straightforward.
The paper also opens research questions into: how to account for the wireless physical layer. In the paper, it is abstracted as a way to define the connectivity, and thus the topology, of the network, but the actual impact of the wireless interface on the placement of the replicated content could have some other implications. An interesting idea to look into.
Subscribe to:
Posts (Atom)