Nalanda

Citation: Bicket, J., Aguayo, D., Biswas, S., and Morris, R. 2005. Architecture and evaluation of an unplanned 802.11b mesh network. In Proceedings of the 11th Annual international Conference on Mobile Computing and Networking (Cologne, Germany, August 28 - September 02, 2005). MobiCom ‘05. ACM, New York, NY, 31-42. DOI= http://doi.acm.org/10.1145/1080829.1080833

The idea presented in this paper is as intriguing as it is compelling: can an unplanned wireless mesh network provide better performance than one which is carefully planned? Unplanned networks have the obvious advantage of ease of deployment; but conventional wisdom would seem to indicate that such networks would likely have lower performance than a carefully planned network. As the authors demonstrate, this is decidedly not the case for their system, Roofnet.

Roofnet was designed with following considerations in mind: unconstrained node placement, omni-directional antennas, multi-hop routing, and an assumption that nodes are fixed, rather than mobile. There are two distinct components that enable Roofnet’s operation on commodity 802.11b hardware: the Srcr routing protocol, and SampleRate bit-rate selection. Additionally, NAT is used both to connect clients to nodes, and nodes to gateways.

Srcr gets routing information in a number of ways: by including link metrics in a packet’s source route (Roofnet encapsulates IP packets in its own header format), through flooded queries when necessary, by overhearing queries and responses, and via periodic dummy queries flooded from gateways. This last point enables nodes to maintain updated metrics for routes to their nearest gateway, and also means that nodes do not typically have to flood queries themselves. However, as the authors point out, this means that the query mechanism could be a constraining factor in a larger or denser network. Srcr uses a combination of delivery probability and highest throughput bit-rate on each link for its routing metric. This leads to the counterintuitive result that links with a high loss rate, but also a high bit-rate, provide better performance than multiple links with zero loss. The SampleRate bit-rate selection algorithm estimates bit-rates in realtime, by basing its decisions on actual data transmissions, along with periodic shifts in bit-rate to estimate delivery probabilities of different bit rates.

In practice, Srcr tends to ignore longer links, and uses a relatively small number of shorter high throughput links. As might be expected, this also means that performance and connectivity of the mesh increases with density of nodes, as a greater number of shorter routes become available. Roofnet is robust as a mesh, in the sense that nodes tend to route through many neighbours, and that the mesh continues to operate well in the face of degradation or loss of links. Most significantly, perhaps, Roofnet requires fewer gateways to operate than a similar access point network. Although the node placement may be unplanned, careful choice of gateway placement increases network performance, which may be why Roofnet’s commercial successor, Meraki, operates the gateways for their San Francisco deployment themselves.

Inter-hop interference appears to be a significant cause of loss in Roofnet, on which the use of RTS/CTS has no effect, and remains an open issue in the paper.

The use of NAT at gateways means that TCP connections are tied to a gateway once established, even though the route to the gateway may change. Additionally, the means that if the routing metric to a gateway degrades, subsequent connections may be directed to other gateways, while existing connections cannot shift. This would seem to imply that Roofnet can deal more reliably with short connections rather than long ones, although this may not be as much of an issue if the network is sufficiently dense, and gateways are generally reliable themselves.This also means that the gateway becomes a factor in fate-sharing between hosts inside and outside Roofnet. While this approach violates layering, it does not seem unreasonable to me; from the last few papers we’ve read, it seems apparent that these kinds of approaches are necessary to bridge wired and wireless networks.

Citation: Gurtov, A. and Floyd, S. 2004. Modeling wireless links for transport protocols. SIGCOMM Comput. Commun. Rev. 34, 2 (Apr. 2004), 85-96. DOI= http://doi.acm.org/10.1145/997150.997159

The authors’ are concerned that inadequate modeling of wireless links is leading to implementations of wireless link layer protocols, and transport protocols, which may not interoperate as anticipated by the models. This paper seems to be their attempt to point out how widespread this practice is, and provide an examination of problem areas along with guidelines and suggestions for the development of better models. As the authors point out, there is a tussle between wireless link design and transport protocol design, with open questions as to how each should change in order to accommodate the dynamics of the other. The principal problem, of course, is that TCP assumes that all packet losses are indicators of congestion, which is often not true of wireless links.

Three types of wireless links are studied: cellular, wireless LAN and satellite. A variety of topologies are discussed, ranging from single to multiple wireless hops, potentially over different link layers (e.g., WLAN+Bluetooth). A topology that is mentioned in passing, but which I would have liked to see more discussion of, is that of a wireless backhaul, which is discussed in our other reading for today, and is being used in metropolitan area networks, such as those operated by Meraki.

In the section on performance metrics, goodput is mentioned as a key indicator, with a link drawn between goodput and the energy efficiency of the transport protocol, and therefore the battery power of the mobile terminal.

A wide range of wireless link characteristics are discussed, along with their effects on transport protocols. These include error losses and corruption, delay variation, packet reordering, on-demand resource allocation, bandwidth variation and asymmetry in bandwidth and latency. In addition, the effects of varying queue management schemes and the effects of mobility are also examined. Of the many issues discussed here, one of the most interesting to me was that link layers should not perhaps try too hard to shield transport protocols from their idiosyncracies. For instance, retransmitting packets too many times, may actually work against end-to-end performance, as the transport protocol may trigger a retransmission even while the wireless link layer is attempting to redeliver a packet.

Drawing these together, an attempt can be made to understand how and where wireless link layer and transport protocols might need to be modified in order to work better together. To begin with, a distinction can be made between fundamental limits (the speed of light for a satellite link), and those which are not so (high latency in terrestrial links, degree of reordering of packets). An interesting notion of an explicit corruption notification is brought up, which would allow wireless links to signal transport protocols that a loss is due to corruption rather than congestion. Other suggestions included making TCP more robust to reordering, to allow wireless protocols more leeway in this area, to allow applications to specify the level of tolerable corruption to reduce retransmits, to limit the delay variation made visible from link layer to transport protocol, to improve handover mechanisms to minimize delay spikes, and to enable cross-layer communication to allow transport and link layers to negotiate with one another on their requirements and capabilities.

This is a difficult paper to summarize, since it covers so much ground. The pieces of the paper that I drew the most from were their discussion of the interplay of the protocols themselves, rather than how these complexities might be encoded in models. Both the discussion of these complexities and the comments on specific cases they examined were of great value.

Citation: Balakrishnan, H., Padmanabhan, V. N., Seshan, S., and Katz, R. H. 1996. A comparison of mechanisms for improving TCP performance over wireless links. In Conference Proceedings on Applications, Technologies, Architectures, and Protocols For Computer Communications (Palo Alto, California, United States, August 28 - 30, 1996). M. Steenstrup, Ed. SIGCOMM ‘96. ACM, New York, NY, 256-269. DOI= http://doi.acm.org/10.1145/248156.248179

As the title suggests, the authors compare a variety of mechanisms for improving TCP performance of wireless links; interestingly, the authors also suggest that the same mechanisms may be of use in any network, not necessarily just wireless, which has lossy links. The schemes examined are broken into three broad classes: end-to-end protocols, link layer protocols and split-connection protocols. In every instance, the goal is to provide better end-to-end behaviour by either modifying TCP to deal with loss less drastically, or by attempting to shield TCP from wireless losses. The measures used to examine these schemes are throughput and goodput (the ratio of actual transfer size to the total bytes transmitted over a path).

End-to-end protocols rely on the sender to perform loss recovery. The mechanisms adopted for this purpose here include partial acknowledgements, selective acknowledgements (based on IETF specifications, and the SMART mechanism) and the use of Explicit Loss Notification. While useful as a basis for comparison to other approaches, E2E mechanisms are faced with the problem of adoption: in order to function effectively, wired senders must be modified to handle SACK and ELN information. The experimental results show that use of both SACK and ELN information provides improved performance, which provides a useful guideline for the design of end-to-end protocols in general.

Link layer protocols attempt to perform loss recovery at the link layer, shielding TCP from wireless losses. In general, these protocols need to maintain buffers at base stations to enable local retransmission. SMART may again be used here as an acknowledgement scheme. These protocols may also be implemented to violate layering, by making them TCP-aware. As controversial as this may have been, it seems a reasonable choice when trying to shift bits between two media that impose such different design constraints. As experimental results indicate, the TCP-aware link layer protocol provides the greatest benefit. This protocol also provides the best performance in the presence of burst errors and under different error rates.

Split-connection protocols attempt to completely shield TCP from wireless losses by performing all retransmissions at the base station. Of all the three approaches, this one instinctively seemed the least likely to succeed; complete isolation would seem to imply an abrupt shift between wired and wireless media which would likely impose unreasonable memory and processing requirements on the base station for correct and adequate performance. As the experimental results show, this results in 100% goodput for the wired sender, but stalls whenever the wireless sender experiences a timeout, due to bounded buffer space.

Though brief, I found the discussion of wireless handoffs particularly interesting. The idea of sharing state across nearby base stations is compelling, and I can see how this could work very easily with a link layer scheme. As the paper notes, split-connection schemes fare badly here as well, since they require the transfer of transport layer state across base stations.

Citation: Bharghavan, V., Demers, A., Shenker, S., and Zhang, L. 1994. MACAW: a media access protocol for wireless LAN’s. In Proceedings of the Conference on Communications Architectures, Protocols and Applications (London, United Kingdom, August 31 - September 02, 1994). SIGCOMM ‘94. ACM, New York, NY, 212-225. DOI= http://doi.acm.org/10.1145/190314.190334

The authors describe MACAW, a set of extensions to the Media Access, Collision Avoidance (MACA) protocol with the goals of dealing better with fair allocation, with congestion in general, and more specifically with non-homogeneous congestion. The extensions proposed are motivated by four observations:

• Contention is at the receiver, not the sender. Although, interestingly, some of their protocol modifications result in potential for congestion at both receiver and sender.
• Congestion is location dependent.
• For fair allocation, congestion levels must be communicated amongst the nodes of the network.
• Synchronization information about contention periods must be shared to allow effective contention.

The last two points are particularly interesting, since they point to an approach to network design - maintain shared state, at least locally, across the network - which seems to be the antithesis of approaches to wired networking. It seems to me that they come to this conclusion by rejecting carrier sense as an approach in their design, although the authors do suggest later in the paper that carrier sense might actually be a viable approach in general. For instance, I imagine that carrier sense could be used in place of shared synchronization information: at least in a LAN scenario, stations could conceivably contend effectively at the moment that they sense no carrier (this would, of course, require more changes to the protocol, including a different backoff algorithm).

Following their observations, the authors suggest the addition of the following mechanisms to MACA:

• ACK messages to allow recovery from packet loss at the link layer, which cater to the shorter timescales of wireless communications. Given the greater loss rates for wireless media, and that loss here does not necessarily indicate congestion, this is of great importance in preventing TCP from backing off.
• DS messages to handle the exposed terminal problem, signalling nearby stations that a DATA transmission is about to commence, and also informing them of the length of the transmission, so that they are aware of the next contention period.
• RRTS messages to complement DS messages at receivers, rather than senders. This is motivated by the useful observation that there can be situations where a receiver cannot respond to a RTS, since it may be deferring to another station sending DATA. It does, however, seem that DS/RRTS could be replaced with a carrier sense approach, as I noted earlier.
• Sharing of information about contention periods and congestion (backoff counter values) via control messages.

These are complemented by a backoff algorithm that randomly calculates an interval to wait before sending a RTS, to provide fair allocation. The same algorithm is also used to determine which of a station’s streams should be serviced. The range over which this interval is calculated follows a multiplicative increase/linear decrease (MILD, which seems analgous to AIMD) depending on whether or not a CTS is received, the assumption being that a lost CTS indicates congestion. To handle non-homogeneous congestion, separate backoff counters are maintained for each stream through a station. The backoff to use is calculated over the range from a fixed minimum to the sum of backoff values across receiver and sender, to account for congestion at both ends.

While the discussion in the paper distinguished between base stations (with a wired backhaul) and pads, I think it would have been useful to make this distinction explicit in the protocol. Base stations, for instance, could be treated as gateways (a single wired connection on one side, probably with  a large bandwidth-delay product, many wireless connections on the other) which would make them amenable to approaches such as RED.