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 Arguments
Applicant’s arguments with respect to claim(s) 1, 3-11 and 13-20 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 § 112
The following is a quotation of 35 U.S.C. 112(d):
(d) REFERENCE IN DEPENDENT FORMS.—Subject to subsection (e), a claim in dependent form shall contain a reference to a claim previously set forth and then specify a further limitation of the subject matter claimed. A claim in dependent form shall be construed to incorporate by reference all the limitations of the claim to which it refers.
The following is a quotation of pre-AIA 35 U.S.C. 112, fourth paragraph:
Subject to the following paragraph [i.e., the fifth paragraph of pre-AIA 35 U.S.C. 112], a claim in dependent form shall contain a reference to a claim previously set forth and then specify a further limitation of the subject matter claimed. A claim in dependent form shall be construed to incorporate by reference all the limitations of the claim to which it refers.
Claims 3-4 and 13-14 are rejected under 35 U.S.C. 112(d) or pre-AIA 35 U.S.C. 112, 4th paragraph, as being of improper dependent form for failing to further limit the subject matter of the claim upon which it depends, or for failing to include all the limitations of the claim upon which it depends. Claims 3 and 4 depend from canceled claim 2 and claims 13 and 14 depend from canceled claim 12 and therefore does not further limit the parent claims. Applicant may cancel the claim(s), amend the claim(s) to place the claim(s) in proper dependent form, rewrite the claim(s) in independent form, or present a sufficient showing that the dependent claim(s) complies with the statutory requirements.
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.
Claims 1, 3-11 and 13-20 are rejected under 35 U.S.C. 103 as being unpatentable over Natarajan (US 20230266997 A1), in view of Alapati (US 8838801 B2) and Rao (US 20200019444 A1)
Regarding claim 1, Natarajan teaches:
A method for distributing workloads among nodes in a distributed computing environment, comprising. (Claim 1. A computer-implemented method for load balancing of computer jobs in a distributed computer network, the distributed computer network comprising a plurality of nodes, the method comprising.)
receiving, by a scheduling engine, a workload for placement in the distributed computing environment, each of the nodes in the distributed computing environment being associated with a node score. ([0022] The central scheduler 104 performs a selection process to determine where the pending pods should be placed. An example of a selection process is described in more detail in conjunction with FIG. 3. ([0017] The exemplary embodiments herein describe techniques for distributed scheduling in container orchestration engines….For example, some embodiments distribute at least a portion of the scheduling overhead to various nodes and/or clusters…Additionally, each node to cluster can apply local policies, filtering rules, and/or scoring criteria independently of other nodes or clusters to determine the extent to which it can satisfy the requirements of the workload…”.))
receiving, by the scheduling engine, node attributes from each of the nodes; determining attributes of data required by the workload; ([0016] Each of these techniques suffer from one or more of the following disadvantages: the scheduler processes workloads sequentially, thereby negatively impacting scheduling throughput; the central scheduler becomes a bottleneck when a deployment scales to a large number of nodes or a large number of clusters (for example, telephone communication companies often have edge nodes that need to scale to potentially thousands of clusters); and prevents each node or cluster from adopting different policies, filtering, or scoring criteria for hosting workloads. For instance, a node or cluster that has a significantly higher central processing unit (CPU) utilization compared to memory utilization can be assigned a higher score for a pod that is memory intensive in order to balance resource usage, for example. Also, for edge workloads, a cluster that is closer to end users of a workload is assigned a higher score. Different workloads require different criteria to be optimized, for example, in terms of latency, throughput, proximity, availability, and the ability to specify and realize these. See also [0026] and [0049-0051])
scoring the workload, by the scheduling engine, with a workload score that is based on attributes of the workload, wherein the node attributes received from the nodes are repeatedly received and repeatedly updated.([0017] Also, in some embodiments, a node is configured to independently score a subset of workloads it is capable of hosting, and this is done in parallel with other nodes. In some embodiments, each workload specifies its resource requirements and optimization objective (for example, resource balancing, latency and/or proximity).[0021]In some embodiments, each vote can correspond to a score by a given one of the nodes 108 with respect to a given pod. The scores for each pod are provided to the global workload registry 106 through the API server 110. An example process that can be performed by a given node 108 utilizing, at least in part, its pod selection module 120 is described in more detail in conjunction with FIG. 2. In at least one embodiment, the score can comprise a combination of a fixed score and a functional score. For example, the functional score can be a function of available resources of a given one of the nodes 108 to permit resource balancing, and the fixed score can be a numerical value based on the extent to which the given node 108 can fulfill the requirements of the pod. See also [0026], [0029], [0034-0035])
selecting, by the scheduling engine, a placement node from among the nodes for placing the workload based on the workload score and the node scores by ([0051] The information may include at least one of: resource requirements and optimization objectives for the plurality of workloads. The generating may include applying a set of local rules to generate the respective scores. The set of local rules may be different for at least two entities of the plurality of entities. The selecting may be performed based at least in part on resources available at each of the plurality of entities. The process may further include the step of: in response to the selecting, updating the resources available associated with the selected at least one entity. The process may further include the step of creating a group of two or more of the plurality of workloads, wherein the selecting comprises selecting the at least one of the entities to host the group. See also [0023] and [0048])
placing, by the scheduling engine, the workload at the selected node and executing the workload at the selected node. (([0022] The central scheduler 104 performs a selection process to determine where the pending pods should be placed. An example of a selection process is described in more detail in conjunction with FIG. 3. [0027] Referring now to FIG. 3, this figure shows a flow diagram of a placement process in accordance with exemplary embodiments. In this example it is assumed that the placement process is performed by the central scheduler 104.)) .
Natarajan it does not explicitly teach: in a first stage of a filtering operation, comparing the workload attributes with static node attributes of the nodes to identify first candidate nodes; in a second stage of the filtering operation, filtering the first candidate nodes by comparing the workload attributes with dynamic node attributes to identify final candidate nodes; wherein nodes having a workload attributed that does not satisfy a static node is filtered out during the first or second stage, wherein the placement node is selected from the final candidate nodes,
However, Alapati teaches: col 3, line 61-65. Generally, the illustrative embodiments provide effective allocation and usage of the cloud resources based on the nature of the submitted workload. An embodiment analyzes the workload--statically and dynamically to determine suitability of a cloud resource for executing that workload. col 4, line 44-64. While the static analysis of an embodiment provides some insights into the optimal placement of the workload on cloud resources, the runtime behavior of a workload may not be predictable based only on the static analysis. Therefore, an embodiment further provides for monitoring the execution of the workload in a dynamic analysis phase. The dynamic analysis of an embodiment monitors the workload execution on the selected cloud resource using, but not limited to, the performance parameters identified during static analysis. As an example, the dynamic analysis according to an embodiment can use the performance counters available in many data processing systems to determine the utilization of various processor resources, such as the cache, input/output (I/O) buffers, and registers. As another example, the dynamic analysis according to an embodiment can also compute a performance index for the workload's execution to determine whether the cloud resource that is being used to execute the workload is the optimal cloud resource for the execution under the prevailing circumstances in the cloud. Col 4, line 65 – col 5, line 10. The dynamic analysis according to an embodiment can further suggest another cloud resource to execute the workload if the selected cloud resource is sub-optimal for the workload. For example, based on the runtime characteristics of a workload, and based on the availability of certain cloud resources at the time of the execution, the dynamic analysis of an embodiment can suggest releasing the cloud resource being used for the workload and moving the workload to another available cloud resource, such that either the execution performance of the workload is improved, the cost of executing the workload is reduced, or both. The dynamic analysis according to an embodiment can further instruct a job scheduler to effect the change of cloud resources. Col 11,line 65 – col 12 line 11. (78) With reference to FIG. 7, this figure depicts a flowchart of an example process of cloud optimization using workload analysis in accordance with an illustrative embodiment. Process 700 can be implemented in a workload analyzer, such as in workload analyzer 312 in FIG. 3, which can be configured to include static analyzer 504 in FIG. 5 and dynamic analyzer 604 in FIG. 6. Process 700 begins by receiving a workload, such as from a job queue (step 702). Process 700 performs a static analysis on the workload, such as by using static analyzer 504 in FIG. 5 (step 704). Process 700 allocates cloud resources to the workload according to the static analysis (step 706). Process 700 sends the workload for execution, such as by informing a job scheduler to schedule the workload (step 708).
Accordingly, it would have been obvious to a person having ordinary skill in the art before the effective filing date of the claimed invention, having the teachings of Natarajan and Alapati before them to combine Alapati’s dynamic and static resource selection. One would have been motivated to make such combination to improve placement by eliminating resources early by using static attributes and refining selection by using dynamic runtime conditions.
Natarajan it does not explicitly teach: wherein the selected node has a current best node score,
However, Rao teaches: ([0054] In the example, for each node shown in column 1102, the health score of FIG. 9 and the FRAS of FIG. 10 are added to calculate SES as shown in column 1104. Accordingly, node 1 has an SES of 115 at row 1111; node 2 has an SES of 120 at row 1112; node 3 has an SES of 180 at row 1113; node 4 has an SES of 110 at row 1114; node 5 has an SES of 190 at row 1115; node 6 has an SES of 80 at row 1116; and node 7 has an SES of 110 at row 1117. In this example, the constants are tuned such that a score above 150 is preferable to be a candidate to receive a new job. A score of less than 120 is preferable to avoid scheduling if possible. Therefore, in the example, nodes 3 and 5 are given top priority for assignment of jobs, while nodes 1, 6, and 7 should be avoided if possible.[0043] This score is computed based on the health score and the future resource availability score. At 458, a new job is assigned to the node with the optimal schedule eligibility score.. See also [0044] and [0053].
Accordingly, it would have been obvious to a person having ordinary skill in the art before the effective filing date of the claimed invention, having the teachings of Natarajan and Rao before them, to combine Rao’s health base node scoring for selecting optimal node (best score) with Natarajan workload scoring. One would have been motivated to make such combination to ensure that each workload is place or migrated to the most optimal node.
Regarding claim 3, Natarajan in view of Alapati and Rao teaches the elements of claim 1 as outline above. Rao also teaches:
The method of claim 2, further comprising generating the node scores based on the node attributes such that each node is associated with a node score, wherein the current best node score is a lowest node score when using a first scoring mechanism and wherein the current best node score is a highest node score when using a second scoring mechanism. ([0050] FIG. 9 is a table 900 showing exemplary node health data. In the example, there are 7 nodes identified in column 902. They include Node 1 at row 911, Node 2 at row 912, Node 3 at row 913, Node 4 at row 914, Node 5 at row 915, Node 6 at row 916, and Node 7 at row 917. For each node, CPU idle percentage is indicated in column 904 and memory availability is indicated in column 906. Uptime is indicated in column 908. Penalty is indicated in column 910. In embodiments, the penalty is a factor of uptime. If the uptime is below a lower limit predetermined value or above an upper limit predetermined value, then a penalty is assessed, indicating possible lowered reliability of a node. For a node that recently completed its boot sequence and has an uptime below the lower limit predetermined value, it is not yet known if the node is stable. For a node that has a very long uptime that exceeds the upper limit predetermined value, issues such as memory leaks can degrade stability. The use of the penalty accounts for these issues in deriving the health score. In some embodiments, the penalty can additionally/alternatively be applied due to an increasing memory gradient as shown in FIG. 6. The computed health score (HS) is indicated in column 922.; Further note [0054] In the example, for each node shown in column 1102, the health score of FIG. 9 and the FRAS of FIG. 10 are added to calculate SES as shown in column 1104. Accordingly, node 1 has an SES of 115 at row 1111; node 2 has an SES of 120 at row 1112; node 3 has an SES of 180 at row 1113; node 4 has an SES of 110 at row 1114; node 5 has an SES of 190 at row 1115; node 6 has an SES of 80 at row 1116; and node 7 has an SES of 110 at row 1117. In this example, the constants are tuned such that a score above 150 is preferable to be a candidate to receive a new job. A score of less than 120 is preferable to avoid scheduling if possible. Therefore, in the example, nodes 3 and 5 are given top priority for assignment of jobs, while nodes 1, 6, and 7 should be avoided if possible.; Further it is noted that scheduling from highest to lowest or lowest to highest are well known scheduling algorithms that are further obvious to one of ordinary skill in the art.)
Regarding claim 4, Natarajan in view of Alapati and Rao teaches the elements of claim 1 as outline above. Natarajan also teaches:
The method of claim 3, further comprising updating the node scores, wherein the node attributes include the static node attributes and the dynamic node attributes. ([0026] Step 202 includes obtaining a list of pods (for example, from the global workload registry 106). Step 204 includes determining the characteristics associated with the list of pods. For example, the characteristics may include resource requirements and/or an optimization objective (for example, resource balancing, latency, and/or proximity). Step 206 includes computing a score using local rules for each pod. As an example, the local rules may include locally configured policies, filtering rules, and/or scoring criteria. Step 208 includes publishing the scores. For example, the scores can be published via the API server 110 to the global workload registry 106. The scores determined by the process depicted in FIG. 2 can be used to by the central scheduler 104 to place the pods on the nodes using the process depicted in FIG. 3, for example. See also [0017] and [0018])
Regarding claim 5, Natarajan in view of Alapati and Rao teaches the elements of claim 1 as outline above. Natarajan also teaches:
The method of claim 1, further comprising accounting for data attributes associated with data used by the workload and node attributes of the nodes, wherein the workload attributes, the node attributes, and the data attributes each include one or more of computer attributes, memory attributes, storage attributes, accelerator attributes, network attributes, runtime attributes, stream attributes, event attribute, energy attributes, and/or security attributes. ([0021] The scores for each pod are provided to the global workload registry 106 through the API server 110. An example process that can be performed by a given node 108 utilizing, at least in part, its pod selection module 120 is described in more detail in conjunction with FIG. 2. In at least one embodiment, the score can comprise a combination of a fixed score and a functional score. For example, the functional score can be a function of available resources of a given one of the nodes 108 to permit resource balancing, and the fixed score can be a numerical value based on the extent to which the given node 108 can fulfill the requirements of the pod. [0026] Step 202 includes obtaining a list of pods (for example, from the global workload registry 106). Step 204 includes determining the characteristics associated with the list of pods. For example, the characteristics may include resource requirements and/or an optimization objective (for example, resource balancing, latency, and/or proximity).; see also [0050-0051])
Regarding claim 6, Natarajan in view of Alapati and Rao teaches the elements of claim 1 as outline above. Natarajan also teaches:
The method of claim 1, further comprising filtering the nodes to identify candidate nodes, wherein the filtering includes comparing the workload attributes to the node attributes and/or data attributes. ([0020 ]Each of the pod selection modules 120 can leverage locally configured policies, filtering rules and scoring criteria to “vote” for at least a subset of the unscheduled pods listed in the global workload registry 106, and this voting process can be performed in a continuous manner, as described in more detail elsewhere herein. In some embodiments, each vote can correspond to a score by a given one of the nodes 108 with respect to a given pod. The scores for each pod are provided to the global workload registry 106 through the API server 110. An example process that can be performed by a given node 108 utilizing, at least in part, its pod selection module 120 is described in more detail in conjunction with FIG. 2. In at least one embodiment, the score can comprise a combination of a fixed score and a functional score. For example, the functional score can be a function of available resources of a given one of the nodes 108 to permit resource balancing, and the fixed score can be a numerical value based on the extent to which the given node 108 can fulfill the requirements of the pod.; see also [0050-0051])
Regarding claim 7, Natarajan in view of Alapati and Rao teaches the elements of claim 1 as outline above. Natarajan also teaches:
The method of claim 6, wherein filtering the nodes includes a first filtering based on static node attributes and a second filtering based on dynamic node attributes. ([0018] Generally, a filtering rule can determine which subset of pods are selected by a node to score. By way of example, a node that has a specific hardware accelerator can have a filtering rule that only picks pods that require that specific hardware accelerator. As another example, a filtering rule can be defined to select pods above a certain minimum memory requirement.; [0028] Step 302 includes obtaining a list of pods and scores generated by the nodes (for example, according to the process depicted in FIG. 2). Step 304 includes selecting a node to place a given one of the pods based on the node scores. Once a node is selected, step 306 includes updating the available resources of the node. As an example, the central scheduler 104 can consider one pod from the list at a time, determine its functional score component for each node based on the available resources of the node, and then pick the node with the best score to place the pod. See also [0019, 0050-0051])
Regarding claim 8, Natarajan in view of Alapati and Rao teaches the elements of claim 1 as outline above. Natarajan also teaches:
The method of claim 7, further comprising selecting the placement node from among the candidate nodes based on at least the node scores of the candidate nodes. ([0028] Step 302 includes obtaining a list of pods and scores generated by the nodes (for example, according to the process depicted in FIG. 2). Step 304 includes selecting a node to place a given one of the pods based on the node scores.)
Regarding claim 9, Natarajan in view of Alapati and Rao teaches the elements of claim 1 as outline above. Natarajan also teaches:
The method of claim 1, further comprising migrating the workload from the placement node to a second node included in the nodes.( [0030] A node, in some embodiments, can also prevent evicting a pod that it is assigned. For example, before the eviction is triggered, the node can provide information indicating plans to decommission a particular pod, and request another node to host that pod, see also [0031])
Regarding claim 10, Natarajan in view of Alapati and Rao teaches the elements of claim 1 as outline above. Natarajan also teaches:
The method of claim 9, further comprising migrating the workload when the workload is moveable and the second node has a sufficient node score. ([0031] As noted herein, the techniques for placing pods on nodes is also applicable for placing workloads on clusters in a multi-cluster environment. As an example, such techniques can be used for edge workloads, which are highly dynamic in nature, require low setup latency (for example, as a network slice in 5G/edge scenarios), have low application latency and/or high throughput, and may need to be dynamically relocated to another edge site if the user is mobile (for example, when the user corresponds to a connected vehicle or self-vehicle). Optimizing workloads in such a manner based on different criteria can be crucial in such situations.)
Regarding claim 11, the claim recites similar limitation as corresponding claim 1 and is rejected for similar reasons as claim 1 using similar teachings and rationale. Natarajan also teaches:
A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising. (Claim 13.A computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computing device to cause the computing device to.)
Regarding claim 13, the claim recites similar limitation as corresponding claim 3 and is rejected for similar reasons as claim 3 using similar teachings and rationale.
Regarding claim 14, the claim recites similar limitation as corresponding claim 4 and is rejected for similar reasons as claim 4 using similar teachings and rationale.
Regarding claim 15, the claim recites similar limitation as corresponding claim 5 and is rejected for similar reasons as claim 5 using similar teachings and rationale.
Regarding claim 16, the claim recites similar limitation as corresponding claim 6 and is rejected for similar reasons as claim 6 using similar teachings and rationale.
Regarding claim 17, the claim recites similar limitation as corresponding claim 7 and is rejected for similar reasons as claim 7 using similar teachings and rationale.
Regarding claim 18, the claim recites similar limitation as corresponding claim 8 and is rejected for similar reasons as claim 8 using similar teachings and rationale.
Regarding claim 19, the claim recites similar limitation as corresponding claim 9 and is rejected for similar reasons as claim 19 using similar teachings and rationale.
Regarding claim 20, the claim recites similar limitation as corresponding claim 10 and is rejected for similar reasons as claim 10 using similar teachings and rationale
Conclusion
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to CARLOS A ESPANA whose telephone number is (703)756-1069. The examiner can normally be reached Monday - Friday 8 a.m - 5 p.m EST.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, LEWIS BULLOCK JR can be reached at (571)272-3759. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/C.A.E./Examiner, Art Unit 2199
/LEWIS A BULLOCK JR/Supervisory Patent Examiner, Art Unit 2199