"Wireless TCP" is probably a popular prelim question; it also reappears from time to time in conferences; I've thought about working on it myself. The basic problem is at least clearly stated: TCP believes that all packet losses are caused by congestion, but in wireless this is likely to be incorrect. Thus, it does not perform very well over wireless links. The result of this paper is "yes, but local repair fixes the problem."
The authors evaluate a number of different possible solutions; local retransmission and a series of end-to-end modifications. Intuitively, we should be predisposed to local repair for several reasons: since it is closest to the link, it should have the best information about link quality, and should be able to react the fastest to loss. Split connections is a rather heavy weight solution to a not-that-deep problem, and furthermore will use significantly more network resources. SACKs are a worthy modification to TCP, but are best thought of as solving the bursty loss problem, and helping throughput on high bandwidth-delay links.
What this problem essentially comes down to is that, if a link as a Packet Reception Rate of "p", then with "r" retransmissions, the probability of packet delivery when using link-level acknowledgments is 1-((1-p)^r). What this says is that we can make a poor link look like a good link by estimating the value of p on the fly, and tuning r so as to guarantee a certain level of reliability. Of course, this can be complicated by bursty losses, but the intuition is correct.
The results of the paper bare out this intuition; local repair works as well as anything, and end-to-end protocols are hurt by the fact that the controllers are far from where losses are taking place. Split also works almost as well as local, but there is no gain from just running the local protocol directly on the TCP packets.
The upshot of all of this is that when the original internet papers say that the maximum drop rate of a link should be 1% TCP and IP headers which are either destined for an endpoint or else apply to each hop (hop-by-hop options).
Tuesday, September 30, 2008
MACAW: A Media Access Protocol for Wireless Lans's
The authors present their design for a media access control protocol to a shared 256kbps channel. Their overriding design consideration is fairness, and not throughput which is a decisions which appears at numerous points in the paper. They begin with a typical RTS-CTS-DATA scheme very similar to CSMA/CA and then consider a number of modifications to it to address fairness; the sender can contend for the receiver using RRTS, the data can use link-level recovery with ACKs, or the sender can acknowledge the CTS message with a DS message before sending the payload.
The design of a workable MAC is somewhat complicated, and its design will effect power consumption, throughput, latency, and reliability. Of these axis, the authors did a reasonable job evaluating throughput; however the others are not well treated (although low latency can be a function of fair sharing between senders). My main objection to their MAC is the high protocol overhead in the RTS-CTS-DS-DATA-ACK exchange, which occurs even the absence of channel contention. What we have found in our own research is that the authors are exactly right about local repair; the lossy nature of these links makes it inadvisable to just send a packet and assume it got there. However, our lesson has been that the additional packets involved in more complex coordination schemes result in a noisier channel which can be an important effect with many senders. Furthermore, if the data packets are short, the data is effectively piggybacked on the RTS; if it is received at all then no further transmissions are necessary and power consumption is reduced because of fewer sends and receives.
Several things about this paper means that our design lessons are not directly applicable. For one, they use significantly different radio technology with a "near-field" PHY and short range. Second, their workload model is significantly different (they cite a data rate at one point of 64 packets per second). Finally, all communication is to central collection points. Given these parameters, I probably would have tried to reduce contention by designing a protocol for assigning different channels to nearby receivers to reduce cross-cell interference (this should solve the RRTS problem) and evaluated weather or not the full scheme they propose is necessary in practice.
This brings us to a final criticism of the paper, which is its evaluation methodology. MAC protocols have been shown to be very sensitive to workload and environmental factors; if a protocol is designed for a specific workload and environment, it would be significantly more convincing to have implementation results for that environment then packet-level simulation. Modeling RF communication is notoriously difficult and there is still active work in conferences improving the simulation in ns-2 and TOSSIM. The implementation results, even if simplistic, are an important sanity check.
The design of a workable MAC is somewhat complicated, and its design will effect power consumption, throughput, latency, and reliability. Of these axis, the authors did a reasonable job evaluating throughput; however the others are not well treated (although low latency can be a function of fair sharing between senders). My main objection to their MAC is the high protocol overhead in the RTS-CTS-DS-DATA-ACK exchange, which occurs even the absence of channel contention. What we have found in our own research is that the authors are exactly right about local repair; the lossy nature of these links makes it inadvisable to just send a packet and assume it got there. However, our lesson has been that the additional packets involved in more complex coordination schemes result in a noisier channel which can be an important effect with many senders. Furthermore, if the data packets are short, the data is effectively piggybacked on the RTS; if it is received at all then no further transmissions are necessary and power consumption is reduced because of fewer sends and receives.
Several things about this paper means that our design lessons are not directly applicable. For one, they use significantly different radio technology with a "near-field" PHY and short range. Second, their workload model is significantly different (they cite a data rate at one point of 64 packets per second). Finally, all communication is to central collection points. Given these parameters, I probably would have tried to reduce contention by designing a protocol for assigning different channels to nearby receivers to reduce cross-cell interference (this should solve the RRTS problem) and evaluated weather or not the full scheme they propose is necessary in practice.
This brings us to a final criticism of the paper, which is its evaluation methodology. MAC protocols have been shown to be very sensitive to workload and environmental factors; if a protocol is designed for a specific workload and environment, it would be significantly more convincing to have implementation results for that environment then packet-level simulation. Modeling RF communication is notoriously difficult and there is still active work in conferences improving the simulation in ns-2 and TOSSIM. The implementation results, even if simplistic, are an important sanity check.
Tuesday, September 23, 2008
Scaling Internet Routers Using Optics
McKeown again presents a router architecture, except this time using optics. He begins with the claim that the centralized crossbar and scheduler approach from his previous paper does not scale; this is believable because of the n^2 complexity of the matching problem necessary to efficiently switch packets, and also an argument that multistage systems lead to unpredictable latencies.
He presents his new queuing design, where multiple sets of input queues are connected to output queues cyclically; I think the goal there is to reduce the non-determinism so that the switch can run faster with more predictable latency. He also considers power to be the limiting factor of how much equipment can be stuffed into a rack.
I find it difficult to tell what the magnitude of this paper's contribution is; it seems like it could be either a seminal work laying out a new architecture, or a pie-in-the-sky paper which could never be implemented.
He presents his new queuing design, where multiple sets of input queues are connected to output queues cyclically; I think the goal there is to reduce the non-determinism so that the switch can run faster with more predictable latency. He also considers power to be the limiting factor of how much equipment can be stuffed into a rack.
I find it difficult to tell what the magnitude of this paper's contribution is; it seems like it could be either a seminal work laying out a new architecture, or a pie-in-the-sky paper which could never be implemented.
A Fast Switched Backplane for a Gigabit Switched Router
McKeown presents a series of design decisions to allow high throughput between different ports on a network switch. He points to trends in router design towards more hardware, more parallelism, and fewer shared buses to reduce contention, and so argues that a switched backplane will be best because it reduces contention. His design consists of a star topology where each line card is connected to a single switch. The switch can connect pairs of cards, and so the challenge is to quickly form a matching between enqueued messages and receive buffers which minimizes latency and is fair. The algorithm he proposes is called iSLIP, and consists of multiple rounds of proposals after which the switch can choose a conflict-free match.
He is especially interested in reducing block; HOL (head of line) blocking is particularly problematic. To solve that, he introduces the VOQ, or virtual output queue where each card has multiple output queues, one for each other line card. In this scheme, a packet can never become blocked behind a packed destined for a different port. He also notes that a combination of queuing discipline (in the sense of more VOQs + priorities) has the same effect as more speedup (running the switch at a multiple of the line card speed.
This paper outlines the full design of a small switch; I thought it was an interesting read. The techniques he mentioned are probably still valid today, since a 16-way 2.4 Ghz switch is still a reasonable piece of hardware. It was light on details, and parts were confusing; the frequent note that the Cisco 12000 uses some of the techniques didn't actually contribute to the paper, because he does not go into detail other then the general design of that system.
He is especially interested in reducing block; HOL (head of line) blocking is particularly problematic. To solve that, he introduces the VOQ, or virtual output queue where each card has multiple output queues, one for each other line card. In this scheme, a packet can never become blocked behind a packed destined for a different port. He also notes that a combination of queuing discipline (in the sense of more VOQs + priorities) has the same effect as more speedup (running the switch at a multiple of the line card speed.
This paper outlines the full design of a small switch; I thought it was an interesting read. The techniques he mentioned are probably still valid today, since a 16-way 2.4 Ghz switch is still a reasonable piece of hardware. It was light on details, and parts were confusing; the frequent note that the Cisco 12000 uses some of the techniques didn't actually contribute to the paper, because he does not go into detail other then the general design of that system.
Wednesday, September 17, 2008
Supporting Real-Time Applications
This second Clark, Shenker, and Zhang paper presents a queueing algorithm and architecture for differentiated services. The conceit is separating traffic into two classes, one with real-time requirements and one with more flexible latency requirements. To do so, they allow the network to make service commitments, essentially providing admission control and resource reservations. They also propose a new queuing discipline, FIFO+ to address sharing between flows.
This work seems incomplete, at best, to me. The authors mention off-hand that a pricing model will be essential to provide proper incentives for the system to work correctly, yet there is no discussion of how this would fit into the rest of the scheme. Even Shenker admits in his later paper that this work is particularly unmotivated; one does not get a sense that the complexity introduced here is necessary. Furthermore, the evaluation is lacking, given the incomplete architecture presented. The largest contribution may be the paper's identification of "predicted service" applications; it seems that all internet applications may enter this class by attempting to compute the network capacity available to them on the fly.
This work seems incomplete, at best, to me. The authors mention off-hand that a pricing model will be essential to provide proper incentives for the system to work correctly, yet there is no discussion of how this would fit into the rest of the scheme. Even Shenker admits in his later paper that this work is particularly unmotivated; one does not get a sense that the complexity introduced here is necessary. Furthermore, the evaluation is lacking, given the incomplete architecture presented. The largest contribution may be the paper's identification of "predicted service" applications; it seems that all internet applications may enter this class by attempting to compute the network capacity available to them on the fly.
Fundamental Design Issues for the Future Internet
This 1995 paper by Scott Shenker takes a step back from the networking research of the day and tries to predict what architectural changes will be necessary for the Internet to scale into the next decade. At that time, the internet had about 3 million hosts and tens of thousands of web sites; its transition from academic curio to a piece of public infrastructure was well underway. The challenge he focuses on is Quality of Service (QoS) guarantees, with the driving applications of streaming audio and video. The architectural question behind these demands is the questions of weather or not new service models are necessary for these applications to succeed. While IP provides best-effort delivery, real-time applications might benefit from bounded latency. The solutions he explores are admission control and fair queuing within the network core.
He considers the alternatives and problems with a differentiated services model: the largest problem is fairness, in the sense that end users would have no incentive to request anything less then the best service, which would defeat the point of the service model. The only solution he proposes is the only one that probably has any chance of working: charging different service classes different amounts for their utilization. However, this paper does not seem to seriously believe this will emerge as an evolution of the internet. Shenker also seriously considers maintaining the existing best-effort service model while over provisioning the network to allow latency and bandwidth sensitive applications to perform well; footnote 12 where he contends that if "bandwidth does become extremely inexpensive, some of our design decisions will be altered. It might be preferable to merely add bandwidth rather then extend the service model." is prescient.
With the benefit of hindsight, it appears that internet architects may have overestimated the cost and difficulty of modifying the IP model; even the roughly contemporaneous IPv6 transition has yet to have a major impact. The basic conservatism of network operators and the choice between new, untested technology that might improve utilization versus a lot more of the old technology (more pipes) has so far been answered in favor of the well-understood solution of adding more bandwidth; moreover, with good results.
To argue that the only way the internet has adapted to the demands of realtime traffic in the past ten years would be simplistic. The emergence of traffic-shaping middle boxes near endpoints to effectively prioritize traffic based on deep, stateful packet inspection is one development; another is the proliferation of content delivery overlay networks which geographically distribute latency-sensitive content to put it closer to consumers is another. Both of these have apparently been easier to do then modify the underlying network model.
He considers the alternatives and problems with a differentiated services model: the largest problem is fairness, in the sense that end users would have no incentive to request anything less then the best service, which would defeat the point of the service model. The only solution he proposes is the only one that probably has any chance of working: charging different service classes different amounts for their utilization. However, this paper does not seem to seriously believe this will emerge as an evolution of the internet. Shenker also seriously considers maintaining the existing best-effort service model while over provisioning the network to allow latency and bandwidth sensitive applications to perform well; footnote 12 where he contends that if "bandwidth does become extremely inexpensive, some of our design decisions will be altered. It might be preferable to merely add bandwidth rather then extend the service model." is prescient.
With the benefit of hindsight, it appears that internet architects may have overestimated the cost and difficulty of modifying the IP model; even the roughly contemporaneous IPv6 transition has yet to have a major impact. The basic conservatism of network operators and the choice between new, untested technology that might improve utilization versus a lot more of the old technology (more pipes) has so far been answered in favor of the well-understood solution of adding more bandwidth; moreover, with good results.
To argue that the only way the internet has adapted to the demands of realtime traffic in the past ten years would be simplistic. The emergence of traffic-shaping middle boxes near endpoints to effectively prioritize traffic based on deep, stateful packet inspection is one development; another is the proliferation of content delivery overlay networks which geographically distribute latency-sensitive content to put it closer to consumers is another. Both of these have apparently been easier to do then modify the underlying network model.
Monday, September 15, 2008
XCP
XCP is designed to deal with links with very high bandwidth-delay products. The authors claim that TCP will inevitably become unstable when run over these links; their claim is based on the fact that once the feedback period is too long, TCP will exhibit oscillatory behavior as it increases its congestion window, only to be forced to dramatically decrease it once the link becomes congested; however, the feedback loop is so long that it will have already injected a good deal of data when it receives the control signal. They also argue that slow start is too slow for these links.
As a solution, the authors propose to separate utilization and fairness policy goals, and to provide them with different policies: MIMD and AIMD. Multiple-increase multiple-decrease allow the protocol to quickly grow the amount of bandwidth a connection uses, while the multiplicative decrease still allows quick response to congestion. Further, by adding the congestion window to the transmitted data, senders and receivers gain a better information about the congestion state of the network; effectively extended the one bit of feedback other algorithms use.
One great point of the paper that the authors emphasize is the protocol's TCP-friendliness. I think this is essential for modern transport protocols; no one would risk deploying a new protocol if they did not have at least a reasonably well-founded believe that it would not clobber existing streams. Much of the rest of the paper is the necessary boilerplate to show that the protocol achieves its design goals. However, it's not really clear that the need for this protocol in the wide area has emerged since it was presented in 2002. While there certainly high latency links, often the TCP sessions running over them are just one in a sea of many others. If this is uses anywhere, I would expect it to be in special computing facilities like data centers, supercomputers, and potentially between installations like the various national supercomputer centers.
As a solution, the authors propose to separate utilization and fairness policy goals, and to provide them with different policies: MIMD and AIMD. Multiple-increase multiple-decrease allow the protocol to quickly grow the amount of bandwidth a connection uses, while the multiplicative decrease still allows quick response to congestion. Further, by adding the congestion window to the transmitted data, senders and receivers gain a better information about the congestion state of the network; effectively extended the one bit of feedback other algorithms use.
One great point of the paper that the authors emphasize is the protocol's TCP-friendliness. I think this is essential for modern transport protocols; no one would risk deploying a new protocol if they did not have at least a reasonably well-founded believe that it would not clobber existing streams. Much of the rest of the paper is the necessary boilerplate to show that the protocol achieves its design goals. However, it's not really clear that the need for this protocol in the wide area has emerged since it was presented in 2002. While there certainly high latency links, often the TCP sessions running over them are just one in a sea of many others. If this is uses anywhere, I would expect it to be in special computing facilities like data centers, supercomputers, and potentially between installations like the various national supercomputer centers.
Subscribe to:
Posts (Atom)