Chapter 5

• Dynamic routing protocols


  Purpose: Discovery of remote networks, Maintaining up-to-date routing information, Choosing the best path to destination networks, Ability to find a new best path if current path is no longer available

  
• Types of routing protocols

  • Link-State
  • Distance Vector
  • Path-Vector

  
• Interior Gateway Protocols (IGP)

  • RIP, EIGRP, OSPF, IS-IS
• Exterior Gateway Protocols (EGP)

  Used for routing between Autonomous Systems

  
• BGP


  Exterior Gateway Protocol
• Distance Vector Operation


  1. Router sends and receives routing messages on its interfaces

  2. Router shares routing messages and routing information with other routers that are using the same routing protocol

  3. Routers exchange routing information to learn about remote networks

  4. When a router detects a topology change, the routing protocol can advertise this change to other routers

  
• Link-State Routing Protocols


  • Router uses the link-state information received from other routers to create a topology map and select the best path to all destination networks
  • Do not use periodic updates, only send updates when there is a change in the topology

  
• Classful routing protocols


  Do not send subnet mask information in routing updates, cannot support VLSM and CIDR, create problems in discontiguous networks

  
• Classless routing protocols


  Include subnet mask information in routing updates, support VLSM and CIDR

  
• Classless IPv4 routing protocols

  • RIPv2, EIGRP, OSPF, IS-IS

  
• IPv6 routing protocols are classless

  
• Routing protocol characteristics


  • Convergence speed
  • Scalability
  • Routing algorithm
  • Routing metric
  • Routing updates
  • Routing table size

  
• Routing metric


  Measurable value assigned by the routing protocol to different routes based on the usefulness of that route, used to determine the overall "cost" of a path from source to destination

  
• Routing protocol metrics


  • RIP - Hop count
  • OSPF - Cost based on cumulative bandwidth
  • EIGRP - Bandwidth, delay, load, and reliability

  
• Cold Start


  Router adds directly connected interface IP addresses to its routing table

  
• Network Discovery (Example using RIP: metric = Hop count)


  1. Router sends an update packet with its routing table information out all interfaces

  2. Router receives updates from directly connected routers and adds new information to its routing table

  
• Exchanging the Routing Information (Example using RIP: metric = Hop count)

  1. Routers exchange the next round of periodic updates

  2. Distance vector routing protocols use split horizon to avoid loops

  
• Achieving Convergence (Example using RIP: metric = Hop count)


  1. Network has converged when all routers have complete and accurate information about the entire network

  2. Convergence time is the time it takes routers to share information, calculate best paths, and update routing tables

  
• Distance Vector Technologies


  • Neighbors are routers that share a link and are configured to use the same routing protocol
  • Routers using distance vector routing are not aware of the network topology, only aware of the network addresses of its own interfaces and the remote network addresses it can reach through its neighbors
  • Some distance vector routing protocols (RIPv1 and RIPv2) send periodic updates, others (EIGRP) only send updates when needed

  
• Distance Vector Algorithm


  • Defines the mechanism for sending and receiving routing information, calculating the best paths and installing routes in the routing table, and detecting and reacting to topology changes
  • RIP uses the Bellman-Ford algorithm, EIGRP uses the Diffusing Update Algorithm (DUAL)

  
• Routing Information Protocol (RIP)

  • Easy to configure, routing updates broadcasted (255.255.255.255) every 30 seconds, metric is hop count, 15 hop limit

  
• RIPv2


  • Classless routing protocol - supports VLSM and CIDR, increased efficiency - sends updates to multicast address 224.0.0.9, reduced routing entries - supports manual route summarization, secure - supports authentication

  
• RIPng


  • IPv6 enabled version of RIP, 15 hop limit and administrative distance is 120
• EIGRP replaced IGRP in 1992
• Routing table


  g routes
• Mechanism for detecting and reacting to topology changes

  • RIP uses the Bellman-Ford algorithm as its routing algorithm
  • EIGRP uses the Diffusing Update Algorithm (DUAL) routing algorithm

  
• Distance Vector Routing Protocols

  • Routing Information Protocol (RIP)
  • RIPv2
  • RIPng
  • Enhanced Interior-Gateway Routing Protocol (EIGRP)

  
• RIP


  • Easy to configure
  • Routing updates broadcasted (255.255.255.255) every 30 seconds
  • Metric is hop count
  • 15 hop limit
• RIPv2


  • Classless routing protocol - supports VLSM and CIDR
  • Increased efficiency - sends updates to multicast address 224.0.0.9
  • Reduced routing entries - supports manual route summarization
  • Secure - supports authentication

  
• RIPng


  • IPv6 enabled version of RIP
  • 15 hop limit and administrative distance is 120
• EIGRP


  • Bounded triggered updates - sends updates only to routers that need it
  • Hello keepalive mechanism - Hello messages are periodically exchanged to maintain adjacencies
  • Maintains a topology table - maintains all the routes received from neighbors (not only the best paths) in a topology table
  • Rapid convergence - because it maintains alternate routes
  • Multiple network layer protocol support - uses Protocol Dependent Modules (PDM) to support layer 3 protocols

  
• Link-state routing protocols


  Also known as shortest path first protocols, are built around Edsger Dijkstra's shortest path first (SPF) algorithm

  
• IPv4 Link-State routing protocols


  • Open Shortest Path First (OSPF)
  • Intermediate System-to-Intermediate System (IS-IS)

  
• Dijkstra's algorithm (also known as shortest path first (SPF))


  • Uses accumulated costs along each path, from source to destination
  • Each router determines its own cost to each destination in the topology

  
• SPF Example


  • The table displays the shortest path and the accumulated cost to reach the identified destination networks from the perspective of R4
• Link-State Routing Process


  1. Learn directly connected networks

  2. Use Hello protocol to discover neighbors and form adjacencies

  3. Build link-state packet (LSP) containing link-state information

  4. Flood LSP to all neighbors

  5. Use link-state database and SPF algorithm to construct SPF tree and add best paths to routing table

  
• Link


  A directly connected network

  
• Link-state packet (LSP)


  Contains the link-state information about a router's links

  
• Disadvantages of Link-State protocols

  • Memory Requirements - Link-state protocols require additional memory
  • Processing Requirements - Link-state protocols can require more CPU processing
  • Bandwidth Requirements - The flooding of link-state packets can adversely affect bandwidth
• Using multiple areas can reduce the size of the link-state databases and limit the amount of link-state information flooding