Homework Assignments: 22C:178 & 055:134

Computer Communications Spring 1998

Assignment 6

[3 March (solution added 7 March)]

Limits on Data Rates

The textbook describes certain fundamental limits governing the transmission of data (the speed of light, Shannon's formula). Although many technological factors limit the bandwidth and latency of a data link, the following are the best known limiting factors.

Here are a two questions that exercise the limits above.
Which gives the higher data rate, doubling the bandwidth of frequencies used to encode a signal, or doubling the power of the transmitter? (Assume noise remains the same in either case.)
The textbook points out that it is possible for the bit rate of a data link to actually exceed the signal rate (baud rate), simply by encoding bits with more than two levels of signal. Suppose instead of using two discrete signal levels, we want to have higher data rate and so propose 16 signal levels. In order to use 16 levels, it is necessary to have far more precision in the circuitry that samples frequencies (this is equivalent to using more terms in the Fourier expansion -- we are using more ``harmonics''). If this extra precision requires 5 times the bandwidth than a two-level signal would require, is our proposed encoding worthwhile?

Effective Bandwidth and Framing

Suppose we have a link that uses NRZI with 4B/5B encoding, and the HDLC framing protocol with an average of 1KB of user data per frame generated on the link. The maximum signal rate on the link is 1/16 the maximum frequency of 100MHz. What is the effective bandwidth?

Solution. First, let us see what the raw bandwidth will be for sending bits on the link. This is just 1/16 of the frequency, or 6.25Mbps. Now the user data to be sent will be segmented into packets of 1KB user data each. This means each packet will contain 8,192 bits of user data.

In addition, because these are HDLC frames, we add 48 extra bits per frame (see figure 3.9 in the textbook -- it shows an 8 bit initial sequence, a 16 bit header, a 16 bit CRC code, and an 8 bit final sequence, for a total of 48 extra bits). So each frame would have 8,240 bits to begin with.

But now recall that HDLC uses bit stuffing, meaning that if five 1-bits in a row are sent, an extra 0-bit will have to be inserted. For this solution, we calculate taking a pessimistic approach. Suppose all the bits are 1-bits. Then there would be a zero inserted for every fifth bit. The total number of bits will then be 8,240 + (8240/5) = 9,888 bits actually sent for the HDLC protocol.

Finally, we reckon with the 4B/5B encoding, which causes at the lowest level every group of 4 bits to be encoded using 5 bits. Now we have 9,888 * (5/4) = 12,360 bits actually transmitted on the link.

How long will it take to transmit a packet? At 6.25Mbps, we compute 12,360 bits / 6.25Mbps = 1.236e4 / 6.25e6 = 1.9776e-3 seconds. So it takes 1.9776msec to transmit the original 8,192 bits of user data. The effective bandwidth is therefore 8.192e3 / 1.9776e-3 = 4.14239Mbps. In practice, of course, the effective bandwidth would be significantly larger since user data is not all 1-bits, as we pessimistically assumed.

Error Correction

The textbook (indeed most textbook) explanation of the Cyclic Redundancy Check, in terms of polynomials, can seem intimidating. Usually complicated ideas do not result in simple code, and of course we require efficient code to be practical. So it may be interesting to see how CRC is computed in a C program. Using the example program crc32.c you can experiment with the CRC algorithm. In fact, it is quite efficient, since it uses only bit operations to compute the CRC of a string of bytes.

Some TCP Program Examples

The following programs are simple examples of how TCP can be used in a Unix environment. As with the UDP examples from the previous homework, these are minimal programs constructed for your further experimentation -- not examples of good programming.

The program tcpcli.c is the ``client'' of the example. This program reads from standard input (the terminal) and sends a TCP data stream to a server. You should be able to compile this program and test it with the corresponding server program, tcpserv.c in the same machine (it uses localhost as the network address). To run these programs, follow these steps.

Copy the source files to your local directory.
Compile them with the commands
gcc -o tcpcli tcpcli.c
gcc -o tcpserv tcpserv.c
Then open an X-window and start the server program in that window with the command tcpserv. It should print a message telling you it is waiting.
In another window, start the client program with the command tcpcli. It should be waiting for your keyboad input. Enter some data, such as aaaaaaa. The data you enter should be printed in the server window. Also the server will ``increment'' each character, send it back to the client, and the client will print the result (e.g., bbbbbbb).
After the above steps work, you should try some simple tests such as starting the client first, killing the server in the middle of a conversation with the client, and so on to see what happens if there is a failure. Another thing to try is to change localhost to some other machine name, such as horse@cs.uiowa.edu, and test the pair of TCP programs.

Recall that we looked at the alarm and signal system calls in an earlier homework. These calls make it possible for a program to ``timeout'' if it does not get a response within a certain time limit. A second version of the server, tcpserv2.c and adds the timeout mechanism to the server. Compile and test it using the same instructions as for tcpserv above (it still uses tcpcli for the client). One thing you will notice, if you allow the server to timeout, is that it will fail (after starting a conversation with a client) due to an interrupted system call . To fix this, you can remove comments and enable the line containing EINTR, recompile and test again. We will discuss the meaning of EINTR in class.

Ted Herman