Mark J Carpenter

US Patent:

50034707, Mar 26, 1991

Filed:

Dec 9, 1988

Appl. No.:

7/282409

Inventors:

Mark A. Carpenter - Sunnyvale CA
Steven H. Goldberg - Hillsborough CA

Assignee:

International Business Machines Corporation - Armonk NY

International Classification:

G06F 700

US Classification:

364200

Abstract:

A method for maintaining the integrity of ties and their associated tie groups in a CPU-based, layered communications subsystem in which the connection endpoints in each layer are denoted by a connection control block (CCB), the relationship between CCBs being denoted by ties. Ties and their CCBs can be mapped onto an edge-oriented graph of tie group relations. The arbitrary removal of an edge (tie) in the graph compromises graph integrity by possible formation of unenumerated subgraphs or independent graphs. The solution involves enumerating those edges having vertices which no longer reference CCBs within the tie group, removing them, and forming a second tie group. The enumeration is conducted over a Eulerian traverse of the remaining n edges of the graph. A Eulerian traverse of a graph is one which traverses each edge exactly once. Such a traverse reduces the number of comparisons M to a range N