Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 431Chapter 13Routing Protocols(RIP, OSPF, BGP)2CONTENTSCONTENTS• INTERIOR AND EXTERIOR ROUTING• RIP• OSPF• BGP3INTERIORANDEXTERIORROUTING13.113.14Figure 13-1Popular routing protocols5Figure 13-2Autonomous 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 4096 entries in the forwarding table or as 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 this destinationPotential 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 with its own router ID so that routers build up link stated databases which list all routers is 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 without hearing any hello’s from neighbor know neighbor is down.Routers are fully adjacent when they have detected each others presence and synchronized their link state databases.Whenever there is a change in the link state database, a router must spread the changed data to all its fully adjacent peers. On a LAN if every router hears every other routers hello packets => scaling problem. Instead elect a designated router (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 update13Static Routing Alternative Dynamic routing protocols use the network itself to discover available paths within the networkStatic routing is manually configuredStatic routing has no way to “advertise”changes - it is not really a routing protocol Example Command: route add14Routing Information ProtocolRIP is a Distance Vector Routing ProtocolRIP RFC - 1058 oldest best know “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 netword administrator to specify 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 means advertised as unreachable with HOP count = 16. After 2 more minutes, removed from forwarding