x-kernel(ID:5519/xke001)References: in IEEE Transactions on Software Engineering 17(1) January 1991 view details The International Organization for Standards (ISO) has defined two formal description techniques originally intended for developing the ISO OSI protocol suite. These techniques are LOTOS and Estelle. LOTOS, based on Milner’s Calculus of Communicating Systems, is an algebraic technique with functional properties. Like many functional languages, it is very effective for describing its fundamental abstraction, processes. Unfortunately, also like many functional languages, these abstractions are rigid and may not fit existing protocols without some pain - exactly the pain that protocol languages are supposed to avoid. LOTOS users report some problems with using the language for specification, and LOTOS presents very serious challenges to the compiler writer, including valid programs which potentially generate an infinite number of processes. It seems doubtful that LOTOS specifications can be made to run efficiently. Estelle is one of many protocol languages based on a finite state machine model much like that often used in parsers. Estelle, like LOTOS, includes asynchronous parallelism; it is based on Pascal, and includes a module system (bound up with the parallelism structure) where processes (modules) communicate through broadcast signals. Estelle can be used to create semi-automatic implementations of reasonable performance. However, experience with large protocols is not reported, and high performance is not discussed. Furthermore, the state machine model and its cousin the Petri machine model have intrinsic problems for modeling protocols: the division into states often does not correspond to anything real in the protocol, and relationships between states can become very complicated and difficult to change, even in carefully layered protocols. Esterel is a version of Estelle without asynchronous parallelism: an Esterel specification has a defined sequential execution. High performance Esterel compilers are being developed; however, full implementation of a large protocol is not reported. In terms of language, Esterel suffers from many of the same problems as Estelle due to their common extended finite state machine model. RTAG is based on a context-free attribute grammar. RTAG provides a relatively natural syntax with equivalent modeling power to extended finite state machines. Efficient compilers are reported in the literature, although efficient turns out to mean arguably efficient enough for research use, i.e., simple protocols suffer a factor of 2 slowdown. This slowdown comes partially from parallelism in the language. RTAG is not always suitable for existing protocols, just as yacc is not always suitable for describing computer languages. The x-kernel provides an infrastructure and various tools for creating protocol stacks. Prolac is complementary with the x-kernel, which focuses on organizing protocol stacks; Prolac is primarily designed for implementing a single protocol. Morpheus, an object-oriented protocol language, enforces a large number of constraints on the protocol programmer. These constraints are restrictive enough that existing protocol specification[s] may not be implementable in Morpheus. While some of the constraints are meant to increase the knowledge available to the compiler to enable domain-specific optimizations, others seem to exist solely to prevent the programmer from making bad design choices. Impressive results are reported for UDP speedup, but we regard Morpheus’s inflexibility and inability to implement real protocols as definitive. in IEEE Transactions on Software Engineering 17(1) January 1991 view details |