Sunday, January 23, 2011

Lesson 38 - OSPF Fundamentals Part1 - Terminology

Open Shortest Path First is the dynamic routing protocol based a link-state algorithm. In the upcoming few posts I will attempt to explain the basics of OSPF operation. Cisco CCNA level of expertise assumes that the candidates know how to implement it in a single area. In my OSPF related posts I will go a bit beyond CCNA requirements but not too much, just enough to help you appreciate this fascinating solution and put OSPF into practice.

Link-state algorithm is faster and more accurate in selecting the best path compared to distance vector approach. The latter algorithm allows routers to know how far the destinations are (distance) and the next-hop router(s) the packets should be sent to (vector). Thus, the routers do not know the topology of the network.

Routers using link-state algorithm create "a map" of the network which allows them to choose paths more accurately. Even though they are more demanding hardware-wise (CPU and RAM memory) they supersede distance vector based solutions.

OSPF Basic Operation
OSPF is a very complex routing protocol but its fundamental operation is quite simple. The steps of operation might be pictured as follows:
  1. Each router sends so called hello packets out of all OSPF-enabled interfaces. This way, the OSPF-enabled router discovers directly connected routers which also run OSPF. If certain parameters in the hello packets match between the neighboring routers, they form the relationship called the adjacency. It is a sort of virtual communication between them. 
  2. Then, each router exchanges special packets called Link State Advertisements (LSAs) with its neighbors (adjacent routers). In OSPF terminology the word link is the same as the interface. LSAs contain details such as: addresses/network masks configured on the links (interfaces running OSPF of course), the metric, the state of the link (which is its relation to the rest of the network), list of neighbors connected to the link.
  3. Each router stores the LSAs in its Link State Database (LSDB). These LSAs are then flooded (advertised) to all OSPF neighbors. As a result of the LSA flooding, all routers in the area have identical LSDBs. An analogy would be having the same road map of a given country which all drivers use. Their journey's starting point is different but the map is still the same.
  4. Each router runs Dijkstra's algorithm to select the best path from this topological database (LSDB). This way, each router creates loop free graph indicating the shortest (best) path to each network/subnet advertised. The best paths end up in the routing table.
OSPF Network Types
OSPF distinguishes between two major types of networks:
  • Transit Networks - Networks which have two or more attached routers. The packets might be originated or passing through this type of network.
  • Stub Networks - Networks which have only one router attached (one exit point). Packets are either originated or destined to these types of networks. A loopback interface is a type of stub network as well. The loopbacks are by default advertised as /32 prefixes ( If you want to advertise loopbacks with their real network mask length, you must change the OSPF mode of operation to point-to-point (presented in the upcoming posts).
More specifically OSPF defines five different types of networks it can operate on. These are:
  • Broadcast - such as Ethernet, Token-Ring
  • Non Broadcast Multiple Access (NBMA) - such as Frame-Relay, ATM, X.25 (they may but do not have to be fully meshed)
  • Point-To-Multipoint - such as Frame-Relay but treated as point-to-point links (Hub and Spoke)
  • Point-to-Point - such as using PPP, HDLC protocols
  • Virtual Links - used in special situations if the OSPF area 0 (backbone area) is partitioned or if an OSPF area cannot be connected to the area 0 directly
There are some differences in OSPF operation, depending on what type of network it runs on. I will explain the relevant details in the upcoming posts. 

OSPF routers will go through multiple states with their neighbors before they are ready to route the packets. Some of them will be used on all type of the networks but others only on specific types of networks listed above. 

OSPF Neighbor State Machine
All possible states between the neighbors are shown in pic. 1. They are also referred to as Neighbor State Machine.

Pic. 1 - OSPF Neighbor States.
Icons designed by: Andrzej Szoblik -

In this state, a router has not heard a hello packet from any OSPF neighbor yet.

This state is applied only on NBMA networks in which the neighbors are not discovered dynamically but must be configured manually ('neighbor' statement in the config-router context).

A router has heard a hello packet from its neighbor(s), which among other parameters the Router IDs of all the neighbors are listed  (look at hello packet structure in the next post).

A router has seen its own Router ID in the hello packet from the neighbor(s). This means that bidirectional communication has been established between the routers.

In this state the master/slave relationship is established necessary to exchange Database Description Packets. Since all the packets have their sequence number allowing routers to detect more recent information, initial numbers are negotiated in this state. The router with the highest Router ID becomes the master.

The routers will send Database Description packets (description of the LDSB). Link State Request packets to request more recent LSAs are also sent in this state.

The Link State Request packets are sent to neighbors in the loading state. They request more recent LSAs discovered in the Exchange state. Link State Updates are sent in response to LSRs.

OSPF neighbors are fully adjacent. All information about networks/subnets have been exchanged and acknowledged. 

OSPF Packet Types
In the Neighbor State Machine description, a few types of OSPF packets were mentioned. OSPF uses five types of packets for communication. Take a look at them (pic. 2):

Pic. 2 - OSPF Packet Types.
Icons designed by: Andrzej Szoblik -

Type 1 - Hello
This packet type is used to discover neighbors and maintain the adjacencies between them. More details regarding a hello packet will be presented in the next post.

Type 2 - Database Description
It is used to describe the LSAs so that the receiving router (neighbor) can determine if all LSAs have been synchronized between them (all routers in the area must have the same LSDB). It is accomplished by exchanging the headers of LSAs (Database Description packets aka DD packets) with the neighbor(s). The receiving router will check if it has a match for all LSAs in its local database. If not, LSR packets are sent to retrieve the missing LSAs.

Type 3 - Link State Request
During the exchange state the router creates a list of all missing or older LSAs in the so called Link State Request List. Then, it sends one or more LSR packets asking the neighbor for the copy of all these LSAs.

Type 4 - Link State Update
It is the response to LSR packets. Contains one or more LSAs which are sent to the neighbor which sent LSR. Upon receiving them the router is flooding them to all its neighbors in order to maintain the same LSDB within the OSPF area.

Type 5 - Link State Acknowledgment
Each LSA the router receives must be acknowledged in order to synchronize the LSDB with neighbors reliably. This packet is used to acknowledge the reception of all LSAs.

This lesson's terminology should make it easier for you to understand some details of OSPF operation presented in the upcoming lessons.

In my next post, I will focus in on the process of building adjacency between OSPF routers.

Saturday, January 15, 2011

Lesson 37 - Routing Information Protocol Part3

First, I would like to thank all of you who took the time to read my posts and left some comment. Your feedback means a lot to me and helps me keep up with this little project of mine. I really appreciate it. Thanks a million folks!

In this post, I'm going to finish the RIP fundamentals by showing you RIPv2 in action. After reading this, you will see the major differences presented in the lesson 35 (table1) in practice. Also, I want to present the authentication of RIP packets which protects the RIP domain from being poisoned with false routes.

I'm going to use the same topology diagram as in previous lessons. Currently, the routers are running RIPv1. If you read my previous post, you saw the routing problems we ran into as RIPv1 does not advertise network masks along with IP addresses. The rules for sending and receiving updates are explained in lesson 36.

Pic. 1 - Topology Diagram.
Icons designed by: Andrzej Szoblik -

As you remember, the subnets: and have not been advertised by RIPv1. There are a few solutions to this problem, but none of them can be resolved using RIPv1. The simplest solution is to use RIPv2 which is classless routing protocol.

Our current RIPv1 configuration looks like this (here: R1 given as and example).

Pic. 2 - R1's RIPv1 configuration

Now, let's enable RIPv2. Below is an example of R1's configuration. The two highlighted commands are now added on all routers in the topology.

R1 configuration:
R1#configure terminal
R1(config)#router rip
R1(config-router)#version 2
R1(config-router)#no auto-summary
R1(config-router)#passive-interface loopback1
  • version 2 - Enables RIPv2.
  • no auto-summary - Disables automatic summarization to a class boundary.
Technically, the 'no auto-summary' command is not necessary in this topology, but it will not do any harm. If a router has interfaces configured with IP subnets belonging to different IP classes, this command becomes mandatory if you want to advertise these subnets with their original network masks.

If you display the running configuration of R1, it is going to look like the one below :

Pic. 3 - R1's RIPv2 Configuration.
Now, let's look at the output of 'show ip protocols' on R3. You can compare it with RIPv1 output in the previous post (lesson 36).

Notice, the 'send and receive version'. Only RIPv2 updates will be sent and accepted now. Also, 'Automatic network summarization is not in effect' tells us that 'no auto-summary' command has been used. Also, both loopback interfaces are listed as 'Passive interface(s)'.

Pic. 4 - RIPv2 Information on R3.
It is also a good idea to see RIPv2 advertisements. Again, be careful using 'debug' commands. For better output, I have also disabled the time stamps:

R3 Configuration:
R3#configure terminal
R3(config)#no service timestamps

Extreme care must be taken when using any debug commands on the production equipment. After the diagnostics have been completed, the debug command(s) must be turned off immediately.
All 'debug' commands are VERY dangerous if used on the production routers. They have enormous impact on the CPU and can potentially crash the device. They are typically used as the commands of the last resort during troubleshooting of a given technology when problem cannot be resolved without data they provide. So we tend to use them only in situations when we cannot do any more damage than there has already been done :-).

Pic. 5 - RIPv2 Debug Output on R3.
What are the major differences compared to RIPv1 output in the previous lesson?
  1. Sending and receiving update using version 2.
  2. Received networks/subnets via mean that the advertising router (here: is the best gateway to the given destination.
  3. Sending v2 update uses reserved multicast destination IP address rather than broadcast.
Authentication of RIP Packets
Almost all routing protocols allow to authenticate their packets. This is an extra security mechanism used to protect your routing domain. It is easy to install a routing protocol on a computer and poison the routing domain with illegitimate prefixes. This can disrupt the operation of the whole routing domain.

RIP offers two ways of authenticating their packets:
  1. Simple Password (clear text) authentication.
  2. MD5 based (one-way algorithm) authentication.
Here, I am going to show the more secure one based on well know hashing algorithm called Message Digest 5.

There are three major steps to configure authentication in RIP:
  1. Configure a key chain - It allows to create multiple keys which can be changed automatically if the routers have the time synchronized. The name of the key chain does NOT have to be identical on all routers.
  2. Configure at least one key-string (password) in the key chain - Key number MUST be identical on all routers in the RIP domain. Also, the password (key-string) used for authentication must be identical on all routers.
  3. Apply the key chain - You must apply the key chain on the interfaces where RIP advertisements will be exchanged between the neighbors.

This configuration must be identical on all routers in the RIP domain. Here, I present the configuration on R3.

Step 1
Create a key chain. The name of the key chain (here: RIP).

R3#configure terminal
R3(config)#key chain RIP

Step 2
Configure at least one key-string (password) in the key chain (must be identical on all routers). I do not use additional options allowing the key-string to timeout. The password used is valid forever.

R3(config-keychain)#key 1
R3(config-keychain-key)#key-string secret123

Step 3
Apply the key chain on the appropriate interface(s). Here the packets must be authenticated between R1 and R2 routers so interface F1/0 will use the key chain.

R3(config)#interface f1/0
R3(config-if)#ip rip authentication mode md5
R3(config-if)#ip rip authentication key-chain RIP

If you display information about RIP again, you will notice that authentication of RIP packets has been enabled.

Pic. 6 - RIPv2 Authentication.
If neighbors (R1 and R2) do not sign their packets using the same key number and key-string, R3 is going to reject their advertisements. Both R1 and R2 send their update without authentication. The result is that R3 must ignore them.

Check it out:

Pic. 7 - Invalid Authentication.

Once I have configured identical authentication on all routers, here is the debug output showing that R1 is sending RIP packets with proper authentication.

Pic. 8 - Authenticated RIPv2 Update from R1.

In the next post, I will start exploration of, arguably, the most commonly used routing protocol OSPF.

Friday, January 7, 2011

Lesson 36 - Routing Information Protocol Part2

In this post I'm going to reinforce all the theory discussed in the two previous posts. But I would like to make it more practical this time. This should help you understand RIPv1 better and hone your skills regarding its implementation. RIPv1 is a good prelude to learning RIPv2 as well since the verification commands are identical for both versions of the protocol. I will finish this lesson off by showing you one quick optimization technique used often with both versions of RIP.

Our topology diagram remains the same.

Pic. 1 - Topology Diagram.

Icons designed by: Andrzej Szoblik -

In my previous post I enabled RIP protocol on all the routers and interfaces in the topology presented. Now is the time to verify its operation.

The first RIP verification command I'd like to introduce is the powerful: 'show ip protocols'. It provides information about which dynamic routing protocols are enabled on a router, if any, also displaying specific information about them (here's RIPv1 information).
Pic. 2 - The 'show ip protocols' output on R1.

Get familiar with the output and pay a special attention to the highlighted pieces of information. The output shows us the following (pic.2):
  • Outgoing/incoming filter list - currently, there are no filters applied to updates being sent or received (more on ACLs which are used to do filtering in the upcoming posts).
  • Sending updates - RIP is advertising its routing table every 30 seconds and the next update is going to be sent in 16 seconds.
  • Invalid after - The routing entry is invalidated (can no longer be used) if it is not refreshed by neighbor(s) in 180 seconds.
  • hold down - If the router receives a 'route-poison' message from the neighbor(s), it still does not trust it entirely for another 180 seconds (it is possibly down). After that period of time it invalidates the prefix. Meanwhile, the router keeps sending packets to the destination marked as possibly down like everything is 'a-ok'.
  • flushed after  - The routing entry is removed from the routing table after 240 seconds if not refreshed by the neighbor(s).
  • Default version control - the router is advertising version 1 updates, but able to accept updates from both RIPv1 and RIPv2 enabled routers.
  • Automatic Summarization - Automatic summarization is enabled (more on this in 'RIP rules' section later in the post).
  • Maximum paths - currently the router can use up to 4 equal cost path (metric identical) to a given destination (configurable: up to 16 in most IOS versions as of writing this post).
  • Routing for networks - the router has interfaces in class B networks.
  • Routing Information Sources - neighboring router's addresses which the router heard from. The time shows when was the last time R1 received the advertisement from its neighbors (e.g. neighbor sent its update to R1 8 seconds ago). This timer should never show you more than 30 seconds under normal circumstances. If the last update from a neighbor arrived longer than 30 seconds ago, it means that the either the neighbor stopped sending its updates or they do not get through.
As you recall, the 'network' statement we used to enable RIP on the interfaces takes a classful IP address as its argument (like explained in the previous post). There is no other additional keyword available for RIP (others protocols use wildcard mask to accomplish this). In case your router has multiple interfaces configured as subnets of the same major network, they all are going to participate in the RIP domain.

For instance, if on R1 I wanted to enable RIP protocol on S0/2 interface only, with my addressing scheme it is not possible. All interfaces are subnets of the same class B major network ( and will be automatically encompassed in RIP process. If you try to outsmart it and use the following classless statement, it will be accepted by IOS syntax rules but the resulting configuration is going to look like shown in pic. 3 anyway.

Configuration attempting to enable RIP on S0/2 only:

R1(config)#router rip

Resulting is the following running configuration:

Pic. 3 - RIP's classless statement result.
Of course, it is possible to filter out what is going to be advertised or which updates are going to be accepted by the RIP process. This however is beyond the scope of this lesson as you do not know necessary tools to accomplish that yet.

Another command that you may find useful if you want to see what is currently in the RIP database is the following:

Pic. 4 - RIP Database.
The best entries in the RIP database (normal route selection process applies) are going to populate the routing table. You already know the command 'show ip route' which displays the full routing table including connected and static routes as well. But you can also try to display RIP routing entries only rather than the whole routing table. Here's your command:

Pic. 5 - RIP Routing Table.

The routing table contains two class C network addresses advertised by R4 and R5 respectively:
Also, it tells us that the R1 has seven subnets of class B network. Hang on a second! We can only see three of them listed in pic. 5:
Where are the remaining four subnets?
Take a closer look at pic. 4 which shows the whole RIP database. Can you see the missing four subnets now? In case you can't spot them in pic. 4 look at the following one (pic. 6) which shows all seven of them. For clarity, I have removed class C networks and highlighted the subnets in question.

Pic. 6 - R1's RIP Subnets.
There are seven subnets of class B network indeed! The RIP database shows them all, but the ones that are directly connected subnets, are not making their way to the routing table. Do you still remember why?

The reason is, of course, related to the route selection process already explained in the previous posts. The router knows them as directly connected subnets with the administrative distance of 1, and the same entries are now in the RIP database (as the 'network' statement encompasses them). Recall that RIP's administrative distance value is: 120. The directly connected networks are always the most preferred ones. That is why, we see them as connected rather than RIP generated entries.

Notice the two entries in the routing table: and They both have two equal cost paths (the same metric) which is correct according to our topology. In that case traffic-sharing (load balancing) is going to occur when packets are sent to these destinations. 

However, R1 has not learned and subnets that should be advertised by R3.

What is the explanation to this?

Let's do some diagnostics on R3 in order to find out what is going on. I'm going to start by checking that RIPv1 has been enabled properly on R3. I want to make sure that the loopback1, loopback2, and F1/0 interfaces participate in the RIP domain (the 'network' statement encompasses them). Here is the result of the test.

Pic. 7 - R3's RIP Information.

It seems that configuration is correct! So, let's take a closer look at what R3 is advertising to their neighbors. In order to see that, we must use 'debug ip rip' command.

Extreme care must be taken when using any debug commands on the production equipment. After the diagnostics have been completed, the debug command(s) must be turned off immediately.
All 'debug' commands are VERY dangerous if used on the production routers. They have enormous impact on the CPU and can potentially crash the device. They are typically used as the commands of the last resort during troubleshooting of a given technology when problem cannot be resolved without data they provide. So we tend to use them only in situations when we cannot do any more damage than there has already been done :-).

However, in the lab it is recommended to learn what information can be obtained using 'debug' commands. They help us gain a deeper understanding of a given technology and may be very helpful in troubleshooting.

Since I use the lab equipment (dynamips/dynagen emulator to be accurate), I can safely enable the following debug command to trace the RIP process without any damage to my gear. In practice, it is best if you redirect the output of the debug commands to RAM memory and then copy its content to a text editor for analysis. Here's how you can do this:

Step 1
Make sure that CPU is not heavily utilized first. Enabling 'debug' commands can create high CPU utilization on the production equipment.

R3#show processes cpu

The first line shows the cpu utilization for the last five seconds, one minute and five minutes. If CPU is not very busy you can proceed to step 2.

Step 2
Disable the time stamp service (optionally) to obtain a better output, disable logging to the console and redirect the output to the RAM memory instead.

R3#configure terminal
R3(config)#no service timestamps
R3(config)#no logging console
R3(config)#logging buffered

Step 3
Enable appropriate 'debug' command (here: rip process is being debugged)

R3#debug ip rip

Step 4
Wait a period of time till output is sent to the RAM memory. Nothing will show on a screen as per step 2. Then disable debugging (here, the alias is used which disables debugging of all processes which is the fastest method). You can disable the specific one as well. In case of my debug this could be: 'undebug ip rip', or 'no debug ip rip'.

R3#u all

Step 5
Display the content of the debug from the memory buffer and copy it to a text editor for analysis.

R3#show logging

Step 6
Bring back the previous settings (logging to the console and time stamps).

R3#configure terminal
R3(config)#no logging buffered
R3(config)#logging console
R3(config)#service timestamps

For clarity's sake, I have broken the output of 'debug ip rip' into pieces so it is easier for us to analyze the information it provides. In practice, either you learn how to properly interpret the output the way it is presented to you by the system or you can rearrange the output in a text editor.

The first debug output (pic. 8) illustrates what R3 is advertising out its Loopback1 interface. It's worth mentioning, that RIPv1 uses broadcast address ( to announce networks/subnets as explained in lesson 35. RIPv2 will use the multicast address

Pic. 8 - R3's Update out Loopback 1.

Next output (pic. 9) shows what R3 is announcing out its Loopback2 interface. Both loopback interfaces are enabled in RIP so, naturally, the updates are sent out these interfaces. Take a look at the output and analyse both (pic. 8 and pic. 9) comparing them with the topology diagram (pic. 1).

Pic. 9 - R3's Update out Loopback 2.

Finally, what we have waited for is the answer to the question why R1 and R2 do not receive the subnets /28 from R3. Look at the below picture (pic. 10).

Pic. 10 - R3's update out F1/0.

Suprisingly, R3 does NOT advertise ANYTHING out towards R1 and R2 (out F1/0 interface). We understand, that R3 will not advertise out F1/0 what has been learned on this interface (split-horizon). But why does it not advertise both subnets configured on the loopback interfaces ( and

The answer is the rules used in RIP in terms of sending and receiving updates.
However, before I'll show you all the rules RIP uses, let's finish our diagnostics and look at what R3 is receiving from one of its neighbors R2 (pic. 11). Notice, that the update R3 receives from R2 does NOT contain network mask, only metric (hop-count) like explained in the previous lesson.

Pic. 11 - R2 Advertisement for R1 and R3.

RIPv1 Sending and Receiving Updates Rules
Now, let me show you the update rules RIP uses which should clarify its behavior shown in this lesson.

Pic. 12 - RIP Rules for Sending Updates.
Clearly, according to pic.12, R3 will not advertise /28 subnets since the egress interface (F1/0) DOES belong to the same major B network, but the network mask on this interface is NOT the same as the subnets being advertised. Egress interface uses /24, whereas the subnet candidates for advertisement use /28.

The only way to resolve this issue is to either re-address the subnets according to what is allowed in RIPv1 or use RIPv2 instead.

As for the receiving updates in RIP protocol, the rules look as follows:

Pic. 13 - RIP Rules for Receiving Updates.

Passive Interface in RIP Protocol

You may have noticed that updates are sent out of all interfaces enabled for RIP. Otherwise routing would not work properly.

But what if there is no router listening to these advertisements? A router can be connected to networks with no other routers in them. They must be advertised out other interfaces still. In such situation it is a waste of the bandwidth to send RIP advertisements every 30 seconds if no router listens to them.

The solution is to use the 'passive-interface' command under the RIP process. When used with RIP protocol, the command will prevent a router from sending advertisements out the passive interface, but the subnet/network address of this interface is going to be included in the updates sent out other interfaces. Also, passive interface in RIP is capable of receiving updates and processing them.

Be careful with making the interface 'passive' while using other routing protocol than RIP. The behavior of the same command will be different. In OSPF or EIGRP routing protocols, the 'passive-interface' command prevents these protocols from sending 'hello' packets which has serious implications. More on that in the upcoming posts.

As an example, in order to stop sending advertisements out R3's loopback interfaces, the configuration will look like the one shown below:

R3#configure terminal
R3(config)#router rip
R3(config-router)#passive-interface loopback1
R3(config-router)#passive-interface loopback2

This configuration optimizes RIP operation preventing it from sending its periodic advertisements out of both loopback interfaces.

Of course, in large systems using RIP is not a common solution. Those who have no other choice, would definitely choose RIPv2 rather than RIPv1. And this is going to be the topic of my next post which finalizes the discussion of RIP fundamentals.

Post Questions and Answers

As per request (look at comments below), I decided to post the explanation for the two very interesting scenarios I received from some anonymous person (forgive me but I did not see your name in the post).

First take a look at the picture below.

Pic. 14 - RIPv1 Scenarios.

Example 1
Notice that in RIPv1 auto-summarization to the class boundary is always in effect.
Also, notice that the update does NOT contain a network mask.

R1 receives two RIPv1 updates:
  • from R2.
  • from R3.

The result is as per the rules explain above (pic. 13). R1 is going to have only one RIP prefix which is in its routing table. This is because the rule for receiving update is asking the following question (pic. 13):

Do any subnets of the same major class exist in the routing table?

Yes! subnet exists, that is why which is less specific (major class) is IGNORED.

Example 2
Notice that in RIPv1 auto-summarization to the class boundary is always in effect.
Also, notice that the update does NOT contain a network mask.

R1 receives the SAME prefix on two different interfaces F1/0 ( and S0/1 (
If the metric is the same, R1 considers both paths: via F1/0 and S0/1 as equal cost paths and performs a load balance.

I hope that clarifies these two corner case scenarios!