  In this paper, 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 in this study 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 LANs, 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. We propose to extend these algorithms to study
end-to-end multipoint protocols using a virtual LAN that represents delays of
the underlying multicast distribution tree.
