Network Layer Design Issues: Understanding Routing Algorithms in Computer Networks Network Layer: Design Issues & Routing Algorithm

There are three key design issues to consider in the network layer of computer networks.

Store and Forward Packet Switching
Services Provided to the Transport Layer
2.1. Implementation of Connectionless Service
2.2. Implementation of Connection-Oriented Service
Comparison of Virtual Circuit and Datagram Networks

Let’s delve deeper into each of these design issues.

Contents

Store and forward packet switching

In store and forward packet switching, a source host transmits a packet to the destination host.

In the diagram above, H1 and H2 are hosts, and H1 is sending the packet 1 to H2 through various routers (A, B, C, D, E, F).

The host transmits the packets to the nearest router, in this case, A.
The router A stores the packet until it’s fully arrived. It verifies that the processing of the link is completed by performing a checksum.
Then it is forwarded to the next router along the path until it reaches the destination host.

The host sends the packets to the nearest router, in this case, A. Router A efficiently receives and stores packets to ensure secure data transmission. It verifies packet integrity through checksum verification before forwarding to the next hop router along the network path to the destination host.

To summarize:

Host sends packets to nearest router.
Router receives and stores packets to ensure secure data transmission.
Router verifies packet integrity through checksum verification before forwarding to next hop router.
The process repeats until it reaches the destination host.

Services Provided to the Transport Layer

Connection-Oriented Service

In a connection-oriented service, a path from the source router to the destination router must be established before sending any data packets. This connection is termed a virtual circuit (VC).

Connectionless Service

In contrast, a connectionless service allows packets to be injected into the network individually, without requiring advance setup. Here, packets are often referred to as datagrams.

Packet Switching

Implementation of Connection-Oriented Service

A prime example of a connection-oriented service is the telephone system. A virtual circuit network establishes a connection between two hosts, ensuring that all packets follow the same route.

Implementation of Connectionless Service

This service mirrors the postal system, where each packet has a destination address and can take different routes to reach its destination.

Comparison of Virtual Circuits and Datagram Networks (comparison of connection-oriented and connectionless services)

Issue	Datagram Network	Virtual-Circuit Network

Circuit setup	Not needed	Required
Addressing	Each packet contains the full source and destination address	Each packet contains a short VC number
State information	Routers do not hold the state information about connections	Each VC requires router table space per connection
Routing	Each packet is routed independently	The route is chosen when VC is set up; all packets follow it
Effect of router failures	None, except for packets lost during the crash, the other packets find a new route.	All VCs that pass through failed routers are terminated
Quality of service	Difficult	Easy, if enough resources can be allocated in advance for each virtual circuit
Congestion control	Difficult	Easy, if enough resources can be allocated in advance for each virtual circuit

What is Routing?

Routing involves forwarding a packet in a network to its intended destination. The primary goals of routing include:

Correctness:
Simplicity:
Robustness:
Stability:
Fairness:
Optimality:

Classification of Routing Algorithms

Routing algorithms are classified into adaptive routing algorithms and non-adaptive routing algorithms.

Adaptive routing algorithms

As the name suggests, these types of algorithms are dynamic in nature. It means that they change their routing decisions looking at the topology and traffic of the network. The routers get their information from either the neighbouring routers or from all of them, Depending on the type of algorithm used. The optimization parameters are distance, hop counts, and transit time. These can be further classified into centralized, isolated and distributed systems.

Centralized routing algorithm: In this type, a central node gets information about the network topology, traffic, and also about the other nodes. This then transmits the information to the respective routers. The advantage of having this system is that only one node is required to keep the information. The disadvantage of having this type of system is that all the information is within one central node, so if that goes down then the entire network comes down. This is a single point of failure and it makes the system less robust.

Isolated routing algorithm: In this type, the node decides the routing path without seeking information from other nodes. The sending node doesn’t know about the status of any particular link. The disadvantage of having this method is that the packet may be sent to a congested link, which may result in a delay. Examples of this type of algorithm include hot potato and backward learning.

Distributed routing algorithm: In this type, the node receives information from the neighbouring nodes and then takes the decision about which way to send the packet. The disadvantage is that if it sends the packet and then receives information about congestion then the packet may be delayed.

Non-adaptive routing algorithms

These algorithms are non-adaptive in nature. They don’t consider parameters such as the type of topology or traffic. A route is decided beforehand when the network is booted and the routers download this information. They can’t adapt if there is an error in the present route because they are static. They are further classified into flooding and random walk.

Flooding:

In this method, the node that receives a packet sends it to all the neighbouring nodes except the one it received the node from. One of the problems of flooding is that packets may go in a loop. Sometimes routers will receive multiple copies of the same packet which may be undesirable. To tackle this problem, three solutions are provided, sequence numbers, hop counts, and spanning tree.

Sequence numbers: Each packet has some metadata. In this, a sequence number is attached to the packet. When a node receives the packet it checks the source address and the sequence number and matches it whether it previously sent it forward. If it has already been sent forward then the packet is discarded. Else, it sends the packet forward.

Hop count: Every packet has a hop count associated with it. When a new node sees this packet, the hop count is decremented by one. When the hop count reaches zero, the packet is discarded. Some times a maximum value of hop count is assigned to it. The packet begins with zero and is incremented by one by each node until it reaches the maximum value and then it’s discarded.

Spanning tree: A spanning tree is routed at the source. Nodes then send the packet only on the link which leads to the destination node. This is only possible if nodes have information about the network topology.

Flooding is a good technique but it’s not practical for day to day applications. It’s an overkill for resources. But because this system is so robust, it is used in government networks and military applications.

Random walk:

This is also a highly robust system. The node sends the packet to its neighbouring node. In a highly connected network, the packets have a good way of finding alternative routes. It is implemented by sending the node to the least-queued node.

Routing Algorithms

Shortest Path Routing

Determining optimal routes involves various algorithms and criteria such as minimum hops, transmission delays, and queuing delays.

Dijkstra’s algorithm: Finds the shortest path using a graph representation of the network.
Distance vector routing (Bellman Ford):
Link-state routing:

Network Layer Design Issues: Understanding Routing Algorithms in Computer Networks