Platform-based Design Methodologies for Communication Networks

Marco Sgroi, 2002 Ph.D. (advisor: Sangiovanni-Vincentelli) 

    The increasing complexity and the shortening of the time-to-market windows make the design of electronic system a challenging task that cannot be handled by traditional methodologies anymore. New methodologies are needed to improve design productivity and derive high-performance low-cost implementations. This requires to develop formal methods that synthesize correct-by-construction implementations and maximize reuse of pre-designed components.
In distributed systems the design of the communication among components is a difficult problem due to the tight constraints on performance and cost (e.g. power). This Dissertation proposes a methodology for the design of communication networks that is based on the principles of Platform-based Design. The methodology allows to eliminate expensive loop iterations by structuring the communication network design problem as a sequence of refinement steps that progressively restrict the design space until the final implementation. The refinement procedure identifies multiple layers of abstractions, called network platforms, that are defined as libraries of resources providing communication services to the upper layers. Reuse is supported at each layer by the definition of libraries of pre-designed components.   
    The Dissertation focuses on the problem of designing protocols, i.e. the rules of interaction among system components, and defines a formal methodology based on the principle of orthogonalization of concerns. It separates the communication and computation parts of a specification to maximize design reuse and separates function from architecture to facilitate the exploration of alternative implementations.
    An approach to synthesis from scenario-based specifications, called Ulysses, is proposed. 
    Functionality is captured first specifying sequences of protocol interactions, called scenarios, and their relationships, and then describing the internal protocol computation functions. Scenarios are initially specified as a partial order on the set of send and receive events using Message Sequence Charts (MSCs). Petri Nets (PNs) are used as an underlying model to formally define the MSCs semantics because they support the analysis of the specification for early error detection and the synthesis of the implementation. The synthesis procedure is based on a covering algorithm that uses patterns to derive a consistent Petri Nets model from a set of MSCs. The approach currently can be applied only to the class of protocols that do not require to store multiple packets of the same type over a channel and therefore can be modeled using safe PNs.
    Implementing a functional specification requires to select a set of architectural resources and map the functional components onto them. This procedure is based on functional models that are unbiased towards any specific implementation and relies on performance estimation and simulation tools to compare different implementations and validate the mapping. The Unified Modeling Language (UML) is used to visualize both function and architecture components and express their relationships.
    The proposed methodologies are demonstrated through the application to the design of two wireless networks.