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 16th 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.
|