Computer Networks (AD-602) - Unit 3 Short Notes

How unit 3 is examined

This unit covers the network layer's role, shortest-path routing (Dijkstra and Bellman-Ford), hierarchical, broadcast and multicast routing, IP addressing and the IPv4 header, fragmentation, ICMP and IPv4 versus IPv6; fragmentation and Dijkstra carry the marks.

Network Layer: Need, Services Provided, Design issues

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>The network layer moves packets from the source host to the destination host across many networks, using logical addresses to route and forward them.</mark>

Key points.

1. The need: the data link layer delivers frames only between neighbouring nodes, so a layer is needed to carry data across several different networks (internetworking).
2. Logical addressing gives every host a unique, hierarchical IP address, independent of its hardware address.
3. Routing chooses the best path from source to destination, and forwarding moves each packet to the next hop using the routing table.
4. Services offered to the transport layer are independent of router technology: connectionless (datagram, as in IP) or connection-oriented (virtual circuit).
5. Other services are packet switching, congestion control and internetworking, with fragmentation to fit different networks.
6. Design issues are store-and-forward packet switching, the choice of datagram or virtual-circuit service, routing algorithm, congestion control and quality of service.
7. Examples of protocols: IP for delivery, ICMP for errors, and routing protocols such as RIP and OSPF.

Answer frame. Open with the definition; then need, role (addressing, routing, forwarding), services, design issues; close with IP, ICMP and routing protocols as examples.

Asked: [7 marks] (May 2024) Why is the Network Layer necessary in computer networking? Discuss its role and importance and also explain the key services provided by the Network Layer.

Routing algorithms: Least Cost-Routing

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Least-cost routing selects, among all paths from source to destination, the path whose total link cost (hops, delay, bandwidth or money) is smallest.</mark>

Key points.

1. Each link carries a cost, and the cost of a path is the sum of its link costs.
2. The network is modelled as a weighted graph: routers are nodes and links are weighted edges.
3. Dijkstra's algorithm finds the least-cost path from one source to all others; it is used in link-state routing such as OSPF, where every router knows the full map.
4. Bellman-Ford gives the same result by distance-vector exchange with neighbours only.
5. When link costs change, routers recompute and the tables converge to the new least-cost paths.

Example. Use the graph and distance table worked under Dijkstra's algorithm below: from A, the least-cost path to E is A-C-F-E with cost 20.

Asked: [7 marks] (May 2023) Discuss the Least Cost routing algorithm with suitable example.

Dijkstra's algorithm

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Dijkstra's algorithm is a greedy algorithm that finds the shortest path from one source node to every other node in a graph with non-negative edge weights.</mark>

Steps.

Step 1: Set dist[source]=0 and dist[all others]=infinity; the visited set is empty.
Step 2: Pick the unvisited node u with the smallest dist and mark it visited (permanent).
Step 3: Relax every edge (u,v): if dist[u]+w(u,v) < dist[v], set dist[v]=dist[u]+w and pred[v]=u.
Step 4: Repeat Steps 2-3 until all nodes are visited.

Key points.

1. The greedy principle: the unvisited node with the smallest tentative distance can never be improved later, so it is final.
2. Relaxation is $dist[v]=\min(dist[v],\,dist[u]+w(u,v))$.
3. A predecessor array lets us read off the actual path by walking back from the destination.
4. Complexity is $O(V^2)$ with an array and $O(E\log V)$ with a priority queue.
5. Limitation: it fails with negative edge weights, because a finalised node could later be improved.

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-01" viewBox="0 0 510 295" width="510" height="295" role="img" aria-label="Example graph; source A"><style>#dsfig-u3-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-01 .t{fill:#16181D;font-weight:500}#dsfig-u3-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-01 .dot{fill:#16181D}#dsfig-u3-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-01 .ah{fill:#454C5A}#dsfig-u3-01 .ah.hi{fill:#2340B8}#dsfig-u3-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-01 .e{stroke:#B1B7C3}html.dark #dsfig-u3-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-01 .t{fill:#E6E8ED}html.dark #dsfig-u3-01 .t.inv{fill:#0F1115}html.dark #dsfig-u3-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-01 .dot{fill:#E6E8ED}html.dark #dsfig-u3-01 .ann{fill:#8FA3FF}html.dark #dsfig-u3-01 .lbl{fill:#858D9C}html.dark #dsfig-u3-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-01 .ah{fill:#B1B7C3}html.dark #dsfig-u3-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M53.4,155.6 L155.6,53.4"/><path class="e" d="M55.8,179.5 L153.2,244.5"/><path class="e" d="M58.3,174.2 L322.7,249.8"/><path class="e" d="M169,59 L169,236"/><path class="e" d="M188,40 L322,40"/><path class="e" d="M180.9,240.2 L329.1,54.8"/><path class="e" d="M188,255 L322,255"/><path class="e" d="M354.4,53.4 L456.6,155.6"/><path class="e" d="M454.2,179.5 L356.8,244.5"/><g class="wl"><rect x="94.9" y="95.5" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="104.5" dy=".35em" text-anchor="middle">7</text></g><g class="wl"><rect x="94.9" y="203" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="212" dy=".35em" text-anchor="middle">9</text></g><g class="wl"><rect x="177.3" y="203" width="26.4" height="18" rx="9"/><text class="t" x="190.5" y="212" dy=".35em" text-anchor="middle">14</text></g><g class="wl"><rect x="155.8" y="138.5" width="26.4" height="18" rx="9"/><text class="t" x="169" y="147.5" dy=".35em" text-anchor="middle">10</text></g><g class="wl"><rect x="241.8" y="31" width="26.4" height="18" rx="9"/><text class="t" x="255" y="40" dy=".35em" text-anchor="middle">15</text></g><g class="wl"><rect x="241.8" y="138.5" width="26.4" height="18" rx="9"/><text class="t" x="255" y="147.5" dy=".35em" text-anchor="middle">11</text></g><g class="wl"><rect x="245.4" y="246" width="19.2" height="18" rx="9"/><text class="t" x="255" y="255" dy=".35em" text-anchor="middle">2</text></g><g class="wl"><rect x="395.9" y="95.5" width="19.2" height="18" rx="9"/><text class="t" x="405.5" y="104.5" dy=".35em" text-anchor="middle">6</text></g><g class="wl"><rect x="395.9" y="203" width="19.2" height="18" rx="9"/><text class="t" x="405.5" y="212" dy=".35em" text-anchor="middle">9</text></g><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="169" cy="255" r="18"/><text class="t" x="169" y="255" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="341" cy="40" r="18"/><text class="t" x="341" y="40" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="341" cy="255" r="18"/><text class="t" x="341" y="255" dy=".35em" text-anchor="middle">F</text><circle class="n" cx="470" cy="169" r="18"/><text class="t" x="470" y="169" dy=".35em" text-anchor="middle">E</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Example graph; source A</figcaption></figure>

Example. Source A; entries are distance/predecessor.

Shortest distances from A: B=7 (A-B), C=9 (A-C), F=11 (A-C-F), D=20 (A-C-D), E=20 (A-C-F-E).

Answer frame. Open with the definition and the shortest-path problem; state the steps; draw the graph and the table above (for a paper graph, use its own numbers in the same table); close with complexity and the non-negative limitation.

Pitfall: Do not pick a node by its position; always pick the smallest tentative distance among unvisited nodes.

Asked: [7 marks] (May 2024) Describe the basic idea behind Dijkstra's Algorithm for finding the shortest path in a graph with suitable example. Asked: [7 marks] (Jun 2025) A network consists of 6 nodes (A, B, C, D, E, F) with given link costs. Using Dijkstra's algorithm, determine the shortest path from node A to all other nodes.

Bellman-Ford algorithm

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Bellman-Ford finds shortest paths from a source by repeatedly relaxing all edges; distributed, it is the distance-vector routing used in RIP.

Key points.

1. Each router keeps a vector of its distance to every destination and exchanges it only with neighbours.
2. The update is $D_x(y)=\min_v\{c(x,v)+D_v(y)\}$ over all neighbours $v$.
3. It handles negative edge weights, unlike Dijkstra, and needs $V-1$ rounds; complexity is $O(VE)$.
4. It suffers from count-to-infinity, reduced by split horizon.

Hierarchical Routing

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Hierarchical routing divides the network into regions (areas); routers hold detailed routes only for their own region and one entry per other region.</mark>

Key points.

1. In flat routing every router stores an entry for every other router, so tables grow with network size.
2. In two-level hierarchy, routers inside a region know each other, and gateway routers connect regions; the Internet uses autonomous systems in this way.
3. Benefits: smaller routing tables, less update traffic and processing, and scalability.
4. Limitation: paths may be longer than optimal, because a region is reached through a fixed gateway.
5. Limitation: configuration and management are more complex.

Answer frame. Open with the definition; give a two-level example (regions R1-R3 with gateways); write the table; close with benefit versus limitation.

Asked: [7 marks] (Jun 2025) Explain the concept of hierarchical routing. What are its benefits and limitations compared to flat routing?

Broadcast Routing

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Routing is the process of selecting the path along which packets travel from source to destination; broadcast routing sends a packet to all hosts in the network.</mark>

Key points.

1. Routing is needed because source and destination usually are not directly connected, so routers must choose the next hop.
2. Flooding sends a copy on every outgoing line except the arrival line; it is simple but creates duplicates.
3. Reverse path forwarding forwards a packet only if it arrived on the link the router itself would use to reach the source.
4. Spanning-tree broadcast sends along a tree with no loops, so each node gets exactly one copy.
5. Multicast routing sends to a selected group of hosts only, which are managed by IGMP.

Answer frame. Define routing; explain broadcast methods; define multicast; close with the table.

Asked: [7 marks] (May 2023) What is Routing? Differentiate between broadcast routing and Multicast routing?

Multicast Routing

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Multicast routing delivers one copy of a packet to every member of a group, using a group (Class D) address.

Key points.

1. Hosts join or leave a group using IGMP, and routers keep the membership list.
2. Routers build a multicast tree from source to members, copying a packet only where the tree branches.
3. Protocols are DVMRP, MOSPF and PIM.
4. It saves bandwidth compared with sending many unicast copies.

IP Addresses, Header format, Packet forwarding

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. An IPv4 address is a 32-bit logical address, written as four decimal bytes, that identifies a host's connection to the network.

Key points.

1. It has a network part and a host part; classes A to E start with bit patterns 0, 10, 110, 1110, 1111 (A 1-126, B 128-191, C 192-223, D multicast, E reserved).
2. The IPv4 header is 20 to 60 bytes: Version (4 bits), IHL, Type of Service, Total Length (16 bits), Identification, Flags, Fragment Offset (13 bits), TTL, Protocol, Header Checksum, Source and Destination address, Options.
3. TTL is decremented at every router and the packet is discarded at zero, which stops loops.
4. Packet forwarding: the router looks up the destination network in its table, using the longest prefix match, and sends the packet to the next hop, or delivers directly if the network is attached.

Fragmentation and reassembly

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Fragmentation is the splitting of a datagram into smaller fragments so that each fits the MTU (maximum transmission unit) of the next network; reassembly is rebuilding the original datagram from those fragments at the destination.</mark>

Key points.

1. Different networks have different MTUs (Ethernet 1500 bytes), so a datagram larger than the MTU of a link must be split; this is why heterogeneous networks need fragmentation.
2. Each fragment is a complete datagram with its own header; only the header is copied, and the data is divided.
3. Identification (16 bits) is copied into all fragments, so the destination knows which datagram they belong to.
4. Fragment offset gives the position of the data in the original datagram in units of 8 bytes; so every fragment except the last has data that is a multiple of 8.
5. The MF (More Fragments) flag is 1 on all fragments but the last; the DF flag set to 1 forbids fragmentation, and the router then drops the packet and sends an ICMP error.
6. Transparent fragmentation: the next router rejoins the fragments, so later networks never see them. Non-transparent fragmentation: fragments travel on and are reassembled only at the destination, as IP does.
7. Impact on performance: extra header overhead, extra router work, loss of any single fragment forces the whole datagram to be resent, and fragments may arrive out of order.
8. Path MTU discovery sends packets with DF set to find the smallest MTU on the path and so avoids fragmentation.
9. IPv6 routers never fragment; only the source fragments, using a Fragment extension header, after path MTU discovery.

Example. A 4000-byte datagram (20-byte header, 3980 data) crosses a link with MTU 1500. The data per fragment is at most $1500-20=1480$, which is a multiple of 8.

Offsets are $1480/8=185$ and $2960/8=370$; the destination reassembles fragments with the same Identification in offset order until it gets MF=0.

Answer frame. Open with the definition and MTU; explain why it is needed; describe identification, offset, MF using the example table; then transparent versus non-transparent; for the IPv6 variant, add points 9 and 8; close with the performance impact.

Pitfall: Offset is in units of 8 bytes, not bytes.

Asked: [7 marks] (May 2023, May 2024, Jun 2025) What is Fragmentation and Reassembly? Why do we need fragmentation and reassembly at network? Explain. Also: Describe the operation of IP fragmentation and reassembly, discuss the conditions under which it occurs and its impact on network performance. Also: Describe the process of packet fragmentation and reassembly in IPv4. How does IPv6 handle fragmentation differently?

ICMP

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. ICMP (Internet Control Message Protocol) is the companion of IP that reports errors and gives diagnostic information about packet delivery.

Key points.

1. ICMP messages travel inside IP datagrams (protocol number 1) and are either error reports or queries.
2. Error messages include destination unreachable, time exceeded (TTL zero), source quench and redirect.
3. Query messages include echo request and echo reply, used by ping.
4. Traceroute sends packets with increasing TTL and reads the time-exceeded replies to list the routers.

Comparative study of IPv4 & IPv6

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. IPv6 is the successor of IPv4, with 128-bit addresses instead of 32-bit ones.

Last-minute revision

• Network layer: logical addressing, routing, forwarding, internetworking; IP is connectionless.
• Least-cost path = minimum sum of link costs.
• Dijkstra: greedy, needs non-negative weights, $O(V^2)$ or $O(E\log V)$.
• Relaxation: $dist[v]=\min(dist[v],dist[u]+w)$.
• Example graph from A: B=7, C=9, F=11, D=20, E=20.
• Bellman-Ford: distance vector, $V-1$ rounds, allows negative weights.
• Hierarchical routing: small tables, scalable, but suboptimal paths.
• Broadcast: flooding, RPF, spanning tree; multicast uses IGMP and Class D.
• IPv4 header 20-60 bytes; TTL stops loops.
• Fragment offset is in 8-byte units; MF=0 on last fragment; 4000 bytes at MTU 1500 gives 1480, 1480, 1020.
• ICMP: ping uses echo, traceroute uses TTL.
• IPv6: 128-bit, 40-byte header, no router fragmentation.

Memory hooks

• Dijkstra: "pick the smallest, then relax the rest".
• Fragment fields: I-O-M (Identification, Offset, More fragments).
• Offset times 8 gives bytes.
• Flat table = entry per router; hierarchical = entry per region.
• ICMP: "ping = echo, traceroute = TTL".

Coverage checklist

• Network Layer: Need, Services Provided, Design issues: May 2024 question.
• Routing algorithms: Least Cost-Routing algorithm: May 2023 question.
• Dijkstra's algorithm: May 2024, Jun 2025 questions.
• Bellman-ford algorithm: no recent questions.
• Hierarchical Routing: Jun 2025 question.
• Broadcast Routing: May 2023 question.
• Multicast Routing: no recent questions.
• IP Addresses, Header format, Packet forwarding: no recent questions.
• Fragmentation and reassembly: May 2023, May 2024, Jun 2025 questions.
• ICMP: no recent questions.
• Comparative study of IPv4 & IPv6: no recent questions.