Last year I flew from New York to Osaka for a conference. My journey began when I hailed a cab on Broadway in downtown New York. “JFK,” I told the cabbie, telling her my destination was John F. Kennedy Airport. I was still pushing my luggage down the seat so I could pull my door shut when the cab started to move. The cabbie changed lanes twice before I got it shut. I did make it to JFK in one piece, where I presented my ticket and boarded a flight to Osaka. At Osaka Airport, the taxi driver bowed to me as he took my luggage from my hand. Once the luggage was properly stowed, he asked for my destination. “New Otani Hotel,” I told him, and he bowed again and closed my side door.
This everyday story of a passenger in transit illustrates how a traveler is able to complete a journey in spite of the fact that the whereabouts of his destination are not known to every element in the system. The cabbie in New York knows only local destinations and so knows how to get to JFK but not to the New Otani Hotel. The airline routes passengers between major airports. The taxi driver in Osaka also knows only local destinations, so, when returning to New York, I tell the driver that my destination is “Osaka Airport,” not “New York.” Any single element of the transportation system knows only the local geography. This leads to obvious efficiencies: the cabbie in New York needs to know only the New York metropolitan area, and the taxi driver in Osaka needs to know only the area in and around Osaka; the airline is the backbone linking JFK to Osaka.
Much like the transportation system just described, Open Shortest Path First (OSPF) is a hierarchical routing protocol, implying that the IP network has a geography with each area possessing only local routing information. In contrast, RIP and IGRP are flat, implying that there is no hierarchy in the network -- every router possesses routes to every destination in the network. Right away, you can see that a flat routing protocol has inherent inefficiencies -- in our analogy, if the architecture of the transportation system was flat, the cabbie in New York would have to learn directions to the New Otani Hotel.
A hierarchical architecture, whether that of a transportation system or that of OSPF, allows the support of large systems because each area is responsible only for its local routes. RIP and IGRP cannot support very large networks because the routing overhead increases linearly with the size of the network.
Another radical difference from RIP and IGRP is that OSPF is not a DV protocol -- OSPF is based on a Link State algorithm, Dijkstra. What is a Link State algorithm? Link refers to a router interface; in other words, the attached network. State refers to characteristics of the link such as its IP address, subnet mask, cost (or metric), and operational status (up or down). Routers executing OSPF describe the state of their directly connected links in link state advertisement (LSA) packets that are then flooded to all other routers. Using all the LSAs it receives, each router builds a topology of the network. The network topology is described mathematically in the form of a graph.
This topological database is the input to Dijkstra’s Shortest Path First (SPF) algorithm. With itself as the root, each router runs the SPF algorithm to compute the shortest path to each network in the graph. Each router then uses its shortest-path tree to build its routing table. Compare this with DV protocols: DV protocols propagate routes from router to router (this is sometimes called routing by rumor) and each router chooses the best route (to each destination) from all the routes (to that destination) that it hears.
DV protocols have to set up special mechanisms to guard against bad routing information that could propagate from router to router. In contrast, routers running the SPF algorithm need to ensure the accuracy of their LS databases; as long as each router has the correct topology information, it can use the SPF algorithm to find the shortest path.
Dijkstra’s algorithm is a wonderful tool but, as we shall see in more detail later, the SPF algorithm is expensive in terms of CPU utilization. The cost of running the algorithm increases quickly as the network topology grows. This would be a problem but, given OSPF’s hierarchical structure, the network is divided into “small” areas, and the SPF algorithm is executed by each router only on its intra-area topology. So how do routers in two different areas communicate with each other? All areas summarize their routes to a special area called the backbone area or area 0. The backbone area in turn summarizes routes to all attached areas. Hence, traffic between any two areas must pass through the backbone area (see Figure 6-1).
OSPF derives its name from Dijkstra’s SPF algorithm; the prefix “O” signifies that it’s an “open” protocol and so is described in an “open” book that everyone can access. That open book is RFC 2328, thanks to John Moy. In contrast, IGRP and EIGRP are Cisco proprietary protocols. Multiple vendors support OSPF.
Getting RIP, IGRP, and EIGRP running is easy, as we saw in earlier chapters. When TraderMary’s network grew to London, Shannon, Ottawa, etc., the DV routing protocols adapted easily to the additions. Getting OSPF running on a small network is also easy, as we will see in this chapter. However, unlike RIP, IGRP, and EIGRP, OSPF is a hierarchical protocol. OSPF does not work well if the network topology grows as a haphazard mesh.
In this section, we will configure OSPF on a small network. In later sections, we will learn how to build hierarchical OSPF networks.
TraderMary’s network, shown in Figure 6-2, can be configured to run OSPF as follows.
Like RIP and IGRP, OSPF is a distributed protocol that needs to be configured on every router in the network:
hostname NewYork ... interface Ethernet0 ip address 172.16.1.1 255.255.255.0 ! interface Serial0 description New York to Chicago link ip address 172.16.250.1 255.255.255.0 ! interface Serial1 description New York to Ames link 1bandwidth 56ip address 172.16.251.1 255.255.255.0 ...router ospf 10network 172.16.0.0 0.0.255.255 area 0
The router ospf command starts the OSPF process on the router. The syntax of this command is:
router ospf process-idThe process-id , which should be between 1 and 65,535, is used to identify the instance of the OSPF process. The process-id configured in the previous example is 10. Router Chicago is similarly configured with the same process-id:
hostname Chicago ... interface Ethernet0 ip address 172.16.50.1 255.255.255.0 ! interface Serial0 description Chicago to New York link ip address 172.16.250.2 255.255.255.0 ! interface Serial1 description Chicago to Ames link ip address 172.16.252.1 255.255.255.0 ...router ospf 10network 172.16.0.0 0.0.255.255 area 0
Router Ames is also configured with OSPF:
hostname Ames ... interface Ethernet0 ip address 172.16.100.1 255.255.255.0 ! interface Serial0 description Ames to Chicago link ip address 172.16.252.2 255.255.255.0 ! interface Serial1 description Ames to New York link 2bandwidth 56ip address 172.16.251.2 255.255.255.0 ...router ospf 10network 172.16.0.0 0.0.255.255 area 0
We next identify the networks that will be participating in the OSPF process and associate an area ID with each network. The syntax of this command is:
networkaddress wildcard-maskareaarea-id
The address and wildcard-mask fields identify a network by its IP address. Networks that match the address and wildcard-mask fields are associated with the area area-id. How is a network’s IP address matched against address and wildcard-mask?
wildcard-mask is a string of zeros and ones. An occurrence of a zero in wildcard-mask implies that the IP address being checked must exactly match the corresponding bit in address. An occurrence of a one in wildcard-mask implies that the corresponding bit in the IP address field is a “don’t care bit” -- the match is already successful.
Thus, the following clause can be read as stating that the first 16 bits of an IP address must be exactly “172.16” for the address to match the clause and be associated with area and that the next 16 bits of the IP address are “don’t care bits”:
network 172.16.0.0 0.0.255.255 area 0
Any IP address, such as 172.16.x.y, will match
this address/wildcard-mask and be assigned the
area ID of 0. Any other address, such as 10.9.x.y,
will not match this address/wildcard-mask.
If an interface IP address does not match the address/wildcard-mask on a network statement, OSPF will check for a match against the next network statement, if there is another statement. Hence, the order of network statements is important. If an interface IP address does not match the address/wildcard-mask on any network statement, that interface will not participate in OSPF.
There is more than one method of assigning area IDs to networks. The most rigorous method specifically lists every network when making a match. The wildcard mask contains only zeros:
hostname NewYork ...router ospf 10network 172.16.1.1 0.0.0.0 area 0network 172.16.250.1 0.0.0.0 area 0network 172.16.251.1 0.0.0.0 area 0
The most loose method is an all-ones wildcard mask:
hostname NewYork ...router ospf 10network 0.0.0.0 255.255.255.255 area 0
Note that in the second (loose) method, network 192.168.1.1 also belongs to area 0.
If an IP address does not match an area-ID specification, the match continues to the next statement. So, for example, a router may be configured as follows:
network 172.16.0.0 0.0.255.255 area 0 network 192.0.0.0 0.255.255.255 area 1
An IP address of 192.168.1.1 will not match the
first statement. The match will then continue to the next statement.
All IP addresses with “192” in the
first 8 bits will match the second clause and hence will fall into
area 1. A network with the address 10.9.1.1 will
not match either statement and hence will not participate in OSPF.
The area-id
field
is 32 bits in length. You can specify the area ID in
the decimal number system, as we did earlier, or in the
dotted-decimal notation that we use for expressing IP addresses.
Thus, the area ID 0.0.0.0 (in dotted decimal) is
identical to the area ID
(in decimal); the area ID 0.0.0.100 (in dotted
decimal) is identical to 100 (in decimal); and the area ID
0.0.1.0 (in dotted decimal) is identical to 256
(in decimal). The area ID of
is reserved for the backbone area. The area ID for nonbackbone areas
can be in the range 1 to 4,294,967,295 (or, equivalently,
0.0.0.1 to 255.255.255.255).
The show ip ospf interface command shows the assignment of area IDs to network interfaces:
NewYork#sh ip ospf interface ... Ethernet0 is up, line protocol is up 3Internet Address 172.16.1.1/24, Area 04Process ID 10, Router ID 172.16.251.1, Network Type BROADCAST, Cost: 10... Serial0 is up, line protocol is upInternet Address 172.16.250.1/24, Area 0Process ID 10, Router ID 172.16.251.1, Network Type POINT_TO_POINT, Cost: 64 ... Serial1 is up, line protocol is upInternet Address 172.16.251.1/24, Area 0Process ID 10, Router ID 172.16.251.1, Network Type POINT_TO_POINT, Cost: 1785 ...
The routing tables for NewYork,
Chicago, and Ames will show
all 172.16.0.0 subnets. Here is
NewYork’s table:
NewYork#sh 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
Gateway of last resort is not set
5 172.16.0.0/16 is variably subnetted, 6 subnets, 2 masks
6 O 172.16.252.0/24 [110/128] via 172.16.250.2, 01:50:18, Serial0
C 172.16.250.0/24 is directly connected, Serial0
C 172.16.251.0/24 is directly connected, Serial1
7 O 172.16.50.1/32 [110/74] via 172.16.250.2, 01:50:18, Serial0
C 172.16.1.0/24 is directly connected, Ethernet0
8 O 172.16.100.1/32 [110/138] via 172.16.250.2, 01:50:18, Serial0The OSPF-derived routes in this table are labeled with an
“O” in the left margin. Note that
the routing table provides summary information (as in line 5). This
line contains subnet mask information (24 bits, or
255.255.255.0) and the number of subnets in
172.16.0.0 (6).