Wednesday, November 28, 2012

Principles of Communications 2012 up to L24 - week 8

Finished up with signalling, admission control, capacity planning today.

Comments on quantity of material and supervision q&a welcome 0- will work on this a lot for next year.

Was asked about reference (e.g. textbook) on WiFi  - not sure of good text (neither of Keshav's books cover this) but there's a nice tutorial online at Berkeley here

I'll see if I can find a better standard text on this, as it is quite interesting I feel!

Friday, November 23, 2012

Principles of Communications 2012 up to L21 - week 7

Have covered capacity of ad hoc wireless mesh, plus a bit on LP this week

As students pointed out, PR versus nPR is like comparing "reservation" and "staggered" forwarding in ad hoc mesh (i.e. pipelined forwarding is equiv to the first hop winner getting access to the whole path, whereas non pipelined case defers)

On SPT v. MST
http://www.me.utexas.edu/~jensen/exercises/mst_spt/mst_spt.html

xkcd has a (not so rare) educational cartoon on spectrum allocation which is useful:
http://xkcd.com/273/

LP - simplex solver - see
http://en.wikipedia.org/wiki/Simplex_algorithm


Wednesday, November 21, 2012

Principles of Communications - interim lesson

If someone wants to become a major hero, then fixing the Raspberry Pi linux USB/ethernet driver to remove "buffer boat" would be a very nice exercise - see here for references on what to do, and why - its an interesting lesson in
buffering, latency, and TCP/Queue Management interactions

http://www.teklibre.com/~d/bloat/Not_every_packet_is_sacred-Battling_Bufferbloat_on_wifi.pdf

Not every packet is sacred

Friday, November 16, 2012

Principles of Communications 2012 up to L18 - week 7

Scheduling

Randomness is your friend...see below too

Switching

should mention monsieur Clos!!
n.b. there may be an error in the slide on sorting/batcher switch - will check:)

Sharing

mention inventor of spread spectrum:
http://en.wikipedia.org/wiki/Hedy_Lamarr

A week full of s's...

Friday, November 09, 2012

Principles of Communications 2012 up to L15 - week 6

This week, Optimisation, and a start on Scheduling.

One question came up in optimisation - In the formulation of delay as
F/(C-F),  which I characterised as the load over the "headroom",
this is a dimensionless result - yes - its basically the average number of customers in an M/M/1 Queue (see Richard Gibbens slides from Computer Systems Modelling). However, in a work conserving router with a fixed speed output link, this translates into delay by multiplying by the
mean packet size/the output link line rate (which would have dimension time:)

Several people asked for more info about control theory - the chapter in Keshav's book (as per course web sight) is really quite clear (goes a bit past what I would ask, but knowledge is good, right?)...so recommend an hour reading that chapter - it also has exercises that are useful.
Keshav, S. (2011). Mathematical Foundations of Computer Networking. Addison-Wesley,
covers all but the graph theory bits of the maths I cover (and also covers some queueing and other performance things you might find useful as an alternative text, if you are attending Dr Gibbens' course too).

As per previous blog,
Keshav, S. (1997). An engineering approach to computer networking. Addison-Wesley
is also a useful text for the more protocol-oriented parts of this course.


Finally, if you are interested in the optimisation framework, then I recommend some of Frank Kelly's papers from the statslab - for example, this one briefly menions why we might take the sum of willing to pay times log of rates
w ln(x) 
as the  network view of the utility function..
.Fairness and stability of end-to-end congestion control

The two plots of functions of u_l (link utilisation of link l) are for
two different cost functions where the first one is exp(u_l)
and the second is n*(u_l^n) where n is a parameter (not the number of users - its just to generalise the function to a class of functions whose steepness/convexity can be varied by increasing n!

Friday, November 02, 2012

Principles of Communications 2012 up to L12 - week 5

Just made a hash of control theory....need to re-hash on monday to clarify- slides updated to show how G1 and G2 fit - see slide 23 on
control theory slides

Main point was to go through the decomposition of the control+gain+feedback
into separate boxes, to allow one to play with different controllers, and then re-compose to check the final transfer function for stability and for steady state error:- (slide update also fixes a couple of typos_

Hence, need to expand all the steps in the worked example with the video server and setpoint cpu load monitor

Will re-do on monday w/ additional steps for deriving the overall tranfer function in the s domain for the two different controllers of the CPU system whose basic (G0) behaviour is an integrator in time domain, so 1/s in Laplace transform/freq domain. this applies to the setpoint (Us) and the Mean Completion rate (Rc), so that when we look at these in the transform domain, we have the integral of them over time, which gives us a 1/s in the terms
for Us(s) -> Us/s and Rc(s) -> Rc/s


Looking at the slide where we first encounter G1 and G2, this is basically the design of a ne wsystem where G2 is what G0 was before (i.e. the video server modelled as an integrating service over time, but now with a new, regulated/controlled input), plus G2, which is the controller C, which has inputs which are the setpoint, and the demand, and outputs the new accepted/admitted flows which now go as inputs into our G2 (what was G0) who has an additional input, Rc(s) (or Rc/s).....

G0 = 1/s
Now add an (as yet unspecified) controller, C
and expand to the two stages, G1 and G2:

G1 = C.G0 / (1 + C.G0)
hence G1 = C/s (1+C/s) = C / (s + C)
G2 = G0 / (1 + C.G0)
hence G2 = 1/s / (1 + C/s) = 1 / (s + C)

Now our overall system is the composition of G1+G2, with
G1 handling the input decision, and G2 taking that plus the completion rate of work:
U(s) = G1.Uset/s + G2.Rc

so proportional controller just as C = K
and proportional-integral (PI) controller has C = K(1 + Ki/s)
where K and Ki are the constants to be chosen by designer:)


U(s) = C.Uset/s.(s+C)    + Rc / (s+C)       1.
which with C=K
 ( a proportional controller), gives
U(s) = K.Uset/s.(s+K) + Rc / (s+K)
Proportional controller:
stability: pole at s=-K, therefore ok.
error: lim of s.U(s)
= s . [K.Uset/s.(s+K) + Rc(s) / (s+K) ]
assume Rc(s) = Rc/s (i.e. Rc doesn't vary fast compared with feedback loop time)
= s.  [K.Uset/s.(s+K) + Rc /s.(s+K) ]
= [ K.Uset - R / (s+K) ]
which as s->0, goes to
Uset - Rc/K - so the error is Rc/K

For PI controller, put C = K(1 + Ki/s) in to 1 instead


G1=C G0 / (1 + C G0)
G2= G0 / (1 + C G0)

C = K(1+Ki/s)
G0 = 1/s

so G1 = K/s(1+Ki/s) / (1 +  K/s(1+Ki/s)) (* top and bottom by s^2)
 = (Ks + KKi) / (s^2 + Ks + KKi)

G2 = 1/s / (1 +  K/s(1+Ki/s)) (* top and bottom by s^2)
 = s / (s^2 + Ks + KKi)

response = Us G1 / s + Rc / s G2


....need to do this in tex:)

If people are interested in the stability of TCP's AIMD, then I have to say that its complex - to my knowledge, no-one has shown it for a network with FIFO "drop tail" queues, and heterogeneous RTTs - however, with an Active Queue Management system (like RED - see upcoming lectures on Scheduling and QUeue Management) there are some solutions - see
1. paganini's proof
and
2. INRIA work


Friday, October 26, 2012

Principles of Communications 2012 up to L10 - week 4

Made Errors:)

About to Start Flow Control. (Feedback welcome:)

Asked what books cover the non math component of PoC - answer is on the course web page - best reference is the other book by Keshav (An Engineering Approach to Computer Networking), which should be in most (college/lab) libraries.

Asked where to find proof of the bound on diameter of Erdos-Renyi graph - refer to this review/tutorial paper:
http://www.barabasilab.com/pubs/CCNR-ALB_Publications/200201-30_RevModernPhys-StatisticalMech/200201-30_RevModernPhys-StatisticalMech.pdf


Friday, October 19, 2012

Principles of Communications 2012 up to L7 - week 3

Couple of errata on graphs :

1.
s/walk/path/ in one slide (i.e. whether a vertex can appear more than once!)
2.
p<3 -="-" algorithm="algorithm" dar="dar" does="does" finding="finding" fraction="fraction" good="good" greedy="greedy" high="high" in="in" is="is" make="make" of="of" p="p" probability.="probability." property="property" succeed="succeed" sure="sure" that="that" to="to" triangles="triangles" with="with">
progress:
finished LS&DV Routing -
Coming Monday,  wil complete Multicast, Mobile
Wednesday, errors
Friday, Flow Control& Start on Control Theory

Friday, October 12, 2012

Principles of Communications 2012 up to L4 - week 2

Today, started Graph Theory (well, background at least)
Monday, will pick up on graph properties, random graphs, small world/clustering and searching. Then Next week, should cover most the Routing area.

For further edification and amusement,

Cambridge Networks Network

http://www.cnn.group.cam.ac.uk/

Erdos Bacon number
http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Bacon_number

Erdos zombies:
http://xkcd.com/599/

kirchoff geek traps
http://xkcd.com/356/

Friday, October 05, 2012

Principles of Communications 2012 L1 - week 1/2!

oops #1 - failed to spot 2nd box of lecture handouts - so they will be available on monday - apologies - mea culpa (not the admin fault)

oops #2 - 1kbps on the net is 1000 bps, because the k is from the sample rate (so a KHz refers to 1000 samples a second) but 1k bits (or bytes) in computer speak refers to 1024 bits (or bytes) coz its 2^10 memory locations or whatever

so being pedantic and wrong on slide 9 is a bit embarassing:)

Michaelmas Term 2012 - Start of Term & IET President's Inaugural Speech

Today (well this week) term kicks off and I'm teaching Principles of Communications to Part II, and Network Architecture to Part III and MPhil students.

Meanwhile, last night, I attended Andy Hopper's really excellent speech at the IET in London, where a host of stars turned out, including an MP who is an engineer (and female) and other luminaries to hear his very very good words on how to make things innovative - he used a lot of nice use cases, taken from his experience and others nearby (ARM, RealVNC, Xen and of course UbiSense) but he also made some very good high level points about UK industry (under investing in Research) and how to fix that, and about Universities (do LOTS of innnovation and let the market pick) and about government (stop the REF now - it served its purpose and is past its sell by date and actually probably damaging things now). All good stuff - I dn't want to stand up and ask a question but if I had, I'd have asked him about the new stuff we're doing with raspberry pi, Digital Life Foundation, OcamlLabs, and Computing at School, all of which have extreme "business model" approaches -
See IET TV of Andy Hopper's talk

might have been a good place to name check serial entrepreneurs like Ian Pratt and Keir Fraser (Bromium and Convergent.IO, post xen), too....next time:)

Two ideas
1. cheap opthalmoscope made out of toy microscope & android camera phone & some simple DSP code (on the phone
2. remote control for hearing aid using ultrasonic sound from the android phone (speaker can go to frequencies higher than you can hear, but hearing aid can hear them) so you can reset programmes for different environments
(both for me:)

3. Must talk to CCNx folks about Andrea lo Pumo's work on policy routes for content centric networking - ok, so we are ignoring "content value chain" but I think its more than just "cache flow" versus "packet flow" :)

Back to school.....

Tuesday, July 10, 2012

testbeds - its not what they are, its who they are

my experiences of testbeds (arpanet, satnet, dartnet, planetlab, onelab, umbrella, gini, etc etc) is that it isn't so much the technology and budget, but the cohort of people engaged that mark out a testbed for success or failure or damp squib.

but that's just my experience - what do other people say?