DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Amendment
Regarding the objection of claims 14-18 because of the claims recite an abbreviate “VRG” that has not been made clear. Applicant has amended the claims to include a definition of the abbreviation. Therefore, the objection of claims 14-18 is withdrawn.
Regarding the objection of claim 15 because on line 1 of claim 15, the limitation “The switch of claim 1” should be --The switch of claim 13. Applicant has made appropriate amendment to correct the dependency of claim 15. Therefore, the objection of claim 15 is withdrawn.
Response to Arguments
Applicant’s arguments with respect to claim(s) 1-18 have been considered but are moot because the new ground of rejection does not rely on any reference applied in the prior rejection of record for any teaching or matter specifically challenged in the argument.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 13-18 are rejected under 35 U.S.C. § 101 because the claims are directed to non-statutory subject matter. Claim 13, as presently drafted, does not constitute a proper “machine” claim because it fails to recite the structural elements that define the machine. While the preamble recites “A switch for preventing deadlocks in a high-performance computing environment…,” the body of the claim only sets forth functional capabilities and operations to be performed, without specifying the tangible structural components that make up the network device.
A “machine” under 35 U.S.C. § 101 must be a concrete thing, consisting of parts, or of certain devices and combination of devices, capable of performing the claimed functions. The present claim recites the switch only in terms of what it is “configured to” do (e.g., “configured to execute primitives,” “configured to perform operations comprising…”), and describes the receiving, and routing of packets entirely at a functional level. The claim does not identify any physical parts, components, or arrangements (such as processors, memory, interfaces, buses, circuitry, etc.) that structurally constitute the switch.
The absence of recited structural elements means the claim encompasses any device capable of performing the recited functions, regardless of its physical makeup. As such, the claim is not limited to a statutory “machine” but instead reads on non- statutory subject matter in the form of a set of functional results.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claim(s) 1,5-7, 11-13 and 17-18 is/are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Haramaty et al. (US 2016/0028613 A1).
Regarding claim 1, Haramaty discloses a method of preventing deadlocks in a high-performance computing environment (fig. 1, high-performance virtual computer network 20), the method comprising (Haramaty, fig.1 [0009;0029] discloses a high-performance computer network 20 configured to prevent cyclic flow-control deadlocks):
assigning switches (24 – fig. 1; [0030]) within a virtual routing group (VRG) (28 – fig. 1; [0030]) to one of two sets (i.e., within each group 28, nodes 24 are connected in a bipartite graph topology. In such a topology, the nodes are divided into two subsets, such that all links 36 connect a node of one subset and a node of the other subset. [0032]) (Haramaty, fig. 1, [0023] discloses a virtual dragonfly network topology. That is, the network is subdivided into virtual groups, with each group containing some number of switches and some number of endpoints. The nodes in each group are interconnected in a bipartite topology, meaning that the nodes of a given group are divided into two subsets, such that all intra-group links connect a node of one subset with a node of the other subset. That is, assigning switches within virtual routing group to two sets and the groups are interconnected in a mesh topology);
receiving, by a switch (node 24) assigned to one of two sets (nodes are configured in bipartite topology) of a virtual routing group [(VRG)], a packet on a link (Haramaty, figs.1 & 4 [0026; 0061] at a reception step 80, a node 24 receives a packet and determines a virtual lane associated with the packet at a virtual lane identification step 84); and
routing the packet by selecting either virtual lane level Vlev0 or Vlev1 in dependence upon the assigned set (set of permitted onward routes) and the link type (direct or indirect) on either virtual lane level Vlev0 or virtual lane level Vlev1 (Haramaty, fig. 4 [0012;0024;0051;0064] a given node is configured to define a set of permitted onward routes for a packet depending on a virtual lane value of the packet and on a port of the given node via which the packet was received. The given node is configured to store two or more forwarding tables, and to define the set of permitted onward routes by choosing one of the forwarding tables depending on the virtual lane value (VL0 and VL1) and the port. Since the nodes typically apply flow control independently per VL, depending on whether a received packet VL have already been modified or not, a forwarding node may choose virtual lane zero (VL0) or virtual lane one (VL1) to route the packet to a destination node).
Regarding claim 5, Haramaty discloses the method of claim 1 wherein the VRG comprises a plurality of switches arranged in an all-to-all topology and both sets include the same number of switches (Haramaty fig. 1, [0023;0033] discloses a dragonfly network topology. That is, the network is subdivided into groups, with each group containing some number of switches and some number of endpoints. The nodes in each group are interconnected in a bipartite topology, meaning that the nodes of a given group are divided into two subsets, such that all intra-group links connect a node of one subset with a node of the other subset. The bipartite topology may be full (i.e., every node in one subset is directly connected to every node in the other subset) or partial. The two subsets may be of the same size or of different sizes. In a partial bipartite topology, not every node of one subset is connected to every node of the other subset).
Regarding claim 6, Haramaty discloses the method of claim 1 where in the VRG comprises a virtual routing group in a Dragonfly topology (Haramaty, fig. 1, [0023] discloses a virtual dragonfly network topology. That is, the network is subdivided into virtual groups, with each group containing some number of switches and some number of endpoints).
Regarding claim(s) 7, 11-12, the claims are rejected with rational similar to that of claim(s) 1,5 and 6, respectively.
Regarding claim(s) 13,17 and 18, the claims are rejected with rational similar to that of claim(s) 1,5 and 6, respectively.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The text of those sections of Title 35, U.S. Code not included in this action can be found in a prior Office action.
Claim(s) 2-4,8-10 and 14-16 is/are rejected under 35 U.S.C. 103 as being unpatentable over Haramaty et al. (US 2016/0028613 A1) in view of Froese (US 2022/0166705 A1).
Regarding claim 2, Haramaty discloses the method of claim 1 wherein the packet is received on a terminal link and routing the packet in dependence upon the assigned set and the link type on either virtual lane level Vlev0 or virtual lane level Vlev1 (Haramaty, [0012;0024;0051] a given node is configured to define a set of permitted onward routes for a packet depending on a virtual lane value of the packet and on a port of the given node via which the packet was received. The given node is configured to store two or more forwarding tables, and to define the set of permitted onward routes by choosing one of the forwarding tables depending on the virtual lane value (VL0 and VL1) and the port. Since the nodes typically apply flow control independently per VL, depending on whether a received packet VL have already been modified or not, a forwarding node may choose virtual lane zero (VL0) or virtual lane one (VL1) to route the packet to a destination node).
Haramaty did not explicitly disclose routing the packet to a switch in the same set on virtual lane level Vlev0 if the destination is within the VRG and route control is non-minimal; routing the packet to the destination switch on virtual lane level Vlev1 if the destination is within the VRG and route control is minimal; and routing the packet to a switch in the same set on virtual lane level Vlev0 if the destination is not within the VRG and the switch does not have a global link to the destination VRG; and routing the packet to a switch in the destination VRG on virtual lane level Vlev0 if the destination is not within the VRG and the switch has a global link to the destination VRG.
In analogous art, Froese teaches routing the packet to a switch in the same set on virtual lane level Vlev0 (local virtual channels/links – links within the same group) if the destination is within the VRG (Switches in the same group/connected by local links/lanes) (Froese [0025] the dragonfly network topology subdivides the network into groups, with each group containing some number of switches and some number of endpoints. The ports of each switch are divided between edge ports, local ports, and global ports, where local ports connect to other switches within the same group and are used for forwarding packets designed for a local nodes. The FRF component 400 may choose VC 0/Vlve0 type local virtual channels/links/lanes based on the classification of the traffic to exchange traffic within a group) and route control is non-minimal (Froese [0027] when routing non-minimally, a packet must not be routed to an intermediate group that lacks connectivity with the destination group. This restriction can be achieved by preventing a group from being used as an intermediate group if it lacks connectivity with any other group. [0134] A Remote Switch Busy Local Port (RSBLP) Table (RSBLP table) stores busy port masks indexed by destination switch (switch_id), and again, can be used in the evaluation of local non-minimal paths consisting of a local hop to a neighboring switch followed by another local hop to the destination switch);
routing the packet to the destination switch on virtual lane level Vlev1 if the destination is within the VRG (Froese [0025] local ports connect to other switches within the same group and are used for forwarding packets designed for a local nodes. The FRF component 400 depending on the classification of a traffic may choose either VC 0/Vlve0 or VC 1/Vlve1 type local virtual channels/links/lanes to exchange traffic within a group) and route control is minimal (Froese [0102] the FRF component 400 includes at least: a minimal ports selection component 402 (which includes a minimal tables component 402A), various ports filters (permitted ports filters, operational ports filters, busy ports filters); a preferred ports discrimination component 402B. These components are used to ensure that route control is minimal); and
routing the packet to a switch in the same set on virtual lane level Vlev0 if the destination is not within the VRG (Froese [Abstract; 0028] dragonfly network topologies subdivide the network into plurality of groups containing switches, with each group coupled to all other groups via global links, including: at each switch within the network, maintaining a global fault table identifying the links which lead only to faulty global paths. Each switch in the source and destination groups maintain a global fault table. When a packet received at a switch in a source group is destined for a destination outside the source group, using a global fault table maintained in the switch, the switch identifies the links which lead only to faulty global paths. That is, links that do not have connection to a global link. When the data communication is received at a port of a switch that does not have a global link, the switch determines a destination for the data communication and, route the communication across Vlve0 in the network using the global fault table to avoid selecting a port within the switch that would result in the communication arriving at a point in the network where its only path forward is across a global link that is faulty. The global fault table is used at each hop the packet takes in the network until the packet reaches its destination group); and the switch does not have a global link to the destination VRG (Froese [Abstract] Each switch in the source and destination groups maintain a global fault table which is used to identify switches with faulty global links so that packets received on such switches that are destined for endpoint outside of the source group can be rerouted to a switch with a global link to the destination group); and
routing the packet to a switch in the destination VRG on virtual lane level Vlev0 if the destination is not within the VRG and the switch has a global link to the destination VRG (Froese [Abstract; 0028] When a packet received at a switch in a source group is destined for a destination outside the source group, using a global fault table maintained in the switch, the switch identifies the links which lead only to faulty global paths. That is, links that do not have connection to a global link. When the data communication is received at a port of a switch that does not have a global link, the switch determines a destination for the data communication and, route the communication across Vlve0 in the network using the global fault table to avoid selecting a port within the switch that would result in the communication arriving at a point in the network where its only path forward is across a global link that is faulty. The global fault table is used at each hop the packet takes in the network until the packet reaches its destination group).
One of ordinary skill would have been motivated to combine the teachings of Haramaty, and Froese because these teachings are from the same field of endeavor with respect to prevention of deadlock in packet transmission channels.
Therefore, before the effective filing date of the invention, it would have been obvious to a person of ordinary skill in the art to incorporate the strategies by Froese into the method by Haramaty, thereby enabling a global fault table is to be used for both a global minimal routing methodology and a global non-minimal routing methodology, Froese, [Abstract].
Regarding claim 3, Haramaty discloses the method of claim 1 wherein the packet is received on a global link and routing the packet in dependence upon the assigned set and the link type on either virtual lane level Vlev0 or virtual lane level Vlev1 (Haramaty [0049-0051] discloses forwarding packets in outbound direction from a local link to a global link via an intermediate virtual routing group. Because the packet traverses an intermediate group, it means that the virtual lane value has been modified. That is, the value has been changed from VL0 to VL1, such that, virtual lane 1 (VL1) is selected to route the packet).
Haramaty did not explicitly disclose routing the packet to a switch in the other set on virtual lane level Vlev0 if the destination is within the VRG and route control is non-minimal; routing the packet to the destination switch on virtual lane level Vlev1 if the destination is within the VRG and route control is minimal; and routing the packet to a switch in the other set on virtual lane level Vlev1 if the destination is not within the VRG and the switch does not have a global link to the destination VRG and route control is non-minimal, routing the packet to a switch in the destination VRG on virtual lane level Vlev1 if the destination is not within the VRG and the switch has a global link to the destination VRG.
Froese discloses routing the packet to a switch in the other set on virtual lane level Vlev0 if the destination is within the VRG and route control is non-minimal (Froese, figs. 4A &B, [0102;104; 0134] When a packet enters a source group, the packet may be routed either locally or globally through non-minimal path or a combination of local and global non-minimal paths depending on the destination of the packet. Routing in the switch fabric may be controlled by a fabric routing function (FRF) implemented in switch 202. A FRF component 400 of the switch may comprise: a non-minimal ports selection component 410 that includes local non-minimal selection component 410A and global non-minimal selection component 410B); and output logic component 412, which includes an adaptive selection component or logic 412A. When a packet received at a switch in a group is destined for a destination within the group where the packet is received, using a routing algorithm table 408, the FRF component 400 may route the packet to the destination by selecting a set of local non-minimal links/Virtual channels (Vlve0) forming a path to the destination within the group. The routing algorithm table 408, along with the adaptive selection function or logic 412A, also determines the VC to be used for the frame's next hop. A Remote Switch Busy Local Port (RSBLP) Table stores busy port masks indexed by destination switch (switch_id), and again, can be used in the evaluation of local non-minimal paths consisting of a local hop to a neighboring switch followed by another local hop to the destination switch);
routing the packet to the destination switch on virtual lane level Vlev1 if the destination is within the VRG and route control is minimal (Froese [0134] When a packet received at a switch in a group is destined for a destination within the group and for topologies, such as fat-tree, where a local minimal path can consist of a local hop to a neighboring switch followed by another local hop to the destination switch, the RSBLP Table can also be used in the evaluation of local minimal paths. The RSBLP table is used to filter out ports on the current switch which are poor choices for use in indirectly reaching the destination switch because the neighboring switch's port or ports that connect to the destination switch are too heavily loaded. The FRF selects local hops/virtual channels – Vlve1 that provide a local minimal path to the destination of the packet within the group); and
routing the packet to a switch in the other set on virtual lane level Vlev1 if the destination is not within the VRG (Froese, fig. 9, [0026; 0208] When a packet enters the network at one group (the source group) and leaves the network at a different group the destination group), the packet may be globally routed (routed between its source and destination group) either minimally or non-minimally. That is, the packet is routed either through a first or second Virtual Channels/lanes (VC 0 -Vlve0 or VC 1-Vlve1) from a source group to a destination. The packet takes a global minimal path if it traverses one global link, directly connecting the source group to the destination group) and the switch does not have a global link to the destination VRG (Froese [Abstract; 0028] When a packet received at a switch in a source group is destined for a destination outside the source group/destination group, using a global fault table maintained in the switch, the switch identifies the links which lead only to faulty global paths. That is, the switch does not have a global link connection to a destination group) and route control is non-minimal (Froese [Abstract; 0028] discloses global non-minimal routing, where some packets leaving the source group are routed to a group other than the destination group. This other group is chosen at random and is termed the intermediate group. On reaching an intermediate group, the packet is then routed directly to the destination group using a global link that directly connects the intermediate group to the destination group),
routing the packet to a switch in the destination VRG on virtual lane level Vlev1 if the destination is not within the VRG and the switch has a global link to the destination VRG (Froese [0026] When a packet enters the network at one group (the source group) and leaves the network at a different group the destination group), the packet may be globally routed (routed between its source and destination group) either minimally or non-minimally using Virtual Channels (VC 0 - Vlve 0 or VC 1 - Vlve 1). The packet takes a global minimal path if it traverses one global link, directly connecting the source group to the destination group. With global non-minimal routing, some packets leaving the source group are routed to a group other than the destination group. This other group is chosen at random and is termed the intermediate group. On reaching an intermediate group, the packet is then routed directly to the destination group using a global link that directly connects the intermediate group to the destination group).
The motivation to combine is similar to that of claim 2.
Regarding claim 4, Haramaty discloses the method of claim 1 wherein the packet is received on a local link and routing the packet in dependence upon the assigned set and the link type on either virtual lane level Vlev0 or virtual lane level Vlev1 (Haramaty [0049-0051] discloses forwarding packets in outbound direction from a local link to a global link via an intermediate virtual routing group. Because the packet traverses an intermediate group, it means that the virtual lane value has been modified. That is, the value has been changed from VL0 to VL1, such that, virtual lane 1 (VL1) is selected to route the packet).
Haramaty did not explicitly disclose routing the packet to the destination on a local link on virtual lane level Vlev1 if the destination is within the VRG; routing the packet to the destination VRG on a global link on virtual lane level Vlev1 if the destination is not within the VRG and the switch has a link to the destination VRG; and routing the packet to a pass-through VRG on a global link on virtual lane level Vlev0 if the destination is not within the VRG and the switch does not have a link to the destination VRG.
Froese discloses routing the packet to the destination on a local link on virtual lane level Vlev1 if the destination is within the VRG (Froese [0134] When a packet received at a switch in a group is destined for a destination within the group and for topologies, such as fat-tree, where a local minimal path can consist of a local hop to a neighboring switch followed by another local hop to the destination switch, the RSBLP Table can also be used in the evaluation of local minimal paths. The RSBLP table is used to filter out ports on the current switch which are poor choices for use in indirectly reaching the destination switch because the neighboring switch's port or ports that connect to the destination switch are too heavily loaded. The FRF selects local hops/virtual channels – Vlve1 that provide a local minimal path to the destination of the packet within the group);
routing the packet to the destination VRG on a global link on virtual lane level Vlev1 if the destination is not within the VRG and the switch has a link to the destination VRG (Froese [0026] When a packet enters the network at one group (the source group) and leaves the network at a different group the destination group), the packet may be globally routed (routed between its source and destination group) either minimally or non-minimally using Virtual Channels (VC 0 - Vlve 0 or VC 1 - Vlve 1). The packet takes a global minimal path if it traverses one global link, directly connecting the source group to the destination group. With global non-minimal routing, some packets leaving the source group are routed to a group other than the destination group. This other group is chosen at random and is termed the intermediate group. On reaching an intermediate group, the packet is then routed directly to the destination group using a global link that directly connects the intermediate group to the destination group); and
routing the packet to a pass-through VRG (intermediate group) on a global link on virtual lane level Vlev0 if the destination is not within the VRG and the switch does not have a link (faulty global links) to the destination VRG (Froese [0027; 0208] fig. 9, illustrates the process of choosing valid paths in a Dragonfly network. When a destination group is different from a source group. Packets are routed through paths including pass through switches located in in intermediate groups when they intersect the edge of the rectangle representing a group. A packet may take two or fewer local hops in both the source group 922 and intermediate group 924. It may take up to two local hops in the destination group 926 if it arrives at the group on VC 0 or 1. [0027] In situations where certain global links in the network are faulty, considerations must be made to avoid these global links such that a packet must not be routed to an intermediate group that lacks connectivity with the destination group. One way to achieve this restriction is to prevent a group from being used as an intermediate group if it lacks connectivity with any other group).
The motivation to combine is similar to that of claim 2.
Regarding claim(s) 8-10, the claim(s) are rejected with rational similar to that of claim(s) 2-4, respectively.
Regarding claim(s) 14-16, the claim(s) are rejected with rational similar to that of claim(s) 2-4, respectively.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. The following publications show the state of the art related to the use of Dragonfly network topology in preventing deadlock in a computer network.
Muntz Gary EP 4109853 A1
Any inquiry concerning this communication or earlier communications from the examiner should be directed to DIXON F DABIPI whose telephone number is (571)270-3673. The examiner can normally be reached on Monday - Friday from 9:00 am to 5:00 pm.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Christopher L Parry, can be reached at telephone number 571-272-8328. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from Patent Center. Status information for published applications may be obtained from Patent Center. Status information for unpublished applications is available through Patent Center to authorized users only. Should you have questions about access to the USPTO patent electronic filing system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free).
Examiner interviews are available via a variety of formats. See MPEP § 713.01. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) Form at https://www.uspto.gov/InterviewPractice.
/D.F.D/ Examiner, Art Unit 2451
/Chris Parry/Supervisory Patent Examiner, Art Unit 2451