Microservices based architectures are increasingly widespread in the cloud software industry. Still, there is a shortage of auto-scaling methods designed to leverage the unique features of these architectures, such as the ability to independently scale a subset of microservices, as well as the ease of monitoring their state and reciprocal calls. We propose to address this shortage with ATOM, a model-driven autoscaling controller for microservices. ATOM instantiates and solves at run-time a layered queueing network model of the application. Computational optimization is used to dynamically control the number of replicas for each microservice and its associated container CPU share, overall achieving a fine-grained control of the application capacity at run-time. Experimental results indicate that for heavy workloads ATOM offers around 30%-37% higher throughput than baseline model-agnostic controllers based on simple static rules. We also find that model-driven reasoning reduces the number of actions needed to scale the system as it reduces the number of bottleneck shifts that we observe with model-agnostic controllers.

The authors previously showed that a complex layered performance model could be simplified by aggregating the contributions of subsystems, following a few simple principles which give good accuracy in many cases. The question of which subsystems to merge in layered performance models is further examined here, leading to identifying groups of subsystems (corresponding to "tasks" in layered queuing models) which can be safely aggregated. The grouping begins by identifying tasks which should be preserved, not aggregated, including those which are (or might become) bottlenecks. Then the groups are defined by their relationship to these preserved tasks. Aggregation by groups provides adequate accuracy in the vast majority of cases examined.

Management of large service centers and clouds requires adaptation to changing conditions and workload. Optimal deployments are possible on private clouds if there is full knowledge of the applications. Previous work,CloudOpt,combines large-scale linear optimization with a detailed non-linear performance model of every application to determine such deployments. However, when conditions change the new solution is independent of the previous deployment, and often requires excessive changes. Practical adaptive management needs a controlled compromise between the effort and cost of changing the current deployment, and the value lost by not making a change. This paper enhances CloudOpt by incorporating adjustablepersistencetechniques to constrain the deployment changes in each update. Three such techniques are compared, and the best ones reduce the reconfiguration effort at each adaptation step by about 90 percent, with about a 5-10 percent penalty in running costs. Persistence techniques impose no reduction in the scalability of CloudOpt.

In Model Driven Engineering, the relationship between a source and target model can be maintained, when the source model undergoes changes, by a coupled transformation, whereby changes applied to the source model are incrementally propagated to the target model.Cross-model traceability links are key to applying the correct changes to the target model.The coupled transformation considered in this paper propagates changes to a Layered Queueing Network (LQN) performance model (originally derived from a UML design model of a SOA system) as an effect of applying design patterns to the SOA model.A special problem arises because of differences in the level of abstraction between UML and LQN (i.e. a performance model element may represent a set of many design model elements).This paper bridges the abstraction gap between models by proposing traceability links that use new collection types (not defined in the source metamodel) to represent complex source model elements, which are then mapped to simple target model elements.

COLOR (client-oriented layered optimistic replication) is a combination of optimistic and conservative data replication that allows cloud services to be replicated across widely distributed locations without suffering from the latency overhead of strict algorithms, and with quantifiable and controllable tradeoffs between performance and consistency guarantees. The COLOR solution adopts a layered approach to enable optimistic delivery of client messages on top of any existing storage layer that manages the strict replication of the cloud service. When clients may be temporarily exposed to inconsistent states due to replication failures, such inconsistency is made recoverable similar to "optimistic concurrency control" for clients that cache the server state. COLOR supports different numeric parameters to trade the strict consistency for better performance to possibly match Eventual Consistency, while the end-to-end consistency is always guaranteed as the storage layer will never deliver any client messages generated from inconsistent states.

Service Oriented Architecture (SOA) patterns can be applied to improve different qualities of SOA designs.The performance impact of a pattern (improvement or degradation) may affect its use, so we assess its impact by automatically generated performance models for the original design and for each candidate pattern and pattern variation.This paper proposes a technique to incrementally propagate the changes from the software to the performance model.The technique formally records the refactoring of the design model when applying a pattern, and uses this record to generate a coupled transformation of the performance model.The SOA design is modeled in UML extended with two profiles, SoaML and MARTE; the patterns are specified using Role Based Modeling and the performance model is expressed in Layered Queuing Networks.Application of the process, and pattern performance exploration, is demonstrated on a case study.

The first ACM Workshop on Challenges in Performance Methods for Software Development is held in Austin, Texas, on Jan. 31 2015, and is co-located with the 2015 ACM/SPEC International Conference on Performance Engineering (ICPE). Its purpose is to open up new avenues of research on methods for software developers to address performance problems. The software world is changing, and there are new challenges. As its name implies, the workshop includes the description of problems as well as solutions. The acronym WOSP-C also recalls the original discussion-heavy format of WOSP, the ACM International Workshop on Software and Performance, which has been a co-organizer of ICPE since 2010.

Current cloud management systems have limited awareness of the user application, and application managers have no awareness of the state of the cloud. For applications with strong real-time requirements, distributed across new multi-cloud environments, this lack of awareness hampers response-time assurance, efficient deployment and rapid adaptation to changing workloads. This paper considers what forms this awareness may take, how it can be exploited in managing the applications and the clouds, and how it can influence cloud architecture.

Design patterns for Service Oriented Architecture (SOA) provide solutions to architectural, design and implementation problems, involving software models in different layers of a SOA design. For performance analysis, a performance model can be generated from the SOA design and used to predict its performance. The impact of the design patterns is also reflected in the performance model. It is helpful to be able to trace the causality from the design pattern to its predicted performance impact. This paper describes a technique for automatically refactoring a SOA design model by applying a design pattern and for propagating the incremental changes to its LQN performance model. A SOA design model is expressed in UML extended with two standard profiles: SoaML for expressing SOA solutions and MARTE for performance annotations. The SOA design pattern is specified using a Role Based Modeling Language (RBML) and their application is automated using QVT-O. Automated incremental transformations are explored and evaluated for effectiveness on a case study example.

This paper proposes a system model that unifies different optimistic algorithms designed for deploying geographically replicated services in a cloud environment. The proposed model thereby enables a generalized solution (COLOR) by which well-specified safety and timeliness guarantees are achievable in conjunction with tunable performance requirements. The proposed solution explicitly takes advantage of the unique client-cloud interface in specifying how the level of consistency violation may be bounded, for instance using probabilistic rollbacks or restarts as parameters. The solution differs from traditional Eventual Consistency models in that inconsistency is solved concurrently with online client-cloud interactions over strongly connected networks. We believe that such an approach will bring clarity to the role and limitations of the ever-popular Eventual Consistency model in cloud services.

Estimation techniques have been largely applied to track hidden performance parameters (e.g. service demands) of web based software systems. In this paper we investigate dynamic multiclass modeling of such systems, with variable classes of service, aiming at finding a low complexity model yet with enough accuracy. We propose a combination of clustering algorithm and tracking filter for effective grouping of classes of services. The tracking estimator is based on a layered queuing model with parameters for CPU demands and the user load intensity of each class of service. Clustering uses the K-means algorithm. The target application is autonomic control of web clusters, where changes occur at different rates and amplitudes and at random time instants. Experiments show that the tracking is effective, and reveal good filter settings for different variations.

Patterns employed for the development of a service oriented system may affect its non-functional properties, including performance. Service Oriented Architecture (SOA) design patterns provide generic solutions for many architectural, design and implementation problems, and any pattern may have an impact on performance, either positive or negative. This research considers how to characterize the performance impact of a SOA design pattern, which includes characterizing some aspects of the design and usage environment as a whole (for example, the scale of the workload and the availability of concurrent platforms for the eventual deployment). The approach uses performance models to characterize the application and the impact of the pattern on it. The planned approach exploits the context of model driven engineering (MDE) to give rapid feedback to developers about the potential impact of a pattern. Model transformations are used to generate the performance model, and to propagate the effect of applying a SOA design pattern to the performance model. The approach is sketched here with a preliminary case study, demonstrating its feasibility.

Adaptive management of a software service system can take advantage of a performance model which can predict the effect of proposed changes, before they are deployed. As the system varies over time the model parameters can be tracked by an estimator such as a Kalman Filter, so that decisions can be updated. The filter is valuable when parameters are 'hidden' and cannot be directly measured without excessive cost (as is usually the case for the CPU time of a service). Because there may be significant delays in some management control actions (especially in deploying a new replica of a service), it is also important to be able to predict the changes ahead somewhat in time, that is, to predict the trends. The trend predictor itself needs to be estimated from observed trends in the model parameters. This work uses an autoregressive model for trend prediction and integrates it with the parameter estimator, in a single Kalman Filter, using auxiliary states for the parameter evolution process. This paper describes how the trend model is constructed, and evaluates its effectiveness. It compares the overall performance predictions to a simpler trend predictor using linear extrapolation of the fitted parameter time-series, which turns out to be almost as good. The approach is validated on a real system running a benchmark web application.

When deploying services in a cloud, a balance must be found between performance and capacity of the service, and the memory available on nodes. This is further complicated if the number of replicas of an application is limited, for instance by the available number of licenses. The analysis of interference between services must scale to large numbers of host nodes, applications, replicas of applications, and classes of users. This paper combines a multi-dimensional packing heuristic and network flow optimization to satisfy simultaneous constraints on throughputs, processor utilizations, memory availability and license availability, at a minimum cost and with a minimum of host processors.

Layered queues are a canonical form of extended queueing network for systems with nested multiple resource possession, in which successive depths of nesting define the layers. The model has been applied to most modern distributed systems, which use different kinds of client-server and master-slave relationships, and scales up well. The layered queueing network (LQN) model is described here in a unified fashion, including its many more extensions to match the semantics of sophisticated practical distributed and parallel systems. These include efficient representation of replicated services, parallel and quorum execution, and dependability analysis under failure and reconfiguration. The full LQN model is defined here and its solver is described. A substantial case study to an air traffic control system shows errors (compared to simulation) of a few percent. The LQN model is compared to other models and solutions, and is shown to cover all their features.

To update a performance model, its parameter values must be updated, and in some applications (such as autonomic systems) tracked continuously over time. Direct measurement of many parameters during system operation requires instrumentation which is impractical. Kalman filter estimators can track such parameters using other data such as response times and utilizations, which are readily observable. This paper adapts Kalman filter estimators for performance model parameters, evaluates the approximations which must be made, and develops a systematic approach to setting up an estimator. The estimator converges under easily verified conditions. Different queueing-based models are considered here, and the extension for state-based models (such as stochastic Petri nets) is straightforward.

User and system behaviour is difficult to predict for novel systems, and this affects the capacity of the system (the number of active users that can be supported with acceptable response delay). This leads to a range of values, in the form of a feasible or acceptable region for the potential capacity, conditional on the uncertain parameters. This work considers uncertainties in the delay between requests (user think time), network latency, and cache behaviour due to users' locality of reference. The acceptable region is shown to be bounded approximately by linear constraints which are easy to derive. This simple result is useful for sensitivity and scalability analysis, and appears to have been overlooked. It is applied to a Web-based system for telephony, using voiceXML for service ranging from interactive voice response, to voice-based E-mail.

Models can help to understand the performance aspects of a computer system from the software architecture and its configurations, but ease of model creation is critical. A compositional model-building approach is described here, in which component submodels are generated from the scenarios they participate in. Submodel classes are derived from an analysis of behaviour patterns as the scenarios traverse the software components. Then submodels are instantiated and combined in the overall system model. The approach is particularly effective in peer-to-peer systems in which subsystems inherit most of their behaviour from a few shared patterns, termed "behaviour-inheriting peer" (BIP) systems. A model-building algorithm is described, and is demonstrated on a prototype emulator for a network of routers. The emulator, called CGNet, can be configured for its deployment and for traffic patterns and routes. An automatic model-generator uses this information to build a model which represents the overall system configuration. The approach is quite general and can be used to model component-based systems in which the components themselves are created in many configurations.

Dependable-LQNS is a software tool for modeling and evaluating performability of fault-tolerant layered distributed applications that use a separate architecture for failure detection and reconfiguration. It takes into account the effects of management architecture, application software architecture, failure of management and application components in the dependability computation. It uses a combination of minpath algorithms, AND-OR graphs, non-coherent fault trees and Layered Queueing modeling in the analysis.

Increasingly, fault-tolerant distributed software applications use a separate architecture for failure detection instead of coding the mechanisms inside the application itself. Such a structure removes the intricacies of the failure detection mechanisms from the application, and avoids repeating them in every program. However, successful system reconfiguration now depends on the management architecture (which does both fault detection and reconfiguration), and on management subsystem failures, as well as on the application. This paper presents an approach which computes the architecture-based system reconfiguration coverage simultaneously with its performability.

To evaluate a software specification for its performance potential, it is necessary to supply additional information, not required for functional specification. Examples range from the execution cost of operations and details of deployment, up to missing subsystems and layers. The term "completions" is used here to include all such additions, including annotations, component insertions, environment infrastructure, deployment, communication patterns, design refinements and scenario or design transformations which correspond to a given deployment style. Completions are related to the purpose of evaluation, so they are tailored to describing the performance at a suitable level of detail. Completions for evaluating other attributes such as reliability or security are also possible. The paper describes how completions are added to a specification regardless of the language used (provided that it describes the system behaviour as well as its structure), and experience with completions in Use Case Maps.

To reverse engineer scenarios from event traces, one must infer causal relationships between events. The inferences are usually based on a trace with sequence numbers or timestamps corresponding to some kind of logical clock. In practice, there is an explosion of potentially causal relationships in the trace, which limits one's ability to extract scenarios. This work defines a more parsimonious form of causality called scenario causality that concentrates on certain major causal relationships and ignores more subtle, potentially causal links. The influence of an event is restricted to the particular scenario it is part of. An event which is not a message reception is defined to be caused by the previous event in the same software object, while a message reception is caused by a sending event in another object. The events are ordered to form a scenario event graph where typed nodes are events and the typed edges are certain causal relationships. Intuitively, we might say that most logical clocks, which identify events which "happened before" a given event and, thus, are potentially causal, give an upper bound on the set of causal events; scenario causality identifies a lower bound. The much smaller lower bound set makes it possible to reverse engineer and automate the analysis of scenarios.

Performance is determined by a system's resources and its workload. Some of the resources are software resources which are an aspect of the software architecture; some of them are even created by the software behaviour. This paper describes software resources and resource architecture, and shows how resource architecture can be determined from software architecture and behaviour. The resource architecture is distinct from views of software architecture which describe software components, but it is related to the so-called "execution view" of architecture. The paper considers how resource architecture emerges during design, the relationship of software and hardware resources, some classes of resource architecture, and what they can tell us about system performance. Other uses of resource architecture are, to analyze deadlocks, to understand special software architectures developed for demanding situations, and to analyze how subsystems fit together when they share resources. Resource architecture can be described using description languages (ADLs) developed for software architecture.

Many distributed systems must be scalable, meaning that they must be economically deployable in a wide range of sizes and configurations. This paper presents a scalability metric based on cost-effectiveness, where the effectiveness is a function of the system's throughput and its quality of service. It is part of a framework which also includes a sealing strategy for introducing changes as a function of a scale factor, and an automated virtual design optimization at each scale factor. This is an adaptation of concepts for scalability measures in parallel computing. Scalability is measured by the range of scale factors that give a satisfactory value of the metric, and good scalability is a joint property of the initial design and the scaling strategy. The results give insight into the scaling capacity of the designs, and into how to improve the design. A rapid simple bound on the metric is also described. The metric is demonstrated in this work by applying it to some well-known idealized systems, and to real prototypes of communications software.

An approach called PERFECT is described which evaluates the feasibility of proposed software concurrency architectures for a set of scenarios and a set of quality-of-service requirements. An evaluation is performed by constructing and simulating a virtual implementation which conforms to the specified behaviour and the specified concurrency architecture. For simulation, the execution of application activities and kernel primitives must be sequenced for each concurrent thread. The approach is successfully demonstrated on specified scenarios for a group communication server.

Performance models of software designs can give early warnings of problems such as resource saturation or excessive delays. However models are seldom used because of the considerable effort needed to construct them. The ANGIOTRACE/sup TM/ was developed to gather the necessary information from an executable design and develop a model in an automated fashion. It applies to distributed and concurrent software with synchronous (send-reply or RPC) communications, developing a layered queuing network model. The trace-based load characterization (TLC) technique presented here extends the ANGIOTRACE/sup TM/ to handle software with both synchronous and asynchronous interactions. TLC also detects interactions which are effectively synchronous or partly-synchronous (forwarding) but are built up from asynchronous messages. These patterns occur in telephony software and in other systems. The TLC technique can be applied throughout the software life-cycle, even after deployment.

Very few analytic models have been reported for distributed database systems, perhaps because of complex relationships of the different kinds of resources in them. Layered queueing models seem to be a natural framework for these systems, capable of modelling all the different features which are important for performance (e.g. devices, communications, multithreaded processes, locking). To demonstrate the suitability of the layered framework, a previous queueing study of the CARAT distributed testbed has been recast as a layered model. Whereas the queueing model bears no obvious resemblance to the database system, the layered model directly reflects its architecture. The layered model predictions have about the same accuracy as the queueing model.

The paper presents a functional view of end-system protocol implementations whereby the protocol is decomposed into multiple functions, each causing a change in the protocol state. This view makes the interactions and the relationships among the various functional modules explicit. In terms of this view, currently prevalent architectural optimizations for performance improvement (such as 'parallel executions' and 'integrated layer processing') can be easily described as a set of control flow relationships among modules. If a protocol implementation is analyzed using our functional model, the possible architectural optimizations in the protocol can be easily identified and implemented without violating correctness. Thus, our approach can be used to optimize existing implementations by casting the underlying protocols in our framework, and it is particularly useful in developing implementations for new protocols.

Complete decomposition is a new strategy for evaluating the performance of a network of generalized service centers, represented in the notation of Generalized Stochastic Petri Net (GSPNs). Each service center can have arbitrary internal structure (including internal parallelism), but it must conserve tokens at the boundaries, and its inputs must be i/o-connected to its outputs. Routing between centers can depend on the state of the departure center. The new method adapts a delay equivalence decomposition technique used previously. Within this framework, it reduces the solution complexity of the auxiliary models which must be solved in the iteration. This new method is applied to a scalable model for computer system performance.>

Complete decomposition is a new strategy for evaluating the performance of a network of generalized service centers, represented in the notation of Generalized Stochastic Petri Nets (GSPNs). Each service center can have arbitrary internal structure (including internal parallelism), but it must conserve tokens at the boundaries, and its inputs must be i/o-connected to its outputs. Routing between centers can depend on the state of the departure center. The new method adapts a delay equivalence decomposition technique used previously. Within this framework, it reduces the solution complexity of the auxiliary models which must be solved in the iteration. This new method is applied to a scalable model for computer system performance.>

Distributed or parallel software with synchronous communication via rendezvous is found in client-server systems and in proposed open distributed systems, in implementation environments such as Ada, V, remote procedure call systems, in transputer systems, and in specification techniques such as CSP, CCS and LOTOS. The delays induced by rendezvous can cause serious performance problems, which are not easy to estimate using conventional models which focus on hardware contention, or on a restricted view of the parallelism which ignores implementation constraints. Stochastic rendezvous networks are queueing networks of a new type which have been proposed as a modelling framework for these systems. They incorporate the two key phenomena of included service and a second phase of service. This paper extends the model to also incorporate different services or entries associated with each task. Approximations to arrival-instant probabilities are employed with a mean-value analysis framework, to give approximate performance estimates. The method has been applied to moderately large industrial software systems.>

Software bottlenecks are performance constraints caused by slow execution of a software task, in typical client-server systems a client task must wait in a blocked state for the server task to respond to its requests, so a saturated server will slow down all its clients. A rendezvous network generalizes this relationship to multiple layers of servers with send-and-wait interactions (rendezvous), a two-phase model of task behavior, and to a unified model for hardware and software contention. Software bottlenecks have different symptoms, different behavior when the system is altered, and a different cure from the conventional bottlenecks seen in queueing network models of computer systems, caused by hardware limits. The differences are due to the "push-back" effect of the rendezvous, which spreads the saturation of a server to its clients. The paper describes software bottlenecks by examples, gives a definition, shows how they can be located and alleviated, and gives a method for estimating the performance benefit to be obtained. Ultimately, if all the software bottlenecks can be removed, the performance limit will be due to a conventional hardware bottleneck.>

This paper describes a multiview characterization of concurrent software and systems suitable for displaying and analyzing performance information. The views draw from well-known descriptions, and are compatible with established techniques and tools such as execution graphs, Petri Nets, State-Charts, structured design or object-oriented design, and various models for performance. The views are connected by means of a "Core model" and are used together to extract information relating to system integration, such as interprocess overheads, and the delay behavior of separate software components in complex systems. The integration of the views in the Core assists by converting results in one view (such as scheduling delay for resources) to parameters in another (such as delays along a path). The ultimate goal of the views is to support designers in making tradeoffs which involve performance, and to provide early assessment of the performance potential of software designs.>

Abstract This paper presents a notation for extracting complex performance measurements of parallel software from an event log. NICE defines a ‘complex interval’ as a sequence of events in the event log that match a rather general template using an interval monitor process (IMP). The IMP process model combines an extended FSM with parametrized event descriptors to provide a generalized description of a sequence of subintervals each one of which may be measured for duration. An interval matching algorithm provides a strategy for distributing the events in the log to multiple concurrent IMPs, thereby handling interval occurrences that overlap and/or share the same event. Practical issues of implementing and using NICE are addressed in a discussion of our performance monitoring tool called Finale.

The use of parallelism in enhancing protocol execution performance is examined. In particular the use of a separate concurrent task for each protocol layer is discussed. Two layers of the OSI protocol system were implemented and run on a multiprocessor, with from one to five processors at each end of the connection. Potentially concurrent entities included user tasks as data source and sink, the OSI session layer (kernel functional unit only), the OSI transport layer (classes 0 and 2), vestigial network tasks, and tasks to buffer data between layers. Three substantially different design architectures with from nine to twelve tasks at each end of the connection were compared. The design differences centered on different ways to provide interlayer coordination and buffering; the protocol code was kept identical. The implementation used a real-time kernel which provides synchronous (request-reply) interprocess communication. The variation in throughput between designs covered a range of approximately two to one. The best design is found to be symmetrical decentralized two-way pipeline with courier communications.>

MULTIFIT-COM, a static task allocator which could be incorporated into an automated compiler/linker/loader for distributed processing systems, is presented. The allocator uses performance information for the processes making up the system in order to determine an appropriate mapping of tasks onto processors. It uses several heuristic extensions of the MULTIFIT bin-packing algorithm to find an allocation that will offer a high system throughput, taking into account the expected execution and interprocessor communication requirements of the software on the given hardware architecture. Throughput is evaluated by an asymptotic bound for saturated conditions and under an assumption that only processing resources are required. A set of options are proposed for each of the allocator's major steps. An evaluation was made on 680 small randomly generated examples. Using all the search options, an average performance difference of just over 1% was obtained. Using a carefully chosen small subset of only four options, a further degradation of just over 1.5% was obtained. The allocator is also applied to a digital signal processing system consisting of 119 tasks to illustrate its clustering and load balancing properties on a large system.>

To use queuing theory to analyze real systems such as computer communications networks, one makes assumptions that are, strictly speaking, untrue. The authors provide an exact analysis for cases with greatly relaxed assumptions. Service times can have general increasing failure rate distributions, different by class even at FIFO nodes. Routing can be arbitrary, including dependencies along the route, provided the number of visits to each node is a random variable. Only the mean service time and mean visit rates at nodes need be specified. A lower throughput bound is found which gives a minimum guaranteed throughput for each class; together with the familiar multiclass asymptotic upper bounds they give a convex feasible region in a multidimensional throughput space. A detailed analysis is given for systems with FIFO and infinite-server nodes, and the extension to processor-sharing nodes is described. The results can be reinterpreted as a set of bounds on the separate throughputs. This is equivalent to a circumscribed rectangular region called the robust box bounds.>

A means of approximating light-traffic performance of RAD (random-arrivals-with-deadlines) systems for four basic preemptive scheduling policies is presented. The design goal is to keep congestion low enough to make the probability of rejection acceptably small. These designs must have low processor utilization. The study analyzes rejection probabilities at utilizations up to 20% and rejection probabilities up to about 10% for various well-known preemptive scheduling disciplines (shortest job first, earliest due date, and least laxity first), as well as first-come, first-served. Good approximations for the rejection probability and for a number of other properties, such as the distribution of time-to-go at rejection, are found.>

A network of communicating software tasks in a distributed system is considered. Over the period of interest they are permanent concurrent entities, statically allocated to processors. Tasks communicate by messages sent to ports, sockets, or entries. A task execution is such that for each message received on a certain port, a known average number of other actions takes place, including sending of messages and waiting for replies, or reception of messages on some designated port. Various interesting special cases occur. From the behavior model and parameters of each task, network-wide relationships are obtained that govern the rates of intertask messaging. Certain rates may be taken as independent and they determine the remaining rates. In some cases, a narrowly constrained operating subspace results which contains all feasible task-throughput combinations. The relationships cover a variety of types of tasks and types of communication mechanisms, including rendezvous as well as nonblocking send with blocking receive.>

Consideration is given to a homogeneous distributed network of nodes with a quasi-dynamic random task-sharing discipline and identical Poisson hard real-time traffic at each node. The task-sharing discipline under consideration permits tasks to be shared randomly around the network as long as remaining task laxity permits. Analysis of task loss in such a network requires the assumption that the transferred task stream from all nodes form a Poisson stream. The authors study the requirements for such an assumption to be justified by using computer simulation to examine transferred traffic for both independence and its fit to an exponential distribution as a function of network size. A rough rule of thumb for estimating independence is to assume the transfers are independent after the system size exceeds the average number of transfers between nodes.>

The execution workload of a protocol often limits the data communications throughput in local area and wide area networks. The handling of buffers is one of the implementation factors that affects the execution workload of a protocol implementation: if possible, copying of user data should be avoided. Two buffer cut-through strategies for avoiding copying higher-level data are described, with some of the mechanisms necessary to implement them. The resulting execution workload in a transport protocol (similar to the ISO class 4 protocol) is studied in detail. Individual protocol actions are modeled for a wide range of data-stream parameters. The improvement when copying is avoided is shown to be relatively insensitive to the parameter values and to be as high as 80% when the checksum is not computed at the transport level.>

A research project is described in which an experimental software CAD environment called the Carleton embedded system design environment (CAEDE), oriented toward embedded systems and Ada, was developed to provide a demonstration of the concept and to serve as a research testbed. The major contribution of CAEDE is a demonstration of a visual paradigm which combines semantic depth and syntactic shallowness, relative to Ada, in a manner that makes it possible for the embedded-system designer to work in terms of abstract machines while still thinking Ada. A secondary contribution is the identification of Prolog as a promising approach for supporting tool development in an environment which supports the visual paradigm. Also described are experimental tools for temporal analysis, performance analysis, and the generation of skeleton Ada code.>

Stochastic rendezvous networks (SRVN) are models for the throughput of distributed programs executed concurrently and synchronously on distributed computing nodes. Server tasks respond to requests from user tasks and execute in a two-phase pattern (in-rendezvous phase, then postrendezvous phase), and may themselves act as user tasks to further servers, to any depth. The authors extend the model to permit the execution time and the occurrence of nested rendezvous calls to depend on the identity of the calling user task. An iterative approximation method is developed, and compared to exact throughput calculations found with timed Petri nets. The approximation has errors of a few percent in most cases, and executes very much faster than the Petri-net calculation.>

A product-form queuing network with multiple open and closed chains is considered. Some of the closed chains, which have a single customer each, require allocation of resources in the network so as to maximize a weighted throughput performance criterion. Chains with more than one customer can be decomposed into many chains of one customer each. It is proved that an optimal allocation of resources lies on a vertex (extreme points) of the set of feasible allocations. This considerably reduces the search space for an optimal allocation. Applications of this result in distributed computing are discussed.

Interrupted service, which may occur in fading radio channels, in low-priority channels which can be preempted or in systems with failures may make severe demands on buffer size if overflow is to be avoided. This paper analyzes a buffer with a Markov-interrupted timeslotted server, generalizing earlier work on independent random interruptions. An equivalent service distribution is defined for use in an approximateM/G/1model, which in turn gives buffer probabilities and overflow probabilities. For very small overflow probabilities, the necessary buffer size is found from a further analytic approximation to the tail of the buffer size distribution. The accuracy of the two approximations together is good, shown by an example of a fading radio channel.

Adjustable feedback schedulers control the relative performance obtained from a computer system by different classes of users. This work examines the control of relative throughputs (or related measures) by feedback of departure counts. Counts from key resources in the system are used to dynamically adjust the priorities of the different classes at certain queues in an attempt to achieve preset values of the ratios of the class throughputs. An iterative mean-value algorithm is given which approximates the throughputs actually achieved by this scheduler within a few percent of error. Limits of controllability are observed beyond which the achieved throughput ratios cannot follow the preset values. A characterization is given for this `controllable performance set'. It is also shown how, using this set, the scheduler can be tuned to have approximately optimal set points for the ratios.

A globally optimal allocation for files in a local network environment is presented. The principal concern is the delays due to contention at the file servers; storage space is assumed to be adequate. A queuing network model is used to represent the file servers and the workstations. The workloads generated by the workstations are statistically identical. The model assumes that the communications medium is lightly loaded. In this case there is very little queuing, so that a message transmission requires an approximately constant average delay which can be included in the local processing time of the workstation. Under these assumptions the model can be applied to any of the various LAN technologies. It is shown that all the files of each workstation should be placed on one file server, with the workstations divided as equally as possible among the file servers.

Interface processors are being developed in hardware and firmware for communications protocols at higher and higher levels (HDLC, X.25, Ethernet ...), for smaller and smaller host systems. How far this process will go depends on the driving factors of increased performance and simpler implementation of the systems which use the protocols. A simplified performance model with parameters, which encompasses a large part of all systems using communications, is used to find those parameter combinations offering various degrees of performance improvement. The results can be used to approximately distinguish those cases which will provide the market for performance improvement via higher-level interface processors.

An algorithm is described by which TDM slots in many links of a network can be optimally allocated between voice and data. It is an adaptation of a convex-programming method due to Fox, by which a pool of resources is allocated to minimize a convex separable criterion function such as blocking probability for voice subject to a single convex separable constraint such as specified maximum mean delay to data. In our case the single pool of resources is the total of the available slots. The necessary adaptation of Fox's algorithm is described for the minimum blocking problem, and for minimum data delay subject to a blocking constraint.