Transcription
Chapter 13Routing Protocols(RIP, OSPF, BGP) INTERIOR AND EXTERIOR ROUTINGRIPOSPFBGP1 The McGraw-Hill Companies, Inc., 20001 Adapted for use at JMU by Mohamed Aboutabl, 2003
Introduction Packets may pass through several networks on their way todestinationEach network carries a price tag, or a “metric”The metric of a network may be: constant (i.e. each network costs one hop) Service type-dependent (the cost of the network depends onwhat service the packet needs: e.g. throughput, delay, . etc.) Policy-dependent: a policy defines what paths should, or shouldnot, be followed.The router uses a “routing table” to determine the path Static vs. Dynamic routing tables.2 The McGraw-Hill Companies, Inc., 20002 Adapted for use at JMU by Mohamed Aboutabl, 2003
13.1 Interior & Exterior RoutingAutonomous system:a group of networks and routers under authority of a single administrator3 The McGraw-Hill Companies, Inc., 20003 Adapted for use at JMU by Mohamed Aboutabl, 2003
Popular routing protocols4 The McGraw-Hill Companies, Inc., 20004 Adapted for use at JMU by Mohamed Aboutabl, 2003
13.2 RIP: Routing Information Protocol Distance Vector Routing Share the most you know about the entire autonomous system Share with all your direct neighbors, and them only Share periodically, e.g. every 30 secondsDestinationHop CountNext .0.04200.5.1.6Other Info5 The McGraw-Hill Companies, Inc., 20005 Adapted for use at JMU by Mohamed Aboutabl, 2003
RIP Updating AlgorithmReceive: a response RIP message1. Add one to the hop count for each advertised destination2. Repeat for each advertised destination If ( destination is not in my routing table) Add the destination to my table Else If ( next-hop field is the same) Replace existing entry with the new advertised one Else if (advertised hop-count –after incrementing- is smaller) Replace existing entry with the new advertised one6 The McGraw-Hill Companies, Inc., 20006 Adapted for use at JMU by Mohamed Aboutabl, 2003
Example of updating a routing tableReceive: a response RIP message1.Add one to the hop count for each advertised destination2.Repeat for each advertised destination If ( destination is not in my routing table) Add the destination to my table Else If ( next-hop field is the same) Replace existing entry with the new advertised one Else if (advertised hop-count –after incrementing- issmaller) Replace existing entry with the new advertised one7 The McGraw-Hill Companies, Inc., 20007 Adapted for use at JMU by Mohamed Aboutabl, 2003
Initial routing tables in a small autonomous system Configuration File Directly attachednetworks Hop-count 18 The McGraw-Hill Companies, Inc., 20008 Adapted for use at JMU by Mohamed Aboutabl, 2003
Final routing tables for the previous autonomous system RIP messages areexchangedRouting tables areupdated9 The McGraw-Hill Companies, Inc., 20009 Adapted for use at JMU by Mohamed Aboutabl, 2003
RIP message format1: Request2: ResponseAddress FamilyIdentifier2: TCP/IP family1 or 212 Bytesup to25AFIsHops fromadvertising routerto dest. network10 The McGraw-Hill Companies, Inc., 200010 Adapted for use at JMU by Mohamed Aboutabl, 2003
RIP Request Messages Sent by a router when booted, or when an entry times-outMay request updates for ALL networks, or specific one(s)RIP Response Messages Solicited responding to a previous requestUnsolicited (sent periodically to all neighbors)11 The McGraw-Hill Companies, Inc., 200011 Adapted for use at JMU by Mohamed Aboutabl, 2003
Example 1What is the periodic response sent byrouter R1? Assume R1 knows aboutthe whole autonomous system.12 The McGraw-Hill Companies, Inc., 200012 Adapted for use at JMU by Mohamed Aboutabl, 2003
RIP Timers Periodic Timer ( 25 random 35): controls advertising of updatemessages. There ONE such timerExpiration Timers: governs route validity. Reset upon receipt of anupdate. If it ever expires, destination is considered unreachable. Yet, entry is not removed from table, it continues to be advertisedwith hop count 16 ( i.e. infinity)Garbage Collection Timers: Reset to 120sec when a route isinvalidated. If it expires, the route entry is completely removed fromrouting table13 The McGraw-Hill Companies, Inc., 200013 Adapted for use at JMU by Mohamed Aboutabl, 2003
Example 2A routing table has 20 entries. It does not receive information about five routesfor 200 seconds. How many timers are running at this time?SolutionThe timers are listed below:Periodic timer: 1Expiration timer: 20 - 5 15Garbage collection timer: 514 The McGraw-Hill Companies, Inc., 200014 Adapted for use at JMU by Mohamed Aboutabl, 2003
RIP Problems: 1) Slow convergence Network topology changes propagate slowly (avg. 15 sec per hop)Solution: Limit the diameter of an autonomous system to 15 hops.15 The McGraw-Hill Companies, Inc., 200015 Adapted for use at JMU by Mohamed Aboutabl, 2003
RIP Problems: 2) Instability Net1 is disconnected fromRouter ARouter A updates its hopcount to 16Router A waits for 30seconds before sending itadvertisementRouter B advertises Net1(with hop-count 2) to Abefore A has a chance toadvertise that Net1 isdisconnectedA is fooled and sets itsHop-count to 2 1 316 The McGraw-Hill Companies, Inc., 200016 Adapted for use at JMU by Mohamed Aboutabl, 2003
Remedies for RIP Instability Triggered Update: Send an immediate update (with hop count 16) whenever anetwork becomes unreachable, otherwise send periodic updates.Split Horizons: Never sent same information back to the interface it came from17 The McGraw-Hill Companies, Inc., 200017 Adapted for use at JMU by Mohamed Aboutabl, 2003
Remedies for RIP Instability: Poison reverse A variation of Split Horizon.18 The McGraw-Hill Companies, Inc., 200018 Adapted for use at JMU by Mohamed Aboutabl, 2003
RIP-v2 Format: Same length as in RIP-v1 ASnumberRIP version 2 supports CIDR.RIP messages are encapsulated in a UDP datagramRIP uses the services of UDP on well-known port 520.or prefixuseful if 2AS share abackbonenetwork19 The McGraw-Hill Companies, Inc., 200019 Adapted for use at JMU by Mohamed Aboutabl, 2003
Authentication Protect against unauthorized advertisementFirst entry (with family type FFFF) is used for authontication20 The McGraw-Hill Companies, Inc., 200020 Adapted for use at JMU by Mohamed Aboutabl, 2003
3 The McGraw-Hill Companies, Inc., 2000 Adapted for use at JMU by 3 Mohamed Aboutabl, 200
