Routing Algorithms - Computer Networks

UNIT 4

Network Layer - Design Issues - Routing Algorithms – Congestion Control Algorithms – IP Protocol – IP Addresses – Internet Control Protocols.

Why do we study Network Layer Design Issues?

We study network layer design issues because the network layer is responsible for end-to-end delivery of data across multiple networks, not just a single link.

1. It enables end-to-end communication 🌍

Unlike the data link layer (which only moves frames over one physical link), the network layer ensures that a packet:

Starts at the source host
Travels through multiple routers
Reaches the final destination host

Without proper network layer design, large networks like the Internet simply cannot function.

2. It decides how packets travel (Routing & Path Selection) 🧭

The network layer must:

Understand the network topology (routers + links)
Choose the best path among many possible routes
Adapt when links fail or congestion occurs

Studying its design helps us understand routing algorithms, shortest paths, and dynamic routing decisions.

3. It prevents congestion and resource wastage 🚦

Poor routing can:

Overload some links and routers
Leave other paths completely unused

Network layer design addresses:

Load balancing
Congestion control at the routing level
Efficient utilization of network resources

4. It handles communication between different networks 🌐

When source and destination are in different networks:

Addressing schemes differ
Packet forwarding becomes complex
Inter-network compatibility is required

The network layer (using protocols like IP) solves these internetworking problems.

5. It is the foundation of the Internet (IP) 🧱

The Internet runs on the IP protocol, which belongs to the network layer.
By studying network layer design issues, we understand:

How IP works
How packets are forwarded
Why the Internet scales to billions of devices

1. Store-and-forward packet switching is a packet transmission technique in which each intermediate device (router or switch) receives the entire packet, stores it temporarily, and then forwards it to the next node toward the destination.

Explanation

Data is divided into packets
Each packet is sent independently
At every router:

1. The packet is fully received

2. It is stored in memory

3. Then forwarded to the next hop

Key Features

Ensures error checking before forwarding
Allows routing decisions at each node
Suitable for large and complex networks
Introduces delay due to storage at each hop

Example

The Internet (IP-based networks) uses store-and-forward packet switching, where routers forward packets hop-by-hop until they reach the destination.

2. Services Provided to the Transport Layer

The network layer offers services to the transport layer through the network/transport layer interface. These services must be carefully designed to ensure reliable and flexible communication.

Design Goals of Network Layer Services

Ø Services independent of router technology

The services provided to the transport layer should not depend on how routers are implemented internally.

Routers may differ in hardware or software
Transport layer should work without knowing router details

Ø Transport layer shielded from number, type, and topology of routers

The transport layer should be completely unaware of:

How many routers exist
What type they are
How they are connected

Routing complexity is hidden
Transport layer focuses only on end-to-end communication

Ø Uniform network addressing across LANs and WANs

The network layer must provide a uniform addressing scheme usable by the transport layer, regardless of the underlying network.

Same type of network address used in:

Local Area Networks (LANs)
Wide Area Networks (WANs)

3. Implementation of connectionless service

When the network layer offers a connectionless service, packets are sent individually into the network without establishing a prior connection.

Key Characteristics

· No advance setup is required before sending data

· Each packet is routed independently

· Packets may follow different paths to reach the destination

· Such packets are called datagrams

· The network is called a datagram network

Datagram Transmission Process

Let us assume that the message to be transmitted is four times longer than the maximum packet size. Therefore, the network layer divides the message into four packets: 1, 2, 3, and 4.

These packets are sent one after another to router A.

Routing Tables in Routers

· Every router maintains an internal routing table

· Each table entry contains:

o Destination address

o Outgoing line (next hop)

· Only directly connected lines can be used

· Routing tables may change dynamically

Packet Forwarding at Router A

Initial Situation

· Router A’s initial routing table specifies that packets destined for F should be sent via router C

· Packets 1, 2, and 3:

o Arrive at router A

o Are briefly stored

o Forwarded to C, then to E, and finally to F

Later Situation (Dynamic Routing)

· When packet 4 arrives at router A:

o A traffic jam occurs along the A–C–E path

o Router A updates its routing table

o Packet 4 is sent via router B, even though the destination is still F

This shows that:

· Packets belonging to the same message may take different routes

· Arrival order at destination is not guaranteed

Routing Algorithm

The process that:

· Maintains routing tables

· Updates paths

· Decides where to forward each packet

is called the routing algorithm.

4. Implementation of connection-oriented service

When a connection-oriented service is used, a path from the source router to the destination router is established before any data packets are sent.
This pre-established path is called a Virtual Circuit (VC), and the network is known as a virtual-circuit network.

Connection Setup Phase

· Before data transmission, the network:

o Selects a fixed route from source to destination

o Stores this route in the routing tables of all intermediate routers

· All packets belonging to this connection follow the same path

· This operation is similar to the telephone system

Data Transfer Phase

· Each packet carries a Virtual Circuit Identifier (VCI)

· Routers use the VCI to:

o Look up the routing table

o Forward the packet to the correct outgoing line

· Routing decisions are not made for every packet, only during setup

Connection Release Phase

· When communication ends:

o The connection is terminated

o The virtual circuit is released

o Table entries are removed

Routing Algorithms

Routing algorithms in computer networks are procedures within the network layer that determine the optimal, least-cost path for transferring data packets from source to destination. They ensure efficient traffic direction based on metrics like hop count, latency, or congestion. Main types include adaptive (dynamic) algorithms that adjust to network conditions, and non-adaptive (static) algorithms that use precomputed routes.

1. Optimality Principle

The purpose of a routing algorithm at a router is to decide which output line an incoming packet should go. The optimal path from a particular router to another may be the least cost path, the least distance path, the least time path, the least hops path or a combination of any of the above.

The optimality principle can be logically proved as follows

(a) If router J is on the optimal path from router I to router K, then the optimal path from

J to K also falls along the same route.

(b) The set of optimal routes from all sources to a given destination form a tree rooted at

the destination. Such a tree is called a sink tree.

Example

Consider a network of routers, {G, H, I, J, K, L, M, N} as shown in the figure. Let the optimal route from I to K be as shown via the green path, i.e. via the route I-G-J-L-K. According to the optimality principle, the optimal path from J to K with be along the same route, i.e. J-L-K.

computer routers

Now, suppose we find a better route from J to K is found, say along J-M-N-K. Consequently, we will also need to update the optimal route from I to K as I-GJ- M-N-K, since the previous route ceases to be optimal in this situation. This new optimal path is shown line orange lines in the following figure