Total points 30. Total time 75 mins. 3 problems over 3 pages. No book, no notes, no calculator.

1. [10 pts] Consider an error-detecting CRC with the generator 10101. Assume the CRC bits follow the data bits in any transmission.

a.

Compute the transmitted bit sequence for the data bit sequence 01101101.

b.

The string of bits 110011001100 is received. Is it acceptable, and if so what is the data bit sequence.

2. [10 pts] 

The above network uses the distance-vector routing algorithm. Assume the following:

• Links are bidirectional, and a link has the same cost in each direction.
• If several neighbors of a node can serve as the node's next hop to a destination, the node chooses the neighbor with the smaller id (where A < B < C < D).
• Nodes exchange their routing info once every second, in perfect synchrony and with negligible transmission delays. Specifically, at every time i, i = 0, 1, 2, 3, ..., each node sends its routing info, then receives routing info and updates its routing table; the update is completed by time i+0.1.
• At time 0, the link costs are as shown above and the routing tables are stable. At time 0.5, the cost of the link between C and D becomes 13. There is no further change in the link costs.

Give the evolution of the routing table with respect to destination D. Specifically, give the routing table entry for destination D at nodes A, B, C, for time 0.1, 1.1, 2.1, ..., until they stabilize. Point out when they stabilize. Present your final answer in the format given below, where the entry for time 0.1 has already been filled. Do your rough work elsewhere.

Time   At A, distance to D    At B, distance to D    At C, distance to D
         via   B    C            via   A     C          via   A    B   D

0.1            6    4                  6     4                6    6   2

1.1

2.1

 .
 .
 .

3. [10 pts] Repeat problem 2 but using distance-vector with poisoned reverse. Give your answer in the same format.