---
title: "Short note: Routing algorithm in data communication"
subject: "Telecommunications"
chapter: 8
key: "semester_8/telecommunications:routing-algorithm-data-comm"
source: https://www.bctengineer.com/q/semester_8/telecommunications/routing-algorithm-data-comm
site: BCT Engineering
---

# Short note: Routing algorithm in data communication

Telecommunications · Chapter 8: Data Communication

- Asked in: 2069 Bhadra (old course), 10 marks; 2065 Magh (old course), 10 marks (asked 2 times)
- Video: [Routing in Computer Networks](https://www.youtube.com/watch?v=duXDA2Rb-68) — Engineering Funda
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_8/telecommunications/routing-algorithm-data-comm
- Whole chapter: https://www.bctengineer.com/md/semester_8/telecommunications/chapter-8

## Question

Write a short note on routing algorithm in data communication.

## Short answer

A routing algorithm decides the output line for packets and maintains routing tables, aiming for correctness, robustness, stability, fairness and low overhead. Optimal routes to a destination form a sink tree. Algorithms are static (shortest path, flooding, flow-based) or dynamic (centralized, isolated, distributed distance-vector or link-state).

## Answer

**Routing** is the process of choosing a path for packets from the source node to the destination node through a network of routers (packet switches). The **routing algorithm** is the part of the network layer software that decides on which output line an incoming packet should be sent. It builds and updates the **routing table** of each node.

#### Desirable properties of a routing algorithm
- **Correctness and simplicity.**
- **Robustness:** keeps working when links or nodes fail or traffic changes.
- **Stability:** routes should converge to a fixed set and not oscillate.
- **Fairness and optimality:** gives fair service to all and minimises a cost such as delay or hop count.
- **Low overhead:** little control traffic and processing.

#### Optimality principle and sink tree
If router J is on the optimal path from I to K, then the optimal path from J to K also lies on the same route. Hence the optimal routes from all sources to one destination form a tree rooted at the destination, called the **sink tree**. Routing algorithms try to find and use sink trees.

#### Classification

```text
           Routing algorithms
          /                  \
 Non-adaptive (static)    Adaptive (dynamic)
  - Shortest path          - Centralized
  - Flooding               - Isolated (hot potato)
  - Flow-based             - Distributed
                              . Distance vector
                              . Link state
```

**1. Non-adaptive (static) routing:** routes are computed in advance (offline) and loaded into routers; they do not change with traffic or topology.
- **Shortest path routing (Dijkstra):** the network is a graph; each link has a weight (distance, delay, cost); the path of least total weight is chosen.
- **Flooding:** every incoming packet is sent on every outgoing line except the one it came from. A hop counter or sequence numbers stop endless copies. Very robust (used in military networks and to spread link-state packets) but wasteful.
- **Flow-based routing:** uses both topology and the known average traffic between node pairs to choose routes that minimise average delay.

**2. Adaptive (dynamic) routing:** routes change automatically as topology and load change.
- **Centralized:** a Routing Control Centre collects information from all nodes, computes routes and sends tables to routers. Optimal but a single point of failure.
- **Isolated:** each node decides using only local information, e.g. **hot potato** routing sends the packet on the shortest output queue.
- **Distributed:** each node exchanges information with others.
  - **Distance vector (Bellman-Ford):** each router keeps a table of (destination, distance, next hop) and periodically sends it to its neighbours. A router updates its entry as $D_x(y) = \min_v \{c(x,v) + D_v(y)\}$. Simple, but slow convergence and the **count-to-infinity** problem. Used in RIP.
  - **Link state:** each router discovers its neighbours and link costs, floods a **link state packet** to all routers, so every router knows the whole topology and runs **Dijkstra's algorithm** to find shortest paths. Fast convergence, no count-to-infinity; used in OSPF and IS-IS.

**3. Hierarchical routing:** in large networks routers are grouped into regions (areas, domains). A router knows the full detail of its own region and only one route to each other region, which keeps tables small.

**4. Broadcast and multicast routing:** send one packet to all or to a group of hosts, using spanning trees or reverse path forwarding.

#### Comparison of the two main dynamic methods

| Point | Distance vector | Link state |
|---|---|---|
| Knowledge | Only neighbours' tables | Whole topology |
| Algorithm | Bellman-Ford | Dijkstra |
| Information sent | Full table, to neighbours | Own link costs, to all (flooding) |
| Convergence | Slow, count-to-infinity | Fast |
| Resources | Low memory, CPU | More memory, CPU |
| Example | RIP | OSPF, IS-IS |

#### Metrics used
Hop count, delay, bandwidth, load, reliability and cost. In telephone-type data networks the route is fixed at call set-up (virtual circuit); in datagram networks each packet is routed separately, so routing must be fast and adaptive.

Good routing gives low delay, high throughput, balanced load and survives failures, which is why it is the central function of the network layer.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does the optimality principle lead to?
   A. Flooding is optimal
   B. Optimal routes from all sources to one destination form a sink tree rooted at it
   C. Routes must be recomputed per packet
   D. All routes are equal in cost
   Answer: B. If J is on the best path from I to K, the rest of that path is also best from J, giving a tree. (Key point: Sink tree)

2. In flooding, how are endless copies prevented?
   A. By using Dijkstra
   B. By hot potato queues
   C. By a hop counter or sequence numbers
   D. By sending only on the best line
   Answer: C. Each packet is sent on all lines except the input one, and limited by a hop counter or sequence numbers. (Key point: Flooding)

3. How does a distance-vector router update its distance to destination y?
   A. It floods its link costs to all routers
   B. D_x(y) = min over neighbours of c(x,v) + D_v(y)
   C. D_x(y) = max over neighbours of c(x,v) + D_v(y)
   D. It runs Dijkstra on the full map
   Answer: B. Bellman-Ford takes the minimum of neighbour cost plus neighbour's distance. (Key point: Distance vector)

4. Which is true of link-state compared with distance-vector routing?
   A. It knows only neighbour tables
   B. It is slow and suffers count-to-infinity
   C. It floods link costs, builds the whole topology, converges fast and has no count-to-infinity
   D. It is used in RIP
   Answer: C. Link state (OSPF, IS-IS) uses Dijkstra on the full map; RIP is distance vector. (Key point: DV vs LS)

## Related in Telecommunications

- [Switching techniques in data communication](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Aswitching-techniques-data-comm) — Telecommunications, chapter 8, asked 3×
- [Flow control mechanisms in data communication](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Aflow-control-mechanisms) — Telecommunications, chapter 8
- [Flow control in data communication network](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Aflow-control-network) — Telecommunications, chapter 8
- [Adaptive and non-adaptive routing algorithms](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Aadaptive-nonadaptive-routing) — Telecommunications, chapter 8, asked 3×
- [Static and dynamic routing algorithms](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Astatic-dynamic-routing) — Telecommunications, chapter 8
- [Routing, flow control and dynamic routing](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Arouting-flow-control-dynamic) — Telecommunications, chapter 8

## Related in other subjects

- [Short note: Viterbi decoding algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Aviterbi-decoding-algorithm) — Wireless Communication, chapter 6, asked 4×
- [Optimal equalizer weights using MSE algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Amse-optimal-weights) — Wireless Communication, chapter 5, asked 3×
- [Binary search with algorithm and example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-algorithm-example) — Data Structure and Algorithm, chapter 8, asked 4×
- [Algorithm for infix to postfix conversion](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ainfix-postfix-algorithm) — Data Structure and Algorithm, chapter 2, asked 3×