Formal Specification, Verification, and Automatic Test Generation of ATM Routing Protocol: PNNI

1. Introduction

For the reliability of ATM networks, there is an urgent need to apply some formal methods in validating these protocols and in generating test cases. The tools needed to accomplish these purposes include: a technique to model the protocol, a formal description language to describe the model, a protocol simulator to perform verifications, and a test generator to produce test cases. This work is a case study of applying formal verification and test generation tools to the ATM network routing protocol, or the ATM Forum Private Network-Network Interface (PNNI) Specification Version 1.0 [1].

The PNNI specification consists of three layers of protocols: the Hello protocol for identifying the status of NNIs; the Database Synchronization protocol for maintenance of routing databases; and the Peer Group Leader Election protocol for operations of hierarchical routing. Each of the PNNI sub-protocols can best be modeled as communicating Extended Finite State Machines (EFSM) with parameters [2].

Computernetwork

English: Created by me using OmniGraffle and relea...

MS PDC 2005, day 2

The system behavior of the PNNI protocol system is the combined effects of three communicating EFSMs. The issue at hand is: Is it necessary to develop a complete composite state machine to correctly model PNNI, and if so, how? Furthermore, since a PNNI system represents an ATM network switching node, within a network switching nodes are expected to interact with each other. Therefore what is the minimum number of nodes needed to correctly simulate the operation of PNNI?

In our study, we take two nodes connected by a full-duplex channel, based on the following observations. We want to detect design/specification errors from verification, implementation errors from conformance testing, and errors from both the design and implementation from interoperability testing. Suppose that an error is revealed using a two-node model, then obviously, faults in the specification are detected. Conversely, suppose that there are faults...