Simple finite-state fault detectors for communication networks

This work provides a framework for approaching the problem of fault detection in communication processes. Communication processes are modeled as finite state machines (FSMs), and the authors' model consists of two FSMs, one observing part of the behavior of the other. The authors prove that specific classes of faults are detectable, and give a procedure for constructing detectors, but the design of the minimum alphabet detector is NP-complete. An example applicable to the 802.2 protocol is provided     

Fault identification using a finite state machine model withunreliable partially observed data sequences

The problem of minimum cost identification of a finite state machine (FSM) using a trace of its event history is addressed. The motivation is fault identification in communication systems, although other applications are possible as well. The event history used for the identification is partially observed, i.e., it is known to be a member of a regular language. Any string which belongs in this regular language is a possible trace of the FSM's event history. Furthermore, the event history is assumed to be corrupted with deletions, additions, and changes of symbols. The FSM to be estimated is related to a known FSM by performing an unknown number of additions and changes of arcs. An identification algorithm based on a fast algorithm that can correct corrupted data strings generated by a known finite state machine is developed. Examples of the method are provided, including one based on the IEEE 802.2 logical link control protocol     

Distributed fault identification in telecommunication networks

Telecommunications networks are often managed by a large number of management centers, each responsible for a logically autonomous part of the network. This could be a small subnetwork such as an Ethernet, a Token Ring or an FDDI ring, or a large subnetwork comprising many smaller networks. In response to a single fault in a telecommunications network, many network elements may raise alarms, which are typically reported only to the subarea management center that contains the network element raising the alarm. As a result, a particular management center has a partial view of the status of the network. Management Centers must therefore cooperate in order to correctly infer the real cause of the failure. The algorithms proposed in this paper outline the way these management centers could collaborate in correlating alarms and identifying faults.Work done while the author was with the IBM T. J. Watson Research Center, New York.Work done while the author was with the IBM T. J. Watson Research, Center, New York.Work done during the author's internship at the IBM T. J. Watson Research Center, New York, Summer 93.     

Correcting dependent errors in sequences generated by finite-stateprocesses

A new channel model and channel inversion algorithm are presented for correcting symbol sequences that have been corrupted by an unknown combination of known fault mechanisms. The algorithm is similar to the Viterbi algorithm in that it is suitable for situations in which the uncorrupted data string is generated by a known finite-state process, but it is more versatile in that it can correct a much broader class of errors. Of particular importance is the fact that the algorithm corrects common context-sensitive errors, such as symbol changes, transpositions, mergers, splits, insertions, and deletions, which may be assigned different probabilities depending on the context of preceeding and subsequent symbols. As many communication channels can be modeled in this way, this algorithm is a significant extension over the Viterbi algorithm and previous decoding techniques. The notion of channel rules is introduced to provide a framework for the user to specify the channel operation. The algorithm is given in both an off-line form and a recursive form suitable for sequentially presented data streams. In most applications, the recursive form has computational complexity only a constant times that of the Viterbi algorithm