Summary: Congestion Control for High Bandwidth-Delay Product Networks

In the light of the clean slate nature of the Katabi et al. paper, other attempts to address congestion control/avoidance within the framework of TCP seem severely constrained.  The holy grail is a fair and efficient scheme whose parameters are not dependent on either the delay bandwidth of the network or the number of simultaneous connections.  Networks with massive bandwidth and high delay like satellite networks are poorly served by slow-start, which is unlikely to fill the pipe especially with short sessions.  Worse still, the TCP protocol's use of packet dropping as a signal and AIMD as a windowing strategy plays poorly with high delay conditions: it is easy to see how this will cause oscillation.

These issues are addressed by starting from scratch and proposing a protocol spoken at the ends AND the core, that separates the controls for efficiency and fairness, and uses explicit feedback in packet annotations to achieve a core-stateless solution.  Basically, the senders request an optimal window based on the application's needs, which is adjusted in the packets enroute, such that the eventual acknowlegement represents the available resources at the bottleneck router on the network path: one round trip is sufficient to initialize the window to a reasonable value.  

The obvious criticism of this otherwise beautiful (and intuitive) system is the difficulty of implementation in the existing infrastructure.  That said, the author's concept of a TCP over XCP overlay is rather elegant: just as CSFQ used the concept of router "islands" in the core, islands of XCP with TCP-aware edges could be introduced piecemeal into the core.

Summary: Random Early Detection

A good paper begins with a good idea.  The insight of RED comes from the observation that  a powerful gateway-side congestion control algorithm must focus not merely on anticipating and preventing congestion events, but on quality guarantees like maintaining consistently low latency and high throughput.  This boils down to two things: don't operate with full queues, as this causes high latency for all connections, and send feedback in such a way that you avoid synchronous back-off requests, which can result in dramatic underutilization of bandwidth when all clients exponentially reduce their windows.  That the RED technology supports actual binary feedback for compliant systems and packet-dropping feedback otherwise is a tremendous asset, as it ensures that the technology could be deployed router-by-router.

RED implements these heuristics by adding a third (middle) state to the naive binary congestion control algorithm (passive acceptance or global back-off feedback based on average queue size) , in which a client sending a packet receives feedback (literal or implicit in the form of dropping) with a probability that is a function of the average queue size.  Exponential decay is used in averaging to implement a low-pass filter that prevents oversensitivity to recent events, and the probabilistic function is random, preventing bias and coming very close to enforcing the fairness properties of much less scalable solutions like connection-wise queueing, because connections that use more than their fair share of the queue are more likely to receive feedback.

Of course, since the authors recommend tuning the parameters to keep queues small, random dropping within a single queue is extremely unlikely to approximate well the fairness of FQ.

Summary: Core-Stateless Fair Queueing

It would have been cheating to point out in my previous post that fair queueing sounded expensive, both in terms of the added overhead in processing per packet and the extra state (n queues where n=connections) that must be stored -- wouldn't it?  The title of the CFFQ paper says it all.

To realize the benefits of fair queueing without globally incurring these costs, Stoica et al. propose an "island" based approach in which edge routers implement FQ and core routers (in "stateless core" fashion) infer state from packets annotated at the edge routers.  The core queueing algorithm is basically FCFS (FIFO), with a probability (a function of the state and the packet) of dropping the packet before enqueueing.  As did Demers et al., the authors begin with a clear description of the kernel of their algorithm in an idealized setting: a bitwise, bufferless router.  With knowledge of the outgoing link speed and flow arrival rates, and assuming we can estimate a "fair share" rate, constructing a per-bit drop probability is straightforward.  Exponential averaging is used at the edge routers both to estimate aggregate traffic and per-flow rates, and to estimate the link fair rate: all three will be used by the core routers' probabilistic function.

This is a great paper.  The island construct, as the authors hint, is very broad: in its most narrow sense, compressed onto every router, it is basically Fair Queueing.  At the opposite end of the spectrum, at the endpoints (if we go even further than "all-core", at the ISP boundaries), it begins to resemble flow control generally.  Placed where it is in islands of core routers embodies the compromise between fairness and scalability that the paper argues.  I would have like to have read more about precisely why packet classification is considered so daunting a task.  The extended discussion towards the end of the paper of unfriendly flows, the identification technique as an alternative to the allocation technique, and punishment mechanisms is pretty prophetic.

Summary: Analysis and Simulation of a Fair Queueing Algorithm

The principal motivation of the paper is the observation that flow control alone, implemented as it is at the communication endpoints, cannot guarantee a congestion free network, let alone fair usage of the network's bandwidth.  The first reason is straightforward:  flow control (mostly) assumes that congestion is a condition that occurs at the other endpoint; the core network resources can give no feedback, and hence are hidden.  The second is that implementing more robust flow control mechanisms at these endpoints misses the point, because congestion avoidance is entirely elective: a user who isn't concerned about network performance overall can simply disregard the packet conservation principle and ignore feedback.  The problem must instead be addressed at the queues of the core routers: first come, first served treatment of the queues must be replaced with an algorithm that, in a game-theoretic fashion, rewards the well behaved users and punishes the abusers, where the "well-behaved" designation can be achieved by endpoints by implementing reasonable flow control.  

The problem is solved logically by Nagle's algorithm: instead of maintaining one queue managed in FCFS fashion, maintain a queue per "user" (a debatable designation; Demers et al. define a flow as analogous to a socket: a connection between two endpoints) or flow, then apply FCFS within queues and round robin among them.  This clearly achieves the desired fairness properties at the packet level, but the authors show that to address differences in packet sizes something like a bit-wise round robin scheme, while unrealistic, would be desirable.  They go on to demonstrate that a packet-wise round robin scheme can be realized by applying the same accounting used in bitwise RR, and using the BR finish times as the packet ordering.  To address the issue of rewarding users with promptness who have had less demand (again, giving that telnet session a break), actual BR finishing times are replaced by bids derived similarly but with reference to a magic parameter that influences the "memory" of a flow's history.

This last detail and the following performance section were fairly difficult to follow.  It is clearly tricky to reason mathematically about periodic functions and queue dynamics, but the idea is at bottom so intuitive that I was unsure it was well served by so difficult a discussion.  Their results are very convincing: as we feared, hosts that do not implement flow control fared better under FCFS, and the miscreants were rewarded, whereas fair queueing kept its promise of rewarding conservative users and effectively protecting the bandwidth of compliant flows from abusive ones.  

I found myself thinking about OS schedulers while I read this paper.  Is that so wrong?

Paper Summary: Analysis of the Increase and Decrease Algorithms

My experience with this paper was emblematic of my relationship with mathematics: distant, aesthetic admiration and sweaty palms.  While I'm following the argument I'm moved by its elegance, but by the end of the paper I am merely intimidated.  Talking about what I do follow is probably the best course of action.

We begin with the intuitive representation of network performance as a pair of graphs for throughput and response time: they are structurally different but share the features of a "knee" and a "cliff."  The "knee" represents saturation of resources (queues, etc), the intervening curve a period of congestion, and the "cliff" the point of rapid, perhaps irrecoverable degradation.  The distinction between congestion "avoidance" and "control" are associated with these points, respectively.  In order to reason mathematically about a number of possible increase/decrease controls, it is necessary to fix certain elements of the system.  These include

• Feedback: Binary feedback is chosen as the resource-side mechanism for reporting overloading, as anything more complicated would require per-user accounting on the resource side, and our goal is to reduce the stored state.
  
• Fairness calculation: we chose a fixed fairness calculation that more or less corresponds to intuition: if the system is fair (fairness==1), then each user is receiving 1/n of the system resources.

With these elements fixed, the paper proposed a vector-based model that allows us to easily visualize the behavior of increase/decrease in the efficiency and fairness dimension, over a vector in R^2 representing 2 users (from here it is easy to abstract, though not visualize, moving to n-dimensional space).  It is demonstrated visually that additive increase increases utilization parallel to the fairness line regardless of where it begins (because x=y is a 45% slope from the origin and any 45% slope in the same direction is parallel), and multiplicative decrease represents a line going through the origin whose slope depends on the initial point.  It is further demonstrated that AI/AD would go into oscillation without moving towards the fairness line at all, while AI/MD converges.  It is left to the reader to note that MI would increase utilization AND decrease fairness.

Chiu et al. go on to prove algebraically these visual intuitions.  This proof is wrinkled somewhat by the distributivity requirement, which severely limits the users' view of the system needed to ensure optimal convergence.  Control truncation is introduced as an approximation solution, but I must admit I don't understand it.  Finally, nonlinear controls are examined briefly, but discarded principally because of their sensitivity to parameters, which frustrates the goal of minimum user interaction.

Criticism of a paper I only partly understand would be hubristic in the extreme.

Paper Summary: Congestion Avoidance and Control

"I don't say 'evasion;' I say 'avoision!'"

  - Kent Brockman

After a brief defense of the internet protocols, Jacobsen et al. begin their paper with a description of a real-world internet meltdown.  What would otherwise be a fairly abstract and sober discussion is therefore framed by a crisis: protocols aside, the implementations were broken and needed immediate repair.

They begin with the intuition that a well-behaved and stable network obeys the packet conservation principle: at equilibrium, a packet leaves for every packet entering the system, and vice versa.  Even ignoring the notion of equilibrium this notion addresses congestion; if we send a packet only after receiving the ACK for our previous packet (this would be self-clocking), we guarantee a stable system but squander its resources, leaving gaps in the pipe and the queues.  Slow start addresses the issue of filling those queues and pipes (even though doing so more aggressively than self-clocking risks overwhelming the receiver) safely; every ACK means injection of a new packet plus a +1 increase in the window; thus the window increases exponentially and we approach equilibrium logarithmically, guaranteed to exceed the receiver's capacity by at most 2X.  As slow-start addresses the problem of efficiently reaching equilibrium, round-trip estimation addresses maintaining that equilibrium.   As a network becomes congested, variance increases as well as round-trip time, so making accurate estimates must involve a variance measure; otherwise it will be reacting to noise as much as congestion.  The authors favor mean deviation (the avg(|m-a|) rather than sum((m-a)**2) ) as a cheaper (and overflow-safe) approximation of real variance.  Finally, addressing resource issues on the whole path that might prevent a connection from reaching equilibrium requires a real congestion avoidance algorithm based in queueing theory: this is the additive increase/multiplicative decrease that is addressed mathematically in Chiu et al.

This is new material for me, so few criticisms spring immediately to mind.  I think it is cool to observe complicated theory generating very simple implementations, and even cooler that independent theories (slow start and AI/MD) compose so well into a single algorithm.  Clearly there are a number of assumptions in spite of the formality of the discussion, but I am unsure how reasonable they are.  It is assumed, for example, that all packets are either eventually ACKed, or fail to be because of buffer expiry or damage (they further indicate that loss due to damage is much less than 1%, but I am unsure where this comes from).

Paper Summaries: Routing Notes and Inferring AS Relationships

 http://portal.acm.org/citation.cfm?id=504616

(Because Gao's paper is largely instructional, and indeed does a better job of explaining the BGP protocol than the text, I have combined my discussions of the two documents into one posting.)

Far from being an arbitrary graph of peers over which routing decisions are made based on algorithmically-determined best paths, the internet backbone comprises an asymmetric collection of commercial networks that buy and sell transit capabilities to one another according to business policy.  IGP protocols like OSPF can take a relatively simplistic view of the network graph, interpreting it as an undirected graph with positive edge weights representing distance or latency.  An Exterior Gateway Protocol like BGP, on the other hand, must extend this model to include directed edges (to account for provider-customer relations) and cost as a second set of weights, which can be negative (which itself rules out the use of Djikstra's algorithm-based protocols like OSPF.)  

Perhaps more significant than these structural differences in the underlying graph representation is the fact that between Autonomous Systems, policy rather than optimality determines routing decisions.  In a world in which forwarding and accepting packets means spending or earning money, and the choice of routes affects these resources, ASs and BGP step in to address the issues of cost-effectiveness and accountability mentioned in Clarke's list of goals but not addressed in the internet protocols.  Under BGP, routing announcements are passed through a set of import filters in order to suppress certain messages and reorder others according to local policy -- and before propagating these messages to other ASs, they are passed through an independent set of export filters to apply other policies.  Independent of this extensible filtering mechanism is a path-vector routing protocol that in some sense resembles an IGP, where the ASs themselves are the nodes.  But because the choice of routes is determined by best path only when a policy (expressed via LOCAL_PREF or with other tricks) is nonexistent or finds a tie, the function of BGP more closely resembles a packet-filtering firewall (usually expressed as a set of rules that are interpreted into pipelined filters) than a distance-vector or link-state routing protocol.

At least at the simplest level, the sorts of policies that an AS would want to enact are intuitive.  If the AS has multiple customers and multiple providers, it wants to propagate routing information about its customers to all its providers (and vice versa) because any traffic to/from the customers makes the ISP money.  On the other hand, it does not want to propagate routes from one provider to another, as this could create a route through the AS where unbillable packets from the second provider are forwarded to the first, costing the ISP money.  Other rules follow in a similarly intuitive fashion, and when the model is complicated by the addition of peering and sibling roles, more rules need to be inferred.  The four roles described in the Gao paper are not built into the BGP protocol; rather, they are a reductive classification of the most common configurations between border routers, enforced only by the policies in import and export filters.

Gao's paper addresses the problem of discovering the graph structure and hierarchy of the various Autonomous Systems, given the handicaps of information hiding on the part of the commercial ISPs and imperfect registration and directory services.  The approach is to use the ASPATH of the BGP route update messages to infer, in aggregate, both the hierarchy tier of given ASs and the binary relationships between ASs, in terms of the classifications given.  The first heuristic draws a relationship between the degree of an AS in the network graph and its level in the tiered hierarchy.  The second says that a path from a customer (through several tiers of ASs) to another customer can be visualized as an uphill path, a peak or plateau (a peak if the top-tier AS is unpeered, a plateau two nodes wide otherwise), followed by a downhill path.  Along the uphill path, all binary relations are customer->provider or sibling-sibling, and the reverse is true downhill.  The first heuristic is used to decide the various tiers of the nodes participating in the hill analogy of the second, and the end result is a classification of BGP nodes into service relationships.

Interesting as the approach may be, it is far from complete.  Gao gives little evidence that the categories used in the algorithm reflect the broad range of policies and configurations existing in the real world; since the author invented the categories, accuracy in classification may be self-satisfying.  The heuristics rely on quite a large number of magic constants that will probably vary widely as the underlying networks grow and change shape.  This said, the paper has great instructional value, providing a rather complete picture of Autonomous Systems and the BGP protocol.