Method and apparatus for designing gateways for computer networks

• US 5,327,544 A
• Filed: 08/29/1991
• Issued: 07/05/1994
• Est. Priority Date: 08/29/1991
• Status: Expired due to Term

• Current Assignee: American and Telegraph Company
• Original Assignee: AT&T, Inc.
• Inventors: Lee, David, Netravali, Arun N., Sabnani, Krishan K.
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US07/752,127
• Time in Patent Office: 1,041 Days
• Field of Search: 395/200, 395/500, 341/50
• US Class Current: 716/104
• CPC Class Codes: H04L 69/08 Protocols for interworking; Protocol conversion
• CPC Class Codes: H04L 9/40 Network security protocols

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.

Claims

1. 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.

2. 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.