1Forouzan, 3rd ed., Chapter 14Routing Protocols(RIP, OSPF, BGP)2CONTENTSCONTENTS• INTERIOR AND EXTERIOR ROUTING• RIP• OSPF• BGP3INTERIORANDEXTERIORROUTING14.14.114Figure 14-2Popular routing protocols5Figure 14-1Autonomous systems6Routing ProtocolsRouting Function 1) Routing Protocols 2) Forwarding PacketsExample IP Routing Protocols: RIPV1 Routing information protocols, version 1 RIPV2 Routing information protocols, version 2 OSPF Open shortest path first I-IS-IS Integrated intermediate system to intermediate system BGP-4 Border gateway protocol, version 4 EGP Exterior gateway protocol IGRP Cisco’s interior gateway routing protocol E-IGRP Cisco’s enhanced - IGRPRouting Domain - collection of routers that speaks the same routing protocolRouters exchange information about the relative locations of all reachable destinations ( represented by their associated network numbers along with some metric that is usually distance - sensitive ) in the routing domain.7In an IP routing domain with 4096 active subnetworks there could be as many as 4096entries in the forwarding table oras few as 16,.... or 4 or 1!201.64.0.0/10 may represent 4096 /22 prefixes[11001001 . 01]000000 . 000000 00 . 00000000/10/22212 = 4096Examples of the /22’s are 201 . 64 . 0 . 0/22 201 . 64 . 4 . 0/22 201 . 64 . 8 . 0/22 … 201 . 127 . 252 . 0/228IP addressing is like Russian “Matryoshka” the nesting dolls.Advertising a prefix - a router’s way of saying I know how to reach destinations having this prefixPotential Routing Problems: 1) Black Hole - outage happens and routing tables are not yet updated. 2) Forwarding loops - A loop has been formedNaturally occur as a result of topology change in network Categories of Routing Protocols:-Distance Vector Routing Protocols-Link State Routing Protocols9Distance - Vector Routing Protocols OverviewRIP - Routing Information Protocol Maximum number of routers that may be crossed is 16. Router advertises distances it sees to destinations. Neighbors may add 1 or more to the distance. Updates every 30 seconds.Characteristics: 1. Periodic updates. 2. Limited routing domain size. 3. Advertisements are derived directly from routing table. 4. Advertisements are broadcast (RIPV1) or multicast (RIPV2) onto every LAN wherever the protocol is active. 5. Received updates easily incorporate into local forwarding table. 6. A technique “ Split Horizon” can limit size of routing updates. (Explained later). 7. A technique “ Poison Reverse” can improve convergence time. (Explained later). 8. Triggered updates allow changes to be propagated immediately without waiting up to 30 seconds.10Link State Routing Protocols OverviewInstead of a hop count (distance), link state protocols use a “cost .” Cost is typically inversely proportional to the speed of the link.Example in OSPF open shortest path first the cost = 108 ÷ link speedWhy is shortest path not always best? 100 MBPS 100 MBPS Cost = 1 Cost = 1 10 MBPS Cost = 10BA CLink state routers advertise links they are directly attached to. Each router tags its advertised links withits own router ID so that routers build up link stated databases which list all routers in the routing domain and tells what links each router is attached to.11Routers share link state database using multicast. Only changes to database are transmitted.“Hello” protocol is used to keep track of each other’s presence. If several hello intervals go by withouthearing any hello’s from neighbor know neighbor is down.Routers are fully adjacent when they have detected each other’s presence and synchronized their linkstate databases.Whenever there is a change in the link state database, a router must spread the changed data to all itsfully adjacent peers.On a LAN if every router hears every other router’s hello packets => scaling problem. Instead elect adesignated router (DR).DR on a LAN: Designated router becomes fully adjacent with all other routers. This reduces traffic.OSPF also designates a backup designated router (BDR).12Summary of link state characteristics: 1. Neighbor discovery via a hello protocol 2. Only form adjacencies when two - way connectivity exists 3. Reliable flooding algorithm enables all routers to share a common link state database 4. More flexible metrics 5. Designated router reduces traffic generated by updates13Static Routing AlternativeDynamic routing protocols use the network itself to discover available paths within thenetworkStatic routing is manually configuredStatic routing has no way to “advertise”changes - it is not really a routing protocolExample Command: route add14Routing Information ProtocolRIP is a Distance Vector Routing ProtocolRIP RFC - 1058 oldest best known “Interior ”routing protocol. RIP Version 1 - Lacks ability to work in a variable length subnet mask environment including ClasslessInterDomain Routing environment.RIP Version 2 - Supports VLSM and CIDR RFC - 2453OSPF is the“Preferred” interior gateway routing protocol for the internet according to RFC - 1371.Most RIP routers update every 30 seconds. The entire forwarding table is always transmitted(in default installations)It is possible to send update triggered by a topology change. In default case RIPV1 transmits entireforwarding table out each and every interface using broadcast.15Split Horizon may be used to not include prefixes that were learned from that interface.Poison Reverse may be used to set prefixes learned from an interface to metric of infinity = 16 and the entire tableis transmitted.Router adds one or more to HOP count for each destination prefix it receives. Is possible for network administrator tospecify to add more than one to an interface.Timer keeps track of an updated value. No new update after 3 minutes goes into garbage collection state, which meansadvertised as unreachable with HOP count = 16. After 2 more minutes, removed from forwarding table.Routing policies for example listing valid