Floodless in SEATTLE

C. Kim, M. Caesar, J. Rexford, "Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises," ACM SIGCOMM Conference, (August 2008).

This paper describes a network architecture called SEATTLE (Scalable Ethernet Architecture of Larger Enterprises) which aims to achieve the scalabilty of IP combined with the simplicity of the Ethernet. The most important aspect of SEATTLE was its plug and play functionality as well its ability to simultanously operate with existing infrastructure and protocols.

The paper started off by discussing the problems of Ethernet bridging (namely inflexible route selection and its dependence on broadcasting for basic operations), Hybrid IP (configuration overhead due to hierarchical addressing, complexity encoutered in implementing network policies and its limited support for mobility if end hosts) and Virtual LAN (Trunk configuration overhead, limited control-plane scalability and insufficient support for richer topologies).

The authors then proposed a system for a network layer one-hop DHT. The concept was to use link state protocol on the switch level to ensure that each switch knows others' position in the network. Now, each end node was hashed based on its MAC and IP addresses on other switches. The idea was that whenever a request came to a switch, it computed the hash of the IP address of destination and queried the switch which resulted. This switch had the location of the switch in whose domain the destination host belonged and the packet was routed to it. Moreover, the value was cached for further tranmissions on source node's switch. The logic behind this was the observation that most of the communications in the modern Internet involved communicating with a small fixed number of destinations. Further, it also enabled flexible service discovery as services like "PRINTER", "DHCP_SERVER" could also be cached in a similar manner on the switches. The system was also much more lenient to topology changes by communicating between switches and upldating key value pairs. Further, the authors discussed about the scalability of the system by proposing a multi-level one hop DHT by defining a separate regional and backbone hash ring. Finally a simulations study was provided based on real-world traffic traces using Emulab to evaluate using Click and XORP routing platforms.

Overall, this paper is very straightforward in its approach and clearly discusses about the current scenario in enterprise networks.  It does an impressive job in tackling out many of the issues that affect the scalability of current networks which rely a lot on broadcasts and flooding as a means of path detection. However, I felt that the authors gave a very fledgling insight in the hierarchical multi-level one-hop DHT. Since the boundary level switch ring has to maintain hash values of each and every host, this puts a question on the size of the enterprise networks that the authors were targeting. Somehow, it was not really clearly defined by the authors. Further, it would have been great if the authors had discussed about the cost/feasibility of the smart switches in the protocol too.

Congestion Control for High Bandwidth-Delay Product Networks

D. Katabi, M. Handley, C. Rohrs, "Congestion Control for High Bandwidth-Delay Product Networks," ACM SIGCOMM Conference, (August 2002)

This paper presented eXplicit Control Protocol (XCP) as a replacement to the current widely deployed Transport Control Protocol (TCP) which introduced the new concept of decoupling utilization control and fairness control. The advantages of XCP (and disadvantages of TCP) were:

1. Unlike TCP where efficiency and fairness are coupled together into AIMD, XCP allows these two things to be decoupled. As a result, XCP effectively implemented MIMD for its efficiency controller and AIMD for its fairness controller.

2. In XCP, each packet sends a congestion header to the gateway which contains the sender's current window size and its RTT. The router in return gives back its feedback in the same header. This allowed that the new protocol does not maintain any per flow state in routers.

3. TCP's additive increase policy makes it less responsive in its ability to acquire spare bandwidth.

4. XCP facilitates the detection of misbehaving sources.

5. XCP provides a good incentive for users to deploy it. However, it can very well co-exist with existing TCP which allows it to be implemented gradually.

6. The parameters  used in XCP are pre-specified which makes it easy to be deployed without much application-specific tuning.


The design of XCP was followed by extensive simulations and stability analysis. The authors showed that XCP clearly outperformed TCP over RED, CSFQ, REM and AVQ.  Overall, this paper being a relatively new paper deals with some of the core issues that affect the Internet today and questioned the very assumptions of TCP. I really liked this approach of stepping back a bit and questioning the core assumption of why should packet loss be a indicator for congestion! Moreover, many of the ideas mentioned in this paper built on things that we had been discussing in the last few classes involving burst traffic and high delay and bandwidth links. Moreover,  I felt that for identifying misbehaving hosts, we do have keep per-flow information, which was not really explained well in the paper. To conclude, it would be really interesting to discuss the applicability of this protocol and how successful was its gradual deployment.

Random Early Detection Gateways for Congestion Avoidance

 S. Floyd, V. Jacobson, "Random Early Detection Gateways for Congestion Avoidance," IEEE/ACM Transactions on Networking, (August 1993).

This paper talks about the Random Early Detection (RED) gateways for congestion avoidance. The underlying idea is that the gateway drops or marks each arriving packet with a probability that is a function of the average queue size and is proportional to the connection's bandwidth share . The main advantages of RED gateways are:

• No bias against bursty traffic
• Avoids global synchronization
• Gradual deployment  is possible in the current Internet

 The paper started off by discussing some early work on congestion avoidance gateways namely Early Drop Gateways (which being a drop-tail gateway resulted in global synchronization and had biased against bursty traffic) and Early Random Drop gateways (whcih were not successful in controlling misbehaving users). Many of the early congestion avoidance schemes focused on instantaneous queue lengths and not on average queue lengths which obviously created a bias against bursty traffic or traffic with high bandwidth-delay product.

The design of the RED algorithm was pretty neat in the way that it dealt with average queue length which was calculated as (1-w)*avg + w*q. Here q was the instantaneous queue size and w was the queue weight which in a way helped in smoothing out the average by making it dependent on the previous calcualted average and the current queue length. The advantage of this was that the momentary changes in queue lengths due to traffic bursts didn't change the average queue length by a huge amount (thereby not resulting in dropping/marking packets).  The authors backed up their algorithm with adequate simulation which confirmed their results.
 
Overall, this paper was pretty clean in its presentation and put forth its point in a clear manner. However, I felt that it had quite a lot of parameters to  manipulate such as  w (queue weight),  the max/min thresholds, the maximum probability and not enough guidelines were given for determining their values. I personally was quite curious to see how various values of w (queue weight) affect the average queue length (and hence the throughput). Moreover, all the simulations assumed equal packet sizes.  As shown, in case of variable packet sizes, the probability of dropping would have been p = p*(packet size)/(max packet size). It would have been interesting to see the overhead of this operation as unlike other operations which involved bit shifting and addition, this operation would have considerably affected the computation time on the gateway. Moreover, it would be really interesting to discuss as to how successful was RED eventually and how does it stand in the current scenario (when bursty and high bandwidth-delay product traffic has increased a lot in the Internet).

Core-Stateless Fair Queueing

I. Stoica, S. Shenker, H. Zhang, "Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks," ACM SIGCOMM, (August 1998).

This paper claims that although fair queueing does a pretty good job in managing bandwidth and buffer space and ensuring promptness, it needs to maintain state, manage buffers and perform packet scheduling on a per flow basis. This increases their complexity as well as decreases their cost-effectiveness. This paper on the other hand proposes a different architecture to tackle the complexity. The idea is that this architecture may not be as good as the strict FQ algorithm but has a very good 'profit by cost' ratio.

The architecture consists of an island of routers (which is quite vague in definition and may refer to a collection of routers owned by an ISP or may even spread across many ISPs in case there are no trust issues) consisting of a contiguous region of network. The authors make a distinction between edge routers and core routers. The idea is that the edge routers maintain flow state information and insert a label into each packet based on their estimates. The core routers which are essentially stateless implement FIFO packet scheduling  and a probabilistic dropping algorithm taking into account the packet labels. Two important assumption taken by the authors were:

• fair allocation mechanism play an important role in congestion control
• the complexity of the current fair allocation algorithms is a substantial hindrance to their adoption.
  

The probabilistic dropping algorithms used by core routers doesn't give nearly-perfect levels of fairness however, it does help in achieving a reasonable approximation to the fair bandwidth allocation. The authors compared this scheme with other queueing scheme FIFO, FRED, RED and DRR and found that CSFQ's performance was better than FIFO and RED and was comparable to FRED. It's complexity level of edge routers were comparable to FRED while core routers were comparable to RED. DRR had a better performance however the cost was a play down.

Overall, this paper was very straight-forward and honest in its approach. It freely questioned its own assumptions and the authors even admitted that they were unsure how to interpret some of the final results! Moreover, even though the paper skipped some mathematical proofs and only gave the final result, it did provide an intuitive understanding of the concept which was really great.

Analysis and Simulation of a Fair Queueing Algorithm

A. Demers, S. Keshav, S. Shenker, "Analysis and Simulation of a Fair Queueing Algorithm," Internetworking: Research and Experience, 1 (1990), pp. 3-26.

This paper involves the design of the fair queueing  algorithm which can ensures proper allocation of bandwidth (which packets get transmitted), promptness (how soon they get transmitted) and buffer state (which/when packets are to be discarded) independently. It shows that fair queueing provides several important advantages over the standard FCFS algorithm used by most of the routers. One of the important one is that the latter assumes that there are no ill-behaved sources in the network while fair queueing provides protection from ill-behaved sources by appropriately penalizing them.

The paper started off by highlighting the work done by Nagle on fair queueing in which the gateways maintaind separate queues of packets for each source and serviced them in round robin manner. However, this simplistic algorithm didn't tackle the case of fair bandwidth allocation due to difference in packet sizes. Eg. large packet connections effectively ended up getting higher bandwidths. Moreover, due to lack of simulation data and comparison metrics involving this algorithm, it was necessary to know exactly 'how much' improvement are these fair queueing algorithms over standard FCFS. This lead to the authors look into designing a better FQ algorithm and back it up with adequate simulation/comparison data. The max-min criterion of fairness was that an allocation is fair if:

• no user receives more than its request
• no other allocation scheme satisfying the above condition has higher minimum allocation
• the above condition remains recursively true as the minimal user is removed and the total resource is reduced accordingly.

The allocation criterion used in this paper was conversations -- source destination pairs. A hypothetical implementation of such a fair criterion would be a bit-by-bit round robin scheme (BR) implemented on the gateways where each bit of data was forwarded by the gateway for each flow in a round robin method. The authors quite elegantly showed that this hypothetical scenario can very well be extended to the generic scenario by simply defining the rule that whenever a packet finishes transmision, the next packet sent was the one with the smallest value of F (finishing time). The authors also introduced 'delta' which was kind of a history element of the packet and helped in promptness. It helped in rewarding those connections which were using less than their share of bandwidth. Moreover, the dropped packets from a hosts were also counted in throughput which rightly penalized ill-behaved senders. The authors did a really good job at simulating the generic, JK and DEC flow control with the FCFS and FQ queueing algorithm in a variety of synthetic scenarios which were kind of border cases of evaluation which nicely backed their above arguments.

Overall, the paper was very well presented and highlighted the deep insight of authors in this area. The experimental data adequately backed up all the claims made by the authors. Few things which could have been taken into account was how would the protocol behave when we had multiple connections from the same host. Since the whole FQ was being done on a 'per connection' basis, there could be very well a series of connections establish by a single ill-behaving host. Moreover, as a young student in network research, an interesting question that comes to my mind is that how do researchers choose evaluation scenarios? Why is it apt to claim that the whole protocol works if it works for 6 boundary case scenarios? Couldn't there have been a 7th scenario which would have uncovered an interesting insight in this problem or flaws in the algorithm?

Congestion Avoidance and Control

Jacobson, V. 1988. Congestion avoidance and control. In Symposium Proceedings on Communications Architectures and Protocols (Stanford, California, United States, August 16 - 18, 1988) 

The underlying idea highlighted by this paper is that most of the problems arise from incorrect implementations of transport layer protocols rather than the protocols themselves. In view of this, the paper highlighted plenty of instances where things could go wrong and described some algorithms to set them right. The whole paper is set in a very practical approach, and is a result of the work done in solving the problem of a sudden massive throughput decrease between LBL and Berkeley due to network congestion in October 1986.

 The following contributions were proposed by the paper:

• Slow start algorithm: This was an algorithm to establish the initial flow. It started off with a one packed window and then kept on doubling the size of the window whenever all the current packets sent by the window were acknowledged (limited by the max size of the window wmax).
  
• Round-trip-time variance estimation: This talks about estimating the mean round trip time R = aR + (1 - a)M where R is the average RTT estimate and M is the recently calcuated RTT time from tthe network.
• Exponential retransmit timer backoff: This deals with how should the transmits be spaced if the packet has to be re-transmitted. The author claims (with a little bit of intuitive explanation) that exponential retransmit works best in this case.
• Dynamic window resizing on congestion: This is more of a caveat taken fromt he last paper, and talks about additive increase (by 1/(window size)) and multiplicative decrease (by 0.5).

Further, the authors claim that if fair sharing has to be taken into account, the congestion detection must be implemented at gateways instead of end points (End-to-end Principle violation?).  In the end, the paper has a very informative appendix which gives a good insight into the implementation of the above proposed algorithms.

Overall, I felt the paper to be perfectly complimentary to the previous paper.  It carefully highlighted the practical aspects of the congestion avoidance problem highlighted in the previous paper. I felt that if I had taken a course in queuing theory, I would have been in a much better position to appreciate the subtleties in this paper. It would be great if we could have a short optional reading on queuing theory along with this paper. Moreover, I am not very convinced by the author's argument of using b = 0.5 instead of 7/8 in the original paper. Though the reason highlighted is that it is due to the nature of  slow start algorithm, I somehow find it difficult to appreciate it. Doesn't slow start run at the beginning just for establishing the flow? Once the flow is established, subsequent throughput is increased/decreased by the additive increase /multiplicative decrease. In this case, halving the window size seems to be pretty harsh!

Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks

Chiu, D. and Jain, R. Analysis of the increase and decrease algorithms for congestion avoidance in computer networks. Comput. Netw. ISDN Syst. 1989

Congestion control mechanisms can be broadly divided into 2 categories, congestion avoidance and congestion recovery. Both of them are aimed at solving the underlying network resource management problem at their heart however with different approaches. The former is a 'preventive' approach where appropriate steps are taken so that the network doesn't reach the congested state in the first palce while the latter is more of a 'responsive' approach which sets into action when the network is already congested. This paper discusses the nuances of the former congestion avoidance approach by taking into account various performance metrics such as efficiency, fairness, convergence time and size of oscillations.

At the heart of the congestion avoidance approach is the 'binary feedback scheme' which kind of acts as a network monitor and sends a binary feedback back to the host (1 if overloaded and 0 if underloaded). Now, when a host comes to know the status of the network through this feedback, it must either increase (in case bit = 0) or decrease (in case bit = 1) its throughput accordingly. Considering a linear change is the new rate (which the author argues is quite simple and sufficient to handle), the new throughput can be given as:

X(t+1) = a + bX(t)

where, a and b can be 'theorectically' positive or negative depending on the increase/decrease. However, when the author took the properties of efficiency, fairness and distributedness into account, the variables a and b pretty much reduced to the condition of b = 1 for increase and  a = 0 for decrease. In other words, it was found that additive increase (X(t+1) = a + X(t)) where a > 0 and multiplicative decrease (X(t+1) = bX(t)) where 0 < b < 1 worked best. At the end, the author also introduced nonlinear controls in a fleeting manner and said that they unnecessarly complicate the task of finding the right scaling factors.

Overall, this paper was a good read because of the simplicity and straightforwardness of its explanations. I loved the way it explained the convergence to efficiency and fairness feasibility conditions through vector graphs! The paper mentions that it considers both under-utilization of network channel and over utilization to be equally wrong and something that the congestion algorithm should tackle accordingly. In spite of the convincing maths and graphs, I somehow find the additive (slow?) increase and multiplicative (faster?) decrease intuitively opposing to the equally wrong consideration. Secondly,  as the author highlights, non-linear controls offer us far more flexibility in reaching equilibrium, however there are obviously performance and complexity trade-offs. It would be really interesting to discuss these trade-offs in class. Furthermore, it would also be great to discuss the behavior of congestion avoidance algorithms in a dynamic environment such as P2P sharing etc. where the hosts join and leave often.