Home » Computer Network » Types of Routing Algorithms in Computer Networks

Types of Routing Algorithms in Computer Networks

Last updated:

Support this post with a reaction:

5,135 views

In computer networks, data is transferred from one device to another in the form of packets. When the source and destination devices are connected through different networks, packets may need to pass through several intermediate routers before reaching their destination.

To deliver these packets successfully, routers must determine a suitable path through the network. The process of selecting a path for transferring data packets is called routing.

A routing algorithm is a set of rules and procedures that helps routers select appropriate paths for packet transmission. It considers different factors, such as network topology, distance, number of hops, bandwidth, delay, and network traffic.

Routing algorithms are important because they help improve network performance, reduce unnecessary delays, and ensure efficient packet delivery.

What Are the Various Types of Routing Algorithms?

Routing algorithms are mainly classified into two major categories based on how they select and update routes:

  1. Non-Adaptive Routing Algorithms (Static Routing)
  2. Adaptive Routing Algorithms (Dynamic Routing)

Non-adaptive routing algorithms use predefined routes, whereas adaptive routing algorithms change their routing decisions according to current network conditions.

The different routing algorithms are explained below.

1. Non-Adaptive Routing Algorithms (Static Routing)

Non-Adaptive Routing Algorithms are routing methods in which the routes are selected in advance and remain fixed during normal network operation.

These algorithms do not automatically change their routing decisions according to current network conditions, such as congestion, traffic changes, or link failures.

The routes are generally determined by the network administrator or based on predefined network information.

Non-adaptive routing is suitable for small networks where the network structure does not change frequently.

The important types of non-adaptive routing algorithms are:

A. Shortest Path Routing

Shortest Path Routing is a routing technique that selects the path with the minimum total cost between the source and destination.

The cost of a path may depend on different factors, such as the number of hops, distance, delay, or transmission cost.

The network is represented as a graph in which:

  • Nodes represent routers or network devices.
  • Edges represent communication links between nodes.
  • Edge weights represent the cost of communication links.

The algorithm calculates the total cost of available paths and selects the path with the lowest cost.

Working of Shortest Path Routing

  1. The network is represented as a graph containing nodes and communication links.
  2. Each communication link is assigned a cost or weight.
  3. The algorithm examines the available paths between the source and destination.
  4. It calculates the total cost of each possible path.
  5. The path with the lowest total cost is selected for packet transmission.

Example of Shortest Path Routing

Suppose a network has three possible routers connecting Computer A to Computer D.

  • Path 1: A → B → D (Cost = 10)
  • Path 2: A → C → D (Cost = 5)

In this situation, the algorithm selects Path 2 because its total cost is lower than Path 1.

<text weight=”medium”>Common algorithms used for shortest path calculation:</text>

  • Dijkstra’s Algorithm
  • Bellman-Ford Algorithm

Advantages of Shortest Path Routing

  • Selects a path with minimum total cost.
  • Helps reduce unnecessary transmission costs.
  • Provides an efficient method for path selection.

Disadvantages of Shortest Path Routing

  • Requires information about network topology and link costs.
  • Recalculating routes may require additional processing.
  • The selected path may become unsuitable if network conditions change and the routing information is not updated.

B. Flooding

Flooding is a routing technique in which a router forwards an incoming packet through all outgoing links except the link from which the packet arrived.

In this method, the router does not calculate a specific best path. Instead, it sends copies of the packet through multiple available paths.

As a result, multiple copies of the same packet may travel through the network. This increases the possibility that at least one copy will reach the destination.

To prevent packets from circulating continuously, flooding uses techniques such as hop count limits, sequence numbers, and duplicate packet detection.

Working of Flooding

  1. The source device sends a packet to the first router.
  2. The router receives the packet and checks its destination.
  3. It creates copies of the packet.
  4. These copies are forwarded through all outgoing links except the incoming link.
  5. Other routers repeat the same process.
  6. The packet copies travel through different paths, and the destination receives one or more copies.

Example of Flooding

Suppose Computer A wants to send a packet to Computer D through a network containing multiple routers.

When Router 1 receives the packet, it forwards copies through all available outgoing links. Other routers continue forwarding the copies until they reach Computer D or their forwarding limits are reached.

Advantages of Flooding

  • Simple to implement.
  • Does not require complete routing information.
  • Increases the possibility of packet delivery when a path is available.
  • Useful for broadcasting and certain network discovery operations.

Disadvantages of Flooding

  • Creates multiple copies of the same packet.
  • Increases network traffic.
  • Wastes bandwidth and network resources.
  • May cause congestion if not properly controlled.

C. Flow-Based Routing

Flow-Based Routing is a routing technique in which routes are selected by considering the amount of traffic flowing through different network links.

A flow refers to a group of packets travelling between a source and destination or following a particular traffic pattern.

In this method, the routing algorithm considers factors such as link capacity, traffic volume, transmission delay, and network utilization.

The main objective is to select routes that can carry traffic efficiently without overloading particular communication links.

Working of Flow-Based Routing

  1. The network is examined to identify available communication links.
  2. Information about the traffic volume on different links is collected.
  3. The capacity and delay of each link are considered.
  4. The routing algorithm evaluates the available paths.
  5. A suitable path is selected based on traffic conditions and network performance.

Example of Flow-Based Routing

Suppose two paths are available between Computer A and Computer D.

  • Path 1 has high traffic and heavy congestion.
  • Path 2 has lower traffic and sufficient available bandwidth.

Flow-based routing may select Path 2 to reduce congestion and improve data transmission.

Advantages of Flow-Based Routing

  • Helps distribute network traffic efficiently.
  • Reduces the possibility of overloading particular links.
  • Can improve network resource utilization.

Disadvantages of Flow-Based Routing

  • Requires information about network traffic and link capacity.
  • Collecting traffic information can create additional overhead.
  • Calculating suitable routes may be complex.

2. Adaptive Routing Algorithms (Dynamic Routing)

Adaptive Routing Algorithms are routing techniques in which routers change or update their routing decisions according to current network conditions.

These algorithms collect information about the network, such as traffic conditions, link failures, congestion, and network topology.

Based on the collected information, routers can select new routes whenever required.

Adaptive routing is useful in large networks where network conditions may change frequently.

The important types of adaptive routing algorithms are:

A. Distance Vector Routing

Distance Vector Routing is an adaptive routing technique in which each router maintains information about the distance and direction to reach different destination networks.

In this method, routers exchange routing information with their neighboring routers at regular intervals or when routing changes occur.

Each router uses the received information to calculate the best available path to different destinations.

The distance is commonly measured using hop count, although the routing metric depends on the protocol.

Working of Distance Vector Routing

  1. Each router maintains a routing table containing destination networks, distances, and next-hop information.
  2. Routers share their routing information with their neighboring routers.
  3. Each router receives routing updates from its neighbors.
  4. It compares the available routes and calculates the distance to each destination.
  5. The router selects the route with the lowest metric.
  6. The routing table is updated whenever a better route is discovered.

Example of Distance Vector Routing

Suppose Router A wants to send data to Network D.

It receives routing information from Router B and Router C.

  • Through Router B, the distance to Network D is 4 hops.
  • Through Router C, the distance to Network D is 2 hops.

Router A selects Router C because it provides a route with fewer hops.

Advantages of Distance Vector Routing

  • Simple to understand and implement.
  • Requires less network topology information than link-state routing.
  • Suitable for small networks.

Disadvantages of Distance Vector Routing

  • Routing updates may take time to reach all routers.
  • Can experience routing loops.
  • May suffer from the count-to-infinity problem.

Link State Routing is an adaptive routing technique in which each router collects information about the links and network topology to calculate suitable paths to different destinations.

Unlike distance vector routing, routers distribute link-state information so that other routers can build a map of the network.

Each router uses this information to calculate the shortest paths using Dijkstra’s Shortest Path First (SPF) algorithm.

  1. Each router identifies its directly connected neighboring routers.
  2. It collects information about the status and cost of its connected links.
  3. The router creates Link State Advertisements (LSAs) containing this information.
  4. The link-state information is distributed to other routers in the routing area.
  5. Each router builds a network topology database.
  6. Dijkstra’s algorithm is used to calculate the shortest paths.
  7. The routing table is updated with the selected routes.

Suppose Router A needs to send a packet to Router D.

The network contains two possible paths:

  • Path 1: A → B → D
  • Path 2: A → C → D

The router examines the network topology and link costs. It then uses Dijkstra’s algorithm to calculate the shortest path and select the most suitable route.

  • Provides detailed information about network topology.
  • Calculates suitable shortest paths.
  • Responds to network topology changes.
  • Generally converges faster than traditional distance-vector protocols in many network environments.
  • Requires more memory and processing power.
  • Maintaining network topology information can be complex.
  • Exchanging link-state information creates network overhead.

C. Hierarchical Routing

Hierarchical Routing is a routing technique in which a large network is divided into smaller sections called regions or areas.

Instead of maintaining detailed routing information about every router in the entire network, routers maintain detailed information about their own region and summarized information about other regions.

This approach reduces the size of routing tables and makes routing more manageable in large networks.

Working of Hierarchical Routing

  1. The entire network is divided into smaller regions or areas.
  2. Each region contains multiple routers.
  3. Routers maintain detailed routing information about their own region.
  4. Information about other regions is represented using summarized routing information.
  5. When a packet needs to travel to another region, it is forwarded through the appropriate gateway router.
  6. The packet reaches the destination region and is delivered to the destination device.

Example of Hierarchical Routing

Suppose a large organization has offices in Hyderabad, Bengaluru, and Chennai.

Each office can be treated as a separate network region. Routers within each region maintain detailed information about their local networks, while communication between regions takes place through gateway routers.

This reduces the need to maintain complete routing information for the entire organization at every router.

Advantages of Hierarchical Routing

  • Reduces routing table size.
  • Makes large networks easier to manage.
  • Improves routing scalability.
  • Reduces the amount of routing information that must be maintained by individual routers.

Disadvantages of Hierarchical Routing

  • Designing network regions can be complex.
  • Route selection may not always provide the globally shortest path.
  • Communication between different regions may require additional routing steps.

D. Path Vector Routing

Path Vector Routing is an adaptive routing technique in which routers maintain information about the complete path used to reach a destination network.

Instead of considering only the distance or cost of a route, it considers the sequence of autonomous systems through which the route passes.

This helps routers make routing decisions based on path information and routing policies.

Working of Path Vector Routing

  1. A router receives routing information from neighboring routers.
  2. The routing information contains the destination network and the path of autonomous systems.
  3. The router examines the available paths.
  4. It selects a suitable path based on routing policies and path attributes.
  5. The selected route is advertised to neighboring routers.
  6. The routing information is updated when network routes change.

Example of Path Vector Routing Protocol

BGP (Border Gateway Protocol) is the most important example of a path-vector routing protocol.

It is used to exchange routing information between different autonomous systems on the Internet.

Advantages of Path Vector Routing

  • Supports routing between large independent networks.
  • Helps prevent routing loops using path information.
  • Supports policy-based routing decisions.

Disadvantages of Path Vector Routing

  • Configuration can be complex.
  • Route selection may take time.
  • Requires careful management of routing policies.

Difference Between Adaptive and Non-Adaptive Routing Algorithms

BasisAdaptive RoutingNon-Adaptive Routing
MeaningChanges routes based on network conditionsUses predefined routes
Other NameDynamic RoutingStatic Routing
Route SelectionUses current network informationUses predefined routing information
Route UpdatesUpdates routes dynamicallyDoes not automatically update routes
Network ChangesCan respond to network changesDoes not automatically respond
ComplexityMore complexComparatively simple
OverheadGenerally higherGenerally lower
ExamplesDistance Vector, Link State, Path VectorFixed Routing, Flooding, Flow-Based Routing in traditional classification

Routing algorithms are essential for transferring data packets from a source device to a destination device through computer networks. They help routers select suitable paths based on different factors, such as distance, link cost, network traffic, and network topology.

Routing algorithms are mainly classified into adaptive and non-adaptive routing algorithms. Non-adaptive routing includes techniques such as shortest path routing, flooding, and flow-based routing. Adaptive routing includes distance vector routing, link state routing, hierarchical routing, and path vector routing.

Each routing algorithm has its own working method, advantages, and limitations. The selection of a suitable routing algorithm depends on the size, structure, traffic conditions, and requirements of the network.