DCII 28.11.08

Timescale Decomposition of Traffic Engineering - a good source of info on this is Richard Mortier's thesis

DCII 26.11.08

Receiver driven protocol design is an interesting area - one protocol that brings together a number of ideas I mentioned today is RLM - see
Steve McCanne's receiver driven layered multicast which was designed for multicast video - very nice!

meanwhile, why are there grooves on Hill's Road that are getting deeper year by year?

DCII 24.11.2008

preventing unwanted traffic, two lesser known attempts:
If you can't beat 'em, join 'em
and confuse 'em

Meanwhile, if you are interested in QoS, Multimedia and Multicast,
I did once write a book about internet multimedia with some colleagues...

DCII 21.11.08

today we looked at intserv and diffserv - an interesting resource to control in the context of 21t century concerns is energy - an excellent paper introducing a well evaluated set of techniques for doing this is by folks from Intel and Berkeley on Reducing network energy consumption via sleeping and rate-adaptation - the same techniques are also being applied in the context of servers (cpu and storage) in data centers - integrating all of the above would be a good thing - the gains (cost saving) can be large (estimates are that we waste more than 50% of power in servers and networks and that the total contribution to world energy consumption is between 2 and 4% - saving half of that with simple techniques is obviously worth doing:)

DCII 19.11.08

paying to use car pool lane is an interesting mix of priority and price based admission control!
On the other hand, aircraft landing slots tend to be more max min fair share to guarantee everyone lands within their max journey time, subject to maximising capacity of runway and thus involved explicit admission control at takeoff time (a.k.a. filing a flight plan!)

DCII 17.10.08

- since the notes are a bit sketchy (although Keshav's book is good here), I'd recommend a couple of good wikipedia articles on
Cross Bar switches, the
Clos Network, and if you want further reading, check out
spanning switches.

In general a good source of ideas on switches and switch router design is Nick McKeown's publications web page at Stanford:
tiny tera was one of his creations; more recently hes worked on open programmable (teaching/learning) router platforms.

lecture too slow?

DCII 7-10.11.08

Flow Control and Shared Media Access are related topics - goals are similar, but solutions differ, since flow and congestion control operate across multiple hops (as well as possibly hop by hop) and Media Access control schemes typically operate on a single hop and on a single technology, to which they are heavily optimised.

One simple difference then is that on a single technology, we can control the schedule and the MAC at the same time, whereas in the Internet in general, we have to put up with heterogeneity in the schedule in forwarding devices.

Fairness of TCP congestion control is usually defined by Raj Jain's equation
[(sum of rate_i)^2] / [n*(sum (rate_i^2))]

Efficiency (max goodput) - Aloha gives best performance under load where Poisson arrival (i.e. independent random arrivals) are such that throughput is 18.1% - you can work this out - if there are lots of sources sending, then if they send lower rate than this, you get less throughput and if they send higher you get more collisions, so you can figure out the mean rate for this best case (excercise for the reader:) for a given mean Poisson arrival and chance that no other node sends at same time (not 1, nor 2,3...)

slotting things makes it better

if the delay is low, listen before send is better

ranom backoff after collision is better

random backoff after listen before send is lower collision, but longer mean time

rts/cts before send eliminates hidden terminal problem (terminal hidden to sender is not hidden to receivers cts message hopefully)...

distributed schemes are fun...and popular, even though central scheme might be good in some cases (constant rate traffic...)

The latest thing (since 2001) is to consider network coding where packets are combined (through xor or linear coding) and recombined and then split out when they arrive over multiple paths - this is a very promising theoertical and practical trick, which can increase diversity and therefore robustness.

DCII 5.11.08

Errors show up even after CRC and TCP checksums - see this paper from stanford on
When the CRC and TCP checksum disagree

In round trip estimation, I commented on the obfuscation in the code - see for example this fragment:

/*
* The smoothed round-trip time and estimated variance
* are stored as fixed point numbers scaled by the values below.
* For convenience, these scales are also used in smoothing the average
* (smoothed = (1/scale)sample + ((scale-1)/scale)smoothed).
* With these scales, srtt has 3 bits to the right of the binary point,
* and thus an "ALPHA" of 0.875. rttvar has 2 bits to the right of the
* binary point, and is smoothed with an ALPHA of 0.75.
*/
#define TCP_RTT_SCALE 32 /* multiplier for srtt; 3 bits frac. */
#define TCP_RTT_SHIFT 5 /* shift for srtt; 3 bits frac. */
#define TCP_RTTVAR_SCALE 16 /* multiplier for rttvar; 2 bits */
#define TCP_RTTVAR_SHIFT 4 /* shift for rttvar; 2 bits */
#define TCP_DELTA_SHIFT 2 /* see tcp_input.c */

/*
* The initial retransmission should happen at rtt + 4 * rttvar.
* Because of the way we do the smoothing, srtt and rttvar
* will each average +1/2 tick of bias. When we compute
* the retransmit timer, we want 1/2 tick of rounding and
* 1 extra tick because of +-1/2 tick uncertainty in the
* firing of the timer. The bias will give us exactly the
* 1.5 tick we need. But, because the bias is
* statistical, we have to test that we don't drop below
* the minimum feasible timer (which is 2 ticks).
* This version of the macro adapted from a paper by Lawrence
* Brakmo and Larry Peterson which outlines a problem caused
* by insufficient precision in the original implementation,
* which results in inappropriately large RTO values for very
* fast networks.
*/
#define TCP_REXMTVAL(tp) \
max((tp)->t_rttmin, (((tp)->t_srtt >> (TCP_RTT_SHIFT - TCP_DELTA_SHIFT)) \
+ (tp)->t_rttvar) >> TCP_DELTA_SHIFT)



In processing acknowledgements, the congestion window needs to be evaluated - here's another fairly compact piece of code that does some of this work (opening the window as data is acked)

/*
* When new data is acked, open the congestion window.
* If the window gives us less than ssthresh packets
* in flight, open exponentially (maxseg per packet).
* Otherwise open linearly: maxseg per window
* (maxseg^2 / cwnd per packet).
*/
{
register u_int cw = tp->snd_cwnd;
register u_int incr = tp->t_maxseg;

if (cw > tp->snd_ssthresh)
incr = incr * incr / cw;