Finally, some systems principles....put in to practice.
and the Course Summary
In general, everything lectured is examinable. Any additional details (e.g. protocol specifics like packet headers/fields etc) or equations should be available as part of any exam questions.
One other dimension to think of Traffic Management - Signaling
congestion is a signal whether packet loss or ECN
price is a signal, whether per session/flow, or per day/month year
users demand is a signal - whether sending VBR video or rate adaptive TCP or QUIC traffic - the rates and duration (or file sizes) tell the network provider what to provision for,,,
aggregate demand (e.g. peering traffic or customer provider traffic) is a signal
so even without deploying an explicit signaling protocol (e.g. like RsVP) there is a lot of meta-data telling stakeholders what is affordable and what to be afforded.
So we looked at optimisation for routes, including multipath, and optimisation for flow rates/congestion pricing. What scope is there for improving the end-to-end protocols themselves in detail - for the first, we see MPTCP, which enables single source-destination pairs to take advantage of multipath routes, and for the second, QUIC, which reduces the latency in the application/transport/network pipeline through several mechanism improvements - of course, there are also now people working on multipath QUIC too, since we seem to be about to deprecate TCP in various forms (at least for web apps).
One question in class today was about QUIC migration (how does a session survive a change of IP address) - the details are discussed in this draft
Why is utility cast in terms of log of rate - risk aversion - see bernouilli's argument for this from a long long time ago!
In working out the function that gives us delay cost in terms of rate allocated to a link of a given capaciity, the headroom (load / (capaciity-load) ) is the simplest function, but queuing theory may give more complex results, and multipath assignments of traffic may multiple the impact...
a useful explanation of proportional fairness
basically, this paper covers the topic QJump !
Next, we'll go back to the wide area and look at joint optimisation (of the network and the end system protocols)
The main reason Generalised Processor Sharing is useful as a model, is to make clear the idea of a round. In work conserving schedules, the time spent by a given packet in a given flow in the router depends on the number of other packets from other flows, ahead of it, waiting to be transmitted to the next hop. The round advances but it isn't a measure of elapsed real time, as it depends on the number of flows currently in the round, which varies as sources start (and stop) sending, so flows join (or leave) the system.
Of course, if all flows were constant packet size and constant packet rate, and we only admitted as many flows as would fit in the capacity along the path, exactly, then the round would map to a wall clock (real time) - but flows are often variable in number, in packet rate and in packet size.
What the model lets us do is
a) reason about how fair and accurate a real scheduler is
b) work out admission control (can we accept a flow in the call setup/open loop flow control paradigm) or not - i..e for variable flows as above, described using some simple parameters like a linear bounded arrival process with a peak and burst size , that want some sort of minimum capacity guarantee (even if just roughly) - will they fit (without excessively disrupting the existing / established set of flows of packets?
c) what latency we might get for that flow, due to queuing and scheduling inaccuracies (op top of the basic latency due to simple propagation delay over the whole end-to-end path).
In the next section, we'll look at the exceptional setup & requirements in data center networks, where we may be able to make simplifying assumptions about the traffic and topology, and hence employ a simpler approach to schedulers.
Last week, we looked at open loop (call setup/signaling) and closed loop (adaptive feedback loops)
In both cases, some information on some timescale about network conditions is learned by senders.
For either case, the network could also use what it learns about sources to make decisions about treating packet flows differently - at the simplest level, this is queue management and giving more precise and useful feedback than packet loss. at the next level, it might be isolating traffic flows in different queues, and scheduling packets from those queues in some fair way, perhaps providing isolation from the impact of packets in other queues, which can then lead to some guarantees about minimum throughput and perhaps maximum latency seen by a given source/destination.
As the complexity of guarantees grows, the signaling protocols and scheduling algorithms can get more expensive - these days, most of the Internet doesn't make use of anything other than the bare bones/simplest approaches, if any:-)
one point about work-conserving - trains wait until their scheduled departure time at each hop, and need an agreed clock everywhere in the network to do so accurately. on the other hand, if you are organising an outing with a bunch of autonomous people on foot/bike/car, best to synchronise at the destination, rather than departure or intermediate points, which make the coordination nightmarishly complex:-)
Today, we're looking at Planes, Trains and Automobiles. Or Open Loop (pre-requested) versus Closed Loop (Dynamic, Adaptive) flow and congestion control.
For some elegant underlying maths, see the section in the Computer Systems Modelling course on Control Theory here CSM, which underpins many systems today (ABS in cars, thermostats in buildings, auto-pilots in planes, and TCP and related transport protocols in the Internet).
Next week, we'll also take a look at schedulers in routers, and see how their design depends on whether the goal is to support open loop flows, or give adequate feedback to closed loop systems, and what the performance criteria should be to compare different schedulers in terms of stability, efficiency and fairness (the latter term being surprisingly complex).
n.b. forgot to resume record, so the video is from pre-recorded version rather than today's live lecture- apologies:-(
as mentioned, Dynamic Alternate Routing, a.k.a sticky random routing, is a form of load shedding, and although telephone networks are circit switched, packet networks can use similar tricks by hasing flow state (e.g. by looking at source&destination IP addresses plus transport (TCP) port numbers, as an index, and then load balance traffic along similar routes - lots of techniques, most famously Valiant Load Balancing - widely used in cloud services - as usual wikipedia article on network load balancing is a decent starting point.
That's it for routing - next topics are flow&congestion control, followed by scheduling and optimisation.
