Method for tying and untying path access in a CPU-based, layered communications system
US5003470A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Dec 9, 1988 |
| Grant date | Mar 26, 1991 |
| Priority date | — |
| Expiry date | Dec 9, 2008 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L69/00
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.