University of Melbourne · FACULTY OF COMPUTER SCIENCE

COMP30023 · Computer Systems

- one subject, every graph, every model, every mark

Computer Science14 Chapters13-page Bible

Our own words - no uploaded lecturer files

Updated for this semester

Chapter 12 of 13 · COMP30023

Network-Layer Routing and Control

Week 11 covers how packets find paths: the distinction between routing (building the tables) and forwarding (using them), link-state routing with Dijkstra's shortest-path algorithm, and network-layer control protocols such as ICMP, DHCP and ARP. Tracing Dijkstra to find a shortest path and cost, and explaining the age field in link-state routing, are flagship exam questions.

In this chapter

What this chapter covers

01Forwarding (data plane, per-packet table lookup) vs routing (control plane, building the tables)
02Good routing-algorithm properties (correctness, robustness, stability); optimising hop count or link cost
03Static vs adaptive routing; flooding as a robust but inefficient benchmark controlled by TTL
04The optimality principle and the sink tree; Dijkstra's shortest-path algorithm over a non-negative-weight graph
05Dijkstra node states (unseen / tentative-open / permanent-closed) and the (distance, predecessor) labels
06Link-state routing's five steps: discover neighbours, set costs, build the LSP, reliably flood, run Dijkstra (OSPF)
07The link-state sequence number and age field (TTL-like, decremented, discarded at 0) guarding stale info
08Internet control protocols: ICMP (echo/ping, time-exceeded/traceroute), DHCP, MAC addresses and ARP

Worked example · free

Tracing Dijkstra's shortest path

Q [4 marks]. On an undirected weighted graph with vertices A, B, C, D, E and edges A-B = 2, A-C = 5, B-C = 1, B-D = 7, C-D = 3, C-E = 8, D-E = 2, find the shortest path and its cost from A to E, showing the label table step by step. (4 marks)

+1Initialise: A = (0, −) as the working (closed) node; every other vertex starts (∞, −). Open A's neighbours with distance = edge weight: B = (2, A), C = (5, A).
+1The lowest-cost open node is B (2) → make it closed. Relax B's neighbours: C via B = 2 + 1 = 3, which beats 5, so update C = (3, B); D via B = 2 + 7 = 9, so D = (9, B).
+1The lowest-cost open node is now C (3) → close it. Relax: D via C = 3 + 3 = 6, which beats 9, so update D = (6, C); E via C = 3 + 8 = 11, so E = (11, C).
+1The lowest-cost open node is D (6) → close it. Relax E via D = 6 + 2 = 8, which beats 11, so update E = (8, D). The next lowest open node is E (8), which is the destination, so stop. Follow predecessors back: E ← D ← C ← B ← A. Shortest path A → B → C → D → E with total cost 8.

Shortest path A → B → C → D → E with cost 8. The label table closes nodes in the order A(0), B(2), C(3), D(6), E(8); the final label for E is (8, D), and tracing predecessors D ← C ← B ← A gives the path. Note A → C directly (5) is beaten by A → B → C (3).

Sia tip — Always pick the lowest-cost open node to close next, relax only its neighbours, and update a label only when the new distance is smaller (labels only ever decrease). Keep the predecessor with each label so you can read the path back. Ask Sia to redraw the graph with different weights and check both your closing order and your final path and cost.

Glossary

Key terms

Forwarding vs routing: Forwarding is the data-plane, per-packet act of looking up a destination address in the forwarding table and sending the packet out the right interface. Routing is the control-plane process that builds those tables — the routing algorithm plus a protocol to gather network information.
Dijkstra's shortest-path algorithm: Given a graph with non-negative edge weights, it finds shortest paths from a source. Nodes move unseen → tentative(open) → permanent(closed); each step closes the lowest-cost open node and relaxes its neighbours, keeping (distance, predecessor) labels that only ever decrease.
Optimality principle / sink tree: If router J lies on the optimal path from I to K, then the optimal J-to-K path is part of that same route. The set of optimal routes from all sources to one destination forms a sink tree rooted at that destination.
Link-state routing: Each router discovers its neighbours, sets link costs, builds a link-state packet {ID, sequence number, age, neighbours + costs}, reliably floods it to all routers, then runs Dijkstra on the full topology. OSPF is the common link-state protocol; it replaced slow-converging distance-vector routing.
Link-state age field: A field in a link-state packet, decremented roughly once per second and discarded at 0 — a TTL for routing information. It guards against a router that restarts and re-numbers its sequence numbers from 0, ensuring stale link-state data eventually expires.
ICMP / ARP: ICMP is the network-layer control protocol (echo/ping to test reachability, time-exceeded which traceroute exploits with increasing TTL). ARP translates an IP address to a link-layer MAC address by broadcasting 'who owns IP X?'; the owner replies with its MAC address.

FAQ

Network-Layer Routing and Control FAQ

What is the difference between routing and forwarding?

Forwarding is the local, per-packet data-plane action: a router reads a packet's destination address, looks it up in its forwarding table, and sends the packet out the corresponding interface. Routing is the control-plane process of building those tables — a routing algorithm at each router plus a protocol that gathers the topology information the algorithm needs. In short, routing decides the paths; forwarding follows them. The exam often asks you to place each in the data plane or control plane.

How does Dijkstra's algorithm find a shortest path?

Label the source (0, −) and every other node (∞, −), and mark the source as the working node. Repeatedly: relax each neighbour of the working node (new distance = working cost + edge weight, updating the label only if smaller and recording the predecessor), then among all open (tentative) nodes pick the lowest-cost one, make it permanent, and treat it as the new working node. Stop when the destination is closed, and read the path back through the predecessors. Edge weights must be non-negative, and labels only ever decrease.

What does the age field do in link-state routing?

The age field is like a TTL for a link-state packet: it is decremented roughly once per second and the information is discarded when it reaches 0. Its job is to expire stale routing information — in particular it guards against a router that has restarted and begun its sequence numbers again from 0, which could otherwise look 'older' than genuinely current data. Combined with sequence numbers (a newer sequence number supersedes an older one), it keeps flooded link-state information fresh and consistent.

What does ARP do and why can it be a security risk?

ARP (Address Resolution Protocol) translates an IP address into the link-layer MAC address needed to actually send a frame on the local network. A host broadcasts 'who owns IP X?' and the owner replies with its MAC address, which is then cached. It is a security risk because there is no authentication and replies are cached even when unsolicited, so an attacker can send forged replies (ARP spoofing) associating their own MAC with another host's IP — the entry point for many man-in-the-middle attacks on a LAN.

Can AI help me with routing in COMP30023?

Yes. Sia can generate practice graphs and check your Dijkstra label tables and final paths, explain the routing-vs-forwarding and link-state mechanics, or walk through ICMP, DHCP and ARP step by step, checking your reasoning. It is a study aid for the networking half; it does not do your graded exam, quizzes or projects, and University of Melbourne academic-integrity rules apply.

Study strategy

Exam move

Routing is a near-certain exam topic, and a Dijkstra trace is the flagship, so practise it until the mechanics are reflexive: initialise labels, repeatedly close the lowest-cost open node, relax its neighbours (updating only on a smaller distance), and read the path back through predecessors. Do several fresh graphs and always report both the path and its total cost. Alongside the trace, learn the conceptual answers: routing vs forwarding (control plane vs data plane), the five link-state steps and why OSPF mandates Dijkstra, and the purpose of the sequence number and age field. Keep the control-protocol facts ready — ICMP echo/ping and time-exceeded/traceroute, DHCP address leasing, and ARP's IP-to-MAC broadcast with its spoofing risk. These combine for a lot of marks; confirm the exam date on Canvas and keep consolidating toward your WAM.

Working through Network-Layer Routing and Control in COMP30023? Sia is AskSia’s AI Computer Science tutor — ask any COMP30023 Network-Layer Routing and Control question and get a clear, step-by-step explanation grounded in how COMP30023 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.

Keep going — explore the course

A+Everything unlocked

Unlocks this Bible + all 14 of your University of Melbourne subjects - and 1,000+ Bibles across every Australian university.

Sia - your COMP30023 tutor, unlimited, worked the way the exam marks it

The full 13-page Bible + practice bank with worked solutions

Chrome extension - sync your LMS so Sia knows your deadlines

Bilingual EN / Chinese on every Bible and every Sia answer

$25/ month

30-day money-back · cancel in one tap · how it works