Protocol verification using database technology

A novel application of databases in communications networks, namely, protocol verification on a parallel database machine, is described. An approach to protocol verification that uses database algorithms executing on a commercially available, parallel architecture called a hypercube multicomputer is introduced. The goal is to achieve the high degree of computational parallelism necessary to explore rapidly the global state space of even very complex protocols, significantly reducing the time required to verify a protocol and allowing formal verification to be included as part of the process of protocol design. An overview is provided of the relational model of protocol verification used, and extensions to the model are described. The hypercube multicomputer and the algorithms for relational database operations designed to execute in that environment are then described. Estimates of the performance improvements achievable by parallel executing of verification algorithms in the proposed system are given.<>