22C:116, Lecture Notes, Oct. 18, 1995

Douglas W. Jones
University of Iowa Department of Computer Science

  1. Communications Technology

    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 a token ring network or an ethernetwork. These options are far more complex than either of the above, and will be discussed in later sections.

  2. Serial Communication Links

    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!

    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). Thus, a bidirectional link between two mahcines can be constructed as follows:

        ______    ______                  ______    ______
       |      |--|      |_______________\|      |--|      |
       |      |  | UART |               /| UART |  | comp |
       |      |  |      |/_______________|      |  | 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. The convention is that each packet of data is prefixed with a start signal and terminated by a stop signal. 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. Traditionally, 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. 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 protocol commonly used 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 baud rate.

    A 75 baud communication line can transmit 75 bits per second using the most trivial modulation methods. 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, etc). For simple modems, it is worth noting that standard telephone lines are rated to handle frequencies between 300 and 3000 cycles per second, and that simple modulation schemes require on the order of one cycle to transmit one bit. 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.

    Note that, with an asynchronous protocol, the start and stop bits require a significant fraction of the available time. This 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 is 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.

    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 conventionsl 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.

  3. Errors

    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.

  4. Loop or Ring Networks

    Loop or ring networks are widely used. Typically, such a network has unidirectional serial communications links between processors, as follows:

                        __________
                       | computer |
      __________       |__________|       __________
     | computer |___\_____|    |_____\___| computer |
     |__________|   /                /   |__________|
              |_____________/______________|
                            \
    
    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---------
                      |                    |
                      |  ________________  |
            _______\__|_| shift register |_|__\______
                   /    |________________|    /
                          |  parallel  |
                          |   access   |
                          | from local |
                          | controller |
    
    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 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 indicates the current station, and if the host computer has provided an input buffer, it 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 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, when 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 a conventional DMA interface; the host computer is interrupted at the completion of each message transmission or reception.

    The widely used FDDI and Apollo/HP ring networks are both based on this approach.

  5. Ethernet

    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.