SME
Computer Networks
Routing
Use this for “Router X’s links cost 2, 7, 4 to A, B, C, which report distances 6, 3, 5. Find X’s distance.”
Diagram
The cheapest path X–A–Z costs 2 + 6 = 8.
This is an example. Type your own values to start a new problem.
cA
Link cost to A
example
cB
Link cost to B
example
cC
Link cost to C
example
DA
A’s distance to Z
example
DB
B’s distance to Z
example
DC
C’s distance to Z
example
D
X’s distance to Z
worked out (not typed)
H
Next hop
worked out (not typed)
Formulas
D
=
min(cA
+
DA,
cB
+
DB,
cC
+
DC)
8 = min(2 + 6, 7 + 3, 4 + 5)
H
:
the
first
neighbour
whose
link
cost
plus
distance
is
D
2 + 6 = 8, so via A
Assumptions
•
Each neighbour reports its own distance to the destination Z (dashed).
•
X takes the cheapest link cost plus reported distance (Bellman–Ford).
•
On a tie, X keeps the first neighbour in the order A, B, C.
Step-by-step
WE KNOW
cA = 2, cB = 7, cC = 4, DA = 6, DB = 3, DC = 5
FIND
X’s distance to Z (D), next hop (H)
Step 1 · Find X’s distance to Z (D)
Use D = min(cA + DA, cB + DB, cC + DC)
Each route is a link cost plus that neighbour’s distance; take the cheapest.
D
=
min(2
+
6,
7
+
3,
4
+
5)
D
=
min(8,
10,
9)
D
=
8
Step 2 · Find next hop (H)
Use H: the first neighbour whose link cost plus distance is D
X sends packets for Z to the neighbour on the cheapest route.
2 + 6 = 8: via A
H
=
the
neighbour
on
the
cheapest
route
H
=
via
A
Check
Put the numbers back in. Both sides should match.
8 = min(2 + 6, 7 + 3, 4 + 5) ✓
2 + 6 = 8, so via A ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.