Link State Routing Protocol

Features of Link State Routing Protocol

Link State routing is a dynamic routing protocol where each router has complete knowledge of the entire network topology. Its key features are:

1. Complete Topology Knowledge: Every router maintains a complete map of the entire network (topology database), unlike distance vector where routers only know about neighbors.

2. Hello Packets: Each router discovers its neighbors by sending "Hello" packets to directly connected routers.

3. Link State Advertisements (LSAs): Each router broadcasts LSAs (containing its identity, neighbors, and link costs) to all routers in the network using flooding.

4. Dijkstra's Algorithm: Each router independently runs Dijkstra's Shortest Path First (SPF) algorithm on its topology database to compute the shortest path to every destination.

5. Fast Convergence: Link state protocols converge much faster than distance vector protocols because topology changes are flooded immediately.

6. Loop-Free Routes: Since every router has the same topology map and runs SPF independently, routing loops are avoided.

7. Incremental Updates: Only changes in the network (not the full table) are advertised, reducing bandwidth usage after initial convergence.

8. Hierarchical Design Support: Supports areas (e.g., OSPF areas) to reduce LSA flooding scope and improve scalability.

9. Examples: OSPF (Open Shortest Path First), IS-IS (Intermediate System to Intermediate System).

How Link State Routing Finds the Shortest Path (Dijkstra's Algorithm)

Steps of the Algorithm

Let:

• N' = set of nodes whose least-cost path is definitively known
• D(v) = current best estimate of cost from source to node v
• p(v) = predecessor node of v on the best path

Algorithm:

1. Initialize:
   - N' = {source}
   - For all nodes v:
       If v is a direct neighbor: D(v) = cost(source, v)
       Else: D(v) = infinity

2. Loop until all nodes are in N':
   a. Find node w NOT in N' with minimum D(w)
   b. Add w to N'
   c. Update D(v) for all neighbors v of w NOT in N':
      D(v) = min( D(v),  D(w) + cost(w, v) )

3. The result gives shortest path from source to all nodes.

Worked Example

Consider the following network with 6 nodes: A, B, C, D, E, F

Link costs (bidirectional):

A -- B : 2
A -- C : 5
B -- C : 3
B -- D : 1
C -- E : 4
D -- E : 2
D -- F : 6
E -- F : 1

Network Diagram:

    2       1
A------B-------D
|      \       |\
5    3  \      | 6
|        \     |
C-------- +    F
 \     (B-C=3) |
  4            1
   \           |
    E----------+
         2
    D----E (cost 2)

Let us find the shortest path from Source = A to all other nodes.

Initialization:

N' = {A}

Iteration 1:

• Node with minimum D not in N': B (D=2)
• Add B to N' → N' = {A, B}
• Update neighbors of B (C, D):
  • D(C) = min(5, 2+3) = min(5, 5) = 5
  • D(D) = min(inf, 2+1) = 3

Iteration 2:

• Minimum D not in N': D (D=3)
• Add D to N' → N' = {A, B, D}
• Update neighbors of D (E, F):
  • D(E) = min(inf, 3+2) = 5
  • D(F) = min(inf, 3+6) = 9

Iteration 3:

• Minimum D not in N': C or E (both D=5, pick C)
• Add C to N' → N' = {A, B, D, C}
• Update neighbors of C (E):
  • D(E) = min(5, 5+4) = min(5, 9) = 5 (no change)

Iteration 4:

• Minimum D not in N': E (D=5)
• Add E to N' → N' = {A, B, D, C, E}
• Update neighbors of E (F):
  • D(F) = min(9, 5+1) = 6

Iteration 5:

• Minimum D not in N': F (D=6)
• Add F to N' → N' = {A, B, D, C, E, F}

Final Shortest Path Table (from A)

Note that C has two paths of equal cost, the direct link A to C of cost 5 and A to B to C of cost 2 plus 3, so either may be entered in the table.

Disadvantages of Link State Routing

Conclusion

Link state routing gives each router a complete and identical map of the network, built from the link state advertisements flooded by every router, and each one then runs Dijkstra's algorithm on that map to compute its own shortest path tree. In the example above the router at A learns costs of 2, 5, 3, 5 and 6 to B, C, D, E and F respectively. Because every router works from the same map, convergence is fast and routing loops are avoided, which is the main advantage over distance vector routing. The cost is memory, processing and flooding overhead, which is why protocols such as OSPF and IS-IS divide a large network into areas.

Differences Between Noise, Distortion, and Attenuation

Definitions and Key Differences

Brief Explanations

1. Attenuation

• Attenuation means the loss of signal energy as the signal propagates through the medium.
• The signal becomes weaker with increasing distance.
• It is measured in decibels (dB).
• Example: A signal sent over a long copper wire arrives with much lower amplitude.

2. Distortion

• Distortion means the signal changes its shape.
• In a composite signal, each frequency component travels at a slightly different speed, causing them to arrive at different times, thus distorting the overall waveform.
• It is common in wired media carrying composite signals.

3. Noise

• Noise is any unwanted signal that mixes with the original signal.
• Types include: thermal noise, induced noise, crosstalk, and impulse noise.
• It is the most unpredictable of the three impairments.
• Measured using the Signal-to-Noise Ratio (SNR).

Summary

All three -- attenuation, distortion, and noise -- are types of transmission impairments that degrade signal quality, but they differ in cause, nature, and effect: attenuation reduces signal strength, distortion alters signal shape, and noise adds unwanted random signals.

MAC Address and CRC Calculation

Given data

• Message M = 1101011011
• Generator polynomial $G(x) = x^3 + x + 1 \Rightarrow$ bit string 1011 (degree 3)

MAC Address (2 marks)

A MAC (Media Access Control) Address is a unique 48-bit hardware identifier assigned to a Network Interface Card by the manufacturer. It operates at the Data Link Layer (Layer 2) of the OSI model.

• 48-bit (6-byte) physical address, written in hexadecimal, e.g. 00:1A:2B:3C:4D:5E
• First 3 bytes = manufacturer (OUI), last 3 bytes = device serial
• Also called physical/hardware address; used for LAN addressing

CRC Calculation (3 marks)

Step 1: Append 3 zeros (degree of G = 3)

$$1101011011 \rightarrow 1101011011000$$

Step 2: Modulo-2 division of 1101011011000 by 1011

The dividend 1101011011000 is 13 bits long. Load its leading four bits into a working register, XOR the divisor 1011 into the register whenever the leading bit of the register is 1, and bring down the next dividend bit after each comparison. The nine bits left after the first group, 0 1 1 0 1 1 0 0 0, are brought down one at a time:

1 1 0 1 | 0 1 1 0 1 1 0 0 0

• Take 1101, XOR 1011 = 0110; drop next 0 → 1100
• 1100 XOR 1011 = 0111; drop next 1 → 1111
• 1111 XOR 1011 = 0100; drop next 1 → 1001
• 1001 XOR 1011 = 0010; drop next 0 → 0100
• 0100 leading 0, no XOR; drop next 1 → 1001
• 1001 XOR 1011 = 0010; drop next 1 → 0101
• 0101 leading 0, no XOR; drop next 0 → 1010
• 1010 XOR 1011 = 0001; drop next 0 → 0010
• 0010 leading 0, no XOR; drop next 0 → 0100

All nine bits have now been brought down and every dividend bit is consumed. The working register holds 0100, and its low-order three bits are the remainder, so the CRC is 100.

Step 3: Remainder (CRC)

$$\text{CRC} = 100$$

Step 4: Transmitted encoded frame

$$\text{Frame} = \text{Message} + \text{CRC} = 1101011011 + 100 = \boxed{1101011011100}$$

Result

Verification: 1101011011100 ÷ 1011 should give remainder 000. Dividing confirms exact divisibility, so the frame is correct.