Department of Electrical Engineering and Computer Sciences University of California Berkeley 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 TCP Example 1 TCP connections detect congestion after it has happened May cause packet drops from uncongested well behaved flows Non congested flows back off Example 2 Two TCP flows sharing the same router get uneven bandwidths because one has a much smaller RTT than the other Routing Oscillation and countless other pathologies It is very difficult to avoid these unintended effects Focus on the algorithms behind protocols How to move from Centralized to Distributed Alg Synchronous and Asynchronous computation Why does the Asynchronous Bellman Ford converge What are the effects of a changing topology on algorithm design How can protocols be designed to protect against dishonest nodes Very High Level Coverage 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 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 0 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 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 1 Error correction Assume that errors can eventually corrected Propagation Delay Fixed Variable but no more than d Variable with no upper bound Other components of delay Queueing Delay Transmission Delay Packet order FIFO Can be delivered in arbitrary order 2 3 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 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 Proving correctness is generally tractable if the centralized algorithm is analyzable Easier to understand the sequence of communication between nodes 4 56 7468 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 j that has h 1 hops Dh 1 i j mink N i Dh k c i k 1 2 1 4 1 1 2 2 1 1 6 1 3 2 4 1 51 4 1 4 2 3 1 3 3 1 6 5 6 4 4 2 3 5 2 2 6 4 6 1 3 3 3 1 4 6 5 3 2 5 9 1 2 1 4 1 2 3 1 2 3 1 2 3 3 1 6 1 3 2 4 1 5 4 9 1 2 1 4 1 2 1 6 1 2 4 1 5 4 3 2 1 3 3 2 1 3 3 Suppose the slowest process can complete an iteration in time Tp Link delay is always less than Tl Then a slot size of Tp Tl or more is sufficient But most processors may be idle most of the time What if Tp and or Tl are not known 9 1 2 1 1 2 1 6 1 2 4 1 5 4 3 2 4 1 3 3 2 1 3 3 0 1 2 1 4 1 2 3 2 1 1 3 2 3 3 1 6 1 3 2 4 1 5 4 4 6 7 468 Don t even wait to hear from all neighbors Use most recent information to compute new distance vectors i e use last received values of D and d Whenever ready each node i computes D i mink N i D k c i k Sends the result to each of its neighbors No notion of global iterations In general nodes are using different and possibly inconsistent estimates 1 1 2 1 1 2 3 4 5 6 7 8 4 9 10 11 12 1 2 3 1 2 3 13 14 15 3 1 6 1 3 2 4 1 5 4 16 2 4 6 Regardless of how asynchronous the nodes are the algorithm will eventually converge to the shortest path Links can go down and come up but as long as the topology is fixed after some time t the algorithm will eventually converge to the shortest path Why There s some hope because the D j can only go up if one of j s neighbors estimates has gone up There are too many different runs of ABF so lets try to bound the range of distance estimates of D j over time Do this by two different runs of SBF One bounds the estimates from above one from below Use different initial conditions for the two runs Standard initial conditions that we know converges to the correct answer Uo j and for node 1 estimates are zero Lo j 1 for j 2 3 and for node 1 estimates are zero 1 2 It turns out that both SBF runs converge to the correct optimal estimates D j i e for large enough k Uo j U1 j Uk j Uk 1 j D j Lo j L1 j Lk j Lk 1 j D j For every iteration k of the two SBF runs Lk j Lk 1 j D j Uk 1 j Uk j It is possible to show that for any k there is a time t such that Lk j Lk 1 j D t Uk 1 j Uk j Since both lower and upper runs converge to the optimal so will ABF eventually 46 Consider a version of ABF in which a new estimate is sent iff and only if it is lower than the one previously sent Compare this with a scheme LSBF that uses local synchronization this is faster than using SBF Then it …
View Full Document
Unlocking...