Routing Protocols: IGP, EGP, and Distance Vector

Classifying Routing Protocols

• Dynamic routing protocols discover remote networks.
• Dynamic routing protocols maintain up-to-date routing information.
• Dynamic routing protocols choose the best path to destination networks.
• Dynamic routing protocols find new best paths when the current one is unavailable.
• Types of routing protocols include Link-State, Distance Vector, and Path-Vector.

IGP and EGP Routing Protocols

• Interior Gateway Protocols (IGP) route within an Autonomous System (AS).
• Examples of IGPs include RIP, EIGRP, OSPF, and IS-IS.
• Exterior Gateway Protocols (EGP) route between Autonomous Systems.
• An example of an EGP is BGP.

Distance Vector Fundamentals

• Distance Vector Operation includes sending and receiving routing messages on interfaces.
• Routers share routing messages and information with others using the same protocol.
• Routers exchange routing information to learn about remote networks.
• When a router detects a topology change, the routing protocol advertises this change.

Link-State Routing Protocols

• A Link-State router uses received link-state information.
• A Link-State router creates a topology map and selects the best path to all destination networks in the topology.
• Link-state routing protocols send updates only when there's a topology change.
• OSPF and IS-IS are examples of Link-state routing protocols.

Classful vs Classless Routing Protocols

• Classless routing protocols include subnet mask information in updates.
• Classful routing protocols, do not send subnet mask information in routing updates.
• Classful routing protocols do not support variable-length subnet masks (VLSMs) and classless interdomain routing (CIDR).
• Classful routing protocols can create problems in discontiguous networks.
• Classless IPv4 protocols (RIPv2, EIGRP, OSPF, IS-IS) include subnet mask information in updates.
• Classless routing protocols support VLSM and CIDR.
• IPv6 protocols are classless

Routing Protocol Characteristics

• Routing protocols can be compared based on characteristics such as convergence speed.
• Routing protocols can be compared based on characteristics such as scalability.
• Routing protocols can be compared based on characteristics such as VLSM support.
• RIPv1 and IGRP are not used anymore.

Routing Protocol Metrics

• A metric is a measurable value assigned by the routing protocol for different routes, based on usefulness.
• Routing metrics are for determining the "cost" of a path from source to destination.
• The best path is the route with the lowest cost.
• RIP uses hop count, OSPF uses cost based on bandwidth, and EIGRP uses bandwidth, delay, load and reliability as metrics.

Distance Vector Operation

• Routers send and receive routing messages on their interfaces.
• Routers share messages and routing information using the same routing protocol.
• Routers exchange routing information to learn about remote networks.
• Routing protocols can advertise topology changes too other routers.

Cold Start

• Routers apply saved configuration and discover directly connected networks after booting.
• The router adds any directly connected interface IP addresses to its routing table.

Network Discovery

• If configured, a routing protocol exchanges updates to learn about any remote routes.
• Routers send update packets with routing table information out of all interfaces.
• Routers also receive information from directly connected neighbors and add the information to the routing table.

Exchanging Routing Information

• Routers exchange the next round of periodic updates.
• Distance vector routing protocols use split horizon to avoid loops.
• Split horizon prevents information from being sent out the same interface from which it was received.

Achieving Convergence

• The network has converged when every router has accurate information about the entire network.
• Convergence time is how long it takes to share, calculate, and update routing tables.
• Routing protocols can be rated by convergence speed; the faster, the better.

Distance Vector Technologies

• Neighbors share a link and use the same routing protocol.
• Distance vector routing protocols share updates between neighbors.
• Routers are only aware of their own interfaces' addresses and remote network addresses reach through their neighbors.
• RIPv1 and RIPv2 send periodic updates, while RIPv1 uses 255.255.255.255 broadcasts.
• RIPv2 and EIGRP can use multicast to send updates to specific neighbors, and EIGRP can use a unicast message.
• EIGRP sends updates only when needed.

Distance Vector Algorithm

• Mechanism to send and receive routing information.
• Mechanism to calculate best paths and install routes in the routing table.
• 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 Information Protocol (RIP)

• RIP is easy to configure.
• RIP sends updates (255.255.255.255) every 30 seconds.
• RIP uses hop count as a metric and has a 15 hop limit.
• RIPv2 is a classless routing protocol and supports VLSM and CIDR.
• RIPng is an IPv6 version of RIP with a 15 hop limit and administrative distance of 120.
• RIPv2 is more efficient, using multicast address 224.0.0.9 for updates.
• RIPv2 supports manual summarization/authentication.

Enhanced Interior-Gateway Routing Protocol

• EIGRP replaced IGRP in 1992, and only sends updates to routers that need it.
• EIGRP uses hello messages to maintain adjacencies and uses a topology table that contains all the received routes.
• EIGRP offers rapid convergence using alternate routes and multiple network layer protocol support.

Shortest Path First Protocols (SPF)

• Link-state routing protocols are known as shortest path first protocols.
• They use Edsger Dijkstra's shortest path first algorithm (SPF).
• IPv4 Link-State routing protocols: Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (IS-IS).

Dijkstra's Algorithm

• All link-state protocols apply Dijkstra's algorithm to calculate the best path route.
• 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 shortest path and cost from the perspective of R4.

Link-State Routing Process

• Routers learn about each own's directly connected networks and say hello to neighbors.
• Routers build Link-State Packets (LSP) with the state of each directly connected link.
• Each router floods the LSP to all neighbors, who store all LSP's in a database.
• The LSP data is used to construct a complete topology map and compute the best path to each destination network.
• The process for IPv4 and IPv6 OSPF are the same

Link and Link-State

• The first step in link-state routing is for each router to learns it's own directly connected networks.

Say Hello

• The second step requires each router uses the Hello protocol to see any neighbors on it's links.
• When 2 link-state routers learn they are neighbors, they form an adjacency.
• If a router does not receive Hello packets from a neighbor, it is considered unreachable.

Building the Link-State Packet (LSP)

• The third step is that each router builds a LSP that contains link-state information about it's links.

Flooding the LSP

• The fourth step is that each router floods the LSP to all neighbors.
• An LSP needs to be sent when the router boots or restarts, or when there's a change in the topology
• LSPs need sequence numbers and aging information in order for each router to understand if its already seen something, or what the older/newer data is.

Building the Link-State Database

• Each router constructs a complete topology map and computes the best path to each destination.

Building the SPF Tree

• Each router uses the link-state database and SPF algorithm to build a tree.
• Routers add directly connected networks/costs, as well as any unknown info.
• The Shortest Path First algorithm calculates the shortest paths resulting in the SPF tree.
• Each router makes its own SPF tree, independantly.

Adding OSPF Routes to the Routing Table

• The shortest path information determined by the SPF algorithm is added to the routing table.
• Directly connected and static routes are also included in the routing table.

Advantages of Link-State Routing Protocols

• Each router builds a topological map of the network to determine the shortest path.
• Immediate flooding of LSPs achieves faster convergence, and they are only sent when there is a change.
• Hierarchical design is used when implementing multiple areas.

Disadvantages of Link-State Protocols

• Link-state protocols require additional memory and more CPU processing.
• Flooding of link-state packets can adversely affect bandwidth.
• Using multiple areas can reduce the size of the link-state databases and may limit amount of data sent out.

Protocols that Use Link-State

• Two protocols use Link State: OSPF and IS-IS
• Open Shortest Path First is a popular implementation that has 2 versions: OSPFv2 for IPv4 and OSPFv3 for IPv6.
• Integrated IS-IS includes support for IP networks, and it is used mainly by ISPs and carriers.