Homework #1 Solution 1. (OSI and TCP/IP models) What is the principal difference between connectionless communication and connection-oriented communication? In connectionless communication, the route for data is determined independently for each packet. In connection-oriented communication, a connection must be set up and later released. While the connection is active, all data follows the same route 2. (OSI and TCP/IP models) A system has an n-layer protocol hierarchy. Applications generate messages of length M bytes. At each of the layers, an h-byte header is added. What fraction of the network bandwidth is filled (wasted) with headers? Each protocol layer forms a "protocol data unit" (PDU) by adding an h-byte header to the PDU passed down from a higher layer. The total number of bytes for headers is hn and the message (application data) is M bytes, so the fraction of bandwidth wasted is hn/(hn+M). 3. (Error Detection) When bit errors are infrequent, why are ARQ schemes more efficient than FEC? FEC requires more bits per frame for error correction than ARQ schemes for error detection. This overhead is incurred for every frame. In an ARQ scheme, an errored frame must be retransmitted. But if bit errors are infrequent, there will be very few retransmissions. Then ARQ schemes will involve less overhead per frame than FEC. 4. (Error Detection) a. Suppose we are detecting bit errors by using horizontal and vertical parity bits. What is a pattern of 4 bit errors that would be undetected? b. Using horizontal and vertical parity bits, what is a pattern of 6 bit errors that would be undetected? (a) Using horizontal and vertical parity bits, an undetectable pattern of 4 bit errors would look like: (b) Using horizontal and vertical parity bits, an undetected pattern of 6 bit errors would look like: 5. (CRC) Suppose you are transmitting a data message M(x) = 1110011 using a cyclic redundancy check (CRC) code with generator polynomial G(x) = 101. What is the checksum that you would append to the message? (a) Given a data message M(x) = 1110011 and generator polynomial G(x) = 101, a remainder is found by appending 00 to the data (temporarily) and dividing by G(x): 6. (Error Detection and Correction) Would error detection (and retransmission) or error correction be a better choice for (a) transmissions between the Earth and Mars (b) encoding music on a CD-ROM (c) transmissions on a short optical fiber link with very low error rate? (a) Error correction is better because the roundtrip propagation delay is long. (b) Error correction is better because there is not time for re-reading audio data during playing of the music (c) Error detection is better because the error rate is low and the propagation delay is short. 7. When transferring a file between two computers, (at least) two acknowledgement strategies are possible. In the first one, the file is chopped up into packets, which are individually acknowledged by the receiver, but the file transfer as a whole is not acknowledged. In the second one, the packets are not acknowledged individually, but the entire file is acknowledged when it arrives. Discuss these two approaches. The preferred approach will depend on the probability of packet loss in the network. If packet loss is high, it would be better to acknowledge each one separately, so the lost packets can be retransmitted. On the other hand, if packet loss is low, sending one acknowledgement at the end of the entire transfer will save bandwidth in the typical case (but the entire file will be retransmitted in the rare case of a packet loss).