By Jeff Kabachinski
We continue the discussion of the specification called the Open Shortest Path First (OSPF) – it’s the Internet routing protocol. OSPF is classified as an Interior Gateway Protocol (IGP). This means that it distributes routing information between routers within a single Autonomous System (AS). The OSPF protocol is based on link-state status as we’ll see.
Background
The OSPF protocol was designed expressly for the TCP/IP Internet environment. It’s been around for a long time, in fact the latest version was last revised in 1998. OSPF builds a view or map of the AS to determine which way to route packets. OSPF also provides for the authentication of routing updates, and utilizes IP multicast addressing that includes just routers programmed to read the multicast to send and receive updates. In addition, OSPF was designed to respond quickly to network topology changes, however also partly due to multicasting it creates a small amount of routing protocol traffic. After initial convergence of routing tables among the AS’s routers, the only network traffic produced by the routers is when they detect a network topology change.
OSPF routes packets based solely on the destination IP address in the IP packet header. These packets are routed without any changes – they are not put into any further protocols as they move in the AS. OSPF is a dynamic routing protocol. It detects network changes in the AS (e.g. router link failures) and determines new loop-free paths after a period of “re-convergence.” The period of convergence happens quickly, involving a minimum of routing traffic.
OSPF Function
As OSPF is a link-state routing protocol where each router maintains a database mapping the AS’s topology from its point of view. This database is referred to as the link-state database or routing table. Each router’s individual routing database shows the router’s state or the router’s usable network interfaces (links) and their neighbor routers. The router distributes its local state or map throughout the AS by flooding.
OSPF enables sets of networks to be grouped together – called an area. The topology map of an area is not seen by the rest of the AS. By not sharing this information beyond the area allows a considerable reduction in routing traffic in the AS. An area can be thought of as an IP subnet.
Example Network Area
Figure 1 shows an example portion of an AS or area. For discussion purposes networks are named A, B, … . In reality networks are named per the IPv4 class system as discussed in last month’s column. The diagram also shows the cost of each network indicating their available bandwidth for handling traffic. A cost is associated with the output side or link of each router interface. This cost is configurable by the system administrator. The lower the cost, the higher the bandwidth helping the routers to choose best paths for sending data. The costs in the diagram are fictitious, however the general calculation divides network bandwidth by the data rate. Usually a 100M network bandwidth is used so for a 10M Ethernet connection the cost is 10.
In addition, in this example routers are ID’d simply as Router 1, Router 2, and so on, while in real life, routers have a unique 32-bit number.
The example starts with Router 1 booting up and checking for its preconfigured basic routing database or table – based on its link status:
The initial table shows only the status of Router 1’s direct links. Notice that the costs listed in the table are the network costs. Router 1 then sends its routing table to all neighboring routers using the multicast address of 224.0.0.5. The other routers respond with their routing tables. For example, Router 2 responds with:
Notice that Router 2 claims it can get to network C via Router 4 at a cost of 9. By adding the total cost of the route, we get 9 or 4+3+2 crossing these three networks to get there. When several equal-cost routes to a destination exist, traffic is distributed equally among them.
Router 1 then adds the information from neighbor routers 2 and 3 to its table:
Note – now there are two available routes to networks B, C, D and E. Obviously, the router will use the lowest cost (highest available bandwidth) first. Should trouble arise on that preferred link, it can use the alternate route. Note also that the total cost for each path includes all the costs of each network encountered along the way.
Recall that the actual network names come from the IPv4 class system detailed in last month’s column. A more realistic routing table may look like:
Summary
This short series describes the most ommon routing system employed within an AS. Covering how routers recognize network names or IDs. How they build their map of the area or AS that they’re in and how they determine the best path to forward network data packets.