Link-State Routing Protocols

1. Link-State Routing Protocols

Link-State Protocols also fall into the classless category of routing protocols, and they work within packet-switched networks. Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (IS-IS) are two examples of Link-State Routing Protocols.

big idea

Remember, for a protocol to be a classless routing protocol, the subnet-mask information must be carried with the routing update. This enables every router to identify the best route to each and every network, even those that don’t use class-defined default subnet masks (i.e., 8, 16, or 24 bits) such as variable length subnet mask (VLSM) networks. All neighbor routers know the cost of the network route that’s being advertised.

One of the biggest differences between Link-State and Distance-Vector protocols is that Link-State Protocols learn and maintain much more information about the internetwork than Distance-Vector Routing Protocols do. Distance-Vector Routing Protocols only maintain routing tables with the destination routes and vector costs (like hop counts) in them. Link-State Routing Protocols maintain two additional tables with more detailed information. The first of these is the neighbor table. The neighbor table is maintained through the use of hello packets that are exchanged by all routers to determine which other routers are available to exchange routing data with. All routers that can share routing data are stored in the neighbor table.

The second table maintained is the topology table, which is built and sustained through the use of link-state advertisements (LSAs) or link-state packets (LSPs). In the topology table, you’ll find a listing for every destination network and every neighbor (route) through which it can be reached. Essentially, it’s a map of the entire internetwork.

Once all of that raw data is shared and each of the routers has the data in its topology table, the routing protocol runs the Shortest Path First (SPF) algorithm to compare it all and determine the best paths to each of the destination networks.

term to know

Hello Packets

Router-to-router message for verifying connectivity of adjacent networks.

1a. Open Shortest Path First

Open Shortest Path First (OSPF) is an open-standard routing protocol that’s been implemented by a wide variety of network vendors. OSPF works by using the Dijkstra algorithm. First, a shortest-path tree is constructed, and then the routing table is populated with the resulting best paths. OSPF converges quickly (although not as fast as Enhanced Interior Gateway Routing Protocol [EIGRP]), and it supports multiple, equal-cost routes to the same destination. Like EIGRP, it supports both IP and IPv6 routed protocols, but OSPF must maintain a separate database and routing table for each, which means you’re basically running two routing protocols if you are using IP and IPv6 with OSPF.

key concept

OSPF provides the following features:

• Consists of areas and autonomous systems (ASs)
• Minimizes routing update traffic
• Allows scalability
• Supports VLSM/classless inter-domain routing
• Has unlimited hop count
• Allows multi-vendor deployment (open standard)
• Uses a loopback (logical) interface to keep the network stable

OSPF is the first Link-State Routing Protocol that most people are introduced to, so it’s good to see how it compares to more traditional Distance-Vector Protocols like RIPv2 and RIPv1. The following table compares these three protocols.

OSPF has many features beyond the few listed in the table above, and all of them contribute to a fast, scalable, and robust protocol that can be actively deployed in thousands of production networks. One of OSPF’s most noteworthy features is that after a network change, such as when a link changes to up or down, OSPF converges quickly. In fact, it’s the fastest of any of the interior routing protocols we’ll be covering. Convergence happens when all routers have been successfully updated with the change.

OSPF is supposed to be designed in a hierarchical fashion, which basically means that you can separate the larger internetwork into smaller internetworks called areas. This is definitely the best design for OSPF.

key concept

The following are reasons you really want to create OSPF in a hierarchical design:

• To decrease routing overhead
• To speed up convergence
• To confine network instability to single areas of the network

While OSPF has these benefits, it can be complex and difficult to configure.

The diagram below shows a typical simple OSPF design. Notice how each router connects to the backbone—called area 0, or the backbone area. OSPF must have an area 0, and all other areas should connect to this area. Routers that connect other areas to the backbone area within an AS are called area border routers (ABR). Still, at least one interface of the ABR must be in area 0.

OSPF runs inside an AS, but it can also connect multiple ASs together. The router that connects these ASs is called an autonomous system border router (ASBR). Typically, in today’s networks, Border Gateway Protocol is used to connect between ASs, not OSPF.

hint

Ideally, you would create other areas of networks to help keep route updates to a minimum and to keep problems from propagating throughout the network. But that’s beyond the scope of this chapter. Just make note of it for your future networking studies.

terms to know

Open Shortest Path First (OSPF)

A Link-State Routing Protocol that is used to calculate routes based on the number of routers, transmission speed, delays, and route cost.

Dijkstra Algorithm

An algorithm for finding the shortest paths between nodes in a network.

Area

A logical grouping of hosts and networks.

Area 0

An OSPF backbone area.

Area Border Routers (ABRs)

A router that maintains separate link-state databases for each area it serves and maintains summarized routes for all areas in the network.

Autonomous System Border Router (ASBR)

A gateway to routers outside the OSPF domain.

1b. Intermediate System-to-Intermediate System

Intermediate System-to-Intermediate System (IS-IS) is an Interior Gateway Protocol, meaning that it’s intended for use within an administrative domain or network, not for routing between ASs. That would be a job that an Exterior Gateway Protocol would handle instead.

IS-IS is a Link-State Routing Protocol, meaning it operates by reliably flooding topology information throughout a network of routers. Each router then independently builds a picture of the network’s topology, just as they do with OSPF. Packets or datagrams are forwarded based on the best topological path through the network to the destination. The diagram below shows an IS-IS network and the terminology used with IS-IS.

key concept

Here are the definitions for the terms used in the IS-IS network shown in the diagram above:

• Level 1 (L1) intermediate systems route within an area. When the destination is outside an area, they route toward a Level 2 system.
• Level 2 (L2) intermediate systems route between areas and toward other ASs.

The similarity between IS-IS and OSPF is that both employ the Dijkstra algorithm to discover the shortest path through the network to a destination network. The difference between IS-IS and OSPF is that IS-IS uses Connectionless Network Service (CLNS) to provide connectionless delivery of data packets between routers, and it also doesn’t require an area 0 like OSPF does. OSPF uses IP to communicate between routers instead.

An advantage to having CLNS around is that it can easily send information about multiple routed protocols (IP and IPv6), and OSPF must maintain a completely different routing database for IP and IPv6, respectively, for it to be able to send updates for both protocols.

IS-IS supports the most important characteristics of OSPF and EIGRP because it supports VLSM and also because it converges quickly. Each of these three protocols has advantages and disadvantages, but it’s these two shared features that make any of them scalable and appropriate for supporting the large-scale networks of today.

IS-IS, although comparable to OSPF, is actually preferred by ISPs because of its ability to run IP and IPv6 without creating a separate database for each protocol as OSPF does. That single feature makes it more efficient in very large networks.

terms to know

Intermediate System to Intermediate System (IS-IS)

A Link-State Routing Protocol designed to move information efficiently within a computer network.

Connectionless Network Service (CLNS)

An OSI network layer datagram service that does not require a circuit to be established before data is transmitted and routes messages to their destinations independently of any other messages.