Improving TCP Performance Over Wireless Links

In this paper, the authors compare several methods for improving wireless TCP performance, divided into three major types: end-to-end, link-layer, and split-connection. The end-to-end protocols require both ends to modify normal TCP; the link-layer protocols use the wireless link layer to improve performance, mostly by being aware of TCP's semantics; and the split-connection protocols give the non-wireless end the appearance of a non-lossy network connection, while dealing with loss by itself.

The major failing of TCP when it comes to wireless lossy networks is that packet loss in TCP indicates congestion, and rarely in wired networks do packets actually get lost. Thus, the basic strategy is to deal with packet loss through some other mechanism, not indicating that congestion is occurring.

My major criticism is that the division of these modifications is dealt with by having each category treaded in its own section, with not as much comparison across the various strategies until the last section. I think more detail in how the different strategies compare would have been useful; this is more of a organizational problem and less a research question.

Overall, I think the most promising is the link-layer schemes which perform the best (I believe). The end-to-end protocols give good performance, but because they require changes at the ends, it seems impractical to implement. In addition, the ELN enhancement seems difficult to implement, even given their suggestions. The split-connection protocols, at least as implemented here, do not perform well.

MACAW

This paper presents a protocol for a specific kind of wireless network and its interactions with wired TCP. In particular, the test case is an actual network of wireless pads that are mobile and move room-to-room, with relatively small footprints of communication. The base stations are in the ceiling of the rooms, leading to the low range (since the communication is always >6 ft apart). Interestingly, the paper says that noise is not one of their major design points; I think this is somewhat unrealistic, given the noise sources present in all offices (microwaves, speakers, etc.)

The protocol designed starts off as something relatively simple: an RTS-CTS-MSG sequence.

After that, the designers use a number of scenarios to add on to their protocol, including adding ACKs, adding a Data-Send to let others know a message exchange is occurring, adding an RRTS, and so on. Although each is motivated by a specific example, the end result is a convoluted algorithm which has quite a complicated flow even in the usual case. Something so complicated gives many opportunities for flaws.

In addition, I'm not sure how handoff works in this algorithm. Since the ranges are so small, it seems like handoff would be something that occurs often.

Supporting Real-Time Applications in ISPN

Written around the same time as the previous paper, this one attempts to design a network infrastructure for three different classes of service: guaranteed (delivery within a certain advertised latency limit), predicted (give some guarantee based on the level of traffic), and usual datagram traffic. Based on the desire to route these classes, the network is built to work with two kinds of real-time applications: ones that adapt and can tolerate some increased latency, as well as applications that do not adapt and are intolerant to increased latency.

WFQ is used for the guaranteed class, but the paper points out that FIFO is actually better than an FQ-type algorithm when it comes to predicted service because FIFO, in some sense, "distributes" the bursty penalty over all the flows in the router, while WFQ penalizes the bursting one only; predicted service prefers a small penalty to all over a large penalty to a single flow.

One major result here is a new kind of FIFO (called FIFO+) queuing that attempts to make packets operate in a FIFO manner over all links in the path. This allows the network to route

the predicted class well. However, such an algorithm requires distributed control data; for each flow one has to have enough control to know which packets deserve to be routed first. In addition, any advertised delay must be an aggregate of delays on the path; this also involves communication and control record-keeping across any flow before it is actually allocated. These seem like large inefficiencies.

Overall, the algorithms in the paper do meet their goals in some sense. Given, however, the large increases in bandwidth as well as the major changes required in this proposal, it is no wonder it has not been implemented. Along with the large changes required in routing etc., there is also the need for additional record keeping for billing as well as other non-technical aspects that just seem impossible to overcome.

Fundamental Design Issues for the Future Internet

Looking at the future from 1995, about the time the Internet was being commercialized, this paper examines design issues going forward from services that are latency-tolerant ("elastic" in their designations) to services like video and audio, which require a better "class" of service. The paper advocates changing the network to accommodate different service types. Building a framework to evaluate different implementations, the paper introduces a measure that maximizes the "utility" of all flows--- with some flows requiring real-time service and others with less strict requirements.

A result of this paper is that sharing between flows that need fast service and elastic flows actually is more efficient than having separate networks for the two types of service. In addition, it is unrealistic to have the network "detect" the required type of service, so the network has to expose some kind of interface for the applications and users to request the types of service.

Two major problems with having different kinds of service is 1) how do you get people to settle for lower-levels of service and 2) how do you get ethernet/ATM/etc to support different classes of service. The first problem is fundamental in that one must incentivize things such that higher levels of service cost more--- the author rightly points out that this is going to require a huge culture change. In fact, the culture change is so large that I'm not sure it could be brought about, except if it was through services people already pay for (cable tv, for example). Asking for more money for services users are used to having for free is pretty insurmountable in the context of the internet.

Moreover, as Shenkar points out over and over, his analysis is based on bandwidth continuing to be expensive. Many of these concerns go away if bandwidth can be increased by a huge amount; however, I think the desire for low-latency class of service still remains today, but for applications such as gaming, the issue is not high bandwidth, but just having low latency. Thus there is a spectrum of latency and bandwidth requirements that would benefit from having different classes of service.

But while the Internet remains "good enough," this won't happen, especially given the invasiveness of the changes required. Even Ethernet wouldn't work. I don't have much critical to say about the paper, as it is more setting up a framework, one that I believe is reasonable given the concerns at the time.

Congestion Control for High Bandwidth-Delay Product Networks

EXplicit Control Protocol, XCP, is introduced in this paper as a bottom-up redesign of congestion control without the limitations of TCP. By allowing a better feedback mechanism than dropping packets (in fact making the feedback an explicit part of the underlying protocol, and not dropping packets at all), XCP better communicates both over- and under-utilization of resources to clients by modifying packet headers at intermediate gateways and having clients react based on the feedback. Separating out efficiency and fairness issues into two different controllers, an XCP gateway attempts to gain the best efficiency in a fair manner; the EC decisions are implemented by feedback given by the FC.

The best summarized explanation of the two controllers is that the EC uses Multiple-Increase Multiple-Decrease to rapidly hit efficiency targets, and the usual AIMD to converge to fairness. Most interestingly, the parameters for XCP can be set once for all workloads, and do not depend on the kinds of traffic the gateway receives, unlike RED.

The performance of XCP is explored in several simulations, and it achieves extremely high efficiency for any number of flows, as well as good fairness--- always much fairer than TCP. The one downside in the performance section is that it seems to be a bit less efficient than some of the other algorithms; the paper says it "trades a few percent of utilization for a considerably smaller queue size" but I fail to see the advantage of having smaller queue sizes if utilization is not being fully reached.

Of course, XCP is not TCP and integrating the two is covered in the paper to some extent. Gradual deployment would require gateways that understand both protocols and performed some fairness calculations between the two; this intermediate level of implementation seems much too complex, but unavoidable given TCP's hold.

The paper shows how congestion control "should" have been designed into routers and the protocol, as opposed to how it was integrated after the fact into TCP due to the discovery of failings of the original underlying algorithm.

Random Early Detection Gateways for Congestion Avoidance

Taking the viewpoint that the gateway is the best place to determine whether congestion is occurring, and that a gateway-based congestion avoidance scheme is tractable if it has little per-connection state, the RED paper proposes to control congestion by maintaining a stable average queue size that can temporarily increase in response to transient congestion. RED gateways keep the queue sizes between two threshold values by marking packets with some probability when in the correct range (to prevent queues from getting too big), and marking/dropping all packets when the maximum threshold is exceeded.

This results in essentially two algorithms, one for accommodating burstiness, and another for maintaining a particular level of traffic. I found it somewhat odd that these algorithms are packet based, as opposed to being byte-based; in fact the way they attempt to mitigate for this is modify the algorithm to mark proportional to the packet size; this is not quite the same as making the queue calculation byte-based, however.

The simulation results show that RED accomplishes its goals of maintaining average queue size and dropping packets with less bias against burstiness. Given TCP's limited feedback mechanism (dropping packets is really the only indication of congestion), the simulations demonstrate that RED utilizes packet dropping well in order to avoid congestion, by showing that when congestion begins to occur, the system drops packets, and the result is a reduction in average queue size.

RED is not fair in the max-min sense. In fact, the authors say fairness is not "well-defined," but I think there are reasonable fairness metrics--- RED does not in anyway guarantee fairness or ensure equitable utilization of gateway resources. Like all the congestion avoidance schemes we've looked at, it assumes cooperative clients and does not deal with malicious users.

In addition, it is quite sensitive to parameter selection, and different parameters seem to work for different workloads. The authors do provide some guidelines for parameter selection, but it is not clear how the interaction of the different parameters works with different traffic characteristics. Thus it seems more of a matter of "guess and check" to figure the optimal way to configure the routers for each kind of traffic.

Overall, given the limitations of TCP and the desire to have a simple algorithm that prevents congestion, RED is an interesting and useful simple way to maintain performance in the face of approaching congestion.

Core-Stateless Fair Queueing

In this paper, a simpler queueing algorithm is proposed that divides routers into "core" and "edge" routers: the edge ones essentially are inter-AS while the core ones are within an AS. In this regime, only edge routers require per-connection state, and such routers insert some state into packets as they traverse into an AS (or, in this paper's terms, an "island" of routers). Core routers are stateless with respect to outside connections, but do queueing based on the information from the headers.

The basic outline of the algorithm uses flow arrival rates, estimated and weighted using exponential averages. This is interesting, but I am not clear on why it is the right thing to do, other than the authors asserting that using constant parameters results in wrong behavior.

The overall algorithm seems somewhat complicated, but since the edge routers are much fewer than the core routers, most routers can be implemented without having to do complicated state manipulation and computations. It is not as fair as the previous paper's algorithm, but requires less computation per packet. The algorithm does punish ill-behaved hosts, which is a good property.

In simulation, the CSFQ algorithm does quite well, and although it is not as fair as the more complicated WFQ, it behaves rather fairly. However, although some routers don't have to be super-complex, the edge ones do, requiring packet classification mechanisms. How much of an improvement this is over FQ is not clear. In addition, I believe Moore's Law outpaces bandwidth increases, so all the computation involved in FQ may not be a problem.