10  Combined Day 8/9 — Subnetting, forwarding and routing algorithms

Allow approximately 60–90 minutes for the theory and worked examples, followed by 90–110 minutes for the three exercises. Solutions are omitted.

The connection throughout is:

Subnets define address ranges; prefixes describe those ranges in forwarding tables; routing computes paths; each path supplies a next hop; forwarding selects that next hop using the destination address.

1. IPv4 addresses, prefixes and masks

An IPv4 address contains 32 bits, written as four 8-bit octets in dotted decimal.

In a.b.c.d/p:

  • the first \(p\) bits form the network/prefix part (Netzanteil, Netz-ID);
  • the remaining \(h=32-p\) bits form the host part (Hostanteil, Host-ID), identifying an interface within that subnet.

The prefix length belongs to the network configuration: an address alone does not determine its subnet.

Increasing the prefix length fixes more bits, making the represented block smaller. When a parent /p is divided into equal /q subnets, the additional \(q-p\) prefix bits distinguish those subnets.

Historically, a Class-C network meant /24. For these calculations, use the explicitly given CIDR prefix.

Construct a subnet mask from scratch

A subnet mask contains \(p\) leading ones followed by \(32-p\) zeros.

Its ones retain the network bits; its zeros remove the host bits when performing bitwise AND.

  1. Write 255 for every complete group of eight prefix bits.
  2. If \(r\) prefix bits remain in the next octet, write \(r\) leading ones there.
  3. Fill all remaining bits with zeros.

For \(1\le r\le7\), the partial octet has decimal value:

\[ 256-2^{8-r}. \]

Prefix Mask construction Dotted-decimal mask Host bits Total addresses
/20 16 ones, then 11110000, then 8 zeros 255.255.240.0 12 4096
/24 24 ones, then 8 zeros 255.255.255.0 8 256
/27 24 ones, then 11100000 255.255.255.224 5 32

For the reverse conversion, count the leading ones, including the complete 255 octets.

For example:

\[ 255.255.252.0 \]

contains \(8+8+6=22\) leading ones because:

252 = 11111100

Therefore, its prefix is /22.

A CIDR mask must contain contiguous leading ones. 255.255.250.0 is invalid because 250 = 11111010.

Total addresses versus usable host addresses

For a /p block:

\[ h=32-p,\qquad S=2^h\text{ total addresses}. \]

For an ordinary IPv4 LAN in this unit, exclude:

  • the network address, whose host bits are all zero;
  • the broadcast address, whose host bits are all one.

Therefore:

\[ \text{usable interface addresses}=2^h-2. \]

A router’s LAN interface also consumes one usable address. If a requirement counts only end devices, add the necessary router interfaces before sizing the subnet.

Follow the question’s convention. Sheet 10 A2 uses ordinary host counting; A3 explicitly permits all addresses.

For ordinary point-to-point links here, use /30: four total addresses and two usable addresses. A /31 can support a point-to-point link under a separate convention; do not silently switch conventions. A /32 represents one address, often used as a host route.

Thus, \(2^h-2\) is the ordinary LAN rule, not a universal rule for every prefix length.

Network address, host ID and represented range

For address \(A\) and mask \(M\):

\[ N=A\mathbin{\&}M, \]

\[ H=A\mathbin{\&}(\text{32-bit complement of }M). \]

Here:

  • \(N\) is the full network address;
  • \(H\) is the host part with all network bits cleared.

As integers:

\[ H=A-N. \]

Once \(N\) and block size \(S\) are known:

\[ B=N+S-1, \]

where \(B\) is the broadcast address for an ordinary subnet.

Its usable range is:

\[ N+1\quad\text{through}\quad B-1. \]

Address arithmetic treats the address as one 32-bit integer, carrying between octets when necessary. For an aggregate prefix, \(B\) is simply its highest represented address: an aggregate need not describe one physical broadcast subnet.

Worked example: 192.0.2.149/27.

Only the last octet matters:

Address:  10010101   (149)
Mask:     11100000   (224)
AND:      10000000   (128)
Host:     00010101   (21)

The five host bits are 10101.

Therefore:

Quantity Result
Network 192.0.2.128/27
Host ID 21
Broadcast 192.0.2.159
Usable range 192.0.2.129–192.0.2.158
Usable addresses 30

A faster block-boundary method

In the octet containing the prefix boundary, calculate:

\[ \Delta=256-\text{mask octet}. \]

Then:

\[ \text{network octet} = \left\lfloor \frac{\text{address octet}}{\Delta} \right\rfloor\Delta. \]

Earlier octets stay unchanged. Later network-address octets become zero; later broadcast-address octets become 255.

For 172.22.77.203/20:

  • mask: 255.255.240.0;
  • relevant octet: the third;
  • increment: \(256-240=16\);
  • 77 belongs to the interval 64–79.

Therefore:

\[ \text{network}=172.22.64.0/20, \]

\[ \text{broadcast}=172.22.79.255. \]

Notice that the host part extends across two octets. Its numerical host ID cannot be determined from the last octet alone.

Are two addresses in the same subnet?

Under a specified mask \(M\), addresses \(A\) and \(C\) belong to the same subnet exactly when:

\[ (A\mathbin{\&}M)=(C\mathbin{\&}M). \]

Compare their masked network addresses, not merely their first three decimal octets.

2. Subnet allocation: capacity, alignment and VLSM

VLSM (Variable Length Subnet Masking) allocates differently sized subnets within one parent block.

Each ordinary subnet receives a complete power-of-two block, including its network and broadcast addresses.

Reusable allocation procedure

  1. Establish whether requirements mean total addresses or usable interface addresses, and whether gateways are included.

  2. For \(H\) ordinary usable addresses, choose the smallest integer \(h\ge2\) satisfying:

    \[ 2^h-2\ge H. \]

    If all addresses are explicitly usable, use \(2^h\ge H\).

  3. Calculate:

    \[ p=32-h,\qquad S=2^h. \]

  4. Allocate larger blocks first, choosing free, correctly aligned starts.

  5. Record each network, mask, complete range and usable range.

  6. Check containment within the parent, non-overlap and capacity.

Count unused addresses using complete allocated block sizes, rather than requested host counts.

Why alignment matters

A network address must have all host bits zero.

Equivalently, its 32-bit integer value must be divisible by its block size.

A /26 contains 64 addresses. Within one /24, its possible last-octet starts are:

\[ 0,\ 64,\ 128,\ 192. \]

A proposed start .96/26 actually denotes the block beginning at .64; it does not create a /26 beginning at .96.

Short example. Within 192.0.2.0/24, two networks require 50 and 20 usable interface addresses.

Their minimum sizes are:

\[ 64-2\ge50\quad\Rightarrow\quad /26, \]

\[ 32-2\ge20\quad\Rightarrow\quad /27. \]

Allocate:

  • 192.0.2.0/26;
  • 192.0.2.64/27.

Both starts are aligned and the ranges do not overlap.

If the smaller subnet were allocated at .0/27 first, the /26 would need to start at .64, leaving a gap. Largest-first allocation makes packing simpler.

For equal-size subdivision:

\[ \text{number of `/q` subnets within `/p`} = 2^{q-p}. \]

No additional two subnets are subtracted under the conventions used here.

Sheet 10 A3’s special allocation notation

A3 also permits large prefix minus smaller prefix, with all addresses usable.

For example:

10.30.6.0/25 - 10.30.6.124/30

allocates .0–.123 to one address set and reserves .124–.127 separately.

The remainder contains:

\[ 128-4=124\text{ addresses}. \]

It is not itself one CIDR block. This is the exercise’s address-set notation rather than ordinary one-prefix LAN allocation.

A forwarding entry for the covering /25 still matches the reserved /30. If the smaller range needs another output, add a more-specific /30 entry.

Subtracting an allocated range does not change the bits matched by the original prefix.

3. Prefixes, aggregation and longest-prefix matching

A forwarding-table entry associates a destination address range with an outgoing interface and, for a remote destination, a neighboring next-hop router.

A destination \(A\) matches N/p if:

\[ A\mathbin{\&}M_p=N. \]

Use a canonical network address \(N\), with zero host bits.

Convert an address range into one prefix

For an inclusive range \(L\) through \(U\):

  1. Calculate \(S=U-L+1\).

  2. Check that \(S\) is a power of two, say \(2^h\).

  3. Check that \(L\) is aligned: its last \(h\) bits must be zero.

  4. The exact prefix is then:

    \[ L/(32-h). \]

Alternatively, compare the endpoints’ binary forms. After their common leading bits:

  • the lower endpoint must contain only zeros;
  • the upper endpoint must contain only ones.

For example, 192.0.2.64–192.0.2.127 contains 64 addresses and starts at a multiple of 64.

Its last octets are:

64:   01000000
127:  01111111

They share two leading bits, giving \(24+2=26\) prefix bits:

192.0.2.64/26

An arbitrary interval may require several prefixes. The common leading bits of its endpoints can describe a larger containing block, rather than the exact interval.

Route aggregation

Two equal-size prefixes can merge into a prefix one bit shorter when they are the two aligned halves of that parent.

For example:

192.0.2.64/27
192.0.2.96/27

merge into:

192.0.2.64/26

Adjacency alone is insufficient: .32/27 and .64/27 are not the aligned halves of one /26.

For straightforward forwarding aggregation, the merged destinations must use the same next hop/output. More-specific exceptions can override an aggregate where explicitly required.

Longest-prefix matching

Among all matching entries, select the entry with the greatest prefix length.

Use this procedure:

  1. Identify every prefix containing the destination.
  2. Compare their prefix lengths.
  3. Select the largest length and use its output/next hop.

A longer prefix fixes more destination bits, describing a smaller, more specific subset. This supports exceptions within broader routes.

Destination prefix Output
0.0.0.0/0 WAN
10.8.0.0/16 A
10.8.12.0/24 B
10.8.12.128/25 C

Examples:

  • 10.8.12.170 matches all four entries: /25 selects C.
  • 10.8.12.20 matches the first three: /24 selects B.
  • 10.8.13.20 matches /16 and /0: select A.

The /0 entry fixes no bits and matches every destination. It is the default route.

If nothing matches and there is no default, there is no forwarding route.

For a paper table scanned until the first match, sort entries by decreasing prefix length. The underlying rule remains longest-prefix matching, regardless of physical row order.

Adding a narrower exception does not shrink the broader prefix’s represented range. It changes which destinations actually select that broader entry.

4. Routing versus forwarding

Forwarding (Weiterleitung) is a router’s local per-packet action: inspect the destination, match a prefix and select an output.

Routing (Wegewahl) computes or learns the path information used to populate those entries.

For example, routing establishes that the cheapest path to the router serving 10.50.4.0/24 begins through neighbor \(a\). The source installs:

10.50.4.0/24 → next hop a

Forwarding subsequently matches packet destinations against that entry.

Distinction Meaning
Mask/prefix calculation versus path calculation Which addresses belong together versus which sequence of links reaches them
Destination prefix versus next hop Ultimate destination range versus adjacent router receiving the packet next
Longest prefix versus shortest path Most specific matching destination range versus lowest sum of link costs
Predecessor versus next hop Last node before the destination versus first node after the source

Longest-prefix matching does not run Dijkstra for every packet.

Among entries for different matching prefixes, it chooses the most specific prefix even if a broader entry has a smaller route cost.

5. Dijkstra: construct and complete the table

Model the network as a weighted graph:

  • nodes represent routers;
  • edges represent links;
  • \(c(v,w)\) is the cost of link \((v,w)\).

Path cost is the sum of edge costs, not necessarily the number of hops.

Unless specified otherwise, assume an undirected graph with nonnegative costs.

Use the course and 2016-exam notation:

Symbol Meaning
\(N'\) Nodes whose shortest-path costs from source \(u\) are finalized
\(D(v)\) Current tentative cost from \(u\) to \(v\); exact once \(v\in N'\)
\(p(v)\) Predecessor: last node before \(v\) on the currently recorded path

Blank-page procedure

Initialization

Set:

\[ N'=\{u\},\qquad D(u)=0. \]

For every other node \(v\):

  • if adjacent to \(u\), set \(D(v)=c(u,v)\) and \(p(v)=u\);
  • otherwise, set \(D(v)=\infty\) and \(p(v)=-\).

Write the initialization row.

One main iteration per subsequent row

  1. Among nodes outside \(N'\), select \(w\) with the smallest \(D(w)\).

  2. Add \(w\) to \(N'\). Its distance and predecessor are now fixed.

  3. For every neighbor \(v\) of \(w\) still outside \(N'\), calculate:

    \[ \text{candidate}=D(w)+c(w,v). \]

  4. If this is smaller than \(D(v)\), update both:

    \[ D(v)\leftarrow D(w)+c(w,v), \qquad p(v)\leftarrow w. \]

  5. Carry forward unchanged entries and record the row after relaxation.

Stop when all required nodes are finalized. If the smallest remaining distance is infinity, the remaining nodes are unreachable.

Why finalize the smallest tentative distance?

With nonnegative links, a path reaching the selected node through a still-unfinalized node cannot improve its minimum distance: it must first reach a node whose tentative distance is at least as large, then add nonnegative cost.

This supports finalization. Do not subsequently relax nodes already in \(N'\).

Two short iterations

Consider edges:

\[ u-a=3,\quad u-b=7,\quad a-b=2,\quad a-c=6,\quad b-c=1. \]

Phase \(N'\) \(D(a),p(a)\) \(D(b),p(b)\) \(D(c),p(c)\)
Initialization \(\{u\}\) \(3,u\) \(7,u\) \(\infty,-\)
Add \(a\) \(\{u,a\}\) \(3,u\) \(5,a\) \(9,a\)
Add \(b\) \(\{u,a,b\}\) \(3,u\) \(5,a\) \(6,b\)

Adding \(a\):

  • improves \(b\) using \(3+2=5\);
  • discovers \(c\) at \(3+6=9\).

Adding \(b\):

  • improves \(c\) using \(5+1=6\);
  • leaves finalized \(a\) unchanged.

Ties and useful checks

If two unfinalized nodes have the same minimum distance, either may be selected unless a tie rule is specified.

If a relaxation offers an equal-cost alternative, retaining the old predecessor or selecting another equal-cost predecessor can yield valid alternatives, provided finalized nodes remain fixed and predecessor chains form paths to the source.

For this unit:

  • select alphabetically when tentative distances tie;
  • retain the old predecessor on equal candidate cost.

Different valid tie choices can change the predecessor tree and next hops while preserving shortest-path costs. A different cost is not explained by tie handling.

For every final predecessor, check:

\[ D(v)=D(p(v))+c(p(v),v). \]

Also check that:

  • predecessor chains reach the source;
  • finalized distances are nondecreasing.

6. From predecessors to next hops

The predecessor tree contains edges:

\[ (p(v),v) \]

for reachable destinations other than the source.

It encodes complete shortest paths. Forwarding needs their first step.

To derive the next hop from \(u\) toward \(v\):

  1. Start with \(z=v\).
  2. Follow predecessor pointers backward until \(p(z)=u\).
  3. That node \(z\) is the next hop.
  4. Select the source interface connected to \(z\).

If \(p(v)=u\), the next hop is \(v\) itself. An unreachable destination has no predecessor chain or next hop.

Worked example

Suppose:

\[ p(t)=r,\qquad p(r)=b,\qquad p(b)=u. \]

The complete path is:

\[ u\rightarrow b\rightarrow r\rightarrow t. \]

For destination \(t\):

  • predecessor: \(r\);
  • next hop from \(u\): \(b\).

If \(t\) serves 10.50.4.0/24, the source installs an entry for that destination prefix, using next hop \(b\) and its interface toward \(b\).

The graph identifies routers; attached-network information identifies destination prefixes. Dijkstra does not calculate subnet masks.

For a directly connected LAN, use the local interface without an intervening router.

Also, a direct physical link to a destination router need not be its cheapest route: a path through other neighbors can cost less.

7. Bellman–Ford and distance-vector updates

The course relation is:

\[ d_x(y) = \min_{v\in\operatorname{neighbors}(x)} \left\{c(x,v)+d_v(y)\right\}. \]

Quantity Meaning
\(d_x(y)\) Cheapest-path cost from \(x\) to destination \(y\)
\(c(x,v)\) Cost of the local link from \(x\) to neighbor \(v\)
\(d_v(y)\) Neighbor \(v\)’s cost to \(y\); an advertised estimate during an update

A path from \(x\) starts through some neighbor \(v\). Pay:

\[ \text{cost to neighbor}+\text{neighbor’s cost to destination}. \]

Then minimize over the possible first neighbors.

This relates to shortest-path decomposition: a subpath of a shortest path must itself be shortest, because replacing it with a cheaper subpath would reduce the complete path’s cost.

During distance-vector routing, routers exchange estimates and repeat the calculation when advertisements or link costs change. One update need not already equal the globally converged shortest distance.

Each router keeps its distance to itself at zero.

One concrete update

At router \(x\), for destination \(y\):

Neighbor \(v\) \(c(x,v)\) Advertised \(d_v(y)\) Candidate
\(a\) 2 8 10
\(b\) 6 1 7
\(c\) 3 3 6

Therefore:

\[ d_x(y)=6,\qquad\text{next hop}=c. \]

Choosing the smallest advertisement alone would incorrectly select \(b\). The local link cost also matters.

For a whole distance vector, repeat the minimization separately for every destination column, recording both cost and next hop.

Updating from one new advertisement

For a 2016-style improvement question, compare a retained valid alternative with the candidate through the newly advertising neighbor:

\[ \min\left\{D_x^{old}(y),\ c(x,v)+D_v(y)\right\}. \]

This works when the old alternative remains available.

If a changed advertisement invalidates the route supporting the old minimum, that stale minimum cannot simply be retained. Recompute from the current neighbor information.

When all neighbor advertisements are supplied, use the full neighbor minimum.

Dijkstra versus distance vector

Approach Information used Calculation
Link-state / Dijkstra Complete weighted network topology Repeatedly finalize the smallest tentative source distance
Distance-vector / Bellman–Ford Local link costs and neighbors’ advertised destination distances Repeatedly minimize local-link cost plus neighbor distance

Both can produce next-hop information. A distance-vector update does not use Dijkstra’s finalized set or predecessor tree.

8. Common exam traps

  • Addresses versus usable hosts: allocate complete power-of-two blocks and apply the stated network/broadcast convention. Include gateway interfaces where required.
  • Capacity without alignment: a sufficiently large interval is not automatically a CIDR block; network addresses require zero host bits.
  • Network versus first host versus broadcast: these are distinct under ordinary LAN conventions. A network address need not end in .0.
  • First match versus longest match: compare all matching prefix lengths. Adding an exception does not shrink the broader prefix.
  • Incorrect Dijkstra relaxation: use \(D(w)+c(w,v)\), update the predecessor with an improved distance, and leave finalized nodes fixed.
  • Predecessor versus next hop: trace backward to the first node after the source; the destination’s predecessor may be several hops away.
  • Incomplete Bellman–Ford calculation: add the local link cost to each advertisement. A stale old minimum cannot prevent a required cost increase.

9. Exam-like exercises

Show intermediate calculations. Each exercise’s conventions are part of the problem.

The set contains 50 practice points, weighted toward allocation/forwarding and Dijkstra. These are not predicted exam marks.

Exercise 1 — Subnetting fundamentals

12 points; suggested time: 20–25 minutes

A company has the inclusive address range:

172.19.80.0 through 172.19.87.255

Exclude ordinary network and broadcast addresses from usable hosts. All host requirements count every interface needing an address, including gateways.

1.1 — Parent block: 3 points

Determine:

  • total address count;
  • the single CIDR prefix representing the entire range;
  • its dotted-decimal mask;
  • the binary form of the nontrivial mask octet;
  • number of host bits.

1.2 — Equal-size subdivision: 3 points

Divide the parent into the maximum number of equal-size subnets, each supporting at least 62 usable interface addresses.

Derive:

  • minimum host-bit count;
  • subnet prefix and mask;
  • total and usable addresses per subnet;
  • number of subnets.

1.3 — Address decomposition: 4 points

Using your mask from 1.2, analyze:

172.19.83.173

Give:

  • network address;
  • numerical host ID;
  • broadcast address;
  • usable host range.

Show the bitwise-AND calculation in the octet containing the prefix boundary and give the host bit string.

Explain which bits distinguish these subnets within the original parent block.

1.4 — Same-subnet decisions: 2 points

Which addresses belong to the same subnet as 172.19.83.173 under that mask?

172.19.83.190
172.19.83.193
172.19.82.173

Justify each decision using network addresses or prefix bits.

Exercise 2 — Subnet allocation, forwarding and longest-prefix matching

18 points; suggested time: 35–40 minutes

Three routers form a triangle:

  • \(R_0\) serves LAN A;
  • \(R_1\) serves LAN B;
  • \(R_2\) serves LANs C and D.

All addresses must come from:

10.42.12.0/23
Subnet Required usable interface addresses
LAN A 100
LAN B 50
LAN C 25
LAN D 25
Link \(R_0-R_1\) 2
Link \(R_0-R_2\) 2
Link \(R_1-R_2\) 2

Requirements include router interfaces.

Exclude network and broadcast addresses in every allocated subnet. Use /30 for links. Allocate complete CIDR blocks, without prefix subtraction.

Use these allocation rules:

  1. Largest block first.
  2. Lowest aligned free block.
  3. Alphabetical order for equal-size LANs.
  4. Links in the displayed order.
  5. On each link, the smaller-index router receives the lower usable address.

2.1 — Allocation table: 7 points

For all seven subnets, give:

  • prefix;
  • dotted-decimal mask;
  • network and broadcast addresses;
  • usable range and capacity.

Assign both router interface addresses on every link.

Calculate how many parent-block addresses remain unallocated, counting complete allocated blocks.

2.2 — Alignment check: 1 point

A colleague proposes that LAN B should start at:

10.42.12.160/26

Is this a canonical /26 network address? What network does it actually denote?

2.3 — Base forwarding table and aggregation: 4 points

Construct \(R_0\)’s forwarding table for all seven allocated subnets.

Use these supplied routing decisions:

  • LAN B through \(R_1\);
  • LANs C and D through \(R_2\);
  • the \(R_1-R_2\) link subnet through \(R_1\).

For directly connected subnets, write direct and identify the interface.

For remote subnets, give:

  • destination prefix;
  • next-hop IP address on a link directly connected to \(R_0\);
  • outgoing interface.

Then replace the LAN C and D entries with one exact aggregate.

Give its prefix and the significant binary prefix bits in its final octet. Justify that it represents precisely those two allocations and uses a common next hop.

2.4 — Overlapping entries and lookup: 6 points

Extend the aggregated table from 2.3 with:

  • 10.42.12.0/23 → R1, using \(R_0\)’s interface toward \(R_1\);
  • 0.0.0.0/0 → WAN;
  • an exception sending the lowest 16 total addresses of LAN D’s allocated block through \(R_1\), which then forwards toward \(R_2\).

Derive the exception’s prefix.

This is a forwarding-policy range: it does not create a new physical subnet or change the allocation from 2.1.

For each destination, list all matching prefixes, then give the selected prefix, interface and next hop where applicable:

10.42.12.20
10.42.12.150
10.42.12.210
10.42.12.230
10.42.12.246
10.42.13.2
10.42.13.6
10.42.13.10
10.42.13.100
10.42.14.1

Finally: does adding the exception change the aggregate’s represented address count, or only which destinations select it?

Exercise 3 — Routing algorithms

20 points; suggested time: 35–45 minutes

The graph is undirected. Edge labels are nonnegative link costs; only the displayed edges exist.

Use:

  • source \(u\);
  • alphabetical selection when tentative distances tie;
  • the existing predecessor when a candidate cost equals the current cost.
flowchart TD
    u((u)) ---|4| a((a))
    u ---|2| b((b))
    u ---|9| c((c))
    a ---|2| b
    a ---|2| c
    a ---|7| d((d))
    b ---|6| c
    b ---|8| d
    c ---|2| d
    c ---|7| e((e))
    d ---|1| e

3.1 — Complete Dijkstra table: 8 points

Run Dijkstra to completion.

Use one initialization row, then one row after each node is added and its eligible neighbors are relaxed.

Keep finalized values visible. Each destination cell contains distance, predecessor.

Phase \(N'\) \(D(a),p(a)\) \(D(b),p(b)\) \(D(c),p(c)\) \(D(d),p(d)\) \(D(e),p(e)\)
Initialization
Step 1
Step 2
Step 3
Step 4
Step 5

3.2 — Tree and complete paths: 3 points

Give the final predecessor-tree edges.

Write the complete shortest paths from \(u\) to:

\[ c,\quad d,\quad e. \]

Check their costs by summing the corresponding link weights.

3.3 — Convert to forwarding information: 4 points

Router \(u\) has:

  • interface \(I_a\) toward \(a\);
  • interface \(I_b\) toward \(b\);
  • interface \(I_c\) toward \(c\).

The routers serve these destination LANs:

Serving router Destination prefix
\(a\) 10.60.0.0/24
\(b\) 10.60.1.0/24
\(c\) 10.60.2.0/24
\(d\) 10.60.4.0/23
\(e\) 10.60.6.0/24

Ignore additional cost inside each destination LAN.

Construct one forwarding entry per prefix, including:

  • path cost to the serving router;
  • next-hop router;
  • outgoing interface.

Show the predecessor-chain procedure explicitly for destination \(e\).

Which entry, next hop and interface are selected for:

10.60.5.17

Are \(p(e)\) and the next hop toward \(e\) the same router?

3.4 — Equal-cost alternative: 1 point

Identify the two equal-cost paths from \(u\) to \(a\).

Explain which predecessor your table retains and why choosing the alternative under another valid tie convention would not itself constitute an algorithmic error.

3.5 — Independent distance-vector snapshot: 4 points

Router \(d\) now uses distance-vector routing for destination \(z\), outside the drawn graph.

Use \(d\)’s incident link costs from the graph. Its neighbors advertise:

Neighbor \(v\) Advertised \(d_v(z)\)
\(a\) 3
\(b\) 1
\(c\) 5
\(e\) 4

Write the Bellman–Ford equation for \(d_d(z)\), calculate every candidate sum, and identify the new distance and next hop.

Explain why the smallest advertised distance need not identify the best neighbor.

Then \(e\) changes its advertisement to 11. All other advertisements and link costs remain unchanged.

Recompute using all current advertisements.

Does retaining the previous minimum as an additional candidate produce a valid update? Briefly distinguish the information used here from the information used by Dijkstra.

Source calibration

The preparation plan and Sheet 10 analysis identify A2–A5 as the core calculation material, with A6(c) supporting Bellman–Ford. I also inspected the earlier paging, scheduling and filesystem chapters for their theory–procedure–traps–exercises format. The attached notes end at Day 6, so Day 7 is treated as the prerequisite context you specified. 15-Operating-Systems-and-Networks-SoSe-25-Notes.pdf

The recent memory protocol’s Aufgabe 4 explicitly combines Dijkstra, routing/forwarding-table completion, subnet division, prefixes and masks. It supports this integrated preparation pattern without preserving the exact original graph or marking scheme. 13-Ged-chtnisprotokoll_Klausur_-IBN_Ersttermin.pdf

The 2016 exam’s Questions 5.1–5.3 directly test Dijkstra-table execution, predecessor-to-forwarding conversion and a distance-vector update. Question 4.3 supports same-subnet reasoning with a mask. 12-ibn-klausur-2016.pdf

Sheet 10 supplies the allocation conventions, prefix/range calculations, longest-prefix matching, full Dijkstra execution and Bellman–Ford connection used here. 10-ueb10-ibn-SS2025.pdf Its supplied solutions cover A2–A4 and end after A4. The A3(b) tables omit explicit own-LAN entries and inconsistently follow the figure’s router labels; the exercises above therefore derive entries from their explicitly stated topology. 14-Operating-Systems-and-Networs-SoSe-25-Solutions.pdf

The IBN summary supplies the network/host terminology, Dijkstra symbols and Bellman–Ford relation. 01-ibn-zusammenfassung.pdf