Network Layer: Routing and Packet Switching

Introduction to the Network Layer

• The network layer's job is to get packets from the sender to the destination
• The Network Layer enables end-to-end delivery, unlike the Data Link Layer that transfers frames across a single link.
• Delivering packets involves traversing multiple intermediate routers.

Functions of the Network Layer

• Routing determines the optimal path for packets using network topology data
• Congestion Control prevents network overload through efficient traffic distribution.
• Internetworking facilitates communication across different networks.

Packet Switching (Store-and-Forward Mechanism)

• Routers (Carrier's Equipment) forward packets within the network
• Hosts (Customer's Equipment) send and receive packets
• Packets move from one router to the next until they arrive at the final destination.
• Each router briefly stores a packet before sending it onward.

Services Provided to the Transport Layer

• The Network Layer offers both Connectionless and Connection-Oriented Services

Connectionless Service (Datagram Subnet)

• It does not require prior setup.
• Individual packets are routed independently and can take different paths.
• Each packet is fully addressed.

Connection-Oriented Service (Virtual Circuit Subnet)

• Establish a fixed path (virtual circuit) before transmission
• All packets follow the predetermined route.
• The service needs setup and teardown phases.

Connectionless Service (Datagram Subnet) example

• A process on host sends a large message to a process on another host
• Messages are divided into packets routed based on network conditions.
• Routers dynamically update their routing tables to optimize delivery.

Connection-Oriented Service (Virtual Circuit Subnet) example

• A predefined virtual circuit is established before data transmission
• If a third host connects, a new connection identifier may be required to avoid conflicts.
• Label switching replaces connection identifiers as packets move through routers.

Routing in the Network Layer

• Routing Algorithms determine the best path for packets
• Routing decisions are made once for virtual circuits during connection setup
• Routing decisions are made for each packet individually for datagrams.

Optimal Routing Principles

• Aims to minimize packet delay, maximize network throughput and minimize hops
• Optimality Principle: If the path from I to J to K is optimal, then the sub-path from J to K is also optimal.

Shortest Path Routing (Dijkstra's Algorithm)

• It represents networks as graphs
• Nodes represent routers in the graph
• Edges represent communication links in the graph
• Weights are assigned to the link costs (distance, delay) in the graph
• Dijkstra’s Algorithm finds the shortest path between nodes.

Steps of Dijkstra's Algorithm

• Begin by setting the source node distance to 0, and all others to infinity
• Select the node with the shortest distance and mark it as permanent
• Update distances to neighboring nodes.
• Repeat until all nodes have the permanent state

Dijkstra's Algorithm variations

• Setting link weight to 1 finds the path with the fewest hops.
• Setting link weight to delay finds the fastest path.

Distance Vector Routing (Dynamic Routing Algorithm)

• Routers maintain a table with the best outgoing link and estimated distance for each destination.
• Routers exchange distance information with neighbors, updating periodically or when changes happen.

Distance Vector Routing example

• A router estimates delays to its direct neighbors
• It calculates the best routes to other destinations using neighbors' info
• The shortest path is chosen based on these computations.

Link State Routing

• Replaced Distance Vector Routing due to slow convergence in modern networks
• Steps involve discovering neighbors, measuring delays, broadcasting information, constructing a topology map, and computing shortest paths

Link State Routing Key Techniques

• HELLO packets discover neighboring routers
• ECHO packets are used to measure link delay
• Flooding distributes link-state information across the network.

True or False Questions

• The Network Layer delivers packets, not frames, across networks (False).
• Connection-oriented services route packets along a fixed path, not independently (False).
• Datagram subnets do not require pre-set paths (True).
• Store-and-forward packet switching involves intermediate storage (False).
• Dijkstra's algorithm does indeed find the shortest path in a network graph (True).
• Link State Routing involves broadcasting delay information, not entire routing tables (False).

Multiple-Choice Questions

• The main function of the Network Layer is packet delivery from source to destination.
• Connection-Oriented Routing requires a virtual circuit to be established before transmission.
• Dijkstra’s Algorithm finds the shortest path in a network.
• Link State Routing shares full network topology, while Distance Vector Routing only shares distance estimates.

Short Answer Questions

• Connection-oriented service establishes a fixed route while connectionless service routes each packet independently
• Routers in Distance Vector Routing learn about network changes from neighboring routers update exchanges.
• Link State Routing is more efficient because it provides a complete network view for more accurate path calculation.