Module 5 Tutorials & Solutions
Routing Protocols (Forouzan Chapter 11)
Daniel Franklin
April 8, 2022
11.1 In RIP, why is the expiration timer value six times that of the periodic timer value?
A: This allows for some messages to be lost, in case some transient problem has caused a
message to be dropped.
11.3 Contrast and compare distance vector routing with link state routing.
A: DVR uses local knowledge, building a table of least-cost paths to destination networks
based on information sent periodically by neighbours. LSR uses global knowledge, with all
participating routers flooding the network with link state packets on any change of link state
(e.g. link goes up/down); all routers have a global picture of network topology. Shortest paths
in LSR are computed using Dijkstra while in DVR usually Bellman-Ford.
11.5 What is the size of a RIP message that advertises only one network? What is the size
of a RIP message that advertises N networks? Devise a formula that shows the relationship
between the number of networks advertised and the size of a RIP message.
A: Single-network advertisement is 24 bytes long. For N networks, we have 20N + 4 bytes. See
Figure 1.
11.7 A router using RIP has the routing table shown in Table 1. Show the RIP response
message sent by this router.
A:
11.9 How many bytes are empty in a RIP message that advertises N networks?
A: The general header has two empty bytes (set to 0s). Each advertisement section has 10
empty bytes. This means we have 2 + (10 × N ) empty bytes in a message advertising N
Command Version Reserved
Family All 0s
Network address
Repeated
All 0s
All 0s
Distance
Figure 1: RIP Packet Structure (width is 4 octets)
1
Table 1: Simple routing table
Dest Cost Next Router
Net1 4 B
Net2 2 C
Net3 1 F
Net4 5 G
Table 2: RIP message structure
2 Version Reserved
Family: 2 All 0s
Net1
All 0s
All 0s
4
Family: 2 All 0s
Net2
All 0s
All 0s
2
Family: 2 All 0s
Net3
All 0s
All 0s
1
Family: 2 All 0s
Net4
All 0s
All 0s
5
2
networks.
11.13 Show the autonomous system with the following specifications:
• There are eight networks (N1 to N8)
• There are eight routers (R1 to R8)
• N1, N2, N3, N4, N5, and N6 are Ethernet LANs
• N7 and N8 are point-to-point WANs
• R1 connects N1 and N2
• R2 connects N1 and N7
• R3 connects N2 and N8
• R4 connects N7 and N6
• R5 connects N6 and N3
• R6 connects N6 and N4
• R7 connects N6 and N5
• R8 connects N8 and N5
Now draw the graphical representation of the autonomous system of Exercise 29 as seen by
OSPF. Which of the networks is a transient network? Which is a stub network?
A: The network is shown in Figure 2.
11.15 In Figure 3, assume that the link between router A and router B fails (breaks). Show
the changes in the routing table for routers in Figure 11.7.
A: The repair process is shown in Figure 2.
11.17 Use the Bellman-Ford algorithm (Table 11.1) to find the shortest distance for all nodes
in the graph of Figure 5.
A: See Table 3-6.
Table 3: Initialisation of Cost Table
A B C D E
A 0 ∞ ∞ ∞ ∞
B ∞ 0 ∞ ∞ ∞
C ∞ ∞ 0 ∞ ∞
D ∞ ∞ ∞ 0 ∞
E ∞ ∞ ∞ ∞ 0
11.19 Find the shortest path tree for node B in Figure 6.
A:
1. Added node B, D = {2(BA), 0(B), 5(BC), ∞, 4(BE), ∞, ∞}
2. Added node A, D = {2(BA), 0(B), 5(BC), 5(BAD), 4(BE), ∞, ∞}
3
Figure 2: Network structure for Problem 11.13
Table 4: 1-hop Costs Added
A B C D E
A 0 4 2 ∞ ∞
B 4 0 ∞ 3 2
C 2 ∞ 0 5 ∞
D ∞ 3 5 0 ∞
E ∞ 2 ∞ ∞ 0
3. Added node E, D = {2(BA), 0(B), 5(BC), 5(BAD), 4(BE), 6(BEF ), ∞}
4. Added node C, D = {2(BA), 0(B), 5(BC), 5(BAD), 4(BE), 6(BEF ), 8(BCG)} (C and
D both have cost 5, arbitrarily pick C as it has one hop rather than 2)
5. Added node D, D = {2(BA), 0(B), 5(BC), 5(BAD), 4(BE), 6(BEF ), 8(BCG)} (no change
as adding D doens’t change any costs or provide connectivity to any new nodes)
4
Figure 3: Network structure for Problem 11.15
Figure 4: Repair process for Problem 11.15
Table 5: 2-hop Costs Added
A B C D E
A 0 4 2 7 6
B 4 0 6 3 2
C 2 6 0 5 ∞
D 7 3 5 0 5
E 6 2 ∞ 5 0
6. Added node F , D = {2(BA), 0(B), 5(BC), 5(BAD), 4(BE), 6(BEF ), 7(BEF G)} (cheaper
path to G found)
4
A B
2 3 E
5
C D
Figure 5: Topology for Problem 11.17
5
Table 6: 3-hop Costs Added
A B C D E
A 0 4 2 7 6
B 4 0 6 3 2
C 2 6 0 5 8
D 7 3 5 0 5
E 6 2 8 5 0
2 5
A B C 3
3 4 4 G
1
D E F
5 2
Topology
Figure 6: Topology for Problem 11.19
7. Added node G, D = {2(BA), 0(B), 5(BC), 5(BAD), 4(BE), 6(BEF ), 7(BEF G)} (no
change as we already have all of G’s neighbours)
11.21 Find the shortest path tree for node G in Figure 6.
A:
1. Added node G, D = {∞, ∞, 3(GC), ∞, ∞, 1(GF ), 0(G)}
2. Added node F , D = {∞, ∞, 3(GC), ∞, 3(GF E), 1(GF ), 0}
3. Added node C, D = {∞, 8(GCB), 3(GC), ∞, 3(GF E), 1(GF ), 0}
4. Added node E, D = {∞, 7(GF EB), 3(GC), 8(GF ED), 3(GF E), 1(GF ), 0} (cheaper path
to B found)
5. Added node B, D = {9(GF EBA), 7(GF EB), 3(GC), 8(GF ED), 3(GF E), 1(GF ), 0}
6. Added node D, D = {9(GF EBA), 7(GF EB), 3(GC), 8(GF ED), 3(GF E), 1(GF ), 0} (no
change)
7. Added node A, D = {9(GF EBA), 7(GF EB), 3(GC), 8(GF ED), 3(GF E), 1(GF ), 0} (no
change)