Homework Assignments: 22C:178 & 055:134

Computer Communications Spring 1998

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.

- The speed of light limits signal propagation, so a signal
cannot travel faster than
`3*10^8`meters per second. - Shannon's formula tells us that the maximum data rate
in terms of bits per second is
`H*lg(1+S/N)`, where`lg`is the base 2 logarithm,`H`is the bandwidth measured in Hz, and`S/N`is the signal to noise ratio on the link. Note that`S/N`is a*power ratio*usually specified by the quantity`10*log(S/N)`, which is the measurement unit in decibels (dB). For instance, a ratio of 1000 is given as 30 dB. The bandwidth on a link is computed from the frequency range (lowest to highest) used on the link for signal transmission. For instance, if signals use only frequencies in the range from 20 kHz to 34 kHz, then the bandwidth is 14 kHz. - The
*Nyquist Limit*is another formula (actually a theorem) limiting data rate. The Nyquist limit does not depend on noise, but rather the way in which frequencies encoding a signal can be filtered. The Nyquist limit states that the maximum data rate (again in bits per second) is`2H*lg V`, where`H`is bandwidth and`V`is the number of ``signal levels'' used in the signal encoding. For square-wave signals there are only two levels, so the Nyquist limit in that case is just`2H`. However if four discrete signal levels are available, then we can have`4H`bits per second of data transmission. The Nyquist limit is derived from the fact that to measure a two-level signal of bandwidth`H`, the receiver of the signal needs to measure`2H`samples per second, but measuring any more than`2H`samples per second yields no additional information. - Another limiting factor can be seen from the same idea underlying
the Nyquist limit. The frequency used for a signal is inversely
proportional to the wavelength of the signal, which constraints the
``bit width'' used. We recall from elementary physics that the
product of frequency and wavelength is the speed of light. For instance,
a frequency of 5 Mhz has a wavelength of 60 meters (in a vacuum, where
the speed of light is
`3*10^8`meters per second). Suppose we have a fiber-optic link using light with a wavelength of 670 nanometers. Then the frequency of the light is 298,507 Ghz (using`2*10^8`for the speed of light in a fiber). We do not have any electronic circuitry capable of manipulating signals at such an enormous frequency. If we considered even a frequency range corresponding to two close wavelengths, say 660 nanometers and 670 nanometers, the bandwidth will be enormous in terms of Hz, but we do not have any practical way of utilizing this bandwidth: the Shannon and Nyquist limits don't mean anything in practice for fiber optics, since we cannot come even close to these theoretical limits.

- 1.
- 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.)
- 2.
- 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?

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.

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.

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.

- 1.
- Copy the source files to your local directory.
- 2.
- Compile them with the commands
`gcc -o tcpcli tcpcli.c`

`gcc -o tcpserv tcpserv.c` - 3.
- 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. - 4.
- 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`).

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.