Department of Electrical Engineering and Computer SciencesUniversity of CaliforniaBerkeley ! "#$%&'( )*+ # Nodes are local processorsMessages are exchanged over various kinds of linksNodes contain sensors which sense local changesNodes control the network jointly Method for doing this is a distributed algorithm Example: RoutingTime taken to solve the problem has two components: Computation time taken for local processing Communication time for messages to be received over the links ! "#$%&"& ,-,, TCPExample 1TCP connections detect congestion after it has happenedMay cause packet drops from uncongested “well behaved flows”Non congested flows back offExample 2Two TCP flows sharing the same router get uneven bandwidths because one has a much smaller RTT than the otherRoutingOscillation and countless other pathologiesIt 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 nodesVery High Level Coverage ! "#$%&/-+& Examples:Minimum Spanning TreeShortest PathLeader ElectionTopology Broadcast Much easier to think in terms of centralized algorithmsCreativity needed to convert to the distributed case ! "#$%&0' ) Speed Dialup to terabit fiberReliability Hosts: Distributed Server farms to 486 PC Links: Noisy wireless to virtually error free fiberCongestionTrustworthinessWhat is a general enough model to cover all of this? ! "#$%& -*A and B in a connection over an unreliable linkThey both want to terminate the connection only if they are certain that no more packets will arrive from the other userA BA 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 ! "#$%&1 &Suppose B tells A it can terminate and A receives this message, say MA can terminate, but B will never know if A actually received M and so it can’t terminateA BA 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. ! "#$%&2Error correctionAssume that errors can “eventually” correctedPropagation DelayFixedVariable but no more than dVariable with no upper boundOther components of delayQueueing DelayTransmission DelayPacket orderFIFOCan be delivered in arbitrary order ! "#$%& # -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 SONETAsynchronous 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 nodesEvery node can run the same algorithm Proving correctness is generally tractable if the centralized algorithm is analyzableEasier to understand the sequence of communication between nodes ! "#$%&# 4567468Every node runs the same algorithmTime 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 hopsDh+1(i,j) = minkN(i){Dh(k) + c(i,k)} 13462513 2351362514 241621413462514114123113462513 236 ! "#$%&"#9� 321 32 1 32
View Full Document
Unlocking...