Roofnet

Roofnet is an unplanned 802.11b mesh network that aims to provide high performance Internet access. Roofnet has the following design advantages: Unconstrained node placement, omni-directional antennas, multi-hop routing and throughput-optimized routing. While these advantages ease deployment, the question is how it affects the performance of the network.

I like the deployment scenario of Roofnet – volunteers who just signed up and installed the node on their roof tops. Routing happens over a combination of link-state and DSR-style querying. The installation is fairly straightforward, and nodes form a wireless ad-hoc network among them. I would have liked to see a photo of the antenna installed on the rooftop along with node. Are the nodes to which the antennas are connected, placed on the roof top too? What are the effects of wear and tear, pollution etc.? In any case, a nice follow-up work to this could be something like “The Operational Difficulties of maintaining a wide-spread mesh network” (like the TIER paper in NSDI 2008 – I loved it!).

The evaluation determines performance of Roofnet based on the following measurements:

1. Multi-hop TCP data obtained using a one-way bulk TCP transfer between each pair of Roofnet nodes (15 seconds)
2. Single-hop TCP data measured using direct links between nodes
3. Loss matrix that quantifies the loss rate between each pair of nodes using 1500-byte broadcasts
4. Multi-hop density: TCP throughput between a fixed set of four nodes for different Roofnet nodes

Another aspect of their evaluation could be to see at what density does it become too chaotic that there is just way too much interference. But “living with the interference” is a theme in MIT’s current research…so it seems to be consistent.

I am personally not a fan of multi-hop networks in real life. I have never been able to get its utility in a generic sense (I understand it is clearly useful for special cases like sensor nets). And in any case, Roofnet isn’t too relevant for an urban setting where each user is likely to have a gateway anyway. But it would be interesting to see how Meraki does (or has done).

But overall, I found this paper to be quite interesting and smart but I wouldn’t vote for keeping it on the list.

Modeling Wireless Links for Transport Protocols

Design and evaluation of transport protocols can be improved by using good models for wireless links that provide control over realism, generality and detail. Despite the vast differences in the different wireless technologies compared to the wired networks, the paper argues that it is still advantageous to use the same protocol stack as it enables interoperability. For example, delay variation models vary depending on real-world scenarios and have a strong impact on the transport protocol’s functioning. This paper considers WLAN, cellular and satellite links – wireless technologies used in practice. These have different characteristics in terms of latency and throughput, and are preferred in different settings because of their range.

The paper devotes a section to explaining the flaws in the current simulation models and parameters. It points out very important points about packet loss rate, retransmission timer, TPC flavors etc. While I am not well-versed with the references in this paper, I do sometimes feel that some “flawed” models are totally good enough for the particular problem in hand. If a certain aspect of the model is unrealistic, then probably the authors of the model have concluded with good reasoning that aspect is not expected to influence the results. On the other hand, having a model with all the knobs inevitably results in people not knowing how to set the values of the knobs accurately. For wide usage, some pre-built models have to be provided and it would obviously come along with the risk of being unrealistic in certain cases.

Error-based losses, delay variation, packet reordering, on-demand resource allocation (and associated latencies), bandwidth variation and asymmetry in bandwidth and latency are the characteristics of wireless links considered. The paper also talks about queue management and mobility modeling. The paper says that modeling handoffs and their associated delays etc. will be a more realistic model in the way wireless networks will be adopted (I agree!).

It finally gets to the chicken-and-egg equivalent problem in wireless networks: do transport protocols change or link layer technologies change? I find this to be a dangerous argument because if link layer technologies change to become more reliable (and essentially TCP-ish), then the very purpose of a transport protocol seems lost! Also, this is totally unfair to applications that bank on UDP for performance reasons. Clouding link-layer technology development with views from the TCP-world is not good.

MACAW

Media access in wireless networks is a harder problem than wired networks. This paper gives a nice description of the lay of the land. CSMA senses the medium before transmitting but since collisions typically occur on the receiver, it suffers from the hidden and exposed terminal problems. MACA fixed this with a Ready-to-Send (RTS) and Clear-to-Send (CTS) control protocol. MACA used an exponential back-off timer which, as described in this paper, becomes a source for unfairness. The crux of the problem is that the back-off timer is a function of the number of tries that a node has made, bringing in inequality.

This paper proposes MACAW that proposes the following four modifications:

1. Fairness is achieved by nodes updating their back-off timer on hearing a packet.

2. DS and RRTS mechanisms to synchronize timing across senders

3. Location-tagged back-off timers, as congestion is more a function of a sender-receiver pair as opposed to a sender alone.

I vote to keep this paper in the reading list as it gives a good idea of the area stand-alone. I wasn’t happy about the experimental setting (base stations and pads) on two counts: One, it was unclear (and the paper doesn’t convince either) on how realistic this setting was to real wireless LANs. Second, I would have liked a description that helped me perform their experiments again, under different conditions. I didn’t understand what it would take to reproduce their experiments.

A Comparison of Mechanisms for Improving TCP Performance over Wireless Links

TCP was inherently designed for wired links that experience packet losses mainly due to congestion as opposed to corruption in wireless networks. The mechanisms to adapt TCP fall into three categories: link-layer loss correction using coding, tweaking TCP congestion control mechanisms, and split-TCP connection (base station to mobile host is a separate TCP connection). This paper compares the performance of the techniques under simulated losses. Techniques primarily focus on hiding things from TCP so that it doesn’t react too much. Link layer techniques suppress duplicate acknowledgements arising out of reordered packets so that the sender does not reduce its congestion window in reaction. End to end techniques avoid wastage using SACK and are a good option. Splitting TCP connections also helps insulate TCP from the vagaries of the wireless world.

I liked the second and third technique, with the latter being especially smart (though it is unclear if base stations can function at line speeds with this extra overhead). While the second technique is relatively easier to deploy, the third technique requires changing TCP semantics and base stations. Overall, this was a nice survey/evaluation sort of a paper and very informative. I vote for keeping it in the reading list.

This paper leaves itself open to the standard criticism of showing results based on simulations as opposed to real implementations. While, undoubtedly, the paper would be stronger with real evaluations, I think the lessons from the paper are still valuable.

Questions:

1. What eventually won the race? Do we have a modified version of TCP for wireless links now, or is it all uniform?

2. The techniques for improving TCP over wireless links seem to have no regard for the E2E principle. Maybe it is all about identifying the "correct" end-points...Can we have a discussion of this in class?

XCP

This paper describes the eXtensible Control Protocol and aims to address TCP’s inherent instability (overestimating and resizing the window), and conservative nature (slow-start). Like in RED, XCP involves the router to provide an explicit feedback. Each data packet has a feedback field updated by the routers along the path, and eventually returned to the sender via ACKs. Since every router updates the feedback field, the sender can identify the “weakest link” and behave accordingly. I think XCP is a very powerful idea and evaluations show that it clearly performs better than TCP.

While this paper leaves itself open to criticism of nodes manipulating the feedback fields and hijacking the router resources, I think that is a larger problem and wouldn’t criticize XCP in particular. Most ideas that propose differentiated servicing (QoS), have to deal with the problem of admission control and dishonest hosts. I think Scott’s paper on the future of the Internet also mentions the point of admission control. A possible solution to that problem could be on the lines of deploying some sort of a middle-box that monitors the tampering of the feedback field (assuming symmetric routes) and incorporation of the feedback by the hosts. Solutions like XCP can be very useful for solving DDoS problems.

Overall, I found the paper very interesting and suggest we keep it in the list. Also, if this stays, RED can be replaced by a different paper.