CH 5 Scaling Network

1. How Much Does This Cost

This modeling activity illustrates the network concept of routing cost.

You will be a member of a team of five students who travel routes to complete the activity scenarios. Each group will be required to have one digital camera or any device that has a camera, a stopwatch, and the provided student file for this activity. One person will function as the photographer and event recorder, as selected by each group. The remaining four team members will actively participate in the scenarios below.

A school or university classroom, hallway, outdoor track area, school parking lot, or any other location can serve as the venue for these activities.

Activity 1

The tallest person in the group establishes a start and finish line by marking 15 steps from start to finish, indicating the distance of the team route. Each student will take 15 steps from the start line toward the finish line and then stop on the 15th step—no further steps are allowed.

Note: Not all of the students may reach the same distance from the start line due to their height and stride differences. The photographer will take a group picture of the entire team’s final location after taking the 15 steps required.

Activity 2

A new start and finish line will be established; however, this time, a longer distance for the route will be established than the distance specified in Activity 1. No maximum steps are to be used as a basis for creating this particular route. One at a time, students will “walk the new route from beginning to end twice”.

Each team member will count the steps taken to complete the route. The recorder will time each student and at the end of each team member’s route, record the time that it took to complete the full route and how many steps were taken, as recounted by each team member and recorded on the team’s student file.

After both activities have been completed, teams will use the digital picture taken for Activity 1 and their recorded data from Activity 2 file to answer the reflection questions.

Group answers can be discussed as a class, time permitting.

Class Activity - How Much Does This Cost? Instructions

2. Classifying Routing Protocols

Dynamic routing protocols are used to facilitate the exchange of routing information between routers. A routing protocol is a set of processes, algorithms, and messages that are used to exchange routing information and populate the routing table with the routing protocol's choice of best paths. The purpose of dynamic routing protocols includes:

• Discovery of remote networks

• Maintaining up-to-date routing information

• Choosing the best path to destination networks

• Ability to find a new best path if the current path is no longer available

Routing protocols can be classified into different groups according to their characteristics. Specifically, routing protocols can be classified by their:

• Purpose - Interior Gateway Protocol (IGP) or Exterior Gateway Protocol (EGP)

• Operation - Distance vector protocol, link-state protocol, or path-vector protocol

• Behavior - Classful (legacy) or classless protocol

For example, IPv4 routing protocols are classified as follows:

• RIPv1 (legacy) - IGP, distance vector, classful protocol

• IGRP (legacy) - IGP, distance vector, classful protocol developed by Cisco (deprecated from 12.2 IOS and later)

• RIPv2 - IGP, distance vector, classless protocol

• EIGRP - IGP, distance vector, classless protocol developed by Cisco

• OSPF - IGP, link-state, classless protocol

• IS-IS - IGP, link-state, classless protocol

• BGP - EGP, path-vector, classless protocol

The classful routing protocols, RIPv1 and IGRP, are legacy protocols and are only used in older networks. These routing protocols have evolved into the classless routing protocols, RIPv2 and EIGRP, respectively. Link-state routing protocols are classless by nature.

The figure displays a hierarchical view of dynamic routing protocol classification.

3. IGP and EGP Routing Protocols

An autonomous system (AS) is a collection of routers under a common administration such as a company or an organization. An AS is also known as a routing domain. Typical examples of an AS are a company’s internal network and an ISP’s network.

The Internet is based on the AS concept; therefore, two types of routing protocols are required:

• Interior Gateway Protocols (IGP) - Used for routing within an AS. It is also referred to as intra-AS routing. Companies, organizations, and even service providers use an IGP on their internal networks. IGPs include RIP, EIGRP, OSPF, and IS-IS.

• Exterior Gateway Protocols (EGP) - Used for routing between ASes. It is also referred to as inter-AS routing. Service providers and large companies may interconnect using an EGP. The Border Gateway Protocol (BGP) is the only currently-viable EGP and is the official routing protocol used on the Internet.

Note: Because BGP is the only EGP available, the term EGP is rarely used; instead, most engineers simply refer to BGP.

The example in the figure provides simple scenarios highlighting the deployment of IGPs, BGP, and static routing:

• ISP-1 - This is an AS and it uses IS-IS as the IGP. It interconnects with other autonomous systems and service providers using BGP to explicitly control how traffic is routed.

• ISP-2 - This is an AS and it uses OSPF as the IGP. It interconnects with other autonomous systems and service providers using BGP to explicitly control how traffic is routed.

• AS-1 - This is a large organization and it uses EIGRP as the IGP. Because it is multihomed (i.e., connects to two different service providers), it uses BGP to explicitly control how traffic enters and leaves the AS.

• AS-2 - This is a medium-sized organization and it uses OSPF as the IGP. It is also multihomed; therefore, it uses BGP to explicitly control how traffic enters and leaves the AS.

• AS-3 - This is a small organization with older routers within the AS; it uses RIP as the IGP. BGP is not required because it is single-homed (i.e., connects to one service provider). Instead, static routing is implemented between the AS and the service provider.

Note: BGP is beyond the scope of this course and is not discussed in detail.

4. Distance Vector Routing Protocols

Distance vector means that routes are advertised by providing two characteristics:

• Distance - Identifies how far it is to the destination network and is based on a metric such as the hop count, cost, bandwidth, delay, and more.

• Vector - Specifies the direction of the next-hop router or exit interface to reach the destination.

For example, in the figure, R1 knows that the distance to reach network 172.16.3.0/24 is one hop and that the direction is out of the interface S0/0/0 toward R2.

A router using a distance vector routing protocol does not have the knowledge of the entire path to a destination network. Distance vector protocols use routers as sign posts along the path to the final destination. The only information a router knows about a remote network is the distance or metric to reach that network and which path or interface to use to get there. Distance vector routing protocols do not have a map of the network topology like other types of routing protocols do.

There are four distance vector IPv4 IGPs:

• RIPv1 - First generation legacy protocol

• RIPv2 - Simple distance vector routing protocol

• IGRP - First generation Cisco proprietary protocol (obsolete and replaced by EIGRP)

• EIGRP - Advanced version of distance vector routing

5. Link-State Routing Protocols

In contrast to distance vector routing protocol operation, a router configured with a link-state routing protocol can create a complete view or topology of the network by gathering information from all of the other routers.

To continue our analogy of sign posts, using a link-state routing protocol is like having a complete map of the network topology. The sign posts along the way from source to destination are not necessary, because all link-state routers are using an identical map of the network. A link-state router uses the link-state information to create a topology map and to select the best path to all destination networks in the topology.

Link-state routing protocols do not use periodic updates. In contrast, RIP-enabled routers send periodic updates of their routing information to their neighbors. After the routers have learned about all the required networks (achieved convergence), a link-state update is only sent when there is a change in the topology. For example, the link-state update in the animation is not sent until the 172.16.3.0 network goes down.

Click Play in the figure to view link-state operations.

Link-state protocols work best in situations where:

• The network design is hierarchical, usually occurring in large networks

• Fast adaptation to network changes is crucial

• The administrators are knowledgeable about the implementation and maintenance of a link-state routing protocol

There are two link-state IPv4 IGPs:

• OSPF - Popular standards-based routing protocol

• IS-IS - Popular in provider networks

6. Classful Routing Protocols

The biggest distinction between classful and classless routing protocols is that classful routing protocols do not send subnet mask information in routing updates. Classless routing protocols include subnet mask information in the routing updates.

The two original IPv4 routing protocols developed were RIPv1 and IGRP. They were created when network addresses were allocated based on classes (i.e., class A, B, or C). At that time, a routing protocol did not need to include the subnet mask in the routing update, because the network mask could be determined based on the first octet of the network address.

Note: Only RIPv1 and IGRP are classful. All other IPv4 and IPv6 routing protocols are classless. Classful addressing has never been a part of IPv6.

The fact that RIPv1 and IGRP do not include subnet mask information in their updates means that they cannot provide variable-length subnet masks (VLSMs) and classless interdomain routing (CIDR).

Classful routing protocols also create problems in discontiguous networks. A discontiguous network is when subnets from the same classful major network address are separated by a different classful network address.

To illustrate the shortcoming of classful routing, refer to the topology in Figure 1. Notice that the LANs of R1 (172.16.1.0/24) and R3 (172.16.2.0/24) are both subnets of the same class B network (172.16.0.0/16). They are separated by different classful subnets (192.168.1.0/30 and 192.168.2.0/30) of the same class C networks (192.168.1.0/24 and 192.168.2.0/24).

When R1 forwards an update to R2, RIPv1 does not include the subnet mask information with the update; it only forwards the class B network address 172.16.0.0.

R2 receives and processes the update. It then creates and adds an entry for the class B 172.16.0.0/16 network in the routing table, as shown in Figure 2.

Figure 3 shows that when R3 forwards an update to R2, it also does not include the subnet mask information and therefore only forwards the classful network address 172.16.0.0.

In Figure 4, R2 receives and processes the update and adds another entry for the classful network address 172.16.0.0/16 to its routing table. When there are two entries with identical metrics in the routing table, the router shares the load of the traffic equally among the two links. This is known as load balancing.

As shown in Figure 5, this has a negative effect on connectivity to a discontiguous network. Notice the erratic behavior of the ping andtraceroute commands.

7. Routing Protocol Characteristics

Routing protocols can be compared based on the following characteristics:

• Speed of Convergence - Speed of convergence defines how quickly the routers in the network topology share routing information and reach a state of consistent knowledge. The faster the convergence, the more preferable the protocol. Routing loops can occur when inconsistent routing tables are not updated due to slow convergence in a changing network.

• Scalability - Scalability defines how large a network can become, based on the routing protocol that is deployed. The larger the network is, the more scalable the routing protocol needs to be.

• Classful or Classless (Use of VLSM) - Classful routing protocols do not include the subnet mask and cannot support VLSM. Classless routing protocols include the subnet mask in the updates. Classless routing protocols support VLSM and better route summarization.

• Resource Usage - Resource usage includes the requirements of a routing protocol such as memory space (RAM), CPU utilization, and link bandwidth utilization. Higher resource requirements necessitate more powerful hardware to support the routing protocol operation, in addition to the packet forwarding processes.

• Implementation and Maintenance - Implementation and maintenance describes the level of knowledge that is required for a network administrator to implement and maintain the network based on the routing protocol deployed.

The table in the figure summarizes the characteristics of each routing protocol.

8. Routing Protocol Metrics

There are cases when a routing protocol learns of more than one route to the same destination. To select the best path, the routing protocol must be able to evaluate and decide between the available paths. This is accomplished through the use of routing metrics.

A metric is a measurable value that is assigned by the routing protocol to different routes based on the usefulness of that route. In situations where there are multiple paths to the same remote network, the routing metrics are used to determine the overall “cost” of a path from source to destination. Routing protocols determine the best path based on the route with the lowest cost.

Different routing protocols use different metrics. The metric used by one routing protocol is not comparable to the metric used by another. As a result, two different routing protocols might choose different paths to the same destination.

The following lists some dynamic protocols and the metrics they use:

• Routing Information Protocol (RIP) - Hop count

• Open Shortest Path First (OSPF) - Cisco’s cost based on cumulative bandwidth from source to destination

• Enhanced Interior Gateway Routing Protocol (EIGRP) – Minimum bandwidth, delay, load, and reliability.

The animation in the figure shows that RIP would choose the path with the least amount of hops; whereas, OSPF would choose the path with the highest bandwidth.

9. Dynamic Routing Protocol Operation

All routing protocols are designed to learn about remote networks and to quickly adapt whenever there is a change in the topology. The method that a routing protocol uses to accomplish this depends upon the algorithm it uses and the operational characteristics of that protocol.

In general, the operations of a dynamic routing protocol can be described as follows:

1. The router sends and receives routing messages on its interfaces.

2. The router shares routing messages and routing information with other routers that are using the same routing protocol.

3. Routers exchange routing information to learn about remote networks.

4. When a router detects a topology change, the routing protocol can advertise this change to other routers.

Click Play in the figure to view an animation of a dynamic routing protocol in operation.

10. Cold Start

All routing protocols follow the same patterns of operation. To help illustrate this, consider the following scenario in which all three routers are running RIPv2.

When a router powers up, it knows nothing about the network topology. It does not even know that there are devices on the other end of its links. The only information that a router has is from its own saved configuration file stored in NVRAM. After a router boots successfully, it applies the saved configuration. If the IP addressing is configured correctly, then the router initially discovers its own directly connected networks.

Click Play in the figure to view an animation of the initial discovery of connected networks for each router.

Notice how the routers proceed through the boot up process and then discover any directly connected networks and subnet masks. This information is added to their routing tables as follows:

• R1 adds the 10.1.0.0 network available through interface FastEthernet 0/0 and 10.2.0.0 is available through interface Serial 0/0/0.

• R2 adds the 10.2.0.0 network available through interface Serial 0/0/0 and 10.3.0.0 is available through interface Serial 0/0/1.

• R3 adds the 10.3.0.0 network available through interface Serial 0/0/1 and 10.4.0.0 is available through interface FastEthernet 0/0.

With this initial information, the routers then proceed to find additional route sources for their routing tables.

11. Network Discovery

After initial boot up and discovery, the routing table is updated with all directly connected networks and the interfaces those networks reside on.

If a routing protocol is configured, the next step is for the router to begin exchanging routing updates to learn about any remote routes.

The router sends an update packet out all interfaces that are enabled on the router. The update contains the information in the routing table, which currently is all directly connected networks.

At the same time, the router also receives and processes similar updates from other connected routers. Upon receiving an update, the router checks it for new network information. Any networks that are not currently listed in the routing table are added.

Refer to the figure for a topology setup between three routers, R1, R2, and R3 with RIPv2 enabled. Based on this topology, below is a listing of the different updates that R1, R2, and R3 send and receive during initial convergence.

R1:

• Sends an update about network 10.1.0.0 out the Serial0/0/0 interface

• Sends an update about network 10.2.0.0 out the FastEthernet0/0 interface

• Receives an update from R2 about network 10.3.0.0 and increments the hop count by 1

• Stores network 10.3.0.0 in the routing table with a metric of 1

R2:

• Sends an update about network 10.3.0.0 out the Serial 0/0/0 interface

• Sends an update about network 10.2.0.0 out the Serial 0/0/1 interface

• Receives an update from R1 about network 10.1.0.0 and increments the hop count by 1

• Stores network 10.1.0.0 in the routing table with a metric of 1

• Receives an update from R3 about network 10.4.0.0 and increments the hop count by 1

• Stores network 10.4.0.0 in the routing table with a metric of 1

R3:

• Sends an update about network 10.4.0.0 out the Serial 0/0/1 interface

• Sends an update about network 10.3.0.0 out the FastEthernet0/0

• Receives an update from R2 about network 10.2.0.0 and increments the hop count by 1

• Stores network 10.2.0.0 in the routing table with a metric of 1

Click Play in the figure to view an animation of R1, R2, and R3 starting the initial exchange.

After this first round of update exchanges, each router knows about the connected networks of their directly connected neighbors. However, did you notice that R1 does not yet know about 10.4.0.0 and that R3 does not yet know about 10.1.0.0? Full knowledge and a converged network do not take place until there is another exchange of routing information.

12. Exchanging the Routing Information

At this point the routers have knowledge about their own directly connected networks and about the connected networks of their immediate neighbors. Continuing the journey toward convergence, the routers exchange the next round of periodic updates. Each router again checks the updates for new information.

Refer to the figure for a topology setup between three routers, R1, R2, and R3. After initial discovery is complete, each router continues the convergence process by sending and receiving the following updates.

R1:

• Sends an update about network 10.1.0.0 out the Serial 0/0/0 interface

• Sends an update about networks 10.2.0.0 and 10.3.0.0 out the FastEthernet0/0 interface

• Receives an update from R2 about network 10.4.0.0 and increments the hop count by 1

• Stores network 10.4.0.0 in the routing table with a metric of 2

• Same update from R2 contains information about network 10.3.0.0 with a metric of 1. There is no change; therefore, the routing information remains the same

R2:

• Sends an update about networks 10.3.0.0 and 10.4.0.0 out of Serial 0/0/0 interface

• Sends an update about networks 10.1.0.0 and 10.2.0.0 out of Serial 0/0/1 interface

• Receives an update from R1 about network 10.1.0.0. There is no change; therefore, the routing information remains the same

• Receives an update from R3 about network 10.4.0.0. There is no change; therefore, the routing information remains the same

R3:

• Sends an update about network 10.4.0.0 out the Serial 0/0/1 interface

• Sends an update about networks 10.2.0.0 and 10.3.0.0 out the FastEthernet0/0 interface

• Receives an update from R2 about network 10.1.0.0 and increments the hop count by 1

• Stores network 10.1.0.0 in the routing table with a metric of 2

• Same update from R2 contains information about network 10.2.0.0 with a metric of 1. There is no change; therefore, the routing information remains the same

Click Play in the figure to view an animation of R1, R2, and R3 sending the latest routing table to their neighbors.

Distance vector routing protocols typically implement a routing loop prevention technique known as split horizon. Split horizon prevents information from being sent out the same interface from which it was received. For example, R2 does not send an update containing the network 10.1.0.0 out of Serial 0/0/0, because R2 learned about network 10.1.0.0 through Serial 0/0/0.

After routers within a network have converged, the router can then use the information within the routing table to determine the best path to reach a destination. Different routing protocols have different ways of calculating the best path.

13. Distance Vector Technologies

Distance vector routing protocols share updates between neighbors. Neighbors are routers that share a link and are configured to use the same routing protocol. The router is only aware of the network addresses of its own interfaces and the remote network addresses it can reach through its neighbors. Routers using distance vector routing are not aware of the network topology.

Some distance vector routing protocols send periodic updates. For example, RIP sends a periodic update to all of its neighbors every 30 seconds. RIP does this even if the topology has not changed. RIPv1 sends these updates as broadcasts to the all-hosts IPv4 address of 255.255.255.255.

The broadcasting of periodic updates is inefficient because the updates consume bandwidth and network device CPU resources. Every network device has to process a broadcast message. Instead of using broadcasts like RIP, RIPv2 and EIGRP can use multicast addresses to reach only specific neighbor routers. EIGRP can also use a unicast message to reach one specific neighbor router. Additionally, EIGRP only sends updates when needed, instead of periodically.

As shown in the figure, the two modern IPv4 distance vector routing protocols are RIPv2 and EIGRP. RIPv1 and IGRP are listed only for historical accuracy.

14. Distance Vector Algorithm

At the core of the distance vector protocol is the routing algorithm. The algorithm is used to calculate the best paths and then send that information to the neighbors.

The algorithm used for the routing protocols defines the following processes:

• Mechanism for sending and receiving routing information

• Mechanism for calculating the best paths and installing routes in the routing table

• Mechanism for detecting and reacting to topology changes

In the figure animation, R1 and R2 are configured with the RIP routing protocol. The algorithm sends and receives updates. Both R1 and R2 then glean new information from the update. In this case, each router learns about a new network. The algorithm on each router makes its calculations independently and updates the routing table with the new information. When the LAN on R2 goes down, the algorithm constructs a triggered update and sends it to R1. R1 then removes the network from the routing table.

Different routing protocols use different algorithms to install routes in the routing table, send updates to neighbors, and make path determination decisions. For example:

• RIP uses the Bellman-Ford algorithm as its routing algorithm. It is based on two algorithms developed in 1958 and 1956 by Richard Bellman and Lester Ford, Jr.

• IGRP and EIGRP use the Diffusing Update Algorithm (DUAL) routing algorithm developed by Dr. J.J. Garcia-Luna-Aceves at SRI International.

15. Shortest Path First Protocols

Link-state routing protocols are also known as shortest path first protocols and are built around Edsger Dijkstra's shortest path first (SPF) algorithm. The SPF algorithm is discussed in more detail in a later section.

The IPv4 link-state routing protocols are shown in the figure:

• Open Shortest Path First (OSPF)

• Intermediate System-to-Intermediate System (IS-IS)

Link-state routing protocols have the reputation of being much more complex than their distance vector counterparts. However, the basic functionality and configuration of link-state routing protocols is equally straight-forward.

Just like RIP and EIGRP, basic OSPF operations can be configured using the:

• router ospf process-id global configuration command

• network command to advertise networks

16. SPF Example

The table in Figure 1 displays the shortest path and the accumulated cost to reach the identified destination networks from the perspective of R1.

The shortest path is not necessarily the path with the least number of hops. For example, look at the path to the R5 LAN. It might be assumed that R1 would send directly to R4 instead of to R3. However, the cost to reach R4 directly (22) is higher than the cost to reach R4 through R3 (17).

Observe the shortest path for each router to reach each of the LANs, as shown in Figures 2 to 5.

17. Link-State Routing Process

So exactly how does a link-state routing protocol work? With link-state routing protocols, a link is an interface on a router. Information about the state of those links is known as link-states.

All routers in an OSPF area will complete the following generic link-state routing process to reach a state of convergence:

1. Each router learns about its own links and its own directly connected networks. This is done by detecting that an interface is in the up state.

2. Each router is responsible for meeting its neighbors on directly connected networks. Link state routers do this by exchanging Hello packets with other link-state routers on directly connected networks.

3. Each router builds a Link-State Packet (LSP) containing the state of each directly connected link. This is done by recording all the pertinent information about each neighbor, including neighbor ID, link type, and bandwidth.

4. Each router floods the LSP to all neighbors. Those neighbors store all LSPs received in a database. They then flood the LSPs to their neighbors until all routers in the area have received the LSPs. Each router stores a copy of each LSP received from its neighbors in a local database.

5. Each router uses the database to construct a complete map of the topology and computes the best path to each destination network. Like having a road map, the router now has a complete map of all destinations in the topology and the routes to reach them. The SPF algorithm is used to construct the map of the topology and to determine the best path to each network.

Note: This process is the same for both OSPF for IPv4 and OSPF for IPv6. The examples in this section will refer to OSPF for IPv4.

18. Link and Link-State

The first step in the link-state routing process is that each router learns about its own links, its own directly connected networks. When a router interface is configured with an IP address and subnet mask, the interface becomes part of that network.

Refer to the topology in Figure 1. For purposes of this discussion, assume that R1 was previously configured and had full connectivity to all neighbors. However, R1 lost power briefly and had to restart.

During boot up R1 loads the saved startup configuration file. As the previously configured interfaces become active, R1 learns about its own directly connected networks. Regardless of the routing protocols used, these directly connected networks are now entries in the routing table.

As with distance vector protocols and static routes, the interface must be properly configured with an IPv4 address and subnet mask, and the link must be in the up state before the link-state routing protocol can learn about a link. Also, like distance vector protocols, the interface must be included in one of the network router configuration statements before it can participate in the link-state routing process.

Figure 1 shows R1 linked to four directly connected networks:

• FastEthernet 0/0 - 10.1.0.0/16

• Serial 0/0/0 - 10.2.0.0/16

• Serial 0/0/1 - 10.3.0.0/16

• Serial 0/1/0 - 10.4.0.0/16

As shown in Figures 2 to 5, the link-state information includes:

• The interface's IPv4 address and subnet mask

• The type of network, such as Ethernet (broadcast) or Serial point-to-point link

• The cost of that link

• Any neighbor routers on that link

Note: Cisco’s implementation of OSPF specifies the OSPF routing metric as the cost of the link based on the bandwidth of the outgoing interface. For the purposes of this chapter, we are using arbitrary cost values to simplify the demonstration.

19. Flooding the LSP

The fourth step in the link-state routing process is that each router floods the LSP to all neighbors, who then store all LSPs received in a database.

Each router floods its link-state information to all other link-state routers in the routing area. Whenever a router receives an LSP from a neighboring router, it immediately sends that LSP out all other interfaces except the interface that received the LSP. This process creates a flooding effect of LSPs from all routers throughout the routing area.

Click Play in the figure to view an animation on LSP flooding.

In the animation, notice how the LSPs are flooded almost immediately after being received without any intermediate calculations. Link-state routing protocols calculate the SPF algorithm after the flooding is complete. As a result, link-state routing protocols reach convergence very quickly.

Remember that LSPs do not need to be sent periodically. An LSP only needs to be sent:

• During initial startup of the routing protocol process on that router (e.g., router restart)

• Whenever there is a change in the topology (e.g., a link going down or coming up, a neighbor adjacency being established or broken)

In addition to the link-state information, other information is included in the LSP, such as sequence numbers and aging information, to help manage the flooding process. This information is used by each router to determine if it has already received the LSP from another router or if the LSP has newer information than what is already contained in the link-state database. This process allows a router to keep only the most current information in its link-state database.

20. Building the Link-State Database

The final step in the link-state routing process is that each router uses the database to construct a complete map of the topology and computes the best path to each destination network.

Eventually, all routers receive an LSP from every other link-state router in the routing area. These LSPs are stored in the link-state database.

The example in the figure displays the link-state database content of R1.

As a result of the flooding process, R1 has learned the link-state information for each router in its routing area. Notice that R1 also includes its own link-state information in the link-state database.

With a complete link-state database, R1 can now use the database and the shortest path first (SPF) algorithm to calculate the preferred path or shortest path to each network resulting in the SPF tree.

21. Building the SPF Tree

Each router in the routing area uses the link-state database and SPF algorithm to construct the SPF tree.

For example, using the link-state information from all other routers, R1 can now begin to construct an SPF tree of the network. To begin, the SPF algorithm interprets each router’s LSP to identify networks and associated costs.

In Figure 1, R1 identifies its directly connected networks and costs.

In Figures 2 through 5, R1 keeps adding any unknown network and associated costs to the SPF tree. Notice that R1 ignores any networks it has already identified.

The SPF algorithm then calculates the shortest paths to reach each individual network resulting in the SPF tree as shown in Figure 6. R1 now has a complete topology view of the link-state area.

Each router constructs its own SPF tree independently from all other routers. To ensure proper routing, the link-state databases used to construct those trees must be identical on all routers.

22. Adding OSPF Routes to the Routing Table

Using the shortest path information determined by the SPF algorithm, these paths can now be added to the routing table. The figure shows the routes that have now been added to R1’s IPv4 routing table.

The routing table also includes all directly connected networks and routes from any other sources, such as static routes. Packets are now forwarded according to these entries in the routing table.

23. Why Use Link-State Protocols?

As shown in the figure, there are several advantages of link-state routing protocols compared to distance vector routing protocols.

• Builds a Topological Map - Link-state routing protocols create a topological map, or SPF tree, of the network topology. Because link-state routing protocols exchange link-states, the SPF algorithm can build an SPF tree of the network. Using the SPF tree, each router can independently determine the shortest path to every network.

• Fast Convergence - When receiving an LSP, link-state routing protocols immediately flood the LSP out all interfaces except for the interface from which the LSP was received. In contrast, RIP needs to process each routing update and update its routing table before flooding them out other interfaces.

• Event-driven Updates - After the initial flooding of LSPs, link-state routing protocols only send out an LSP when there is a change in the topology. The LSP contains only the information regarding the affected link. Unlike some distance vector routing protocols, link-state routing protocols do not send periodic updates.

• Hierarchical Design - Link-state routing protocols use the concept of areas. Multiple areas create a hierarchical design to networks, allowing for better route aggregation (summarization) and the isolation of routing issues within an area.

Disadvantages of Link-State Protocols

As summarized in figure 1 link-state protocols also have a few disadvantages compared to distance vector routing protocols:

• Memory Requirements - Link-state protocols require additional memory to create and maintain the link-state database and SPF tree.

• Processing Requirements - Link-state protocols can also require more CPU processing than distance vector routing protocols. The SPF algorithm requires more CPU time than distance vector algorithms such as Bellman-Ford, because link-state protocols build a complete map of the topology.

• Bandwidth Requirements - The flooding of link-state packets can adversely affect the available bandwidth on a network. This should only occur during initial startup of routers, but can also be an issue on unstable networks.

However, modern link-state routing protocols are designed to minimize the effects on memory, CPU, and bandwidth. The use and configuration of multiple areas can reduce the size of the link-state databases. Multiple areas can limit the amount of link-state information flooding in a routing domain and send LSPs only to those routers that need them. When there is a change in the topology, only those routers in the affected area receive the LSP and run the SPF algorithm. This can help isolate an unstable link to a specific area in the routing domain.

For example, in figure 2, there are three separate routing domains: area 1, area 0, and area 51. If a network in area 51 goes down, the LSP with the information about this downed link is only flooded to other routers in that area. Only those routers in area 51 need to update their link-state databases, rerun the SPF algorithm, create a new SPF tree, and update their routing tables. Routers in other areas learn that this route is down, but this is done with a type of LSP that does not cause them to rerun their SPF algorithm. Routers in other areas can update their routing tables directly.

We're here to help you!