The advent of multicast and the growth and complexity of the Internet has complicated network protocol design and evaluation. Evaluation of Internet protocols usually uses random scenarios or scenarios based on designers' intuition. Such an approach may be useful for average case analysis but does not cover boundary-point (worst or best case) scenarios. To synthesize boundary-point scenarios, a more systematic approach is needed. In this paper, we present a method for automatic synthesis of worst and best case scenarios for protocol boundary-point evaluation. Our method uses a fault-oriented test generation (FOTG) algorithm for searching the protocol and system state space to synthesize these scenarios. The algorithm is based on a global finite state machine (FSM) model. We extend the algorithm with timing semantics to handle end-to-end delays and address performance criteria. We introduce the notion of a virtual LAN to represent delays of the underlying multicast distribution tree. Our algorithms utilize implicit backward search using branch and bound techniques and start from given target events. As a case study, we use our method to evaluate variants of the timer suppression mechanism, used in various multicast protocols, with respect to two performance criteria: overhead of response messages and response time. Simulation results for reliable multicast protocols show that our method provides a scalable way for synthesizing worst case scenarios automatically. Results obtained using stress scenarios differ dramatically from those obtained through average case analyses. We hope for our method to serve as a model for applying systematic evaluation to other multicast protocols.
There is a large body of literature dealing with verification of protocols. Verification systems typically address well-defined properties --such as safety , liveness , and responsiveness @cite_41 -- and aim to detect violations of these properties. In general, the two main approaches for protocol verification are theorem proving and reachability analysis @cite_2 . Theorem proving systems define a set of axioms and relations to prove properties, and include model-based and logic-based formalisms @cite_39 @cite_22 . These systems are useful in many applications. However, these systems tend to abstract out some network dynamics that we study (e.g., selective packet loss). Moreover, they do not synthesize network topologies and do not address performance issues per se.
@cite_41 @cite_22 @cite_39 @cite_2
2005307131 2119895020 2099078002 2034717157
This paper addresses the problem of designing stabilizing computer communication protocols modelled by communicating finite state machines. A communication protocol is said to be stabilizing if, starting from or reaching any illegal state, the protocol will eventually reach a legal (or consistent) state, and resume its normal execution. To achieve stabilization, the protocol must be able to detect the error as soon as it occurs, and then it must recover from that error and revert back to a legal protocol state. The later issue related to recovery is tackled here, and an efficient procedure for the recovery in communications protocols is described. The recovery procedure does not require periodic checkpointing and, therefore, is less intrusive. It requires less time for rollback and fewer recovery control messages than other procedures. Only a minimal number of processes will roll back, and a minimal number of protocol messages will be retransmitted during recovery. Moreover, our procedure requires minimal stable storage to be used to record contextual information exchanged during the progress of the protocol. Finally, our procedure is compared with an existing recovery procedure, and an illustrative example is provided. By providing a formal semantics for Z, this book justifies the claim that Z is a precise specification language, and provides a standard framework for understanding Z specifications. It makes a detailed theoretical comparison between schemas, the Z construct for breaking specifications into modules, and the analogous facilities in other languages such as CLEAR and ASL. The final chapter contains a number of studies in Z style, showing that Z can be used for a wide variety of specification tasks. Contains a precise and complete description of the computational logic develo by the authors; will serve also as a reference guide to the associated mechanical theorem proving system. Annotation copyright Book News, Inc. Portland, Or. Hardware and software systems will inevitably grow in scale and functionality. Because of this increase in complexity, the likelihood of subtle errors is much greater. Moreover, some of these errors may cause catastrophic loss of money, time, or even human life. A major goal of software engineering is to enable developers to construct systems that operate reliably despite this complexity. One way of achieving this goal is by using formal methods, which are mathematically based languages, techniques, and tools for specifying and verifying such systems. Use of formal methods does not a priori guarantee correctness. However, they can greatly increase our understanding of a system by revealing inconsistencies, ambiguities, and incompleteness that might otherwise go undetected. The first part of this report assesses the state of the art in specification and verification. For verification, we highlight advances in model checking and theorem proving. In the three sections on specification, model checking, and theorem proving, we explain what we mean by the general technique and briefly describe some successful case studies and well-known tools. The second part of this report outlines future directions in fundamental concepts, new methods and tools, integration of methods, and education and technology transfer. We close with summary remarks and pointers to resources for more information.