Address Mapping-Error reporting and multicasting - Delivery, Forwarding and Routing

algorithms, Distance Vector Routing, Link State Routing. Dijkstra

Address Mapping, Error Reporting, and Multicasting

These are key functions within the Network Layer that support the primary task of packet
delivery.

Address Mapping

A computer on a network has two main addresses: a logical address (like an IP address) used
for routing across different networks, and a physical address (like a MAC address) used for
delivery within a single local network (LAN). Address mapping is the process of translating
one type of address into another.

 Address Resolution Protocol (ARP): This is the most common mapping process.
When a device needs to send a packet to another device on the same local network,
it knows the destination IP address but needs the corresponding MAC address to
create the frame for the data link layer.

o How it works: The source device broadcasts an ARP Request packet to the
entire LAN, asking, "Who has this IP address?"

o The device with that IP address replies with an ARP Reply packet containing
its MAC address, sent directly to the original source.

o The source device then stores this IP-to-MAC mapping in its ARP cache for
future use.

 Reverse Address Resolution Protocol (RARP): This is an older protocol used by

diskless workstations that know their MAC address but need to be assigned an IP
address at boot time. It's largely been replaced by more robust protocols like BOOTP
and DHCP.

Error Reporting and Control Messages

The Internet Protocol (IP) is an "unreliable" or "best-effort" protocol. It doesn't have built-in
mechanisms to report errors if a packet is lost, discarded, or encounters a problem. This is
where the Internet Control Message Protocol (ICMP) comes in. ICMP works alongside IP to
provide error reporting and network diagnostics.

ICMP messages are encapsulated within IP packets. Key message types include:

 Destination Unreachable: Sent by a router when it cannot find a path to the final
destination.

 Time Exceeded: Sent by a router when a packet's Time-To-Live (TTL) field reaches
zero. This prevents packets from looping endlessly in the network.
  Echo Request / Echo Reply: These are used by the ping utility. A host sends an Echo
Request to a target, and the target responds with an Echo Reply, allowing you to
check connectivity and measure round-trip time.

 Redirect: Sent by a router to inform a host on the same local network that there's a
better route to a particular destination.

Multicasting

Multicasting is a communication method where a single packet is sent from one source to
multiple interested destinations simultaneously. It's a one-to-many model, more efficient
than sending multiple individual packets (unicasting) and less wasteful than sending to every
device on the network (broadcasting).

 Use Cases: Common applications include video conferencing, live streaming, and
online gaming.

 Internet Group Management Protocol (IGMP): For a host to receive multicast traffic,
it must join a multicast group. IGMP is the protocol used by hosts and routers to
manage membership in these groups. A host sends an IGMP message to its local
router to signal that it wants to receive packets addressed to a specific multicast
group address (a special Class D IP address).

Delivery, Forwarding, and Routing

These three terms describe how a packet gets from its source to its destination.

 Delivery: This refers to the final step of handing the packet to the destination host.

o Direct Delivery: The source and destination are on the same physical
network. The sender can use ARP to find the destination's MAC address and
send the frame directly.

o Indirect Delivery: The source and destination are on different networks. The
sender sends the packet to its default gateway (a local router), which is
responsible for getting it closer to the destination.

 Forwarding: This is the action a router takes when it receives a packet. It involves
examining the packet's destination IP address, looking it up in its routing table, and
sending the packet out the appropriate interface (port) towards the next hop or the
final destination. Forwarding is a local decision made by a single router.

 Routing: This is the overall process of creating the routing tables that forwarding
depends on. Routing involves routers communicating with each other using routing
protocols to learn about the network's topology and determine the best paths to all
possible destinations. Routing is a global process involving multiple routers.

Routing Algorithms
Routing algorithms are the logic used by routing protocols to calculate the best paths
through a network. They fall into two main categories.

Distance Vector Routing

This is one of the simplest routing approaches. Each router maintains a routing table that
lists all known destinations, the distance (metric, e.g., hop count) to reach them, and the
next router (the "vector") on the path.

 Core Idea: Routers only know about their immediate neighbors. They periodically
share their entire routing table with these neighbors. This is sometimes called
"routing by rumor" because a router learns about the rest of the network from its
neighbors' perspectives.

 Algorithm: It's based on the Bellman-Ford algorithm.

 Example Protocol: Routing Information Protocol (RIP), which uses hop count as its
metric.

 Weakness: It suffers from the count-to-infinity problem. If a link goes down, routers
can get stuck in a loop, incrementally increasing their hop count to a now-
unreachable destination until it reaches a maximum value. This leads to slow
convergence.

Link State Routing

This is a more modern and robust approach. Instead of sharing their entire routing tables,
routers build a complete map of the network's topology.

 Core Idea: Every router has a complete picture of the network, including all other
routers and the state (up/down) and cost (metric) of the links connecting them.

 How it Works:

1. Discover Neighbors: Each router discovers its directly connected neighbors.

2. Flood Link State Advertisements (LSAs): Each router creates a small packet
called an LSA that describes its own links and their costs. This LSA is then
"flooded" (sent) to all other routers in the network.

3. Build Topology Map: Each router collects all the received LSAs to build an
identical, complete map of the network.

4. Calculate Shortest Paths: With the complete map, each router independently
runs a Shortest Path First (SPF) algorithm, like Dijkstra's algorithm, to
calculate the best path from itself to every other destination.

 Example Protocol: Open Shortest Path First (OSPF).

  Advantage: It converges much faster than distance vector and is less prone to routing
loops.

Dijkstra's Algorithm Explained 💡

Dijkstra's algorithm is the cornerstone of link-state routing. It's used to find the shortest path
from a single source node to all other nodes in a weighted graph.

The Logic: It works by maintaining a set of "visited" nodes. It starts at the source node and
iteratively selects the unvisited node with the lowest known distance from the source. It
then "relaxes" the paths to the neighbors of this newly visited node, meaning it checks if the
path through this new node is shorter than any previously known path.

Example

Let's find the shortest path from node A to all other nodes in the network below. The
numbers on the links represent the "cost" or "distance".

Initial State:

 Visited Set: {} (empty)

 Unvisited Set: {A, B, C, D, E, F}

 Distance Table: We'll track the shortest distance from A and the previous node in the
path.

Node Shortest Distance from A Previous Node

A 0 N/A

B $\infty$ N/A

C $\infty$ N/A

D $\infty$ N/A

E $\infty$ N/A

F $\infty$ N/A

Step-by-Step Execution:

1. Visit A (Current Node: A, Distance: 0)

  Examine neighbors of A: B and C.

 Update distance to B: $0 + 2 = 2$. (Path: A -> B)

 Update distance to C: $0 + 5 = 5$. (Path: A -> C)

 Visited: {A}

Node Shortest Distance from A Previous Node

A 0 N/A

B 2 A

C 5 A

D $\infty$ N/A

E $\infty$ N/A

F $\infty$ N/A

2. Visit B (Next smallest distance is B with 2)

 Examine neighbors of B: C and D.

 Update distance to C: Current is 5. Path via B is $2 + 2 = 4$. Since $4 < 5$, we update
it. (Path: A -> B -> C)

 Update distance to D: Current is $\infty$. Path via B is $2 + 3 = 5$. We update it.

(Path: A -> B -> D)

 Visited: {A, B}

Node Shortest Distance from A Previous Node

A 0 N/A

B 2 A

C 4 B

D 5 B
 Node Shortest Distance from A Previous Node

E $\infty$ N/A

F $\infty$ N/A

3. Visit C (Next smallest distance is C with 4)

 Examine neighbors of C: E.

 Update distance to E: Current is $\infty$. Path via C is $4 + 4 = 8$. We update it.

(Path: A -> B -> C -> E)

 Visited: {A, B, C}

Node Shortest Distance from A Previous Node

A 0 N/A

B 2 A

C 4 B

D 5 B

E 8 C

F $\infty$ N/A

4. Visit D (Next smallest distance is D with 5)

 Examine neighbors of D: E and F.

 Update distance to E: Current is 8. Path via D is $5 + 6 = 11$. Since $11 > 8$, no
change.

 Update distance to F: Current is $\infty$. Path via D is $5 + 8 = 13$. We update it.

(Path: A -> B -> D -> F)

 Visited: {A, B, C, D}
 Node Shortest Distance from A Previous Node

A 0 N/A

B 2 A

C 4 B

D 5 B

E 8 C

F 13 D

5. Visit E (Next smallest distance is E with 8)

 Examine neighbors of E: F.

 Update distance to F: Current is 13. Path via E is $8 + 3 = 11$. Since $11 < 13$, we
update it. (Path: A -> B -> C -> E -> F)

 Visited: {A, B, C, D, E}

Node Shortest Distance from A Previous Node

A 0 N/A

B 2 A

C 4 B

D 5 B

E 8 C

F 11 E

6. Visit F (Last node, distance 11)

 All nodes have been visited. The algorithm terminates.

Final Result

The final table gives us the shortest path from A to every other node. We can construct the
path by backtracking using the "Previous Node" column. For example, the path to F is found
by: F <- E <- C <- B <- A, which reversed is A -> B -> C -> E -> F with a total cost of 11.

Unicast Communication and Link State Routing

Unicast means the transmission from a single sender to a single receiver. It is a point-to-
point communication between the sender and receiver. There are various unicast protocols
such as TCP, HTTP, etc.

 TCP (Transmission Control Protocol) is the most commonly used unicast protocol. It is
a connection-oriented protocol that relies on acknowledgment from the receiver
side.

 HTTP stands for HyperText Transfer Protocol. It is an object-oriented protocol for

communication.

Unicast Routing

Major Protocols of Unicast Routing

1. Distance Vector Routing: Distance-Vector routers use a distributed algorithm to

compute their routing tables.

2. Link-State Routing: Link-State routing uses link-state routers to exchange messages

that allow each router to learn the entire network topology.
 3. Path-Vector Routing: It is a routing protocol that maintains the path that is updated
dynamically.

Link State Routing

Link State Routing is a protocol where each router learns the entire network topology
instead of just neighbor information. Using this knowledge, routers calculate the shortest
path to every destination with Dijkstra’s algorithm.

Key Features:

1. Neighborhood Knowledge: Each router shares information about its directly

connected links (cost and identity) rather than the full routing table.

2. Flooding: This information is broadcast to all routers in the network so that everyone
has the same view of the topology.

3. Information Sharing: Updates are sent only when changes occur (not periodically).

Phases of LSR:

1. Reliable Flooding: Every router eventually learns the complete network graph.

2. Route Calculation: Each router applies Dijkstra’s algorithm to compute the optimal
path to every other node.

Features of Link State Routing Protocols

 Link State Packet: A small packet that contains routing information.

 Link-State Database: A collection of information gathered from the link-state packet.

 Shortest Path First Algorithm (Dijkstra algorithm): A calculation performed on the

database results in the shortest path

 Routing Table: A list of known paths and interfaces.

Calculation of Shortest Path

To find the shortest path, each node needs to run the famous Dijkstra algorithm. Let us
understand how can we find the shortest path using an example.

Note: We use a boolean array sptSet[] to represent the set of vertices included in SPT. If a
value sptSet[v] is true, then vertex v is included in SPT, otherwise not. Array dist[] is used to
store the shortest distance values of all vertices.

Consider the below graph and src = 0.

Shortest Path Calculation - Step 1

STEP 1: Initially, the shortest path tree set (sptSet) is empty, and the distances are:
{0, ∞, ∞, ∞, ∞, ∞, ∞, ∞} (where ∞ = infinity).

The vertex with the minimum distance is chosen vertex 0.

Add vertex 0 to sptSet i.e sptSet = {0}.
Update distances of vertices adjacent to 0:

 Distance to vertex 1 becomes 4.

 Distance to vertex 7 becomes 8.

So, the distance array is updated to:

{0, 4, ∞, ∞, ∞, ∞, ∞, 8}

The following subgraph shows vertices and their distance values. Vertices included in SPT are
included in GREEN color.
Shortest Path Calculation - Step 2

STEP 2: Pick the vertex with minimum distance value and not already included in SPT (not in
sptSET). The vertex 1 is picked and added to sptSet. So sptSet now becomes {0, 1}. Update
the distance values of adjacent vertices of 1. The distance value of vertex 2 becomes 12.

Shortest Path Calculation - Step 3

STEP 3: Pick the vertex with minimum distance value and not already included in SPT (not in
sptSET). Vertex 7 is picked. So sptSet now becomes {0, 1, 7}. Update the distance values of
adjacent vertices of 7. The distance value of vertex 6 and 8 becomes finite (15 and 9
respectively).
Shortest Path Calculation - Step 4

STEP 4: Pick the vertex with minimum distance value and not already included in SPT (not in
sptSET). Vertex 6 is picked. So sptSet now becomes {0, 1, 7, 6}. Update the distance values of
adjacent vertices of 6. The distance value of vertex 5 and 8 are updated.

Shortest Path Calculation - Step 5

We repeat the above steps until sptSet includes all vertices of the given graph. Finally, we get
the following Shortest Path Tree (SPT).
Shortest Path Calculation - Step 6

Characteristics of Link State Protocol

 Requires a large amount of memory.

 Shortest path computations need more CPU cycles.

 Quickly reacts to topology changes.

 Authentication mechanisms can be used.

 No split horizon techniques are needed/possible.

 Example protocol: OSPF (Open Shortest Path First).

Protocols of Link State Routing

1. Open Shortest Path First (OSPF)

2. Intermediate System to Intermediate System (IS-IS)

Open Shortest Path First (OSPF)

 Type: Link-state, intradomain (interior) routing protocol developed by IETF.

 Nature: Open standard, classless (supports VLSM and CIDR).

 Updates: Multicast to [Link] (all OSPF routers) and [Link] (designated routers).

 Implementation: Runs at the network layer over IP, using protocol number 89.

 Algorithm: Uses Shortest Path First (SPF), i.e., Dijkstra’s algorithm.

 Advantage: Supports subnetting flexibility, fast convergence, and secure neighbor

authentication.

Intermediate System to Intermediate System (IS-IS)

  Type: Standardized link-state routing protocol for the OSI model.

 Identification: Routers are identified by a System ID.

 Updates: Sent via CLNS (Connectionless Network Service), so IS-IS does not require IP
connectivity between routers.

 Use Case: Widely used in large service provider networks due to scalability.

Comparison between Distance Vector Routing and Link

State Routing
Distance Vector Routing Link State Routing

Bandwidth required is less due to Bandwidth required is more due

local sharing, small packets and to flooding and sending of large
no flooding. link state packets.

Based on local knowledge, since Based on global knowledge, it

it updates table based on have knowledge about entire
information from neighbours. network.

Make use of Bellman Ford Make use of Dijakstra's

Algorithm. algorithm.

Traffic is less. Traffic is more.

Converges slowly i.e, good news

spread fast and bad news spread Converges faster.
slowly.

Count of infinity problem . No count of infinity problem.

Persistent looping problem i.e, No persistent loops, only

loop will be there forever. transient loops.

Practical implementation Practical implementation

Distance Vector Routing Link State Routing

is RIP and IGRP. is OSPF and ISIS.