clog

Today we wrap up this course with the network systems design toolbag of tricks.

It could be instructive to take each trick and see where it showed up earlier in the course.

Statistical multiplexing - in conservation law and scheduling.

Pipelining- the entire idea both of a stack (vertical) and the network path (sequence of links and switches and routers) is illustrative of pipelining. Both closed loop and open loop flow control are trying to balance the pipeline, either through congestion control to share the bottleneck, or through admission control.

Caching/Locality - mentioned in passing memcached as a data center service, for example.

Batching also shows up in some data center distributed processing platforms (not really covered here)

Optimising the common case is probably something that BGP demonstrates how not to do!

Binding and Indirection - e.g. multicast addresses aren't real locations, but logical group identifiers, and the actual locations are distributed by the group membership protocol...

Randomness - as discussed in telephone routing! Also used in some load balancers when talking to replicated services (and flow or packet level balancing over multipath enabled routes).

There are many many other examples...

On the other, space could be cool but cooling in spacecould be very hard... this is maybe a nice example of how systems thinking can be applied using the simple laws of physics (gravity, EM radiation, thermodynamics) before you get as far even as thinking about resource management of processing, memory, comms.. ... ...

Things you do not need to remember:- Padhye's "simple" TCP throughput equation, and Erlang's call blocking probability ...

tue: traffic management timescales, users, large and small, demands, short and long...

signaling and soft state

thu: systems design patterns

This week we'll cover

• qjump[qj] - data center networking - a big special corner case of traffic scheduling.

• optimisation - routes for traffic, and traffic for routes

We've revisited flow and congestion control - one way of visualising the progress of an adaptive flow&congestion control protocol is the time sequence diagram:-

but note this is a massive over-simplification as really what you see here is an ideal with only one source and (apparently) only one bottleneck queue. In reality, in FIFO queues, traffic from multiple sources mixes and interferences (causing high variance in delay, hence round trip time, and very unpredictable loss. If we had Round Robin (by flow) queues, things might be a bit better, but how much? That is what we look at under Scheduling, and with the Generalised Processor Sharing model, can see how close to some ideal of "isolation" between flows, we can get.

With FIFO queues, RTTs and rates (as estiamted from data or ack packet inter-arrival times are going to be varying fairly chaotically, as the ensemble of flows at any bottleneck will not be coordinated in any special way as they all have different RTTs and perhaps just different performance senders, maybe different packet sizes, possibly different inter-packet timing at transmit time, etc etc

This week, we've got two random[ref] examples

1. random telephone routing

c.f. triangles

can we greedily find the tandem? (only) if you want to check the reasoning behind that part of DAR!

2. random drop congestion - serioiusly, today's lecture is mainly revision of IB congestion/flow control...

c.f.tcp arena

how many TCPs are there, really? again, only here for the keen background reader!

ref: there's a very nice study of general applicability of random choices in this harvard paper if you want some more background reading...

separately, in a discussion with a supervisee/supervisor, i realise some people may be interested in looking at real code to reinforce their understanding - for IB material, I strongly recommend Rich Stevens' TCP/IP Illustrated Volumes 1 and 2, but for this course, there's not really any such a nice single text - an alternative might be this:-

This week we wrap up BGP - looking at abstractions of the algorithm (The Stable Paths Problem in Interdomain Routing) and concrete realisations of problems in implementations.

While you may find the stable paths model helpful in removing noise from BGP complexity, I am not so sure its a great abstraction for thinking about how actually to resolve the problem(s) (non convergence etc). A nicer approach (by same lead person, Tim Griffin) is meta routing, which is very powerful and general, but would need an entire other course to discuss and I just put here for background in case anyone is interested !

Then we'll next make a start on Multicast Routing. Two compelling applications were tv/radio broadcast and software distribution. However, application layer overlays (Content Distribution Networks) have subsumed those needs - a great example is how Zoom coordinates multiparty sessions - this talk by their CEO is instructive. Also interesting is this paper on netflix content distribution approach.

Interdomin routing- BGP - key 4 slides - 124 126 131 132

Moving from intra-domain (within one autonomous system/routing domain/internet service provider) to intradomain, the key change is from policy within a domain (as used for steering traffic in centralised routing or in mpls or segment routing) to policy between multiple autonomous (i.e. independent) domains who may have conflicts and often require some level of information hiding (protecting knowledge of their customers' needs from competitors). So while connectivity is the minimum requirement, there's often no shared goal in terms of what is "optimal" (i.e. what routing metric to use) - we'll see that in default cases, for traffic engineering, and various tie breaking reasons, metrics implicitly creep in as an implici part of BGP routing, but not in any way consistently.