Homework 02 Solution

    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 139.179.192.0/18 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.

2
1
1
12
6





1



6









1


1


1


3

4

5








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

Di(j) is the distance vector element denoting the distance from i to j.

Time, t

D1 (6) via

D 2 (6) via
D 3 (6) via

D 4 (6) via

D 5 (6) via

2

4

6
1
3
2
4
1

3

5
4
6
0.1

































0.5

































1.1

































2.1

































3.1

































4.1

































5.1

































6.1

































7.1

































8.1

































9.1

































10.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 p(v).




2
1
B



C








8


2
















1
3





E



F



8



3



6












2













5


3







H



I






















8




4


1










D

6



G


4



J

K














N’
D(C),
D(D),
D(E),
D(F),
D(G),
D(H),
D(I),
D(J),
D(K),
Step

p(C)
p(D)
p(E)
p(F)
p(G)
p(H)
p(I)
p(J)
p(K)




































































































































    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. Determine to 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 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 2x108 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 follows:

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?



X







2


Z
3
A
1













4





4


W
1
B

3











2



































Y






U

T