21. Communication Technology
Part of
the 22C:116 Lecture Notes for Fall 2002
|
Computers have been connected to each other in a number of ways over the years; whenever two or more computers (each with at least one processor and some memory) are connected by any means, the result is a network.
Among the technologies used for computer to computer links, consider the following:
Connect a parrallel output port of one computer to a parallel input port of another, with the data ready bit of the output port connected to the data available bit of the input port. This approach to connecting machines has frequently been used for machines located in the same room.
Connect a serial output port of one computer to a serial input port of another. This connection may be local (through what is called a null modem) or remote, through a modem and telephone line.
Connect the computers to a token ring or to an ethernet. These options are far more complex than either of the above, and will be discussed in later sections.
In the IBM PC world, there are a number of conflicting standards for such parallel-port to parallel-port links. The reason is that the IBM PC parallel port standard was originally developed as an output-only standard for interfacing to Centronics printers, but the printer port had enough readable status lines to allow some bidirectional misuse of this port for machine to machine communications. Later IBM PC parallel ports (all of those currently made) allow 8-bit data transfers in both direcitons, but software support for this generality is not standardized, and a number of the older conventions are still in use.
An appropriate use of the PC parallel port for machine to machine communication involves a physical connection such as the following (this is a mode 2 8-bit parallel PC to PC parallel port cable):
Machine A Machine B
DATA 0 ----------- Data 0
DATA 1 ----------- Data 1
DATA 2 ----------- Data 2
DATA 3 ----------- Data 3
DATA 4 ----------- Data 4
DATA 5 ----------- Data 5
DATA 6 ----------- Data 6
DATA 7 ----------- Data 7
STROBE ----->----- SLCT
AUTOFD ----->----- PE
INIT ----->----- ACK
SCLTIN ----->----- BUSY
SLCT -----<----- STROBE
PE -----<----- AUTOFD
ACK -----<----- INIT
BUSY -----<----- SLCTIN
An appropriate protocol for moving data between two machines using the above cable is as follows:
A serial communication link operates by sending the data one bit at a time over a single wire between sender and receiver. The byte parallel data presented by a conventional parallel output port is converted to serial form by a parrallel to serial converter, and at the receiving end, the data is converted back to parallel form by a serial to parallel converter. The problem of identifying the start of each data byte adds complexity to this!
By the early 1970's, many machines were made with RS-232 serial ports that could be pushed to data rates over 100 kilobits per second for local communications with a null modem, although few of these were officially advertised as supporting rates above 9600 baud until the late 1980s.
The complete logic for a serial transmitter and a serial receiver are usually combined into a single chip called a Universal Asynchronous Receiver Transmitter (a UART). Today, the UART function is easily integrated with other common functions such as real-time-clock and parallel port support on a single peripheral support chip, and many programmable microcontrollers include the UART function as a built-in peripheral on the CPU chip itself. However it is physically implemented, a bidirectional link between two mahcines can be viewed as follows:
______ ______ ______ ______
| |--| |_______________\| |--| |
| comp | | UART | /| UART | | comp |
| uter | | |/_______________| | | uter |
|______|--|______|\ |______|--|______|
Parallel serial parallel
Data is usually sent over a serial line least significant bit first, so if the bit pattern 10110111 is to be sent over a serial link, it would usually be transmitted as:
1 1 1 0 1 1 0 1
_____ ___ _
|_| |_|
| | | | | | | | |
time -------->
Clearly, there is a need to mark the beginning and end of each data packet (one byte, in the common case) sent over a serial link. This is usually done with a start and stop bit. This asynchronous convention dates back into the early 1900's, and it works as well with modern computers as it worked with early electromechanical Teletypes. Each data byte is prefixed with a start signal, and a stop signal is added as a suffix. These are coded in exactly the same way as data, with ones and zeros; therefore, they don't require a second wire to cary synchronization data. By convention, the start bit is a one, and the stop bit is a zero; furthermore, if no data is available for transmission, a continuous stream of zeros is sent between the stop bit and the start bit of the next character.
As a result, in context, our example data byte, 10110111, would be transmitted as:
start 1 1 1 0 1 1 0 1 stop
_______ ___ _
___| |_| |_| |____
| | | | | | | | | | |
time -------->
This convention is followed for transmitting asynchronous data using the RS-232 protocol, the oldest of the protocols commonly used today to move data between computers and modems. In the RS-232 protocol, logical ones are represented by voltages between -5 and -15 volts, and logical zeros are represented by voltages between 5 and 15, and the bit times may vary depending on the data rate. These strange voltages provide noise immunity, but they also require special purpose level converters to convert between these signalling voltages and the logic levels used within the computer system. (Some RS-232 receiver chips allow TTL compatabilty by declaring voltages from +0.5 to -15 to be logical ones, and many early laptop computers took advantage of this with RS-232 ports that could not properly output the negative voltages.)
A 75 baud RS-232 communication line can transmit 75 bits per second. Commonly used baud rates include the old Teletype rates of 75 and 110 baud, plus the series based on 300 baud (300, 600, 1200, 2400, 4800, 9600, 19200, 38400 etc). 75 baud was used with 5- and 6-bit character codes as far back as the 1920's, while 110 baud was used with teletypes that used the ASCII character set. In both cases, the data rate allowed 10 characters per second to be transmitted. The first generation of Bell System modems, from the 1960's, could handle a maximum of 300 baud.
Standard telephone lines are rated to handle frequencies between 300 and 3000 cycles per second, so simple on-off modulation schemes that require on the order of one accoustic cycle to transmit one bit are limited to 3000 bits per second. Thus, while it is easy to transmit 300 or 1200 baud over a phone line, higher rates require successively more complex analog signalling technology to squeeze their data over a phone line.
The limit of 56 Kilobaud comes from the fact that most modern phone lines are sampled at a rate of 7000 8-bit samples per second, with long-distance signals sent in digital form. This sampling rate allows recreation of low-fidelity audio signals at 3500 cycles per second, and thus meets the 300 to 3000 limit, but it makes it absolutely impossible to send more than 56000 bits per second of digital data.
Note that, with an asynchronous protocol, the start and stop bits require a significant fraction of the available time. This protocol overhead can be avoided by using a synchronous protocol, where consecutive bytes are simply packed together and transmitted as one long string of bits. Maintaining the synchronization between transmitter and receiver with a synchronous protocol requires far better clocks than are required for asynchronous protocols. For 8 bit data with start and stop bits as outlined above, if the transmitter and receiver clocks are tuned to within about one part in 20 of each other, reliable communication is possible. This is because the clocks are resynchronized by every start pulse, no more than 10 bits are sent following each start pulse, and if the difference between transmitter and receiver clocks is more than one bit at the end of 10 bit times, the data will be misread.
In synchronous data communication, resynchronization occurs whenever there is a 0 to 1 or a 1 to 0 transition on the input, but long strings of 0s or 1s offer no opportunity to resynchronize. If parity bits are included with each transmitted byte, and if odd parity is used, this guarantees two transitions for every 8 data bits transmitted, but it offers no way to detect the boundary between successive data bytes. It is conventional to include special synchronization characters in the line periodically to overcome this problem -- in IBM's bisynch protocol, for example, two consecutive SYNC characters must be inserted in the data stream periodically, SYNC characters are transmitted continuously when there is no data to transmit, and the receiver removes all sync characters from the data stream delivered to the user.
It is interesting to look at the consequences of errors in asynchronous communication. If one bit is changed, at random, in a stream of asynchronously transmitted data, not only can a data bit be corrupted, but bytes can be added or lost from the data stream.
If a string of 8 zeros is transmitted using an asynchronous protocol, the only one bit in the packet will be the start bit, and if this is corrupted by an error, no packet will be received. If an accidental one bit is injected into the string of zeros between data packets, the receiver will recognize this as the start of an extra unintended data packet.
Error detection in asynchronous data streams is usually done by appending a parity bit to the end of each packet of data bits right before the stop bit. Thus, for 8 bit data, the total packet would consist of 11 bits, including data, start, stop and parity bits. Even parity is computed by exclusive oring all the data bits; odd parity is computed as the inverse of the exclusive or of the data bits.
Error detection over a block of consecutive data bytes can be accomplished by computing the checksum over that block; there are many checksumming algorithms, ranging from the simple bytewize exclusive or of all the data bytes, through a simple arithmetic sum to CRC (cyclic redundancy check) codes and cryptographic signatures. It is worth noting that, if each byte has a parity bit, and if all the bytes in a block are exclusive ored together, the resulting code allows correction of single errors. Courses on coding theory discuss a number of more complex error correcting codes.
Loop or ring networks are widely used. Typically, such a network has unidirectional serial communications links between processors, as follows:
__________
| computer |
__________ |__________| __________
| computer |___\_____| |_____\___| computer |
|__________| / / |__________|
|_____________/______________|
\
Ring networks were first proposed and explored in detail by J. R. Pierce at Bell Labs in the early 1970's. The success of loop or ring networks rests on the details of the connection of the communications lines to the computers. Typically, this connection involves logic to passively forward data if the local computer isn't working, and it involves a bidirectional parallel port allowing data to be injected into the ring or picked off of the ring or forwarded. A typical structure is as follows:
___ shorting relay
--------o o---------
input | | output
| ________________ |
_______\__|_| shift register |_|__\______
/ |________________| /
| parallel |
| access |
| from local |
| controller |
The shorting relay in the interface shown above is typically designed to directly connect the input to the output whenever there is no power at the local controller. Thus, unplugging or powering down one machine on the ring will only briefly corrupt the circulating data and will not permanently disrupt communication by other users of the ring.
When the power is on at a station on the ring, the input data to that station is shifted through the local shift register to the output, so data entering the station appears on the output after N clock cycles, assuming an N-bit shift register. To transmit data, the station does a parallel load into the shift register, while to receive data, the station examines the contents of the shift register.
Pierce's original ring network was what is called a slotted ring -- the number of bits around the ring (the sum of all the shift registers and a buffer somewhere in the cycle) was required to be a constant, and the circulating data was divided into fixed sized packets analogous to sectors of a disk.
A simpler alternative scheme is called the token ring; these dominate the ring networks used today. When used with a token ring network controller, under normal operation, incoming data is shifted through the shift register to the outgoing line in only one word's worth of clock cycles. If the local power fails, the shorting relay assures that incoming data is connected through to outgoing data.
The controller for a token ring monitors the data as it is shifted by, looking for a special bit pattern, the token, that indicates the start of a data block. If it sees a token indicating that a message follows, and if the destination address field in the token is the address of the current station, and if the host computer has provided an input buffer, the token-ring controller deletes the token from the shift register and begins to read one block of data from the ring, deleting each word of data from the shift register after reading it, except for the final word, which is replaced by an empty token (one that indicates that no data follows).
If the controller has a message to transmit, it waits until it sees an empty token, it replaces it with a token containing the destination address, then begins inserting the successive words of one data block into the shift register after each preceeding word has been shifted out.
The controller interface to the host computer is typically a conventional DMA interface so that the host computer is interrupted only at the completion of each message transmission or reception.
The widely used FDDI and the old Apollo/HP ring networks are both based on this approach. Many of the local subnets of the Internet use T1 rings to connect groups of large clients. A T1 telephone line is a line with sufficient bandwidth to support one television channel, these lines were not originally intended for computer networks, but by the early 1970's, it was obvious that T1 lines were ideally suited for such uses. The original Pierce Loop network, for example, used T1 lines.
The Ethernet interconnection scheme is typically based on a single length of coaxial cable interconnecting all computers on the local network:
__________
| computer |
|__________|
| cable
|==================================|
____|_____ ____|_____
| computer | | computer |
|__________| |__________|
The interface on each computer constantly listens to the data on the cable. If it "hears" a start of block code, and if the address that follows matches its address, it begins receiving data and transferring it to the local computer. If an entire uncorrupted message is received, it interrupts the host computer to inform it of the successful receipt.
If an interface has been primed to transmit a message, it waits until it "hears" silence on the cable, and then begins transmission. For this reason, the Ethernet protocol is known as a "carrier sense" protocol. Unfortunately, it is possible that two different computers may be listening for silence at the same time because this is a multiple access network. If this occurs, both will simultaneously begin transmission at the same time, and the two messages will garble each other.
When an Ethernet interface that is transmitting data "hears" that its data is being corrupted, it immediately ceases transmission, and then waits a random interval before it begins listening again, awaiting silence. The random delay is needed to avoid livelock battles where two contending transmitters repeatedly start transmission, detect a collision, stop, and try again.
The total Ethernet protocol is called a CSMA (Carrier Sense, Multiple Access) protocol. Similar protocols have also been used on a number of other underlying network technologies.
It is worth noting that both the Ethernet and token ring protocols are strongly related to the mutual exclusion problem. In both, only one network host may transmit at any instant. In the case of the token ring, the circulating token is used to assure mutual exclusion. Hosts not needing to transmit pass it on, and when a host wishes to transmit, it awaits the token. Ethernet takes a more optimistic approach, based on the assumption that contention will be rare. When a host wishes to transmit, if it hears no other hosts transmitting, it simply begins to transmit. In the event of a collision, a roll-back and retry approach is used. This is analogous to protecting critical sections by detecting multiple entry and forcing all offending processes out if such a multiple entry is detected.
The problem with the classical Ethernet technology was that it was based on a single long piece of coaxial cable connecting all of the computers in the network. So-called thicknet cable was the worst, being comparable in thickness to the coaxial cable usef for long-haul cable TV transmissions, and requiring special taps to be set into the side of the cable at each network station. So-called thinnet cable was nicer, being based on flexible coaxial cable that plugged into T-connectors on the back of each computer interface.
The 10-base-T and 100-base-T technologies allowed the use of standard Ethernet interfaces with twisted pair cables from each machine to a hub. The basic 10-base-T hub is almost a passive device, all it does is reflect the signals sent from any of the connected lines to all of the connected lines. No digital logic is required, just appropriate filters and analog amplification.