CSC 4320/6320 Operating Systems Lecture 12 Distributed System StructuresChapter 16: Distributed System StructuresChapter ObjectivesCentralized vs Distributed SystemsDistributed Systems: Motivation/IssuesDistributed Systems: Goals/RequirementsNetworking DefinitionsBroadcast NetworksBroadcast Networks DetailsBroadcast Network ArbitrationCarrier Sense, Multiple Access/Collision DetectionPoint-to-point networksPoint-to-Point Networks DiscussionPoint-to-Point Network designFlow control optionsFlow Control (con’t)The Internet Protocol: “IP”Address SubnetsAddress Ranges in IPHierarchical Networking: The InternetSimple Network TerminologyRoutingSetting up Routing TablesNetwork ProtocolsNetwork LayeringBuilding a messaging serviceIP Packet FormatSlide 28Reliable Message Delivery: the ProblemUsing AcknowledgementsHow to deal with message duplicationBetter messaging: Window-based acknowledgementsTransmission Control Protocol (TCP)TCP Windows and Sequence NumbersEnd of Lecture 12CSC 4320/6320Operating SystemsLecture 12Distributed System StructuresSaurav KarmakarChapter 16: Distributed System Structures•Motivation•Types of Network-Based Operating Systems•Network Structure•Network Topology•Communication Structure•Communication Protocols•Robustness•Design Issues•An Example: NetworkingChapter Objectives•To provide a high-level overview of distributed systems and the networks that interconnect them•To discuss the general structure of distributed operating systemsCentralized vs Distributed Systems•Centralized System: System in which major functions are performed by a single physical computer–Originally, everything on single computer–Later: client/server model•Distributed System: physically separate computers working together on some task–Early model: multiple servers working together»Probably in the same room or building»Often called a “cluster”–Later models: peer-to-peer/wide-spread collaborationServerClient/Server ModelPeer-to-Peer ModelDistributed Systems: Motivation/Issues•Why do we want distributed systems?–Cheaper and easier to build lots of simple computers–Easier to add power incrementally–Users can have complete control over some components–Collaboration: Much easier for users to collaborate through network resources (such as network file systems)•The promise of distributed systems:–Higher availability: one machine goes down, use another–Better durability: store data in multiple locations–More security: each piece easier to make secure •Reality has been disappointing–Worse availability: depend on every machine being up»Lamport: “a distributed system is one where I can’t do work because some machine I’ve never heard of isn’t working!”–Worse reliability: can lose data if any machine crashes–Worse security: anyone in world can break into system•Coordination is more difficult–Must coordinate multiple copies of shared state information (using only a network)–What would be easy in a centralized system becomes a lot more difficultDistributed Systems: Goals/Requirements•Transparency: the ability of the system to mask its complexity behind a simple interface•Possible transparencies:–Location: Can’t tell where resources are located–Migration: Resources may move without the user knowing–Replication: Can’t tell how many copies of resource exist–Concurrency: Can’t tell how many users there are–Parallelism: System may speed up large jobs by spliting them into smaller pieces–Fault Tolerance: System may hide varoius things that go wrong in the system•Transparency and collaboration require some way for different processors to communicate with one anotherNetworking Definitions•Network: physical connection that allows two computers to communicate•Packet: unit of transfer, sequence of bits carried over the network–Network carries packets from one CPU to another–Destination gets interrupt when packet arrives•Protocol: agreement between two parties as to how information is to be transmitted•Broadcast Network: Shared Communication Medium– Shared Medium can be a set of wires» Inside a computer, this is called a bus» All devices simultaneously connected to devices– Originally, Ethernet was a broadcast network» All computers on local subnet connected to one another– More examples (wireless: medium is air): cellular phones, GSM GPRS, EDGE, CDMA 1xRTT, and 1EvDO Broadcast NetworksMemoryProcessorI/ODeviceI/ODeviceI/ODeviceInternetBroadcast Networks Details•Delivery: When you broadcast a packet, how does a receiver know who it is for? (packet goes to everyone!)–Put header on front of packet: [ Destination | Packet ]–Everyone gets packet, discards if not the target–In Ethernet, this check is done in hardware»No OS interrupt if not for particular destination–This is layering: we’re going to build complex network protocols by layering on top of the packetHeader(Dest:2)Body(Data)MessageID:1(ignore)ID:2(receive)ID:4(ignore)ID:3(sender)Broadcast Network Arbitration•Arbitration: Act of negotiating use of shared medium–What if two senders try to broadcast at same time?–Concurrent activity but can’t use shared memory to coordinate! •Aloha network (70’s): packet radio within Hawaii–Blind broadcast, with checksum at end of packet. If received correctly (not garbled), send back an acknowledgement. If not received correctly, discard.»Need checksum anyway – in case airplane flies overhead–Sender waits for a while, and if doesn’t get an acknowledgement, re-transmits.–If two senders try to send at same time, both get garbled, both simply re-send later.–Problem: Stability: what if load increases?»More collisions  less gets through more resent  more load…  More collisions…»Unfortunately: some sender may have started in clear, get scrambled without finishingCarrier Sense, Multiple Access/Collision Detection•Ethernet (early 80’s): first practical local area network–It is the most common LAN for UNIX, PC, and Mac –Use wire instead of radio, but still broadcast medium•Key advance was in arbitration called CSMA/CD: Carrier sense, multiple access/collision detection–Carrier Sense: don’t send unless idle»Don’t mess up communications already in process–Collision Detect: sender checks if packet trampled. »If so, abort, wait, and retry.–Backoff Scheme: Choose wait time before trying again•How long to wait after trying to send and