Total points 30. Total time 70 mins. 4 problems over 4 pages. No book, no notes, no calculator.

1. [5 pts] Consider an error-detecting CRC with the generator 10011. The CRC bits follow the data bits in any transmission. The string of bits 111011000100 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:

• 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 (A < B < C < ... < Z).
• 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 from C to D becomes 11. There is no further change in the link costs.

Give the evolution of the routing table entry at nodes B and C for destination D, at times 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 B, distance to D      At C, distance to D
           via node C              via node B  via node D

0.1           4                      6        2
1.0           4                      6       11

1.1

2.1

 .
 .
 .

3. [10 pts]

In this problem, every router is a multicast router; links are bidirectional; unicast routing is done on shortest-hop paths with ties resolved by choosing the next hop with smallest id (A < B < C < ... < Z); nodes B, D, E, F form a multicast group; each node in the group generates a flow of 1 packet/second to be delivered to all other nodes in the group. Do your rough work elsewhere.

a.

Assume a center-based shared multicast tree with center node X and join requests sent on unicast routes. Indicate on the figure the multicast tree and the aggregate flow on each link in each direction.

          

b.

Assume that RPF is used to build source-specific routing trees. Indicate in the figures below the appropriate multicast trees.

          

c.

Indicate in the figure the aggregate flow on each link in each direction achieved in part b.

4. [5 pts] Consider the following multiple access scheme that combines TDMA and slotted ALOHA. There are 30 users, separated into two groups, one of 4 users and the other of 26 users. Even time slots (i.e., 0, 2, 4, ...) are reserved for the 4-user group. Odd time slots (i.e., 1, 3, 5, ...) are reserved for the 26-user group. Contention within each group is resolved by the slotted ALOHA protocol (e.g., when a user in the 36-user group wants to send, it waits for an odd slot and then transmits with a probability p).

Determine the maximum throughput of the system, assuming that every user always has something to send and in each group the users have the optimal probability. Your answer can be in terms of fractions.