Packetizer

3 Direct connection, formally!

3.1 General

There are no ISO/IEC International Standards or CCITT/ITU-T Recommendations covering specifications of signalling systems and protocols that have been developed especially with the OSI Physical and Data Link Layers in mind (the layers concerned with direct connection of two systems).

As was discussed in chapter 2, the specifications in these layers either predate OSI, or were developed to support networks (such as ISDN or Ethernet or Token Ring) that can (with suitable Network Layer protocols) be used to provide the OSI Network Service, and hence form part of OSI, but which can also be used to support other protocol suites.

There do exist two Standards - the Physical Service Definition and the Data Link Service Definition - that were produced as an integral part of the OSI work, but their importance, as described earlier, in gluing together layer specifications is minimal.

Another remark can be made justifying the shortness of this chapter on the bottom two layers: the principles of signalling systems and of link layer protocol design have for a long-time been well understood, and any of the many books on Data Communications will give a good treatment of the principles of design in these layers. We therefore include only three short further discussions in this Chapter, covering these two layers in turn, followed by a discussion of Formal Description Techniques (FDTs).

3.2 Getting the bits across

How to convey a string of bits from one system to another over some sort of connection (copper, radio waves, optic fibre) is the province of Physical Layer specifications.

There are a number of signalling systems in common use today, including those using parallel channels to convey eight bits at a time plus a clock signal, those conveying bits serially using wave-forms close to square-waves, those that transmit bits over the telephone network using a series of "whistles" in the voice range, and so on and so on.

As an aside, a lower-layer purist from a telecommunications background would object to the use of the term signalling to describe the means of transmitting general information (and in particular data consisting of zeros and ones), because in telecommunications the term is traditionally restricted to the transmission of information related to the setting up and tearing down of a connection (dial-tones and the like), not to the means of transferring information for the user of the connection. In this text, the term is used as it would be by a layman to describe more generally the mechanism (voltage, current, flashes of light) used for the transmission of any sort of information by some disturbance of some physical medium. The purist would probably use the term data transmission system for this more general activity.

There are interesting problems to be solved in the design of Physical Layer features, particularly problems of skew due to the charging and discharging of the capacitance of a line, and related clocking (bit synchronization) problems. There are also many interesting concerns in the design of optical fibre systems for very high-speed transmission. Whilst the development of new and better and faster signalling systems is vital to computer communications as a whole, it is not particularly related to OSI, and is outside the scope of this text.

There is only one thing I usually say about signalling systems in the Physical Layer of OSI: "If you can waggle it, and someone else can feel it, then you have a signalling system."

When I put that up in my lectures, the brighter students come back with "No, no, no! Communication needs understanding. You have to know what the wiggles mean." Of course they are right - the slide should really have added "And you have an agreement on the type of wiggles to use, and on the meaning of each wiggle, as a zero or a one for example." But that would not be so snappy, and the students would not remember it so well! Ah, the evils that are necessary when you are trying to educate and interest at the same time!

I have one other slide I use about the Physical Layer, designed to make two points: first, that bandwidth (how fast you can signal zeros and ones) is really the main concern in this layer, and bandwidth improvements are the main reason for research and development; secondly, that for the last twenty years or so it has been easier (cheaper) to get higher bandwidth over local area distances (a few kilometers) than over wide-area distances. The reader should question whether this situation will continue, or whether the electronic equivalent of motorways will emerge providing higher bandwidths than congested town driving. My slide is a further quotation from the Encyclopedia Galactica - 20085 version, shown in figure 3.1: Encyclopedia Galactica, p30608.

This also brings out the point that we will always go on producing new and better signalling systems (and means of routing and switching too). OSI will never be complete in these lower layers.

3.3 Handling the link

3.3.1 Historical

Many of the remarks made about the Physical Layer also apply to this the Data Link Layer - the work and the Standards were not produced just to support OSI, and there are many Data Communications text books that give a good treatment of link layer protocols.

Nonetheless, there are a few points to make about the link layer which will help in a general understanding of the provision of the Network Service (the main starting point for understanding OSI) and which we should deal with here.

The earliest link layer standards pre-dated OSI, and were concerned with communication when a single link (typically copper-wire or a radio link) directly connected two end-systems. In the very earliest days of data transmission (1960s), such connections were engineered specifically for the two end-systems that were to communicate, but this was soon replaced by the introduction of the ISO Basic Mode protocol standard. This was a short standard, and no-one except implementors has ever heard of it! The variant of it used by one well-known vendor - commonly called BiSync - became somewhat better known, although in the 1990s even that is not often mentioned (or used). Basic Mode was character-based, and was the origin of the so-called control characters in the ASCII character set. The first 32 bit-patterns in this character set are designated as having a "control" meaning such as

SOHStart of header
STXStart of text
ETXEnd of text
DLEData link escape
ACKAcknowledge

In the ISO Basic Mode Standard we see an attempt to transmit messages, not just a stream of bits or of characters. Each message starts with an SOH, then some addressing information (to cope with multiple stations attached to the link), then an STX, then the actual text, then an ETX, then a two octet check-sum. The single ACK character is used to send a reply saying the message has been successfully received (see figure 3.2: ISO Basic Mode messages).

In the original Basic Mode standard, the message could contain only text - control character bit-patterns were not allowed within it to avoid confusion with their use as message terminators etc. A later version introduced transparency - messages were allowed to contain any bit-pattern including those assigned to control characters, and were pre-processed to ensure that their end could still be detected by the receiver no matter what they contained. The technique was to use DLE followed by ETX as the terminator, and to double any DLE in the original message, sending it as DLE DLE. On receipt, the double DLE was turned back to a single DLE before being passed up to the user. (See figure 3.3: Transparency with DLE).

We also see in these early Standards recognition that errors do occur in transmission, and that these errors require detection using some form of sum-check, with some form of acknowledgement and retransmission mechanism if reliable communication is to be achieved.

If we move into the mid 1970s, we see the development of the so-called bit-oriented link layer protocols, of which High Level Data Link Control (HDLC) is now extremely well-known and the de facto Standard, with support from chip-sets.

It is called bit-oriented because transparency - the ability to transmit arbitrary bit-patterns in its messages - is not obtained by examining the message as a sequence of characters (octets), but rather by treating it as a pure string of bits. The technique (called bit-stuffing) is to insert a zero bit after any sequence of five successive one bits in the message, using transmission of a zero followed by six one bits to terminate the message. This is all very easy to do in transmission chip-sets, but would not be a very nice task if it had to be done by computer software! (See figure 3.4: Bit-stuffing.)

HDLC is the Grand Old Man of Data Link Layer standards, with very many options and extensions, and is still very much alive today. The LAP and LAP-B protocols used as level 2 of X.25 are a subset of HDLC. So is LLC1 and LLC2 used in the IEEE 802 (ISO 8802) set of protocols for Local Area Networks. So is the LAP-D protocol used on the D-Channel of ISDN.

3.3.2 Essential features

For the purposes of this text, we need to recognise the following essential features of the link-layer protocols that have been developed:

  • Message orientation: the protocols provide for the transmission of a sequence of messages (perhaps of limited size) which form the unit for error detection (and perhaps correction); enabling messages containing arbitrary bit-patterns to be delimited (framed) is a main concern of the link layer.
  • Error detection: the inclusion of some form of sum-check which allows received material to be recognised as a good message or as something else; the "something else" might be two (or more) messages with the framing corrupted, or one message turned into what looks like two (or more) by a frame pattern inserted by corruption of data, or a single message with the data corrupted; we don't know which of these has occurred, and all such material is usually simply discarded and ignored.

In HDLC, the "sum-check" is a Cyclic Redundancy Code (CRC) whose design is based on some quite sophisticated mathematics (Galois Field Theory - the study of polynomials with coefficients modulo 2) which predates computers. The mathematical analysis ensures that, for the number of bits added, the probability that corrupt messages will pass the check is minimised. Again, discussion of this area is outside the scope of this text (I am sure the reader regrets this!).

These framing and error detection features can usually be provided relatively simply and cheaply, with virtually all the work being done in special-purpose chips.

If the rules for the receiver are to simply ignore frames with erroneous sum-checks, then the service being provided is one of transmission of a sequence of messages with arbitrary bit-patterns, with those messages that are delivered to the user having a high probability of being uncorrupted (depending on the "strength" of the "sum-check" algorithm in use), but with the occasional message being lost.

Note that the probability of a message being lost in this service is dependent on both the underlying error rate across the link and on the length of the message. For any given error rate there is some message length such that virtually all messages are lost! Thus we see the need to impose maximum message lengths if sensible transmission is to occur. (It is also necessary to impose maximum message lengths when several logically separate transmissions are sharing a channel, in order to ensure that maximum waiting times are kept small.)

3.3.3 Additional features

Beyond framing and error detection, we find HDLC providing (optionally) two further features which add considerable complication, but provide a much improved service to the user.

The first additional feature is error correction by retransmission. In simplest terms, this involves sending a message, waiting for an acknowledgement of correct receipt, and resending it after some time-out period if an acknowledgement is not received. The design of this protocol is quite complicated: you have to allow for the possibility that the acknowledgement and not the original message got corrupted (lost); you have to avoid round-trip times too often; you have to worry about an acknowledgement being delayed rather than lost; and so on and so on. It is an interesting tutorial exercise to develop a simple protocol (that nonetheless correctly does the job required) for error correction by retransmission. A number of Data Communication texts describe this protocol - the thing to look for is a discussion of the alternating bit protocol (including a treatment of parasitic transmissions, which arise if ACKs with the wrong sequence number produce retransmission of the data rather than being ignored, resulting in the double transmission, to no useful effect, of all subsequent messages.) The protocol is a simplified version of HDLC. Such a detailed tutorial is beyond the scope of this text, but the important point to recognise is that the provision of error recovery by retransmission adds considerable complexity over the basic functions.

The second additional feature uses many of the same mechanisms as are developed for error correction by retransmission. This is flow-control - the ability for a receiver to say "Hey, slow down, you are sending me stuff faster than I can handle it, my buffers are filling up, and we are in danger of hitting an over-run situation." Again, problems arise if a "stop-sending" message gets corrupted (lost), but even worse problems arise if an "its OK to go on now" message gets corrupted, because this produces a deadlock situation. (One end thinks flow control is released and that the other end has nothing to send, whilst the other end has material to send, but thinks that flow is still blocked). The detailed design of flow control provision is usually integrated with retransmission mechanisms, and is similarly an addition of considerable complexity to the basic protocol.

HDLC has within it not only defined subsets containing only the essential framing and error detection features, but also defined subsets with full error correction by re-transmission and flow control.

The main purpose, however, of this amount of detailed discussion is to identify the sorts of features that we need to provide between end-systems, and to encourage the reader to think about how we should use concatenated (multiplexed) links. (See section 4.2).

3.4 Formal Description Techniques (FDTs)

This discussion is something of an "aside", but the reader who wishes to progress to reading OSI Standards needs to be aware of the FDT work, and a brief treatment of this comes appropriately after the discussion of the complexity of protocols which is what gives rise to the need for some notation (an FDT) which will enable clear, unambiguous and error free specifications to be produced.

If you pick up any of the main OSI Standards specifying a protocol, you will find some more-or-less readable English language text, usually followed by several pages of State Tables.

The State Table concept is a fairly simple one, particularly for those readers familiar with spread-sheets. It has been employed from the earliest days of OSI specification work. An example is given in figure 3.5: A simple pair of state tables for what is there called the EG-service and protocol (EG for "example"). This is an asymmetric service and protocol so the State Table for the EG-sender and the EG-receiver are different. The protocol being defined is actually the Alternating Bit Protocol, with the parasitic transmissions bug.

In developing a State Table, the designer identifies a number of states that an implementation can be in (the first is the initial state, the others are the result of earlier exchanges). For each state, there is a single column in the State Table. (In the example, the sender initial state is S-WAIT0 (S for State), with the other states S-WAIT1, S-WACK0 (meaning that an ACK0 is awaited), and S-WACK1, and the receiver initial state is S-WAIT0 with other state S-WAIT1). Note that it is often the case in practice that a State Table is too large to print in its entirety on a single page, so the logically single State Table is often printed over several pages as a set of related tables. We are describing the single logical State Table here.

The State Table has one row for each event that can occur in an implementation. The most important events are the receipt of the different types of message that constitute the protocol, and the issue of service primitives (requests for transmission of messages) by the layer above, together with the expiration of any timers that might be running.

(In the example, events at the sender are the issue of an EG-DATA request service primitive from the layer above, arrival of an ACK0 or ACK1 message from the link, or expiry of a timer.)

The cells (row-column intersections) contain the action to be taken when that event occurs in that state (usually either the issue of a service primitive to the layer above, or the transmission of a protocol message) followed by the new state to be entered as a result of that event and action. (Thus the EG-DATA request in state S-WAIT0 at the sender results in transmission on the new data as a DATA0, setting the timer, and entering state S-WACK0. Arrival of an ACK1 message in state S-WACK0 results in retransmission of DATA0 with the old (previous) data, resetting the timer, and staying in the same state. The reader should note that this cell (and its equivalent in S-WACK1) is what produces parasitic transmissions, and may care to modify the State Table to correct this bug!

For local events (issue of service primitives), an event may be forbidden in some states (for example, a T-DATA request cannot be issued until a connection has been established), and the State Table can indicate simply that that event cannot occur in that state - enforcing that is a local matter. On the other hand, for external events (arrival of messages), the events can occur in any state if the other communicating system is non-conforming. The State Table has to reflect this by specifying actions and new states in such cases. Thus in the example, the EG-DATA request for the sender can be decreed never to occur in certain states because it is a local matter to prevent it. Similarly, the TIMER event cannot occur where marked X because it is logically impossible for it to occur in these states (the timer is not running). All other events can, in theory, occur in all states (perhaps only if the peer is non-conformant) and must be covered.

The State Table approach is usually called a "semi-formal description technique", to distinguish it from "true" Formal Description Techniques. In the example, the precise actions indicated by "DATA1(OLD)" (for example) need English language specification (it means "resend a DATA1 message, with the same data as was sent last time"). This is common in the state table approach, and is what makes the technique only semi-formal.

Formal Description Techniques are part of what the reader may have encountered more generally as Formal Methods - the use of a language or notation for specifying systems that is formally rooted in mathematics, and which can be parsed and understood by computers. (Perhaps the best-known such languages for general system design are Z and VDM - not yet standardised. If you have never heard of them, it doesn't matter.)

In the case of Formal Methods for OSI protocol specification, two languages (FDTs) have been developed and standardised. One is called Estelle, and one is called LOTOS (Language of Temporal Ordering Specification).

There is a third language, favoured by some CCITT/ITU-T workers, called System Description Language (SDL) which is closer to Estelle than to LOTOS, but which does not have an ISO Standard, and is not generally regarded by ISO workers as part of OSI in the way that Estelle and LOTOS are accepted, nor is it normally used for specifying the main-stream OSI protocols. (It is, however, standardised as a set of CCITT/ITU-T Recommendations in the Z.100 series). SDL will not be discussed further in this text.

Estelle is an extension of Pascal, and critics of Estelle assert:

  • It specifies too much that should be left unspecified (implementation matters), because it is effectively writing a complete computer program for the implementation of the protocol.
  • It is very verbose, Estelle specifications frequently being several times the size of the corresponding English text.
  • Specifications written using it are hard to transform and analyze for correctness because it contains all the features of a general programming language (so you can't, for example, even prove in general that it will terminate).

On the other hand, much of an Estelle specification is fairly easily readable by any-one with a programming background. Figure 3.6: A piece of Estelle is a piece of Estelle. We shall not attempt to explain it, but the careful reader will recognise a certain similarity to figure 3.5!

LOTOS, by contrast, produces much shorter specifications that are amenable to computer analysis. It does, however, use symbols such as ? and ! with a very specialised meaning, making a LOTOS specification extremely hard to read by anyone who has not been steeped in the language. Figure 3.7: A piece of LOTOS is a piece of LOTOS, but it is too small a fragment for useful discussion of its meaning.

In very crude terms, workers on the European side of the Atlantic Ocean tend to favour LOTOS, whilst workers on the other side of the Atlantic Ocean tended to favour Estelle during the 1980s.

Most OSI protocol Standards have the authoritative specification done using English text and State Tables. In addition, there is sometimes an informative Annex containing an Estelle or LOTOS description, but more commonly such a description (if it exists in a published form at all) is published as an ISO Technical Report, not as a Standard or part of a Standard. There is one exception, where the latest work in the FTAM (File Transfer, Access and Management) Application Layer Standard (see later text on FTAM) makes very heavy use of LOTOS as the main authoritative text for specifying the Overlapped Access extension to FTAM.

I will end this discussion with another quotation from the Encyclopedia Galactica - 20085 version, and two slides I sometimes use. The quotation is shown in figure 3.8: Encyclopedia Galactica, p49576, and the first slide asks:

Why FDT's?
Prevent Omissions
Prevent Ambiguity
Allow machine analysis of specifications
And because they are fun!

FDTs can help to ensure a specification is complete and unambiguous, and potentially allows a computer to analyze it in various ways to detect some errors, or to generate test suites, and with the right sort of (warped?) mind, you can get a lot of fun out of developing a detailed and correct FDT specification!

The second slide redresses the balance:

Why not FDT's?
Specs take a long time to produce
Too much detail, too easy to get wrong
Shortage of people with FDT skills
And they are boring! (and hard!)

It takes a lot of care and time to develop a specification in an FDT, and there are few people with the necessary skill (or even with the skill to check that the result is correct). If you add the need for protocol design skills and knowledge of an application area to the FDT skill, the number of people able to do the work gets even smaller. And finally, it would be hard for anybody to take a piece of FDT to bed with them and enjoy reading it (too many trees obscuring sight of the wood), whereas I have on many occasions fallen asleep reading English language text specifying protocols!

<< >>