Routing Algorithms

In a computer network, packets may have multiple possible paths to reach their destination. So, how does a router decide which path should be used?

This is where routing algorithms come in.

A routing algorithm is a method used by routers to determine the best path for forwarding packets from a source network to a destination network.

The "best" path does not always mean the physically shortest path. A routing algorithm can consider factors such as hop count, bandwidth, delay, cost, reliability, and network policies.

              ┌── Router B ──┐
Source ─ Router A            ── Destination
              └── Router C ──┘

        Which path is better?
                 ↓
          Routing Algorithm

Why Do We Need Routing Algorithms?

Imagine a network with hundreds of routers. There could be many possible paths between two devices.

A router needs a systematic way to decide:

• Which path should be selected?

• Which route is more efficient?

• What should happen if a path fails?

• How should routing information be updated?

Routing algorithms provide the logic needed to answer these questions.

How Does a Routing Algorithm Choose a Path?

Routing algorithms use one or more metrics to evaluate paths.

A routing metric is a value used to determine how desirable a route is.

Common metrics include:

Different routing protocols use different metrics and rules.

Types of Routing Algorithms

Routing algorithms can be classified in several ways. Some important categories are:

1. Distance Vector

2. Link State

3. Path Vector

4. Flooding

5. Hierarchical Routing

Let's understand the important ones.

1. Distance Vector Routing

In Distance Vector routing, each router maintains information about the distance or cost to different destinations and the direction, or next hop, used to reach them.

Routers exchange routing information with their neighbors.

Router A ←→ Router B ←→ Router C
   ↑           ↑           ↑
Exchange routing information

A router gradually learns which destinations can be reached through its neighboring routers.

Example

Suppose:

A ──1── B ──1── C

Router A can learn that C is reachable through B with a total cost of 2.

Advantages

• Relatively simple

• Easy to understand

• Requires routers to communicate with neighboring routers

Disadvantages

• Can converge more slowly after network changes

• Can experience routing loops in some situations

• Limited knowledge of the complete network topology

RIP is a well-known example of a distance-vector routing protocol.

2. Link State Routing

In Link State routing, routers build a more complete view of the network topology.

Each router learns information about network links and distributes that information to other routers in the routing domain.

The router then uses a shortest-path algorithm to calculate the best routes.

Network Information
        ↓
Build Topology Database
        ↓
Calculate Best Paths
        ↓
Routing Table

A common algorithm associated with link-state routing is Dijkstra's Shortest Path First (SPF) algorithm.

Advantages

• Faster convergence than traditional distance-vector approaches

• Better knowledge of network topology

• Works well in larger networks

Disadvantages

• More complex

• Requires more memory and processing

• Routers need to maintain topology information

OSPF is a common example of a link-state routing protocol.

3. Path Vector Routing

Path Vector routing is commonly used for routing between autonomous systems.

Instead of simply maintaining a numerical distance, routers can maintain information about the path through autonomous systems.

The best-known example is BGP (Border Gateway Protocol).

For example:

AS 100 → AS 200 → AS 300

BGP can use the sequence of autonomous systems and other path attributes when selecting routes.

Advantages

• Suitable for very large networks

• Supports routing policies

• Helps prevent certain routing loops between autonomous systems

Disadvantages

• More complex

• Route selection involves policies and multiple attributes

4. Flooding

In Flooding, a router forwards a packet through multiple available paths rather than selecting only one specific route.

             Router B
            ↗         ↘
Source → Router A       Destination
            ↘         ↗
             Router C

Flooding can help ensure that data reaches its destination, but it can generate a large amount of unnecessary traffic.

To prevent packets from circulating forever, techniques such as hop limits, sequence numbers, or controlled flooding can be used.

Advantages

• Simple concept

• Can be useful when route information is unavailable

• Can provide high reachability

Disadvantages

• Creates duplicate traffic

• Can waste network bandwidth

• Not suitable as a general routing strategy for modern large networks

5. Hierarchical Routing

Large networks can become difficult to manage if every router needs detailed information about every other router.

Hierarchical routing divides a large network into different levels or areas.

             Large Network
            /             \
       Area 1             Area 2
       /   \               /   \
    Routers              Routers

Routers can maintain detailed information about their own area while using summarized information for other areas.

This helps improve scalability.

OSPF, for example, supports hierarchical organization using areas.

Distance Vector vs Link State

This is one of the most important comparisons.

Dijkstra's Algorithm

One important algorithm used in link-state routing is Dijkstra's algorithm, also called the Shortest Path First (SPF) algorithm.

Its basic idea is to find the lowest-cost paths from one node to all other nodes.

For example:

       2
   A ───── B
   |       |
  5|       |1
   |       |
   C ───── D
       2

A routing protocol can use link costs to calculate which paths are preferable.

The router runs the algorithm on its topology information and uses the results to build its routing table.

You don't need to memorize the mathematical details at this stage. The important idea is:

Dijkstra's algorithm finds shortest or lowest-cost paths through a network graph.

Routing Algorithm vs Routing Protocol

These terms are related but not the same.

Routing Algorithm

The algorithm is the method used to calculate or select routes.

Examples:

• Dijkstra's Shortest Path First

• Bellman-Ford-based approaches

Routing Protocol

A routing protocol defines how routers exchange routing information and apply rules to select routes.

Examples:

• RIP

• OSPF

• BGP

So:

Algorithm → How the route is calculated

Protocol → How routers exchange information and make routing decisions

Simple Example

Suppose a router has three possible paths to a destination:

Path A → Cost 10
Path B → Cost 5
Path C → Cost 8

If the routing protocol uses this cost as its primary metric, it will generally prefer:

Path B → Cost 5

However, real routing protocols can use more complex rules and multiple attributes. So the lowest numerical value is not universally the definition of "best" across all routing protocols.

Conclusion

Routing algorithms are methods used to determine suitable paths for forwarding packets through a network.

The major concepts to understand are:

• Distance Vector → Learns routing information from neighbors

• Link State → Builds network topology information

• Path Vector → Uses path information and policies between autonomous systems

• Flooding → Forwards through multiple paths

• Hierarchical Routing → Divides large networks into manageable areas

The easiest way to remember the main idea is:

Routing Algorithm = The logic used to decide which path network traffic should take.

Once this concept is clear, learning routing protocols such as RIP, OSPF, and BGP becomes much easier.