10. Congestion Control for High Bandwidth-Delay Product Networks

This paper proposed a new protocol in replace of TCP. The new protocol, eXplicit Control Protocol (XCP), addressed the issues of TCP by putting a congestion level field called Explicit Congestion Notification Proposal (ECN) in the packet headers. This XCP protocol does not maintain a per-flow state in routers and thus, requires less CPU cycles in busy routers.

TCP doesn't react well with high bandwidth, high latency links such as satellite and wireless. Under such circumstances, TCP tends to be unstable and oscillate. For example, TCP sends one packet per RTT to get more bandwidth, and it can takes thousands of RTTs to make good use of the high speed network.

Robustness to congestion should be independent of number of flows, according to the authors. And packet loss shouldn't be a signal of network congestion. Thus, XCP introduces decoupling utilization control from fairness control, which adjusts its aggressiveness according to the spare bandwidth in the network and the feedback delay. It also has a per-flow control in the protocol, rather than in routers, to achieve fairness. Furthermore, XCP distinguishes error loss pack-dropping from congestion, which is quite useful on wireless connections.

Comments:

1. I like the fact that in XCP, packet drops caused by congestion are highly uncommon because it separates drops caused by link errors from network congestion. These two factors should be viewed independently in the protocol and acted upon accordingly.
2. Like every new stuff in our lives, backward compatibility is a big issue. XCP is just like IPv6 where everyone knows about it, but no one seems to be using it. Would it be possible to implement XCP concepts one level up in OSI model in order to be compatible with TCP?

9. Random Early Detection Gateways for Congestion Avoidance

This is yet another algorithm for congestion avoidance. The Random Early Detection (RED) is implemented by computing an average size of the queue, and drops a packet or sets a "congestion bit" in the header by the proportion that connection's share of bandwidth in order to reach a certain fairness for all the end-notes on the network. It is designed to with with TCP or any other protocols with build-in congestion control.

In a traditional manner, a network wouldn't know it is congested until a packet had been dropped, and this could be a problem because the response time would have been greatly increased. The RED algorithm tries to slow down the traffic before it reaches the maximum capacity (cliff) while maintaining a high throughput.

The most effective detecting of congestion lies in the gateway itself, according to this paper, because it can distinguish between transmission delay and queueing delay. RED gateways monitor the average queue size, and either mark the congestion bit or drop a packet to signal sender's connection, depending on whether the packets are marked "essential" or "optional".

RED calculates the average queue size in the gateway by a low-pass filter and an exponential weighted moving average, and compared it to a min and max threshold. If the size is greater than max, all packets going through are marked/dropped; less than min, none. If the value falls between min and max, the probability of marking/dropping a packet is a function of average queue size.

Comment: It makes perfect sense that they drop/tag a packet based on the connection bandwidth share of a specific host. But how do we define a "host"? Is it one TCP connection, one software, one port, or one network interface card?

8. Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks

There are several Fair Queueing (FQ) mechanisms in routers, such as the last paper, and Flow Random Early Drop (FRED). These congestion controls require the routers to maintain state and operate on a per-flow basis, and the authors suggest that it could be the complexity of the per packet processing that prevents from wide-range adoption.

Fair Queueing can be very effective for congestion control. But if it is implemented in every router, it could be very complicated and costly. In responde to this concern, they try to distinguish the core routers and edge routers, giving the former no per-flow state as well as FIFO packet scheduling system, while leaving the latter to do complex Fair Queueing. This is called Core-Stateless Fair Queueing (CSFQ) in this paper.

CSFQ uses a distributed algorithm that core routers do not maintain per-flow state but in stead carry the information throught a label in each packet's header generated from the edge routers.

Secondly, FIFO queueing with probabilistic dropping on input was peformed on the core routers. Fluid Model Algorithm was first demostrated for an idealized bit-by-bit version and later extend to a practical packet-by-packet version.

Simulations between CSFQ and other four additional ones, namely, FIFO, RED (Random Early Detection, drops packets long before buffer full state), FRED (Flow Random Early Drop, drops based on flow state), DRR (Deficit Round Robin, weighted FQ) were performed on single congested links, multiple congested links, and coexistence of different adaptation schemes. The result shows that CSFQ achieves relatively fair bandwidth. It's far better than FIFO or RED and comparable to FRED. But FRED quires packet flow classifcation while CSFQ does not.

The last part of this article gives the reasons why fair allocations are important and introduces punishment for malicious end-notes that uses its own TCP stack to gain more priority of the network data flow.

The traditional approach to achieve fair allocations are very complicated to implement at high speeds among all routers, since each router has to analyse current flow and packet header to reach a decision. CSFQ could be more scalable when the number of routers increases.

Comments: It is understandable to utilize CSFQ in Tier-1 peering since it could simply the processing on the routers since they are obviously the "cores". But do we consider Tier-2 and Tier-3 ISPs to be edges or cores?

7. Analysis and Simulation of a Fair Queueing Algorithm

Ccongestion control can be divided in two aspects, 1) source varies the rate sending data, 2) gateway implements routing and queueing algorithms. This paper focuses on the latter.

Queueing algorithms can be evaluated in three quantities: bandwidth, promptness, and buffer space. The most common queueing algorithm used today is first-come-first-servced (FCFS). It simply discards any incoming packets when its buffer is full, and end-nodes could manipulate its implementations to take advantage of the network bandwidth. Furthermore, it lacks promptness for Telnet-like applications.

In order to achieve fairness throughout the network, Nagle proposed a fair queueing (FQ) algorithm that gateways maintain separate queues for each end-node. It lets data flows to take turns transferring packets (round-robin). But the main problem of FQ algorithm is that it implements fairness in the packet number level but doesn't take the packet length in to consideration. Thus, the authors incorporate a buffer allocation policy into the FQ algorithm.

Simulations of FCFS and FQ at the packet level were performed with different flow-control and queueing algorithms. Modified FQ rewards good-willed end-nodes and provides good bandwidth and promptness.

Comments: This paper sort of answers my question in mind when I read the two papers of last session, which factors in malicious end-nodes and smart queueing, instead of simply divides the bottleneck bandwidth into equal amounts for each thru-traffic connections.

6. Congestion Avoidance and Control

The Internet had the first congestion crash back in 1986 between Lawrence Berkeley National Laboratory and U.C. Berkeley. This paper pointed out that the causes is in the transport protocol implementations instead of the protocols themselves, and offered detailed solutions and rationales behind with simple codes to solve the problem.

The idea of conservation of packets was brought for a connection in equilibrium, in which a new packet isn't put into the network until an old one leaves. Therefore, for the packet conservation to fail, there are three possible ways and solutions:

1. Connection doesn't get to equilibrium: by transitive of equality, if the first packets are sent only in responsive to an ack, the sender's packet spacing time will match on the slowest link in the path, this is also called self clocking. A slow-start algorithm is implemented by sending one single packet to start with and adjust the window according to the time between two ack packets arrive.
2. Sender injects a new packet before an old one has existed: a good round-trip time estimator is the single most factor of any protocol implementation for a heavily loaded network. The authors developed a method to estimate variations and the resulting re-transimit timer derived from RFC793.
3. The equilibrium can't be reached because of resource limits along the path: if timers are in good shape, timeout indicates a lost packet and not a broken timer. Packet lost is more likely to result because network is congested and there's insufficient buffer along the path, so a congestion avoidance strategy should be adopted. Multiplicative decrease (cut window in half), addtive increase (increase cwnd) on each ack of new data, and sending min advertised windows cwnd are the three lines of code to avoid congestion.

While at the end nodes could control their own data flows, there should be some congestion detection on the gateway side to insure fair sharing of the network capacity before reaching its maximum capacity.

Comment: It is good to read a self-explanatory paper that gives you all the detailed explanations behind each steps, while still keeping the code simple. Cal Rocks! haha. Seriously though, it wasn't easy to identy the problems that caused network congestion, particularly from the protocol implementation perspective. And I really liked the figures which include packet size, timing and bandwidth, all in a 2D diagram.