principles of communications, 2013/2014, end of week #7 to L22

This week, we covered shared media & ad hoc capacity, and started on traffic engineering.

A sharp question on proportional fairness in earlier material prompted me to notice that that isn't well contrasted with max-min fair sharing -- It turns out (as often with technical areas) Wikipedia has a nice explanation - see this article on
proportionally fair w.r.t weighted (max/min) fair queues

Next week will finish traffic engineering and wrap up with summary of course.

principles of communications, 2013/2014, end of week #6 to L19

This week have done scheduling, queue management and switching
and just about to start on shared media

One interesting point historically -the colossus computer at Bletcheley Park built for code breaking was not a von Neumann classical architecture computer but was a "switched programme" machine  - this made it incredibly fast (for a 1940s design) although incredibly inflexible -- and it took a very long time for people to catch up on a standard desktop (about 50 years) - amusingly, about as long as the Dr Who series has run on BBC TV:)

principles of communications, 2013/2014, end of week #5 to L16

This week, control theory and optimization...

Some minor inaccuracies in slides have been corrected in the online copies linked from the course materials page...[or will be as soon as I can get powerpoint with the right fonts:) - the key error is in the calculation of the steady state error of the proportional controller - for some reason, there's a subtraction of the two terms for U(s) where it should be +
(KUs + Rc) / (s(s+K)
I think {need to check this:) it kind of makes sense (if the completion rate increases, the admission rate should increase....)

then when we take the limit of s(U(s), as s->0, we'll get Us + Rc/K
so ess (error in steady state) is Us - (Us + Rc/K) which gives us -Rc/K
(i.e. the answer is right, but the system response wasn't...will check and correct soon...

again, to note, the chapter on control theory in Keshav's book is very clear if you want alternative source + some nice example problems.

principles of communications, 2013/2014, end of week #4 to L13

Error, Flow and Congestion Control done (99.9%)

further reading - maybe - on Network Coding (see Digital Fountains)
and on what's in Linux (CUBIC) and Windows (Compound) for congestion control, and what real traffic actually looks like - see CAIDA
http://www.caida.org/home/

next week: control theory...and optimzation:)

principles of communications, 2013/2014, end of week #3 to L10

This week we covered routing -

there's one egregious error on the slide explaining Dijkstra's algorithm in Link State where the sign on the comparison is the wrong way round (well spotted students!) - I leave it as an exercise for you to find, as it makes for careful reading:-)

In Sparse Mode, we use Rendezvous Points to coordinate a single RPF tree around a designated/configured router (maybe one for each of a different block or subset of multicast addresses) - there's no guarantee the RP is in a sensible place, although the switch from RP centric tree to source based tree after an traffic flows helps reduce latency -  automatic placement of an RP to be in the "centre" of the group would be a solution to the Steiner Tree (Min spanning tree) problem which is NP-Hard, although there are polynomial time approximation algorithms for it (but you probably wouldn't deploy them in routers, but in a network management system for e.g. a gamer or trader network, this might be sensible)

One other note - consistency, symmetry of routes, and so on - IP and IP routing make no guarantees about this at all! BGP (inter-AS routes) are often asymmetric...recent computer science work on building new protocols that provide global consistency during route update and computation does exist, but is still research, largely....although the techniques are promising!

Next week, errors, then flow and congestion control.

principles of communications, 2013/2014, end of week #2, to L7

To note for today- the slide on graphs, with Edge and Node list has a list of all edges, alongside o nthe right list of nodes  - the list of nodes isn't meant to line up with the list on the left - its just a list for node i=1-5, what other nodes, in the directed graph,  are adjacent (look at arrows on edges - note in 2 cases (1<->2 and 5<->4, they are bi-directional)....



fun references today:-
Ghost Maps

Collatz

Kirchoff

Erdos

Small Worlds...

DDOS visualised

Couple more corrigenda/errata
1. in the alpha/beta models of random graphs, there's k used for average degree of the net (e.g. pN in the alpha model), but also used for the toal number of edges (N*(N-1)/2) - so take care with k
2. there's an expression in the slides about max-flow in DAR (the "Sticky Random Routing" for the telephoen net) for using Erlang's call blocking probability for a given link, then work out what the toal capacity will be for 1 hop and 2-hop/tandem routes - this has n, which is number of calls you get through, then mentioned a technique called LP  to solve the maximisation problem given in terms of sum of calls that get through (or are blocked) over all direct and tandem routes- we are'nt covering that technique this year, but LP stands for Linear Programming, and is fairly straightforward if you want to look it up - it is commonly used in optimisation and shows up in Operations research/Logistics (freight etc) and so on all the time.

principles of communications, 2013/2014, end of week #1, to L4

We have now covered Systems, and Layers (lawyers)...

Next week, Graphs, and Routes!

principles of communications, 2013/2014, L1

Today this course starts: principles of communcations

This blog will be where I put errata, answers to questions, and just generally track progress of where we've got to for students and supervisors....

Today [11.10.13] got as far as 1/2 way through Systems lecture - Monday
intend to finish that and go about 1/2 way through Layers material:

slides

Publication Culture in Computing Research Design for impact: Rethinking academic institutions from the ground up

Why do we pretend that a publication is an event, rather than a part of an ongoing
process?
Computer Science is a Soft Subject. We create artificial systems/artefacts, and explore
their behaviours. We then report on this by talking about the behaviours at workshops
and conferences, and writing about the systems in papers for web pages, online
archives or even traditional print journals.
People assume that the artificial dichotomy between social events (workshops,
conferences) and archival repositories (journals and the like) is right. And some of the
debate about CS publication culture is oriented around trying to get people to use
these two modalities  more like other disciplines.
I think this is fundamentally wrong, and flies in the face of real scientific method.
Science does not deliver truth. It delivers things that work, and explanations that are
the best, current, simplest ones (c.f. Popper on Objective Knowledge, and of course
Occam’s Razor).
This means that a work is not the final word. It is just the current word. A goal of this
proposal is to reduce the “slice and dice” culture present today due to various perverse
incentives.
So the notion that an “archival paper” has been thoroughly checked and is infinitely
more “correct” than a “rapidly” reviewed conference submission is not tenable. There
is every chance that during the necessarily longer process to create an archival version
of a work, subsequent work has improved over the results. Hence much archived
material is actually less accurate because it is less timely.
The solution, for me, is to remove the notion of immutable publications, and admit
that we should update work continuously
This can apply to the entire process of socialising our work, hence a dialogue (or
multilogue) between authors, reviewers and readers, continually adds accuracy or
timeliness (or invalidates a work).  The same can apply to citations (which should, by
the way, have a “sign bit” to indicate whether the citation is building on fro ma work,
or citing it as the thing the new work invalidates).
Recognising this mutable publication model, would allow work to be presented at any
point along the “production line”, perhaps merely by “acclaim” - some work has
reached a point where it is mature enough and timely and interesting enough to merit
presentation at a social event (workshop or conference) - this could happen before or
after some notional point when it is recognized that an archival version is the current
best knowledge we have (a rare event).

Along side this continual process, I think one would have to abandon ideas of
anonymity in both authorship of work, and reviews/critiques (viz, the “dialogues”
mentioned above could only work in that open way). It goes without saying that code
and data associated with a systems’ behaviour should also be openly available as part
of this ongoing process (after all, since when did we declare code “bug free”
correctly? Why, therefore do we declare journal papers “correct”?).
Finally, this isn’t exclusive to Computer Science, but we built the tools that would
make the new approach viable, so we should use them first.
In fact we also have the next generation tools for this – we just need to combine Arxiv
with Github (versioning repositories)
1
.
Causes of paper count inflation.
CS is notable (in most branches at least) for submitted to conferences more than
journals. There are two pressures to do this
1. Urgency
2. Promotion
CS is a young disciple, and the young are noted for being impatient and impetuous -
our slogan might even be said to be “Publish Early and Publish Often”
2
.
Urgency
We live in a nanosecond world. More than other disciplines, partly because we built
it.
We supplied the tools and tool chains (the net, e-mail, the web, PDF, bibtex/latex,
databases, HotCRP/EDAS, etc)  that let us cooperate to develop ideas, systems,
results, and write papers faster, and deliver them for review, editing, and presentation
more quickly than any previous generation. Surely, other disciplines use the tools, but
we live and breath them.
As a result, there’s a feedback loop between publication of hot new work, This instant
gratification leads to an increase in the rate of submission.
Our profession has also a tendency (at least anecdotally) to attract a share of people
with OCD/Attention Deficit problems, who maybe (amateur psychologist’s hand
waving here) seek instant rather than deferred gratification.
                                             
1
 Github because we want distributed repositories to avoid re-concentrating power in
one place all over again.
2
 I could speculate here about whether these factors also contribute to the gender
imbalance in Computer Science as a profession and academic career (whether
directly, or simply as proxies for a root cause).


Promotion
Our academic research culture is funded largely by tax payers money (NSF, DARPA,
EU), and the tax payers seek metrics to see their money is well spent, and they seek
such feedback on an annual basis. Paper counts (and to a lesser extent, citation
counts) serve this. The same problem (inflation) has hit the industry research and
development world, where patents are a proxy for real work, and are rewarded.
The amount rather than significance of work is measured - hence, the aforesaid dice
and slice approach to work, producing minimal publishable units, and multiplying the
number of venues and publishable units year on year.
Because CS is young and vigorous, we have in the past been able to keep up with this
inflation. We are close to the limits though.
In the UK, we have a national Research Excellence Framework, for which researchers
in universities do not return all their work. Instead, every 5 years, up to 4 “outputs”
(e.g. papers) are returned. Secondly, and in addition, impact stories (pieces of work
10-20 years old, that have had a long term effect on the world, economically, socially,
or in terms of further developments in a discipline) are employed.
It will be interesting to see the outcome of this process, but for me, it is probably a
better basis for looking at some one person, or groups progress, so if we were to use
these sorts of indicators for tenure or similar, this would remove the aforesaid
perverse inventive to maximise the number of publications.
Acknowledgements
Thanks to Richard Clegg and Ioannis Avramopoulos for comments on this draft.

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!

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

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

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...

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!

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

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

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

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/

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.....

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?

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

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.

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).

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.

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.

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...

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...

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?

Week 7 - to Nov 26 - Got to Traffic Management.

Looks like we won't make it to the
Optimisation Theory and LP material this year -

I will wrap up on Monday 29th Nov
with last part of Traffic Management,
and an overview of what I've covered.

That will be the last lecture for Principles of Communications.

Students that are very keen can read the slide-ware on Optimisation and on LP - I am happy to answer questions on it too.

Students interested in the lower levels of physical/link layer may want to take the Digital SIgnal Processing course by Markus Kuhn next term (see here. Students interested in networking performance (and systems in general) may well want to go to Richard GIbbens' course on Computer Systems Modelling which covers a number of these topics in more theoretical depth. If really keen, please sign up for the new Part III, which will be running next year.

Note that next year, Information theory will be taught separately (again), which may make the amount of theory material in PrincComm slightly more tractable.

week 6 - to Nov 19 - Got to end of Switching

Next week, to cover
Shared Media
Capacity of Multihop net
Traffic Management

Then final week, will ust get to do optimisation and LP hopefully:)

n.b. to supervisors and students:- i've put a couple more links to some online information about
control theory, graph theory and some of the sources have worked problems...
see slides page for course
http://www.cl.cam.ac.uk/teaching/1011/PrincComm/ppt/

Week 5 - Nov 12 - end with Control Theory

Today, noticed that the wikipedia article on this is pretty good, but most especially nice is that it cites an 1868 Royal Society paper from the Royal Society by James Clerk Maxwell, which not only mentions Mr Watt's Steam Engine, but Mr J Thomson's experiments (noting that our building is between JJ Thomson Avenue and James Clerk Maxwell Road:)

Next week, we should cover
Scheduling
Switching
Shared Media Access


[The paper above also mentions a Mr Siemens!]

Week 4 Friday November 5th - Principles of Communications Progress

Today, we'll cover Queueing Theory. So that completes network layer stuff
(graphs, routing, errors, queueing)

Note in the printed (and old online pdf) queuing theory slides, there was a font error on some slides with \rho being rendered as ~n.
I've fixed it on the PDFs online (its ok in the ppt). apologies (again).

Next week we start on Flow Control, and hopefully get up to control theory.

Principles of Communications - End of Week 3

I have just about got to the end of routing
(having fixed, i think, some bugs in the distance vector worked example) -

next week
monday, wrap up multicast/mobile routing
then

error control
queueing
and maybe start flow control

Principles of Communications end of (full) week 2.

Today, I'll finish the graph theory lectures, covering social networks, small world nets, random graphs, alpha/beta and spreading/search.

So we'll have done:
# Introduction1
# Systems
# Layering
# Information Theory
On this topic, John Daugman's notes are great
# Channel Capacity
(not Modulation - this is on hold to end in case we have time)
# Graph Theory
# Social Networks+

On the last topic, this book on Small Worlds by Duncan Watts is a nice read. Another good book on the topic covers more about flows over such networks (information or diseases for example) is
Connected, by Nicholas A. Christakis and James H. Fowler

That means from monday (and most of next week, oct 25,27,29) we're doing Routing.
If things go to schedule, then subsequent week (nov 1,3,5) will be Error Contol, Queueing Theory and Flow Control.

Principles of Communications...end of first week (15.10.2010)

Should just have got up to first slide set on Information Theory (Entropy)
Monday 18th will start on Shannon - by 22.10.10 hope to get to Graph Theory.

Have just updated online slides (1up and 6up should all print ok now, fingers crossed:)

information theory - live example

powerpoint for lecture on information theory+colour printer -> slides without equations:(

powerpoint for lecture on information theory+mono printer -> slides with equations:)

ergo, colour printer driver is an erasure channel with memory and rather non random behaviour and information rate is massively reduced :-(

pushing this as an example for explaining shannon is a bit of a stretch...in the sense that the "physical channel" is the printer and the colour printer should have more capacity in some sense, although I suppose the point is that the "noise" process" is an erasure channel that removes (say) bytes that code yellow but not bits that code white/black...

In schloss dagstuhl again - 99/100 (1 small nit)

I really like dagstuhl - the organisation is wonderful - lots of lovely quietly smart tricks (for example, the librarian puts out copies of all the books by attendees for display and they are invited to sign them!) - the bar (wine) is fantastic (makes up for the so-so food - although the cheese platter is superb !) - the visitors book and other information for wider awareness of what is going on and who is there is excellent - the area is great - even the "interesting" challenge of getting here from the "nearest" airport or railway station is a fun problem

only 1 minor complaint - the website (in almost all ways very very good) has a facility for attendees to upload materials for their seminar/talk/wiki/discussion etc - but the site as a design flaw which makes it very counter intuitive to getting the first thing uploaded (when you navigate to My Documents, you MUST have a title and click on the very small "save all" button to avoid weird apache error messages:)

otherwise 999/100 for the best seminar/retreat/workshop site in Europe by miles

fine snooker room ,very nice music room, great cellar, good walks/hikes, pleasant and efficient (and mostly invisible!) staff....

2 weeks of workshops taking its toll!

I was at IMDEA for this workshop on energy in networks, then at this one at Microsoft on Network Economics, then another one at UKERNA on SuperJANET 6 research requirements planning at the very nice Royal Society Chichelery Hall Kavli center then there's this one at the Isaac Newton Institute on networkmeasurements, and one on new internet architectures and incentives rn by the Eiffel thinktank, then one at Telefonica I+D on a vision for 2020 networking, then this one run by the Trilogy Project on resource pooling

Boy, now I need a vacation:)

here we go again with government interference

without waiting for Lord Brown of Madingley's report, the new government make proncouncements about UK Universities - the BBC is reporting David Willett's saying he needs 700M savings and the coalition's evidence-free arguments that
a) we (the uk universities) are in a financial mess
and
b) that we have to find ways to be cheaper and more flexible.

Well we don't actually. We are quite cheap (which is because we have to serve the UK government) compared to a lot of EU and US universities AND we are evidentially quite flexible and quite good (compred to most EU universities) - the government should check the figures on health and education in the UK and compare them with similar quality systems in the world. We attract a lot of overseas students of very high quality preceisely because we strike both a bargain, and a high standard. We don';t have to serve the UK - we could just turn into private institutions for rich kids from here and overeas. Or we could be rubbish. But we are not inflexible or expensive.

Frankly, I'd held out a bit of hope that this new government would actually base its policy on facts, but it looks like I was hopelessly naive and sentimental.

What a shame

schroeding & turing

Schroeding's Cat is the typical name for a thought experiment about the oddness of the Quantum model of the Universe. It is an artificially constructed scenario where the normally microscopic quantum level effect selects a macroscopic change in the state of the Universe - i.e. the decay of 1 single atom triggers the life or death of a large creature (a cat is presumably on the order of 10^24 molecules) - Life or Death states of the cat are
quite visibly distinguishable to a human observer. Of course a simpler trick would be to have a critical mass of fissile material, less 1 atom, and then just add that 1 atom and then see if it decays or not and does so triggering the chain reaction or not....that would also be quite visible and not very distorted by emotive weird observable things (when is the cat dead? what is life? :-)

Turing's test of intelligence decides the matter based on a human observer's ability to distinguish the responses of a black box to a set of questions (sent over some teletype line to avoid any complex non verbal comms). It can be generalized.

Some confusion arises when thinking about Schroedinger's Cat ("paradox") and observers.
Note that the state of the cat is actually created by an observer (the geiger counter described in the wiki article above is the thing that detects the decaying atom, and triggers the hammer to break the flask of cyanide that kils the cat (probably). The uncertainty is purely about when the decay happens. An observer of the dead cat is a secondary thing - we can assume fairly certainly the cyanide kills the cat (all nine lives) so in fact all we need is a red light on the box that says the geiger counter detected the atom decaying. The confusion arises because two words are misused from natural language:

observer

description

The observer does not have to be intelligent.
The description is not obvservable.

Hence we can't use this to talk about consciousness, and there is no paradox (descriptions of intermediate unobservable states are figments of maths - only if actually observable are they interesting (e.g. remote entaglement).

The point of mentioning the turing test is that Schroedinger also conflates two things:

simple observation (detect decay from emitted particle

complex observation (is the cat alive).

Is detecting life, perhaps a nice turing test?

remarkable engineers

this is a fun read if you like these sort of mini-bio things :-
Remarkable Engineers follows similar excellent books on maths&science. But it is an interesting book for its lack of people that I would regard as engineers from Ancient Greece, Arabia, and China - however, within its well-defined model of what an engineer is, it is interesting (seems like you not only have to build something, you have to patent and sell it, and preferably be Scottish:)

1 mole of stars. Avagadro, state and human perception of scale

so reading
The Eerie Silence by Paul Davies,
he points out that there are estimated to be around 10^23 starts in the universe around now....this is an interesting number (like all numbers) which is around Avagadro's number which is the number of atoms in 12 grams of carbon 12
or roughly 24 liters of air at STP.

one amusing number to play with is the number of molecules in a glass of water, which is MUCH more than the number of glasses of water in all the oceans of the Earth.

So the number of stars is in between.

maybe, they are the same thing.

Conferences, Journals & unrealistic levels of Academic labour taken for granted

I was talking to some PhD students here recently about the relative merits of submitting their work to Conferences or Journals - a typical chapter of a thesis makes a nice paper

before you write the dissertation, it is nice to have it published in paper form, but to get the process done and dusted before the PhD examination comes along, you almost certainly have to send it to a conference rather than a journal because of the turnaround times - its 6 months from submission to presentation for typical top-league conferences, and more like 2 years for the equivalent conferences in Computer Science.

Reason for publications: confidence boosting (for student AND for examiners:)
and feedback is useful to improve work even if it doesn't get in...

Plan B (if things work out) is to submit a 9-12 page version to a top conference, get your PhD and submit the 12-20 page version to a journal after....reason for submission: archival version (maybe) and certain academic communities' career paths still value journal higher than conference (mostly, though, citation is lower...)

Some points to consider though
1. academics or industry research lab workers do all the work for conference and journals (run submission sites, do reviewing, do editorial work, do selection, do a large part of conference organisation etc etc)
2. a typical top class journal or conference paper represents about 1MY effort - typically if you include all the effort by a PhD student for a year, plus their advisor and any co-authors - in systems, it can be as much as 2-3 people's work
3. a typical conference reviewer might look at 20 papers in 30 days - so if they are really really insanely fast at reading, and on top of all the latest material (and not handing it out to their poorly as yet calibrated own students to review, or at least only doin this to help their students get calibrated or give them up-to-date feedback, but still doing the review themselves) if you are lucky, your paper gets 4 hours work on it at a conference
4. a journal submission might get a rainy Sunday first submission, and then several hours more over revisions, so you get a lot more detailed care and feeding in the process.
5. In my experience, examining a PhD takes 3 days work - if you consider the naive equation, that 1 dissertation is == 3 good papers, then this is about twice the level of attention a paper gets (at best)
6. Finally, a lot of researchers use long journeys to read a lot of papers (transoceanic flights are good) - this appears to have stalled for the last few days around this part of the world - I wonder what impact this will have on conference review quality?
On the other hand, maybe the mortorium on flying will reduce the number of weak or nearly pointless workshops ...who knows...

two mixed reality dystopias.

1. Gravity 3.0 didn't turn out to be such a good idea, did it Professor Sheckley - I mean superficially, the notion of an inverse cube law force so that people on smaller planets, but nearby, get a strong attraction and don't drift off into space, looks OK - but then look at the terminal velocity - not good for the robot ships landing delivering out food....gasp gasp
Of course, it wasn't such a terrible mistake when you compare with Gravity 2.0, the result of the Campaign for Real Gravity - attaching everyone to the surface of an apparently zero mass planet, by colored elastic looked cool - but we didn't reckon with people customizing their g-strings, to have different h-indexes - Hookes' law is amusing, but then when they started playing paddle-ball with the alien, and we had to tell them to turn down the space-trance remixes of Phil Collins and eventually called in the Cruel and Unusual Ludic Police, it took a turn for the worse.

2. The entropic viral pandemic of 2012 has run its race, and now we cannot rely on the value of bits to be discrete any longer. Unfortunately, it was detected too late to do anything about backups, and so we cannot state the meaning of any program or data with any certainty any more. Such diseases of meaning were unanticipated in the early days of the semantic web, so that elementary precautions, like repeated recall and re-enforcement of what we were saving
were not taken. Now we have to rely on humans to memorize entire sections of the Internet, including music, live performance of movies, and physical versions of VR games.

The cause of the emergent entropic virus will never truly be known (just like every other piece of what use to pass for online human knowledge) but it is suspected that it was the mean temperature of the time series of arrivals of Youtube videos, exceed Centigrade 451, the point at which binary systems move to a higher, ternary state.

Cooling the system down will do no good now. It would be like telling Schroedinger to open the box and finding one and a half cats, one half dead and the other half alive.

This has been a Horizon special

progress bars and stress

so i just have had the 3rd experience of the week when I want to carry out a routine task on some Win* box and it decides it needs to run a massive update and
to make matters worse, this locks out other activities
but the straw that broke this camel's back is the
progress bar

the example of the service pack update for vista will suffice to show what a load of stress this causes - the bar is in %age complete - but there are 3 seperate phases and you are given no indication of their relative longevities nor does the bar actually
move linearly w.r.t time in any fashion (not even relativistic) so if you go away for what ought to be enough time (e.g. cup of tea or watch a movie) you come back and inevitably either something finishes 10 times earlier, so you now have to go to the next step, or else it still has a full 3-day test match (cricket) to go ....

this is like being in a travel warzone when the train/plane is late and the announcements are intermittent and noisy (or in a language you don't speak)...

The Law in 1995

I found this proposal I wrote in 1995 for a programming language for a sort of active web called The LAW - A Language for Agents in the Web

It kind of presages stuff like map/reduce and declarative networks, n'est ce pas?

I am a gadget, you are a widget, they fidget, bridget - Its the Long Gadget, Gromit

Jaron Lanier's fine new book,
You are not a Gadget has a lot of things to say that I agree with.

Turning it up to 11, there's a nice chapter suggesting some new models, which might very much fit the Horizon Digital Economy project - there are three notions, which I have re-branded as follows:-

1. songlets - his idea is more Ubicomp than mine - basically, create a
"songle" - this is a physical key to a right to play a song - could be an Rfid, or a Barcode on a can of coke - it creates an "artificial scarcity" for songs so that instead of people trading them for free on filesharing nets, people trade them for
micropayments (possibly bundled with other things)...its a nice idea
2. giglets - telegigging is the idea of inviting a live band to your party over the net - giglets would be my old version, which is that all live gigs should be webcast and recorded (a la bbc iplayer, NOT a la youtube) with low cost DRM - possibly using a model where its pay per view up to some deadline, and then switches to free if not moving out of the long tail, but staying pay per view for longer if it gets popular and moves up the zipfian...
3. marklets - these are instruments (in the trader sense) which can be formally checked for sanity against a policy + safety rule-base - this is a good idea and resembles some of the things George Soros- wrote in his fine work on the Crash of 2008 and What it Means - he put in some meta-rules (some are basically stability conditions in feedback systems with many actuators - some are what a Programming Languages person would recognize as reflection - all nicely and intuitively explained).


Things I disagree with:-

1. music and midi

- kids share music - they don't share midi, but they do share
recordings, Youtube videos, tab and formal classical notation
so that they can learn stuff - kids I see doing this
do play amazingly better than kids when I was their age - they
don't know they aren't supposed to be that good yet, so they just do it

The real problem is that any abstract representation of music (i.e. notation) degrades it - classical notation, tab etc

using printed symbols for notes is (to reuse an Elvis Costello phrase) like
dancing about architecture

kids i know (in the 12-18 current cohort) share the recordings of the results
not midi - maybe its coz uk is guitar-live oriented, or maybe i am ignorant of dance culture (well, 20 years out of date on it)

midi is so 70s/80s/ synth/drum machine - agreed - but that's only a trap
someone who is synth/keyboard/tech obsessed would fall into


2. code and inflexibility -
i) I was amazed not to see Larry Lessig cited...
ii) I don't see files as lock-in - that is like saying
bits are lock-in - files are just ways to frame a set of data - you can have sets of sets , etc - just like bits. there's a load of theory why this is general....

this is a granularity/sampling error, which i think is a mistake as a metaphor for a cognitive framing error - the notion of Unix files as a problem is much less weak, but still not as good an example as midi, even if I believe midi is a red herring...

3. on music
Doh, how dumb, the internet
Ray, a blade of golden sun
me, an apple trademark bet
far, site, neat place to keep one
sew, a cpu scheduling threads
la, a loony tune land of cgi fun
t, a pipe with 3 ends
and that brings us recursively back, doh

good, bad or midi?

4. singularity (c.f. Singularity Sky, Accelerando etc) and
techno-totalitarianism (none so bad as Extropian!)

The idea goes back a long way - Indian and pretty much
every other early myths have avatars and nirvana,
although, perhaps less blue and with less grunge...
to sublime, to get to cloud nine, to reach Twoness (oops, sorry, Woody Allen:)
or oneness - read Lord of Light....

5. upload and the Turing test - yes, its reductionist - Turing
wanted something akin to what Shannon had for information theory of a channel - so
he constrained the situation - of course it then lacks context, state, emotion, society etc - yes its sad.


6. Some more thoughts on this as I read about his critique of the impact of the "free to air, paid by advertising" business model - he uses examples from
journalism and music and berates the long tail argument


However, the death of journalism long pre-dates the Internet, although it is a technocentric death - the centralisation of press by barons such as Murdoch (and before, Maxwell - c.f. Wapping etc etc) destroyed most of the community of local newspapers and full time journalists who gave detail and colour - this is well documented - the book "Flat Earth News" shows the fraction of news that is actually written anew and analytically by journalists and the vast majority that is simply a verbatim reproduction of press releases. The complaints by media that Google gets revenue from avertisers simply for "indexing" this stuff is rediculous, since the majority of the material isn't even copyrightable by the so-called "publishers" in the first place - it is effectively plagiarised anyhow. (often literally without citing the original "source").

secondly, the music business has concentrated for 20 years on back catalog - this is why it has seen a demise faster than film - the problem is that this is the exact OPPOSITE of the long tail - the claim that A&R men invest a significant fraction of profit in finding new talent is pathetic - it is about as pathetic as most drugs company claims that they spend a large fraction of their profits on new drug development - they don't - they spend more on advertising. One obvious consequence of this is that kids are overwealmed with the quantitiy of high quality material they can see - if you are setting out to learn to play (remember first 3 issues of the first and greatest punk fanzine, Sniffin Glue covers: "here's a chord". "here's another chord". "here's a third chord - now go form a band") - this is just not going to occur in the retro world....on the other and, myspace is full of some cool crazy dudes - i would comapre the clunky wonderful amateurism of, say, sulek, with the madness that is harmelodic metal tapping, sweeping and shredding of Buckethead...

The Internet is a corrective to these poor trends - that doesn't mean it is a perfect replacement, but it sure is better than the alternative.

I love the idea that language might have started as swearing about smells - that is really cool.


otherwise 11/9:)

research is wasteful

reading about the government's reaction to the recession (well at least in its own (our) coffers), we can see that it is highly likely they will cut funding to research over the next year(s).

there are two ways to do this - both wrong - one is to spread the reduced funding thinner, the other is to concentrate funding in fewer (elite) places (actualyl 50% of the money goes to the top 5 institutes anyhow).

But what they should do is spend more. Research is wasteful, very very much like evolution - but necessity is the mother of invention and (just like in evolutonary systems) the impact of a big recession might make people more creative - more creativity does lead to more potential outputs, but it also leads to LESS predictability - we don't know what will fit the future landscape (i.e. what is "selected" as most fit, is not something you can do a priori, but a posteriori, only).

No doubt they will get this wrong, which is sad, as doubling the UK's governemt research funding would still leave it at under 2% of the bank bailout last year, and would be likely to yield more profit by about an order of magnitude.

Unfortunately, we are not ruled by people that have a clue.

clown computing

its so much more fun, and easier to market than the cloud

send in the clowns

i've looked at clowns from both sides now

clown atlas, using the Grimaldi internet coordination system based on
empirical data from Big Foot

CRU/Dr Phil Jones are a bigger pain than maybe they realize

I' reasonably well trained in natural sciences and computing. So I usually trust scientists to do their job as well as they can. In medicine, there's a whole bunch of due process before they loose a new procedure or drug on the world, and even if the big Pharma might be a bit dodgy (and most are fine), the process stops rediculous things happening too often (unless politicians get in the loop).

WHen I or a close family member or friend get ill, I do read the literature (the tech. literature, not just online freebie dodgy internet health sites) to figure out what is what - when i spent a week in hospital with metal in my leg, a couple of years after my father died in a hospital from an MRSA infection, I read all the latest papers on that - I didn't find it too hard to catch up and it mattered to me - but I assume, most of the time , that the latest practice is ok....so I don't have to read the 1 paper published per scientist per month in the world (it.d make me, on average, the 2nd reader only on average).

This is true in most areas where there's a large scale deployment of some piece of engineering (planes, trains, automobiles) too.

So even though I could get my head around a lot of the work, I assume I don't have to.

So the consensus on climate change has been fairly overwealmingly behind the anthropgenic global warming explanation, leading to many government initiatives and international schemes to try to get people, society, industry, nations etc to reduce carbon emmissions. Seemed ok to me - the bit I like was the sane stuff which looks at being, simply, more sustainable, anyhow, as that seems like a good way to conduct oneself - not having had a car for 45 years and having got 3 kids to/thru school on bikes- having an efficient house, etc - I feel ok - then I feel like I should carbon offset my flights (I used to do more, but I still, as an academic, go all over the place for project meetings, conferences, PC meetings etc etc etc)....

so now, because of the CRU fiasco (not their fault the email was leaked, but it is there fault the data isn't avaialble and in good clean shape) I now have to read through the mountains of literature on this topic to try to figure out what is sane and what isn't.

You know what is scary? In the 21st century, there is absolutely no way to tell what is authoritative .

I know what/who is serious in my own area. In biomedical area, I can usually guess to some extent. But in this area, it is completely impossible to determine

so not only do I have to read the literature, it looks like I might need to go out, and audit where the data comes from, then get ahold of some of the data, and then do my own analysis.

that is rediculous, but without doing it, I really don't see a way to have any confidence in the statements by AGW proponents, or by climate skeptics.
I am sure most of them are genunine. But none of them has a clue how to instill a sense of public understanding of why we should listen

this does not make me a climate skeptic (not at all) - it just means that for the first time, I'm looking at an entire body of so-called knowledge, and while I can grok the concepts, until I can grep the raw data files, I am basically saying that this is a complete crock!

mandy cuts his knows to spite his feys

1.
Mandelson said: "We know that universities have a vital contribution to our economic growth, so we are not going to undermine them. We are asking for savings of less than 5% and we expect universities to make these in a way that minimises the impact on teaching and students. I am confident they will."

2.
Mandelson said: "I am an arts graduate myself. We don't dictate to universities which courses they put on. They tailor courses to meet demand. We want universities to play to their strengths, but we also want to keep this country civilised."

since the universities contribute net profit to the UK, cutting them decreases the UKs GDP. so cutting them ANY percent will have an impact both on students and on everyone else.

of course, being an Arts graduate, Mandelson is probably not numerate to understand this.

doh

4 colour map problem solved....

...automatically -
turns out just to be a
bunch of
corner cases

:-)

now on to fermat's.................................................................................

Big Scary Software - python runtime, filesystems, etc

Mort (now at Nottingham) pointed us at some educational videos in the last couple of days

1.The Giant Interpreter Loop that python runtime uses is not really something that admits of concurrency, but also has a lot of weirdnes about it...
(sorry - as per comment - GIL = Global Interpreter Lock, not Giant Incense Lamp)

2. Making sure things really are written to stable storage or disk, as we used to call it, is really not quite as simple (or obvious) as you might think

3. not even on windows

I guess these should be like public health warnings, a bit like the German and French governments recent IE warnings

cloud computing is so noughties

now we are in the pre-teen era of the 21st century,
we should concentrate on Blue Sky research...

no more sensor nets (wastes batteries - very unsistainably)

no more MANETs (dont work)

no more opportunistic or p2p networks (capitalism is so much better than anarchy)

no more economics + computing (computing is dismal enough without addign an entire dismal other "science" to it)

no more green computing (the answer is 1 bit - turn it off:)

Digital Communications II Progress by 27.11.2009

QoS, Int-serv, Diff-serv, RSVP, and Traffic Engineering.
Last lecture, monday, 30 nov. wrapup.

trying to understand the world of 2009

just went through what I read in trying to get a handle on just what is going on in 2009 - see
my 2009 reading list - note this is not compelte - i've only listed things I liked:)

Friday, November 13, 2009 Digital Communications II Progress by 20.11.2009

Switching & Sharing done now

next week - intserv, diffser, traffic

Digital Communications II Progress by 13.11.200

Friday 13th - we havn't got quite as far as I thought - so we've done Scheduling (and Queue Management), and made a start on Switching.

Next week, must finish switching AND do contention networks.

Digital Communications II Progress by 6.11.2009

This week, should have finished
error control (sequence numbers, retransmit/rtt timer estimation)
and
flow control (at least intro to open&closed loop)

as with last week (routing)
these topics come up in exam questions frequently.

Digital Communications II Progress by 1.11.2009

This week I'm doing routing - I've updated the material so please check the new version of slides - DAR + DV/LS is a bit tidier (I hope) but if you spot errata, let me know!

lots of stuff for supervisions and exam questions now.

Digital Communications II Progress by 23.10.2009

We have now covered the material in Section Two of the course

Part 2 - Philosphy/Design

Systems, lecture 5
Layering, lecture 6
Implementation, lecture 7
Alphabet Soup, lecture 8

So I talked about user land and kernel implementations, concurrency and OS problems, and finally about what IP and TCP (and ICMP packets look like

A very nice reference for this last bit is W RIch Steven's fine books
TCP/IP Illustrated volumes 1 (operations of protocols) and 2 (walkthru of code!)

Digital Communications II Progress by 16.10.2009

By the end of this week, I will have covered the historical review of
telephone nets (circuit switched, voice networks), basic Internet technology (packet switched, datagram networks) reminders, and the comparison with B-ISDN and Asynchronous Transfer Mode (Cell Switched, virtual circuit) Networks.

From Monday 19th, til end of next week, I'll be covering
systems design in general, layered protocol designs, specifically, a quick
overview of different implementation strategies, and then a very quick tour through the immensely thick alphabet soup of protocols - all of Part II (hopefully!) on
http://www.cl.cam.ac.uk/teaching/0910/DigiCommII/slides/index.html

google wave

bbc article about google wave says "how e-mail would look if it were invented today" - actually it looks how Lotus Notes looked about 20 years ago.

what a lot of people using cr**ppy internet email today don't realize is that early systems for collaboration (Notes, but even Microsoft Exchange) started from a model of sharing documents and sharing editing of documents, and included facilities for managing groups, instant comment/annotation, privacy controls, and multimedia, and predate most of the internet wave of stuff - its amusing that google can rely on the lack of colective memory of the past, and claim they are inventing the future, when really all they've done is re-package an old old old idea (vanevar bush, rip, c.f.)

indeed, the backend for early systems like notes was a database, which meant search/index was optimised already so its even closer to google than you think...

foundational computer science research "at risk"

we had a visit from the EPSRC's ICT team last week - for those people who don't know, ICT is Information and Communications Technology, wherein CS (including theory and systems and HCI and all the rest) is lumped alongside radio and optical and other low level engineering things, and is a term favoured by eurocrats who don't see why silos are bad, and incorrectly labelled silos are even worse.

Anyhow during the conversation between computer lab academics and EPSRC it was fairly clear that they didn't think it was important that the top ranked computer science department in the UK (and equal top ranked deparment in cambridge, the top ranked university in europe) currently had no EPSRC (i.e. UK government basic research) funding for its theory faculty.

Someone in the EPSRC is either asleep at the wheel, or else they have become slaves to the blairite mantras of industrial relevance. what they don't seem to get is that if the EPSRC only funds short term "industrial relevant" work, why would we need the EPSRC? we could go to the EU.

What is depressing about their taking the moral low-ground like this is that we wil lstart to go to the European Research Council (ERC) to get money first (i.e. the better places will try that) and this wil lstart a vicious cycle of driving EPSRC funded projects ever more short term, making my projection ever more likely...

the rot must be stopped...

new job title for programmers..

I think we should call them
software artistes
and systems analysts could become
computational magicians

patents, monopolies and innovation

I'm just reading Heroes of Invention: Technology, Liberalism and British Identity, 1750-1914, by Christine McLeod (CUP), and was thinking about
why we have patents and market failureshttp://www.cipil.law.cam.ac.uk/

[aside: this was because I attended an excellent workshiop run by the
Centre for Intellectual Property and Information Lawin Cambridge earlier in the week, where we were discussing the nature of the invetor, the invention and the inventive step. ]

The market is supposed to deliver the best for consumer and producer (Adam Smith etc)
but it requires efficient (information rich) competition, Market failures are usually indicated by monopoly behaviour (price hiking) which can include cartels.
Markets are claimed to be good for social welfare...
Innovation is supposed to be protected by patents, and a large patent count is supposed to indicate innovation is happening.
Innovation is supposed to be good for social welfare..

What is happening these days (and was happening in the 1600-1700 period) was a lot of patents and a lot of monopolies or near monopolies. In the 17th century, this was regarded very badly and parliament put big changes in place....now, what is happening is big companies are smarter - by analogy with high functioning autistics, who can emulate empathy by running a purely cognitive model of how they should feel, rather than actually feeling it, large companies run a "model" of how a competing company in a market should behave (as close to the line as they can get away with, occasionally overstepping it) - the idea is exemplified by Cisco, whose CEO has allegedly said that they always want to own the middle 50% of the market - i.e. neither be an innovator, nor truly work in the purely marginal business (bottom feeding?) of cheap and cheerful devices - similar observations could probably be made of microsoft and intel - they
tolerate the existence of low end and very high end, but only when its a small part of the market -
they use this to price as high as possible without appearing to have market failure.

they engage in generating as many patents as possible, as close to the line of
obviousness or inaaplicability as can be allowed, to give the appearance of being innovative without the reality.

this also puts a chill on innovation.

innovation often happens in computing related areas in government sponsored labs (same is often true in bio-medical in fact) and then is "absorbed" magically into these large organisations....typically by hiring of PhDs -

what universities should do is charge a LARGE finders fee for PhDs placed in companies.
what patent offices should do is have a revocation on patents that are not exploited with a VERY large revocation fee. the revocation interval should be set according to aggressive norms of the sector. revoked patents are put in the public domain.

Where do you want your Go To to go to, today, sir?

maybe, we should ask what happened to the "Come From" idea? is this google?

why is #storm >> #planetlab

so if I wanted to develop an internet scale ap, why wouldn't I buy time on storm instead of Amazon EC2 or planetlab? eh? eh?

cloud atlas....an idea for future privacy architecture work

two areas (not unrelated) people want to do better security (both privacy and access control) are
1. social networks
2. cloud computing

I'm going to ignore the (hard) problem of traffic analysis and full on pseudanonymity for this blog for now...

since social nets run (mainly) in the clode, lets see if we can use 1 hammer for both rusty nails:

traditionally, we'd like to have a full subject/object matrix of capabilities - in general, for cntrolling who can see/use/alter what, for n objects, with k attributes and z access styles, we could end up with z*k*n^2 entries.
This doesn't scale for computers, and it doesn't scale for people.

In reality, many systems reduce the problem by two means
a) hierarchy (or multiple hierarchies with domain specific roots) reducing the space to k*z*ln(n) - think unix file systems and r/w/x
b) groups. n.b. with enough groups, you can do the entire s/o matrix of course, but that kind of defeats the purpose (which is simplification by aggregation)....think unix file systems and sudo and r/w/x for u/g/o, and then add newgrp etc etc

People do this sort of thing manually in their online existence by having multiple social net accounts and managing their friend lists differently on each one.

The problem (something Boris Dragovic did his phd on here a few years back) is that a hierarchy doesn't always capture what you want, but an ad hoc collection of exceptions
breaks things and makes things hard to remember for poor old humans again

so lets introduce two new things
1. Dunbar's work on social groups and layers of trust
2. games and BAR-T

In 1, we have a way to express trust relations which auto-magically gives us groups - the layers of trust in a social network are known to decrease as you move out from kinship, through friendship, through colelagues, then acquaintences. But, its dynamic, jim, and not necessarily, dynamic as we know it....
In 2, we have behaviours that are trustworthy (altruism, rational, byzantine) and measureabl, and can be attested to by witnesses....

SO we can build a system that creates defaults and learns and relearns the right settings in the (number of) hierarchy(s), and number of groups and access rights for each layer of the onion, both socially and technically.

We can also incorporate downgrading (or your reputation,creditworthiness, or access rights) forgetting (or un-friending) in the same architecure -

activity keeps friendships alive and rational or altruistic acivity keeps a cloud access right alive at some level.

Now we need a data structure that is an efficient representation of a tree but within a sparse representation of a (easy to update) matrix...that should be easy...

s/w update process heading for 100% duty cycles

so every time I go away for more than 1 day, i live in fear of coming home or back to my office -no, its not the mountain of email (or spam) - I have the tools for that

its the s/w update on windows, linux, mac (and ditto smart phones) that is queued up waiting to install (and ask me to agree to terms I already agreed to 11 zillion times before for iTunes or Mac Office or foobarbaz antivirus)...

but also it's how **** slow the whole system goes (and there are lots of systems) and how unresponsive it is till all the stuff is done and dusted.....note this is not an anttimicrosoft rant - its just as bad on a Mac and not much better on linux boxen...

there really ought to be a better way (pre-click EULAs and then trickle the updates in is ok, but its not very green or even safe as I have to leave a zillion boxes on in my house - there should be a "sort merge " on the update (I know service packs do this, but perhaps not in enough permutations)...

Post docs in Cambridge - could be a whole lotta fun

Horizon Project at Cambridge Computer lab is lookin for 2 researchers (fairly experienced/senior) - it's 5 year
mission, to boldly explore new pervasive computing universes and make them commercially relevant...


http://www.admin.cam.ac.uk/offices/hr/jobs/vacancies.cgi?job=5622
http://www.admin.cam.ac.uk/offices/hr/jobs/vacancies.cgi?job=5623

this could be a lot of fun...please pass it along!

cheers
jon

android g2 phone....

..we got some for a project (on mobile social nets..) and they are jolly nice (this is the HTC hero) - very very close functionally to the iPhone, plus a lot of cool apps (Doom, can you believe:) - and all this on an open platform....neat...with wifi and GPS on it lasts about most a working day, but with 3G on, wifi and GPS off, about 2 days....with just voice, about 3...so not too bad...nice camera...

wireless on planes

--------
yesterday we flew back from Crete to London on a nice A320 run by
Monarch Airlines - very pleasant - after the usual safety announcements
about turnign off all wireless (which actually listed wireless
laptops, games, GSM, 3G, SMS and so on), we took off, quickly reached
cruising altitude and then a whole bunch of different kids started
playing on their Nintendo DSs - there's this cute ad hoc wireless
conferencing app that they all started using, and slowly, abut 30 kids
discovered each other and a game evolved which was very like
Nottingham University's "can you see me now", with kids waving arm in
the air and other kids had to tag a person on screen before a hand
went down....very cute

and of cours, entirely based on wireless ethernet......
the game ewnt on most the 3.30 flight and noone from the
flight attendants said a word....

ignorance and creativity...

so cute:)

and prima facie evidence that a WHOLEr LOT Of wifi traffic has abslutely zero impact on the safe flying of a fly-by-wire moden plane.

software engineering is really about programming avoidance

just reading the very amusing "Head First Design Patterns" book by Freeman&Freeman (freemen) _ basically, as far as I can tell, all of software engienening is about deferred gratification, or in other words, putting off the real work as long as possible - i.e. avoiding programming if it costs you the earth...

this means that by definition we should never ever ever teach Software Engineeing
becuase no-one learning it would ever do any programming, and so they'd never know why you need software engineering (doh)

maybe we need a new OO paradigm called Manana - the ultimate in late binding...

meanwhile, I am trying out this excellent book on python programming on an 11 year old kid in my house - he's on chapter 3 in 1 day...awesome!

epidemics....how the swine flu should roll out, and back again

so the beeb reports 100,000 people have h1n1, mainly in under 14s.

Schools finished last friday, i.e. 6 days ago, and in the younger age group, people are infections for 2 days more (7 days), and shed virus thru skin (i.e. touching) - assume most these kids are in families of 4 on average, one would expect all those in the family to be infected during this period too (but not necessarily displaying symptoms just yet), which means an underestimate by *4 - i.e. 400,000. assume most these people are infected last weekend (when kids came home from school and socialised most) and then went to work as normal monday - they would infect (but with lower probability) a fraction of the people they socialise with (on average a person's social group is 150 - this is in physical world, people in family, friends and colleagues) - say per day they infect 1% - i.e 1 person - by end of the week (tomorrow) you'd expect to see the number grow * 7 - ie. 2.8M. This weekend, the rest of the family (except the, curiously, and luckily, mainly immune grannies and grandpas) get it and nex week, those 2.8M infect around 7* more, i.e. 21M

so I'd predict the epidemic peaks with 1/2 the population infected by mid august, but then as everyone who's had i is now immune (we hope) form re-infection, the faction still infectious is decreasing, and the faction not yet infected is decreasing, so the rate should fall fairly fast til september...

that's my 2 cents.

oh, background - i'm using handwavy approcximation to the SIR model (good for pandemics over large numbers) - see
wikipedia entry for SIR for more details

dI = [ beta * I * S ] - [R * I]
dt

where beta is contact rate (we meet that many people a day)
I is number infected so far
and S is susecptability
and R is recover rate

so in discrete terms, with a 1 day step
taking beta as 4 and S as 1/3
and R 1/4 (recovery time as 7 days)
I grows at nearly doubling per day until we hit about 1/2... as per above
and this then starts to fall....

3 startup ideas and one visual metaphor

1. using contact graphs (as per haggle project) do a
realorgchart.org
startup - basically find out what true
hubs and clique, and flow of info between them is
and comapre to company's "pretend" org chart:)

2. pedagogoc virtual machines (aka tinyxen) - so we need to teach people about
multicore and h/w support for virtualising (core/thread, memory, I/O) and OS tasks that use this - so we need a small (like linux was origianly, or xen was or minix or xinu)
system (both a multicore arm and a multucore VM) to teach people from - sort of the henessy&patterson h/w: s/w interface book, but most of that concentrates on what the interface between programming lanagauges (stack/procedure call) and h/w - now we need it for microkernels and OSs etc

3. a business model process for managing the Techncail Intercept window - this is the time that it is best to try spinning an idea out - we were discussing internet food shoping yesterday and remembered a US failed startup a few years back that tried to do an Ocado - just a few years before there were enough broadband accustomed customers to make it make sense...so how tdo you find the ideal window?
(say from inception to boringiness is 20 years and there's roughly a 5 year gap in that 20 years when there might be a 1 ear opportunity to get things first, but not too soon.....optimise!)

FInally, it'd be neat to have a "bad idea crime scene investigations" toolkit - we could carry away the broken ideas in body bags, leaving a chalk outline on the lab floor and pieces of string where the bullets flew....

greening the internet/computing

is a bit naive - take a look at
gavin schmidt's rather more holistic and complex view of the type of things we need to consider about models and the future in general

Recent CL proposal successes

so we've been sucessful in two EPSRC proposals - one is we are part of the Nottingham run hub in gdigital economy called Horizon - this is mostly about new business models (e.g. advertising) in pervasive computing - the other is an ordinary project in secure by design federating of sensor nets, called Fresnel, collaborating with folks in Oxford (OII and Computing) - each entails 2 post docs and soem PhDs - adverts will appear shortly on the CL normal vacancies page

better than zero-copy stacks

conundrum - can you do better than a zero-copy stack?

far as i recall, some folks at Sun Microsystems did the first unix with zero copy
from user space to/from network device way way back (prob. 92?) so that was as good as it gets in some sense....or is it? can you get a packet from the net in less than no time? I think you can in the sense that you could wake up the application before all the packet had finished dma-ing (or for a non blocking read/write application, you could do the copy on write thing 1 bit ahead rather than the whole packet) - of course, you'd need some insanely fine grain lock on the packet buffer somehow (or some fine grain virtual memory hack) which will be Rather Expensive(TM) in Real Life...

quantum networking...

I just got back from madrid where we had a nice dinner in Real Madrid's home stadium restuarant. the event was IMDEA's seminar n qunatum networking and had some seriously interesting talks from

Chip Elliott, BBN Technologies, USA
has a real operational QKD net in Cambridge Mass

Matthieu Legr?, id Quantique, Switzerland
works for a company that sell working QKD kit

Michele Mosca, Inst. of Quantum Computing, Canada
runs this institute in Waterloo which does the whole thing (incl QC algorithmics)

Emina Soljanin, Bell Labs, USA
very clear theorist with clean models of things like quantum multicast

Paolo Villoresi, Univ. of Padova, Italy
QKD over satellite and other free space (i.e. non photonic/fiber) based channels!

i had 4 bad ideas during the meeting
1. have a classical resource model of qunatum resources for the classically challenged
2. QKD satellelites could provide eye in the sky secure control plane
3. QZKP and other interesting zero knowledge or shared secret stuff, homomrphic hashes, quantum watermarks)
4. what's the Qbit rate for a multihop free space qunatum channel?

my proposal is to get the physicists to do this under some bogo-banner (e.g. Quntum Grid)

isps complaints about content companies

so here's th thing
BT, (for example) complain that the bbc's iplayer (for example) causes too much traffic.
well, huhn - now I susbscribe to the internet at a given data rate because that is what is advertised - note this is a _download_ rate - I am already getting a massively erduced uplink speed to prevent me messign up the net as a small customer, and that is fine (and partly due to technology and physics limitations of ADSL on copper).

but when they sold me a service, they should have thought "oh, maybe he'll actually use it" - note I have a solid 8Mbps...

and when the BBC connect a large scale data center to the net (at some large scale price)
maybe the service provider should think "hmm, wonder why they're doing that" and think about who they are (oh, the bbc - maybe they want to let people download programmes later)

so when they service provider complains about the content provider "causing too much traffic", recall AT& complaining about google "causing load" and wanting a slice of the action

whaty is really going on is that company A failed to realise company B was going to be a success, and is now upset it didn't and is trying to remove neutrality as a threat (stick) to get a part of company B's profit. Nevermind that there was nothing whatsoever except lack of imagination stopping company A being in the business company B provided (oh, ok, so in BT's case, there was a long running rule about being a TV company....however this didn't stop them making money out of selling capacity to TV broadcast companies, and now, thanks to Ofcomm, is going away anyhow).

No, sorry, this is getting silly - nonetheleast because they "blame" is the wrong direction - blaming the BBC because the BBC's customers use BT's customers to use BT's network is surreal. You sell some folks a network, (and get a monthly fee, AND a lot of them upgrade as fast as they can pay more to get the upgrade) then complain when they use the network. Doh. what business did you want to be in then, is it?

(BT is a bad example, I admit due to the old no-TV rule) - so add your own.

Now look at Virgin's new "all you can eat" music subscription service proposal , and big stick if you do anything bad (they disconnect you) - this sounds like dubious practice to me...

a week in cambridge

this week has been bonkers - we had a great talk on monday by Fabio Bustamante about his use of crowdsourcing in bittorrent clients to measure the internet
then we had this stochastic nets workshop which Richard Gibbens organised which was fantastic, with loads of great talks on resource pooling, P2P systems and so on, then we had this workshop on pricing an auctions which Peter Key organised with some great talks on mechanism design and social networks, and now we have this biowire 2009 workshop which has some superb talks on the natural world and its "network" algorithms, and there was a really great semianr by Andrew Birrell on the history of concurrency!

enough for a whole year

Wrong Blog

You have reached the wrong blog. please go back and try again.

helping tourists from america

cambridge is famous for science, but that might put off some tourists so I propose that we found some new institutions to attract american investment

we could start with
1. the Darwin Institute of Theology
2. the Isaac Newton Institute of Astrology
and perhaps
3. the Stephen Hawking Economics Laboratory

twitter users clueless about computing

this survey of happy programmers on twitter just proves what I say about a) twitter users and b) perl....

perl amoongst swine?

how useful is pervasive computing....MP expense data analysis

this guardian datastore MP expense visualisation site is a very nice example of how the net + data processing comes togetehr to allow rapid analysis and display of things that matter - this is a lot better than all the headline grabbing and really brings home a lot of interesting facets of the behaviour of our elected representatives...its also a nice example of a distributed collaboration!

matter transmogrifiers & trek tech

so how come in star trek when they beam across to an alien space ship
the enterprise crew don't arrive in the alien transporter
in alien bodies, eh?

answer me that, dearie

all CS People should read

this interview with lamport is timeless (so to speak:-)

is a research lab useful?

a tech news report on MSR Cambridge open day on zdnet seems to feel that the sort of open ended research they do is not "useful" and is merely a status thing - the report is based on the things seen that day and could be contrasted with the glowing bbc report about google

The contrast is strong - the stuff the zdnet reporter says is useless and the stuff the bbc enthuse about are completely different - they are also selective
a) MSR cambridge has done shedloads of things (more than any other lab) that have made it into products and mainstream products at that (tools and techniques to fix concrrency problems, remove device driver problems, and game AI work, for example) -
b) the pipleline for work to get out of MSR into a products group is around 5 years...
c) the google work, in contrast is much more like Cisco's model (hire or buy some PhDs in whose work is nearly done...and
d) is mostly just development

The lack of context in either report is typical of modern slapdash journalism - IPv6 mobile work came from Lancaster - things like lo-power are on everyone's agenda from home users, EU and US lawmakers to data centers and mobile devices....the idea that apple would exist without the tech transfer from Xerox PARC into Apple research into product lines is laughable - the timeline there was more like 10-15 years - once tat group was done, of course Jobs shut it down but longer term, they will regret not having a constantly refreshed on tap pool of researchers

in the current economic climate, most pundits think it is even more crucial to have a research pipeline to come out of recession with shiny new stuff - hence Telefonica, T-Labs, MSR, etc etc, have ring-fenced the budget for their research labs - governments too have (Obama increased US research budgets, the UK have tried to at least keep EPSRC funding level...)

yes it has status and marketing value none the least amongst tech/geek followers - of course it doesn ,because it is a clueful strategy, not some empty-headed shell purely for windows-dressing (pun intended).

Having recently been part of a review team at Telefonica I&D, the Hamilton Institute, Max Planck Institute for Software Systems, Eurecom (in Sophia Antipolis) and MSR, I can honestly say that these guys are all fantastically useful, and people that can't see this are looking for the wrong thing (I'm not just talking about contributions to fundamental human knowledge, I am talking about contributions to health, entertainment and business (the bottom line)

class hierarchy and facebook

I've just got facebook on my Windows mobile 6 phone

next to my friends who have iPhones, I feel pretty sad

and next to the folks here who haev snazyy android phones, I feel somewhat sad

so
windows mobile = working class
android = middle class
iPhone = upper class

This is inline with th immortal Cleese, Barker, Corbett class sketch from pre-python years....

Monty-Haskell, anyone?

jolly good project to do with helicopter....

oh, ok it's quite cool - iphone
to run things :-
remotely, in the air

maybe a nintendo wii controller would have been better tho