Distributed Algorithms in Networks EECS 122 Lecture 17 Department of Electrical Engineering and Computer Sciences University of California Berkeley The Internet is a HUGE Distributed System Nodes are local processors Messages are exchanged over various kinds of links Nodes contain sensors which sense local changes Nodes control the network jointly Method for doing this is a distributed algorithm Example Routing Time taken to solve the problem has two components Computation time taken for local processing Communication time for messages to be received over the links March 21 2006 AKP EECS122 Lecture 17 2 1 Solving Global Problems in a Distributed Setting Examples Minimum Spanning Tree Shortest Path Leader Election Topology Broadcast Much easier to think in terms of centralized algorithms Creativity needed to convert to the distributed case March 21 2006 AKP EECS122 Lecture 17 3 Network Protocols often have unintended effects TCP Example 1 TCP connections detect congestion after it has happened May cause packet drops from uncongested well behaved flows Two TCP flows sharing the same router get uneven bandwidths because one has a much smaller RTT than the other Routing Non congested flows back off Example 2 Oscillation and countless other pathologies It is very difficult to avoid these unintended effects March 21 2006 AKP EECS122 Lecture 17 4 2 Today Focus on protocol design issues How to move from Centralized to Distributed Alg Synchronous and Asynchronous computation Why does the Asynchronous Bellman Ford converge Selfish behavior distributed systems March 21 2006 AKP EECS122 Lecture 17 5 The Network is Heterogeneous Speed Dialup to terabit fiber Reliability Hosts Distributed Server farms to 486 PC Links Noisy wireless to virtually error free fiber Congestion Trustworthiness What is a general enough model to cover all of this March 21 2006 AKP EECS122 Lecture 17 6 3 Consensus over an Unreliable Link A and B in a connection over an unreliable link They both want to terminate the connection only if they are certain that no more packets will arrive from the other user A B A won t terminate unless it knows that B knows it is about to terminate B won t terminate unless it knows that A knows it is about to terminate March 21 2006 AKP EECS122 Lecture 17 7 Consensus Problem Suppose B tells A it can terminate and A receives this message say M A can terminate but B will never know if A actually received M and so it can t terminate A B A sends ACK M to B but then A needs to makes sure that B received this message so it must wait for ACK ACK M A never terminates In fact NO protocol exists to solve this problem Worth convincing yourself of this fact March 21 2006 AKP EECS122 Lecture 17 8 4 Link model Error correction Propagation Delay Fixed Variable but no more than d Variable with no upper bound Other components of delay Assume that errors can eventually corrected Queueing Delay Transmission Delay Packet order FIFO Can be delivered in arbitrary order March 21 2006 AKP EECS122 Lecture 17 9 Maintaining accurate topology information A B Whenever a link goes down up its end points send messages to all their neighbors who then flood slow link C D March 21 2006 AKP EECS122 Lecture 17 10 5 Maintaining accurate topology information A B Down C Whenever a link goes down up its end points send messages to all their neighbors who then flood 1 CD fails Down D March 21 2006 AKP EECS122 Lecture 17 11 Maintaining accurate topology information Down A B Whenever a link goes down up its end points send messages to all their neighbors who then flood 1 CD fails A marks the link down Down C D March 21 2006 AKP EECS122 Lecture 17 12 6 Maintaining accurate topology information Up A B Down Up C Whenever a link goes down up its end points send messages to all their neighbors who then flood 1 CD fails A marks the link down 2 CD comes back up Up D March 21 2006 AKP EECS122 Lecture 17 13 Maintaining accurate topology information Up A B Down Whenever a link goes down up its end points send messages to all their neighbors who then flood 1 CD fails A marks the link down 2 CD comes back up Up C D March 21 2006 AKP EECS122 Lecture 17 14 7 Maintaining accurate topology information Up A B Down Up C Whenever a link goes down up its end points send messages to all their neighbors who then flood 1 CD fails A marks the link down 2 CD comes back up A marks the link up 3 A marks the link down D March 21 2006 AKP EECS122 Lecture 17 15 Maintaining accurate topology information Up Down A B Up msg lost Up C This can be fixed with sequence numbers but then other problems emerge March 21 2006 Whenever a link goes down up its end points send messages to all their neighbors who then flood 1 CD fails A marks the link down 2 CD comes back up A marks the link up 3 A marks the link down 4 CA fails Up message lost A thinks CD is down when it is actually up D AKP EECS122 Lecture 17 16 8 Synchronous v s Asynchronous Algorithms Synchronous algorithms can be described in terms of global iterations The time taken for a given iteration is the time taken for the slowest processor to complete that iteration time driven E g TDM or SONET Asynchronous algorithms execute at a processor based on received messages and internal state event driven E g IP protocols which must run over heterogeneous systems March 21 2006 AKP EECS122 Lecture 17 17 Slotted Time Slotted system 1 2 3 All nodes agree on slot boundaries Have access to a global clock Helps to co ordinate the nodes Every node can run the same algorithm March 21 2006 Proving correctness is generally tractable if the centralized algorithm is analyzable Easier to understand the sequence of communication between nodes AKP EECS122 Lecture 17 18 9 Synchronous Bellman Ford SBF Every node runs the same algorithm Time is slotted and in every tick each node sends its distance vector At time h node i has as an estimate of the shortest path to node 1 that has h 1 hops Dh 1 I j mink N i Dh k j c i k 1 2 1 4 1 1 2 2 1 3 3 1 6 1 51 4 3 1 2 4 1 4 1 3 2 3 1 6 4 1 3 2 3 1 4 6 6 5 6 5 6 5 4 4 2 3 2 3 2 March 21 2006 19 AKP EECS122 Lecture 17 Synchronous Timing 1 2 1 Great when links are reliable and similar idle idle 4 3 3 1 6 1 2 4 1 5 4 idle 1 2 3 Node 1 1 2 3 Node 6 March 21 2006 5 AKP EECS122 Lecture 17 20 10 Synchronous Timing 1 2 1 But what when some links are much faster idle idle …
View Full Document
Unlocking...