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 .
DETAILED ACTION
This Office Action is in response to Application No. 18/481483 filed on October 20, 2023. Claims 1-20 are presented for examination and are currently pending.
Claim Rejections - 35 USC § 103
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.
Claim(s) 1-3, 9, 11-14 and 20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Wong (US 20150215397) in view of Kogias (R2P2: Making RPCs First-Class Datacenter Citizens, 2019).
Regarding claim 1, Wong teaches a method for performing network accelerated scheduling, the method comprising:
receiving, at a programmable switch comprising a scheduler, a job comprising a plurality of tasks from a client (“The request may specify a job 19 that requires the retrieval of data from the client machine 5… the application program interface module 15 may asynchronously process the request by storing the job 19 in a scatter gather logical database 21 for parallel processing by a scatter gather peer-to-peer network 23.” ¶[0023-24]);
storing the plurality of tasks in a queue (“The scatter gather logical database 21 includes… a sub-job queue 27… Sub-jobs 20 may respectively correspond to sub-job events 51 that are stored on the sub-job queue 27.” (¶[0026]-[0028]));
scheduling, using a scheduling policy, at least one task in the queue to be performed by the first executor (“The scheduler 89 may utilize the job priority and remote resource information 33… to identify whether remote resources 41… are available for the sub-jobs 20… the scheduler 89 may move a sub-job event 51… based on the priority of the job 19… and an identification that the remote resources 41 are available.” (¶[0043]));
transmitting the at least one task to the first executor (“The task processor 99 may execute the tasks 39 in the sub-job 20… may execute a task 39 that utilizes an API server 13… to request listing data from the client machine 5… In response… the client machine 5 may communicate the listing data to the task processor 99…” (¶[0083])); and
receiving a task completion indication from the first executor (“Responsive to completion of the sub-job 20… decremented… The quantity of capacity utilized… may be based on the… requirements… The monitor module 18… generate user interfaces… to drill down… from a task 39 to a machine… that worked on the task 39.” (¶[0045-46])).
Wong, however, does not explicitly teach wherein the plurality of tasks in the queue are stored on the programmable switch; and receiving an indication from a first executor on a working node that the first executor is available for task execution.
On the one hand, Wong teaches detailed queuing and scheduling of tasks, but only in software, not on a switch. On the other hand, Kogias teaches in-network scheduling in a programmable switch, but does not implement a persistent, general-purpose task queue on the switch.
That is, Wong demonstrates the value of a centralized queue for scheduling jobs and tasks, but does so in software. Kogias (R2P2) shows that programmable switches (e.g., P4/Tofino) can be used to implement stateful, high-performance scheduling and load balancing, including maintaining per-worker state and bounded queues directly in the switch pipeline. Both references address the problem of efficient, scalable task/job scheduling in distributed systems/datacenters. As programmable switches became more capable (P4, Tofino), it would have been obvious to a POSITA to attempt to migrate the queuing and scheduling logic of Wong from a software server to a programmable switch, to gain the performance and scalability benefits shown in R2P2.
Kogias teaches wherein the plurality of tasks in the queue are stored on the programmable switch (“Register instances that correspond to different queues are organized in groups that can be checked in one pass… When i reaches n and there is still no available server, we keep recirculating the packet… The logic for R2P2-FEEDBACK decrements the outstanding count for the specific server…” (Section 4.3 P4/Tofino implementation)); and receiving an indication from a first executor on a working node that the first executor is available for task execution (“These messages, sent by the servers back to the router after completing the service of a request, specify… The number of requests this server has served including the last request… The router uses this information to track the current number of outstanding requests in the server’s bounded queue.” (Section 3.3, R2P2-FEEDBACK messages)).
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the queuing and scheduling techniques of Wong with the programmable switch-based scheduling techniques of Kogias, and to implement the task queue and scheduling logic of Wong on a programmable switch as taught by Kogias.
Wong and Kogias both address task/job scheduling in distributed systems and datacenters. Kogias demonstrates that programmable switches can be used for in-network scheduling and stateful logic, providing benefits of higher throughput, lower latency, and centralized control. A POSITA would recognize that implementing Wong’s queue and scheduling logic on a programmable switch, as taught by Kogias, would predictably yield these benefits, and would have a reasonable expectation of success given the state of the art in switch programming (P4/Tofino).
.Regarding claim 2, Wong/Kogias teaches the method of claim 1, further comprising:
receiving an indication from a second executor on the working node that the second executor is available for task execution (“The sub-job event 51 may be retrieved from the sub-job queue 27 and the corresponding sub-job 20 may be initially processed by the scatter gather peer-to peer network 23 until completion or until the sub-job 20 is interrupted causing the sub-job event 51 to be stored on the sub-job retry queue 53 with an associated time-out. Responsive to expiration of the timeout, the sub-job event 51 may be retrieved by scatter gather peer-to peer network 23 for further processing.” (¶[0027-29] on Wong);
scheduling, using the scheduling policy, at least one subsequent task in the queue to be performed by the second executor (“The scheduler 89 may utilize the job priority and remote resource information 33 (not shown) to identify whether remote resources 41 (not shown) are available for the sub-jobs 20. For example, the scheduler 89 may move a sub-job event 51 on the sub-job queue 27 based on the priority of the job 19 (e.g., high, medium, low), the remote resources 41 to execute the sub-job 20, and an identification that the remote resources 41 are available.” (¶[0042-44]) on Wong);
transmitting the at least one subsequent task to the second executor (“The task processor 99 may execute the tasks 39 in the sub-job 20. In the present example, the task processor 99 may execute a task 39 that utilizes an API server 13 from the API server resource pool 45 to request listing data from the client machine 5, as illustrated by the dashed line to operation 425, where the client machine 5 receives a request for listing data. In response to the request, the client machine 5 may communicate the listing data to the task processor 99 on the processing node 26. Further, at operation 423, the task processor 99 may execute a task that utilizes a database server in the database server resource pool 43 to add the listings to the items table 307 on the network-based marketplace 203.” (¶[0082-84]) on Wong); and
receiving another task completion indication from the second executor (“The current utilization information 110 may be used to store a current utilization of local resources ( e.g., memory, processors, etc.) by sub-jobs 20 for the associated pool of processing nodes 26. For example, the current utilization 110 may be stored as a normalized capacity that may be incremented coincident with moving a sub-job event 51 to the sub-job retry queue 53 and decremented responsive to completion of the sub-job 20.” (FIG.3A description ¶[0044-46] on Wong)).
Regarding claim 3, Wong/Kogias teaches the method of claim 2, wherein the first executor and the second executor perform task execution in parallel (“It will be appreciated that operation 421 may be performed by multiple processing nodes 26 in parallel. The processing nodes 26 may continue to process the sub-job events 51 until all of the sub-job events 51 associated with the job 19 are completed.” (¶[0081-83] on Wong)).
Regarding claim 9, Wong/Kogias teaches the method of claim 1, wherein the scheduling policy is a resource-constraint aware policy, further comprising:
determining minimum resources necessary to execute each respective task of the plurality of tasks (“The scheduler 89 may utilize the job priority and remote resource information 33 (not shown) to identify whether remote resources 41 (not shown) are available for the sub-jobs 20.” (¶[0042-44] on Wong)); and
wherein scheduling the at least one task in the queue to be performed by the first executor comprises identifying the at least one task for scheduling on the first executor in response to determining that the first executor has the minimum resources necessary to execute the at least one task (“The local resource information 55 may include current utilization information 110 and maximum utilization information 112.” (FIG.3A description ¶[0044-43] on Wong)).
Regarding claim 11, Wong/Kogias teaches the method of claim 1, wherein the client is a remote procedure call (RPC) client (“Remote Procedure Calls are widely used to connect data-center applications … R2P2: Making RPCs first-class datacenter citizens … R2P2 is a UDP-based transport protocol specifically designed for RPCs inside a datacenter.” (Title, Abstract, Sections 1, and 3 on Kogias)).
Regarding claims 12-14; these claim(s) limitations are significantly similar to those of claim(s) 1-3; and, thus, are rejected on the same grounds.
Regarding claims 20; these claim(s) limitations are significantly similar to those of claim(s) 1; and, thus, are rejected on the same grounds.
Claim(s) 4, 7, 10, 15 and 18 is/are rejected under 35 U.S.C. 103 as being unpatentable over Wong (US 20150215397) in view of Kogias (R2P2: Making RPCs First-Class Datacenter Citizens, 2019); and further in view of Ousterhout (Sparrow: Distributed, Low Latency Scheduling, 2013).
Regarding claim 4, Wong/Kogias explicitly teach all the claim limitations except for the method of claim 1, wherein receiving the job comprises receiving at least one job submission packet that indicates each of the plurality of tasks and task data dependencies.
Ousterhout teaches wherein receiving the job comprises receiving at least one job submission packet that indicates each of the plurality of tasks and task data dependencies (“Each scheduling request includes a list of task specifications; the specification for a task includes a task description and a list of constraints governing where the task can be placed.” (Section 6.1)).
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, to use the scheduling technique as disclosed in Ousterhout in the system of Wong/Kogias. The combination would have been obvious because a person of ordinary skill in the art would know to use the known technique outline in Ousterhout to improve the similar device of Wong/Kogias in the same way.
Regarding claim 7, Wong/Kogias teaches explicitly teach all the claim limitations except for the method of claim 1, wherein the scheduling policy is a first-in-first-out (FIFO) policy, and wherein scheduling the at least one task in the queue to be performed by the first executor comprises: identifying the at least one task for scheduling on the first executor in response to determining that the at least one task is an oldest available task in the queue.
Ousterhout teaches the method of claim 1, wherein the scheduling policy is a first-in-first-out (FIFO) policy, and wherein scheduling the at least one task in the queue to be performed by the first executor comprises: identifying the at least one task for scheduling on the first executor in response to determining that the at least one task is an oldest available task in the queue (Sparrow should schedule queries in FIFO order. Currently, Sparrow’s algorithm attempts to schedule jobs in FIFO order; adding query-level scheduling policies should improve end-to-end query performance. (Section 8)).
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, to use the scheduling technique as disclosed in Ousterhout in the system of Wong/Kogias. The combination would have been obvious because a person of ordinary skill in the art would know to use the known technique outline in Ousterhout to improve the similar device of Wong/Kogias in the same way.
Regarding claim 10, Wong/Kogias explicitly teach all the claim limitations except for the method of claim 1, wherein the scheduling policy is a data-locality aware policy, further comprising: determining, in nodes within a cluster comprising the working node, each location of data required to execute each respective task of the plurality of tasks; and wherein scheduling the at least one task in the queue to be performed by the first executor comprises identifying the at least one task for scheduling on the first executor in response to determining that a location of data required to execute the at least one task is stored on the working node of the first executor.
Ousterhout, in analogous art, teaches determining, in nodes within a cluster comprising the working node, each location of data required to execute each respective task of the plurality of tasks (“Tasks in the first stage are constrained to execute on machines that contain the task’s input data, while tasks in remaining stages (which read data shuffled or broadcasted over the network) are unconstrained.” (Section 7.1)); and
wherein scheduling the at least one task in the queue to be performed by the first executor comprises identifying the at least one task for scheduling on the first executor in response to determining that a location of data required to execute the at least one task is stored on the working node of the first executor (Sparrow also handles jobs with per-task constraints, such as constraints that limit tasks to run on machines where input data is located. Co-locating tasks with input data typically reduces response time, because input data does not need to be transferred over the network. (Section 4.1)).
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, to use the scheduling technique as disclosed in Ousterhout in the system of Wong/Kogias. The combination would have been obvious because a person of ordinary skill in the art would know to use the known technique outline in Ousterhout to improve the similar device of Wong/Kogias in the same way.
Regarding claims Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, to use the scheduling technique as disclosed in Ousterhout in the system of Wong/Kogias. The combination would have been obvious because a person of ordinary skill in the art would know to use the known technique outline in Ousterhout to improve the similar device of Wong/Kogias in the same way.
Regarding claims 15 and 18; these claim(s) limitations are significantly similar to those of claim(s) 4 and 7; and, thus, are rejected on the same grounds.
Claim(s) 5 and 16 is/are rejected under 35 U.S.C. 103 as being unpatentable over Wong (US 20150215397) in view of Kogias (R2P2: Making RPCs First-Class Datacenter Citizens, 2019); and further in view of Ganfield (US 2006/0106749).
Regarding claim 5, Wong/Kogias explicitly teach all the claim limitations except for the method of claim 1, wherein the queue has a P4-compatible circular queue design.
Ganfield, in analogous art, teaches wherein the queue has a P4-compatible circular queue design (A circular queue including several entries for storing commands is provided and a head loop count is stored with each command entry, when the entries are added to head of the queue; title, abstract).
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, to apply the known technique of organizing data in a circular queue as disclosed by Ganfield to the system of Wong/Kogias. The combination would have been obvious because a person of ordinary skill in the art would know to use the known technique of circular queues to improve the similar device of Wong/Kogias in the same way.
Regarding claim 16; these claim(s) limitations are significantly similar to those of claim(s) 5; and, thus, are rejected on the same grounds.
Claim(s) 8 and 19 is/are rejected under 35 U.S.C. 103 as being unpatentable over Wong (US 20150215397) in view of Kogias (R2P2: Making RPCs First-Class Datacenter Citizens, 2019); and further in view of Ramaswamy (US 2017/0060641).
Regarding claim 8, Wong/Kogias explicitly teach all the claim limitations except for the method of claim 1, wherein the scheduling policy is a priority-aware policy, further comprising: assigning a priority value to each of the plurality of tasks; and wherein scheduling the at least one task in the queue to be performed by the first executor comprises identifying the at least one task for scheduling on the first executor in response to determining that the at least one task is an oldest available task with a highest priority value in the queue.
Ramaswamy teaches wherein the scheduling policy is a priority-aware policy, further comprising: assigning a priority value to each of the plurality of tasks (Different scheduling policies include first come first served scheduling, shortest job first scheduling, priority scheduling, round robin scheduling, and weight-based scheduling. First come first served policy executes tasks based on the time the tasks are placed in the queue. Shortest job first policy schedules the shortest task in the queue first for execution. The policy minimizes the waiting time of the tasks, however there is a need to know the execution time of each task in advance, which is impractical in most applications. Priority (or priority based) scheduling assigns a priority to each task. The task with the highest priority is executed first. [¶0033-36]); and wherein scheduling the at least one task in the queue to be performed by the first executor comprises identifying the at least one task for scheduling on the first executor in response to determining that the at least one task is an oldest available task with a highest priority value in the queue (As shown, the scheduling policies 310-320 for each application is stored in a database 325. During the execution of each application 220-230, the corresponding local task manager 250-260 uses the application's intra application scheduling policy 310-320 to determine which task is removed from the corresponding application's queue 235-245 (shown in FIG. 2). In the absence of a custom defined scheduling strategy, each LTM uses a default scheduling policy such as first come first served. [¶0035]).
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, to use a priority-based scheduling policy as disclosed in Ramaswamy in the system of Wong/Kogias. The combination would have been obvious because a person of ordinary skill in the art would know to use the known technique of priority-based scheduling to improve the similar device of Wong/Kogias in the same way.
Regarding claim 19; these claim(s) limitations are significantly similar to those of claim(s) 8; and, thus, are rejected on the same grounds.
Allowable Subject Matter
Claims 6 and 17 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to RAMON A MERCADO whose telephone number is (571)270-5744. The examiner can normally be reached Mo-Th: 5:30AM-4PM.
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.
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.
/Ramon A. Mercado/Supervisory Patent Examiner, Art Unit 3658