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.

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

This paper reviews the algorithms used in avoiding network congestions and offers several suggestions throughout the article.

As fiber optics and gigabit local area networks are getting more popular these days, the link speed could vary from several giga bits-per-second (bps) to 56K bps dial-ups. These various types of networks co-exist in the network, and there has to be some sort of flow/congestion control to achieve maximum possible speed while keeping collision / dropped packets to the minimum.

Traditionally, congestion control schemes kick in when congestion occurs near it's max possible throughput (cliff), but the response time which starts to increase significantly while throughput remains about the same (knee), occurs before cliff. In this paper, this knee-working-range is called congestion avoidance, as opposed to congestion control that keeps the network working before cliff.

Congestion avoidance utilizes the same increase/decrease algorithm that congestion control uses. There's a binary feedback signal that simply tells if the network transport is busy (1), or not busy (0) in the QoS header. The abstract model assumes that all users on the network receive this information and act on it accordingly.

User data flow demands can either flow to centralized decision-making managers or to decentralized locations, which is this research is based on. The successfulness of congestion avoidance is measured in four aspects,

• efficiency: the closer the total load to the knee, the more efficient
• fairness: maxmin fairness criterion, bottleneck sharing within the same group
• distributedness: awareness of the congestion on the user end
• convergence: time taken to reach a relatively stable state (knee)

Congestion avoidance is achieved through network monitoring and asking users to increase or decrease their load appropriately by a binary system. The decrease of data flow must be multiplicative from the experiment results, and additive increase with multiplicative decrease is the optimal policy.

Thoughts:

1. Instead of sending a binary bit about the congestion status of the network, would it be possible to have, say, a multi-bits status for the level of the congestion? e.g. 00 for extremely congested, every user stops sending new packets for a random amount of time, 01 for severely congested, 10 for mildly congested, and 11 for light-workload, please send packets faster? This way the user sides could decide if they need to slow down a little bit or a lot.
2. As we discussed in the first week, some applications require reliable data transmission, others more latency-critical. Maybe this extra magic bit(s) could include how fast/reliable it wants to be handled?

4. Understanding BGP Misconfigurations

This paper is a quatitative study of Border Gateway Protocol (BGP) misconfigurations by analyzing configuration errors over a 3 week period. The authors concluded that most errors, while 1 on every 25 incidents actually affects connectivity, could be prevented through better router design or protocol revision.

BGP is a policy based protocal in which autonomous systems (ASes) receive and send routing information to hosts and neighbors. They put the misconfiguration into two categories: origin misconfiguration, and export misconfiguration. An example of the former is a wrong prefix injection into global BGP tables; for the latter, the router exports a route that shouldn't go through.

The effects of the misconfiguration were discussed in three different aspects, including routing load, connectivity disruption, and policy violation. The new routes lasting less than a day are carefully considered as misconfiguration while using external vantange points and administrator email surveys to check if it actually caused the above three kinds of effects. Selection bias is addressed by the authors, and by comparing the results of the email surveys and vantage points, it is kept to a minimum in a safe way.

The physical links and relationships between ASes are usually commercial secrets, and Gao's algorithm was used to estimate the actual linkage, which is based on three rules: 1) all valid AS-path routing information goes downward (e.g. from provider to customer), 2) AS-path can have at most one peer-to-peer edge, 3) ASes with more neighbors are likely to be providers.

Results: A equivalent to 0.2-1.0% of the glocal BGP table size suffers from misconfiguration each day, which means up to 3 in 4 new route annoucements per day are misconfigs. While connectivity was surprising solid, affected in onlly 4% of the misconfiged announcements or 13% of the misconfig incidents, the extra loading in the routers takes up to 2% of the time, or more than 10% of the total update load. In an extreme case, it went higher than 60% of the update load with 15minutes averaging.

The paper investigates the causes of misconfiguration and classify the human errors into slips (errors in the excution of a correct plan, e.g. typoes) and mistakes (erros in the plan itself, e.g., logic bugs). In owing to the human operatior error rate affects the system, as seen in phone network, aircraft, and bank databases, the authors suggests that BGP router configuration is far from error-free because of the command-based editing and lack of high-level languages and checking. Protocol revisions/extensions were suggested, and active alerting wrong routing infomation was also proposed.

Afterthoughts:

1. This is a carefully examined paper with almost all stastistical and bias errors were carefully considered, which makes the the results very confincing that the BDP is far from perfection.
2. It's interesting to see that they conducted this experiment after Christmas during the New Year. There's no explanation of why they specifically chose this period depite their careful, scientific setting. Is it probable that there is less/more routing updates during this period?