Obtaining Unique Input/Output Sequences of Communication Protocols

Wen-Huei CHEN

Publication
IEICE TRANSACTIONS on Communications   Vol.E80-B    No.10    pp.1509-1513
Publication Date: 1997/10/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Issue on Network Interworking)
Category: Communication protocol
Keyword: 
conformance testing,  protocols,  UIO sequences,  test sequence,  

Full Text: PDF>>
Buy this Article


Summary: 
A Unique Input/Output (UIO) sequence for the state J of a protocol is a sequence of input/output pairs that is unique to state J. Obtaining UIO sequences from the protocol specification is a very important problem in protocol conformance testing. Let n and m be the total number of states and transitions of the protocol, respectively, and dmax be the largest outdegree of any state, W. Chun and P. D. Amer proposed an O(n2(dmax)2n-1) algorithm to obtain the minimum-length UIO sequences (where the length refers to the number of input/output pairs). However, n and m are normally very large for real protocols. In this paper, we propose an O(n*m) algorithm for obtaining UIO sequences. In theory, our algorithm yields a UIO sequence which contains at most n1 input/output pairs. In experimentation, ten protocol examples collected from recent papers, the ISO TP0 protocol, the ISDN Q. 931 network-side protocol, and the CCITT X. 25 protocol show that in average the obtained UIO sequences are only 11.8% longer than the minimum-length ones, and 97.4% of the existent UIO sequences can be found. And our algorithm is extended for minimizing the cost of UIO sequences and for obtaining synchronizable UIO sequences, which have not been achieved by any algorithm proposed earlier.