CPS110: More NetworksVirtual/physical interfacesOrdered messagesSlide 4Slide 5Slide 6Reliable messagesDetecting and fixing dropsSlide 9Slide 10What about corruption?Slide 12Slide 13Byte streamsSlide 15Slide 16Slide 17SentinelsCourse administrationDistributed systemsMotivation for distributed appsSlide 22Slide 23Slide 24Building up to distributed appsSlide 26Send/receive primitivesSlide 28Slide 29Slide 30Client-serverSlide 32Producer-consumerSlide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Other approachesSlide 42Network abstractionsRemote procedure call (RPC)The RPC illusionRPC stub functionsSlide 47Slide 48RPC notesRPC exampleJava RMI exampleProblems with RPCExample RPC with pointersSlide 54Finishing RPCStructuring a concurrent systemAlternative structureRest of the semesterCPS110: More NetworksLandon CoxMarch 30, 2009Virtual/physical interfacesHardwareHardwareOSOSApplicationsApplicationsOrdered messagesNetworks can re-order IP messagesE.g. Send: A, B. Arrive: B, AHow should we fix this?Assign sequence numbers (0, 1, 2, 3, 4, …)Ordered messagesDo what for a message that arrives out of order?(0, 1, 3, 2, 4)a.Save #3 and deliver after #2 is delivered(this is what TCP does)b.Drop #3, deliver #2, deliver #4c.Deliver #3, drop #2, deliver #4b. and c. are ordered, but not reliable (messages are dropped).Relies on the reliability layer to handle lost messages.Ordered messagesFor a notion of order, first need “connections”Why?Must know which messages are related to each otherIdea in TCPOpen a connectionSend a sequence of messagesClose the connectionOpening a connection ties two sockets togetherConnection is socket-to-socket unique: only these sockets can use itSequence numbers are connection specificVirtual/physical interfacesHardwareHardwareOSOSApplicationsApplicationsReliable messagesUsually paired with orderingTCP provides both ordering and reliabilityHardware interfaceNetwork drops messagesNetwork duplicates messagesNetwork corrupts messagesApplication interfaceEvery message is delivered exactly onceDetecting and fixing dropsHow to fix a dropped message?Have sender re-send itHow does sender know it’s been dropped?Have receiver tell the senderReceiver may not know it’s been sentLike asking in the car,“If we left you at the theater, speak up.”Detecting and fixing dropsHave receiver acknowledge each messageCalled an “ACK”If sender doesn’t get an ACKAssume message has been droppedResend original messageIs this ok for the sender to assume?No. ACKs can be dropped too (or delayed)Detecting and fixing dropsPossible outcomesMessage is delayed or droppedACK is delayed or droppedStrategyDeal with all as though message was droppedWorst case if message wasn’t dropped after all?Need to deal with duplicate messagesHow to detect and fix duplicate messages?Easy. Just use the sequence number and drop duplicate.What about corruption?Messages can also be corruptedBits get flipped, etcEspecially true over wireless networksHow to deal with this?Add a checksum (a little redundancy)Checksum usually = sum of all bitsDrop corrupted messagesWhat about corruption?Dropping corrupted messages is elegantTransforms problem into a dropped messageWe already know how to deal with dropsCommon techniqueSolve one problem by transforming it into another1.Corruption  drops2.Drops  duplicates3.Drop any duplicate messages (very simple)Virtual/physical interfacesHardwareHardwareOSOSApplicationsApplicationsByte streamsHardware interfaceSend information in discrete messagesApplication interfaceSend data in a continuous streamLike reading/writing from/to a fileByte streamsMany apps think about info in distinct messagesWhat if you want to send more data than fits?UDP max message size is 64 KBWhat if data never ends?Streamed mediaTCP provides “byte streams” instead of messagesByte streamsSender writes messages of arbitrary sizeTCP breaks up the stream into fragmentsReassembles the fragments at destinationReceiver sees a byte streamFragments are not visible to either processProgramming the receiverMust loop until certain number of bytes arriveOtherwise, might get first fragment and returnByte streamsUDP makes boundaries visibleTCP makes boundaries invisible(loop until you get everything you need)How to know # of bytes to receive?1.Size is contained in header2.Read until you see a pattern (sentinel)3.Sender closes connectionSentinelsIdea: message is done when special pattern arrivesExample: C stringsHow do we know the end of a C string?When you reach the null-termination character (‘\0’)Ok, now say we are sending an arbitrary fileCan we use ‘\0’ as a sentinel?No. The data payload may contain ‘\0’ charsWhat can we do then?Course administrationLast day for Project 2 submissions89, 89, 89, 89, 87, 86, 83, 79, 79, 78, 76, 75, 49, 33, 28Project 3 will be out next weekHack into a serverSocket programming how-to postedRyan will cover in discussion section this weekWill post example client/server codeAny questions?Distributed systemsYou use distributed systems everyday.Both on your PC and behind the scenes.Motivation for distributed apps1. PerformanceMotivation for distributed apps1. Performance2. Co-locationCan locate computer near local resourcesExamples of local resourcesPeople, sensors, sensitive databaseMotivation for distributed apps1. Performance2. Co-location3. ReliabilityNot all computers will go down at onceDue to floods, fires, earthquakes, etcBetter chance of continuous serviceMotivation for distributed apps1. Performance2. Co-location3. Reliability4. Already have multiple machinesCan’t put everyone on one machineTry to stitch existing machines togetherBuilding up to distributed appsNeeded two things in multi-threaded programs1. Atomic primitives to control thread interleavings(interrupt disable/enable, atomic test&set)2. Way to share information between threads(shared address space)These won’t work for distributed applicationsNo interrupt disable/enable or atomic test&setNo shared memoryBuilding up to distributed appsCan only communicate through messagesSend messagesReceive messagesIf no shared data, are there race