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.

Analsis and Simulation of Fair Queueing

This paper introduces a FQ algorithm that replaces the usual first-come first-served queueing of routers. The FQ algorithm gives each active connection a "fair" share under the max-min definition of fairness, and, with the promptness modification, prioritizes low-bandwidth links. This makes sense since such links usually are interactive connections that should be serviced in a prompt manner.

I would say the analysis of the algorithm is somewhat simplistic, but the fact is that there are many possible ways to analyze any queueing algorithm, and having just two types of connections is good enough to show some of the behavior characteristics. The most interesting result here is that the queueing algorithm on its own is not the only important parameter; one must also take into account the flow control algorithm. In fact, queueing by itself does not "fix" network behavior; interaction with flow control is important.

Under FQ, using "generic" flow control gives you less than your fair share--- the authors frame this as an incentive, but a contrarian view could look at it as a weakness of the algorithm. I think a better algorithm would penalize "generic" flow control but would only penalize misbehaving hosts which do not perform flow control or try to overuse their fair share.

In addition, the authors say that under other scenarios result in confusing behavior; an example would be useful. Overall, the paper is good in showing that more sophisticated queueing and flow control can result in fairer service, but the large weakness here is that routers must perform quite a bit of work, including maintaining per-connection state, that may slow down the routing overall.

Congestion Avoidance and Control

In response to the 1986 overcongestion of the internet, the 4.4BSD stack was changed to control congestion. This paper explores the major changes and reports on the results through empirical experiments. In particular, the paper uses a concept from flow theory that says that a flow should be conservative, which is violated under three conditions; each condition is dealt with by a separate algorithm. First, the implement "slow start" that allows communications to reach equilibrium by starting out sending a single packet and then ramping that up as acks are received.

To avoid unnecessary injections, the authors point out the retransmit timer must be well-designed and take into account the variability of the network as well; a simple modification to the usual filter fixes this by estimating the variance at each point. Lastly, they introduce the congestion avoidance technique used in TCP stacks, which has its roots in the previous paper. Both use additive increase/multiplicative decrease, but the TCP algorithm is clever in that it requires no global state and just uses lost packets as the network congestion signal. No feedback from the gateway or router is required.

This paper is quite interesting in that it presents refinements to each algorithm (much of it is not new) and then presents how the new algorithms fare in actual network performance. It is a validation of the congestion avoidance regimes in the previous paper as well. In terms of its importance historically, the paper was of course instrumental in making the internet more robust in the face of capacity. Again, however, the paper assumes friendly/non-malicious clients; how this works in the face of malice is unclear. In particular, the gateway would probably need to be involved; not following the endpoint behaviors outlined could be a simple signal for gateways to shut down a malicious user.

Analysis of Increase and Decrease Algorithms for Congestion Avoidance

The authors of this paper analyze algorithms for congestion avoidance using very limited feedback from the global resource--- a single bit sent from the router that indicates whether the network is overloaded or underloaded. Each sender reacts independently (and in a trustworthy manner) with some policy that reflects the goals for the network (such as efficiency, fairness, etc.). In analyzing the potential algorithms, the authors look at policies are reflecting linear space (they do talk a little bit about nonlinear versions, but rightly point out that they may be too complicated); that is, you can add or multiply or do a combination of the two.

The corresponding diagrams on a plane are extremely informative, and intuitively explain some of the conclusions of the paper. For example, the authors advocate additive increases and multiplicative decreases, showing that they converge to optimality in terms of efficiency and fairness. This is because the multiplicative decreases take the network closer to fairness, while the additiveness makes the network more efficient.

Although this paper does not deal with TCP per se (the next one does), the congestion avoidance here is important to study because it was later used to improve TCP's performance, which suffered several meltdowns as the early internet reached higher percentages of capacity.

The paper is essential even just for the graphical explanations of the various congestion avoidance schemes. These help explain the algorithm's relative effectiveness, and, when the algorithm less than ideal, where/why it breaks down. However, the paper does not go into the specifics of what the parameters should be--- this would require some kind of simulation. Still, a specific example that shows behavior for some sets of patterns would be useful. In addition, how are the parameters related to the network parameters (things like bandwidth, latency, number of nodes, etc.)? Even broad relationships between network and optimum congestion avoidance policy would be interesting. Lastly, of course, this requires some sort of global state at the router level in order to send feedback to the endpoints.

Given all of that, I think the essential point of the paper is important to remember: to converge to optimum efficiency and fairness, one should use additive increase and multiplicative decrease.

Inferring AS Relationships in the Internet

In this paper, the authors attempt to "map" the relationships between autonomous systems and the ways they interact through routing. First, the paper defines the different kinds of relationships between AS's, similar to how the Interdomain paper defines them, although this paper has several additional relationship types. Then, the paper shows how to construct a graph of the AS's where each AS is a vertex and their relationships are expressed as edges.

This is done by considering the way routing is related to the relationship. For example a customer will not want to route its provider's routes; seeing how the routing between the two is expressed tells us something about how the AS's are related. By using heuristics, the authors are able to map the AS's quite well.

Admittedly, some of the details were over my head in terms of how the graph is constructed, but I understood the gist. This is not a fault of the paper, but moreso due to my relative ignorance of BGP. I understood most of how the policies express relationships; I think the paper does a good job of formally detailing how policy and relationship can be used to interchangably.

The confirmation of their results, however, left me scratching my head. "As much as 99.1%" is quite an ambiguous number; this could be anything between 0 and 99.1. Furthermore, they don't specify what kinds of information AT&T internally has, or how it got it--- are their relationships accurate? If they only deal with AT&T's connectivity, then we can assume they are accurate, but what percentage of inferences does that cover? I was unsatisfied by their metrics in this sense.

Interdomain Ineternet Routing

This paper discusses the post-commercialization routing between different networks occurs by describing the possible relationships between domains and how BGP is used to exchange/propagate information from one to another. In addition, the paper describes how policies for inter-domain routing are implemented by modifying BGP entries when importing or exporting them.

The entire process is quite complex, and there are no rules per se for how providers import/export routes. I think the paper does a good job explaining the complexities by starting with an explanation of different kinds of inter-AS agreements; this helps explain why distributing routing information is not simple and intuitive. BGP is explained well, and although is a simple point-to-point algorithm, has complexities that arise mostly in import and export rules.

Clearly BGP is one of the aspects of the internet that has room for improvement. Because of all the odd complexities of the internet architecture, I'm not convinced that a point-to-point protocol is the only way. Even within a domain, having some kinds of collective decision-making would possibly be more efficient in the end; some kind of distributed data structure (with sufficient replication) such as a dist hash could make routing more robust against failures.

The paper itself was excellent for introducing the issues with interdomain routing and BGP; I knew very little of the details of the post-commercialization realities of routing.

Design Philosophy of the DARPA Internet Protocols

(link to paper)

By outlining the goals of the Internet protocols and explaining how the features of the protocols come from the design goals, this paper gives insight into the historical decisions made in developing IP, TCP, and UDP. Since the major purpose was to connect disparate networks with very different underlying media and protocol guarantees, IP took little functionality as given. Based on secondary purposes, a number of decisions, such as using a "stateless" protocol (for survivability) and layering protocols with stronger features on top of IP.

The paper also goes into some of the goals the protocols did not meet very well, some of which has changed since the paper was written. For example, accountability has become much more robust, with routers etc. having the ability to record detailed usage statistics. Others, however, like engineering issues, remain. Implementing a protocol stack is still quite difficult, requiring more than just following a spec due to performance issues.

As a historical document, the paper is essential because it shows some of the background in the decision-making process for IP, but a more updated version would go into some detail explaining how the state-of-the-art has changed, enhancing some of the goals while making others less important. For example, I think the modern IP implementors do keep some state ("soft state") at intermediate points. In addition, some detail on TCP's problems and solutions, although possibly out of scope, would drive home some of the kinds of things implementors need to be cognizant of.

An additional paper going into TCP motivations and issues would be sufficient to cover that shortcoming.

End-to-End Arguments in System Design

(link to paper)

The recurring argument/theme in this paper is that lower-level layers of system design are often not the best place to provide functionality like encryption, guaranteed message delivery, etc. because higher-level applications have more knowledge and may therefore need to replicate the functionality. In addition, the cost of providing some of these services at a low level is higher than building them at the application ("end") level.

As an example, a banking application may need to know that a withdrawal message was received by the server; the best way to do this is probably not through a low-level guaranteed message layer, since the message could be corrupted or tampered with in between the time it reaches the low-level messaging system of the server and the time the application receives it. What really needs to occur is that the application must acknowledge receiving (and acting on!) the withdrawal message.

I believe the general principle the paper espouses. However, I think (and the paper acknowledges this) the difficulty is in figuring out the "ends." How do we determine what they are? In addition, what is the argument in the context of layered messaging such as that in TCP/IP? Does it make sense to, instead of treating applications as the ends, treat layers as ends and build applications on top of the layers? When should a layering be used?

I think the paper leaves the determination of ends up for discussion, but as a discussion tool, it is perfect for the syllabus because it opens up space to discuss which functionality is essential and whether the cost of providing further features is worth the cost at each level. In that sense, the goal of the paper is to push designers to examine the costs of each function and whether it must be replicated before implementing it into the lower-level layers of the design.