Link State Versus Distance Vector Routing Protocols

Last Updated on Thu, 01 Feb 2024 | Ospf Network

This section describes the two most common and relevant routing protocols that TCP/IP has available for use, namely RIP and OSPF. Controversy surrounds the debate over link-state versus distance vector routing algorithms regarding which is better.

NOTE Link-State and distance vector routing protocols are also known as interior gateway protocols (IGPs); this concept is discussed later in the discussion of OSPF and border gateway protocol (BGP) interoperability. Chapter 7, "Summarization," discusses OSPF/ BGP interoperability in greater detail.

An IGP is a classification that describes the use of a dynamic routing protocol to exchange routing information within an autonomous system (AS). Examples of common IGPs include IGRP, OSPF, Intermediate System-to-Intermediate System (IS-IS), and RIP. You can contrast an IGP with an exterior gateway protocol (EGP) such as BGP.

52 Chapter 2: Introduction to OSPF

Link-State Routing Protocols

Link-state algorithms (also known as shortest path first algorithms) flood only incremental changes that have occurred since the last routing table update. During this incremental update, each router sends only that portion of the routing table that describes the state of its own links, as opposed to its entire routing table.

Link-state routing protocols require routers to periodically send routing updates to their neighboring routers in the internetwork. In addition, link-state routing protocols are quick to converge their routing updates across the network in comparison to distance vector protocols.

The speed at which they converge makes link-state protocols less prone to routing loops than distance vector protocols. However, link-state protocols also require more CPU power and system memory. One of the primary reasons that additional CPU power and memory are needed is that link-state protocols are based on the distributed map concept, which means that every router has a copy of the network map that is regularly updated. In addition to the size of the routing table, the number of routers in an area and the number of adjacencies amongst routers also has an affect on router memory and CPU usage in linkstate protocols. These factors were obvious in the old fully meshed asynchronous transfer mode (ATM) networks, where some routers had 50 or more OSPF adjacent peers and performed poorly.

Link-state protocols are based on link-state algorithms, which are also called shortest path first (SPF) algorithms or Dijkstra algorithms. "SPF in Operation," later in this chapter, covers the SPF algorithm in more detail.

A simple way to understand how link-state technology operates is to picture the network as a large jigsaw puzzle; the number of pieces in your puzzle depends on the size of your network. Each piece of the puzzle holds only one router or one LAN. Each router "draws" itself on that jigsaw piece, including arrows to other routers and LANs. Those pieces are then replicated and sent throughout the network from router to router (via link-state advertisements [LSAs]), until each router has a complete and accurate copy of each piece of the puzzle. Each router then assembles these pieces by using the SPF algorithm.

NOTE The principle of link-state routing is that all the routers within an area maintain an identical copy of the network topology. From this map, each router performs a series of calculations that determine the best routes. This network topology is contained within a link-state database, where each record represents the links to a particular node in the network.

Each record contains the following pieces of information:

• Interface identifier

• Link number

• Metric information regarding the state of the link

Armed with that information, each router can quickly compute the shortest path from itself to all other routers.

The SPF algorithm determines how the various pieces of the puzzle fit together. Figure 2-3 illustrates all of these pieces put together in operation.

Figure 2-3 Link-State Operation

LSAs are the foundation of the link-state database.

Figure 2-3 Link-State Operation

LSAs are the foundation of the link-state database.

: Link-State Database (LSDB)

SPF Algorithm

Shortest Path First Tree Each router builds one with itself as the root.

Link-state protocols such as OSPF flood all the routing information when they first become active in link-state packets. After the network converges, they send only small updates via link-state packets.

OSPF Characteristics

OSPF is a link-state protocol in which all routers in the routing domain exchange information and thus know about the complete topology of the network. Because each router knows the complete topology of the network, the use of the SPF algorithm creates an extremely fast convergence. Other key characteristics of OSPF are as follows:

• Provides routing information to the IP section of the TCP/IP protocol suite, the most commonly used alternative to RIP.

• Sends updates to tables only, instead of entire tables, to routers.

• Is a more economical routing protocol than RIP over time because it involves less network traffic.

54 Chapter 2: Introduction to OSPF

The "It Depends Rule"

I occasionally invoke a rule I invented that I call the "It Depends Rule," and I am invoking it now! OSPF is usually more efficient than RIP in exchanging routing information when a network is stable; however, for this rule to hold true, it depends on network events. For example, during an external convergence event, OSPF could flood more traffic than RIP. Consider that RIP carries 25 routes per update; on the other hand, OSPF floods a single LSA per external route that is affected by the convergence event. So, provided that you have a (relatively) stable environment, OSPF involves less traffic, and over time, it is statistically more economical than RIP. Using a single LSA per external route is inefficient, but OSPF was never designed to be an EGP. Therefore, I recommend an OSPF/BGP deployment when large numbers of external routers are present.

Another popular type of dynamic routing protocol that is based on the Dijkstra SPF algorithm is IS-IS. The use of IS-IS versus OSPF has been hotly debated.

Integrated Intermediate System-to-Intermediate System

IS-IS is an OSI link-state hierarchical routing protocol that is based on work originally done at Digital Equipment Corporation for DECnet/OSI (DECnet Phase V). This protocol floods the network with link-state information to build a complete, consistent picture of network topology.

The International Organization for Standardization (ISO) has developed the following routing protocols for use in the Open System Interconnection (OSI) protocol suite:

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

• End System-to-Intermediate System (ES-IS) protocol

• Interdomain routing protocol (IDRP)

For more information on IDRP or ES-IS, start with the RFCs, which can be found at www.ietf.org.

The American National Standards Institute (ANSI) X3S3.3 (network and transport layers) committee was the motivating force behind ISO standardization of IS-IS, which was originally developed to route in ISO connectionless network protocol (CLNP) networks. A version has since been created that supports both CLNP and IP networks. It is usually referred to as integrated IS-IS; this is the version discussed here.

OSI routing protocols are summarized in several ISO documents; those dealing with IS-IS are as follows:

• ISO 10589: Standards definition for IS-IS

• RFC 1195: Intermediate IS-IS

Distance Vector Routing Protocols

Distance vector means that information sent from router to router is based on an entry in a routing table that consists of the distance and vector to destination—distance being what it "costs" to get there and vector being the "direction" to get to the destination.

Distance vector protocols are often referred to as Bellman-Ford protocols because they are based on a computation algorithm described by R. E. Bellman; the first description of the distributed algorithm is attributed to Ford and Fulkerson. Distance vector algorithms (also known as Bellman-Ford algorithms) call for each router to send its entire routing table, but only to its neighbors. The neighbor then forwards its entire routing table to its neighbors, and so on. Figure 2-4 illustrates this routing table forwarding process.

Figure 2-4 Distance Vector Operation

Every router must be told of the change when a network goes down.

As Figure 2-4 illustrates, whenever a change to the network occurs, this causes the entire routing table to be sent from neighbor to neighbor in order for the network to reconverge in response to the network event (network down). What is not shown is the periodic sending of the routing table between neighbors—a mechanism that double-checks that the routing information each router has is valid.

56 Chapter 2: Introduction to OSPF

Routing Information Protocol Characteristics

RIP v1 is a distance vector protocol designed at Berkeley in the late 1960s that is still widely deployed today. In this protocol, the router only exchanges routing information from the connected neighbors. Key characteristics of RIP are as follows:

• RIP broadcasts every 30 seconds to maintain network integrity.

• RIP maintains routing tables, showing the number of hops between routers, and is limited to a 15-hop count.

• A router using RIP passes its entire routing table to each directly connected neighbor router that it knows of.

A detailed discussion about RIP is not very relevant in a book dedicated to OSPF, but if you want to learn more on RIP v1 and v2, consider the following resources:

• Routing TCP/IP, Volume I, by Jeff Doyle. Chapter 5 is dedicated to RIP.

• Routing information protocol (RIP) at cisco.com:

www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/rip.htm

• RFC 2453 RIP Version 2, published in 1998

Conclusion

Link-state algorithms send small updates everywhere; distance vector algorithms send large updates only to neighboring routers. Because they create a consistent view of the internetwork, link-state algorithms are somewhat less prone to routing loops than are distance vector algorithms. When a network is in stable or steady state, link-state protocols allow for smooth routing.

On the downside, link-state algorithms can cause significant, widespread control traffic, for example, when a network event occurs and the event must be flooded throughout the network. The main concern in today's networks is the amount of flooding that can happen as networks grow ever larger.

Link-state algorithms are also computationally difficult compared to distance vector algorithms, requiring more CPU power and memory than distance vector algorithms. However, this has become less of an issue as router-processing capabilities have improved.

Link-state algorithms can therefore be more expensive to implement and support. Despite their differences, both algorithm types perform well in circumstances and networks that suit their strengths and recognize their limitations.

Continue reading here: SPF in Operation

Was this article helpful?

Readers' Questions

Lisa
Which statement regarding the asynchronous transfer mode (atm) technology is accurate?

24 days ago
- Reply

One accurate statement regarding Asynchronous Transfer Mode (ATM) technology is: ATM is a high-speed networking technology that transmits data in fixed-size cells, allowing for efficient utilization of network resources and low-latency communication.

bucca
Which statement regarding the border gateway protocol (bgp) is accurate?

24 days ago
- Reply

One accurate statement regarding the Border Gateway Protocol (BGP) is that it is the primary protocol used for determining the best path for Internet traffic routing between autonomous systems (ASes) on the internet.

cynthia
Which statement regarding the asynchronous transfer mode (atm) technology is accurate?

2 months ago
- Reply

One accurate statement regarding Asynchronous Transfer Mode (ATM) technology is that it is a high-speed networking technology that is designed to handle both voice and data communication efficiently.

ROSARIO
Which statement regarding the border gateway protocol (bgp) is accurate?

2 months ago
- Reply

One accurate statement regarding the Border Gateway Protocol (BGP) is: - BGP is the primary routing protocol used for exchanging routing information between different autonomous systems (AS) on the internet.

Cora Watt
Which statement regarding the asynchronous transfer mode (atm) technology is accurate?

2 months ago
- Reply

One accurate statement regarding the Asynchronous Transfer Mode (ATM) technology is: ATM is a high-speed networking technology that utilizes fixed-length cells for data transmission, providing low latency and efficient bandwidth allocation.

juho
Which statement regarding the border gateway protocol (bgp) is accurate?

2 months ago
- Reply

The Border Gateway Protocol (BGP) is the protocol used for exchanging routing information between different autonomous systems (AS) in the Internet. It is primarily designed to provide scalability and reliability in the routing of internet traffic. One accurate statement regarding BGP is that it is a path vector protocol. Unlike other routing protocols like OSPF or RIP, which use metrics like hop count or bandwidth to determine the best path, BGP considers the path attributes such as AS path, next hop, and other policies. BGP uses these attributes to make routing decisions and choose the best path to reach a destination network.

bisrat saare
Which statement regarding the asynchronous transfer mode (atm) technology is accurate?

4 months ago
- Reply

One accurate statement regarding the Asynchronous Transfer Mode (ATM) technology is that it is a connection-oriented networking technology that operates at the data link layer of the OSI model.

Duilio
Which statement regarding the border gateway protocol (bgp) is accurate?

4 months ago
- Reply

One accurate statement regarding the Border Gateway Protocol (BGP) is: BGP is an Exterior Gateway Protocol (EGP) that is used to facilitate routing information between different autonomous systems (AS) on the internet.

BOBBY
Which statement regarding the asynchronous transfer mode (atm) technology is accurate?

5 months ago
- Reply

One accurate statement regarding the Asynchronous Transfer Mode (ATM) technology is that it is designed to transmit data in fixed-size packets called cells.

jaden
Which statement regarding the border gateway protocol (bgp) is accurate?

5 months ago
- Reply

There are multiple accurate statements regarding the Border Gateway Protocol (BGP). Here are a few examples:

BGP is a routing protocol used in the Internet to exchange routing information between Internet Service Providers (ISPs) and Autonomous Systems (AS).

BGP is a path-vector protocol that allows different autonomous systems to exchange information and make routing decisions based on various attributes.

BGP operates on TCP/IP and uses port 179 for communication.

BGP is highly scalable and provides better control over routing policies compared to Interior Gateway Protocols (IGPs) like OSPF or EIGRP.

BGP uses the Longest Prefix Match algorithm to make forwarding decisions in order to find the most specific route for a given destination IP address.

BGP is responsible for the core routing decisions and exchange of routing information between different autonomous systems on the Internet.It is essential to note that BGP is a complex protocol, and various statements can be accurate depending on the context and specific aspects being addressed.

Abele
How are distance vector routing protocols similar to linkstate routing protocols (select two.)?

6 months ago
- Reply

1) Both distance vector and link-state routing protocols aim to find the best path to forward network traffic. 2) Both distance vector and link-state routing protocols update their routing tables based on the exchange of routing information among neighboring routers.

rian munro
Which of the following is a common linkstate routing protocol?

6 months ago
- Reply

One example of a common link-state routing protocol is the Open Shortest Path First (OSPF) protocol.

Niklas
Which statement regarding the asynchronous transfer mode (atm) technology is accurate?

6 months ago
- Reply

One accurate statement regarding the Asynchronous Transfer Mode (ATM) technology is: "ATM is a high-speed networking technology that utilizes fixed-size cells to efficiently transmit data, voice, and video over the network."

s
Which statement regarding the border gateway protocol (bgp) is accurate?

6 months ago
- Reply

One accurate statement regarding the Border Gateway Protocol (BGP) is: "BGP is an internet routing protocol used to exchange routing information between different autonomous systems (AS)."

TESMI SELAM
Which statement does not accurately describe characteristics of the ospf protocol?

7 months ago
- Reply

The statement "OSPF is a link-state routing protocol" does not accurately describe characteristics of the OSPF protocol. OSPF (Open Shortest Path First) is indeed a link-state routing protocol. It uses link-state advertisements (LSAs) to exchange information about network topology with other routers in the OSPF domain. This information includes the state of links, network reachability, and the cost of reaching different destinations. Other accurate statements about OSPF characteristics include:

OSPF uses a hierarchical design called areas, with one Area 0 (backbone area) and other areas connected to the backbone.

OSPF uses the Dijkstra algorithm to calculate the shortest path to a destination.

OSPF supports multiple types of networks, such as broadcast, point-to-point, and non-broadcast multi-access (NBMA).

OSPF supports both IPv4 and IPv6 addressing.However, stating that OSPF is not a link-state routing protocol would be incorrect.

Fatima Galbassi
Which statement regarding the asynchronous transfer mode (atm) technology is accurate?

7 months ago
- Reply

One accurate statement regarding Asynchronous Transfer Mode (ATM) technology is that it is a high-speed networking standard that provides efficient and reliable transmission of data, voice, and video over a wide area network (WAN).

Finn
Which statement regarding the border gateway protocol (bgp) is accurate?

7 months ago
- Reply

One accurate statement regarding the Border Gateway Protocol (BGP) is: - BGP is an exterior gateway protocol (EGP) used to exchange routing and reachability information between autonomous systems (AS) on the internet.

Tesmi
When convergence on a routed network occurs, which of the following is true?

8 months ago
- Reply

When convergence occurs in a routed network, the following is true:

All routers in the network have learned and updated their routing tables with the most current and reliable route information.

Routing protocols, such as OSPF, EIGRP, or RIP, have exchanged and updated their routing information with neighboring routers.

The network topology has stabilized, and all routers have reached a consistent state in terms of routing decisions.

Data traffic can flow smoothly and efficiently between different network segments or subnets.

Any temporary disruptions or failures in the network have been resolved, and the network is back to normal operation.In summary, convergence ensures that all routers in a routed network have synchronized and updated routing information, leading to a stable and efficient communication.

Elvia Russo
What is the difference between distance vector and link state routing protocol?

8 months ago
- Reply

Distance Vector Routing Protocol and Link State Routing Protocol are two different approaches to routing in computer networks. Here are the key differences between them:

Update Processes: Distance Vector protocol uses periodic updates to communicate routing information between routers. It sends the entire routing table to its neighboring routers after a fixed time interval. On the other hand, Link State protocol updates the routing information only when there is a change in the network topology. It sends small packets called Link State Advertisements (LSAs) containing information about the local router's directly connected links and their status.

Information Exchange: In Distance Vector, routers only exchange routing information with their directly connected neighbors. Each router maintains its own routing table based on the received information. In Link State, routers flood LSAs throughout the network, ensuring that all routers have a complete picture of the network topology. Each router uses these LSAs to construct a map of the entire network.

Metrics and Path Selection: Distance Vector algorithms typically use hop count as the routing metric, where each link has an equal cost. The shortest path is determined by the minimum number of hops required. Link State protocols can consider various metrics such as bandwidth, delay, or load to determine the best path. They use Dijkstra's algorithm to calculate the shortest path based on these metrics.

Scalability: Distance Vector protocols have limited scalability due to the need for periodic updates and the potential for routing loops. As networks grow larger, convergence time increases and there is higher overhead in exchanging large routing tables. Link State protocols are more scalable as they provide a complete view of the network and allow routers to make more informed routing decisions. However, the flooding of LSAs can lead to increased overhead and memory usage in very large networks.

Reaction to Topology Changes: Distance Vector protocols have slower convergence time because it takes time for routing updates to propagate through the network. They rely on hop-by-hop updates, meaning routers need to wait for information from their neighbors before updating their routing tables. Link State protocols have faster convergence time as routers immediately react to topology changes by flooding LSAs and recalculating the shortest path.

Examples: Examples of Distance Vector protocols include Routing Information Protocol (RIP), Interior Gateway Routing Protocol (IGRP), and Border Gateway Protocol version 4 (BGPv4). Examples of Link State protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS).In summary, Distance Vector protocols use periodic updates, exchange limited information with neighboring routers, and have slower convergence time. Link State protocols use flooding to exchange complete network information, consider various metrics for path selection, and have faster convergence time.

marta
Which statement regarding the asynchronous transfer mode (atm) technology is accurate?

8 months ago
- Reply

An accurate statement regarding Asynchronous Transfer Mode (ATM) technology is that it is a high-speed networking technology that enables the simultaneous transmission of voice, video, and data over a single network.

ABDULLAH
Which statement regarding the border gateway protocol (bgp) is accurate?

8 months ago
- Reply

The Border Gateway Protocol (BGP) is a routing protocol used to exchange routing information between different autonomous systems (AS) on the internet. Here are some accurate statements regarding BGP:

BGP is an exterior gateway protocol used to route traffic between autonomous systems.

BGP is a path-vector protocol that considers various attributes to determine the best path for routing.

BGP uses TCP as its transport protocol, ensuring reliable and secure communication between routers.

BGP is designed to be highly scalable and capable of handling large networks with thousands of routers.

BGP allows for policy-based routing decisions, giving network administrators control over traffic flows.

BGP uses autonomous systems (AS) as a fundamental unit for routing, separating the internet into different domains.

BGP allows for the exchange of routing information and network reachability between different autonomous systems.

BGP supports both IPv4 and IPv6, enabling the routing of traffic using either protocol.

BGP relies on incremental updates, only sending the necessary changes in routing information rather than the entire routing table.

BGP operates independently of the underlying network protocols, enabling compatibility with various network technologies.It is important to note that BGP is a complex subject, and understanding its full functionality and intricacies requires more in-depth study and experience.

Fesahaye Ali
Which statement regarding the asynchronous transfer mode (atm) technology is accurate?

9 months ago
- Reply

ATM is a connection-oriented protocol that is used to transport voice, video, and data over a wide area network.

Mantissa
Which statement regarding the border gateway protocol (bgp) is accurate?

9 months ago
- Reply

BGP is a routing protocol used to exchange routing and reachability information between autonomous systems on the Internet.

jouko
Which statement regarding the asynchronous transfer mode (atm) technology is accurate?

10 months ago
- Reply

ATM is a technology for transmitting data, voice, and video over a single network platform, allowing for consistent and reliable connections.

bilba hogpen
Which statement regarding the border gateway protocol (bgp) is accurate?

10 months ago
- Reply

BGP is a routing protocol used to exchange routing and reachability information between autonomous systems on the Internet.

Abbey
Which statement regarding the asynchronous transfer mode (atm) technology is accurate?

11 months ago
- Reply

Atm is capable of providing high-speed data communications over high-speed digital networks.

maria
Which statement regarding the border gateway protocol (bgp) is accurate?

11 months ago
- Reply

? BGP is an Internet protocol used to exchange routing information between networks in the Internet Protocol (IP) network.

james
Which statement regarding the asynchronous transfer mode (atm) technology is accurate?

1 year ago
- Reply

Asynchronous Transfer Mode (ATM) technology is a connection-oriented switching technique used to transmit data across a network, supporting high bandwidth and low latency.

Carola
Which statement regarding the border gateway protocol (bgp) is accurate?

1 year ago
- Reply

BGP is a routing protocol used to exchange routing and reachability information between autonomous systems on the Internet.

oscar
Which of the following is a routing related gateway protocols?

1 year ago
- Reply

The following are routing related gateway protocols:

Border Gateway Protocol (BGP)

Open Shortest Path First (OSPF)

Enhanced Interior Gateway Routing Protocol (EIGRP)

Routing Information Protocol (RIP)

Interior Gateway Routing Protocol (IGRP)

ali
Which statement regarding the border gateway protocol (bgp) is accurate?

1 year ago
- Reply

BGP is a routing protocol that is used to exchange routing and reachability information between Autonomous Systems on the Internet.

Gimja
Which of the following is a routing related gateway protocol?

1 year ago
- Reply

Routing Information Protocol (RIP)

Open Shortest Path First (OSPF)

Border Gateway Protocol (BGP)

Intermediate System to Intermediate System (IS-IS)

sara
Which statement regarding the border gateway protocol (bgp) is accurate?

1 year ago
- Reply

BGP is a routing protocol that allows routers in different autonomous systems to exchange routing information.

benjamin
Which statement regarding the border gateway protocol (bgp) is accurate?

1 year ago
- Reply

BGP is a routing protocol used to identify how data should move across the internet.

beth
Which of the following is true about the ospf routing protocol?

1 year ago
- Reply

* OSPF is an open, link-state routing protocol used by network devices to exchange routing information. * It is an Interior Gateway Protocol (IGP) that is widely used, especially in larger networks. * OSPF uses a link-state algorithm for determining the best path for data to travel, based on topology and metrics. * It is an interior routing protocol, meaning it is used within an autonomous system, such as a single organization's network.

James
Which statement regarding the border gateway protocol (bgp) is accurate?

1 year ago
- Reply

BGP is a standard routing protocol used to exchange routing and reachability information among autonomous systems on the Internet.

jan
Which of the following routing protocols uses paths rules and policies instead of a metric?

1 year ago
- Reply

The routing protocol that uses paths, rules, and policies instead of a metric is the Border Gateway Protocol (BGP).

jessika
What routing protocol is the most popular linkstate protocol used within a large organization?

1 year ago
- Reply

OSPF (Open Shortest Path First)

nadine
Which of the following is a common linkstate protocol?

1 year ago
- Reply

OSPF (Open Shortest Path First)

IS-IS (Intermediate System to Intermediate System)

BGP (Border Gateway Protocol)

EIGRP (Enhanced Interior Gateway Routing Protocol)

tito
What is an advantage of ospf compared to rip?

1 year ago
- Reply

The main advantage of OSPF compared to RIP is its improved performance in larger networks. It has more efficient routing updates, shorter convergence time, and greater scalability. Also, OSPF allows for VLSM (Variable Length Subnet Masks) and CIDR (Classless Inter-Domain Routing) which allows for more efficient utilization of IP space. Additionally, OSPF also supports more powerful authentication and encryption than RIP.

Link State Versus Distance Vector Routing Protocols

Link-State Routing Protocols

OSPF Characteristics

Routing Information Protocol Characteristics

Conclusion

Recommended Books

Related Posts

Readers' Questions