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 good number of publications dealing with conformance testing @cite_24 @cite_27 @cite_26 @cite_5 . However, conformance testing verifies that an implementation (as a black box) adheres to a given specification of the protocol by constructing input output sequences. Conformance testing is useful during the implementation testing phase --which we do not address in this paper-- but does not address performance issues nor topology synthesis for design testing. By contrast, our method synthesizes test scenarios for protocol design, according to evaluation criteria.
@cite_24 @cite_5 @cite_27 @cite_26
2073074602 1965028135 2158348156 2029755436
Abstract We present simple randomized algorithms for the fault detection problem : Given a specification in the form of a deterministic finite state machine A and an implementation machine B , determine whether B is equal to A . If A has n states and p inputs, then in randomized polynomial time we can construct with high probability a checking sequence of length O ( pn 4 log n ), i.e., a sequence that detects all faulty machines with at most n states. Better bounds can be obtained in certain cases. The techniques generalize to partially specified finite state machines. Abstract A procedure presented here generates test sequences for checking the conformity of an implementation to the control portion of a protocol specification, which is modeled as a deterministic finite-state machine (FSM). A test sequence generated by the procedure given here tours all state transitions and uses a unique signature for each state, called the Unique Input Output (UIO) sequence. A UIO sequence for a state is an input output behavior that is not exhibited by any other state. An algorithm is presented for generating a minimum-length UIO sequence, should it exist, for a given state. UIO sequences may not exist for some states. Abstract Now that many international standards for Open Systems Interconnection (OSI) services and protocols have reached at least the Draft International Standard stage, there is much international activity in standardizing OSI conformance test suites. This new activity is based on the emerging OSI conformance testing methodology and framework standards being progressed by ISO and CCITT. This paper presents the major aspects of this methodology and framework. A novel procedure presented here generates test sequences for checking the conformity of protocol implementations to their specifications. The test sequences generated by this procedure only detect the presence of many faults, but they do not locate the faults. It can always detect the problem in an implementation with a single fault. A protocol entity is specified as a finite state machine (FSM). It typically has two interfaces: an interface with the user and with the lower-layer protocol. The inputs from both interfaces are merged into a single set I and the outputs from both interfaces are merged into a single set O. The implementation is assumed to be a black box. The key idea in this procedure is to tour all states and state transitions and to check a unique signature for each state, called the Unique Input Output (UIO) sequence. A UIO sequence for a state is an I O behavior that is not exhibited by any other state.