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?

Friday, November 25, 2011

Principles of Communications - Week 7 - Nov 25

FInished COntention Networks, and Shared Media/Multihop Capacity, and just started Traffic Management.

Goal is to complete traffic management on Monday Nov 28th. And wrap there- LP is a step too far.

Will update on monday to describe which components are non-examinable. In general, see
the contents for the course,
here

Friday, November 18, 2011

Principles of Communications - Week 6 - Nov 18

Today, I wil finish the section on switching (covering routers as well as TDB and Space switch designs) - since we have "Silicon Valley comes to Cambridge" in the building today, its worth talking about the link between
Cisco, Sun Microsystems and Stanford University, then we can also mention the link with Granite and Google (Dave Cheriton) and Arista. Also, the early Sun 3 and CIscos were same M68000 multibus motherboard + ether*n + T1 serial line....alas, only sun ran BSD Unix, whereas Cisco wrote a low level executive called IOS (nowhere near as innovative as 3 years later when Apple wrote an Operating System for the iPhone and called it IOS...)....if routers had run BSD unix, the Internet might be a better place:-)

Next week, we;ll cover contention networks (shared media0 as well as capacity of multihop radio nets.

Friday, November 11, 2011

Principles of Communications - Week 5 - Nov 11

Finished Control Theory
and Optimzation Framework for IP/TCP networks

Next: Monday 14: Scheduling and possibly might get to Switching by next friday (18th).

Friday, November 04, 2011

Principles of Communications - Week 4 - Nov 4

Reached end of flow control

couple of very insightful questions about
1) reduce buffering in IP routers
ii) play with RTT by delaying acks in smart phones...to help redux negative impact of buffer bloat!

Monday - control theory
wed/fri optimization.

Sunday, October 30, 2011

Principles of Communications - Week 3 - Oct 28

Got as far as channel model of errors after modulation/coding, and a basic intro to Shannon. [New copy of channel slides just posted that fixes a couple of errata pointed out by students - note, that specific material is non-examinable]

Starting Oct 31, Will finish errors, then move on to flow and congestion control.

Friday, October 21, 2011

Principles of Communications Week 2 2011

Today (21.10.2011), got as far as LS routing (having rather messed up explanation of DV).
Monday, will repair DV, and then cover
multicast and mobile.

I need to re-check the DV count to inf example isn't wrong....

Then wed/fri 26/28 cover errors...hopefully with less errors...

Friday, October 14, 2011

Principles of Communications Week 1 2011

I've just got up to the representation of graphs today (14.10.11) - see
lecture 4 including kirchoff - Monday, we'll do Erdos and Bacon.

SO we've covered Systems and Layers mainly, if you want to look at Supervision topics...

Wednesday, January 19, 2011

Escher Circuits and Perpetual Immotion

Followers of my blog will be aware of my discovery of circular wind patterns across Cambridge, that cyclists have suspected are always against them. For several years, I have taken advantage of this, and make my journeys out of phase with other cyclists
thus getting blown along in the right direction "for free".

Accidentally over the last couple of weeks I have discovered another phenomenon in Cambridge, which requires you to travel out of phase with the wind, but when there isn't any, and that is that there are certain routes which are down hill all the way there and back again. I refer to these routes as Escher Circuits after the great MC Escher's famous eternally descending waterfall (and the stairs in the library in the Name of the Rose of course, by the oft-copied inimitable Umberto Eco).

The existence of Escher Circuits has long been disputed since first suggested by the theoretical natural philosopher, H.King in his paper "Not enough string". The possible existence of Macro-circuits, measurable using crude mechanical devices was put forward in the seminal work by A. Hitchcock "Just enough Rope". But until now, these were mere hypotheses.

Of course, those of you who are students of natural philosophy will be aware that a naive analysis would dismiss such theories as contrary to the idea of conservation of energy, for surely, the cyclist pursing her cyclic route, would ever gain momentum.
However, my observations have shown that the real-world phenomenon is more subtle than the mind of man. While it is the case that the journey from A to B is downhill, as is the journey from B to A, nature, in her wisdom, has arranged the dimensions so that one arrives at A after a trip to B, at the same time that one started. Hence, time has flown backwards. And this is true no matter where you measure the progress of time - for any subset of the journey, for the return part, while you are on the 2D segment of the Escher circuit, time flows in the opposite direction, so you can take no advantage of the accumulated energy at all. A new branch of relativistic invariants must be supposed, not special, or general, but adversarial.

Thus Escher Circuits are rare, and exhibit adversarial relativistic time dilution.
Now, it is the case that one can make use of the properties, but only for a rather narrow application, and that is when one needs to use no energy to stand still in the face of a headwind. Of course, the hands of time and the wheels of the bike make the same amount of progress, which is to say, none at all. But you can get plenty of uninterrupted thinking done, which, after all, is the main reason we cycle everywhere in Cambridge anyhow, isn't it?