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.