Homework Assignments: 22C:178 & 055:134
[3 March (solution added 7 March)]
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
Here are a two questions that exercise the limits above.
- 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
- 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.
- 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?
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
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.
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,
in the same machine (it uses localhost as the network address).
To run these programs, follow these steps.
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
firstname.lastname@example.org, and test the pair of TCP programs.
- 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
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,
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.