Title :
Systematic testing of multicast routing protocols: analysis of forward and backward search techniques
Author :
Helmy, Ahmed ; Estrin, Deborah ; Gupta, Sandeep
Author_Institution :
Univ. of Southern California, Los Angeles, CA, USA
Abstract :
We present a new methodology for developing systematic and automatic test generation algorithms for multipoint protocols. These algorithms attempt to synthesize network topologies and sequences of events that stress the protocol´s correctness or performance. This problem can be viewed as a domain-specific search problem that suffers from the state space explosion problem. One goal of this work is to circumvent the state space explosion problem utilizing knowledge of network and fault modeling, and multipoint protocols. The two approaches investigated are based on forward and backward search techniques. We use an extended finite state machine (FSM) model of the protocol. The first algorithm uses forward search to perform reduced reachability analysis. Using domain-specific information for multicast routing over LAN, the algorithm complexity is reduced from exponential to polynomial in the number of routers. This approach, however, does not fully automate topology synthesis. The second algorithm, the fault-oriented test generation, uses backward search for topology synthesis and uses backtracking to generate event sequences instead of searching forward from initial states. Using these algorithms, we have conducted studies for correctness of the multicast routing protocol PIM
Keywords :
backtracking; computational complexity; conformance testing; finite state machines; formal verification; local area networks; multicast communication; network topology; protocols; reachability analysis; telecommunication network routing; FSM model; LAN; PIM; automatic test generation algorithms; backtracking; backward search; event sequences; extended finite state machine; fault modeling; fault-oriented test generation; forward search; multicast routing protocols; multipoint protocols; network topologies; polynomial algorithm complexity; protocol correctness; protocol performance; reachability analysis; systematic testing; topology synthesis; Automatic testing; Explosions; Multicast algorithms; Multicast protocols; Network synthesis; Network topology; Routing protocols; State-space methods; Stress; System testing;
Conference_Titel :
Computer Communications and Networks, 2000. Proceedings. Ninth International Conference on
Conference_Location :
Las Vegas, NV
Print_ISBN :
0-7803-6494-5
DOI :
10.1109/ICCCN.2000.885549