Link state Routing Protocol

Link state routing protocol is one of the two protocols (the other is distance vector routing protocol), used in packet switching networks. Link state routing uses the Dijkstra or Shortest Path First (SPF) algorithm. The protocol works as each node makes a connectivity map of the network in the form of a graph that shows where the node connects to which neighboring node. The protocol will then calculate the best logical path to each destination node and adds it to its routing table. Examples of link state routing protocols are OSPF and IS-IS.

The contrast with link state routing and distance vector routing is that link state routing shares only the information about the connectivity with its neighbors, whereas distance vector routing shares the full routing table of the node with its neighbors. Another one is that after the initial exchange of LSAs are made, link state protocols do not exchange information anymore until there is a change in the network topology. However, it will advertise all its LSAs every 30 minutes, whereas distance vector protocols sends full routing table and process it every 30 or 90 seconds. Compared to DV, LS is therefore more bandwidth and resource efficient.

The first process in creating a routing link is that the routers must be neighbors first by forming an adjacency. To form this adjacency, the routers must agree on the area number, the hello and dead timer settings, and stub area and link authentication configuration. All of this must be the same on both sides of the link or this adjacency will not be formed. The default Hello timer is 10 seconds, and the default dead timer is 40 seconds.

To check router's adjacency type the command "#show ip ospf neighbor" or "#show ip ospf interface"

After this adjacency is formed, the routers will send then Link State Updates (LSUs) which contains Link State Advertisements (LSAs). LSA contains e.g. subnet masking information. LSA will be processed by the receiving router and placed into the link state database and the SPF algorithm is applied to this database to create the OSPF routing table.

To see the database type the command: "#show ip ospf database"

LSA contains sequence numbers which will be checked upon arrival on the destination router. This router will then compare its sequence number (from the previous LSA) to the current LSA. There are 3 possible actions that can happen:

1. If the sequence number is the same, the LSA is ignored by the receiving router

2. If the sequence number is lower than the sequence number the router has, than the router will ignore the update and sends the LSU back to the sending router.

3. If the sequence number is higher, the LSA is accepted an will be added to its database. Afterwards, the receiving router will send an LSA acknowledgment back to the sending router. It will the flood that LSA and will run the SPF algorithm to update its own routing table and holds therefore the most updated route.

To config OSPF type the command:
(config)#router ospf
(config-router)#network area
(config-router)#network area

Configure it on both ends of the link and an adjacency should be formed. We can show it using : #show ip ospf neighbor

To see the ospf database: #show ip ospf database

To see the interface running ospf: #show ip ospf interface

-- 3 Januari 2011 --

Passive interface on routing update

Routing update usually updates the nearby routers about the current configuration of a router. There is a way in order not to transmit updates about the status of the router by using passive interface. Passive interface means that the interface will receive the update from other neighboring routers, but will not transmit its routing table configuration.


To apply passive interface use the command:

(config)#router rip // do it on the hub router to be a passive interface
(config-router)#passive-interface

To cancel passive interface then:
(config-router)#no passive-interface

It is possible to send updates to only a specific router neighbor. To do this, the hub router must be set in the passive interface first.
To do this type the command:

(config)#router rip
(config-router)#neighbor // will send the update to the selected neighbor.

To verify this, type the command #show ip route

Routing Table Operation

Routers use their routing tables to determine the outgoing route of the incoming packets. The routing table operation goes as follow in the following order:

1. The route with the longest prefix (or the shortest subnet mask) will be prioritized first, despite of its routing protocol. So if there is a RIP route of 172.10.10.0/28 and an OSPF route of 172.10.10.0/29, it will choose the OSPF route when sending outgoing packets because 172.10.10.0/29 (6 hosts) has a longer prefix and thus more specific hosts than the 172.10.10.0/28 (14 hosts) route.

2. If the route has the same prefix length, it will look for its administrative distance (AD) of the connection to the neighboring routes. Administrative distances are distances that are measured based on the reliability of the connection and routing protocol of one router to the other. Routes with a lower AD are considered more reliable and will be chosen over the other routes with a higher AD number.

For example, directly connected routes are considered very reliable and has therefore an AD=0. RIP routes are considered simple and not so reliable and has therefore an AD=120. OSPF are considered more reliable than RIP and is given an AD=110.

3. If (1) and (2) are the same for multiple routes, the router will look for its metrics according to its table. The metric is the cost of a route to go from the source address to the destination address. Metrics are different from each other's routing protocol.

RIP metrics uses hop counts where the path with the lowest hops of routers is considered as the shortest path. OSPF metric uses cost which is the inversely proportional bandwidth of the current connection and gets prioritized. Lower cost means a faster interface with higher speed and gets prioritized. IGRP uses a composite metric, based on a the composite of bandwidth, delay, load, reliability and max. MTU. By default, IGRP chooses its route based on bandwidth and delay only. Lowest composite metric means better connection and gets prioritized.

4. If (1) to (3) has the same values, then equal-cost load sharing will be applied, where the load will be equally shared between the multiple connections.

In any of the 4 cases above, only the best route is shown on the show ip route command. The alternative route is there when the best route is down, but the alternative route configuration will not be shown in the show ip route command.

To show the IP route type the command:
RX#show ip route

It will show the routing configuration. A B[C/D] via E (optional), F, G
where:
A = type of connection (direct, RIP, IGRP etc)
B = the destination group IP address
C = administrative distance
D = metric
E = next hop inbound interface (not the final destination)
F = length of connection
G = interface connected to

for example:

R 172.10.0.0 [120/5] via 10.20.30.40, 0:02:34, serial0

means that the connection uses RIP routing protocol to the destination 172.10.0.0 with the administrative distance of RIP=120 and the metric of 5 hops. 10.20.30.40 is the inline interface of the next hop and the router is already connected for 2 minutes and 34 seconds. The connection is connected to the serial0 of the router.

-- 6 December 2010 --