Problem 26
Step
N’
D(t),p(t)
D(u),p(u)
D(v),p(v)
D(w),p(w)
D(y),p(y)
D(z),p(z)
0
x
∞
∞
3,x
6,x
6,x
8,x
3
7,v
6,v
3,x
6,x
6,x
8,x
Problem 27
a)
Step
N’
D(x), p(x)
D(u),p(u)
D(v),p(v)
D(w),p(w)
D(y),p(y)
D(z),p(z)
0
t
∞
2,t
4,t
∞
7,t
∞
1
∞
2,t
4,t
5,u
7,t
∞
2
2,t
4,t
5,u
7,t
∞
4
2,t
4,t
5,u
7,t
5
tuvwxy
2,t
4,t
5,u
7,t
6
2,t
4,t
5,u
7,t
b)
Step
N’
D(x), p(x)
D(t),p(t)
D(v),p(v)
D(w),p(w)
D(y),p(y)
D(z),p(z)
u
∞
2,u
3,u
3,u
∞
∞
∞
2,u
3,u
3,u
9,t
∞
2,u
3,u
3,u
9,t
∞
2,u
3,u
3,u
9,t
∞
2,u
3,u
3,u
9,t
2,u
3,u
3,u
9,t
2,u
3,u
3,u
9,t
c)
Step
N’
D(x), p(x)
D(u),p(u)
D(t),pt)
D(w),p(w)
D(y),p(y)
D(z),p(z)
v
3,v
3,v
4,v
4,v
8,v
∞
vx
3,v
3,v
4,v
4,v
8,v
11,x
3,v
3,v
4,v
4,v
8,v
11,x
3,v
3,v
4,v
4,v
8,v
11,x
3,v
3,v
4,v
4,v
8,v
11,x
3,v
3,v
4,v
4,v
8,v
11,x
3,v
3,v
4,v
4,v
8,v
11,x
d)
Step
N’
D(x), p(x)
D(u),p(u)
D(v),p(v)
D(t),p(t)
D(y),p(y)
D(z),p(z)
w
6,w
3,w
4,w
∞
∞
∞
wu
6,w
3,w
4,w
5,u
∞
∞
6,w
3,w
4,w
5,u
12,v
∞
6,w
3,w
4,w
5,u
12,v
∞
6,w
3,w
4,w
5,u
12,v
14,x
6,w
3,w
4,w
5,u
12,v
14,x
6,w
3,w
4,w
5,u
12,v
14,x
Step
N’
D(x), p(x)
D(u),p(u)
D(v),p(v)
D(w),p(w)
D(t),p(t)
D(z),p(z)
y
6,y
∞
8,y
∞
7,y
12,y
yx
6,y
∞
8,y
12,x
7,y
12,y
6,y
8,y
12,x
7,y
12,y
6,y
8,y
12,x
7,y
12,y
yxtvu
6,y
8,y
12,x
7,y
12,y
6,y
8,y
12,x
7,y
12,y
yxtvuwz
6,y
8,y
12,x
7,y
12,y
Step
N’
D(x), p(x)
D(u),p(u)
D(v),p(v)
D(w),p(w)
D(y),p(y)
D(t),p(t)
z
8,z
∞
∞
∞
12,z
∞
zx
8,z
∞
11,x
14,x
∞
12,z
zxv
8,z
14,v
11,x
14,x
12,z
15,v
zxvy
8,z
14,v
11,x
14,x
12,z
15,v
8,z
11,x
14,x
15,v
Problem 28
Cost to
u v x y z
v ∞ ∞ ∞ ∞ ∞
From x ∞ ∞ ∞ ∞ ∞
z ∞ 6 2 ∞ 0
Cost to
u v x y z
v 1 0 3 ∞ 6
Cost to
u v x y z
v 1 0 3 3 5
Cost to
u v x y z
v 1 0 3 3 5
Problem 29
The wording of this question was a bit ambiguous. We meant this to mean, “the number
of iterations from when the algorithm is run for the first time” (that is, assuming the only
information the nodes initially have is the cost to their nearest neighbors). We assume
that the algorithm runs synchronously (that is, in one step, all nodes compute their
distance tables at the same time and then exchange tables).
At each iteration, a node exchanges distance tables with its neighbors. Thus, if you are
node A, and your neighbor is B, all of B’s neighbors (which will all be one or two hops
from you) will know the shortest cost path of one or two hops to you after one iteration
(i.e., after B tells them its cost to you).
Problem 30
a) Dx(w) = 2, Dx(y) = 4, Dx(u) = 7
b) First consider what happens if c(x,y) changes. If c(x,y) becomes larger or smaller (as
long as c(x,y) >=1) , the least cost path from x to u will still have cost at least 7. Thus
Problem 31
Node x table
Cost to
x y z
x 0 3 4
x ∞ ∞ ∞
From y 3 0 6
z ∞ ∞ ∞
Cost to
x y z
Problem 32
Problem 33
At each step, each updating of a node’s distance vectors is based on the Bellman-Ford
Problem 34
a)
Router z
Informs w, Dz(x)=f
Informs y, Dz(x)=6
Router y
Informs w, Dy(x)=4
time
Æ w, Dz(x)=f
Æ y, Dz(x)=11
W
Æ y, Dw(x)=f
No change
Æ z, Dw(x)=10
Y
Æ w, Dy(x)=9
No change
Æ w, Dy(x)=14
time
via w, f
z
via z, 50
W
Æ y, Dw(x)=f
Æ y, Dw(x)=51
via w, f
Æ z, D
w
(x)=50
Æ z, D
w
(x)= f
via y, f
Æ w, Dy(x)= f
Problem 35
Problem 36
The chosen path is not necessarily the shortest AS-path. Recall that there are many issues
Problem 37
a) eBGP
Problem 38
a) I1 because this interface begins the least cost path from 1d towards the gateway router
Problem 39
Problem 40
Problem 41
BitTorrent file sharing and Skype P2P applications.
3. This is equivalent to B forwarding data that is finally destined to stub network Y.
Problem 42
Problem 43
Since Z wants to transit Y’s traffic, Z will send route advertisements to Y. In this manner,
Problem 44
The minimal spanning tree has z connected to y via x at a cost of 14(=8+6).
A
B
C
w
x
y
A
B
C
w
x
y
Problem 45
The 32 receives are shown connected to the sender in the binary tree configuration shown
above. With network-layer broadcast, a copy of the message is forwarded over each link
Problem 46
Problem 47
A
B
G
D
E
c
F
A
B
G
D
c
Problem 48
Z
y
x
v
t
u
w
Problem 49
Problem 50
Problem 51
Dijkstra’s algorithm for the network below, with node A as the source, results in a least–
B
Problem 52
After 1 step 3 copies are transmitted, after 2 steps 6 copies are transmitted. After 3 steps,
12 copies are transmitted, and so on. After k steps, 3*2k-1 copies will be transmitted in
…
Problem 53
Problem 54
A simple application-layer protocol that will allow all members to know the identity of
all other members in the group is for each instance of the application to send a multicast
Problem 55
28432
bits are available for multicast addresses. Thus, the size of the multicast
1073.32
N
The probability that 1000 groups all have different addresses is
¹
©