Diagnosis of Multiple Faults in a Nationwide Communications Network

1. Introduction

This paper describes the development of an expert system for diagnosing multiple faults in a nationwide communications network (COMNET). Our effort focused on understanding the human effort required to implement an expert system and on identifying missing features in the existing technology. In the process of implementing NDS it was necessary to extend existing expert systems technology dealing with multiple and intermittent failures. The domain was chosen on the basis of prior domain experience with trouble shooting electronic equipment, the availability of a domain expert, and by expected benefits from the eventual operational system. Criteria considered during the seeping of the project were that it require less than one person year of effort, that it be a non­ trivial application, and that it avoid excessive uninteresting detail.

2. The Problem: Fault Isolation in COMNET

COMNET is a geographically distributed communications network supporting a variety of application systems. The application software runs on a central computing facility and is accessed remotely by users throughout North America via interactive terminals. The communication path from each user terminal to the central computer is a

Diagnosis of Multiple Faults in a Nationwide Communications Network

Thomas L. Williams Smart Systems Technology

Paul J. Orgren Shell Development Company

Carl L. Smith Shell Development Company

circuit (called a 'virtual wire') composed of both digital and analog electronic devices . The field repairable units, i.e. the components which can fail and be repaired, include te lecomm unica tion processors, statistical multiplexors, modems, telephone circuits, frequency divisional multiplexors, RS-232 cables and computer terminals (see fig. 1.). The capabilities which had to be included in the NDS are discussed in the remainder of this section.

The diagnostic process draws upon several different types of knowledge. The topology of the network, and in particular the virtual wire which has failed, is fundamental in guiding the diagnostician's search for the fault. In general the diagnostician will try to exploit hierarchical search methods. To optimize the search the diagnostician must know which diagnostic tests are available, what their information content is in terms of which components they test, and their cost. Actual physical devices have limited test points which are chosen by the designer, not the diagnostician. As a result, diagnosis is often driven by the availabi ty of test points and diagnostic tests . There is the additio¥1 factor of accessibility for certain tests. In cases were the diagnostician does not have the required access to perform desired tests he must proceed as far as possible on the basis of incomplete or partial inf o rmation, often resorting to alternative types of knowledge, such as frequency of failure data.

COMNET can fail in s e veral modes and in gene r al the single failur e and non-intermittenc y assumptions do not hold ([1],[2]). Bec ause the functi on of the various components in a virtual wire are closely inter-related, it is often the case that one failure will lead to, or cause, other dependent failures. For example, a statistical multiplexor may be inadvertently reset, and as a result it will reset the baud rate on a remote modem with which it communicates. Multiple failures can also be independent. When a user canno t acce ss an application system he may tamper with the terminal, the RS-232 cables and/ or the modem. As a result, there c ould be, in addition to the original failure, several unrelated independent failures. The presence o f telephone circuits introduces frequent intermittent failures due to noise in the telephone equipme nt, and such intermitte nt failures can collaborate with unrelated failures elswhere in the network to generate multiple independent failures. It is also possible for repair operations t o fail, further restricting the assumptions the diagnos.tician can reasonably make.

3. Approach: ARBY

Because our problem was one of fault isolation within an electronic system, we chose ARBY as our implementation vehicle for NDS. ARBY was designed by Drew McDermott and Ruven Brooks for Smart Systems Technology specifically for applications in electronic fault diagnosis. For a more detailed discussion of ARBY see ( [ 3] , [ 4] ) ·

Fault isolation is represented in NDS as a hierarchical search through a space of successively mor e refined hypotheses ([1],[2],[3],[4]). Each outcome of each diagnostic test provides evidence for or against a fault being in some set of components. A hypothesis is introduced for each such set of components, and a refinement hierarchy is derived from the partial order defined by the inclusion relation on this set of hypotheses. The terminal hypotheses in the refinement hierarchy correspond to singleton sets whose only member is a field repairable unit (FRU).

The search proceeds through the refinement hierarchy from general hypotheses to more refined hypotheses. Choices among competing hypotheses are based on the outcomes of diagnostic tests. When a terminal hypothesis has been reached, a repair operation is performed on the corresponding FRU. Since the state of the failed component has been altered, all evidence involving that FRU is revoked. After performing the repair operation, a termination test is run to determine if all faults have been isolated and repaired. If so, NDS halts. Otherwise the search for multiple failures resumes with the most refined hypothesis which is more general then the current terminal hypothesis and which was not affected by any piece of evidence to be r evoke d as a r e sult of the most r ecent r epair operation. Figure 2. shows the refinement graph for NDS, with refinement links s hown as s o lid lines and generalization links shown as b roke n lines. The hypothesis refinement algorithm i s shown in figure 3.

4. Solution: Network Dia~ostic System (NDS)

NDS uses a refine me n t graph constructed fr om eleven terminal hypotheses and eight intermediate hypotheses (see fig. 2). Most o f the diagnosti c tes ts, of which there are twelve includ ing the termination test, are loop-back tests which tes t subsections of the virtual wire. The rule base , including evidence rules and interac tion frames (see [3], [4] ), consists of approximately 150 ARBY rules. A more detailed description o f NDS may be found in [5].

The current version of NDS required approximately four person-months of knowledge engineer and one person-month of domain expert. In the diagnostic expert's opinion the present l evel of performance of NDS is comparable to an intermediate level diagnostician . The rate at which new rules were added increased significantly toward the end of the project, due to increased understanding of the diagnostic process by the knowledge engineer and increased understanding of the implementation method by the domain expert.

5. Concluding Remarks

The NDS project demonstrates the feasibility of constructing expert systems for isolation and repair of multiple faults in electronic systems. The project also points out two hurdles to large scale deployment of expert systems in commercial environments. First is the labor intensive nature of current knowledge engineering practice. In many commercially desirable domains the expertise required is extremely valuable and of limited availability. Ultimately it will be necessary to develop methods for at least partially automating the construction of expert systems. In this vein we are currently exploring algorithms for automatically generating the refinement hierarchy for ARBY based consultants. Second is the absence of a commercial quality expert system implementation vehicle which is a stable, supported product and which runs on the variety of machines in use in the commercial sector. We are also actively working to overcome this second hurdle by streamlining the ARBY system and studying the requirements for porting it to machines such as the IBM 4300 and the new generation of microcomputers.

6. References

1. Davis, R., et al. "Diagnosis based on Description of Structure and Function". Proc. of the National Conference on Artificial Intelligence, Pittsburgh Pa., 1982, 137-142.
2. Genesereth, M. "Diagnosis Using Hierarchical Design Models". Proc. of the National Conference on Artificial Intelligence, Pittsburgh, Pa., 1982, 278-283.
3. McDermott, D. and Brooks, R. "ARBY: Diagnosis With Shallow Causal Models". Proc. of the National Conference on Artificial Intelligence, Pittsburgh, Pa., 1982 , 278-283.
4. McDermott, D. and Brooks, R. The ARBY ~anual. Smart Systems Technology, Falls Church, va., 1982.
5. Williams, T.L. "Isolating Multiple Faults in NDS". Technical Report 010, Smart Systems Technology, Falls Church, VA 1982.