Network Layer: Routing and Congestion Control

• The network layer focuses on delivering packets from the source to the destination.
• Reaching the destination involves multiple hops via intermediate routers.
• The network layer differs from the data link layer, which transfers frames across a single link.

Functions of the Network Layer

• Routing involves selecting appropriate paths through the subnet.
• Congestion control prevents overloading certain links while leaving others idle.
• Internetworking handles communication between different networks.

Store-and-Forward Packet Switching

• Carrier's equipment includes routers connected by lines within the shaded oval of a network diagram.
• Customer's equipment includes hosts, located outside the shaded oval of a network diagram.
• Host connections to the subnet utilize leased lines or a LAN and customer-operated routers.
• To send a packet, a host transmits it to the nearest router within the subnet.
• Packets are temporarily stored and then forwarded router to router until they arrive at the destination.

Services Provided to the Transport Layer

• The network layer provides connection-oriented and connectionless services to the transport layer.

Connectionless Service

• No advance setup is needed.
• Packets are injected and routed independently, known as datagrams.
• The subnet is called a datagram subnet.

Connection-Oriented Service

• A path must be established before sending packets.
• The path is called a virtual circuit (VC).
• The subnet is known as a virtual-circuit subnet.

Connectionless Service in Detail

• Process P1 on host H1 needs to send a long message to process P2 on host H2.
• A message that is 4 times larger than the maximum packet size is broken into four packets by the network layer.
• These packets are sent to router A.
• Router A temporarily stores the packets to verify checksums.
• The packets are forwarded to the next node based on A's routing table.
• Packets 1, 2, and 3 are routed from A to C to E to F.
• A traffic jam causes A's routing table to change.
• Packet 4 is routed along a different route to bypass the jam.
• Routing algorithms manage the routing tables.

Connection-Oriented Service in Detail

• Once a virtual circuit is established, the route is stored in the routers’ tables.
• All packets are sent on this route.
• Host H1 sets up connection 1 with host H2, which updates the network table routing and stores it in the first entry.
• A’s first entry is set up to ensure packets with connection identifier 1 are sent from H1 to C and given connection identifier 1.
• C also routes the packet to E with the same connection identifier 1 value.
• H3 establishes connection 1 to H2 but, to avoid conflicts, A assigns a different identifier to the outgoing packets.
• Routers must be able to connection identifiers, otherwise known as label switching.

Comparison of Datagram and Virtual-Circuit Subnets

Routing Algorithms

• Packet forwarding determines the outgoing link for transmission using routing tables.
• Routing algorithms update these tables.
• With virtual circuits, the algorithm decides when the circuit is set up.
• With datagrams, a decision must be made upon every arrival.

Routing Optimality

• Routing algorithms are chosen to optimize objectives like minimizing packet delay, maximizing throughput and minimizing hops..
• The optimality principle states that if router J is on the optimal path between routers I and K, then the optimal path between J and K also lies on the same route.
• If a better route existed, it could be combined with the initial segment to achieve greater route optimization.

Shortest Path Routing

• Represents a network as a graph. Routers are nodes and communication lines are the links.
• Each link as a weight that represents its length.
• Algorithms find the shortest path between nodes corresponding to a pair of routers.

Dijkstra’s Algorithm

• Start by labeling all nodes with the distance from the source node.

• Initially, all labels are tentative, and set to infinity, as the paths are unknown yet.

• Mark the sender A as permanent (black circle) Then,

• Examine each node adjacent to A

• Relabel each node with the distance to A We choose the node with the smallest tentative label and mark it permanent.

• If the {label of B + distance from B to C (respectively E) 9 is labeled (9,B) Choose the node with the smallest tentative label and mark it permanent.

• Repeat until all nodes are permanently labeled giving the shortest path from source-destination.

Dijkstra’s Algorithm Variations

• If each link is equal to 1, it determines the path using the fewest hops.
• If the packet delay over a link is used as weight, it provides the fastest path.

Distance Vector Routing

• Dynamic routing algorithm
• Each router maintains a distance vector table with the best known route to each destination and its outgoing link.
• Tables are updated through neighbor exchanges.
• This was the ARPANET routing algorithm and used on the internet.

Distance Metric

• The router A’s routing table has an entry for each destination network address
• This entry has 2 parts: the preferred outgoing link, and an estimate of the distance from the destination.
• Distance metrics can be a number of hops, time delays (in milliseconds), or the total number of packets queued along the link.
• Each router knows its distance to its neighbors.
• To measure hops, the nearest neighbor distance is equal to one.
• To measure delay, the rotor sends each neighbor a special echo packet that the neighbors will respond to as quickly as possible.
• Estimate delay by ensuring that the round trip time and each router can get an estimate of the delay to its neighbor.

Distance Vector Routing Algorithm Flow

• Every 'T' msec each router sends a destination delays list and likewise, receives a neighboring list. An incoming table from a neighbor 'X' to Router 'Y' has 'Xi' being the estimated delay from the nearest neighbor.
• The destination router will know the delay to router X is 'm' msec and can calculate the formula ''Xi + m = Time''.
• Performing the calculation to determine which routes are best, it then updates and sets new path assignments.

Distance Vector Routing Example

• J measures neighbours A, I H and K to be at respective delay intervals of 8ms, 10ms, 12ms and 6ms.
• The vectors show that the delays from A to B is claims 12ms, 25ms to 'C' and 40 for 'D' etc.
• Router J computes a new route to G, which claims via A (8+18=26ms), also checking via H and K. The lowest time is via route 'H' with a value of 18.
• Router J creates a new routing table and makes the entry to use route (H) with a time of 18MS and does so for all available neighbors.

Link State Routing

• Replaced Distance vector routing, due to the slow convergence.

Steps for Link State Routing

• Discovering the neighbors’ network addresses.
• Measuring the delay to each neighbor.
• Constructing packets with neighbor delays.
• Sending the packet to all routers.
• Finally computing the shortest path to all routers.

Learning about the Neighbors

• Upon booting, a router sends HELLO packet on each outgoing link.
• The device on either node sends an acknowledgment packet containing its network address.

Measuring Link Costs

• Every router transmits to EACH neighbor is echo packet.
• The device on either node sends the sent packets as FAST as possible.
• With the round trip time divided 2, the approximate cost to near routers can be estimated.

Building Link State Packets

• Routers construct link data packets upon regular intervals or whenever an event occurs.

Broadcasting Link State Packets

• Flooding spreads the link state packets to all nodes in the network.
• Each packet contains a number sequence, which increments foreach data being sent.
• Compare the receiving numbered packets, forwarding newest packages whilst discarding old and duplicated entries.
• A life span is assigned during creation and it decrements each time the router forwards the state of the packages. when zero is hit, the package is deleted to prevent infinite travelling

Computing The Shortest Paths

• Routers construct the graph when all packets exist for each destination.
• The Dijkstra algorithm is applied to find shortest paths.
• Routing Tables are updated accordingly.