Method and apparatus for designing gateways for computer networks
AssigneeAT&T Bell Laboratories
InventorsDavid Lee, Arun N. Netravali, Krishan K. Sabnani
Life of this patent
Estimating the term…
Abstract
A method for synthesizing gateways from formal specifications. We present an efficient procedure that computes protocol converters from formal specifications. This procedure has a polynomial number of computation steps. The method involves computation of a common subset of services. This common subset is used to compute the converter. Conditions under which the converter can be stateless are also described.
Claims2
A method for synthesizing a gateway between a plurality of protocols, wherein a protocol provides a set of services, wherein each protocol is represented by a set of one or more directed graphs, wherein each directed graph includes a set of one or more edges, the method comprising the steps of:
- (a) determining a set of common services equal to a subset of the intersection of the sets of services provided by at least two of the protocols;
- and
- (b) determining a set of one or more processes to represent the set of common services;
- wherein the step of determining a set of one or more processes comprises the steps of:
- (1) deleting an edge of a first directed graph when the edge does not correspond to a member of the set of common services to form a first pruned directed graph;
- (2) deleting an edge of the first pruned directed graph which is not within a strongly connected component of the first pruned graph that contains the initial state to form a second pruned directed graph;
- and
- (3) deleting an edge of a second directed graph which does not corresponding to an edge in the second pruned directed graph.
A method for synthesizing a gateway between a plurality of protocols, wherein a protocol provides a set of services, wherein each protocol is represented by a set of one or more directed graphs, wherein said directed graph includes a set of one or more edges, the method comprising the steps of:
- (a) determining a set of common services equal to a subset of the intersection of the sets of services provided by at least two of the protocols;
- and
- (b) determining a set of one or more processes to represent the set of common serves;
- wherein the step of determining a set of one or more processes comprises the steps of:
- (1) deleting an edge of a first graph when the edge does not correspond to a member of the set of common services to from a first pruned directed graph;
- (2) determining a strong connected component of the first pruned directed graph which contains the initial state to form a strongly connected graph;
- (3) removing an edge of the first pruned directed graph which does not correspond to an edge within the strongly connected graph to form a second pruned directed graph;
- and
- (4) deleting an edge of a second directed graph which does not correspond to an edge in the second pruned directed graph.
Dependencies are inferred from the claim text.