Computer Science 425 Distributed Systems CS 425 / CSE 424 / ECE 428 Fall 2010Our Distributed System DefinitionSo far…Slide 4Internet 5-Layer Networking StackRouting AlgorithmsDistance Vector RoutingDistance Vector RoutingSlide 9Pseudo-Code for RIPLink State RoutingSlide 12Slide 13Transport Layer =Transmission Control ProtocolDNS: Domain Name SystemDNS Name ServersDNS: Root Name ServersSimple DNS ExampleDNS ExampleDNS: Iterated QueriesDNS: Caching and Updating RecordsSummaryMidterm Exam StatisticsBackup SlidesARP: Address Resolution Protocol between IP and Underlying NetworksARP ExampleARPSlide 28Slide 29Lecture 14-1Lecture 14-1Computer Science 425Distributed SystemsCS 425 / CSE 424 / ECE 428Fall 2010Computer Science 425Distributed SystemsCS 425 / CSE 424 / ECE 428Fall 2010Indranil Gupta (Indy)October 7, 2010Lecture 14NetworkingReading: Chapter 3 (relevant parts) 2010, I. Gupta, K. Nahrtstedt, S. Mitra, N. Vaidya, M. T. Harandi, J. HouLecture 14-2Lecture 14-2Our Distributed System DefinitionOur Distributed System DefinitionA distributed system is a collection of entities, each of which is autonomous, programmable, asynchronous and failure-prone, and communicating through an unreliable communication medium.•Our interest in distributed systems involves –design and implementation, maintenance, study, algorithmics•Entity=a process on a device (PC, PDA)•Communication Medium=Wired or wireless networkFocus of this lectureLecture 14-3Lecture 14-3So far…So far…•Abstract distributed system – collection of processes over a communication medium•Protocols/algorithms for synchronization, snapshots, multicast, election, mutual exclusion, failure detectors•Will work in any distributed group of processes1. E.g., Group of processes on computer hosts2. E.g., Group of processes on PDAs•For most of this course, we’ll focus on (1): computer hosts over the InternetLecture 14-4Lecture 14-4The Internet (Internet Mapping Project, color coded by ISPs)PCs,routers,switches…=nodeslinks=edgesLecture 14-5Lecture 14-5Internet 5-Layer Networking StackInternet 5-Layer Networking StackMessages (UDP) or Streams (TCP)ApplicationTransportInternetUDP or TCP packetsIP datagramsNetwork-specific framesMessageLayersUnderlying networkData Link LayerThis is where all distributed algorithms/techniques runLecture 14-6Lecture 14-6Routing Algorithms Routing Algorithms Nodes connected in some topology. Routing algorithm runs at network layer in each node. Goal of routing algorithm:given the destination IP address in packet, determine the “next hop”thus determine the route for each packet as it travels through the net,dynamically update routing information to reflect failures, changes and congestion. Two approaches:Distance-vector (e.g., RIP)Every node knows the next-hop for each possible destination LANLink-state (e.g., OSPF)Every node knows status of each “link” in the networkIn both, information maintained as a tableTables updated eitherProactively – periodically, orReactively – when a neighbor/some link status changesNETWORK/INTERNET LAYERLecture 14-7Lecture 14-7Distance Vector RoutingDistance Vector Routing•Also termed as distributed Bellman-Ford algorithm or Ford-Fulkerson algorithm, included in RIP (Routing Information Protocol), AppleTalk, and Cisco routers.–Each node/router maintains a table indexed by each destination node. Entry gives the best known distance to destination and which link to use for forwarding.–Once every T seconds each router sends to each neighbor its own entire table. Neighbor uses this to update its own table. (proactive)Lecture 14-8Lecture 14-8Distance Vector Routing Distance Vector Routing ABDECHosts or LANsRouters136452To Link Cost B 1 1 C 1 2 D 3 1 E 1 2 A local To Link Cost A 2 2 B 2 1 D 5 2 E 5 1C local Routing Table for ARouting Table for CTo Link Cost A 1 1 C 2 1 D 4 2 E 4 1B local Routing Table for BLink number (all links have cost=1)Lecture 14-9Lecture 14-9Distance Vector RoutingDistance Vector Routing+, then min across neighborsCosts only (next hop omitted)Lecture 14-10Lecture 14-10Pseudo-Code for RIPPseudo-Code for RIPSend: Each t seconds or when Tl changes, send Tl on each non-faulty outgoing link.Receive: Whenever a routing table Tr is received on link n:for all rows Rr in Tr {if (Rr.link not equal n) {Rr.cost = Rr.cost + 1;Rr.link = n;if (Rr.destination is not in Tl) add Rr to Tl; // add new destination to Tlelse for all rows Rl in Tl {if (Rr.destination = Rl.destination and (Rr.cost < Rl.cost or Rl.link = n)) Rl = Rr;// Rr.cost < Rl.cost : remote node has better route// Rl.link = n : remote node is more authoritative}}}Lecture 14-11Lecture 14-11Link State RoutingLink State Routing•Each router must1. Discover its neighbors and learn their network addresses–When a router is booted up, it learns who its neighbors are by sending a special Hello packet on each point-to-point link.–The router on the other end sends back a reply.2. Measure the delay or cost to each of its neighbors–A router sends a special Echo packet over the link that the other end sends back immediately. By measuring the round-trip time, the sending router gets a reasonable delay estimate.3. Construct a packet telling all it has just learned.–Broadcast this packetLecture 14-12Lecture 14-12Link State RoutingLink State Routing•A router broadcasts a link-state-advertisement (LSA) packet after booting, as well as periodically (or upon topology change). Packet forwarded only once, TTL-restricted•Initial TTL is very high.Lecture 14-13Lecture 14-13Link State RoutingLink State Routing4. Broadcast the LSA packet to all other routers.•Each packet contains a sequence number that is incremented for each new LSA packet sent.•Each router keeps track of all the (source router, sequence) pairs it sees. When a new LSA packet comes in, it is checked against the pairs. If the received packet is new, it is forwarded on all the links except the one it arrived on.•The age of each packet is included and is decremented once per time unit. When the age hits zero, the information is discarded. Initial age = very high5. For routing a packet, since the source knows the entire network graph, it simply computes the shortest path
View Full Document
Unlocking...