Link-State Routing Protocols

{loadposition adposition4}

Link-State Routing Protocols Overview

Link-State Routing protocols are routing protocols whose algorithms calculate the best paths to networks differently than Distance Vector routing protocols. Whereas Distance Vector protocols know routes by measures of distance and vector(direction) as reported by neighboring routers, Link-State routing protocols calculate their network routes by building a complete topology of the entire network area and then calculating the best path from this topology or map of all the interconnected networks.

{loadposition adposition5}There are two link-state routing protocols, OSPF and IS-IS. The Cisco CCNA curriculum covers the Open Shortest Path First or OSPF link-state routing protocol, and the IS-IS routing protocol is part of the CCNP curriculum.

Link-State Characteristics

  • SPF algorithm – Link-State routing protocols are designed around Dijkstra’s Shortest Path First Algorithm (SPF) in which the shortest path from point A to point B is build around a metric of cost.
  • Cost metric – SPF algorithm finds the shortest path based on a metric network link costs. Each router measures the cost of its own directly connected networks or "links." Cost is a measure of the quality of a link based mostly on bandwidth.
  • Hello packets – Link-State routing protocols establish adjacencies with neighboring routers using hello packets.
  • Link State Packets (LSP) – Initial flooding of link-states to all routers in the network.
  • Topology or SPF Tree – Link-State routing protocols build and maintain a complete map or topology of the network area.   {loadposition adposition6}

Link-State Advantages

  • Faster Convergence – Unlike Distance Vector routing protocols which run algorithm calculations before sending updates, Link-State routing protocols send link-state updates to all routers in the network before running route calculations
  • Triggered Updates – Unlike Distance Vector routing protocols (except EIGRP) which send periodic updates at regular intervals, Link-State routing protocols send LSPs during router startup (flooding) and when a link changes states like going up or down. If their are no changes in the network the protocol only sends hello packets to maintain adjacencies.
  • Scalability – Link-State routing protocols support the ability to configure multiple routing "areas" which allows an administrator to segment a routing protocol processes to defined areas which supports the expansion and troubleshooting of much larger networks.

Link-State Disadvantages

  • Greater Processing Requirements – Link-State routing protocols typically demand greater processing power and memory resources from the router.
  • Greater Administrator Knowledge – Link-State routing protocols can demand advanced administrator knowledge to configure and troubleshoot the network area


{loadposition adposition4}

{loadposition adposition9}

Parent and Child Routes


It is beneficial to understand how Cisco routers look-up routes in the routing table. There are various scenarios where the router might behave contrary to expected and by understanding the router’s look-up processes you may be able to identify a problem and apply a quick remedy.

Cisco routers were originally designed to work according to the classful hierarchy of IPv4 networks. Therefore, to understand the Cisco IOS routing table, it helps to maintain the perspective of classful versus classless networking.

Route Types

In the Cisco CCNA you will need to be able to identify the following types of routes in the routing table:

• Level 1 route – is a network route, a default route, or a supernet route. It is also called an ultimate route.

• Level 2 route – is a subnetted route with a greater than classful subnet mask, it is also a called a child route.

• Parent route – is a classful route, but it is not an ulltimate route. A parent route has subnetted child routes. If there are no child routes there is no parent route. Parent routes do not have an exit interface or next hop IP address. A parent route is also called a level 1 route.

• Child route – A child route is a subnetted route, where the subnet mask is greater than the classful subnet mask (eg. /27 versus /24). A child route is a level 2 route.

• Ultimate route – an ultimate route is a route that has an exit interface or a next hop IP address.

• Default Route – also known as a “gateway of last resort,” is a route configured to the /0 network and mask. This route does not have to qualify or “match” the destination network therefore it is a match for all destinations.

• Network Route – is a level one, ultimate route with an exit interface.

Routing Table Behavior

The router can be configured to behave classfully or classlessly, which is a separate issue from the routing protocol and whether or not the routing protocol has the capability to support classless networks. Classless routing behavior is configured by default on the routers and you can verify this by issuing a “show running-config” command. If you wanted to turn classless behavior on you use the ip classless command, the no ip classless command removes classless behavior

     (config)#ip classless

     (config)#no ip classless

The important difference between “ip classless” and “no ip classless” is that with “ip classless” enabled, if the router finds a matching parent route it will search for a match in the child routes and if it does not finding a matching child routes from the subnets that are available in the routing table it will go back and search the Level 1 routes for a possible secondary match like a default route.

Example: In the image above showing a routing table, if the router was to receive a request for it would find a match to the classful parent route of and proceed to search through the child routes. After not finding a match to it would go on looking in the table for a possible match, if a default route was available, like the default static route “S*” above, it would find a suitable match, because the /0 in the subnet mask indicates that no bits in the route’s network address need to match the packet’s destination address in order to have a match.

With “no ip classless” enabled, the router after not finding a matching child route would simply drop the packet. Why would it drop the packet? My personal guess is that “no ip classless” means “classful behavior” and in the world of purely classful network hierarchies, prior to the possibility of discontiguous classless networks, meaning VLSM and CIDR, either you owned the classful network and therefore all of the possible subnets, or you didn’t, so why keep searching the routing table, the destination network couldn’t possibly be anywhere else, so it is dropped.

Note: In Packet Tracer, the global commands “ip classless” and “no ip classless” are not available.

Video Tutorial

Routing Loops


Routing Loops are a risk in networks that utilize an older dynamic routing protocol like RIP. A routing loop is a scenario where data, instead of being routed to its correct destination, is sent from router to router endlessly. This scenario can be caused by routers not receiving updated routing information quickly enough, and as a result, forwarding packets incorrectly and propagating routing information to neighbor routers incorrectly. When every router in the system has the correct routing information the network is said to be converged. Therefore, it is desirable to use a routing protocol that can converge a network quickly and prevent routing loops.

Typically distance vector routing protocols like RIPv1, RIPv2 and IGRP, do not converge networks as quickly as link state routing protocols like OSPF and ISIS, with the EIGRP routing protocol being the exception.

Count-to-inifinity is a RIP routing loop scenario whereby the routes in the routing tables keep increasing their hop-count metric. This is caused by incorrect routing information being propagated on the network.

Distance Vector routing protocols have been designed and improved over the years to minimize the possibility of routing loops. RIP uses the following methods and rules to avoid routing loops and count-to-infinity: split horizon, hold down timers, route poisoning, poison reverse, and TTL values.     

Video Tutorial

Static and Default Routes


It is important to know how to configure static routes on a router. Many networks are small enough that all of the routing can be handled by a few static routes and a default route out of the network. If you want to know a router’s routes you need to look at its routing table. The routing table will show you connected routes, static routes, if there is a default route, and it will also show you if there are any dynamically learned routes too. In this section we will look at connected routes, static routes and default routes.

Connected Routes

Connected routes are routes to networks directly connected to the router. To establish connected routes all you have to do is bring up your router’s interfaces. This means configuring the router’s interfaces with IP addresses and subnet masks and making sure they are not in an administratively shutdown state.

To configure a Fast Ethernet interface from global configuration mode:

R1(config)#interface fastethernet 0/0
R1(config-if)#ip address <your ip address> <your subnet mask>
R1(config-if)#description <your description>
R1(config-if)#no shutdown

To configure a serial interface from global configuration mode. You can first check to see if your interface is the DCE and will need a clock rate:

R1#show controllers serial 0/0

Checking the “show controllers” command results to see If the interface is the DCE, you can see from the output below, that the interface is in fact the DCE, and that the clock rate needs to be set.


R1(config)#interface serial 0/0
R1(config-if)#ip address <your ip address> <your subnet mask>
R1(config-if)#clock rate 64000 (only if the interface is the DCE)
R1(config-if)#description <your description>
R1(config-if)#no shutdown

Now that the interfaces have been brought up you can see the connected routes by looking at the routing table by issuing a “show ip route” command and looking for the lines that start with “c”:

Static Routes

In the picture below, R1 has three connected networks in its routing table but it does not know about the network and therefore cannot route traffic to it. To solve that problem a static route to the network can be configured.

There are two ways of configuring a static route. The first uses the next hop router’s IP address on the connected network:
     R1(config)#ip route <destination network> <subnet mask> <next hop router address>

The second uses the router’s own exit interface. This way is faster for the router because it doesn’t have to first look up the exit interface from the connected network:

R1(config)#ip route <destination network> <subnet mask> <local router exit interface> 

both types of static route commands are listed below:


After the static route has been configured you should be able to verify the static route in the router’s routing table be issuing a #show ip route command and looking for the “s” entry in the routing table. The image below shows the router’s routing table after a static route was configured and the “show ip route” command was executed. Notice the highlighted static route which starts with an “s” in the routing table:
     R1(config)#ip route fa1/0
R1#show ip route

Default Routes

In the diagram below R1 needs a default route or gateway of last resort configured so that it can route traffic to unknown networks across the internet. If R1 does not have a default route, traffic to all unknown networks will be dropped, and surfing the Web will not be possible. To configure a default route you must configure a static route to the network and subnet mask to the next hop router or exit interface which has a path out of the network (see below). The commands to create a default route or gateway of last resort are:

R1(config)#ip route <next hop router IP address>
R1(config)#ip route <exit interface>

Once you have configured a default route it will show up in the routing table as an “s” with an asterisk “*” next to it signifying it as a default route. You can also see from the highlighted areas in the routing table output below that the default route is also acknowledged as the “Gateway of last resort is to network” (see below):

Video Tutorial on Default Routes

In this video I demonstrate configuring a default route using Packet Tracer

Routers and Routing Intro


Some of the ideas that are covered in this section are how Cisco routers are put together, their different types of memory, their various interfaces both LAN and WAN, and their start-up processes? Allso in this section there is a review on how to configure a router, how to bring up its interfaces, and how to issue show commands to read its status. This first part of CCNA 2 also covers in an introductory way the router’s routing table, and static versus dynamic routing.

Router Memory

Similar yet different from a regular computer, the router has different kinds of memory ROM, Flash, NVRAM, and SDRAM which all have different functions:

  • ROM – POST, Bootstrap, and ROMMON
  • Flash – IOS
  • NVRAM – Configuration File
  • SDRAM – Running-Config, Routing Table, IOS (everything is loaded and executed from RAM)

Notice: The router is a computer but it does not have a traditional hard drive to store files and the operating system, this is accomplished in Flash memory and NVRAM memory.

Bootup Process

  1. POSTROM memory,
  2. BootstrapROM memory,
  3. Load the IOS – the router has an ordered routine for loading the IOS

    1. Flash Memory – the IOS is typically loaded from Flash memory
    2. TFTP – if there is no IOS in Flash, the router will search for a network TFTP server,
    3. ROM – if there is no IOS found, the router defaults to a recovery IOS called Rommon,
  4. Load the Startup-Configthe router has an ordered routine for loading the startup-config file

    1. NVRAM memory – the startup-config file is typically loaded from NVRAM memory
    2. TFTP – if there is no config file in NVRAM, the router will search for a network TFTP server,
    3. Setup-Mode – if there is no configuration file found, the router defaults to setup-mode

The Function of the Router

The router’s purpose or function is to find the best path (route) and switch out of the correct interface. The router will make the decision of the “best path” by first determining the destination network, and second by consulting its routing table.

Static Routing and Dynamic Routing

Routers can be configured to route traffic based on static routes that have to be manually entered by an administrator or by dynamic routes that are created dynamically by a routing protocol. Static routing is a good choice for networks that: never change, are small in size or have only one router, or have only one way out of the network. Dynamic routing is a good choice if a network has multiple routers, is part of a larger network, or if the network changes frequently. For instance, in a situation where the network changes, with a dynamic routing protocol if a network goes down, the routers will inform each other automatically through the routing protocol, and the route will be removed from the routing table; with static routing, if a network goes down, an administrator will have to go in and remove the the static route manually.

There is a difference between routed or routable protocols and routing protocols. A routed protocol is a protocol that is routable over multiple networks like the internet. Today the de facto routed protocol is TCP/IP. A routing protocol is a protocol used by routers to share information with each other, specifically information about available routes. Examples of routing protocols would be RIP, EIGRP, OSPF, and ISIS.

For the Cisco CCNA certification exam you will need to know how to configure an interior gateway routing protocol in a multiple router network. You will be required to know the following interior gateway routing protocols: RIPv1, RIPv2, EIGRP, and OSPF.

Routed Protocols
IPX/SPX (Novell – no longer in use)
Apple Talk (Apple – no longer in use)

 Routing Protocols

RIP v1 – interior gateway protocol, IETF – RFC1058, open standard
RIP v2 – interior gateway protocol, IETF, open standard
EIGRP – interior gateway protocol, Cisco proprietary
OSPF – interior gateway protocol, IETF, open standard
ISIS – interior gateway protocol, covered in CCNP
BGP – exterior gateway protocol, covered in CCNP

Interior Gateway Routing Protocol Types
Distance Vector     Link State  

The Routing Table and RIP

A demonstration of reading routing tables and activating the RIP routing protocol