Routing Protocols

Routing is the process of directing packets from a source node to a destination node on a different network. Getting packets to their next hop requires a router to perform two basic activities: path determination and packet switching.

Path determination: Involves reviewing all paths to a destination network and choosing the optimal route. To determine the optimal route, information is put in a route table, which includes information such as destination network, the next hop, and an associated metric.
Packet switching: Involves changing a packet's physical destination address to that of the next hop (the packet's logical destination and source addresses will stay the same).

Information a Router needs to know to route a packet

Destination address.
Neighbor routers.
Possible routes to all remote networks.
The best route to each network.
How to maintain and verify routing information.

Routers learn about remote networks from neighboring routers or an administrator. The router then builds a routing table that tells how to get to the remote networks. Routes are either directly connected, static, or dynamic. Static routes are entered in by the administrator. Dynamic routes are learned from neighboring routers using routing protocols. In dynamic routing, the routers update each other at set intervals. Changes cause the routers to update all the other routers. If a routers receives a packet with a destination network not in its routing tables, it will discard the packet. To show the IP routing tables on a Cisco router use the show ip route command:

   Router_2#show ip route
   Codes: C - connected, S - static, I - IGRP, R - RIP, M - mobile, B - BGP
          D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area
          N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2
          E1 - OSPF external type 1, E2 - OSPF external type 2, E - EGP
          i - IS-IS, L1 - IS-IS level-1, L2 - IS-IS level-2, * - candidate default
          U - per-user static route, o - ODR


   Gateway of last resort is not set

        172.16.0.0/24 is subnetted, 7 subnets
   C       172.16.30.0 is directly connected, Ethernet0
   C       172.16.40.0 is directly connected, Serial1
   C       172.16.20.0 is directly connected, Serial0
   I       172.16.10.0  [100/1] via 172.16.20.1, 00:00:01, Serial0
   I       172.16.15.0  [100/1] via 172.16.20.1, 00:00:01, Serial0
   I       172.16.55.0  [100/1] via 172.16.40.2, 00:00:14, Serial1
   I       172.16.50.0  [100/1] via 172.16.40.2, 00:00:14, Serial1

Static Routing

The process of manually adding routes in each router's routing table. The administrator configures the destination network, next hop, and appropriate metrics. The route doesn't change until the network administrator changes it.

Advantages

No overhead on router CPU.
No bandwidth usage between links.
Security (only administrator adds routes).

Disadvantages

Administrator must really understand internetwork and how each router is connected.
If a new network is added, administrator must update all routers.
Not practical on large networks as it is time intensive.

Uses syntax of:

   ip route [destination_network] [subnet_mask] [next_hop_address | exit_interface] 
   [administrative_distance] [permanent]

Example of static route

   Router3(config)#ip route 192.168.1.0 255.255.255.0 serial0 permanent

Default Routing

A default route, which will point to a router, can be established to receive and attempt to process all packets for which no route appears in the routing table instead of discarding them. Only used when there is only 1 exit interface on a router. Same as static route with the ip route command, but use 0.0.0.0 0.0.0.0 for the IP network and subnet mask followed by the next hop router's common interface. Have to also use the ip classless command since there aren't any routes in the routing table. ip classless is enabled by default in IOS version 12.

   Router3(config)#ip route 0.0.0.0 0.0.0.0 192.168.10.2
   Router3(config)#ip classless

Dynamic Routing

Dynamic routes adjust to changes within the internetwork environment automatically. When network changes occur, routers begin to converge by recalculating routes and distributing route updates. The route update messages spread through the network, which causes other routers to recalculate their routes. The process continues until all routes have converged. Uses protocols to find and update routes on a routing table. It uses CPU time and consumes bandwidth between links. The routing protocol defines the rules used by the routers when they communicate with each other.

There are two types of routing protocols on internetworks, Interior Gateway Protocol (IGP) and Exterior Gateway Protocol (EGP). IGP is used in networks in the same administrative domain. EGPs are used to communicate between the domains.

Administrative Distances

Used to note the reliability of routing information received on a router from a neighbor router. ADs range from 0-255. 0 is the most trusted and 255 means the route won't be used.

Route Source	Default Distance
Connected interface	0
Static Route	1
EIGRP	90
IGRP	100
OSPF	110
RIP	120
External EIGRP	170
Unknown	255

The Three Classes of Routing Protocols

Distance Vector

Uses the distance to a remote network to find the best path. Each time a packet goes through a router, it is called a hop. The route with the least number of hops is determined to be the best. Examples of DV are RIP and IGRP.

Link State

Typically called shortest path first, each router creates three tables. 1 tracks directly attached neighbors, 1 determines the entire network topology, and 1 is used for routing table. An example of LS is OSPF.

Hybrid

Uses parts of DV and LS. An example is EIGRP.

Distance Vector vs. Link State Routing Protocols
Distance Vector	Link State
Sees the network from its neighbor's perspective.	Sees the entire network from its own perspective.
Distance metrics accumulate from router to router.	Calculates shortest path to other routers.
Route updates occur periodically.	Route updates are event triggered.
Convergence is slow.	Convergence is fast.
Broadcasts entire route table to neighbors.	Broadcasts link status information to all routers.

Link State Routing Protocols

Link state protocols require each router to send the state of its own interfaces to every router in the internetwork. Link state protocols converge more quickly, but they use more of the router's CPU and memory resources. Link state protocols rely on network events to address topology changes in the network. If a router detects a network event (new router or router down), it triggers an update.

Link State Overview

Routers broadcast and receive link state packets to and from other routers via the network. Link state packets contain the status of a router's links or network interfaces.
The router builds a topology database of the network.
The router runs the Shortest Path First (SPF) algorithm against the database and generates a SPF tree of the network with itself as the root of the tree.
The router populates it route table with optimal paths and ports to transmit data through to reach each network.

Link State Problems

CPU and memory usage when maintaining routing tables on large networks. -- This affects the router's ability to move user data packets through the network.
Large amount of network bandwidth used during convergence. -- Affects the amount of bandwidth that is available to users during this time. Occurs with network initialization or when several routers start up.
If one part of the network receives route information before another part, convergence may take longer or SPF trees and route tables may store inaccurate information.

Link State Remedies

Minimize router resource usage by lengthening update frequency or exchanging route summaries.
Coordinate updates with time stamps or sequence numbers.

Distant Vector Routing Protocols

Passes complete routing tables to neighbors. The neighbors integrate the new table with theirs to create their internetwork map, this is how distance vector determines the network topology. Can have multiple links to a network if this occurs the administrative distance is first checked and the one with the lowest administrative distance is used. RIP uses hop count for best path to a network, if it finds multiple links it uses load balancing with a maximum of 6 equal links. However, it doesn't take the bandwidth into consideration and treats all links equally.

Convergence

When routers using routing protocols first startup, they send their routing tables to each other and the time it takes for them to synchronize is called network convergence. RIP has a slow convergence time, which can cause routing loops.

Routing Loops

Occur in part because of slow convergence times. Routers using Distance Vector routing protocols send their routing tables at set intervals. When a router's network goes down, it broadcasts a message that updates its neighbors. The neighboring routers will gradually update their neighbors (convergence). However; if one of the distant routers, who hasn't received the update about the downed network, sends out its normal update packet which states that the downed network is reachable through it, it will create a routing loop. Its path really points to its neighbors who are closer to the downed network and know the network is down, but they will see the downed network as being available through the distant router. They will send the packets destined for the downed network to the distant router who will in turn send the packet along the path that it originally had (to the downed network's neighbors). The neighbor to the downed network knows its connection to the downed network isn't available so it sends the packet to the distant router (thinking that it is a new path) who still believes the original path is available. This will repeat itself continuously; the neighbor sends it to the distant router and the distant router sends it to the neighbor of the downed network who in turn sends it back to the distant router, each thinks that the other has a connected path. This is called counting to infinity.

Solutions to Routing Loops

Maximum Hop Count

DV (RIP) permits hot count of up to 15. So a packet that is caught in a routing loop will only travel 15 hops, on the 16^th the network is deemed unreachable and the packet is discarded.

Split Horizons

Specify that a router can't send information about routes back out the interface they originated from. Won't send old data about downed networks.

Route Poisoning

If a router's connected network goes down, it sets its hop count to unreachable (16 for RIP) for the network. The neighboring router will receive information about the unreachable network and won't try to send packets to it even if it receives outdated data from a distant router.

Hold downs

Prevent regular update messages from reinstating a route that is down. Also prevent router from changing too rapidly by allowing time for the downed network to come backup or the network to stabilize before changing to the next best route. Also tells the router to restrict changes for a specific time period, any changes that would affect recently removed routes. If a router receives an update claiming that a network has gone down, it starts the hold down timer. If it receives an update with a better metric, the timer is removed and packets are passed. However, if an update arrives from a neighbor router before the hold down timer expires and it has a lower metric than the previous route, the timer keeps going. This allows for convergence. Hold downs use triggered updates that are sent immediately to neighboring routers and contains a new routing table.