cmsc417-f99 exam 2 solution

CMSC 417-F99

EXAM 2 SOLUTION

Fall 1999

1 [10 pts]. Solution

Generator is 10101. So r=4.

(a) The CRC for data bit sequence 01101101 is the remainder after dividing the data bit sequence concated with four 0's by the generator.

                 01110111
           ______________
     10101 | 011011010000
             00000
             -----
              11011
              10101
              -----
               11100
               10101
               -----
                10011
                10101
                -----
                 01100
                 00000
                 -----
                  11000
                  10101
                  -----
                   11010
                   10101
                   -----
                    11110
                    10101
                    -----
                     1011 

The remainder is 1011.
So the transmitted sequence is 011011011011

(b) Is the string of bits 110011001100 acceptable.

                 11111100
           ______________
     10101 | 110011001100
             10101
             -----
        10101 | 110011001100
             10101
             -----
              11001
              10101
              -----
               11000
               10101
               -----
                11010
                10101
                -----
                 11111
                 10101
                 -----
                  10101
                  10101
                  -----
                   00000
                   00000
                   -----
                    00000
                    00000
                    -----
                     0000

It is acceptable because the remainder is 0000.
The data bit sequence is  11001100

GRADING:

In part a, 4 points for the division, 1 point for the transmitted sequence.
In part b, 4 points for the division, 1 point for the data sequence.

2 [10 pts]. Solution


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

0.1       6     4     4          6     4    4         6     6     2    2

1.0       6     4     4          6     4    4         6     6     13   6

1.1       6     8     6          6     8    6         6     6     13   6

2.1       8     8     8          8     8    8         8     8     13   8

3.1      10    10    10         10    10   10        10    10     13  10

4.1      12    12    12         12    12   12        12    12     13  12

5.1      14    14    14         14    14   14        14    14     13  13

6.1      16    15    15         16    15   15        16    16     13  13

7.1      17    15    15         17    15   15        17    17     13  13

8.1      17    15    15         17    15   15        17    17     13  13

Stable at time 7.1.

GRADING:

Entry at time 1.0 and columns for min did not count toward grade.
Max 2 points for stating that stable by time 2.1 or 3.1 or 4.1.
Max 6 points for not getting it correct but showing that the min distance decreases by 2 every iteration.

3 [10 pts]. Solution

Next hop indicated by *

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

0.1       6     4*    4          6     4*   4       inf   inf     2*   2

1.0       6     4*    4          6     4*   4       inf   inf    13*  13

1.1       6*   15     6          6*   15    6       inf   inf    13*  13

2.1     inf    15*   15        inf    15*  15         8     8    13*   8

3.1      17*  inf    17         17    10*  10       inf   inf    13*  13

4.1      12*   15    12        inf    15*  15        19   inf    13*  13

5.1      17    15*   15        inf    15*  15        14   inf    13*  13

6.1      17    15*   15         17    15*  15       inf   inf    13*  13

Stable at time 6.1.

GRADING:

Entry at time 1.0 and columns for min did not count toward grade.
Max 4 points for not getting it correct but showing that infinity cost is sent to next hop.
Max 2 points for not getting it correct but showing correct initial condition .iem