Description
P1. (12 pts.) Suppose node C receives the following link-state packets from other nodes as in the following table. Answer
the following questions.
Link-State packet from Neighbor nodes (Link Cost)
A B(8) G(1) H(5)
B A(8) F(3)
D C(4) E(4) F(4) H(2)
E C(3) D(4)
F B(3) D(4)
G A(1) C(9)
H A(5) C(8) D(2)
a. Construct the topology of the network from the Link-State packets given in the table. (4 pts)
b. Use Dijkstra’s shortest-path algorithm to compute the shortest path from node C to all network nodes. Fill the
table below and you can add more rows if you need. (4 pts)
N’ D(A),
p (A)
D(B),
p (B)
D(C),
p (C)
D(D),
p (D)
D(E),
p (E)
D(F),
p (F)
D(G),
p (G)
D(H),
p (H)
c. Based on the results in b), fill in the following forwarding table for node C. Note that the “shortest path cost”
ELEC 3120: Computer Communication Networks
Homework 4
Page 2
column refers to the cost from node C to all destination nodes. (4 pts)
Destination Next Hop Shortest path cost
A
B
C
D
E
F
G
H
P2 (10 pts.) Consider the three-node topology shown below. The link costs are c(p,q) = 1, c(q,r) = 2, c(r,p) = 3. The DV
routing algorithm runs in the following way. Nodes are synchronized. In every second, nodes exchange link cost
information. Afterwards, each node computes its distance vector locally.
Compute the distance tables for node p, q, and r:
a) after the initialization step
b) after each iteration of the distance-vector algorithm
P3 (8 pts.) Consider the network shown below. Suppose AS3 and AS2 are running OSPF for their intra-AS routing
protocol. Suppose AS1 and AS4 are running RIP for their intra-AS routing protocol. Suppose eBGP and iBGP are
used for the inter-AS routing protocol. Initially suppose there is no physical link between AS2 and AS4.
a. Router 3c learns about prefix x from which routing protocol: OSPF, RIP, eBGP, or iBGP? (2 pts)
b. Router 3a learns about x from which routing protocol? (2 pts)
c. Router 1c learns about x from which routing protocol? (2 pts)
d. Router 1d learns about x from which routing protocol? (2 pts)
ELEC 3120: Computer Communication Networks
Homework 4
Page 3
P4. (10 pts.) In slotted ALOHA systems, we assume there are N active nodes and recall that the efficiency of slotted
ALOHA is 𝑁𝑝(1 − 𝑝)
𝑁−1
.
(a) Find the optimal value of p that can maximize the efficiency of slotted ALOHA. Please show the derivation.
(3 pts)
(b) With the optimal value of p found in (a), find the efficiency of slotted ALOHA by letting N approach infinity.
Please show the derivation. (3 pts)
(c) Show that the maximum efficiency of pure ALOHA systems is 1/2e. Please show the derivation. (4 pts)
P5. (8 pts.) Consider the cyclic redundancy check. Assume the generator is given by G = 1010. What is the value of R
for the following value of D?
a. D = 11000111010. (2 pts)
b. D = 01101010101. (2 pts)
c. D = 11111011111. (2 pts)
d. D = 10001110001. (2 pts)
P6. (12 pts.) Consider a network topology shown in the following figure that consists of three notebooks and two routers.
The IP addresses of the notebooks are shown in the figure and the MAC addresses for the corresponding interfaces
are shown in the following table. Answer the following questions.
Note: table filling problems will be graded on a row basis. A row is correct if and only if all the units of this row are
correctly filled in. A student will get points for a correct row.
ELEC 3120: Computer Communication Networks
Homework 4
Page 4
a. Suppose host A wants to send a packet to host B. In describing how this packet is sent from host A to host B
through C. Please fill out the table below. You may add more rows if needed. (2 pts)
b. Suppose now devices C and D are switches. Assume that the ARP tables in all the notebooks and the switch
tables in all switches are initially empty. After host A sends an ARP query packet to learn the MAC address of
host B, will host E receive the ARP query packet sent by host A? Justify your answer. (2 pts)
c. Based on assumption in sub-problem b, fill out the switch table below for switch C after host A receives reply
from host B. You may add more rows if needed. (2 pts)
d. After host A has successfully sent a data packet to host B, host E tries to send a data packet to host B. Does host E
need to issue an ARP query packet to learn the MAC address of host B? Why? If yes, will host A receive the ARP
query packet sent by host E? Why? (3 pts)
e. Fill out the following switch table for switch C after host E has successfully sent a data packet to host B. You
may add more rows if needed. (3 pts)
