Description
The figures show an IP network. The numbers on the links are the costs associated with them
by the routing protocol. Answer the questions below.
• A, Shortest path: (15 points) Fill out the routing tables of all nodes.
N.H.
A
C
A
A
C
Dest.
A
C
D
E
F
A B C
D E F
5
6
12
28
15
18 19
9
4
N.H.Dest.
B
C
D
E
F
N.H.Dest.
A
B
C
E
F
N.H.Dest.
A
B
C
D
F
N.H.Dest.
A
B
C
D
E
N.H.Dest.
A
B
D
E
F
Figure 1: Shortest path
• B, Distance vector: (15 points) Assume first that the network uses a distance vector routing
protocol. Fill out the central routing databases of all nodes after the failure of link AE (after
the routing information stabilizes).
• C LSP flooding: (20 points) Assume next that the network uses a link state routing protocol.
As a response to the failure of link AE nodes A and E generate new LSPs. Show how these
LSPs are flooded through the network. Assume that packet propagation delays are the same
on all links, all routers process all LSPs immediately and that A and E detect the failure of
the link at the same time. If a router gets two identical LSPs at the same time on links X
and Y, it floods the LSP only on links other than X and Y. For your answer, just draw on
the figure on which links (and in which direction) LSPs from A and E are propagated. You
do not have to provide times at which LSPs arrive at each node. The picture below shows a
few such packets for a start.
1
Cost Cost
Cost Cost Cost
Cost
A B C
D E F
5
6
12
28
15
19
9
4
Dest. N.H.
B
C
D
E
F
Dest. N.H.
A
B
C
E
F
Dest. N.H.
A
B
C
D
F
Dest. N.H.
A
B
C
D
E
Dest. N.H.
A
B
D
E
F
Dest. N.H.
A
C
D
E
F
D
D
F
D
F
21
26
13
15
9
Figure 2: Distance vector
A B C
D E F
failure LSP E
LSP E LSP E
LSP A LSP A
Figure 3: LSP flooding
2
