Description
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 followingtable. Assume that the 139.179.192.0/18 address block is given to you for this purpose. Usethefollowing 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 correspondstothe 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 taskistofind the most reliable path between each node pair. Assume that an implementationof theDijkstra’s algorithm that computes the least cost path (path with the smallest sumofweights) between any pair of nodes in the graph is available to you as a black box. Youcannot make any changes in the given code. Describe how you can usetheimplementation of the Dijkstra’s algorithm to compute the most reliable paths inthenetwork, i.e., the path with the smallest product of weights between each node pair. Justifythat your solution correctly computes the paths with the highest probability of operationasdefined 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 andwithnegligible transmission delays. Specifically, at every t = i, i = 0, 1, 2, 3,…, eachnodesends and receives routing info instantaneously, and updates its routing table; theupdate is completed by time t=i+0.1. At time t = 0, the link costs are as shown below and the routing tables havebeenstabilized. At time t = 0.5, the cost of the link (3,4) becomes 7. There are nofurtherlink cost changes. Route advertisements are only exchanged periodically, i.e., there are no immediateroute 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 linkimmediately 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, givethe 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 belowwhereD (j)
i
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 Dvia (6)
5 Dvia
2 4 6 1 3 2 4 1 3 5 4 60.1
0.5
1.1
2.1
3.1
4.1
5.1
6.1
7.1
8.1
9.1
10.1
2 1
3 4 5
6
1 12
1 6
1 1
1
4. Execute the Dijkstra algorithm at node B for the network shown belowby fillinginthefollowing table. In the table, you need to give both the distance D(v) and the previous nodep(v).
Step
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)1
2
6
8
5 3
4
8
1 3
6
2
B C D
E F
H I J
K
G
8
3
4
2 1
5. The following is the forwarding table at router R, which uses CIDR. Destination Network Next Hop
139.179.39.0 / 25 A
139.179.39.128 / 25 B
139.179.72.0 / 26 C
196.101.153.64 / 26 D
139.179.0.0 / 16 E
196.0.0.0 / 8 F
Suppose packets with the following destination IP addresses arrive at router R. Determineto which next hop each of these packets will be forwarded. Destination IP Address Next Hop
139.179.39.130
139.179.39.165
139.179.72.66
196.101.153.127
196.101.153.130
6. Suppose the data sequence 01101100110 is transmitted using the generator sequence110101. 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 canbedetected by CRC. 7. Consider an Ethernet LAN using CSMA/CD running at 100 Mbits/sec. The propagationspeed for the signal over the cable is 2×10
8 m/sec. The distances between the nodes inthisEthernet are given in the following table. Ignoring the jamming signal, computetheminimum frame size in Bytes so that the CSMA/CD algorithm will work properlyfor thisLAN. 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 threenodesare involved in a collision which is the third collision for A’s frame, fourth collisionforB’s frame and second collision for C’s frame. After the collision is detected (we assumethat all nodes detect the collision exactly at the same time), nodes calculate their backofftimes according to the binary exponential backoff algorithm. i) What is the probability that the first transmission after the above collision will beasuccessful retransmission by C?
ii) What is the probability that the first transmission after the above collision will beacollision involving all nodes?
iii) What is the probability that the first transmission after the above collision will beacollision involving only nodes A and B?
9. Consider two nodes A and B on a shared link, and both nodes need to transmit framestonode C, which is also on the same broadcast link. Assume that there are no other nodesonthe shared link that currently want to transmit packets. Assume that we use the SlottedAloha protocol. Suppose that a collision just occurred at time t, when Aand Btransmittedin the same slot. i) In this part, assume that each node retransmits the collided frame with probabilitypineach successive slot after t. Express the probability of having a successful time slot interms of p. Find the optimum value of p, which maximizes the probabilityof asuccessful slot, and the resulting maximum value for probability of a successful timeslot. ii) Calculate the average number of time slots elapsed after time t until bothnodessuccessfully transmit their respective frames.
10. Consider the switched network given below. Assume that the switch tables at time t areasfollows:
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, Ysends aframewith destination MAC address U. Third, Z sends a frame with destination MACaddressT. 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?
A
B
X
Z
W UT
Y1
2
4
3
4
1
2
3
