CMPE 150 Introduction to Computer Networks Dr Chane L Fullmer chane cse ucsc edu Spring 2003 UCSC cmpe150 1 Homework Assignments Homework assignment 2 Due now Spring 2003 UCSC cmpe150 2 Homework Assignments Homework assignment 3 Chapter Four Due by May 22 Spring 2003 UCSC cmpe150 3 CMPE 150 Introduction to Computer Networks Lecture 9 Routing Part I Spring 2003 UCSC cmpe150 4 Network Layer The main functions at the network layer are addressing routing congestion control and admission control Addressing consists of identifying where a destination is with respect to the network topology Routing consists of a computing paths from sources to destinations and b forwarding packets along such paths Congestion control consists of limiting the amount of data a source can sent into the network Admission control consists of limiting the number of sources allowed to send data into the network and in a way is part of system wide congestion control Spring 2003 UCSC cmpe150 5 Routing Algorithms used to compute paths from sources to destinations can be Static or adaptive Routers compute paths off line or dynamically in response to changes in topology or even traffic Hierarchical or flat heterarchical Routers and hosts are organized into clusters of nodes or all destinations and routers are treated as peers On demand or table driven Routers maintain routing information for only those destinations for which need to forward data or for all destinations You will also see routing algorithms classified according to the type of information they use Spring 2003 UCSC cmpe150 6 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 This is a very limiting view Spring 2003 UCSC cmpe150 7 Routing Algorithms A routing algorithm is carrying out a distributed computation obtaining correct paths from each source to its desired destinations Some indication that at least some aspect of this computation has ended must be available to routers The end of any distributed computation can be detected in three known ways and combinations of such ways Termination detection over a tree Termination detection using sequence numbers Termination detection over a ring Distances or link states can be used in each of these three types of algorithms Spring 2003 UCSC cmpe150 8 Shortest Path Routing Problem Compute the path of minimum length from each router to each destination Notation G N E is the network of N nodes and E links Pji Ni i k i l i j hx l h h i i 1 j hop h i P ji p Spring 2003 i k D q h2 k UCSC cmpe150 9 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 10 Bellman Ford Algorithm 1 H 1 A 10 C 1 2 1 2 2 10 S 0 Only A and B can be reached within one hop 1 2 5 B 5 Spring 2003 E UCSC 1 D cmpe150 11 Bellman Ford Algortihm H 2 11 1 10 A C 2 1 2 2 2 2 10 S 0 E 2 5 B 5 3 Spring 2003 UCSC 1 D cmpe150 12 Bellman Ford Algorithm H 3 11 5 1 10 A C 1 2 2 2 10 S 3 0 Only E cannot be reached within three hops 5 2 3 B 3 Spring 2003 E UCSC 1 D 4 cmpe150 13 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 14 Distributed Bellman Ford Algorithm DBF The objective of DBF is to have a distributed implementation of BF so that routers can compute distances to destinations distributedly To accomplish this the computation of a distance to a destination starts at the destination itself The iteration of DBF is on the number of hops away from a destination DBF operates independently for each destination Destination starts by stating the distance to itself is 0 The neighbors of the destination receive this information process it and send their own updates Distances propagate throughout the network Spring 2003 UCSC cmpe150 15 Notation D ijk D D l i j i jk D kj i k k i k i successor for j s lki i j D jp j p D q j q Node i must compute the shortest distance to j which we show to be through neighbor k Spring 2003 UCSC cmpe150 16 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 17 DBF D ijk D D l i j i jk i k i The next hop for j is a neighbor that provides the minimum distance according to the Bellman Ford equation D kj i k k s ij l ki D jp j p D q j q i Router I computes D j every time it receives an input event link change or update message and sends an update message to its neighbors D ij is computed with the Bellman Ford Equation D ij Min D ijp l ip p N i Spring 2003 UCSC cmpe150 18 Example of DBF Operation For simplicity we will assume synchronous operation in all cases d 4 1 3 1 c b 2 1 a 1 1 j 0 1 2 3 4 1 2 3 4 time Spring 2003 UCSC cmpe150 19 Counting to Infinity in DBF The problem with DBF is that it does not have a termination detection mechanism d 4 3 c b 2 a X 1 j 3 2 1 4 5 6 5 6 6 7 4 3 1 7 5 5 7 7 6 etc Spring 2003 UCSC cmpe150 time 20 Correctness of DBF Note that BF converges because H is finite 1 Step 1 Initialize …
View Full Document
Unlocking...