Wednesday, October 29, 2008

2008-10-09 Readings - Making the Best of Broadcast


ExOR: OPPORTUNISTIC MULTI-HOP ROUTING FOR WIRELESS NETWORKS

Sanjit Biswas and Robert Morris


Summary:

Describes ExOR, a routing + MAC protocol for multi-hop wireless networks. Basic idea is that since each transmission is broadcast, some packets may be received by far away highly lossy links. Traditional routing (ETT/ETX flavor) would not take advantage of such opportunities, and all data would go along fixed route. Key elements include a packet buffer to store received packets in a batch, a mechanism to determine what is the set of nodes that may have received the packet, a mechanism to determine which nodes actually received the packet, and a mechanism to determine which node should next transmit towards the destination. Measurements under certain contexts show it's a significant improvement over ETX.

Discusisons & Criticisms:

Yet another study done on the Roofnet platform. Basically the whole train of work would be waste if one day someone shows directional antenna > omnidirectional antenna, or someone finds something really wrong with Roofnet.

Knee-jerk skepticism re multi-hop wireless networks.

The Roofnet paper also came out at the same time as this (SIGCOMM 2005 for this and MobiComm 2005 for Roofnet). Roofnet uses ETT as a significant improvement over ETX. Why wasn't ETT talked about here?

Also, per ETX paper, ETX is highly susceptible to discrepancies between loss rate measurement packet size and data packet size. In particular, for the ETX implementation in the ETX paper, packets at 1024 bytes perform VERY POORLY. The ExOR comparison measurements here use 1024 bytes packets, without telling us whether the ETX problems noted in the ETX paper have been properly mitigated. So comparison conclusions are sketchy.

Would be interesting for them to present the "average" hop count reduction that ExOR makes. From the Sally Floyd wireless modeling paper, we know that any intermediate transmission should be minimized because wireless is by nature not duplex.

Reduced throughput variation was cool though.


XORs IN THE AIR: PRACTICAL WIRELESS NETWORK CODING

Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Medard, Jon Crowcroft


Summary:

Presents COPE (never said what it stands for), a new architecture for wireless mesh networks. Basic ideal is to have a relay XOR packets and send out. Omnidirectional broadcast means XOR packets can be decoded by each sender if they know their own transmitted packet, and they're receiving an unknown packet. This would potentially cut the transmission count. Benefits of architecture can be characterized as coding gain (reduction in packet transmission needed per data) and coding/MAC gain (increased throughput due to traditional MAC fairness throttling relay send rate). Need mechanisms to opportunistically listen, opportunistically code through XOR, and learn neighbor state. Measurements on single floor wireless testbed show significant improvement for both TCP and UDP.

Discussions & Criticisms:

My standard skeptical reaction towards wireless multi-hop networks.

Also, a fundamental reservation about the overall approach. The authors showed that the traditional MAC concept of "fairness" is broken in a multi-hop context. So shouldn't the approach be redesigning the MAC instead of adding more complexity to cover up a broken MAC?

TCP losses > 10% and the thing still work? What happened to the 3% figure above which loss rate TCP basically fail and not make progress?

Good to see them use ETT routing as outlined in Roofnet paper.

Throughput was their only performance metric. Latency?

Also, their results for TCP is for an artificially compressed topology, and they themselves admit limited improvement with COPE in a real topology.

Increased RTT could push memory needs to unacceptable levels.

Overall, not sure if adding COPE is the right approach to address the problems they identified. Maybe designing a better MAC for wireless mesh would be more helpful.



Sunday, October 26, 2008

2008-10-07 Readings - Routing in Ad-hoc Networks



A HIGH THROUGHPUT PATH METRIC FOR MULTI-HOP WIRELESS ROUTING

Douglas S. J. De Couto, Daniel Aguayo, John Bicket, Robert Morris.

Summary:


Presents the ETX (Estimated transmission count) metric. Motivated by the fact that conventional DSDV hop-count metric is broken - picks long links with high error rates instead of short links with low error rates. Routing packets get through in DSDV but data packet does not. ETX calculated as 1/(df x dr) where df and dr are the forward and reverse delivery probabilities, and their product is the probability that a packet is transmitted successfully. df and dr found using dedicated link probe packets, sent according to some known size and average frequency. Can be implemented by modifying DSDV and DSR. Performance is best when the network has many loss links, or transmitters have low power. For a given network, performance improve is best for multi-hop links. Discrepancy between size of link probe packets and data packets can decrease performance.

Discussions & Criticisms:

Still don't somewhat skeptical about the multi-hop wireless network concept ... Where would such networks be needed, given that we have so much wired infrastructure in place, even in 3rd world countries? Seems only needed for sensor nets and other such niche applications.

As already mentioned in their own evaluation, any time you have a transmission count based thing you would likely have issues with packet size variations. Glad to see they modified the metric to ETT (Estimated transmission time) for Roofnet.

Also, the metric solves specifically the problem of conventional DSDV not finding routes with low loss rates. What about other metrics for evaluating a routing algorithm? Overhead (for both traffic and latency)? Stability? Speed of convergence? Topology changes (either nodes moving or link quality change)?

It wasn't immediately clear that with ETX replacing hop-count in DSDV, DSDV will preserve its loop-free property.

I think the whole wireless multi-hop routing thing has gone through the typical borrow-first refine-later process. That process is pretty evident in the paper.



A PERFORMANCE COMPARISON OF MULTI-HOP WIRELESS AD HOC NETWORK ROUTING PROTOCOLS

Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, Jorjeta Jetcheva.


Summary:

Compares the performance of DSDV, TORA, DSR, and AODV protocols. Emphasize the performance of protocols under various degrees of mobility. Done in ns2 with several modification to take care of wireless link details. Movement patterns with each node move to a random destination at a constant uniformly distributed speed, and then pause for a range of discrete pause times. Nodes send at constant bit rate, and various number of nodes send for various scenarios. Figure of merit include delivery ratio, and number of routing packets (overhead). Bottom line finding: AODV and DSR performs well, DSDV and TORA not so well.

Discussions & Criticisms:


Routing skepticism re multi-hop wireless networks.

The study emphasize mobility a lot. Good thing their results extend to pretty long pause times (900 seconds = 15 minutes), else we wouldn't know the protocol performance for stable topologies. I would argue they need even longer pause times. 30 sources and 15 minutes pause time = a topology change roughly every 30 seconds - still a very very non-stable network.

Also another interesting axis to plot might be the performance vs. the speed at which the nodes moved.

Maybe the Roofnet guys need to build a car-roof net and repeat this experiment for a "real" implementation comparison. Would be more convincing than ns2 stuff.



Sunday, October 19, 2008

2008-10-02 Readings - Wireless Networks in the Real World


MODELING WIRELESS LINKS FOR TRANSPORT PROTOCOLS

Andrei Gurtov, Sally Floyd

Summary:

Talks about how to model real world wireless links. Critical topic because modeling and simulation is precursor to any extensive and/or expensive field tests. Includes discussion about essential aspects of models, examples of bad models in literature, modeling various link characteristics, modeling queue management, effect on mobility, and wireless link vs. transport protocol issues.

Background:

Needs to know basic wireless 802.11 type knowledge.

Discussions and Criticisms:


Paper talks well about science. More helpful would be a operational checklist of common modeling pitfalls, and list of how to model each aspect of network. This way somebody wanting to use wireless link models can quickly reference the essential results of the work. For my own future reference, I make the list below.

Common modeling pitfalls (may apply for wired as well)

Unrealistic models:
- TCP with unrealistically high loss rates.
- Evaluating active queue management by focusing on TCP start-up.
- Assuming regular inter-packet delays.
- Constant TCP retransmission timer.
- Using deprecated TCP versions.
- Modeling WLAN as duplex.

Modeling a subset of parameter space:
- Evaluate using a single flow.
- Assume a particular link is bottleneck and not try the opposite assumption.
- Assume reserves transmission.

Overly realistic models:
- Focus on transient implementation flaws.

Lack of reproducibility (my routine complaint against a lot of methodological descriptions, far less emphasized today as it was in the early days of modern science):
- Not giving enough modeling details.

Also, list of wireless link aspects being modeled:

- Error loss & corruption.
- Delay variation.
- Packet reordering.
- On-demand resource allocation.
- Bandwidth variation.
- Asymmetry in bandwidth/latency.
- Queue management.
- Mobility.


ARCHITECTURE AND EVALUATION OF AN UNPLANNED 802.11B MESH NETWORK

John Bicket, Daniel Aguayo, Sanjit Biswas, Robert Morris.

Summary:


Talks about the architecture and realization of the Roofnet system. Key aspects of the system include totally unplanned - volunteers sign up and get antenna kit, omnidirectional antennas, use multi-hop routing, with estimated transmission time (ETT) metric - derived from estimated transmission count (ETX), which is presented in a separate paper.

Background:

Probably should read the ETX paper before this one. Also 802.11b knowledge. Maybe something about the different mesh routing algorithms would also help.

Discussions & Criticisms:

Pretty thorough performance characterization. However most of the results have no baseline for comparison - ok it's good, but HOW good is it? Not clear what should be the baseline of comparison either. Some kind of planned network? Directional antenna? Single hop to gateway? Some mixture of everything?

Tables 4 & 5 pretty valuable - comparison of multi-hop and single-hop networks.

Two key insights:
- Transmissions on multi-hops will interfere with each other.
- 802.11 RTS/CTS is BROKEN. They found RTS/CTS doesn't do what it's supposed to do, and introduces overhead. The evaluation should be repeated for other more general 802.11 settings. If results are reproduced, then we need to give general advice that RTS/CTS should be turnned off.

One evaluation that I think they missed - evaluate network performance under heavy load/utilization. Their network is utilized around 70% - for the Internet gateway i.e. - can we push it up to heavier loads? Also, scalability of gateway - all traffic funnel through gateway, so gateway = bottleneck? This will be apparent only if the network more heavily loaded.