## 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 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.

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)

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 D via (6)

5 D 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

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 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).

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. 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 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

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?

A

B

X

Z

W U

T

Y

1

2

4

3

4

1

2

3