Network Layer Routing Algorithms / Protocols PDF

Network Layer Routing Algorithms / Protocols Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.  Network Layer Two main functions at the Routers 1.Forwarding 2. Routing e i ff e r e n c...

Network Layer Routing Algorithms / Protocols Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.  Network Layer Two main functions at the Routers 1.Forwarding 2. Routing e i ff e r e n c i s t h e d nd Wh a t r d in g a n f o r w a be t w e e t i n g ? rou Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.  What is forwarding ? Forwarding is a switching action taken by a router when a packet arrives at a port Router ‘switches’ or ‘forwards’ a packet from an input port to an output port, Router forwards based the packet the destination addressbased field on a forwarding table indicated in the packet. which is already created in the router ….now the question is …who McGraw-Hill Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. ©The McGraw-Hill Companies, Inc., 2000  How is the forwarding table created ? This is where ROUTING is used Forwarding tables are created by executing the function called ROUTING This is most intelligent function of the Router. Every router executes a specified distributed algorithm called as Routing algorithm Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2000  The term Routing is slightly confusing. It sounds like sending a packet in a ( best possible) route. No…that is not routing Probably term ROUTING may be replaced with the phrase McGraw-Hill Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. ©The McGraw-Hill Companies, Inc., 2000  ROUTING PROTOCOLS-Basics A routing table can be either static or dynamic. A static table is one with manual entries. A dynamic table is one that is updated automatically when there is a change somewhere in the Internet. A routing protocol is a combination of rules and procedures that lets routers in 22.6 the Internet inform each other of changes. Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.  What is the meaning of Shortest Path ( Best path or Best Route ?) Shortest path can be one or more of the following Geographical Distance METRIC Is a cost assigned for Number of hops passing through a network Efficiency of the routes the total metric of a Bandwidth particular route is equal to the sum of metrics of Mean queue length networks along the route Measured delay Shortest path attributes are and other factors defined in the Routing Communication cost protocols E.g. RIP uses number of hops as the attribute Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 22.7  Popular routing protocols Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 22.8  Distance Vector Routing –Phillosophy 1. Each router estimates the best route to a destination network (subnet) by collecting data from all its neighboring routers 2. Each router shares the estimated best route with all its the neighboring routers. 3. This is a continuous process that happens throughout the network, in a distributed way. Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 22.9  Distance Vector Routing – Basic Principle 1. Each router maintains a table ( VECTOR ) giving best known distance to each destination which line to use to get there 2. Each router exchanges information periodically with the neighbors Each router is assumed to know the ‘distance’ to each of its neighbors Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 22.10  The Concept of Distance Vector Routing Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 22.11 Distance Vector Routing Algorithm – Steps Step# Find out who are all the neighboring routers 1 - by sending A ‘hello’ ( PING) packet and getting the reply from the active neighbors Step# Get the ‘distance vector’ from all the neighbors 2 Step# Use Bellman-Ford equation to find out the 3 updated minimum cost to every destination As a result new ‘distance vector’ is computed Step# Share the new ‘distance vector’ to all the 4 neighbors Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. How is the best route or least cost route is computed ? Simple algorithm Bellman-Ford Equation Define dx(y) := cost of least-cost path from x to y Then dx(y) = min {c(x,v) + dv(y) } v where min is taken over all neighbors v of x Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. Bellman-Ford example 5 Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3 v 3 w u 2 5 B-F equation says: 2 3 1 z 1 x du(z) = min { c(u,v) + dv(z), y 2 c(u,x) + dx(z), 1 c(u,w) + dw(z) } = min {2 + 5, 1 + 3, 5 + 3} = 4 Node that achieves minimum is next hop in shortest path ➜ forwarding table Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 4-14 Distance Vector Algorithm Dx(y) = estimate of least cost from x to y x maintains distance vector Dx = [Dx(y): y є N] node x: knows cost to each neighbor v: c(x,v) maintains its neighbors’ distance vectors. For each neighbor v, x maintains Dv = [Dv(y): y є N ] Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.  Routing Information Protocol [ RIP ] Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 22.16  Routing Information Protocol [ RIP ] – key features RIP is an intra-domain routing protocol Makes use of distance vector routing Destination in a routing table is a network Metric used is number of links ( hop counts) 22.17 Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.  Routing Information Protocol [ RIP ] – key features ‘infinity’ is defined as 16… means any route in the autonomous system cannot have more than 15 hops next-node column defines the address of the router to which the packet is to be sent to reach its destination 22.18 Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.  Link State routing Intra-domain routing protocol 19 Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. McGraw-Hill ©The McGraw-Hill Companies, Inc., 2000  Link State Routing –Phillosophy To main steps in Link state routing algorithm : 1. Each router computes the complete network map ( network topology along with the cost ) to which it belongs to by getting the information ( data) from all the other nodes in the network. 2. Once it has the network topology along with costs, the router computes the shortest path to all the destinations in the network, using one of the shortest path finding algorithms like 22.20 Dijkstra algorithm Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.  Link State Routing Each router does the following 5 steps: 1. Discover its neighbors, learn their network address. 2. Measures the cost to each of its neighbors. 3. Construct a Link State Packet (LSP), telling all it has just learned. 4. Send this packet to all other routers. 5. Compute the shortest path to every other router. Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.  Concept of link state routing Each router has the complete network topology information Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 22.22 Step#1 : Issues / challenges : How does a router compute the complete network topology ? Who gives that information ? that is something interesting…… Every router keeps track of information about its neighbors Broadcasts ( floods ) this information in the form of Link State Packets ( LSP) to all the other routers Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.  Concept of Link State Routing Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 22.24 Figure 22.21 Link state knowledge Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.  Step1:Learning about the Neighbors When a router is booted, it sends a special HELLO packet on each point-to-point line Router on the other end replies telling who it is Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 22.26  Step-2:Measuring Line Cost A special ECHO packet is sent ; Other side sends back immediately Cost / Round trip delay is measured Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 22.27  Step-3:Building Link State Packets Link State Packets are either built periodically or when some event occurs such as a line or neighbor going down or coming back Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 22.28  Step 4: Distributing the Link State Packets ‘Link state packets’ are flooded To keep the flood in check, sequence number is used for each ‘link state packet’ When a new packet comes in , it is checked against the list of packets already seen If it is new, it is forwarded on all lines except the one it arrived on If it is duplicate or old, it is rejected Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 22.29 Figure 21-27 Flooding of A’s LSP Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 22.30 Final step : Shortest Path Finding Dijkstra algorithm It is presumed that students know Dijkstra algorithm while learning some other subjects like ADA Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.