Internet Congestion Control for Future High Bandwidth-Delay Product Environments May 25, 2009

This paper discusses XCP, a proposed successor to TCP which provides much better behavior than TCP by increasing bandwidth utilization, reducing bottleneck queueing, and drastically reducing packet loss, especially over networks with high bandwidth-delay products.

The main points of the paper were as follows:

1. The most significant insight provided by this paper is that TCP tries to do too much at once. By separating efficiency and fairness, XCP is able to better serve both goals. This is primarily because optimizing efficiency and fairness require two different algorithms. Optimizing efficiency is best served by a multiplicative-increase multiplicative-decrease (MIMD) system, which allows XCP to quickly converge on maximum utilization of the available bandwidth by all flows. Optimizing fairness, on the other hand, it best served by an additive-increase multiplicative-decrease (AIMD) system, which converges to a fair solution. Since TCP only uses AIMD for all efficiency and fairness requirements, it is sluggish when trying to take advantage of all of the available bandwidth.
2. In addition to allowing different algorithms for efficiency and fairness, splitting the goals also allows modifying one system without affecting the other. This is useful in multiple contexts. For example, it is possible to modify the fairness controller to take advantage of pricing information to allow usage-based billing and bandwidth allocation. It is also possible to use a different fairness controller, like one based on a binomial law, in order to try to optimize fairness in different situations. This simplifies the design and testing of different algorithms because the amount of code that has to be modified is reduced and there is no risk of damaging efficiency while modifying fairness.
3. While XCP is a very effective system, it is all for naught if it cannot be deployed efficiently. The authors of the paper provide two different ways that XCP can be incrementally deployed. The first is as a cloud within a TCP network. This would allow an ISP to deploy XCP within their administrative domain while the rest of the Internet remained primarily TCP-based. This would benefit ISPs because of the fairness options allowed under XCP. Some ISPs are already trying to implement usage-based billing/allocation, and XCP would facilitate that through its fairness controller design. The other option is to modify XCP routers to handle TCP traffic as well, balancing TCP and XCP traffic using a weighted fair-queuing approach. This is somewhat similar to the dual-stack IP situation, where more and more routers are having to handle two similar, but distinct, classes of traffic fairly.

The biggest weakness of this paper is that many of the parameters seem to be based on theoretical results. Normally this is the thing lacking from papers, which tend to use “stochastic optimization” to pick algorithmic parameters. However, in the case of this paper, it might be nice to see a chart where they try their optimal parameters against others to verify that they are indeed optimal.

Future research on XCP should look at various fairness algorithms in order to determine which are best for deployment on the Internet at large, with its large number of traffic classes and diversity of users. Research could also examine all of the various control parameters to verify that they still apply on the Internet as well.

Congestion Control for High Bandwith-Delay Product Networks May 25, 2009

This paper by Katabi et al. proposes a novel approach to congestion control as a successor for TCP. The approach is a clean-slate design, which tries to solve the problem of congestion with support from network routers. Possible deployment paths for this new protocol (XCP) are also indicated.

The major contribution of this paper is to decouple utilization control from fairness control and to distinguish between congestion losses and error losses. Congestion notifications are now explicit in the packets and the protocol infers from the congestion notifications around a packet loss whether it has been caused by congestion or by errors. The decoupling of the two control mechanisms allows the routers to change the fairness control based on business decisions without touching the necessary utilization control.

The proposed XCP protocol introduces a new congestion header for its packets, which carries the relevant information to handle congestion on the network: the sender’s congestion window, its RTT estimate and an initial demand for increasing the congestion window. Routers on the path between sender and receiver may now change the last field according to their congestions, and can therefore get a sender to increase or decrease its congestion window. By carrying this information, the routers on the way have the complete information about the sender’s view on the path and can set the feedback field accordingly.

In the evaluation of XCP, the authors present a number of advantages over TCP, most notable are the reduction of packet drops and the higher utilization independent of bandwith or round-trip delay. Also, a sender not behaving according to specification, e.g. not reacting according to feedback, can be detected in a few RTTs.

The most glaring problem of the work is probably the section on gradual deployment, I think the authors underestimate the overhead burden their proposals impose on routers.

Future work could include researching further mechanisms for fairness control, especially when looking at flows handling streaming applications such as on-demand video. In theory, those streams could be favored by routers because their bandwith requirements only change little over time and therefore create less overhead in the routers.

Congestion Control for High Bandwidth-Delay Product Networks May 25, 2009

(i) Three most important things

1. TCP becomes inefficient and susceptible to instability in high bandwidth delay product networks. The additive increase of 1 packet per RTT is too slow and the increase in link capacity does not improve the transfer delay of short flows. The paper proposes a new protocol known as XCP designed to be efficient, fair, scalable, and stable as the bandwidth-delay product increases.

2.  Packet loss is a poor signal of network congestion. Loss is bad because congestion is not the only source of loss and because a definite decision that a packet was lost cannot be made quickly. XCP has the routers inform senders about the degree of congestion instead of a single-bit congestion notification. Every router along the path can update the congestion header in the XCP packet and the sender can then use the feedback information to increase or decrease its send window.

3. Efficiency control (control of utilization or congestion) should be decoupled from fairness control. Robustness to congestion requires the behavior of aggregate traffic to be independent of the number of flows in it. XCP uses an efficiency controller (EC) to ensure that all spare bandwidth is being used and a separate fairness controller (FC) to set the feedback values proportionally to ensure that all flows are receiving equivalent bandwidth.

(ii) Most glaring problem

The most glaring problem would be that deploying XCP would require a makeover of both end systems and routers. All the routers along the path would need to be reimplemented so that routers can update the congestion header in the XCP packet and the end systems would need to be reimplemented to handle the feedback information from the congestion header.

(iii) Future Research Directions

Future research directions for this work would be to simulate the gradual deployment of XCP and report results and any issues that arise. The fairness between XCP and TCP competing on the same network should be included.

Internet Congestion Control for High Bandwidth-Delay Product Networks May 25, 2009

The paper stars by mentioning that TCP behaves poorly in environments with high bandwidth-delay product, and that this is the future environment for existing networks. As propagation delay increases, or with higher link capacity, TCP’s performance and utilization degrade. As a solution, they introduce an alternative protocol, XCP, which remains stable, fair, and efficient as this product increases. XCP also distinguishes error losses from congestion losses, which can benefit the wireless networks. Further, XCP dampens oscillations and converges more smoothly to the available bandwidth than TCP does.  TCP is highly sensitive to sudden increase or decrease in bandwidth, whereas XCP adapts quickly to these changes. TCP’s slow start mechanism does not utilize bandwidth well with short-lived bursty flows, whereas XCP quickly adjusts available bandwidth for short flows. The main contributions of this paper are:

1. Providing feedback about congestion: XCP extends TCP’s ECN in the sense that it not only provides feedback about the existence of congestion, but it provides a quantifiable about the amount of congestion. Using XCP, routers provide feedback to senders about the degree of network congestion. This way, the hosts do not need to depend on packet losses as a sign of congestion, but instead can receive quantifiable measures about network congestion from the routers. Routers monitor the input traffic and compare it to available bandwidth. They tell the senders to decrease or increase their congestion window (cwnd). This information is carried in the congestion header of the data packets, thus letting a more congested router overwrite this feedback with a lower value. The sender can explicitly request a higher cwnd from the routers. The routers provide feedback by the congestion header in the packet, indicating whether the rate is to be increased or decreased. Thus this feedback is proportional to spare bandwidth, sending positive feedback proportional to spare bandwidth, and negative feedback when link is congested. The point is to try to provide feedback to the sender quickly enough, such that the sender can adjust its sending rate in time to avoid overrunning the bottleneck router queue. Thus XCP focuses on zero packet drops.
2. Decoupling of fairness and congestion control: the authors point out that the two are usually coupled together, but in reality they should be separated to allow better control of each. TCP uses a AIMD policy to control both. In XCP, congestion control depends on aggregate bandwidth, without regarding per-flow traffic. The router looks at the overall traffic to determine whether transfer rates should be increased or decreased. The efficiency controller uses a MIMD approach which lets XCP utilize available bandwidth quickly, rather than increasing it linearly as TCP does (after slow start). Fairness control on the other hand only cares about per-flow traffic and aims to evenly distribute available bandwidth between active flows. It uses the same AIMD mechanism as TCP. Thus by separating these two policies, bandwidth can grow quickly to reach high utilization (especially useful for shorter flows), and fairness can be achieve by keeping TCP’s AIMD  policy.
3. Not End-to-End: XCP places functionality at the lower layers, the routers. Instead of letting the end hosts adjust bandwidth, the routers provide feedback about bottleneck bandwidth and the end hosts adjust accordingly. One advantage is that the routers do not need to keep per flow states since this information is passed along to the senders in packets. Thus routers can scale better, while the protocol can remain more efficient because the feedback provided by the routers would be more accurate than the sender’s estimation of the network congestion.

Problems: XCP was designed without care about backwards compatibility. To fully utilize the new protocol, both the end systems and the routers need to understand XCP; this is a big drawback. For a flow to utilize XCP, all routers on the route need to be XCP routers. Even if this scheme works well at first, routes change frequently in the internet, and an XCP flow might face a dead-end if a bottleneck XCP router goes down.

Future research: perhaps a more backwards compatible version can be developed so that incremental deployment of XCP becomes more practical.

Internet Congestion Control for Future High Bandwidth-Delay Product Environments May 25, 2009

The paper  proposes eXplicit Control Protocol, XCP, that generalizes the Explicit Congestion Notification proposal (ECN). It outperforms TCP in common environments and offers better fairness, scalability snd stability when the delay-bandwidth product increases.

The primary contribution of the XCP protocol is that it introduces the concept of decoupling utilization/efficiency control from fairness control. Traditionally, the same policies or protocols are used to achieve fairness and efficiency simultaneously. Conceptually though, they are independent. The paper describes a mechanism to achieve the two through independent algorithms by considering the aggregate traffic’s behavior for the efficiency controller and relative throughput of individual flows for the fairness controller.

Another important contribution is that XCP distinguishes between error losses and congestion losses. Traditionally TCP assumes that all losses are caused by congestion and reduces the congestion window whenever there is a loss. While this assumption makes a lot of sense for wired networks, wireless networks work very differently. The loss rate is fairly high in wireless networks and distinguishing the two types of  drops is very useful.

A third important concept is that in XCP, the aggressiveness of sources are adjusted based on the delay in the feedback loop. So as the delay increases sources change their sending rates more slowly.

The biggest challenge to XCP is probably the difficulty in incrementally deploying it. XCP requires both hosts as well as routers to be changed. Changing the installed base of routers is difficult. So if it is being deployed, for a long time, a majority of the routers in the Internet would not be XCP routers. In this case, XCP cannot be used end to end. So hosts would have to revert to TCP. So until then there is not enough incentive for hosts to change to XCP. Another issue with XCP is security. The paper states that since the control state is contained in the packets, XCP does not need per-flow state in the routers. XCP relies on the RTT information contained in the packets to decide the feedback. Hosts might set incorrect values of the RTT in the congestion header to get an unfair advantage or with a malicious intent to bring down the network. The paper does not address this issue specifically of how the routers can routers can trust the hosts.

Future research in this direction would be to see how XCP behaves in very low latency and high bandwidth networks. Data center networks typically have very low end-to-end latencies of the order of a few microseconds. Studying the performance of XCP under such conditions might be useful. The other aspect is that in a data center, all the routers and hosts are under a single administrative domain and it might be possible to deploy XCP on all of the them unlike in the Internet where it is difficult to deploy XCP on all the routers. Another interesting property of XCP is that it has very low loss rates and small queue sizes. This might be very useful for storage area networks which require nearly lossless networks. Studying the applicability of XCP in such environments is another possible direction.

Internet Congestion Control for Future High Bandwidth-Delay Product Environments May 25, 2009

This paper studies the increasing inefficiencies of TCP in the high delay-bandwidth product of today’s network and proposes a new congestion control protocol called XCP that performs significantly better than TCP under all circumstance of network traffic and bottlenecks. XCP uses explicit congestion control mechanism by adding a few extra bytes in the packet header to indicate congestion. Since packet loss is a poor indicator of congestion which just indicates presence or absence of congestion in a binary manner, XCP uses a value to indicate the level of congestion instead of a binary prediction. In XCP, the network explicitly tells the sender the state of the congestion and how to react. This allows the sender to decrease their sending window quickly when the bottleneck is highly congested, while performing small reductions when the sending rate is close to the bottleneck capacity. This results in protocol which is more responsive and less oscillatory. They have modeled the dynamics of congestion control as a control loop with feed back delay and found that the aggressiveness of the sources should be adjusted according to the delay in the feedback loop. Also the robustness to congestion should be independent of the unknown and quickly changing parameters like number of flows. Since the dynamics of TCP aggregate depends on the number of flows which changes overtime, the controller can’t be fast enough to operate with an arbitrary number of flows. This leads to the need of decoupling of efficiency control from fairness control which makes the behavior traffic to be independent of the number of flows in it. The intermediate XCP routers maintains both fairness controller and efficiency controller. As the acks go back to the sender, each router in the paths writes it congestion value to the packet header if greater than the original value. Thus in reaching the sender, it indicates the bottleneck congestion which is used by the sender to adjust its window size. Simulations under varying traffic loads like bursty nature or short web flows, show that XCP performs significantly better than existing TCP in terms of packet loss, bandwidth utilization, and fairness. Finally implementing security against misbehaving sources is also much easier in XCP by sending explicit congestion windows back to the sender and monitoring its reaction. Sources ignoring such explicit signals can be marked to be adversarial and handled appropriately.

The major problem with the paper is the change in the packet header formats for explicit congestion signaling since changing legacy formats may pose a barrier to deployment. This also requires the intermediate routers to be more intelligent and able to detect congestion in a quantitative way. On the whole such an approach is trying to make the entire network more intelligent and hence complex, thus negating the philosophy of end-to-end arguments with simple networks in between. Finally although such sophisticated protocols may increase the overall efficiency of the network, implementing business policies using them to properly reflect the providers intent can become more complex and error prone.

Future works can include deploying the XCP protocol in real networks and studying its TCP friendliness as claimed with the existing protocols. Small fraction of resources may be allocated to XCP while the major fraction may be still used for existing TCP and UDP traffic. If happy coexistence is found between the protocols, the fraction of deployment may be increased slowly and steadily until it becomes the most commonly used protocol in the transport layer.

Internet Congestion Control for Future High Bandwidth-Delay Product Environments May 25, 2009

In the wake of very high bandwidth and large-delay links TCP has been shown to be becoming increasingly inefficient and unstable. The paper proposes XCP (Explicit Control Protocol) based on control theory to guarantee stability, fairness, scalability and efficiency of congestion control in the Internet. The main concepts behind the protocol proposed by the authors are to avoid a flow with packet drops which result in an inefficient binary model of congestion control and to decouple efficiency control from fairness control. Since internet flows are highly dynamic, they need to be decoupled from link bandwidth efficiency to ensure and respect the basic law of control theory which states that the variables of a control flow should change at rate slower than the speed controller itself. Given these ground rules, the authors establish a feedback control theory based protocol specification that meets the above requirements. The main points discussed are the framework of the protocol, the stability and robustness argument and its performance advantages over TCP.

XCP produces an environment that utilizes max-min fairness to distribute bandwidth. It is responsive in as little as one RTT when there is an increase or a decrease in the number of flows and reaches the desired congestion window size (CWND). It prevents losses by holding packets in queues when the network gets congested and notifies flows of the congestion via a congestion header on each packet. The routers give explicit and precise feedback to the senders, telling the sender how to change the CWND value (feedback of the bottleneck link prevails) without under/over-utilizing the network bandwidth.  During each RTT the congestion header is marked so that if more/less bandwidth becomes available it is quickly de-allocated/allocated to other flows. The efficiency controller utilizes the multiplicative increase and multiplicative decrease protocol thus trying to quickly attain the spare bandwidth-delay product and drain persistent queues. On the other hand, the fairness controller utilizes the additive increase and multiplicative decrease like in TCP. The fairness controller can naturally be extended to perform service differentiation. With each RTT these feedback values are recalculated to ensure that the end convergence of the system is stable. The authors conduct extensive simulations to show that XCP outperforms TCP in a variety of settings and it can handle flows with long RTT times. This makes it more feasible than TCP for use with wireless and satellite links. XCP can also accommodate these flows with long RTT values while still handling short RTT flows in a fair and efficient manner. Further, the protocol puts control state in packet headers and does not require per-flow state in routers, which is a good thing as having the per-flow state in a router, might not be feasible for the high bandwidth links.

XCP brings out an interesting proposition of a protocol that is suitable for high bandwidth delay networks which are to be a norm of the future given the penetration of wireless and satellite links for networking. XCP offers good advantages like small queue sizes and low packet losses and the use of explicit congestion feedback to optimize throughput and fairness. Also XCP does not require state in the routers, which makes the protocol scalable. Although novel, the paper does have certain issues that go partially addressed and even unaddressed. Like the authors point out, a problem of shuffling of bandwidth which can cause the aggregate throughput to fall below the optimal level. To achieve fairness XCP sometimes needs larger queue sizes (than TCP) to accommodate bursty traffic and changes in the number of flows without dropping packets. For complete deployment specifics of cost and commercial viability should be explored.

Congestion Control for Future High Bandwidth-Delay Product Environments May 25, 2009

1. Explicit rate control feedback to sender.

XCP explicitly lets the sender know how it needs to vary its rate to optimize utilization while avoiding congestion. This way it does not depend on packet drop as an indication of congestion hence avoiding packet drops. It uses the difference between available and utilized bandwidth and current queue length to compute rate change information.

2. Separate fairness and efficiency control.

It has separate mechanisms to handle fairness control and efficiency control. This gives the user the flexibility to implement different control laws for the two. It also means the user has flexibility to implement different fairness laws for different users depending on commercial incentives. It also means efficiency control can be optimized to maximize bandwidth utilization without being held down by fairness laws. In the implementation mentioned in the paper, MIMD is used for efficiency control which works a lot better than AIMD for short bursts of traffic.

3. Bandwidth shuffling

When the efficiency (a combination of queue length and bandwidth utilization) is near optimum, bandwidth shuffling ensures that throughput of individual flows  continue to converge towards their ideal fair-share values while aggregate throughput at the router remains constant. This ensures efficient decoupling of efficiency and fairness control.

Drawback

The XCP implementation comes at added cost. The routers piggyback congestion control information on packets returning to the sender. This adds to packet size and subsequently the amount of control data flowing in the network.

Future Work

XCP could be extended to distinguish between traffic requiring guaranteed delivery and traffic requiring bandwidth guarantees but can tolerate packet loss (eg. audio/video traffic). The control policies could be modified to handle the two types of traffic differently while maintaining optimized utilization and fair division of resources.

Internet Congestion Control for Future High Bandwidth-Delay Product Environments May 25, 2009

XCP is a new protocol that deals with the inefficiency of TCP when bandwidth and latency increases. The authors suggest that the current Internet congestion control mechanism is likely to run into difficulties in the long term through theory and simulations. XCP uses a congestion header that communicates the sender’s current congestion window, rtt estimate and a feedback field to control the congestion windows of the sources. XCP also introduces a new concept of decoupling of utilization control from fairness control.

Main Points:

1.) Congestion Header

The authors argue that packet loss is not a good indication of congestion. This is why routers will send feedback information to find the bottleneck and increase/decrease their window size from the initial desire value. This is another example of going away from the end to end principle that the Internet relied on before.

2.) Efficiency Controller

The efficiency controller just looks at aggregate traffic and does not care about fairness issues. It was pivotal that they do this because they wanted the dynamics of the aggregated traffic independent of the number of flows. The efficiency controller uses a Multiplicative-Increase Multiplicative-Decrease law that increases traffic based on spare bandwidth from the messages sent in the congestion header. This allows for quick utilization of the spare bandwidth.

3.) Fairness Controller

The fairness controller uses a new concept of bandwidth shuffling. This is the simultaneous allocation/deallocation of bandwidth such that the total traffic rate does not change but the throughput of each individual flow changes slowly to follow the flow’s fair share. They use an Additive-Increase Multiplicative-Decrease law to converge fairness. Even though they use this approach it converges faster than TCP because multiplicative decrease helps the convergence. Multiplicative decrease is done every average RTT in XCP while it is only done on loss packets in TCP which is rare.

Glaring Problem:

When comparing XCP to other congestion control protocols, they use a simulator that is based on a set of assumptions that might not necessarily be true for the Internet. There are some inconsistency with the paper too. The authors state that routers do not need to maintain any state with XCP but later state that the router needs to hold the average rtt.

Future Work:

With TCP’s struggles getting more and more prevalent as the Internet grows, more and more attention is being brought to newer protocols to deal with TCP’s shortcomings. XCP is a good stepping stone in the right direction with suggestions of gradual deployment in the paper. They also show that TCP should separate congestion and fairness. Some future work can be benchmarking XCP in a real network instead of a simulation to see how it holds up. Also different efficiency and fair controllers can be tested with.

Congestion Control for High Bandwidth-Delay Product Networks May 25, 2009

i)

1. TCP is poorly suited for dealing with congestion in networks with a high bandwidth-delay product. The reason for this is that there is a long delay before TCP gets feedback about congestion on the network. Furthermore even though only one flow might be causing congestion, all the flows will backoff once they start detecting packetloss. The author propose a new protocol XCP (eXplicit Congestion Protocol) which allows routers to dynamically scale the congestion windows of the end host based on the current congestion at the router. The way this is done is by putting control state into the packet and having each router along the path adjust the parameters so flows will converge at the correct congestion window for their bottleneck link.

2. Separating efficiency from fairness allows for a more flexible protocol. The authors calculate and efficiency value which is effectively the amount of free unused bandwidth. An efficiency controller monitors this value and adjusts it as necessary. Then they have a fairness controller which apportions the extra bandwidth among all the flows how it sees fit. In the authors implementation the extra bandwidth is distributed evenly across all flows. They also use a concept of bandwidth shuffling when the router is near peak efficiency to periodically redistribute a small amount of bandwidth among the different flows to speedup convergence to a fair distribution.

3. XCP can be deployed incrementally using a cloud based approach. The authors propose having a network running XCP and then having the border routers translated from TCP to XCP or vice versa. This will allow XCP to initially be deployed around links with a high bandwidth delay product such as satellite links.

ii) I think the biggest flaw was not addressing the performance of the XCP cloud from the point of view of two TCP end hosts. Initially it would seem that if XCP were deployed it would be around only very high bandwidth-delay product links such as satellite links or cross-country backbone links. If XCP were to be useful there should be a noticeable gain from the point of view of end hosts using this link if the link converts to XCP.

iii) Future research should address what gains one might see from deploying XCP in a small localized cloud. Specifically would using XCP allow a high bandwidth-delay product link to effectively control the TCP flows going through it to minimize congestion?

Internet Congestion Control for Future High Bandwidth-Delay Product Environments May 19, 2009

(i) The three most important things the paper says:

1. Noticing that TCP becomes unstable as delay or bandwidth increases, the author decided to investigates the protocol decisions and discovers that maybe the fundamental assumption that packet-loss indicates congestion could be incorrect. The author instead suggests a new protocol, XCP, that separates efficiency and fairness control and no longer relies on solely packet-loss for congestion detection. He instead adds an efficiency controller that tells the source to its congestion window using multiplicative increase multiplicative decrease. Because this module does not need to worry about fairness it can use a simple equation to decide if it should give the flow positive or negative feedback.

2. The other necessary control component is the feedback controller. This module uses additive increase multiplicative decrease to limit each flow so that all can share the bandwidth freely. Because of the modularity this control formula for this component can also be expressed succinctly. The fairness protocol can also be modified to provide distinct bandwidth for flows from different sources. The benefit of this is discussed in the next section.

3. The performance of XCP is quite stunning. XCP outperforms TCP and its variants in almost all cases. It maintains by far the top utilazation and fairness of all tested variants while dropping nearly 0 packets. The author also gives a deployment plan for XCP. This is incredibly important because we have an established working internet. New protocols can only be adapted when they can fit the current infra structure. For this reason the author provides a variation that makes XCP TCP-friendly so it can run with the current TCP and he gives a way to provide specific bandwidths for different sources which allows for ISPs to bill eachother and users which is necessary in todays marketplace.

(ii) The most glaring problem with the paper:

The most glaring problem with idea specified by the paper was the author softening the meaning of the number of bottleneck queues and the dropping that occurs after overflow. This hurts the scalability of XCP since as the number of flows increase so does the number of packets stored in queues this means that bigger and bigger queues are required and the network is not entirely scalable. One of there result tables shows that when 1000 flows are present the number of queues has reached the number of queues in a TCP stream well above 2 of the 3 variants and still appears to be rising. The author says that the utilization will drop to about the utilization of TCP RED if the queues overflow which is better than nothing but definitely a suboptimal outcome.

(iii) The future research directions of the work:

How can we lower the reliance on queue size? This would allow this algorithm to be scalable independent of number of flows. Another question is can we obtain even faster feedback, from routers for congestion control between routers at the layer 3 level. Lastly, it would be very useful to do an evaluation of the blocking points towards deployment of XCP with analysis and corrections to let it adapt to the demands of users and ISPs during deployment.

Congestion Control for High Bandwidth-Delay Product May 19, 2009

With high bandwidth delay product of individual links TCP becomes unstable. Paper proposes a new protocol called eXplicit Control Protocol (XCP) which is stable and efficient regardless of the link capacity, round trip delay, and the number of sources. XCP achieves fair bandwidth allocation, high utilization and small standing queue size and near zero packets drop both with steady and highly varying traffic. This does not maintain state per flow and requires only few cycles per packet which makes it implementable in high-speed routers.

TCP reacts adversely to the increase in bandwidth or delay. It has been argued that any active queuing mechanism can maintain stability over high capacity or large delay networks. Adaptive virtual queuing also becomes prone to instability when link capacity is large enough. Short flows which represent significant portion of the flow do not take advantage of the high bandwidth product due to slow ramp up of TCP. Another important issues brought by the paper is the fact that in today’s network lots of different flows with different RTT exists. As the throughput is inversely proportional to the RTT fairness might becomes an issue as more flows are added to the internet with different RTTS.

Paper proposes to inform the senders about the degree of congestion at the bottleneck and another new concept is the decoupling of utilization control from fairness control. To control utilization new protocol adjusts aggressiveness to the spare bandwidth in the network and feedback delay preventing oscillations in face of is bandwidth or large delay and ensures efficient utilization of the network resources. To control fairness protocol reclaims bandwidth from flows whose rate is above their fair share and reallocates it to other flows.

Putting control states in the packet XCP needs no per flow information in the flow and it requires only few clock cycles per packet making it practical for high-speed routers. Constant parameter independent of environment. It maintains good performance in dynamic environments with many short web-like flows and has no bias against long RTT flows.

Decoupling of fairness control from utilization provides bandwidth partitioning separate form congestion control. Protocol distinguishes error losses from congestion losses. Protocol uses explicit congestion control so any packet drop is likely to proceed by an explicit feedback that tells the sources to decrease congestion window.

Paper describes XCP as window-based congestion protocol where each sender maintains congestion window and rtt and sends this as a part of the packet’s congestion header. Router monitor the input traffic to each output queue and according to the link bandwidth as well as sender’s cwnd and rtt, tell the flows to increase or decrease their cwnd (by modifying H-feedback). A router later in path can overwrite a header if it is more congested so that eventual packet contains the bottleneck congestion information. Feedback reaches achiever and  is then copied to the ACK and send back to the sender.

XCP does not drop packets by preventing queues from growing so large that packets need to be dropped. Computations are done on average RTT as determined from information in the packet header. Router maintains per-link timer set to most recent average RTT and updates timer and control decisions when it expires.

Router computation involves efficiency controller that looks at the total traffic and aims at maximizing link utilization while minimizing drop rate and persistent queues. Fairness controller divides aggregate feedback to individual packets in order to achieve fairness. It follows additive increase and multiplicative decrease. When throughput is optimal it does bandwidth shuffling which keep the total throughput same but changes the individual throughput.

XCP shows good utilization and fairness, low queuing delay and drops very few packets and outperforms TCP.

Congestion Control for High Bandwidth-Delay Product Networks May 19, 2009

Dina Katabi and others propose a new transport layer protocol called XCP that provides better congestion control than the polular TCP. The salient points of the paper are:

1. Identification of the problems with TCP congestion control: TCP is criticized for its inefficiency when applied to high bandwidth*delay networks. The reason is that TCP slow start takes a long time to achieve the optimal fair share for the flow’s window size. The paper clearly identifies the root of this problem by arguing that TCP tries to link efficiency control (that the aggregate usage of the network is close to its allowed capacity) with fairness control (that each flow receive a fair share of the bandwidth).
2. Explicit Congestion Notification (ECN) idea is extended in this paper. Unlike ECN which just sets a bit to indicate the potential arrival of congestion, XCP goes a whole hog to explicitly inform the sender of the degree of congestion at the bottleneck through a new packet header for congestion.
3. The most important idea of the paper is the decoupling of efficiency control form fairness control. The authors argue that packet loss is a poor signal of congestion (that TCP uses) because congestion is not the only source of loss. Also, it is difficult to determine when a packet loss has occurred. XCP is proactive, while TCP is reactive for congestion control.

A disadvantage of XCP is that it is not backward compatible with existing TCP infrastructure. Every router and host needs to be modified and a new protocol stack must be built. Though the paper gives a method for TCP-friendliness of XCP, in practice, it will be costly for a router to check/conclude whether all the routers in the flow’s path obey XCP. Also, XCP places the trust on the correct funtioning of routers. If that is not the case, routers can  maliciously change the congestion feedback, which will mislead the host about its window size.

It is unrealistic for a clean slate protocol like XCP to compete with a well-established one like TCP. The reason XCP hasn’t become as popular as TCP, apart froom backward compatibility with TCP, is that it places the power of congestion control on untrustable routers. While it introduces wonderful ideas for separation of efficiency and fairness, research could happen along the lines of how to preserve end-to-end argument while also using the ideas mentioned in the paper.

Congestion Control for High Bandwidth-Delay Product Networks May 19, 2009

This paper introduces a new congestion control mechanism eXplicit Control Protocol (XCP) that overcomes the unfairness, efficiency issues, instability in TCP over networks with high bandwidth-delay products.

1. XCP puts control state in packets. Every packet sent has a congestion header with the sender’s cwnd and rtt estimate. The router monitor the queue output links and modifies a feedback field in the congestion header to let the sender know to slow down.

2. XCP routers have a new AQM scheme which decouples the controller to an efficiency controller (MIMD) and a fairness controller (AIMD) to provide feedback. Feedback calculation is done every RTT. Senders can reach the desired rate after one RTT.

3. The efficiency controller uses an aggregate view of the traffic to maximize link utilization. The fairness controller apportion the feedback to individual packets to achieve fairness

The paper has no significant problems and is well written. The most glaring problem is that deployment issues are barely discussed.

Further research can go into how to resolve deployment issues since XCP will require a redesign of routers, sender, and receiver. Security issues can hamper deployment as well so research can look into how to mitigate people from maliciously using the feedback headers for their own benefit or to take down a network.

Internet Congestion Control for Future High Bandwidth-Delay Product Environments May 19, 2009

The XCP scheme uses explicit feedback to manage the congestion of a network. It does so using a header containing, among other things, a feedback value first initialized by the sending end-host, and modified by routers along the way according to the output of an “efficiency controller” and a “fairness controller” on each.

The idea of having these two controllers is the separation of congestion and fairness. The efficiency controller decides that the total traffic should change by a certain amount. The fairness controller then takes this amount and distributes the change among individual packets by changing the congestion header.

Internet Congestion Control for Future High Bandwidth-Delay Product Environments May 19, 2009

Three Important Things:

• The motivation for this paper is the fact that TCP’s performance degrades significantly when RTT is high and there is a lot of bandwidth available. This is because additive increase is limited to a packet per RTT. The fundamental observation is that a flow controller must be able to react as quickly as the network is changing, which is not the case in high RTT environments. The “smart router” approach is adopted to combat this problem, where routers along the path annotate packet headers with congestion feedback, allowing the senders to adjust the window size appropriately. Once at the destination, the packet will retain congestion information from the network bottleneck. This approach is shown by simulation to yield very low packet loss, low queuing usage, and significantly higher link utilization
• In XCP, the control mechanism is now pushed into the network and separated into two parts. The efficiency controller only deals with congestion issues, and its job is to maximize utilization while minimizing packet loss. It does this with scaling factor adjustments based on the measured spare bandwidth. This is a strong departure from TCP, which needs to purposely cause packet loss since it is the only form of feedback that can be received from the network. Thus XCP offers a more fine grain view of congestion. The fairness controller seeks to apportion bandwidth fairly across all flows, and it does this by scaling back overshooting flows and gradually ramping up needy flows. This separation provides a framework for implementing different usage policies and allocation schemes as desired.
• The authors claim that XCP can be deployed alongside TCP. This is a critical feature to examine given the difficulty of getting new protocols adopted. The first approach to gradual deployment could be a cloud strategy where small parts of the internet ran XCP and had translation entities at the cloud edges. This has been tried and tested in the case of IPv6 for example. The other idea that the authors propose is to have new routers support both protocols and have weighted fair queues for each, as well as respond to queries about their protocol support. This way two XCP-capable hosts can determine if they have a path between them with XCP-enabled routers.

Glaring Problem:

After completing the reading, some of the paper’s discussion did not feel fully developed. For example, the section on security lists an overly simplistic approach to policing misbehaving sources with no discussion of possible spoofing. The paper also does not list any information on continuing research in the section labeled “future work.”

Future Work:

XCP represents a complete departure from the end-to-end principle. Once this is violated and routers become intelligent entities from a protocol perspective there are many more potential benefits that can be reaped. These might include security improvements, fine-grain usage charging policies, etc. All these avenues can be investigated along with the associated cost for the additional router computation.

Internet Congestion Control for Future High Bandwidth-Delay Product Environments May 19, 2009

XCP is a new TCP variant that relies on participation from network elements to achieve nearly perfect efficiency and fairness. The standard TCP header is augmented with three fields. Two of the fields allow the sender to specify its estimated RTT and window size. The third field is used for feedback and initially contains the senders desired window size. The feedback field is decreased by any heavily loaded router along the data path in order to prevent congestion or enhance fairness. The routers maintain no per flow state, using only buffer load and header data to create feedback information. Feedback is returned to the sender in an ACK packet.

Routers run a a simple algorithm on all outgoing interfaces to generate feedback information. The algorithm is divided into two parts. The first part, the efficiency controller, optimizes link efficiency. It maximizes link utilization while minimizing drop rate and queue length. The efficiency controller operates on the traffic aggregate without regard to fairness. The second part, the fairness controller, determines per flow feedback that satisfies the requirements of the efficiency controller and maintains fair sharing of the link capacity.

XCP is shown to operate with almost zero dropped packets and perfect fairness. It will inter-operate with a legacy TCP host. Proper network configuration allows fair sharing with TCP connections. Establishing XCP tunnels for an aggregate of TCP connections simplifies traffic management in the network core.

XCP creates an explicit connection between the layer 3 routing devices and a specific layer 4 protocol. This violates the separation by layers that simplifies Internet protocol and has made is deployment so successful. Violation of the layering principle appears to be required in order to improve service and feedback from the network is a likely development. However, the feedback should not be tied to a single protocol. The feedback should be general enough that multiple higher level protocols can be designed to use its advantage.

A generalized feedback mechanism is required. Work should proceed on determining the applicability of these methods to transport protocols other than TCP and over a wide range of applications. Deployment in the Internet will take years and a system that satisfies the XCP requirements but with wider applicability is desirable.

Internet Congestion Control for Future High Bandwidth-Delay Product Environments May 19, 2009

(i) the three most important things the paper says

The most important idea showed that it is beneficial to separate utilization and fairness control from one another.  The authors demonstrate that using these as separate analyses allows total link utilization to be given a priority over complete fairness control (so that the link doesn’t quickly become overly congested), but also to allow finer tuning in who is using that upper bound of bandwidth.  Another important idea that the authors demonstrate is that router involvement in a protocol can greatly help convergence of a certain set of connections to their maximum link speed.  Without router involvement, the end hosts can only guess what the link saturation is, taking a risk that may cause severe congestion in the process.  Lastly, the authors showed that, even with a long latency connection, XCP can be aggressive in its decisions without highly congesting the links throughout.  It’s able to do this because each router will give very accurate feedback instead of the connection guessing based upon its observation of the network usage.

(ii) the most glaring problem with the paper

I feel that the biggest problem with this paper is that it requires great modification to the internal routers of a connection, and without all of those routers being modified the scheme would be useless.  This requires an ISP to change all of their routers in order of the scheme to be useful (and this would only be for inter-ISP connections).  It seems as if the entire internet would have to be swapped out in order for this scheme to be effective, even if everyone didn’t change protocols right away.  This seems infeasible with the current state of internet politics.  I also feel that adding this complexity to the router level would hinder a router from operating at the fast speeds necessary to handle large amounts of traffic.

(iii) the future research directions of the work

I feel that this scheme is great, but needs to work on a way to tolerate the above listed shortcoming.  I feel that if the authors were able to come up with a way to operate in the meantime (without an entire path having XCP routers), this scheme would be much more viable.

Congestion Control for High Bandwidth-Delay Product Networks May 19, 2009

Modern High Bandwidth-Delay Product networks are becoming more and more unsuitable to be used with the standard TCP protocol. The congestion control of the TCP is indeed to slow to deal with such type of networks. This because the TCP bases its control mechanism on packet losses and RTT. Hence on one side it keeps sending packets until the network is congestioned; on the other side, if the RTT is either very short or very long, the TCP reaction is either too aggressive (it increases its window too fast) or too slow, resulting in a poor bandwidth utilization.

The solution presented in this paper implements a different control mechanism that should be able to deal better with high bandwidth delay product networks.

The three most important aspects of the proposed solution are:

1. Per packet congestion signalling. Each XCP enabled router along the path updates a congestion header associated with each packet. This congestion header eventually reflects the congestion state on the bottleneck of the path between the sender and the receiver. The receiver then sends  the congestion header back to the sender with the ACK of the packet. Hence the sender receives a continuous feedback from the network and increases or decreases the flow accordingly in a much faster fashion. This allow the sender to promptly use the available bandwidth, without waiting for many RTTs to occur.
2. Full bandwidth utilization and zero packet drops. The control mechanism present at 1. allows the network bandwidth to be fully used because even in the case of short web-like flows, senders get notified very quickly of the available network and they can increase their windows, hence flows, very fast. The same holds also the other way around. When the bottleneck gets close to full capacity, it tells the senders to reduce their flows by updating the congestion header of their packets. The senders can then reduce their flows, hence relieving the congestion and avoiding packet drops. Tests show that the XCP’s packet drop rate is several orders of magnitude smaller than the standard TCP.
3. Decoupling of efficiency controller and fairness controller. Through the congestion header is possible for a XCP-enabled router to enforce fairness among the flows, independently from the congestion control mechanisms. Every RTT the router reassigns a 10% of its capacity among the flows trying to converge to a fair balance between them. This is called bandwidth shuffling and it is completely independent from the congestion status. The fairness control allows also the ISPs to apply whatever roule to the flows traversing their routers, like for instance, to give a different bandwidth accordingly to the price paid for the connection.

I found this paper very interesting and the solution proposed very sound. However this solution requires a widely adoption of the XCP protocol, both on the servers and on the end users sides. The servers must be able to update the congestion headers, the end users to react properly to the signalling. The authors suggest that at the beginning of a communication the sender could test the network to see whether it is XCP complaint. If not, the sender would switch to standard TCP mode. While this would work in theory, it would also add an overhead (not quantified in the paper) at the moment of establishing a connection. In case of short web-like flows, this overhead could be too big.

As a research direction I would try to identify how XCP could integrate more seamlessly with the already existing infrastructure and protocols.

Congestion Control for High Bandwidth-Delay Product Networks May 19, 2009

Important Things:
1) XCP decouples utilization control from fairness control, using MIMD for fast utilization convergence, and AIMD for fair convergence. They employ ideas from control theory to prevent oscillatory behavior, and they can control congestion with very low packet loss and short queue lengths.
2) Control state is held in the packet header, so routers don’t have to maintain flow state information. Also, the computation overhead on routers is very small.
3) They propose two paths for the deployment of XCP, one which maps TCP and UDP flows to XCP flows across some XCP cloud, growing the cloud gradually. Another involves making XCP TCP-friendly and falling back to TCP if the receiver or an intermediate router don’t support XCP.

Problems:
XCP seems to be a good path for congestion control, though it would take a long time to deploy widely because it requires lots of expensive routers to be upgraded.

Future Work:
This paper has evaluated XCP in simulation. Future work should continue to evaluate it in real deployments.

Internet Congestion Control for High Bandwidth Delay Product Networks May 19, 2009

(i) The three most important things the paper says:

 

1) The concept of decoupling utilization control from fairness control was a novel idea in this paper.  This stemmed some good points, for instance, opening up new avenues for service differentiation.  This was an important point from a business perspective, since ultimately what drives the deployment of new technology will hinge on large corporations adopting it.  Another good point is how this separation simplifies the design and analysis of each controller by reducing the requirements imposed. 

 

 

2) Since congestion is not a binary variable and requires a degree of values to truly measure it, the protocol must reflect this as well.  Because of this, Katabi et al ultimately decided to use a precise congestion signaling where the network tells the sender the state of congestion. From my perspective, this is the cusp of XCP since it allows them to have amazing results such as “rarely loosing packets” and “efficient use of bandwidth in a multitude of conditions”. 

 

3) The method in which they implemented XCP, a protocol based on network control of flows, with little overhead to routers.  By storing feedback information in a header, and making routers “stateless”, they estimated that a XCP router only performed a few additions and 3 multiplication per packet.  This is important as we are demanding faster routers and switches at the edge of our networks, any additional overhead may make a solution no longer viable.

 

(ii) The most glaring problem with the paper:

 

Although the paper considered security aspects and how to detect senders that do not honor XCP, they do not consider the cases of rouge routers.  Since this is a protocol that relies on the network (aka routers) from making the right choices, I believe that router security should be considered more.  Specifically, consideration of methods to avoid paths that routes through a router that you know is making poor or malicious decisions.  This is pivotal before XCP can be deployed in a commercial setting, since a single rouge router can trick the rest or the routers to believe that senders are misbehaving.

 

(iii) The future research directions of the work:

 

They seem to be very proud on the fact that in their tests, XCP rarely loose packets.  I believe this may have been a blind spot in their research.  A good direction for the research would be to analyze more dimensions of tests that involve XCP behavior in low reliability networks.  Since they aim to replace TCP, this is an important facet to cover the flexibility of this protocol.