Nalanda

Citation: Intanagonwiwat, C., Govindan, R., and Estrin, D. 2000. Directed diffusion: a scalable and robust communication paradigm for sensor networks. In Proceedings of the 6th Annual international Conference on Mobile Computing and Networking (Boston, Massachusetts, United States, August 06 - 11, 2000). MobiCom ‘00. ACM, New York, NY, 56-67. DOI= http://doi.acm.org/10.1145/345910.345920

This paper describes the general concept of directed diffusion for requesting, and retrieving, data from sensor networks. In such a system, users express an interest in certain kinds of data, and this interest then diffuses across the network towards the nodes most capable of responding, and is then relayed back along the same paths, a smaller set of which may be reinforced by the sensor network itself.

Tasks, or interests, are defined as a set of name/value pairs, along with a specification of the region of the network from which data is to be retrieved. Interests are periodically broadcast by the node to which a user connects, called the sink node, initially at a long interval, to probe the network for the existence of nodes which match the interest. Every nodes maintains an interest cache, with gradients on each interest pointing back to the node from which the interest was received and specifying a data rate.

Nodes, starting with the sink, initially broadcast interests to all their neighbours at a relatively low rate. As the sink starts receiving data, it selectively reinforces particualr neighbours, by resending the interest to them with a higher specified data rate. Nodes in turn perform the same process of reinforcement, selecting neighbours based on matches in their data cache to the interest. In addition, neighbour node selection is affected by the delay to respond to an interest: neighbours with lower delays are preferred. As the conditions along paths vary, data rates may also be lowered for negative reinforcement to remove a path from the preferred set.

The approach described here operates based only on local knowledge, which seems an important consideration for networks with power-constrained nodes. The authors suggest, as evaluated more completely in the other reading for today, that intermediate processing of data may yield even greater benefits.

Citation: S. Madden, M.F. Hellerstein, and W. Hong, “TAG: A Tiny AGgregation Service for Ad-Hoc Sensor Networks,” Proc. 5th Usenix Symp. Operating Systems Design and Implementation, Usenix Assoc., 2002, pp. 131–146.

Since the data extracted from sensor networks is often in the form of summaries, or aggregations, this paper makes the argument that aggregation of data should be considered, and made available, as a core service on sensor networks. TAG, an aggregation service for ad hoc networks based on the TinyOS platform is presented and evaluated.

The two essential features of TAG are a declarative data collection language, inspired by SQL, and the mechanisms for distribution and aggregation of queries across the sensor network, keeping in mind power, time and other constraints, as well as lossy links. The use of a high level language for data collection allows a number of end-to-end optimizations which result in lower data demands on the network, and easier recovery from data losses in the aggregation process. A classification is presented of different types of aggregate functions, with interesting implications for the processing requirements and sensitivity to network losses, for different kinds of aggregates.

One of the decisions taken for design of the routing protocol is to use only symmetric links; asymmetric links are blacklisted. The authors state that this is a common decision in wireless ad hoc networks, but I am not clear as to why this would be so. TAG uses a tree-based routing scheme, with periodic announcements to keep the tree up-to-date. The number of messages transmitted by a node obviously has significant effects on power consumption, which is why the authors make the argument that it therefore makes sense to process data within the network, a trade-off of power consumed due to aggregation-related processing against that consumed due to message transmission. To minimize transmissions, parents in the routing tree aggregate data from children, received over parent-specified time intervals, before passing it up the tree. In contrast, a centralized aggregation mechanism would require parents to forward every message received from children as-is.

In simulations, it is demonstrated that TAG, at worst, approximates the behaviour of centralized approaches in terms of the number of messages transmitted. At best, with aggregation functions which return single, or small sets, values, it results in an order of magnitude reduction in the number of messages transmitted.

I found this paper was useful in how it made me think about the ways in which application layer abstractions (the query interface) could be optimized in different ways (aggregation functions) over the functioning of a network.

Citation: Katti, S., Rahul, H., Hu, W., Katabi, D., Médard, M., and Crowcroft, J. 2006. XORs in the air: practical wireless network coding. SIGCOMM Comput. Commun. Rev. 36, 4 (Aug. 2006), 243-254. DOI=http://doi.acm.org/10.1145/1151659.1159942

In a similar vein to the other reading for today, the approach presented in this paper, COPE, attempts to take advantage of, rather than work against, the characteristics of the wireless medium. The COPE approach is, however, fundamentally different from the other papers that we’ve read: instead of trying to optimize the routes that a packet takes through a network, COPE attempts to optimize utilization. It does so by coding packets being sent to the same next hop node together into a single packet, increasing the effective bit rate of a network.

COPE relies on knowledge of packets that neighbours may have received in order to perform coding; receivers must have all “native” packets used to form an encoded packet other than the one meant for them. When choosing packets to code, an estimate is made of the probability that neighbours for whom these packets are destined have already heard them. While this would work well in a relatively dense network, a network topology where most nodes are not in range of one another would probably not be served well by COPE.

Packets are coded together only when the probability that they are known to the next hops remains sufficiently high. Note that this also means that COPE will not function well in a network with high degrees of mobility, where neighbours are constantly changing. It is best applied to cases such as that presented in this paper, of fixed nodes connected to form a wireless backhaul. This also means that gains from COPE become apparent only as the diversity of packets increases, which could happen both with increased traffic, but also, I imagine, as the number of source/destination pairs increases.

Various theoretically derived ideal coding gains are presented, showing that the maximum coding gain without opportunistic listening is 2, and with opportunistic listening tends to infinity. Interestingly, the authors found that coding gain increased beyond this value in their testbed, since the queues at bottleneck routers become smaller with the use of coding, fewer packets are dropped at the router’s queue.

The results of testing on a 20-node wireless testbed are presented, with a very useful discussion of how COPE interacts with both UDP and TCP flows. UDP flows see a large throughput gains, in the range of 3-4 times the same network without COPE. Initial tests for TCP showed only marginal gains (2-3%) due to hidden terminal problems causing sufficient collision-related losses to trigger timeout and backoff in the TCP flows. When the nodes were brought closer together to a range where carrier sense could function, an increase of 38% in throughput was observed.

Where most research in this space has continued to emphasize newer approaches to routing, this paper, as the authors put it, presents a new “orthogonal axis” to extracting more throughput. I really liked this paper, both for the compelling ideas it puts forward, and also for the extensive discussion of their implementation.

Citation: S. Biswas and R. Morris, “ExOR: opportunistic multi-hop routing for wireless networks,” in SIGCOMM ‘05: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, vol. 35, no. 4. New York, NY, USA: ACM Press, October 2005, pp. 133-144. Available: http://dx.doi.org/10.1145/1080091.1080108

Biswas and Morris present draw from cooperative diversity schemes to present an alternative to traditional routing mechanisms. Rather than route a packet along a single best possible route, ExOR relays packets along multiple routes. This allows ExOR to take advantage of longer lossy links: even though the probability of packet delivery may be lower on such a link, even the few packets that manage to get through on many of these links can add significantly to overall throughput. Additionally, ExOR sends packets in batches, rather than one at a time, which can improve throughput even on short low loss links. Since probabilistic forwarding may not account for all packets in a batch, ExOR is used until the destination has at least 90% of the packets, and then the remaining are sent using conventional routing.

The sender chooses a subset of forwarders from all nodes in the network (to allow scaling up to larger network sizes) using a metric such as ETX. The forwarders coordinate amongst themselves to ensure that their transmissions do not interfere by setting timers which anticipate when other forwarders, ordered by priority, would probably have completed transmission. For their tests, the authors used a centralized server to maintain and distribute the routing metric. It is not clear from the paper how decentralized relay of the metric might affect ExOR performance. The requirement for ordering of transmissions amongst all forwarders surprised me; if only one node transmits at a time, this would seem to imply an overall loss of network capacity. While the results of the authors’ tests for single large files are compelling, I think it would have been very useful to get some sense of how ExOR would function with multiple sources.

The problem of coordination amongst forwarders aside, the authors also suggest that 802.11 fairness mechanisms would take care of coordination with competing transmissions. It would be useful to have some discussion in class of 802.11 fairness, and how ExOR might work with this.

The principal contribution of the paper, for me, is the way in which a property of the wireless medium which makes it problematic for traditional routing protocols - every terminal can hear every other terminal - is effectively leveraged to make routing more efficient. This is a compelling idea. However, I would really have liked to see some of the details of the protocol worked out a bit more.

Citation: Broch, J., Maltz, D. A., Johnson, D. B., Hu, Y., and Jetcheva, J. 1998. A performance comparison of multi-hop wireless ad hoc network routing protocols. In Proceedings of the 4th Annual ACM/IEEE international Conference on Mobile Computing and Networking (Dallas, Texas, United States, October 25 - 30, 1998). W. P. Osborne and D. Moghe, Eds. MobiCom ‘98. ACM, New York, NY, 85-97. DOI= http://doi.acm.org/10.1145/288235.288256

This paper presents a comparison of four wireless routing protocols used in ad hoc networks - DSDV, TORA, DSR and AODV - with tweaks to DSDV and AODV. Tests are run in a simulator, with a number of scenarios involving nodes moving at varying speeds. The metrics used for comparison are the packet delivery ratio, routing overhead and path optimality.

The most surprising of the four, to me, was TORA, for its in-order delivery requirement, which seems an impractical choice, especially for a wireless environment. Unsurprisingly, TORA fares the worst in the performance tests, with wildly varying performance under similar conditions, and undergoing congestion collapse beyond a certain number of sources in the network.

DSR provides a consistently high packet delivery ratio, closely followed by AODV, albeit both with increasing routing overhead as the number of sources increase (since they are on-demand protocols), though the incremental cost of adding a source does decrease with the number of sources. Even so, the routing overhead for both these protocols is lower than either DSDV or TORA. DSDV also exhibits little variation in the packet delivery ratio, though it does function best under lower degrees of mobility; at higher mobility, it can completely fail to converge. As might be expected, DSDV’s routing overhead remains largely constant.

The discussion of the effect of packet size was interesting: DSR is more expensive than AODV when routing overhead is measured in bytes. However, the cost to acquire the medium for transmission of a packet is much higher than the incremental cost of adding these extra bytes to a packet.

Citation: De Couto, D. S., Aguayo, D., Bicket, J., and Morris, R. 2003. A high-throughput path metric for multi-hop wireless routing. In Proceedings of the 9th Annual international Conference on Mobile Computing and Networking (San Diego, CA, USA, September 14 - 19, 2003). MobiCom ‘03. ACM, New York, NY, 134-146. DOI= http://doi.acm.org/10.1145/938985.939000

This paper, by some of the same authors as the Roofnet paper, presents the idea of the Expected Transmission Count (ETX) metric that was developed further and used in Roofnet’s routing protocol. ETX is evaluated on a 29-node wireless testbed, as an extension to the DSDV and DSR protocols.

In presenting ETX, the authors contrast it to the commonly used metric used in ad hoc networks, minimum hop count. While useful as a metric in wired networks, minimum hop count suffers from a number of flaws when used in wireless networks. The most important of these, perhaps, is the assumption that links either work, or do not; wireless links typically have intermediate loss ratios. Lower hop counts may also maximize the distance traveled per hop, leading to increased signal attenuation and higher probabilities of loss. Finally, a random choice amongst routes with the same hop count is not likely to pick the best route, as the characteristics of the individual links in this route are not taken into account. This last problem worsens as a network grows, and the number of possible paths increases.

To remedy these problems, ETX attempts to find routes which would have the fewest transmissions, and retransmissions, of packets, by measuring packet loss ratios in both directions on each link. Measurement in both directions is important, to account for 802.11b ACKs being sent back along a link, as it is not unlikely that links may be asymmetric to some degree in an ad hoc network. Packet loss is measured as the delivery ratio for a link: the number of packets received, divided by the number of packets transmitted by the sender. Since ETX is designed to minimize the number of packets transmitted, this also results is lower spectrum use, thereby increasing overall network capacity, and a decrease in energy per packet, which is a particularly an important consideration for devices with limited battery life.

From measurements, it appears that packet size is an important consideration which ETX does not account for. ETX sends small probe packets of fixed size to determine link quality, but these are somewhat larger than 802.11b ACK packets, and inevitably much smaller than data packets. As a result, ETX underestimates the delivery ratio for ACK packets, and, more importantly, may overestimate the delivery ratio for large packets.

In order to be useful, ETX makes a few assumptions: that there are link layer retransmissions, and that radios operate on fixed, rather than variable, power levels. Additionally, the authors suggest that ETX may not be responsive to mobility, as link quality may change too quickly for propagation of accurate route metrics. I’m not so sure about this last point; it seems to me that ETX might be a useful addition to a protocol like DSR in a network with high mobility.

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.