SideBar

Introduction

A protocol is a method of communication between entities. By its very definition, a protocol is 'open'. Any two entities which use it can communicate with each other. Broadly speaking, a protocol has three parts.

Procedures, which define the actual activities which are covered by the protocols.
Message encodings and decodings, which define how information is represented within the protocol interchange.
Services which are offered (from other layers) and expected (from lower layers)

Definition of a good protocol

A good protocol definition has several attributes which can be verified by formal or informal methods:

A protocol is consistent, if all events or sequences of events leads to an internal state and an external action which is predictable and repeatable to a reasonable degree of scrutiny.

A protocol is correct if all paths involving the same sequence of events achieve the same state, assuming that the start was equivalent.

A protocol is live if for every state (other designated 'dead' states), there is a defined transition to the rest of the protocol space.

A protocol is predictable if the effect of the initial event/state diminishes as time passes. Otherwise, the protocol is said to be infinitely sensitive to initial conditions.

Protocol engineering in software

Though protocol engineering has happened for a long time, the first discussion of protocol engineering as a formal science coincided with the development of the OSI reference protocol stack. This also coincided with a great deal of interest in formal methods for protocol verification, etc. The OSI model, though not widely used, was a very interesting reference for studying protocol design in abstraction. Some of the issues that were discussed at that time are valid today.

Fundamental issues

A fundamental context of protocol engineering is the concept of event delivery and service access between layers. Events can be either messages and/or timers.
Services are typically functions which are executed by a lower layer, using parameters provided by the upper layer. Services are nearly always invoked by the upper layer.

Event handling

Appropriate design of event handling is challenging for software design, because events occur at any time and may contain data which is contextual to that flow only. Software is typically not designed to operate in this manner - software procedures are written to be sequential, starting at one particular point. There are two workarounds that are used, both of which have their limitations. In the first, the event handling is queued or deferred till the software reaches a particular point in the processing chain is reached; typically, the top of a waiting loop. In the second, the event is responded to instantly, but the processing is done in a separate function or thread and the outcome has to be integrated into the context of the main program separately. Both are a problem. Unlike hardware interrupt handlers, it does not allow for pre-emption, which is a very fundamental aspect of event handling. Also, without a context for event handling, it is difficult to verify correctness of the operation.

Service access

A second issue, similar to the problem of event handling is that of service access. Services are provided to higher layers by the layer immediately below. There are multiple problems to be solved with service access. One is the mode of access; how does a higher layer communicate with a lower layer. The second is the response to access. How does the lower layer respond and what information should it have so as to provide a meaningful response. See [Saha97] for one attempt to solve this problem.

Protocol modeling

Protocol stacks can be modelled in one of two modes. The first is a dataflow algebra , which describes the protocol as a series of steps dealing with the manipulation of data. Data flow algebras are very convenient when all functions would be executed atomically and the result would be meaningful to the service requester. In the real world, the execution of a function can "hang", take large amounts of time, fail and/or return completely unmeaningful results. The problem is that time-scales between layers are quite different, and there it is very hard to define a meaningful language by which the service requester can explain the connotations of the service request to the service provider. The second mode is a process algebra, where the stack consists of multiple automata, each operating in its own thread. The use of threads isolates the time-scale problem. In this model, the upper layer issues a request to the lower layer for a service. It then continues its work - the lower layer, on completing the service sends an event back to the service requester, which is handled as the paradigm of other events. This model, too, has its special issues, especially of communication of events, alluded to in an earlier section.

There have been multiple attempts at solving the problems mentioned above, typically by specifying new languages which fit the appropriate paradigm. See [Muffke04] for an excellent introduction.

Estelle is a process algebra compiler, designed specifically to handle distributed systems. Estelle consists of multiple modules, each of which is a self-contained finite state machine (FSM). Modules communicate with each other using communication channels, which have some very specific properties. Modules can be nested. The FSM inside a module can have triggered and spontaneous transitions and each transition has an effect. The state machine in OPNET is derived from an Estelle logic. There is a long history of ESTELLE use, especially by the US Military for formal verification. The problem with Estelle is that a full Estelle specification is very complex; a single FSM can easily have over 2000 states [Uyar01]
SDL or the State Description language is similar to the Estelle language, except that it supports state transition diagrams. The author has had experience using SDL to model multi-layered protocol stacks. While SDL provides excellent support for transaction modeling, it is weak when it comes to modeling of algorithms. However, it provides a very good model for the environment, which is something not available in Estelle.
LOTOS or the Language of Temporal Ordering and Specification is designed to specifically target issues of temporal nature, such as livelocks, deadlocks, etc. The use of LOTOS is somewhat limited, since it is a difficult language to learn.

Practical issues in protocol design

We now look at practical issues of designing a protocol stack, some of which have been hinted at previously. Let us reopen the discussion on function vs threaded design we have touched upon briefly earlier. The choice is between implementing a protocol layer as a set of atomic procedures or as an autonomous entity . There are various pros and cons

An atomic procedure acts within the context of the calling process. This means it inherits the properties of that process. This may include priority settings, memory management models, etc. The calling process collects the return status as soon as it is completed and can carry on with its own operations. Atomic procedures also help to make the implementation formally verifiable.
Implementing a protocol as an atomic procedure also means that supervising processes for the calling process, such as debuggers, retain control all the way through.
On the other hand, implementation of a protocol as an atomic process means that the calling function effectively blocks till the procedure is over. If the procedure is relatively atomic (compared to the timescales that the calling process works with), then this doesn't matter. On the other hand, this may be a concern in realtime systems, where no single system can afford to wait indefinitely.
An atomic procedure cannot return interim results. It returns one final results when the procedure is complete. This can lead to very undesirable results. For example, a sendto() to a TCP call returns, not when the data has been transmitted, but when the data has been queued within the underlying stack. Ideally, there would be two points of response, one when the data is queued for delivery and one when it is actually acknowledged. However, a standard functional approach.

Distributed Design

There are many protocols which are meant to work in an distributed environment, with a large and sometimes unknown number of users. Examples include Ethernet, Aloha, cache coherency protocols for symmetric multiprocessing systems, bus management systems, etc. Design and implementation of a distributed protocol is especially challenging, since it is too difficult to test with large numbers of IUTs.
This section is to be extended.

Application level framing

Application level framing was first proposed by Clark and Tennenhouse in the 1990s [ALF90]. The purpose of ALF was to create a new genre of protocol stacks, where the application has full knowledge and control over the outgoing packet all the way down to the bottom layer of the protocol stack. In ALF, the final data packet is very much dependent on the kind of application level data that it is carrying. The purpose of ALF was manifold. First, the intention was to percolate the nature of the data being transmitted down to the lower layers, so that the lower layers could make intelligent choices in the case of error situations. One common example is the delivery of video buffers; when there is a loss of data, it might make more sense to deliver complete buffers in out-of-order sequence, rather than wait for the complete sequence to be recovered before delivering the data to the layers above. The latter can mean a sudden rush of processing load on the higher layer. The second was to streamline processing of data packets through the stack, especially for high-performance data transfer protocols.
Key concepts in ALF are already very much in use throughout the world of data protocols. For example, IP fragmentation is disabled through most of the Internet, and TCPs directly discover and use the appropriate MTU to reduce load on the IP system. The design of the adaptive coding and modulation feature in the GPRS physical layer was done so that the link layer could refragment packets more easily. Realtime Transport Protocol or RTP is a full scale implementation of a protocol based on ALF principles. In RTP, the base protocol spec is supplemented by different profiles, which provides different packet formats depending on what it is carrying i.e. G.711 voice, video, etc. This is directly controlled by the application using RTP.

References


[Estelle91] Budkowski, Dembinski, "An introduction to Estelle: A specification language for distributed systems", Computer Networks and ISDN Systems, 1991

[Saha97] Abheek Saha, Maharaj Mukherjee, P.Dhar, "Design and implementation of a Network SAP for OSI compatibility", Computer Networks and ISDN Systems, 1997

[Muffke04] Muffke, "A better way to design communication protocols", Ph.D. Thesis, University of Bristol, 2004

[Uyar01] Uyar, Fecko, Duare,Sethi, "A formal approach for development of network protocols," 2001

[ALF90] Clark, Tennenhouse, "Architectural considerations for a new generation of protocols", Proceedings of the ACM Sigcomm'90 (1990)