CSD008/COMP3616, Networks & Internet Systems: Problem Set 3
-----------------------------------------------------------
                       Solutions
                       ---------
("Tanenbaum" refers to the 4th Edition)


1. Suppose the data string to be transmitted is 1110010. What
 is the transmitted codeword using
 (a) the single parity check code?
 (b) the Hamming code?

Solution: (a) 11100100
          (b) 11110011001
 (see lecture notes on "Datalink layer, part 1" for details)


2. Suppose you are using the Hamming code. Given the received
 word 10111010110, detect and correct any errors. You may
 assume there is a maximum of one error in the transmitted
 data and no errors in the transmitted check bits.

Solution: the "new" parity bits are computed to be 1001, and
 this tells us that the bit in position 9 is in error. So we
 know that the transmitted codeword was 10011010110, and by
 stripping out the transmitted parity bits, we recover the
 original data string 1001011.
 (see lecture notes on "Datalink layer, part 1" for details)


3. In the General Parity Check error-handling scheme, if the
 minimum Hamming distance is D, this scheme can detect any
 combination of <= D-1 bit errors and correct any combination
 of strictly less than D/2 bit errors. Give a plausible
 explanation (NOT a proof) of these results, based on the
 definition of Hamming distance and the way this scheme works.

Solution: if the minimum Hamming distance is D, then D is the
 the smallest number of bit errors that changes one valid
 codeword into another. Since the way of computing the check
 bits is known, a list of all the valid codewords can be
 compiled and stored at the receiver. Then, when a word W is
 received, the receiver finds the closest valid codeword to W
 (in Hamming distance) and assumes that this codeword was the
 transmitted codeword.
 (1) Suppose the sender transmits a valid codeword C. If,
 during transmission, there are <= D-1 bit errors in C, then
 the received word cannot be a valid codeword, by definition
 of D, so the errors will be detected by the receiver.
 (2) Suppose the sender transmits a valid codeword C. If,
 during transmission, there are < D/2 bit errors in C, then
 the closest valid codeword to the received word will still
 be C, so the receiver will assume correctly that C was
 transmitted, which means all the bit errors were corrected.
 Put another way: if more than D/2 bit errors occurred, then
 there could be another valid codeword closer than C to the
 received word; if exactly D/2 bit errors occurred, there
 could be another valid codeword the same distance as C from
 the received word. In either of these cases, the receiver
 could assume the wrong codeword was transmitted. So errors
 can only be corrected if there were less than D/2 of them.


4. In a broadcast network with a shared communication channel,
 there are 3 basic contention resolution strategies:
 (1) divide the channel into independent sub-channels,
 (2) collision resolution, and (3) reservations.

 (a) Briefly explain under what circumstances the strategy of
 dividing the channel into independent sub-channels is NOT a
 good idea.

 (b) Given the circumstances mentioned in part (a), what are
 the advantages and disadvantages of the other two contention
 resolution strategies?

Solution:
 (a) dividing the channel into independent sub-channels, one
 for each transmission (e.g. using TDM or FDM), turns the
 channel into a set of point-to-point links, with no sharing
 possible between them. This would not be a good idea if the
 individual transmissions were "bursty" -- if the peak traffic
 values were much higher than the average values. Since the
 sub-channels would have to be sized to handle the peak values,
 there would be a lot of wasted capacity when the traffic was
 less than its peak value. But this traffic profile is very
 common with computer-to-computer traffic, which tends not to
 be very "smooth" (unlike traditional telephone network voice
 traffic, which was assumed to be 64kbps constant bit rate).

 (b) comparison of collision resolution and reservations:
 -- reservation schemes use tokens, and a node needs to possess
    the token in order to transmit; in collision resolution
    schemes, a node can transmit at any time (or maybe at any
    time when the channel is idle...).
 -- collision resolution schemes have a non-zero collision
    probability, and thus need a retransmission policy;
    reservation schemes ideally avoid collisions altogether.
 -- in general it's easier to add/remove/move a node in a
    collision resolution scheme, since there is no
    predetermined access order.
 -- reservation schemes typically have good performance under
    heavy traffic loads; collision resolution schemes typically
    have good performance under light traffic loads.