CMPE 150 Introduction to Computer Networks Dr Chane L Fullmer chane cse ucsc edu Spring 2003 UCSC cmpe150 1 Homework Assignments Homework assignment 3 Chapter Four Due by May 22 Spring 2003 UCSC cmpe150 2 CMPE 152 Introduction to Computer Networks SET 10 Routing Part II Spring 2003 UCSC cmpe150 3 Routing Algorithms Most books and papers classify routing algorithms into distance vector and link state algorithms Distance Vector Algorithm Routers exchange their distances to known destinations a router uses the distance vectors received from its neighbors to compute its own distances Computation is distributed Link State Algorithm Routers exchange information about the state of the links in the network a router uses this information to compute its distances to destinations Computation is local Spring 2003 UCSC cmpe150 4 DBF Information maintained at each router Information exchanged among routers Distance Table Distance to each destination reported by each neighbor Link Cost Table Cost of link to each adjacent node Routing Table Distance and successor next hop to each destination Vector of one or more entries each entry stating the distance to a destination Services assumed Update messages are exchanged reliably a node knows who its neighbors are Spring 2003 UCSC cmpe150 5 Bellman Ford Algorithm BF iterates on the number of hops away from a node Step 1 Initialize source node S with a 0 distance to itself and all other nodes with an infinite distance A smallest distance from S to the nodes 2 2 2 10 S E 0 2 5 Step 4 Stop if all nodes B have been covered and no label can be reduced by increasing H Else set H H 1 and repeat Step 3 Spring 2003 C 1 Step 2 Set H 1 Step 3 Label all nodes H hops away from S with the 10 1 D Link costs are the same in both link directions UCSC cmpe150 6 Bellman Ford Algorithm H 4 1 A 5 10 C 1 4 2 2 2 10 S 0 E 6 2 5 B 3 1 D 4 No more nodes can be reached and no label can be reduced Spring 2003 UCSC cmpe150 7 Looping in DBF 5 B 5 B 10 A C Similar looping could occur if the cost of the links to j increased drastically e g to 20 1 2 2 6 A Erroneous paths persist as long as they appear to be the shortest paths 10 S DBF cannot be used with link costs that have a large variance 5 5 B 1 3 D Spring 2003 D etc 4 B UCSC cmpe150 8 Traditional Link State Algorithm LSA Developed as a result of DBF s looping and nontermination problems Two components Topology map distribution Local shortest path computation Each router runs a local shortest path algorithm Dijkstra s using the topology stored locally Flooding is used to replicate the topology map at every router Each router is responsible for reporting the state of outgoing links to the rest of the network Two link state updates per link reach every router Spring 2003 UCSC cmpe150 9 Shortest Path First SPF Algorithm Step 1 Initialize Set SPF root where root is router running SPF Distance to root 0 and distance to other nodes cost of link or infinity Step 2 Find next node for SPF set Find a node x not in SPF set such that distance to from root Min distance to node outside of SPF set Augment SPF set with x Stop if SPF set contains all nodes Step 3 Change minimum distance For each node y outside SPF set do dist to y Min dist to y dist to z in SPF cost of z y Repeat Step 2 Spring 2003 UCSC cmpe150 10 SPF Example SPF S A 10 C 1 2 2 2 10 S 0 E 2 5 B Spring 2003 UCSC 1 D cmpe150 11 SPF Example 1 SPF S A 10 C 1 2 2 2 10 S 0 E 2 5 B 5 Spring 2003 UCSC 1 D cmpe150 12 SPF Example 11 1 SPF S A 10 A C 1 2 2 2 10 S 0 E 2 5 B 1 3 Spring 2003 UCSC D cmpe150 13 SPF Example 5 1 SPF S A B A 10 C 1 2 2 2 10 S 0 E 2 5 B 3 Spring 2003 UCSC 1 D 4 cmpe150 14 SPF Example SPF S A B D A Labels do not change as we continue to expand SPF set 10 C 1 SPF S A B D C SPF S A B D C E 5 1 2 2 2 10 S 0 Stop after covering E since all nodes are covered by SPF set 6 E 2 5 B 1 3 D 4 Note that iteration is on the next node that can be covered with the next shortest path hence complete topology must be known by router Spring 2003 UCSC cmpe150 15 Flooding of Link States Information Stored at Routers Each router maintains all the nodes and all the links in the network in a topology graph Each link in the graph has a cost a sequence number and an age Spring 2003 UCSC cmpe150 16 Flooding of Link States Information Exchanged Each router is responsible for communicating the latest state of each adjacent outgoing link The router sends a link state update LSU to report changes on an adjacent outgoing link A sequence number is used to identify the latest LSU An LSU also specified the age of the LSU and the age of an LSU is decremented each time it is forwarded and while it is in storage We assume that LSUs are exchanged reliably between any two routers and that a router knows who its neighbors are Spring 2003 UCSC cmpe150 17 Flooding of LSUs Flooding Mechanism consists of three rules Rule 1 Deleting old LSUs Discard old LSUs locally A router discards an LSU in its topology graph when it reaches a maximum age Refresh own LSUs A router transmits periodically an LSU for each of its outgoing links and assigns a 0 age and the highest sequence number to the LSU Allows recycling of sequence numbers Hands off sequence numbers of LSUs The router originating an LSU is the only one that can change the sequence number of the LSU Spring 2003 UCSC cmpe150 18 Flooding of LSUs Rule 2 Propagating LSUs Forward valid LSUs A router that receives a more recent LSU with a valid age from a given neighbor propagates it to all its other neighbors Correct neighbor that reported old data A router that receives an outdated LSU from a neighbor discards the LSU received and sends its more recent LSU to the neighbor Propagate resets A router that receives a more recent LSU with a zero age propagates the LSU to all its other neighbors if the link is in its topology graph and deletes the link from its topology graph else it ignores the LSU Spring 2003 UCSC cmpe150 19 Flooding of LSUs Rule 3 Handling Topology Changes Spring 2003 Make sure that neighbors have the same topology …
View Full Document
Unlocking...