tag:blogger.com,1999:blog-352388762024-03-05T07:02:22.384-08:00clogcomputer lab objectionable
<a href=http://www.cl.cam.ac.uk/~jac22/music/dan%20zep.mp3>generalisations</a>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.comBlogger409125tag:blogger.com,1999:blog-35238876.post-17075954506861760052023-11-28T00:34:00.000-08:002023-11-28T00:34:44.926-08:00Principles of Communications Final Week to Nov 28th/L16<p> Wrap up - you should now be able to see the supervisor <a href="https://www.cl.cam.ac.uk/teaching/2324/PrincComm/supervisors/">pages</a> which summarise the course and have links to questions and releavnt/in scope past exam questions.</p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-23293619683511200052023-11-21T00:56:00.000-08:002023-11-21T02:34:27.917-08:00Principles of Communications Week 8 to Nov 23rd/L15<p> This week is two Big Pictures </p><p><br /></p><p>On Nov 21, we do:</p><p>1/ Traffic Management over multiple time scales - linking together several ideas between routing/congestion control, open and closed loop flow control, admission, pricing, and, finally, a bit about signaling.</p><p>feedback/admission work at any time scale</p><p>short> reduce rate/ lose packets</p><p>medium> try again later</p><p>long>change to a better provider</p><p>So note peak rate pricing is just a slow version of congestion control + shadow prices.</p><p>Note using a single network may amortize costs well, but a single technology has single failure mode - the model of copper/fiber/radio has a lot of fault tolerance, which is high value for critical infrastructure.</p><p>Note that the problem with capacity planning and traffic matrix/source behaviour in the general internet is that a) it isnt a regular topology, b) each ISP is doing it in competition but also in cooperation with other ISPs! However, this paper showed how well the ISPs coped when everyone switched to working/learning from him <a href="https://cacm.acm.org/magazines/2021/7/253468-a-year-in-lockdown/fulltext">the internet in the age of covid</a></p><p>On Nov 23rd we'll cover:</p><p>2/ System Design Rules - these are rules of thumb that apply in many systems, processsor design, operating systems, networks, etc etc</p><p>More can and will be said...</p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-41105455074502111682023-11-14T00:15:00.000-08:002023-11-16T04:05:03.568-08:00Principles of Communications Week 7 to Nov 17th/L13<p> This week we're covering firstly data centers (through the lens of q-jump and its clever "fan-in" trick), and secondly, optimisation of routes and rates.</p><p>The mix of application platforms we see in the data center lecture are classic mapreduce (as represented by Apache Hadoop) and stream processing (as represented by Microsoft's Naiad)[2], as well as memcached (an in memory file store cache, widely used to reduce storage access latency and increase file throughput - e.g. for aforesaid platforms), as well as PTP (a more precise clock sysnch system than the widely used Network Time Protocol[1]). For an example of use of map reduce, consider Google's original <a href="https://www.ijies.net/finial-docs/finial-pdf/120418CSE0017.pdf">pagerank in hadoop</a>. For the interested reader, this <a href="https://sigops.org/s/conferences/sosp/2013/papers/p439-murray.pdf">paper on timely data flow</a> is perhaps useful background.</p><p><br /></p><p>Optimisation is a very large topic in itself, and underpins many of the ideas in machine learning when it comes to training - ideas like stochastic gradient descent (SGD) are seen in how assign traffic flows to routes, here. In contrast, the decentralised, implicit optimisation that a collection of TCP or "TCP friendly" flows use is more akin to federated learning, which is another whole topic in itself.</p><p>Why a log function? maybe see <a href="https://tgmstat.wordpress.com/2014/01/22/declining-marginal-utility-and-the-logarithmic-utility-function/">bernouilli</a> on risk</p><p>Why proportional fairness? from <a href="https://en.wikipedia.org/wiki/Proportional-fair_rule">social choice theory!</a></p><p>Are people prepared to pay more for more bandwidth? One famous <a href="https://people.ischool.berkeley.edu/~hal/Papers/brookings-talk.pdf">Index Experiment</a> says yes.</p><p><br /></p><p>1. see <a href="https://www.cl.cam.ac.uk/teaching/2223/ConcDisSys/materials.html">IB Distributed Systems</a> for clock synch</p><p>2. see last year's <a href="https://www.cl.cam.ac.uk/teaching/2223/CC/">Cloud Computing</a> (II) module for a bit more about data centers&platforms.</p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-90412641255867700372023-11-06T21:43:00.004-08:002023-11-06T21:43:38.569-08:00Principles of Communications Week 6 to Nov 10th/L11<p> This week, we cover two closely related topics:-</p><p>1. Flow&Congestion Control</p><p>There are three regimes for where there may need to be a matching process between sender and recipient rates.</p><p>a) sender - the sender may not always have data to send - think about sourcing data from a camera or microphone with a given coding, you get some peak rate anyhow. or you just might have a short data transfer that never "picks up speed"</p><p>b) network - here some type of feedback is needed to tell senders about network conditions - this could be a call setup (open loop control) - not something we do in today's internet, or it could be closed loop feedback via dupacks, packet loss or ECN, and a rate adjustment in the sender (congestion window or explicit rate control.</p><p>c) receiver - the receiver can slow down the sender by advertising a small receive windor or just delaying acks or both.</p><p><br /></p><p>Much of today's network uses these three approachs via TCP or QUIC. There's a nice study based on wide area measrements that shows how congestion control (case b above) is quite rare and more often we have a or c...see this paper:-</p><p><a href="https://discovery.ucl.ac.uk/id/eprint/1401260/">TCP equation&reality</a></p><p><br /></p><p>2. Scheduling&Queue Management</p><p>Schedulers in switches and routers try to minimise the "damage" caused by one flow to other packet flows through a network device that has more packets arriving than it can send just now. Buffering packets turns into jitter, delay, which for audio or video turns into playout buffer delay, or packet loss, which for TCP data traffic is a key congestion signal, and for audio/video is quality degradation.</p><p>Schedulers try to allocate bottleneck capacity fairly e.g. via round robin, but how long do queues really need to be? as the network scales up, perhaps the impact of queueing decreases and fairly simple schedulers may suffice - see this paper/talk for more ideas in this space. Of course, actual overload leading to packet loss is still bad, but the actual delay and jitter seen by a large aggregation of flows through a switch/router may not be the significant worry...</p><p><a href=" https://www.cl.cam.ac.uk/teaching/2002/DigiComm2/mckeown-pratt.ppt">law of large numbers and what happens in queues then really</a><br /></p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-62976901829051372582023-10-31T00:54:00.011-07:002023-11-06T21:44:03.829-08:00Principles of Communications Week 5 to Nov 3rd/L9This week were covering Mobile Networking(*rant*) (briefly) and then telephony networks(^motives for innovation!) - architecture, but in particular, random routing as it is a neat illustration of the use of non-deterministic approaches to distributed systems which yields efficient results See also Valiant Load Balancing (for example this <a href="https://web.eecs.umich.edu/~mosharaf/Readings/VL2.pdf">work at Microsoft</a>, also used in Operating Systems (NGINX, for example. <div><br /></div><div> For a general discussion of random choices and their application, see this <a href="https://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf">study</a> (very much deep background reading only!) </div><div><br /></div><div> *rant*
The TCP checksum is designed to protect end-to-end packets against corruption - it is fairly low cost to. compute (ones-compliment sum of all the 16 bit fields in the TCP header and application data) compared to more complex integrity checks used in lower level protocols (link level checks are usually designed to be implemented in hardware). </div><div><br /></div><div>However, it features one incredibly poor additional design choice, which is that the check also includes adding in fields from the "pseudo header" which includes parts of the IP header (source & destination addre<strike></strike>sses, protocol field and IP segment length). (see <a href="https://www.geeksforgeeks.org/calculation-of-tcp-checksum/">for details</a>)
This has two problems: firstly it messes with the fate sharing design of the Internet so that end system comms is now entangled with network layer. Secondly, it stops a TCP connection surviving IP address re-assignment, which is essentially what happens if you move network (e.g. switch from using your wifi to using your cellular data link). </div><div><br /></div><div>The argument made by the TCP designers was that this prevents some security threat from someone messing with your IP address. It is not clear that that threat actually really represents a real problem since nowadays, TCP implements multipath with multiple IP addresses and switches or combines them safely. Also other protocols (e.g. TLS, above TCP, or else QUIC, as a replacement for TCP+TLS) make use of a secure association between end systems, which is far more secure and resilient to mobility anyhow. So another mistake in the Internet design.</div><div><br /></div><div>^Motivation for Innovation! The first automatic exchange was designed by an undertaker, Almon Strwoger who believed human operators were diverting business calls to his competitors - <a href="https://en.wikipedia.org/wiki/Strowger_switch">real story</a> is a bit less interesting, but still important - precursor to the cross-bar switch!</div><div><br /></div><div>Started on Flow Control - for closed loop/feedback control systems, this paper by <a href="https://royalsocietypublishing.org/doi/10.1098/rspl.1867.0055">James CLerk Maxwell, back in 1868</a> covered some nice maths behind how to desgin controllers!</div>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-10774218078567502962023-10-24T00:06:00.003-07:002023-10-26T02:47:53.034-07:00Principles of Communications Week 4 to Oct 26th/L7<p> This week, we'll finish up BGP, and cover multicast routing.</p><p><br /></p><p>General lessons from BGP - information hiding can be harmful to decentralised algorithms. but information hiding may be a necessary dimension to some distributed systems due to business cases (commercial inconfidence/competitive data). </p><p>Are there other ways to retain decentralised or federated operations but to retain also confidentiality? Perhaps using secure multiparty computations (not covered in this course!). There are a number of other federated services emerging in the world (applications like Mastodon and Matrix, and also, federated Machine Learning systems like flower) so this probably needs a good solution.</p><p>Multicast has a great future behind it - some neat thinking, but largely replaced by application layer content distribution networks (e.g. netflix, youtube, apple/microsoft software update distribution), and the move away from simultaneous mass consumption of video/audio. For more info on limitations of multicast, this <a href="https://ieeexplore.ieee.org/document/819174">paper</a> is a good (quick) read.</p><p>Are application layer overlays a solution to other "in network" alleged enhancements? Possibly - for example, Cloudflare obviate the need tor always on IPv4 or IPv6 addresses - this also wasn't covered in this course, but might be of interest. Thir work is described <a href="https://research.cloudflare.com/publications/Fayed2021/">here</a> and other papers of theirs may be of current interest.</p><p>
</p><div class="page" title="Page 4">
<div class="section" style="background-color: white;">
<div class="layoutArea">
<div class="column">
<p><span style="font-size: 0pt;">Tup </span><span style="font-size: 0pt;">A previously unavailable route is announced as avail-
able. This represents a route repair.
</span></p>
<p><span style="font-size: 0pt;">Tdown </span><span style="font-size: 0pt;">A previously available route is withdrawn. This
represents a route failure.
</span></p>
<p><span style="font-size: 0pt;">Tshort </span><span style="font-size: 0pt;">An active route with a long ASPath is implicitly re-
</span></p>
<p><span style="font-size: 0pt;">placed<br />
with a new route p ossessing a shorter ASPath.
This represents b oth a route repair and failover.
</span></p>
<p><span style="font-size: 0pt;">Tlong </span><span style="font-size: 0pt;">An active route with a short ASPath is implicitly
replaced with a new route p ossessing a longer ASPath.
This represents b oth a route failure and failover. </span></p>
</div>
</div>
</div>
</div><p>Couple of questions on Graphs in last section on BGP </p><p>1. A Few Bad Apples - graph doesn't asymptote, despite being cummulative as it prefixes can be announced more than once (i.e. > 100%!)</p><p>2 How long does BGP take to adapt to changes - the legend refers to</p><p class="p1" style="font-family: Menlo; font-feature-settings: normal; font-kerning: auto; font-optical-sizing: auto; font-size: 12px; font-stretch: normal; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-numeric: normal; font-variant-position: normal; font-variation-settings: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">Tup A previously unavailable route is announced as available. This represents a route repair.</span></p><p class="p1" style="font-family: Menlo; font-feature-settings: normal; font-kerning: auto; font-optical-sizing: auto; font-size: 12px; font-stretch: normal; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-numeric: normal; font-variant-position: normal; font-variation-settings: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">Tdown A previously available route is withdrawn. This represents a route failure.</span></p><p class="p1" style="font-family: Menlo; font-feature-settings: normal; font-kerning: auto; font-optical-sizing: auto; font-size: 12px; font-stretch: normal; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-numeric: normal; font-variant-position: normal; font-variation-settings: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">Tshort An active route with a long ASPath is implicitly </span><span style="font-variant-ligatures: no-common-ligatures;">placed</span></p><p class="p1" style="font-family: Menlo; font-feature-settings: normal; font-kerning: auto; font-optical-sizing: auto; font-size: 12px; font-stretch: normal; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-numeric: normal; font-variant-position: normal; font-variation-settings: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">with a new route p ossessing a shorter ASPath. This represents b oth a route repair and failover.</span></p><p class="p1" style="font-family: Menlo; font-feature-settings: normal; font-kerning: auto; font-optical-sizing: auto; font-size: 12px; font-stretch: normal; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-numeric: normal; font-variant-position: normal; font-variation-settings: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">Tlong An active route with a short ASPath is implicitly replaced with a new route p ossessing a longer ASPath. This represents b oth a route failure and failover.</span></p><p>
</p><div class="page" title="Page 4">
<div class="section" style="background-color: white;">
<div class="layoutArea">
<div class="column">
<p><span style="font-size: 0pt;">Tup </span><span style="font-size: 0pt;">A previously unavailable route is announced as avail-
able. This represents a route repair.
</span></p>
<p><span style="font-size: 0pt;">Tdown </span><span style="font-size: 0pt;">A previously available route is withdrawn. This
represents a route failure.
</span></p>
<p><span style="font-size: 0pt;">Tshort </span><span style="font-size: 0pt;">An active route with a long ASPath is implicitly re-
</span></p>
<p><span style="font-size: 0pt;">placed<br />
with a new route p ossessing a shorter ASPath.
This represents b oth a route repair and failover.
</span></p>
<p><span style="font-size: 0pt;">Tlong </span><span style="font-size: 0pt;">An active route with a short ASPath is implicitly
replaced with a new route p ossessing a longer ASPath.
This represents b oth a route failure and failover.
</span></p>
</div>
</div>
</div>
</div><br /><p></p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-69252393540121707252023-10-16T23:57:00.006-07:002023-10-20T00:43:14.555-07:00Principles of Communications Week 3 to Oct 19th/L5<p>Wrapping up with centralised routing, MPLS and Segment Routing - if you are interested in latter topic, see <a href="https://arxiv.org/pdf/1904.03471.pdf">this survey of SR</a></p><p>This week, we'll start on BGP/Policy Routing, getting up to traffic engineering, including the amusingly named "hot and cold potato". Next week we will wrap up BGP covering semantics & performance.</p><p>A great overview of <a href="https://web.mit.edu/6.829/www/currentsemester/papers/AS-bgp-notes.pdf">BGP</a> if you want an alternate source.</p><p><br /></p><p>Some General <a href="https://www.cl.cam.ac.uk/teaching/2324/PrincComm/slides/pc-possible-problem-sheets-2023">High level questions about material</a> together with rough dates when each topic will appear in lectures.</p><p><br /></p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-85371835047194313342023-10-12T01:37:00.005-07:002023-10-26T22:58:08.651-07:00Principles of Communications Week 2 13/10/2023<p> This week we covered "centralised" routing - two aspects:</p><p>Fibbing - hybrid of SDN/central controller and distributed computation using link-state</p><p>(note on <a href="https://www.dasblinkenlichten.com/rib-and-fib-understanding-the-terminology/">terminology.</a> )</p><p>If you are interested in how to replicate state machines, have a look at this <a href="https://api.repository.cam.ac.uk/server/api/core/bitstreams/4826a463-6b65-427d-b8b2-56fa22fb3841/content">work on distributed consensus</a> . Noting that these replication schemes themselves are very subtle and difficult to get right.</p><p><br /></p><p>MPLS - and segment routing - which is somewhat stateful forwarding, which therefore requires some input from some controller or management plane to do anything other than default paths (if MPLS or SR just use the IGP to setup labels/segements, you just get whatever the IGP does, so kind of making the use of MLPS or SR rather pointless).</p><p>Some useful backup material on segmenet routing, operationally from <a href="https://www.juniper.net/documentation/us/en/software/junos/is-is/topics/task/configuring-srgb-label-range.html">Juniper Networks</a></p><p><br /></p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-4823280181683434772023-10-12T01:33:00.001-07:002023-10-12T01:33:14.260-07:00Principles of Communications Week 1 5/10/2023<p> </p><h3 class="post-title entry-title" itemprop="name" style="background-color: #fff9ee; color: #222222; font-family: Georgia, Utopia, "Palatino Linotype", Palatino, serif; font-feature-settings: normal; font-kerning: auto; font-optical-sizing: auto; font-size: 24px; font-stretch: normal; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-numeric: normal; font-variant-position: normal; font-variation-settings: normal; font-weight: normal; line-height: normal; margin: 0.75em 0px 0px; position: relative;"><p style="font-size: 15.4px;">Today sees start of 2023/2024 year and for Part II taking <a href="https://www.cl.cam.ac.uk/teaching/2324/PrincComm/" style="color: #993300; text-decoration-line: none;">Principles of Communications</a> I'll be noting progress and also adding occasional related reading/ and corrections on this blog.</p><p style="font-size: 15.4px;">If you want to revise anything to warm up for the course, I suggest last year's <a href="https://www.cl.cam.ac.uk/teaching/2223/CompNet/" style="color: #993300; text-decoration-line: none;">Computer Networks</a> course should be a quick re-read! A fun review of <a href="https://www.youtube.com/watch?v=7w-iLiQ9_zA" style="color: #993300; text-decoration-line: none;">40+ years of the Internet</a></p><p style="font-size: 15.4px;">This week we'll just make a start on routing.</p><p style="font-size: 15.4px;">For fun, you might find this discussion on <a href="https://networkingchannel.eu/large-language-models-and-networking-what-are-the-challenges-and-opportunities/" style="color: #993300; text-decoration-line: none;">why LLMs aren't much use for networking, mostly</a> interesting - <a href="https://www.youtube.com/watch?v=hbfXL6zRnuU&ab_channel=TheNetworkingChannel" style="color: #993300; text-decoration-line: none;">video recording of panel session</a></p><p style="font-size: 15.4px;"><br /></p><p style="font-size: 15.4px;">Reference requested for Glossary of Terms: from <a href="https://www.internetsociety.org/internet/glossary-internet-terms/" style="color: #993300; text-decoration-line: none;">ISOC</a></p><p style="font-size: 15.4px;">Some acronyms come from the <a href="https://en.wikipedia.org/wiki/OSI_model" style="color: #993300; text-decoration-line: none;">7 layer model of the communications stack</a> including terms like PHY (short for physical, so not really an acronym).</p></h3><div class="post-header" style="background-color: #fff9ee; color: #222222; font-family: Georgia, Utopia, "Palatino Linotype", Palatino, serif; font-size: 12.6px; line-height: 1.6; margin: 0px 0px 1.5em;"><div class="post-header-line-1"></div></div><div class="post-body entry-content" id="post-body-3747170811437542829" itemprop="description articleBody" style="background-color: #fff9ee; color: #222222; font-family: Georgia, Utopia, "Palatino Linotype", Palatino, serif; font-size: 15.4px; line-height: 1.4; position: relative; width: 570px;"></div>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-30463430104243919052022-11-28T05:24:00.006-08:002022-11-28T05:24:49.782-08:00Principles of Communications Week 9 L16 29th Nov, 2022 - Systems Design pt II and Wrap.<p>Solving for Systems:-</p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"></p><ul style="text-align: left;"><li><span class="s1" style="font-variant-ligatures: no-common-ligatures;">multiplexing</span></li><li><span style="font-variant-ligatures: no-common-ligatures;">pipelining</span></li><li><span style="font-variant-ligatures: no-common-ligatures;">batching </span></li><li><span style="font-variant-ligatures: no-common-ligatures;">exploiting locality (spatial and temporal)</span></li><li><span style="font-variant-ligatures: no-common-ligatures;">exploiting commonality </span></li><li><span style="font-variant-ligatures: no-common-ligatures;">hierarchy </span></li><li><span style="font-variant-ligatures: no-common-ligatures;">using binding with indirection </span></li><li><span style="font-variant-ligatures: no-common-ligatures;">virtualization (multiplexing, indirection, binding) </span></li><li><span style="font-variant-ligatures: no-common-ligatures;">exploiting randomization </span></li><li><span style="font-variant-ligatures: no-common-ligatures;">using softstate versus explicit state exchange </span></li><li><span style="font-variant-ligatures: no-common-ligatures;">employing hysterisis </span></li><li><span style="font-variant-ligatures: no-common-ligatures;">separating data and control </span></li><li><span style="font-variant-ligatures: no-common-ligatures;">extensibility</span></li></ul><p></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span style="font-variant-ligatures: no-common-ligatures;"><br /></span></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span style="font-variant-ligatures: no-common-ligatures;">and measure, measure, measure and characterise.</span></p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-6827097003342092312022-11-24T04:08:00.003-08:002022-11-24T04:10:16.300-08:00lovely explainer of the internet, at 5 levels of complexity<p>Jim Kurose explains <a href="https://www.youtube.com/watch?v=0EqKnvzo3no&ab_channel=WIRED">the Internet</a> to five different levels of complexity.</p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-74730206201883473252022-11-22T00:07:00.004-08:002022-11-23T23:58:18.713-08:00Principles of Communications Week 8 L14/L15 22nd&24th Nov, 2022 - Traffic Management and Systems Design<p>Traffic Management</p><p>This is mainly about the Timescale decomposition of traffic management components, packet transit/RTT times, flow setup times, traffic matrix time variations, and long term demand variation (usually increase).</p><p>Also novel protocol deployment create new demand patterns.</p><p>This all creates requirements for empirical input e.g. of user utilities for elastic and inelastic traffic demands, and for behaviour in response to offpeak (or congestion) type time varying charging for resource use. A great example of recent work on how things change sometimes quite quckly is this <a href="https://gsmaragd.github.io/publications/CACM-COVID19/CACM-COVID19.pdf">paper about the change in application demands during the pandemic</a></p><p>Signaling protocol complexity - signaling couples multiple components - end systems and users, to reuters/switches, schedulers and admission control, and even routing, so signaling is a mess, and to date, very little deployed in the Internet. Most traffic management decisions are made using bespoke (ad hoc) measurement tools and techniques.</p><p>One of the big arguments recently is how to divide up a budget (whether congestion or delay) amongst hops (e.g. AS hops) in a path - with some overall resource constraint (e2e delay must be less than 300ms) each hop will want to maximise the delay it can impose for bursty traffic (same for RED based ECN triggers) so it can maximise user traffic - need incentive matching!</p><p>Systems Design</p><p>Some things change demand surprisingly quick. - already mentioned the impact of the pandemic on increased in demand for interactive video/audio, but also sources shifted from work to working from home in daytime. New change is decentralised social media like Mastodon and Matrix, which have many p2p servers (mastdon today has around 4000, serving 8M people - the user base is growing at around 1M a week!)</p><p>Interesting social/legal/regulatory constraints include the simple (the EU mandates free data roaming or even trivial, like USBC phone charging sockets!) to the subtle - the Digital Markets Act requires any large service provider to open up APIs for interoperation - new work in internet standards means there will be open protocols that allow all systems (not just e-mail and web servers, but messaging and social media etc) to interwork - presumably also video conferencing </p><p>Technically, this is actually trivial (e.g. most video and audio use same coding - indeed in WebRTC have to use same protocols too). The trickier pieces are interworking key management for security, especially for group communications.</p><p>Pipelining example lead to replacement of HTTP 1.0/TCP with HTTP 3/QUIC, which allows arbitrary ordering of packets delivered over UDP (but still with reliability, flow and congestion control, and e2e privacy) - this allows browsers far more freedom to render material from multiple sources/media.</p><p>And this will keep changing and changing as people create new applications and services, and new communications technology - all that requires measurement, measurement and also measurement.</p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-74519065068604029962022-11-15T00:15:00.007-08:002022-11-17T06:50:43.303-08:00Principles of Communications Week 7 L12/L13 15th&17th Nov, 2022 - Data Centers & Optimisation<p> Data Centers - example of Queue Jump</p><p><br /></p><p>1. Data centers have regular topology and software can be centrally managed</p><p>2. the Fan-in factor of traffic, sometiems known as TCP in-cast, can and does cause spikey delays, which very badly reduces the performance of distributed compiutations, clock synchronisation and in memory disk caches, all of which degrades the throughput of data centers</p><p>3. if we can differentiate traffic, we can use different schedules to treat flows with low latency requirements, from those with high throughput but no particularly latency bound needs.</p><p>4. in a 3 hop data center, a small number of priority queues will work - as long as the sum of traffic from sources of a given priority is controlled based on computing the occupancy of that priority class, and its delay impact - then there is capacity left for lower priority, and still very short queues too... Sources can be policed to ensure the classes don't starve out lower priorities, and this can be done below the app in the OS, or below the OS in a hypervisor</p><p>Optimisation:- multipath routes, decentralised rates.</p><p>from an entirely different perspective, we can treat the routing and rate control problems as optimisation challenges - in this approach, we can use gradient descent methods for assigning flows to routes, and distributed optimisation (via feedback control and increase/decrease searching for optimal utility) to compute rates.</p><p>Note well - the optimisation of routes can work at any level of aggregation, and hence is suitable for<i> traffic engineering, </i>and is largely a centralised techniqu<i>e.</i> The formulation is also agnostic about multipath routing, so is suitable in the presence of live use of redundant paths and load balancers, and is consistent with end-to-end multipath protocols (e.g. multipath TCP or QUIC). One tends to think of the route optimisation approaches being for longer term matching of traffic to paths (but could also suit open flow controlled traffic at the individual flow level, obviously, though this is not used in the Internet today). Of course, gradient descent methods are widely used in training in machine learning and AI.</p><p>n.b. finding minimum of a function <a href="https://www.onlinemath4all.com/how-to-find-maximum-and-minimum-points-using-differentiation.html#:~:text=Substitute%20x%20%3D%202%20in%20f%22(x).&text=To%20find%20the%20minimum%20value,2%20in%20f(x).&text=Substitute%20x%20%3D%20%2D1%20in%20f%22(x).&text=To%20find%20the%20maximum%20value,1%20in%20f(x).">reminder</a></p><p>The distributed, asynchronous, non-coordinated optimisation of rates (i.e. TCP congestion control or equivalents) is also applicable to other distributed machine learning. The rate adaptation is also suitable for multipath <i>end-to-end protocols</i> (i.e. MPTCP). So the rate optimisation techniques operate on the round-trip time timescales.</p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-86220793397796325072022-11-08T05:43:00.004-08:002022-11-15T06:06:00.945-08:00Principles of Communications Week 6 L10/L11 8&10 Nov, 2022 - Scheduling and Queue Management<p>I am going to loop back around to flow and congestion control, because these things go together like strawberries and cream, or meta and verse:-)</p><p>Flow control can be open loop (call setup with a traffic descriptor and an associated admission control algorithm), or closed loop, based on feedback (dupack, packet loss/timeout, or explicit congestion notification).</p><p>Packet forwarding can be FIFO, or Round Robin, or weighted according to some request (management, setup, payment, etc - out-of-band). If it is round robin, we get fairness quite naturally, and some degree of protection against misbehaviour of other flows. If the flows are policed (because they gave a descriptor in open loop, or because they implement congestion avoidance and control), then we get more protection against misbehaviour of other flows of packets. If the router implements an Active Queue Management scheme (like RED), as well as a schedule (like round robin), then we get more protection (even against our own misbehaviour).</p><p>A neat example of use of scheduling in a different layer is in the new web protocol, QUIC, in browsers - this paper <a href="https://h3.edm.uhasselt.be/files/HTTP3_Prioritization_extended_3jul2019.pdf">illustrates</a> nicely how one can improve rendering of pages by changing the order that components flow through the layers of HTTP, QUIC, to/from UDP/IP...</p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-5690345364395864292022-11-01T07:00:00.002-07:002022-11-15T00:18:23.484-08:00Principles of Communications Week 5 L8/L9 1&3 Nov, 2022 - Mobile&Random Routing + Open&Closed Loop Flow Control<p> We've looked at unicast (one direction) multicast (some direction), broadcast (all directions), mentioned any cast (any direction), and mobile (one level of redirection. We've also looked at metric v. random based route choice, and some policy interactions with traffic engineering (preferences that differ from policy or metric).</p><p>Note - slide 228 lists R (trunk reservation) with opposite sense to r on y axes on graphs showing diminishing return of impact of trunk reservation</p><p><br /></p><p>Next, we look at open-loop and closed-loop flow control. History of feedback controllers is <a href="https://royalsocietypublishing.org/doi/10.1098/rspl.1867.0055">ancient!</a></p><p>A fun thing to look at is the BSD TCP kernel code. - this book <a href="https://www.amazon.co.uk/TCP-IP-Illustrated-Implementation-APC/dp/020163354X">by Rich Stevens</a> is a walk through of that!</p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-23442809945404531682022-10-26T23:52:00.006-07:002022-11-15T00:18:09.966-08:00Principles of Communications Week 4 L6/7 25&27 Oct, 2022 - BGP Abstraction + Multicast<p> This week, we finished up looking at BGP by covering:</p><p></p><ol style="text-align: left;"><li>the stable paths abstraction - what does path vector+policy do, algorithmically?</li><li>real world dynamics and engineering for stability - the latter performance challenges show that the information hiding goals of inter-domain routing have not really been achieved very thoroughly! So intra-domain dynamics get exported to the world, because of hot potato and MEDs.</li></ol>As well as this, BGP requires a lot of external machinery for specifying policy, and for guarding against misinformation (by definition, harder to do with a system which has a goal of information hiding).<p></p><p><br />Then we looked at Internet Multicast - this also has some interesting challenges, that have prevented wide spread adoption:</p><p></p><ol style="text-align: left;"><li>potential use for leveraging DDoS attacks</li><li>lack of a policy/interdomain/business model (who causes down stream traffic?)</li></ol>In addition, multicast created headaches for high speed switch/router hardware designers<p></p><p>General lesson here is that global scale systems entail complex, multi-factor considerations, and don't believe everything out there running the world is actually based on completely sound design. Nevertheless, it has application in special cases/limited domains, such as backbones for TV distribution, and more especially, data center networks.</p><p>----admin:</p><p>Aside: just to support this, the university information service video recording system failed to capture audio&slides for the 20.10.22 lecture but luckily, last year's recordings are still available, and roughly from same dates (<a href="https://www.cl.cam.ac.uk/teaching/2122/PrincComm/video/">2021 recordings</a>) e.g. <span style="background-color: white; color: #171717; font-family: verdana, arial, sans-serif; font-size: 12px;">2021-10-19 2021-10-21 2021-10-26</span><span style="background-color: white; color: #171717; font-family: verdana, arial, sans-serif; font-size: 12px;"> </span></p><p><span style="background-color: white; color: #171717; font-family: verdana, arial, sans-serif; font-size: 12px;">Apologies for that!</span></p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-40252325821479503912022-10-20T04:02:00.004-07:002022-10-20T04:02:56.438-07:00Principles of Communications Week 3 L4/5 18&20 Oct, 2022 - Interdomain routing and BGP.<p>We started looking at the requirements for Interdomain routing - it has to provide connectivity between Autonomous Routing Domains which may be optimising paths for irreconcilable metrics/goals, so it can, at best, find paths that fit policies - it also respects business relationships - again, injected through policy/configuration somewhere (vendor/product specific tools!). Mistakes can be made. These are mapped into the various hacks to allow BGP to do some traffic engineering, like backup paths, load balancing and so on.</p><p>BGP is a path vector protocol, which has a plus point of hiding information, by default. And also has the minus point of hiding information by default:-) Being path vector (rather than just distance vector) BGP is at least loop free. However, it is still a diffusing computation, rather than a fixed epoch cycle, so news can travel slowly (or not at all). </p><p>Remember, what you announced is what other people look at to see how to get to things, in, or via, your network/AS</p><p>It is a classic political-technical space, where simple algorithmic solutions present themselves, but are dismissed because they don't include the competitive/incentive sides.</p><p>There have also been proposed alternative approaches to information hiding (advertise everything, but encrypt it and only give keys to people allowed to use this particular AS on a path) - that wouldn't scale.</p><p>Useful further reading/notes from this <a href="https://web.mit.edu/6.829/www/currentsemester/papers/AS-bgp-notes.pdf">MIT BGP book.</a></p><p>BGP has been around 20 years, and when it was introduced, was probably the world's first planetary scale programmable system. This is not necessarily a good thing, when the language is obscure, and the runtime is compromised.</p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-40951064898050793112022-10-14T07:15:00.004-07:002022-10-14T07:15:18.168-07:00Principles of Communications 2022. some high level questions<p> someone kindly reminded me i did have some high level problem/questions you could tackle when looking at lecture material - <a href="https://www.cl.cam.ac.uk/teaching/2021/PrincComm/slides/pc-possible-problem-sheets-2022">Questions to ask yourself</a> about the materials in Princ of Comm</p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-66804509499598928802022-10-11T02:19:00.005-07:002022-11-15T00:17:50.187-08:00Principles of Communications Week 2 L2 L3@LT2 11am, 11&13 Oct, 2022 - Central Routing and MPLS&Segment Routing<p> Recommend revisiting notes from IB networks course <a href="https://www.cl.cam.ac.uk/teaching/2021/CompNet/files/Topic04-Network.pdf ">2021-2022</a> where you can find link-state and distance vector from page 25 onwards!</p><p>So underlying distance vector (and path vector, see later when we discuss BGP and Inter-domain routing) is the notion of diffusing computations! Link-state is much simpler given in each epoch, we flood map data, and then everyone does a synchronised computation of shortest paths from themselves to all other nodes/destinations - fibbing relies on this, although the offline/centralised computation that produces additional virtual nodes can be anything - and this is also true of the paths computed for MPLS and segment routing and then distributed via CR-LDP or RSVP or other control protocols. One reference approach is in the paper linked from the course materials web page on DeFo...but there are many, once you open the network up to being re-programmed!</p><p>The key difference between Fibbing and classical SDN is that Software Defined Network controllers use OpenFlow (effectively an RPC like protocol) to add/modify FIBs in specific routers, whereas Fibbing simply joins in the Link State flooding protocol that all the routers use to update each other with the map (put into the RIB, then used to compute FIB entries, e.g. via Dijkstra Shortest Path algorithm). Hence the virtual nodes/and edges that the Fibbing controller adds behave just like real ones - appearing and disappearing as they are added or fail/remove, or the controller(s) adding them become unreachable (or reachable again after repair/reboot) - this is where the resilience comes from....that, and replicating the controllers.</p><p>Note for this course: Hierarchy is good for scaling, but doesn't always work when a network wants diversity - so we could have geographic, topological or organisational hierarchy, but we might want redundancy without common mode failures, so would connect to multiple providers "upstream", which undermines any notion of address aggregation in the forwarding tables! Adding in widespread use of NATs (network address translators) and the world is a lot more complex than we'd like!</p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-45219541176011515582022-10-06T23:07:00.001-07:002022-10-06T23:07:12.267-07:00Principles of Communications Week 1 L1@LT2 11am, 6 Oct, 2022 - Introduction and Start on Routing<p> Introduction to the course/outline of what will be covered.</p><p>Introduction to routing - up to basic idea of routing in general - not just networks, and not just packets and circits, but also cars, spaceships. Not just for shortest path, but also policy and energy.</p><p>Next week will cover features of current Internet Routing, and Centralised Routing, and start on Policy Routing.</p><p>This might be a good time to quickly revise <a href="https://www.cl.cam.ac.uk/teaching/2122/CompNet/">IB Networking</a> material (at least on shortest path/Dijkstra, and link state/distance vector!).</p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-46332560828594711282022-09-30T02:55:00.004-07:002022-09-30T02:55:56.488-07:00Explainable AI & Quantum<p> <span style="font-family: Menlo; font-size: 16px; font-variant-ligatures: no-common-ligatures;">Much "AI" in use today is basic machine learning, which is</span><span class="Apple-converted-space" style="font-family: Menlo; font-size: 16px; font-variant-ligatures: no-common-ligatures;"> frequently </span><span style="font-family: Menlo; font-size: 16px; font-variant-ligatures: no-common-ligatures;">simply statistics, </span><span style="font-family: Menlo; font-size: 16px; font-variant-ligatures: no-common-ligatures;">which have been in use since the first actuarial and ordnance tables were </span><span style="font-family: Menlo; font-size: 16px; font-variant-ligatures: no-common-ligatures;">devised to predict </span><span style="font-family: Menlo; font-size: 16px; font-variant-ligatures: no-common-ligatures;">risk or targets...so several hundred years (or longer if the Greeks or Ph</span><span style="font-family: Menlo; font-size: 16px; font-variant-ligatures: no-common-ligatures;">oencians or M</span><span style="font-family: Menlo; font-size: 16px; font-variant-ligatures: no-common-ligatures;">inoans used same math they had for astronomy for landing greek fire on</span><span class="Apple-converted-space" style="font-family: Menlo; font-size: 16px; font-variant-ligatures: no-common-ligatures;"> </span><span style="font-family: Menlo; font-size: 16px; font-variant-ligatures: no-common-ligatures;">other ships </span><span style="font-family: Menlo; font-size: 16px; font-variant-ligatures: no-common-ligatures;">accurately, or insure their ships' cargo against storm damage...</span></p><p class="p2" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px; min-height: 19px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"></span><br /></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">As for autonomy, this occurred as soon as someone built a feedback loop: M</span><span style="font-variant-ligatures: no-common-ligatures;">y fave paper on </span><span style="font-variant-ligatures: no-common-ligatures;">this james clark maxwell's Royal Society paper </span></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"><a href="https://www.maths.ed.ac.uk/~v1ranick/papers/maxwell1.pdf">On Governors</a> back in 18</span><span style="font-variant-ligatures: no-common-ligatures;">68</span></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><br /></p><p class="p2" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px; min-height: 19px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"></span><br /></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">For "black box" (as in "inexplicable" AI)- this is true of any system so<span class="Apple-converted-space"> </span></span><span style="font-variant-ligatures: no-common-ligatures;">complex that few </span><span style="font-variant-ligatures: no-common-ligatures;">or no single human understands all of it - so pretty much any smart phone </span><span class="s1" style="font-variant-ligatures: no-common-ligatures;">(without even </span><span style="font-variant-ligatures: no-common-ligatures;">getting into what goes on in the camera s/w) - nobody could both design th</span><span style="font-variant-ligatures: no-common-ligatures;">e chip and write</span></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">the OS (actually i think i know one person, but he's probably the last).</span></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><br /></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><br /></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">A "deep learning" (aka neural net) is usually explainable if someone just s</span><span style="font-variant-ligatures: no-common-ligatures;">pends the time and </span><span style="font-variant-ligatures: no-common-ligatures;">energy (it is computationally pricey) - two techniques</span></p><p class="p2" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px; min-height: 19px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"></span><br /></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">1/ shapley values for example <a href="https://arxiv.org/abs/2202.05594">here</a></span></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"><br /></span></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><br /></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">2/ energy landscapes<span class="Apple-converted-space"> - as in <a href="https://www.pnas.org/doi/full/10.1073/pnas.1919995117">this</a></span></span></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">https://www.pnas.org/doi/full/10.1073/pnas.1919995117</span></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"><br /></span></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;">Roughly, you can think about comuting significant changes in the entropy of the net at any step in training, and then, using shapley values on input features, identify what caused that change in the neural network (analogous to change point detection, with thresholds etc) and then export the feature list + decision as a new branch in a decision tree or random forest (for example).</p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"><br /></span></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">So interestingly, once you have built an explanation for a neural net, </span><span style="font-variant-ligatures: no-common-ligatures;">you ca</span><span style="font-variant-ligatures: no-common-ligatures;">n often replace the </span><span class="s1" style="font-variant-ligatures: no-common-ligatures;">thing with a random forest or other directly (i.e. self explaining) approa</span><span style="font-variant-ligatures: no-common-ligatures;">ch - this was sort </span><span style="font-variant-ligatures: no-common-ligatures;">of obvious too once people realised you could massively compress neural n</span><span style="font-variant-ligatures: no-common-ligatures;">ets (even using </span><span style="font-variant-ligatures: no-common-ligatures;">lossy compression algorithms - like video) suggesting most the links and</span><span class="Apple-converted-space" style="font-variant-ligatures: no-common-ligatures;"> </span><span style="font-variant-ligatures: no-common-ligatures;">weights were </span><span style="font-variant-ligatures: no-common-ligatures;">redundant.</span></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"><br /></span></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">So here's the quantum bit (pun intended) - the problem with computing shapley values and energy landscapes at every step in the training iteration is that it is very expensive (compared to the training itself), so if we have to do it often, this is unsustainable.</span></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"><br /></span></p><p class="p1" style="font-family: Menlo; font-size: 16px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">However, these (especially the energy landscape) might be amenable to computation by an analog quantum computer (described <a href="https://en.wikipedia.org/wiki/Adiabatic_quantum_computation">herein</a> ) perhaps making this affordable. Analog quantum computers are available, indeed have been applied to expensive problems like the transfer function of a 3D space to multiple radios - see <a href="https://paws.princeton.edu/quantumxwireless">princeton work</a> on this).</span></p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-45453991749607405072022-06-21T05:56:00.007-07:002022-06-21T05:56:32.314-07:00the philosophal problems of matter transportation and time travel<p><span style="font-family: Menlo; font-size: 14px; font-variant-ligatures: no-common-ligatures;">Theres' a great book by Harry Harrison called </span><span class="s1" style="font-family: Menlo; font-size: 14px; font-variant-ligatures: no-common-ligatures;">One Step From Earh, where he went through pretty much every possible philosophical </span><span class="s1" style="font-family: Menlo; font-size: 14px; font-variant-ligatures: no-common-ligatures;">interpretation of how matter transporter's could/might work including that they might </span><span style="font-family: Menlo; font-size: 14px; font-variant-ligatures: no-common-ligatures;">just copy a person rather than "move" them...</span></p><p class="p2" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px; min-height: 16px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"></span><br /></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">There's also at least one short story by Philip k. Dick where every time someone time </span><span class="s1" style="font-variant-ligatures: no-common-ligatures;">"travels", they actually sending a copy of themselves to the next time - the story ends </span><span style="font-variant-ligatures: no-common-ligatures;">in havoc as the population of the world ends up being dominated by millions of different </span><span style="font-variant-ligatures: no-common-ligatures;">age copies of the first time traveller...</span></p><p class="p2" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px; min-height: 16px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"></span><br /></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">The problem with this is that there's a point where philosophy meets physics or</span></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">chemistry or biology</span></p><p class="p2" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px; min-height: 16px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"></span><br /></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">As in the play, of course, your cells are replaced over time, so that you are not the </span><span class="s1" style="font-variant-ligatures: no-common-ligatures;">same set of components that you were (say) 7 years ago - but this is also true at the </span><span style="font-variant-ligatures: no-common-ligatures;">level of particles, only far faster....</span></p><p class="p2" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px; min-height: 16px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"></span><br /></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">And also at the level of cognition (given brain plasticity, and how it is believed </span><span style="font-variant-ligatures: no-common-ligatures;">memory really works, we are continually modifying who we "are" as we experience new </span><span style="font-variant-ligatures: no-common-ligatures;">things, even just recalling old things)...</span></p><p class="p2" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px; min-height: 16px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"></span><br /></p><p class="p2" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px; min-height: 16px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"></span><br /></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">On a more interesting take about paradox, Behold the Man, by Michael Moorcock was pretty </span><span style="font-variant-ligatures: no-common-ligatures;">ingenious...and for paradox busting par excellence, Robert Heinlein's classic By His </span><span style="font-variant-ligatures: no-common-ligatures;">Bootstraps is the business...</span></p><p class="p2" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px; min-height: 16px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"></span><br /></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">So taking the memory model as a template for the philosophical challenge of continuous </span><span style="font-variant-ligatures: no-common-ligatures;">identity, it seems to me that there's really several problems</span></p><p class="p2" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px; min-height: 16px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"></span><br /></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"></p><ul style="text-align: left;"><li><span class="s1" style="font-variant-ligatures: no-common-ligatures;">Fidelity</span></li></ul><p></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">if something is a high fidelity copy of the previous instance of a person, and the </span><span style="font-variant-ligatures: no-common-ligatures;">previous version is replaced, then from everyone elses point of view, this is the same</span></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">person.</span></p><p class="p2" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px; min-height: 16px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"></span><br /></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"></p><ul style="text-align: left;"><li><span style="font-variant-ligatures: no-common-ligatures;">M</span><span style="font-variant-ligatures: no-common-ligatures;">emory</span></li></ul><p></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">if the next instance of a person has the same (or very similar) memories to the previous </span><span style="font-variant-ligatures: no-common-ligatures;">instance, then they can delude themselves that they are the same person, as they will </span><span style="font-variant-ligatures: no-common-ligatures;">have the illusion of continuous existence - this is actually no different than how </span><span style="font-variant-ligatures: no-common-ligatures;">vision works, where your visual cortex as to make an apparently coherent and spatial and </span><span style="font-variant-ligatures: no-common-ligatures;">temporal continuous visual space out of what your eyes/retina detect, despite that that </span><span style="font-variant-ligatures: no-common-ligatures;">is intermittent and imperfect...</span></p><p class="p2" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px; min-height: 16px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;"></span><br /></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"></p><ul style="text-align: left;"><li><span style="font-variant-ligatures: no-common-ligatures;">C</span><span style="font-variant-ligatures: no-common-ligatures;">onsciousness</span></li></ul><p></p><p class="p1" style="font-family: Menlo; font-size: 14px; font-stretch: normal; font-variant-east-asian: normal; font-variant-numeric: normal; line-height: normal; margin: 0px;"><span class="s1" style="font-variant-ligatures: no-common-ligatures;">this is very tricky, since the locus of attention moves ahead (anticipation/ etc) </span><span style="font-variant-ligatures: no-common-ligatures;">as well as behind (memory) the current moment...however, if the brain is just a machine, </span><span style="font-variant-ligatures: no-common-ligatures;">then it is reasonable for the model it runs of the world to include prediction, and that </span><span style="font-variant-ligatures: no-common-ligatures;">model itself is copied from instance to instance of the person, providing the illusion </span><span style="font-variant-ligatures: no-common-ligatures;">of continued consciousness....</span></p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-929143471400994502022-04-14T05:40:00.000-07:002022-04-14T05:40:00.842-07:00onboard, board, offboard, outboard & knowledge base<p> there was an interesting internal tech talk recently at the Turing Institute by a fairly recent addition to the research engineering group, who had a lot of previous experience in various technologies knowledge bases in various different organisations, and was being mildly critical of the system that had evolved here.</p><p><br /></p><p>One thing struck me about this was that however you construct such a system, much of it (like an iceberg) is not in the visible components, but is reflective of how people use/navigate/update the knowledge, which is a shared delusion (like William Gibson's depiction of cyberspace in Neuromancer) - not in a bad way, but the longer the system exists, the harder it is for new people to acclimatise to it. Large parts of the structural information used by people to work with it are in their heads, not online.</p><p>so the system could automatically document how different kinds of users use it, by keeping breadcrumb/paper trails (you can of course do this in a wiki) and then do some kinds of statistical analysis to provide common, distinct modes/patterns explicitly. This could even be done in a privacy preserving way by combining federated learning (e.g. in client side tools, or browsers etc) with differential privacy, perhaps....</p><p><br /></p><p>a project for an intern?</p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-44499399252668439362022-04-12T06:59:00.002-07:002022-04-12T06:59:34.494-07:00metaphorical computing considered lazy<p> there's a story that originally ECT was discovered as a way to treat manic people after someone observed that chimps in captivity who got that way, but also had epileptic fits, were calmer after a fit. so then realising you could induce something that looked like a fit in chimps and therefore likely in people, the treatment was born, and many people suffered from this ludicrous idea for decades - I heard more recently, ECT has been somewhat rehabilitated and isn't used as a means to control unruly patients but actually has theraputic value, but the origin tale is still alarming.</p><p><br /></p><p>so what about other ideas that are based in leaky reasoning, for example...</p><p>artificial neural networks as a way to build classifiers? not with anything like the same node degree distribution or mechanism for firing whatsoever, so how would one build so many aNNs almost none of which bear any ressemblance to what goes on in our heads?</p><p>evolutionary programming (e.g. GP/GA) as a way to do optimisation? but note evolution is about natural selection of anything that fits the niche in the environment - that doesn't make it an optimisation at all, just a choice.</p><p>bio-inspired search, e..g based in ants trailing pheremones? as with evolution, this is a blind process that assumes nothing about the setup, and is mind bogglingly wasteful.</p><p><br /></p><p>Are there actually any vaguely sustainable ways of tackling these tasks (classifiers, optimisation, search) - of course there are...</p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0tag:blogger.com,1999:blog-35238876.post-3378939585974380142021-12-20T01:06:00.005-08:002021-12-20T01:06:50.413-08:00very good graduate school opportunities <p> strongly recommend Max Planck <a href=" https://www.cis.mpg.de/graduate-programs/cs-max-planck">CS@max</a> well resourced, world leading research institute in pleasant setting.</p>jon crowcrofthttp://www.blogger.com/profile/05692091803072506710noreply@blogger.com0