The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Mar. 26, 1991
Filed:
Dec. 09, 1988
Mark A Carpenter, Sunnyvale, CA (US);
Steven H Goldberg, Hillsborough, CA (US);
International Business Machines Corporation, Armonk, NY (US);
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<M<O(N.sup.2). This facilitates maintaining either one or two tie groups per cutting of an edge in the graph.