Switching Elements
Responsible for the transport of data across a network - routing
May support congestion handling or quality of service mechanisms
Examples
routers - IP
switches - ATM or local area networks (e.g., Ethernet-802.3, token ring)
bridges, hubs - local area networks
Protocols
A protocol is a set of conventions that specifies the rules or parameters for communication between two entities (hosts, processes, switching elts, devices, etc).
Protocols specify conventions for:
The type, semantics, and format of information to be conveyed between entities
Establishing/closing connections or sessions
Routing across a network or internetwork
Flow control: speed matching between entities
Reliability: error detection, handling, correction
ABSTRACT
The problem of finding a minimum number of patterns to exercise the logic elements of a combinational switching net is investigated. Throughout, the word “testing” refers to exercising of this kind; or, equivalently, to fault diagnosis where each line of the net can be directly observed. Any set of permanent faults can be selected to test against, examples of which range from “stuck-at” faults (allowing the most economical test) to “any possible fault” (requiring the most complete test). The method used depends upon exact structural analysis rather than upon search algorithms or random pattern generation. The types of results presented appear to be fundamentally new. In particular, the maximum number of patterns required to test any one of an infinite class of nets is frequently found to be finite and extremely small. For example, any nontrivial connected tree of 2-input nand gates can be tested for “any possible fault” by exactly five patterns—no more and no less. The method in brief: Given a set F of switching functions and a set of required inputs for each (collectively denoted T), a “testing” function is defined for each element of F for each positive integer r. If the lines of a net can be mapped to the domain of the testing functions P(T, r) so that the gates perform consistent with these functions, we say the net “accepts” P(T, r)—and then r patterns are sufficient to test the net for T. Only nets in which each logic element is intended to realize the same switching function are discussed here. Trees (nets without fanout) are studied first, and the conditions under which a tree of identical gates “accepts” a partial function on an arbitrary domain is established. Then the common symmetric switching functions are separately investigated to find for each a minimum value of r such that all trees composed solely of the function accept P(T, r) (for various T). In most cases, as in the example given, the number of patterns required to test any such tree is extremely low. The conditions under which all nets (nontrees included) accept a set of partial functions with arbitrary domain are then established. These conditions are rarely met in practice, even where F consists of a single function. However, many subclasses of nets can be identified which require only a few patterns at most (depending on the function and the class of faults selected). These subclasses often contain nets of arbitrary size and complexity, and frequently consist of exactly those nets for which a related graph can be “colored” (i.e., h-node colored for some particular h) in the classical graph-theoretic sense. For example, any net of 2-input nand gates can be tested by five patterns if one of its related graphs is 2-colorable and another one is 3-colorable (!). The detailed results and methods used to obtain them are summarized, and in conclusion coloring problems and test construction are commented upon.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
1
CHANG, H.Y., MANNING, E., AND METZE, G. Fault Diagnosis of Digital Systems Wiley- Interscience, New York, 1970.
2
HARARY, F. Graph Theory Addison-Wesley, Reading, Mass., 1969.
3
HORNBUCKLE, GARY D., AND SPXNN, R.N. Diagnosis of single-gate failuresin combinational circuits. IEEE Trans. EC-18, 3 (Mar. 1969), 216-220.
4
Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962
5
KAUTZ, W H. Fault testing and diagnosis in combinational digital circuits. IEEE Trans. EC.17, 4 (Apr. 1968), 352-366.
6
MALING, K., AND ALLEN, E.L. A computer organization and programming system for automated maintenance IEEE Trans. EC-IP, 5 (Dec. 1963), 887-895.
7
OaE, O. The Four-Color Graph Problem. Academic Press, New York, 1967.
8
POWELL, T. J A procedure for selecting d~agnostic tests IEEE Trans. EC-18, 2 (Feb. 1969), 168-175.
9
Donald L. Richards, Efficient Exercising of Switching Elements in Combinatorial Nets, Journal of the ACM (JACM), v.20 n.2, p.320-332, April 1973 [doi>10.1145/321752.321763]
10
RICHARDS, DONALD L. Test size and optimum detection in switching nets J. ACM (to appear).
11
ROTH, J.P. Diagnosis of automata failures: A calculus and a method. IBM J. Res. Devel. 10, 4 (July 1966), 278-291.
12
ROTH, J.P., BOURICIUS, W. G, AND SCHNEIDER, P.R. Programmed algorithms to compute tests to detect and distinguish between failures in logical circuits. IEEE Trans. EC-I6, 5 (Oct 1967), 567-580. {In addmon, consult IEEE Trans. EC-20, 11 (Nov. 1971).}
CITED BY
Donald L. Richards, Efficient Exercising of Switching Elements in Combinatorial Nets, Journal of the ACM (JACM), v.20 n.2, p.320-332, April 1973
INDEX TERMS
Primary Classification: G. Mathematics of Computing G.2 DISCRETE MATHEMATICS
Additional Classification: B. Hardware B.8 Performance and Reliability
General Terms: Design, Measurement, Performance, Reliability, Theory, Verification
Peer to Peer - Readers of this Article have also read:
Data structures for quadtree approximation and compression Communications of the ACM 28, 9Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computingKim S. Lee , Huizhu Lu , D. D. Fisher
The GemStone object database management system Communications of the ACM 34, 10Paul Butterworth , Allen Otis , Jacob Stein
Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM 34, 12Ellen Francik , Susan Ehrlich Rudman , Donna Cooper , Stephen Levine
An intelligent component database for behavioral synthesis
Useful downloads:
