1David Evanshttp://www.cs.virginia.edu/evansCS150: Computer ScienceUniversity of VirginiaComputer ScienceClass 29: Making PrimitivesClass 29: Trick-or-Treat Protocols2CS150 Fall 2005: Lecture 29: Trick-or-TreatThis Week in CS150• Today: – Networking and the Internet– Trick-or-Treat Protocols• Wednesday: – How to make a dynamic web site using HTML, SQL, Python• Friday: Return to Models of Computation3CS150 Fall 2005: Lecture 29: Trick-or-TreatWho Invented the Internet?4CS150 Fall 2005: Lecture 29: Trick-or-TreatWho Invented Networking?5CS150 Fall 2005: Lecture 29: Trick-or-TreatWhat is a Network?A group of three or more connected communicating entities6CS150 Fall 2005: Lecture 29: Trick-or-TreatBeacon Chain NetworkingThus, from some far-away beleaguered island, where all day long the men have fought a desperate battle from their city walls, the smoke goes up to heaven; but no sooner has the sun gone down than the light from the line of beacons blazes up and shoots into the sky to warn the neighboring islanders and bring them to the rescue in their ships. Iliad, Homer, 700 BCChain of beacon’s signaled Agammemnon’s return (~1200BC), spread on Greek peaks over 600km.27CS150 Fall 2005: Lecture 29: Trick-or-TreatPony Express• April 1860 – October 1861• Missouri to California– 10 days– 10-15 miles per horse, ~100 miles per rider• 400 horses total (not per station like Kahn’s)8CS150 Fall 2005: Lecture 29: Trick-or-TreatChappe’s Semaphore NetworkMobile Semaphore TelegraphUsed in the Crimean War 1853-1856 First Line (Paris to Lille), 17949CS150 Fall 2005: Lecture 29: Trick-or-TreatMeasuring Networks• LatencyTime from sending a bit until it arrives seconds(or seconds per geographic distance)• BandwidthHow much information can you transmit per time unitbits per second10CS150 Fall 2005: Lecture 29: Trick-or-TreatLatency and Bandwidth• Napoleon’s Network: Paris to Toulon, 475 mi• Latency: 13 minutes (1.6s per mile)– What is the delay at each signaling station, how many stations to reach destination–At this rate, it would take ~1 hour to get a bit from California• Bandwidth: 2 symbols per minute (98 possible symbols, so that is ~13 bits per minute– How fast can signalers make symbols– At this rate, it would take you about 9 days to get ps7.zip11CS150 Fall 2005: Lecture 29: Trick-or-TreatImproving Latency• Less transfer points– Longer distances between transfer points– Semaphores: how far can you see clearly • Telescopes can help, but curvature of Earth is hard to overcome– Use wires (electrical telegraphs, 1837)• Faster travel– Hard to beat speed of light (semaphore network)– Electrons in copper travel about 1/3rdspeed of light• Faster transfers– Replace humans with machines12CS150 Fall 2005: Lecture 29: Trick-or-TreatHow many transfer points between here and California?313CS150 Fall 2005: Lecture 29: Trick-or-Treat] tracert cs.berkeley.eduTracing route to cs.berkeley.edu [169.229.60.28]over a maximum of 30 hops:1 <10 ms <10 ms <10 ms router137.cs.Virginia.EDU [128.143.137.1]2 <10 ms <10 ms <10 ms carruthers-6509a-x.misc.Virginia.EDU [128.143.222.46]3 <10 ms <10 ms <10 ms uva-internet.acc.Virginia.EDU [128.143.222.93]4 <10 ms <10 ms <10 ms 192.35.48.425 <10 ms <10 ms 10 ms 192.70.138.226 <10 ms 10 ms 10 ms nycm-wash.abilene.ucaid.edu [198.32.8.46]7 20 ms 20 ms 20 ms clev-nycm.abilene.ucaid.edu [198.32.8.29]8 21 ms 30 ms 30 ms ipls-clev.abilene.ucaid.edu [198.32.8.25]9 30 ms 40 ms 30 ms kscy-ipls.abilene.ucaid.edu [198.32.8.5]10 40 ms 50 ms 40 ms dnvr-kscy.abilene.ucaid.edu [198.32.8.13]11 70 ms 70 ms * snva-dnvr.abilene.ucaid.edu [198.32.8.1]12 70 ms 70 ms 70 ms 198.32.249.16113 70 ms 70 ms 71 ms BERK--SUNV.POS.calren2.net [198.32.249.13]14 70 ms 70 ms 70 ms pos1-0.inr-000-eva.Berkeley.EDU [128.32.0.89]15 70 ms 70 ms 70 ms vlan199.inr-202-doecev.Berkeley.EDU [128.32.0.203]16 * * * Request timed out.17 70 ms 100 ms 70 ms relay2.EECS.Berkeley.EDU [169.229.60.28]Trace complete.> (define meters-to-berkeley (* 1600 3000)) ;; 3000 miles * 1600 meters/mi> (define seconds-to-berkeley 0.070)> (define speed-to-berkeley (/ meters-to-berkeley seconds-to-berkeley))> speed-to-berkeley ;;; meters per second68571428.57142857> (define speed-of-light 300000000) ;;; 300 000 000 meters per second> (/ speed-of-light speed-to-berkeley)4.375The Internet latency today is about ¼ the best physically possible!14CS150 Fall 2005: Lecture 29: Trick-or-TreatImproving Bandwidth• Faster transmission– Train signalers to move semaphore flags faster– Use something less physically demanding to transmit• Bigger pipes– Have multiple signalers transmit every other letter at the same time• Better encoding– Figure out how to code more than 98 symbols with semaphore signal– Morse code (1840s)15CS150 Fall 2005: Lecture 29: Trick-or-TreatMorse CodeRepresent letters with series ofshort and long electrical pulses16CS150 Fall 2005: Lecture 29: Trick-or-TreatCircuit Switching• Reserve a whole path through the network for the whole message transmissionParisToulonNantesLyonBourgesOnce you start a transmission,know you will have use of the network until it is finished. But,wastes network resources.17CS150 Fall 2005: Lecture 29: Trick-or-TreatPacket Switching• Use one link at a timeParisToulonNantesLyonBourgesInterleave messages – send whenever the next link is free.18CS150 Fall 2005: Lecture 29: Trick-or-TreatCircuit and Packet Switching• (Land) Telephone Network– Circuit: when you dial a number, you have a reservation on a path through the network until you hang up• The Internet– Packet: messages are broken into small packets, that find their way through the network link by link419CS150 Fall 2005: Lecture 29: Trick-or-TreatinternetworkA collection of multiple networks connected together, so messages can be transmitted between nodes on different networks.20CS150 Fall 2005: Lecture 29: Trick-or-TreatOkay, so whoinvented the Internet?21CS150 Fall 2005: Lecture 29: Trick-or-Treat“Trick or Treat” Protocols22CS150 Fall 2005: Lecture 29: Trick-or-Treat“Trick or Treat” Protocols• Trick-or-Treater must convince victim that she poses a credible threat• Need to prove you know a trick, without revealing what it is– Revealing the trick gives victim opportunity to prevent