False Sharing and Shared Congestion Management
Aditya Akella, Hari Balakrishnan, and Srini Seshan

However, all these proposals have been plagued by deployment concerns despite their many demonstrated benefits, primarily due to one reason: false sharing. False sharing of congestion management systems arises because such systems might unknowingly force flows to share congestion information, where they should not. Two or more flows sharing congestion state may in fact not share the same bottleneck.

This work presents a detailed study of this problem, investigating various sources of false sharing and analyzing its negative impact. We categorize the origins of this false sharing into two distinct cases: (i) networks with QoS enhancements such as differentiated services, where a flow classifier segregates flows into different queues, and (ii) networks with path diversity where different flows to the same destination address are routed differently.

We study the problems along three axes:

• Impact What impact does false sharing have on performance and correctness? Does false sharing compromise end-to-end congestion control, perhaps by causing a bottleneck link to become persistently overloaded? Does false sharing degrade the performance of individual flows, causing them to perform significantly worse than if they were not sharing congestion information?
• Detection Under what conditions can false sharing between two flows be detected by a sender, which can then separate the flows into separate groups? How do delay differences, reordering rates, and packet loss patterns compare in this regard?
• Response How should congestion sharing systems be modified to deal with false sharing? Should the default behavior of such systems be to optimistically share information and then separate flows if false sharing is detected, or vice versa?

We have show that for shared congestion control using TCP-style window-based algorithms, the correctness of congestion control is not compromised even when two or more flows of very different available bandwidths end up sharing information. In particular, we have find that the slower sender does not overload its bottleneck link. However, faster senders are heavily penalized as a result of false sharing. We also derive an analytical expression that explains our findings.

We present tests based on packet loss patterns, packet delay, and packet reordering statistics that can be used effectively to detect false sharing. We find that reordering statistics are the most robust detectors of false sharing while packet loss patterns are the least reliable. In addition, packet reordering statistics take the least amount of time to detect false sharing (5-10 secs).

Finally, we exhibit how these tests could be incorporated into congestion management systems at end-points to detect and respond to false sharing. Our simulation results imply that it is easier to start with the default set to share congestion information than with the default set to ``don't share''. Our simulation results confirm the effectiveness of this approach.

Related Publications, Talks and Posters

• The Impact of False Sharing on Shared Congestion Management [ps] [pdf]
  Aditya Akella, Srinivasan Seshan and Hari Balakrishnan.
  IEEE International Conference on Network Protocols (ICNP) 2003, Atlanta, GA.
  Also appeared in Proc. ACM SIGCOMM Computer Communication Review, January 2002 as a short paper.
  Links to the shorter version: [ps] [pdf] [ppt]
  
  
• The Impact of False Sharing on Shared Congestion Management [ps] [pdf]
  Aditya Akella, Srinivasan Seshan and Hari Balakrishnan.
  CMU SCS Technical Report Number CMU-CS-01-135.
  
  
• Congestion Management and Service Differentiation [ppt]
  Presented at the PDL Retreat 2001. Another version of this talk was given at the CMU Monday Systems Seminar in Feb'2001.