Summary: Comparison of Mechanisms

This extremely empirical paper was quite different from others that we've read this semester.  Like other systems papers it identifies the problem domain: composite networks with a wireless component make end-to-end flow control difficult, because (expected) packet loss on the wireless end has network-wide effects on windows, backoffs etc.  But instead of proposing a novel solution to add to the grab bag of tcp adaptations, or sidestepping the end-to-end argument to immediately suggest redundant reliability improvements to the link layer, it first formalizes and then evaluates the viable existing techniques for addressing the problem, and the various ways of composing them.  This is easier illustrated in outline form:

1.  End to End Protocols: keep reliability measures in the transport layer.

- E2E: TCP Reno, the baseline, is itself an end-to-end protocol 

- E2E-NEWRENO: partial acknowledgements

- E2E-IETF-SACK: selective acknowledgements

- E2E-SMART: selective acknowlegements with bitmaps for decreasing message complexity.

- E2E-ELN: explicit loss notification.

2. Link Layer Protocols: enlist the help of the lower levels in the stack, for high-loss networks

- LL: sniff tcp acks, infer local loss and automatically resend

- LL-SMART: smart selective retransmissions.

- LL-TCP-AWARE: less naive than LL, suppresses the duplicate acks that would otherwise initiate congestion control in the sender even though loss is local.

3. Split connection: this is a non-ideal but obvious solution: break the network into 2 networks by partitioning at the loss boundary, and let TCP operate in the two appropriate modes in each network.  This obviously sacrifices the semantics of TCP between the sender and receiver.

[... To be continued...]

Summary: MACAW

Although specifically designed for short-range wireless, MACAW provides a good introduction to the sorts of problems that a link-layer protocol needs to deal with in general.  In spite of the huge engineering efforts that go into them, it seems remarkable that collision avoidance protocols work at all -- and this paper (which is very well written and clear) shows just how ad-hoc the process of implementing reliable collision avoidance at the link layer can be.

The evolution begins with token-passing approaches to messaging: these are rejected out of hand because of the expectation that the network will be volatile, and time will be wasted dealing with lost tokens.  Next a a naive carrier sense approach is considered: the problem is that carrier sense tries to avoid collisions by not sending when a carrier is detected, while the authors show that collisions are an issue at the receiver and not the sender.   MACA evolves from CSMA by adding an acknowledgement pair (RTS-CTS) ahead of every data transfer.  This provides one piece of synchronization, in that processes that hear the RTS wait only long enough for the CTS to return, and processes that hear the CTS are the processes that could reasonably collide with the data transfer, and must deal with collision avoidance.  

MACAW's first evolution from this model is the sharing of congestion state among stations, which prevents races in which a connection gets all the bandwidth and another gets nothing, because of the interaction of the backoff windows.  After this, things get pretty wild: first an ACK, then a DS, and finally an RRTS packet are added to the protocol, which begins to look as complicated as TCP.  The problem of fair allocation that they are trying to fix is tied to synchronization: as the protocol develops, there are certain "contention periods" during which there is a chance of having an exchange go forward, but it is difficult to synchronize so that all contenders have an opportunity to content.  But of course, every extra message that we add to the protocol makes forward progress more complicated.

Summary: Scaling Routers

This paper wasn't like the others, was it?  It begins with a somewhat arbitrary goal -- a 100TB/s router architecture -- and describes the design decisions that will be necessary to realize this goal as well as the difficulties.  It goes without saying that a multi-rack design must be used, as the sheer power needed to represent the packets exceeds what is available on a single rack.  The crossbar switch and VOQ approach suggested by the previous paper is augmented by sandwiching a set of VOQs between two layers of switching fabric: these are driven not by a central scheduler that matches inputs and outputs based on availability, but according to a deterministic pattern that spreads the packet load across the intermediate layer of VOQs.  This introduces the problem of mis-sequencing packets in a particular flow: although allowed by a protocol this is undesired.  Full Ordered Frames First is proposed as a solution: FIFO queues are served in bulk, only when they have reached a certain capacity, preventing the arbitrary interleaving of outgoing packets (but if N is small enough mis-sequencing can still occur, right?)  A bigger challenge is making the distributed router resilient to the loss of individual linecards: this is addressed (as far as I can tell; I don't really get it) by introducing a hierarchy of switches and hence a level of indirection.

What can one say about a paper like this?  It was alienating to read about a topic I know so little about.  

Summary: [...] A Gigabit Switched Router

McKeown's paper provides a good introduction to the concept of crossbar switches as a departure from the shared backplane, and is invaluable in making sense of the Scaling Routers paper.  In a shared backplane, all ports must share the common bandwidth, and hence large scale backplanes suffer from high cost and low scaleability.  A crossbar eliminates the problem by replacing the shared pipe with a fabric comprising all possible point-to-point links between source and destination port, with switches available to a central scheduler to connect the endpoints.  This design naturally lends itself to efficient one-timestep multicast, as a single source can be crossed with multiple destinations in the switching fabric.  

To achieve 100% throughput, however, the scheduler must ensure that at each timestep, each input is connected to (and passing a cell to) each output, which seems achievable but tricky to predict or guarantee.   This problem is addressed in part by virtual output queueing, in which each input maintains a separate FIFO queue for each output.  In this way, a routable cell will never suffer from head-of-line blocking because it sits in a queue behind packets destined for a congested output link.  What happens when the demand for output ports is not evenly distributed, though?

couple comments I didn't get a chance to make in class:

• admission control is going to be a distributed computing problem.   a hard one.
• the reservation system described in class today resembles a specific distributed computing problem: 2-phased commit.  it takes a round trip to request that nodes "prepare" resources, which they then "promise".  2PC has some gnarly failure modes that I'm sure this system shares.
• isn't this in some sense a regression towards circuit-based networks?

Summary: Supporting Real Time Applications

A clear definition of "real time" in the context of internet traffic would have been helpful at the start of the paper.   In my mind, real time typically means that in addition to the obvious correctness requirements, operations have a hard constant deadline before which to perform their work.  The authors eventually weaken this definition: real time applications require "some bound" on delay, and we can enumerate at least two different classes of applications.  Applications that require "guaranteed service" correspond to the stricter definition of real time: service MUST be associated with a constant delay that represents the worst case: any operation below that delay is acceptable.  Like in the Shenker paper, the authors introduce the subjective element of user and application performance expectations to allow the relaxation of guarantees into predictions.  A "predicted service" application adjusts its behavior in order to deliver the expected performance to the user in light of the underlying network conditions.  The emblematic application is playback: if the player knows the delay it can adjust its buffer (and start point) accordingly and mask the underlying delays -- the packet telephone, naturally, cannot.  The authors go on to show that while a weighted fair queueing approach is appropriate to guaranteed service real time applications because it can provide a reliable worst-case bound, it is inappropriate for the predicted service model.  Instead they show (shockingly) that for such adaptive application, a FIFO queue provides less jitter, especially under burst conditions, at the cost of isolation.

Let's face it: David Clark doesn't write the most exciting papers.  I also had some difficulty with the concept of the "token bucket filter" and (naturally) with the flow control model calculus.

Summary: Fundamental Design Issues for the Future Internet

This paper had an interesting scope.  It presents itself as a survey of possible design choices for an unspecified future internet, and ends up instead making some very forceful arguments about the path that should be taken.  The authors show that the overprovisioning approach taken by telephony technology was efficient only because of the regularity (largely because it is human-initiated (and explicitly charged)) of telephone communication, and that internet traffic has too high variance for overprovisioning to be cost effective.

Their discussion of the efficacy measure challenges the assumptions of the current network technology that fair distribution and high throughput define optimality.  The argument for Quality of Service involves (in spite of the tiny bit of math) a fundamentally subjective element: the expectations of users are different for different applications, and this should be accounted for in the estimation of the optimal utilization of the resources.

I don't understand the admission control argument at all. Aside from the fact that it would be very difficult to deploy in a distributed fashion, admission control sucks in terms of fairness: your sister is on the phone all night so you can't make a call.  

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.