Back to results
US 7,068,671 B2Granted
Multiple level minimum logic network
AssigneeNational Security Agency
InventorCoke S. Reed
Life of this patent
Estimating the term…
Abstract
A network or interconnect structure utilizes a data flow technique that is based on timing and positioning of messages communicating through the interconnect structure. Switching control is distributed throughout multiple nodes in the structure so that a supervisory controller providing a global control function and complex logic structures are avoided. The interconnect structure operates as a “deflection” or “hot potato” system in which processing and storage overhead at each node is minimized. Elimination of a global controller and buffering at the nodes greatly reduces the amount of control and logic structures in the interconnect structure, simplifying overall control components and network interconnect components and improving speed performance of message communication.
Claims77
An interconnect structure S containing a plurality of nodes and a plurality of interconnects selectively coupling the nodes, the interconnect structure comprising:
- a node set T;
- an interconnect set I that selectively connects nodes in the node set T;
- a device set A mutually exclusive of the node set T with each device in the device set A being capable of sending data to a node in the node set T;
- a device set Z mutually exclusive of the node set T with each device in the device set Z being capable of receiving data from a node in the node set T;
- a collection C of node sets that are subsets of the node set T, each node in the node set T being contained in exactly one member of the collection C;
- for a device x in the device set Z, a sequence cx=cx0, cx1, cx2, . . . , cxJ exists with each member of the sequence cx being a node set in the collection C, the sequence cx being capable of passing data from devices in the device set A to the device x on a plurality of paths, among the plurality of paths being a path set P(x) characterized in that a path R is included in the path set P(x) only if each node on the path R is in a member of the sequence cx, a node of the path R that receives a message directly from a device in the device set A being in a set having a form cxU and a node of the path R that sends data directly to the device x being in a set of a form cxV with U being larger than V;
- for a member Q of the collection C, a corresponding set of devices Z(Q) exists in the device set Z such that a device zq is included in the set of devices Z(Q) only if the member Q is also a member of a sequence cq;
- for members CXH and CXK of the sequence cx with H>K, a device set Z(cxK) is a subset of a device set Z(cxH) and a device exists in the device set Z(cxH) that is not included in the device set Z(cxK);
- and
- the node set T includes three distinct nodes p, q, and r, the node p being in a member czD of a sequence cz, the nodes q and r being in a member czE of the sequence cz with D>E, in one path of path set P(x) a message moves directly from the node p to the node r and in another path of path set P(x) a message moves directly from the node q to the node r.
7 more elements
An interconnect structure S containing a plurality of nodes md a plurality of interconnects selectively coupling the nodes, the interconnect structure comprising:
- a node set T;
- an interconnect set I that selectively connects nodes in the node set T;
- a device set A mutually exclusive of the node set T with each device in the device set A being capable of sending data to a node in the node set T;
- a device set Z mutually exclusive of the node set T with each device in the device set Z being capable of receiving data from a node in the node set T;
- a collection C of node sets that are subsets of the node set T, each node in the node set T being contained in exactly one member of the collection C;
- for a device x in the device set Z, a sequence cx=cx0, cx1, cx2, . . . , cxJ exists with each member of the sequence cx being a node set in the collection C, the sequence cx being capable of passing data from devices in the device set A to the device x on a plurality of paths, among the plurality of paths being a path set P(x) characterized in that a path R is included in the path set P(x) only if each node on the path R is in a member of the sequence cx, a node of the path R that receives a message directly from a device in the device set A being in a set having a form cxU and a node of the path R that sends data directly to the device x being in a set of a form cxV with U being larger than V;
- for a member Q of the collection C, a corresponding set of devices Z(Q) exists in the device set Z such that a device q is included in the set of devices Z(Q) only if the member Q is also a member of a sequence cq;
- for members cxH and cxK of the sequence cx with H>K, a device set Z(cxK) is a subset of a device set Z(cxH) and a device exists in the device set Z(cxH) that is not included in the device set Z(cxK);
- and
- the node set T includes three distinct nodes p, q, and r, the nodes p and q being in a member czD of sequence cz, the node r being in a member czE of the sequence cz with D>E, in a first path of path set P(x) a message moves directly from the node p to the node q, in a second path of path set P(x) a message moves directly from the node p to the node r.
7 more elements
An interconnect structure comprising:
- a plurality of nodes including a node NE and a node set P, the node set P including a plurality of nodes that ale capable of sending data to the node NE;
- and
- a plurality of interconnect paths interconnecting the plurality of nodes, the interconnect paths including data interconnect paths that couple nodes in pairs, a node pair including a sending node and a receiving node, the sending node being capable of sending data to the receiving node;
- the nodes in the node set P having a priority relationship for sending data to the node NE, the nodes in the node set P including distinct nodes NF and NA, the node NF having a highest priority among the nodes in the node set P for sending data to the node NE so that a message MF arriving at the node NF is not blocked from traveling to the node NE by a message MA arriving at the node NA;
- and
- for a message M arriving at the node NA and the message M is blocked from being sent to the node NE, then the blocking of the message M from being sent to the node NE causes, sending of the message M from the node NA to a node distinct from the node NE.
3 more elements
An interconnect structure comprising:
- a plurality of nodes including a node NE and a node set P, the node set P including a plurality of nodes that are capable of sending data to the node NE;
- and
- a plurality of interconnect paths interconnecting the plurality of nodes, the interconnect paths including data interconnect paths that couple nodes in pairs including a receiving node and a sending node that is capable of sending data to the receiving node;
- and
- the nodes in the node set P having a priority relationship for sending data to the node NE, the nodes in the node set P including distinct nodes NF and NA, the node NF having a highest priority among the nodes in the node set P for sending data to the node NE, a message MF arriving at the node NF is not blocked from traveling to the node NE by a message MA arriving at the node NA, wherein:
- when a message M arrives at the node NA and is targeted for the node NE and not blocked by a message M′ arriving at a node in the node set P having a higher priority than the node NA for sending messages to the node NE, the node NA sends the message M to the node NE.
3 more elements
An interconnect structure S containing a plurality of nodes and a plurality of interconnects selectively coupling the nodes, the interconnect structure comprising:
- a node set T;
- an interconnect set I that selectively connects nodes in the node set T;
- a device set A mutually exclusive with the node set T with each device in the device set A capable of sending data to a node in the node set T;
- a device set Z mutually exclusive with the node set T with each device in the device set Z capable of receiving data from a node in the node set T;
- a set of data-carrying paths P, each path of the path set P being capable of carrying data from a device in the device set A to a device in the device set Z, each node on the path of the path set P is included in the node set T, and each interconnect in the path is included in the interconnect set I;
- a node set U characterized as the set of nodes within the node set T that are on a path included in the path set P;
- for a node N in the node set T such that the node N is on a path in the path set P, a corresponding set of devices Z(N) exists in the device set Z such that a device w is, included in the device set Z(N) only if a path exists in the path set P from a member of the device set A to the device w such that the path contains the node N;
- and
- the node set U includes three distinct nodes NA, ND, and NE such that the node NA is capable of sending data to the node ND and node NE and a device set Z(NA) is the same as a device set Z(ND), and a device set Z(NE) is a proper subset of the device set Z(NA).
6 more elements
An interconnect structure S containing a plurality of nodes and a plurality of interconnects selectively coupling the nodes, the interconnect structure comprising:
- a node set T;
- an interconnect set I that selectively connects nodes in the node set T;
- a device set A mutually exclusive with the node set T with each device in the device set A capable of sending data to a node in the node set T;
- a device set Z mutually exclusive with the node set T with each device in the device set Z capable of receiving data from a node in the node set, T;
- a set of data-carrying paths P, each path being capable of carrying data from a device in the device set A to a device in the device set Z, each node on the path is included in the node set T, and each interconnect in the path is included in the interconnect set I;
- a node set U characterized as the set of nodes within the node set T that are on a path included in the path set P;
- for an interconnect link L in the interconnect set I, the interconnect link L being an interconnect link on a path in the path set P, a corresponding set of devices Z(L) exists in the device set Z such that a device w is included in the device set Z(L) only if a path containing the interconnect link L in the path set P exists from a device in the device set A to the device w;
- and
- the node set U includes distinct nodes NA, ND, and NE such that the node NA is capable of sending data to the node ND on a link LAD, the node NA is capable of sending data to the node NE on a link LAE, and a device set Z(LAE) is a proper subset of a device subset Z(LAD).
6 more elements
Dependencies are inferred from the claim text.