CS421 HW2 solved




1. You are given the assignment of setting subnet addresses for 5 buildings of your company. The number of Internet connected PCs in each building is given in the following table. Assume that the address block is given to you for this purpose. Use the
following table to show the addresses of the five subnets that you created. Building # of PCs Subnet address (CIDR format)
1 3000
2 2200
3 2000
4 1500
5 1000
2. Consider a graph G(V,E), where V is the set of nodes and E is the set of edges (links). For
, let
represent the weight of link . Assume that each link weight corresponds to
the probability that the link is operational and that the probability that a path is operational
is given by the product of the weights of the links constituting the path. Your task is to
find the most reliable path between each node pair. Assume that an implementation of the
Dijkstra’s algorithm that computes the least cost path (path with the smallest sum of
weights) between any pair of nodes in the graph is available to you as a black box. You
cannot make any changes in the given code. Describe how you can use the
implementation of the Dijkstra’s algorithm to compute the most reliable paths in the
network, i.e., the path with the smallest product of weights between each node pair. Justify
that your solution correctly computes the paths with the highest probability of operation as
defined above. 3. The network below uses the distance-vector routing algorithm. Assume the following:  Links have the same cost in both directions.  Nodes exchange their routing info once every second, in perfect synchrony and with
negligible transmission delays. Specifically, at every t = i, i = 0, 1, 2, 3,…, each node
sends and receives routing info instantaneously, and updates its routing table; the
update is completed by time t=i+0.1.  At time t = 0, the link costs are as shown below and the routing tables have been
stabilized. At time t = 0.5, the cost of the link (3,4) becomes 7. There are no further
link cost changes.  Route advertisements are only exchanged periodically, i.e., there are no immediate
route advertisements after a link cost change. Hence the first route advertisement
after the link cost change at t = 0.5 sec occurs at t = 1.0 sec. Note: However, whenever a link cost change occurs, the two nodes at the endpoints of this link
immediately make corresponding changes in their distance tables.  Assume that the distance vector algorithm does not use poisoned reverse.
Give the evolution of the distance tables with respect to destination 6. Specifically, give
the distance table entries for destination 6 at nodes 1-5, for t = 0.1, 0.5, 1.1, 2.1, …, until
all distance vectors stabilize. Present your final answer in the table given below where
D (j)
is the distance vector element denoting the distance from i to j. Time, t (6)
1 D via (6)
2 D via (6)
3 D via (6)
4 D via (6)
5 D via
2 4 6 1 3 2 4 1 3 5 4 6
2 1
3 4 5
1 12
1 6
1 1
4. Execute the Dijkstra algorithm at node B for the network shown below by filling in the
following table. In the table, you need to give both the distance D(v) and the previous node
N’ D(C), p(C)
D(D), p(D)
D(E), p(E)
D(F), p(F)
D(G), p(G)
D(H), p(H)
D(I), p(I)
D(J), p(J)
D(K), p(K)
5 3
1 3
2 1
5. The following is the forwarding table at router R, which uses CIDR. Destination Network Next Hop / 25 A / 25 B / 26 C / 26 D / 16 E / 8 F
Suppose packets with the following destination IP addresses arrive at router R. Determine
to which next hop each of these packets will be forwarded. Destination IP Address Next Hop
6. Suppose the data sequence 01101100110 is transmitted using the generator sequence
110101. Compute the CRC bits and the transmitted bit sequence. Assume that the highest
order first four bits are errored during transmission. Determine whether the error can be
detected by CRC. 7. Consider an Ethernet LAN using CSMA/CD running at 100 Mbits/sec. The propagation
speed for the signal over the cable is 2×10
8 m/sec. The distances between the nodes in this
Ethernet are given in the following table. Ignoring the jamming signal, compute the
minimum frame size in Bytes so that the CSMA/CD algorithm will work properly for this
LAN. Distance (m) A B C D
A – 100 150 400
B 100 – 250 200
C 150 250 – 250
D 400 200 250 –
8. Consider three nodes A, B and C on a 100 Mbits/sec Ethernet. Suppose these three nodes
are involved in a collision which is the third collision for A’s frame, fourth collision for
B’s frame and second collision for C’s frame. After the collision is detected (we assume
that all nodes detect the collision exactly at the same time), nodes calculate their backoff
times according to the binary exponential backoff algorithm. i) What is the probability that the first transmission after the above collision will be a
successful retransmission by C?
ii) What is the probability that the first transmission after the above collision will be a
collision involving all nodes?
iii) What is the probability that the first transmission after the above collision will be a
collision involving only nodes A and B?
9. Consider two nodes A and B on a shared link, and both nodes need to transmit frames to
node C, which is also on the same broadcast link. Assume that there are no other nodes on
the shared link that currently want to transmit packets. Assume that we use the Slotted
Aloha protocol. Suppose that a collision just occurred at time t, when A and B transmitted
in the same slot. i) In this part, assume that each node retransmits the collided frame with probability p in
each successive slot after t. Express the probability of having a successful time slot in
terms of p. Find the optimum value of p, which maximizes the probability of a
successful slot, and the resulting maximum value for probability of a successful time
slot. ii) Calculate the average number of time slots elapsed after time t until both nodes
successfully transmit their respective frames.
10. Consider the switched network given below. Assume that the switch tables at time t are as
Switch Table at A
MAC Addr. Port #
X 2
W 4
U 4
Z 3
Switch Table at B
MAC Addr. Port #
X 4
W 1
After time t, first X sends a frame with destination MAC address Z. Second, Y sends a frame
with destination MAC address U. Third, Z sends a frame with destination MAC address T. Finally, U sends a frame with destination MAC address Y. i) Which node(s) will receive X’s frame?
ii) Which node(s) will receive Y’s frame?
iii) Which node(s) will receive Z’s frame?
iv) Which node(s) will receive U’s frame?