OSPF Tutorial

OSPF Definition:

Open Shortest Path First (OSPF), is a routing protocol used to determine the correct route for packets within IP networks. It was designed by the Internet Engineering Task Force to serve as an Interior Gateway Protocol replacing RIP.

Advantages of OSPF:

  1. Changes in an OSPF network are propagated quickly.
  2. OSPF is heirarchical, using area 0 as the top as the heirarchy.
  3. OSPF is a Link State Algorithm.
  4. OSPF supports Variable Length Subnet Masks (VLSM).
  5. OSPF uses multicasting within areas.
  6. After initialization, OSPF only sends updates on routing table sections which have changed, it does not send the entire routing table.
  7. Using areas, OSPF networks can be logically segmented to decrease the size of routing tables. Table size can be further reduced by using route summarization.
  8. OSPF is an open standard, not related to any particular vendor.
Disadvantages of OSPF:
  1. OSPF is very processor intensive.
  2. OSPF maintains multiple copies of routing information, increasing the amount of memory needed.
  3. Using areas, OSPF can be logically segmented (this can be a good thing and a bad thing).
  4. OSPF is not as easy to learn as some other protocols.
  5. In the case where an entire network is running OSPF, and one link within it is "bouncing" every few seconds, OSPF updates would dominate the network by informing every other router every time the link changed state (I've done this).
OSPF routers check the status of other routers on the network by sending a small hello packet at regular intervals. If a router does not respond to the hello packet, it is assumed dead, and routing updates are sent to every other router by using a multicast address.

In the case where there are no network changes, OSPF will use very little bandwidth (only sending hello packets). As soon as there is an outage, however, OSPF will flood the network as the change is sent to every router (and then every router notifies every other router about the change). This system of near silence when possible and flooding when necessary ensures that routing information gets propagated throughout the network as quickly as possible.

It's now time to...

Build an OSPF network, version 1.0

Scenario: Camp Swampy is running out of IP addresses. They have a fully meshed base backbone consisting of five seperate routers, here known as A through E:

Camp Swampy's Base Network Topology

Camp Swampy has been given the Class B network 181.160.0.0. The network uses IGRP as their routing protocol, and they are using an 8 bit subnet mask (255.255.255.0).

Since IGRP does not support VLSM's, Camp Swampy is forced to use an 8 bit mask throughout their entire network. For networks that contain users, this should be acceptable, but for network connections, such as the network that connects A and B, this is a huge waste of IP addresses. We will rebuild their base network using OSPF for one reason only: To free up IP addresses by using Variable Length Subnet Masks.

This means we are going to have to get into binary, just a little...

Pick a class C equivalent network (in other words, pick a number out of the range available in their third octet), and use it for network connections within their base backbone. In this case, lets use 181.160.254.0. We could use a 14 bit subnet mask, 255.255.255.252 (which would only leave two bits for the host part) to get the maximum number of networks out of the 254 subnet, but that only allows two hosts per network. Since the Camp Swampy admin regularly put sniffers and other devices on their network connections, we need to scale the subnet mask back a bit to 13, 255.255.255.248 (leaves three bits for hosts, a total of 6 possible devices on each net).

You can't use the first or last network to connect to hosts, since the first net is always the network address for the ENTIRE network (for instance, you don't see many IP addresses like 181.160.0.1), and the broadcast address for the last subnetted network is also the broadcast address for the ENTIRE network (you don't see many IP addresses like 181.160.255.1 either). Using a 13 bit subnet mask on 181.160.254.0, you get:
Routers Network First Host Address Second Host Address Broadcast
A - B 181.160.254.8 181.160.254.9 181.160.254.10 181.160.254.15
B - C 181.160.254.16 181.160.254.17 181.160.254.18 181.160.254.23
C - D 181.160.254.24 181.160.254.25 181.160.254.26 181.160.254.31
D - E 181.160.254.32 181.160.254.33 181.160.254.34 181.160.254.39
A - C 181.160.254.40 181.160.254.41 181.160.254.42 181.160.254.47
A - D 181.160.254.48 181.160.254.49 181.160.254.50 181.160.254.55
B - D 181.160.254.56 181.160.254.57 181.160.254.58 181.160.254.63
B - E 181.160.254.64 181.160.254.65 181.160.254.66 181.160.254.71
C - E 181.160.254.72 181.160.254.73 181.160.254.74 181.160.254.79
A - E 181.160.254.80 181.160.254.81 181.160.254.82 181.160.254.87
... ... ... ... ...

Here's what is entered on the "A" Router to implement the change to OSPF: 

	A-router# config t
	Enter configuration commands, one per line.  End with CNTL/Z.
	A-router(config)# interface e 0              A - B connection
	A-router(config-if)# ip address 181.160.254.9 255.255.255.248
	A-router(config-if)# exit
	A-router(config)# interface e 1              A - C connection
	A-router(config-if)# ip address 181.160.254.41 255.255.255.248
	A-router(config-if)# exit
	A-router(config)# interface e 2              A - D connection
	A-router(config-if)# ip address 181.160.254.49 255.255.255.248
	A-router(config-if)# exit
	A-router(config)# interface e 3              A - E connection
	A-router(config-if)# ip address 181.160.254.81 255.255.255.248
	A-router(config-if)# exit
	A-router(config)# no router igrp 200   turn off igrp routing
	A-router(config)# router ospf 1      start ospf routing, Autonomous System # 1
	A-router(config)# network 181.160.0.0 0.0.255.255 area 0  entire net is area 0
	A-router(config)# ^Z
	A-router(config)# write               save the configuration
Now, instead of using 181.160.100.0 to connect A-B, 181.160.101.0 to connect B-C, 181.160.102.0 to connect C-D, and so on, you can now make all the base backbone connections using only 181.160.254.0. Ta-da, addresses saved. Still room for growth. You go home a hero.

Well actually...you're back next year, to:

Build an OSPF network, version 2.0

Scenario: Camp Swampy has grown considerably, and so has their network. The base backbone is still the same, but 30 new routers are now hanging off the backbone network. The routing tables are huge. The routers are getting sluggish. Some of them are coughing up hairballs. They want you to reduce the size of the routing tables, and save the world yet again.

Fortunately, OSPF was designed to deal with the very real problem of huge routing tables. Using seperate areas, a network can be logically segmented and the amount of routing information spread throughout the network can be reduced.

Imagine a router that connects a bunch of users together on one side, and has only a single route out to the world on the other side (this device is cleverly called a "one-armed router" by sales droids). Since this router only has one path to send packets out to the world, it really doesn't need to know much about the network, and nothing short of a new connection can convince it to send it's data any other way.

To keep Camp Swampy's backbone routers from getting too much routing data from end-node routers, and to keep the end routers from getting too much information about the entire base, we are going to divide the base network up into six areas:

Camp Swampy's OSPF Areas

Area 0 is the top level of the OSPF heirarchy. All other areas should border area 0 (what I'm saying is, if you build an OSPF network where areas do not border area 0, you're on your own).

Hanging off the backbone routers are other routers, which eventually lead down to the users. From the backbone router down to the user routers is all one area, and OSPF Link State Advertisements will only be sent to routers in that area. This can significantly reduce the size of the routing tables.

The backbone routers are now part of two areas, area 0, and whichever area they support for the users. This makes them border routers in OSPF parlance. OSPF routers are very careful to keep track of where their border router is.

To further reduce the size of routing tables, we will impliment route summarization in version 2.1. Until then, just remember that for route summarization to work correctly, the range of IP addresses assigned within an area must be consecutive. If Area 1 has all the networks from 181.160.16.0 to 181.160.63.0, this can be neatly summarized into one line.

To gain a further understanding of the network:

After several days of debate, here is the IP addressing scheme that Camp Swampy wants to use:
Area IP Address Range Total Possible Hosts
0 181.160.254.0-255 180 *
1 181.160.1-63.0-255 16,000
2 181.160.64-127.0-255 16,000
3 181.160.128-143.0-255 3,800
4 181.160.144-191.0-255 11,900
5 181.160.192-207.0-255 3,800
Free 181.160.208-253.0-255 11,400
* - Remember that hosts are lost here due to the 13 bit subnet.

This keeps our IP numbering scheme contiguous within areas. A better explanation of why we chose these ranges of numbers will be provided in version 2.1.

We are now prepared to move into the user area, and build some more routers. Let's look at one leg of the base network, which connects to one of the tanker squadrons in Area 4:

The C Router to D Router connection is part of the base backbone. We assigned IP addresses to it in version 1.0. There are several routers connected to the D Router, the one we are interested in is Din1. Further off of Din1 is Duser2, which connects several users to the Internet. Please remember that each router has several other network connections, otherwise, the picture doesn't make much sense.

Within the Area 4 network, we will take a Class C equivalent subnet and use it to make networking connections between routers, just like we did with the 181.160.254.0 network for the base backbone. Since the range of addresses for Area 4 is 181.160.144-191.x, we will use 181.160.144.x for network connections.

The subnetting works just like it did for the 181.160.254 net. The first available network is 181.160.144.8. The first available host is 181.160.144.9. Piece o' cake.

At the end of this chain are the users, all connected into the hub via twisted pair. We will assign them the 181.160.186.0 network, with an 8 bit mask (255.255.255.0).

Connection Network Subnet Mask First IP Second IP Broadcast address
C Router - D Router 181.160.254.24 255.255.255.248 181.160.254.25 181.160.254.26 181.160.254.31
D Router - Din1 181.160.144.16 255.255.255.248 181.160.144.17 181.160.144.18 181.160.144.23
Din1 - Duser2 181.160.144.8 255.255.255.248 181.160.144.9 181.160.144.10 181.160.144.15
Duser2 - Users 181.160.186.0 255.255.255.0 181.160.186.1 181.160.186.2 181.160.186.255

I wont show the commands to put these addresses into the routers, it's pretty simple.

As it stands, Link State Advertisements for routers in Area 4 will stay in Area 4. To really maximize OSPF, we need to add route summarization:

Build an OSPF network, version 2.1

OSPF learns which networks it is responsible for when you enter the network command into the router. In version 1.0, we did: 

	router ospf 1
	network 181.160.0.0 0.0.255.255 area 0
Think of this command as saying: Within OSPF Autonomous System 1, 181.160.anything.anything is in area 0.

Well, that's changed now. Now, the border routers need to say: 

	router ospf 1
	network 181.160.254.0 0.0.0.255 area 0
since only 181.160.254.x is used for area 0 network connections.

To tell the border router about which networks are part of area 4, we could enter: 

	router ospf 1
	network 181.160.144.0 0.0.0.255 area 4
	network 181.160.145.0 0.0.0.255 area 4
	network 181.160.146.0 0.0.0.255 area 4
	...
This gets pretty tedious, though. Fortunately we are saved by the fact that the networks within Area 4 are contiguous. We can summarize which routes Area 4 is responsible for by moving the subnet mask up a couple bits. This not only reduces the amount of commands that must be entered on each router, but also reduces the number of networks that are shown in routing tables.

Since route summarization must be done using subnet masks, it might help to look at the IP addresses in binary. Remember that Area 1 was given the 181.160.1.0 to 181.160.63.255 range of addresses: 

	181.160.1.0    in Binary is 10110101.10100000.00000001.00000000

	181.160.63.255 in Binary is 10110101.10100000.00111111.11111111

181.160.63.255 is as high as you can go without changing one of the bits in bold print:

	181.160.64.0   in Binary is 10110101.10100000.01000000.00000000
Therefore, the following command can be entered on the A Router: 
	router ospf 1				Start OSPF
	network 181.160.254.0 0.0.0.255 area 0	All .254 is Area 0
	area 0 range 181.160.254.0 255.255.255.0	
			Summarize into one line in the routing tables
	network 181.160.0.0 0.0.63.255 area 1	
			All 181.160.0.0 through 181.160.63.255
	area 1 range 181.160.0.0 255.255.192.0
			Summarize into one line in the routing table
If we only had four backbone routers, we could use the same mask on each, and the routing table would only be five lines long (one for each area). But, alas, we cannot use the same mask everywhere.

Back to Area 4, which we were working on in version 2.0. It has been assigned the range of addresses from 181.160.144.0 to 181.160.191.255. It takes three lines to summarize this network, using the binary bit in the 16 position for 181.160.144 through 181.160.191 : 

	181.160.144.0   in Binary is 10110101.10100000.10010000.00000000
	181.160.159.0   in Binary is 10110101.10100000.10011111.00000000

	181.160.160.0   in Binary is 10110101.10100000.10100000.00000000
	181.160.175.0   in Binary is 10110101.10100000.10101111.00000000

	181.160.176.0   in Binary is 10110101.10100000.10110000.00000000
	181.160.191.0   in Binary is 10110101.10100000.10111111.00000000
We can now summarize the IP range of addresses on the D Router: 
	router ospf 1			       Don't confuse AS #'s with Areas
	network 181.160.144.0 0.0.15.255 area 1  181.160.144.0 through 181.160.159.255
	area 1 range 181.160.144.0 255.255.240.0 Summarize in the routing table
	network 181.160.160.0 0.0.15.255 area 1  181.160.160.0 through 181.160.175.255
	area 1 range 181.160.160.0 255.255.240.0 Summarize in the routing table
	network 181.160.176.0 0.0.15.255 area 1  181.160.176.0 through 181.160.191.255
	area 1 range 181.160.176.0 255.255.240.0 Summarize in the routing table

To make sure you believe me when I say this is all worth it:

Here's a routing table without summarization:

duser2#sho 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 
       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

Gateway of last resort is not set

     181.160.0.0 is variably subnetted, 4 subnets, 2 masks
C       181.160.144.8 255.255.255.248 is directly connected, Ethernet0/0
O       181.160.144.16 255.255.255.248 
           [110/20] via 181.160.144.10, 00:41:52, Ethernet0/0
O       181.160.144.24 255.255.255.248 
           [110/20] via 181.160.144.10, 00:41:52, Ethernet0/0
O       181.160.144.32 255.255.255.248 
           [110/20] via 181.160.144.10, 00:41:52, Ethernet0/0

	.....

C       181.160.186.0 255.255.255.0 is directly connected, Ethernet0/5
O       181.160.187.0 255.255.255.0 
           [110/20] via 181.160.144.10, 00:41:52, Ethernet0/0
O       181.160.188.0 255.255.255.0 
           [110/20] via 181.160.144.10, 00:41:52, Ethernet0/0
O       181.160.189.0 255.255.255.0 
           [110/20] via 181.160.144.10, 00:41:52, Ethernet0/0

	.....

O IA    181.160.254.8 255.255.255.248 
           [110/1582] via 181.160.144.10, 00:26:54, Ethernet0/0
O IA    181.160.254.24 255.255.255.248 
           [110/1582] via 181.160.144.10, 00:26:54, Ethernet0/0

	.....
and there's much, much more.

Here's a routing table with summarization:

duser2#sho 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 
       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

Gateway of last resort is not set

     181.160.0.0 is variably subnetted, 4 subnets, 2 masks
C       181.160.144.8 255.255.255.248 is directly connected, Ethernet0/0
O       181.160.144.0 255.255.255.0 
           [110/20] via 181.160.144.10, 00:41:52, Ethernet0/0
O IA    181.160.254.0 255.255.255.0 
           [110/1582] via 181.160.144.10, 00:26:54, Ethernet0/0
O IA    181.160.144.0 255.255.240.0 
           [110/1582] via 181.160.144.10, 00:26:54, Ethernet0/0
O IA    181.160.160.0 255.255.240.0 
           [110/1582] via 181.160.144.10, 00:26:54, Ethernet0/0
O IA    181.160.176.0 255.255.240.0 
           [110/1582] via 181.160.144.10, 00:26:54, Ethernet0/0
C       181.160.186.0 255.255.255.0 is directly connected, Ethernet0/5

Well, that's just about it, kids. Here's the router configurations for:

Link State vs. Distance Vector

Distance Vector routing protocols usually send their entire routing table to their nearest neighbors at regular intervals. Those neighbors then filter through the received routing table to learn which direction to send traffic to reach a given network. Distance Vector routing protocols use some sort of distance measurement (metric) to determine the best path.

One of the simplest Distance Vector routing protocols, RIP, uses a hop count to determine which route is best. If one router says that a network is directly connected to it, it will have a smaller hop count than a router two links away. In RIP, routing decisions are based entirely on this hop count.

Other Distance Vector routing protocols, such as IGRP, improve on this by using such factors as bandwidth, current load, dollar cost or reliability as well as hop count to determine the best path.

Link State routing protocols usually send only the parts of the routing table which have changed to every router within their area. Routers using Link State routing protocols maintain a picture of the entire network, and are aware of outages several hops away. The router can then use this knowledge to determine the best route for traffic, and can avoid sending data across the network if that network is down.

Variable Length Subnet Masking

Within an Autonomous System (AS), most routing protocols insist that every network use the same subnet mask. Therefore, if 181.160.187.0, 181.160.188.0, and 181.160.200.0 are all in IGRP Autonomous System #1, they must all agree upon ONE subnet mask, such as 255.255.255.0.

VLSM is simply a feature which allows a single autonomous system to have networks with different subnet masks. If a routing protocol allows VLSM, then you can use a 14 bit subnet mask on network connections (255.255.255.252), a 13 bit subnet mask on others (255.255.255.248), an 8 bit mask for user networks (255.255.255.0), and even a 6 bit mask (255.255.252.0) for networks with up to 1000 users.

Multicast Addresses

Class A networks are identified with a 1 - 127 in the first octet.

Class B networks are identified with a 128 - 191 in the first octet.

Class C networks are identified with a 192 - 223 in the first octet.

Class D networks are identified with a 224 - 239 in the first octet, and are reserved for multicast addresses.

In OSPF, two multicast addresses are used. When an OSPF area is started, one router is elected the Designated Router (DR), and another is made the Backup Designated Router (BDR). The Designated Router tells all the other routers about changes in the network by sending out Link State Advertisements (LSA's) on multicast address 224.0.0.5. When a router notices a change in the network, it sends this information out on 224.0.0.6, the multicast address reserved for the DR and the BDR.

When a new router is added to the net, it announces it's presence to the world by sending out a hello message on 224.0.0.5. If it doesn't get a response, it becomes the new Designated Router. If a Designated Router responds to the hello message, the new router will use 224.0.0.6 from then on to send out LSA's.

Wasted IP addresses

Network protocols that do not support Variable Length Subnet Masks put network administrators in an awkward position. If a standard 8 bit mask is used throughout the Class B network (255.255.255.0), then IP addresses will be wasted on network connections.

For instance, for the network that connects the "A" router to the "B" router (A,B), if it is given 181.160.187.0, it will waste 252 IP addresses.

This leaves 181.160.187.3 through 181.160.187.254 unusable. Since networks part of larger routed networks must be unique, the remaining IP addresses cannot be used elsewhere.

Pelican.Smith@worldnet.att.net
1