22. Communication Protocols

Part of the 22C:116 Lecture Notes for Fall 2002
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Introduction

A communication protocol is an agreement between the users of a communication medium about how the medium is to be used. For example, a typical asynchronous serial communications protocol might be described as follows:

               time --------->
      V1      _ _ _ _ _ _ _ _ _ _ 
        _____| |_|_|_|_|_|_|_|_|_|_|_|____
      V0      | 1 2 3 4 5 6 7 8 P \ /
              |      data       |  Stop bits
          Start bit             |
                              Parity bit.

The time scale must be specified as part of the protocol, as must the voltages V0 and V1 used to encode zero and one. For example, if someone says they're using an asynch RS232 protocol at 9600 baud, they mean V1 = -15, V0 = +15, and the time per bit is 1/9600 second. In addition, they should specify how many data bits are used per character, whether even or odd parity is used, and whether one or two stop bits follow each character.

It is not sufficient to give this low level protocol. To effectively use a communications line, there must also be an agreement about the interpretation of data. For example, the protocol could specify that the 7-bit ASCII character set is used, with the unused high bit set to zero, or perhaps IBM's EBCDIC charcter set, a legacy of IBM mainframe operating systems, should be used, or the ISO 8859-1 character set, an 8-bit character set upward compatable from ASCII.

Even specifying the character set is not sufficient, however. There must be a convention for identifying messages embedded in the string of characters. All of the example character sets mentioned above code include special control characters that were originally intended for this use. The control characters of ASCII implicitly suggest the following message format:

SOH -- start of heading
header -- for example, the address of the recipient
STX -- start of text
message text
ETX -- end of text
trailer -- for example, the message checksum
EOT -- end of transmission

Other characters provided by the ASCII code related to this kind of protocol issue are:

ENQ -- enquiry
ACK -- acknowledgement
NAK -- negative acknowledgement

These might be used to enquire about the previously transmitted block. An ACK might indicate that the block was received correctly, and a NAK might indicate that there was an error.

Protocol Hierarchy

In general A protocol takes a stream of data and embeds it in a stream containing not only that data but also other information.

              ____________________
               DATA   DATA   DATA    higher level data stream
              ____________________
          _________/|      |\_________
         /          |      |          \
  ______________________________________________
   DATA |   stuff   | DATA |   stuff   | DATA     data stream
  ______|___________|______|___________|________ using protocol

This added information is not necessarily anything the user wants sent, but it is necessary (under the protocol) for the correct conveyance of the data.

In the discussion of asynchronous data transmission, the start and stop bits, inserted between each byte of data, constituted a low-level protocol, while the SOH, header, STX, ETX, trailer and EOT were added to each block of data by a higher level protocol.

Protocols generally exist at many different levels of abstraction, although early protocols frequently mixed and confused these levels. The protocol implicit in the ASCII control characters is an example of one of these early ad-hoc protocols that thoroughly confuses several levels of abstraction.

The ISO (International Standards Organization) OSI (Open Systems Interconnection) model protocol hierarchy clearly identifies multiple levels and helps system designers avoid many of the problems of older ad-hoc protocols.

An example of a confused protocol is IBM's Word Processing EBCDIC protocol from the 1970's. This specified everything from the use of the BISYNC synchronous data transmission method to the use of type-balls on a selectric printing mechanism. Issues of flow control, communications line management, and character set coding were completely mixed together.

If one says RS-232, one is specifying a low-level protocol for conveying ones and zeros. If one says asynchronous, 56 kilobaud, one is specifying a somewhat higher level protocol for conveying a stream of bytes over some low level serial protocol. If one says ASCII, one is specifying an even higher level but somewhat mixed up protocol for the interpretation of those bytes. The problem with saying ASCII is that the ASCII (or ISO-7, as it is now officially known) character set specifies both a set of interpretations of bytes for printable characters and a set of control characters that were originally intended for various higher level protocols but are, today, rarely used as intended.

An open system is a system where the components are made by different manufacturers and combined by the user in ways not always anticipated by the manufacturers. Open systems only work well when there are standards for interconnecting the components. Some standards, like the Centronics printer interface (more widely known as the IBM PC parallel port) or Postscript, are the result of a single company leading the marketplace and being copied by others; other standards, such as ASCII and the ISO OSI suite, are the result of committee actions that span many users and manufacturers.

The ISO OSI Reference Model has seven layers, as follows

Application
A protocol agreed on by the end users for their application.

Presentation
The mechanisms by which the lower level protocols are presented to the application. This is, to a large extent, a matter of packaging.

Session
Protocols for connecting one application to another, establishing data streams or user level addressing of data packets.

Transport
Protocols for moving data from logical sender to logical receiver.

Network
Protocols for moving data from physical sender to physical receiver.

Data Link
Protocols for moving data over a single link in the network.

Physical
Protocols at the electronic, electrical and mechanical levels.

The physical layer

Examples:

In both of the above examples, the type of the physical network connection is given (a 25 pin miniature delta connector, and "75 ohm BNC" is a type of cable and connector). Both specify voltages used for signalling (RS-232 specifies +15 volts for logical 0, -15 volts for logical 1; the baseband Ethernet standard includes a set of voltage assignments). Both specifications include a basic interpretation of the data on the line, in terms of how to identify the start and stop of data and how to encode the individual bits.

In fact, we can easily distinguish sublayers within this single layer of the ISO model! For example, Ethernet interface hardware that was designed for use with 75 ohm BNC coaxial cable can also be used with the older thicknet cable by a simple change to the physical connectors used, and the same interface can be used with 10 Base T cables by using a small adapter. Similarly, while the 25-pin miniature delta connector was once the most common connector used for RS-232 wiring, the 9-pin miniature delta connector is more common today, and the 8-pin mini-DIN connector is increasingly used for this standard.

The link layer

Consider a point to point data format where data is formed into blocks with the following structure based on the protocol suggested by ASCII's control characters:

                >>--time-->>
   ________________________________________ 
  |_|_______|_|_______________|_|______|_|_|
  SOH   |   STX       |       ETX  |  EOT ENQ
       head      n data bytes      |
         n                       checksum
         (number of bytes)         CRC-16 computed over
                                   the head and data.

Suppose someone includes, in their data, an ENQ character? Suppose one of the bytes of the checksum is accidentally an EOT? How does the receiver determine that these characters are data and not part of the protocol for sending the block? The problem with data that contains characters that are accidentally meaningful to the protocol is a consequence of in-band signalling. This term comes form telephony. A protocol using out-of-band signalling relies on two separate communications channels, one to send user data, and one to send the data necessary to control the communications link.

With in-band signalling, both user data and control information are sent over the same channel, and unless care is taken, there are problems that can arise when the two are confused.

In the above example, we can count bytes in the block and in the checksum to make sure we don't interpret data bytes as protocol control characters, but transmission errors could cause bytes to be added or dropped, so if we use this protocol, it is better to make sure that the following control characters are never present in the data:

           ENQ EOT ETX STX SOH ACK NAK
Typically, if these are found in the data, the transmission software would be expected to substitute something else, typically something like an escape sequence, for example ESC-1 for ENQ, ESC-2 for EOT, and so on up to ESC-8 for ESC, in order to prevent the data from corrupting the protocol.

The touch-tone signalling mechanism used in telephony is an example of in-band signalling. In the early 1970's, Captain Crunch cerial (made in Cedar Rapids) was sold with a small whistle in each box. This whistle, unfortunately, was tuned to a signalling frequency used in long distance telephone lines (2600 cycles). The effect of injecting this signal into a line was to cause the remote long-distance exchange to terminate the connection and listen for signals similar to touch-tone signals encoding the new destination being called. Unfortunately for the telephone companies, the billing for the long-distance call ended with the 2600 cycle tone, and the new long-distance call was made at no charge to the customer.

When the telephone companies discovered their error, they got Quaker Oats to discontinue their promotional giveaway, and over the decade that followed, they moved to out-of-band signalling.

The hacker magazine 2600 took its name from this bit of history.

The network layer

The central issue dealt with by the network layer is that of delivering messages to their destinations. Therefore, this layer is very concerned with addressing and address formats. There are two primary approaches to addressing in communication networks:

          * Absolute Addressing

                >>--time-->>
             _______________________
            |______|_|______________|
             fixed  n    n bytes
             size        of data
             address

          * Path Addressing

                >>--time-->>
             _________________________________
            |_|______________|_|______________|
             a  a components  n    n bytes
                of path to         of data
                destination
With absolute addressing, the sender specifies the name of the destination machine, and it is up to the network layer to find a path through the network to get to that destination.

With path addressing, the sender specifies a path to the destination, and the network layer sends the data to the first machine on the path, at which point, the first machine strips off its address and forwards the message to first machine on what is left of the path.

Whatever form of addressing is used, the network layer uses the link layer to communicate from one machine to another along the path, and at each machine on the path, the message is examined again by the network layer in order to determine what link to use next. The network layer is concerned with routing the data from one machine to another, not with lower level issues of link usage.

When a message must traverse many links in its trip through a network, it typically rises to the level of the network layer at each machine that forwards the message. This is illustrated in the following figure:

              sender                         receiver
application     |                                |
                |                                |
presentation    |                                |
                |                                |
session         |                                |
                |     forwarder   forwarder      |
network         |         __          __         |
                |        |  |        |  |        |
link            |        |  |        |  |        |
                |        |  |        |  |        |
physical        |________|  |________|  |________|

In the world of modern commercially available network accessories, tools such as 10-base-T hubs are part of the physical layer, but packet switches and network bridges typically incorporate complete small computer systems and implement the layers up to the session layer. If these components have any higher layers, these are present only to support fixed applications such such as the tools necessary to configure the network layer's routing tables. Any computer with multiple network interfaces can act as a packet switch or network bridge, given appropriate software, and assuming that this runs under a modern operating system, that computer may also host any of a number of applications.

The transport layer

The transport layer deals with movement of data between logical senders and receivers, as opposed to the physical machines that are hosts to these logical entities. We assume that each machine on the network may have more than one logical destination for messages.

For example, data may be transported between processes, or it may be transported from the sender to a named destination such as a socket. The term socket is used in the internet protocol suite to refer to a message destination that many processes on the same machine may read from. Such a destination exists independently of the processes consuming messages addressed to it. In other systems, the transport layer supports the concept of mailboxes, named message destinations from which processes may receive messages and to which messages are sent.

           >>--time-->>
         ______________________
	|_________|_|__________|
          mailbox  n  n bytes
          name        of data
In this example, the transport layer must be able to infer two things from the mailbox name, the network address of the machine to which the message is addressed, and the local address, on that machine, of the destination mailbox. The mailbox name could have two fields, as is done when referencing sockets on the Internet. For example, on the Internet, we might address a message to server.cs.uiowa.edu:44, where server.cs.uiowa.edu identifies a machine, while 44 identifies a particular socket on that machine.

Alternatively, the mailbox name could be machine independent, allowing messages to be sent to destinations that move from machine to machine. If this is done, the transport layer must support more complex addressing logic.

The transport layer can be thought of as a multiplexing messages from multiple logical sources on one machine onto outgoing network connections, and it can be thought of as demultiplexing messages from incoming network connections to different destinations on that machine.

The session layer

The name of the session layer suggests that its inventors expected that this layer would implement interactive sessions between users on remote machines. Typically, the transport layer manages the delivery of messages from logical sender to logical receiver, but the session layer is given the job of organizing these into streams of bytes and guaranteeing delivery.

Not all applications need streams, though, so an alternate session layer might organize data into remote procedure calls or other transaction oriented structures.

No network technology can guarantee the delivery of all messages, while most application programmers would prefer a guarantee of delivery. An attempt at offering such a guarantee can be made at almost any layer, but generally, it is the transport layer or the session layer that makes the most serious attempt. Any layer attempting to offer guaranteed delivery must include tools for error detection and correction in its protocol. For example, checksums may be added to the message, and delivery receipts may be required, with some kind of protocol for retransmission of messages that are not delivered. It is the inclusion of these delivery receipts that frequently forces error correction into the session layer, because the presence of a continuous stream of data over a long lived connection significantly simplifies the management of such receipts and hides their existance from the application.

Many network technologies do not guarantee that messages will be delivered in the order they are sent. This is particularly true when there are multiple possible paths from sender to receiver. The session layer is frequently put in charge of adding sequence numbers to the transmitted messages on a channel, and then delivering the messages in order at the receiving end. These sequence numbers allow trivial detection of missing messages, so this facility naturally integrates with the logic for attempting a delivery guarantee.

Note that, in fact, it is impossible to offer a real delivery guarantee, and ultimately, this requires that network applications take some responsibility for faults. Ultimately, attempts by network layers below the application to offer delivery guarantees serve only to reduce the frequency of failures that must be dealt with by the application. If this frequency is reduced sufficiently, application programmers may choose to ignore the possibility of failure, but if genuine fault tolerance is desired in the application, the application must anticipate failure and the delivery guarantees attempted by lower layers must be viewed entirely in terms of their effect on performance -- because application level fault tolerance is generally fairly slow, correcting errors at lower levels can greatly reduce the run-time cost of fault tolerance.

Upper layers

We will ignore the presentation layer and the application layer here. Generally, the communication software of the distributed system largely ignores these, but specifica applications, for example, remote login tools, window managers, or file servers must, of course, have presentations for their services as well as application-level specifications.

Protocol Bloat

Protocol layering can cause a problem known as protocol bloat. This is because, at each layer in the protocol, it is tempting to try to solve all problems that can be solved at that level. As a result, we end up with a block size field added at each level, a checksum added at each level, sequence numbers at many levels, etc. The sum of all of these additions can easily dominate the total demand on the network!

Consider transmitting a keypress from a keyboard on one machine to an application running on a remote machine. Suppose, at the hardware level, we are using an asynchronous line. Therefore, to each 8 bits we send, we add a start bit, a stop bit and a parity bit multiplying the total traffic by a factor of 1 3/8. At the link layer, assume we use the STX,ETX,EOT protocol to append a 16-bit checksum to each data block, where blocks contain from 1 to 256 bytes. This checksum allows the link layer to request retransmission over one link if a block is corrupted. At the network layer, we might prefix each message with a byte count, and prefix that with the 32-bit machine ID. At the transport layer, we might prefix each message with a 64-bit mailbox ID and a byte count. Combining all of this, we are now transmitting one 8-bit character representing a keypress as:

	1 byte  -- the character  (8 bits)
        1 byte  -- (value 1) the session layer message size
        1 byte  -- the session layer sequence number
      + 4 bytes -- the session layer checksum
      -------
        7 bytes -- the packet sent by the session layer
        1 byte  -- (value 1) the transport layer message size
      + 8 bytes -- the transport layer mailbox ID
      -------
       16 bytes -- the packet sent by the transport layer
        1 byte  -- (value 10) the network layer message size
      + 4 bytes -- the network address of the destination machine
      -------
       21 bytes -- the packet sent by the network layer
        3 bytes -- STX, ETX and EOT added by the link layer
      + 2 bytes -- 16-bit checksum
      -------
       26 bytes -- the packet sent over the physical link
     x 11       -- bits per byte on an asynchronous link
      -------
      286 bits  -- total bits sent over the data link!

Of course, we should also have included a sequence number and another checksum at the session layer, in order to guarantee that keypresses are delivered in order and in order to attempt to guarantee delivery. The net result is that the actual useful data in this stream of keypresses occupies about 8/286 or about 1/36 of the total transmitted data. This example, with one byte packets from a keyboard, is an extreme one!

Exercise: Using the figures given in the above example, estimate the packet size that must be used, on the average, so that one half of the transmitted data is useful. Repeat the exercise to get the average packet size that will give 90% utilization.

The ISO OSI model focuses on standardizing the data stream at each level in the protocol hierarchy. This is probably necessary for open systems, where components at each level may come from different sources, but it is not a good software engineering methodology for constructing an integrated system.

It is not good software engineering practice to focus on data structures, particularly at an early stage in the design. It is far better to focus on functional decomposition of a problem first, and then to concentrate on the abstract components needed. As a result, when system designers get to design entire protocols, without the constraint of open systems compatability, they can optimize by combining functions of multiple layers.

Hierarchies are useful, but the strict information hiding imposed by purist ideas of data abstraction allowing the layers to be completely independent was one source of the protocol bloat illustrated above. For example, this forced each layer to include its own byte count (or some other kind of message terminator) in the messages at that level. It is the lack of transparency in the layers that forced this!

Transparent layers in a hierarchic design add function without duplicating functions of lower layers or hiding information at lower layers in the design. The concept of transparency originated in a paper by D L Parnas in the early 1970's.

An opaque layer in a hierarchidal design hides the details of lower levels in the design. Opacity is useful when one goal is to allow the lower level to be changed with no effect on upper levels, but it forces the duplication of functionality in the upper layer that could otherwise be obtained by reaching through the upper layer and directly manipulating the lower layer.

A transparent layer allows the facilites of a lower level to be used directly by upper levels, without any need to, for example, call on procedures or functions at an intermediate level which forward the request to a lower level. Thus, in a transparent network hierarchy, the session layer might directly make use of the byte count field of the transport layer in order to avoid protocol bloat. As this example illustrates, transparent layers allow high performance, but at the cost of integration; once a higher layer makes direct use of information that could have been hidden by a lower layer, the two layers depend on each other and cannot be separated.