System for request aggregation in cloud computing services
Inventors
Denninnart, Chavit • Salehi, Mohsen Amini
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-11522810-B2
Publication Date
2022-12-06
Expiration Date
Abstract
Cloud-based computing systems, although claimed to have virtually unlimited resources, could get oversubscribed due to budget constraints of cloud users. The disclosed invention proposes a mechanism to identify various types of “mergeable” tasks. The system also determines when it is appropriate to aggregate tasks and how to allocate them so that the QoS of other tasks is not affected. Experimental results under real-world workload settings show that the disclosed system can improve robustness of the system in the face of oversubscription and also saves the overall time of using cloud services by more than 14%.
Core Innovation
The disclosed invention provides a server-less cloud computing system that performs admission control by detecting and merging mergeable tasks to aggregate requests/tasks. The system includes an Admission Control Component with a Task Similarity Detector, a Merge Appropriateness Identifier, a Task Merger, and at least two tasks, where each at least two tasks comprise a Group of Picture of a requested video stream. The Task Similarity Detector maintains one or more Request Similarity Hash-table(s), where each entry comprises a hash-key and a pointer to a corresponding task.
The Merge Appropriateness Identifier evaluates the impact of merging two or more tasks on any other tasks in a scheduling queue. It includes a Merge Impact Evaluator and a Time Estimator that estimates completion time of a task i on a given machine m using a completion time equation, including current time, estimated remaining time to complete the currently executing task on machine m, a sum of estimated execution times of N tasks pending in machine queue m ahead of task i, and an estimated execution time of task i.
The Merge Appropriateness Identifier further comprises a Position Finder and uses it to determine where in the scheduling queue merged tasks should be positioned. Mergeability can be achieved at either a task level or an operational level. The system is configured for use as part of a video streaming service, where at least two tasks are Group of Picture units and merging is performed through task aggregation under admission control.
Claims Coverage
The document contains two independent claims, each describing a server-less cloud computing system for admission control that detects task similarity using hash tables and decides to merge at least two tasks by evaluating the impact of merging on other tasks in a scheduling queue.
Server-less cloud computing Admission Control with Task Similarity Detector, Merge Appropriateness Identifier, Task Merger, and Scheduler
A system for server-less cloud computing comprising a processor and a computer readable medium executable in an Admission Control Component including a Task Similarity Detector, a Merge Appropriateness Identifier, a Task Merger, at least two tasks, a hash-table handler, at least one Request Similarity Hash-table, a Time Estimator, and a Scheduler, wherein each at least two tasks comprise a Group of Picture of a requested video stream.
Hash-table based similarity detection and queue-impact evaluation for merging based on completion-time estimation
The Task Similarity Detector maintains one or more hash tables comprising entries having a hash-key and a pointer to a corresponding task, and the Merge Appropriateness Identifier evaluates the impact of merging two or more tasks on other tasks in a scheduling queue, wherein the Merge Appropriateness Identifier comprises a Merge Impact Evaluator and wherein said Merge Impact Evaluator comprises a Time Estimator that estimates completion time of task i on machine m using a completion time equation with current time, estimated remaining time, a sum over N pending tasks ahead of task i, and estimated execution time of task i.
Position Finder and Merge Impact Evaluator in the Merge Appropriateness Identifier using completion-time estimation
A system for server-less cloud computing comprising a Task Similarity Detector, a Merge Appropriateness Identifier, a Task Merger, and at least two tasks, where the Task Similarity Detector maintains one or more hash tables with entries comprising a hash-key and a pointer to a corresponding task, and where the Merge Appropriateness Identifier evaluates the impact of merging two or more tasks on other tasks in a scheduling queue and comprises a Position Finder and a Merge Impact Evaluator including a Time Estimator that estimates completion time of task i on machine m using a completion time equation with current time, estimated remaining time, a sum over N pending tasks ahead of task i, and estimated execution time of task i.
Across the independent claims, the system’s core claim coverage centers on hash-table based task similarity detection for Group of Picture tasks and a Merge Appropriateness Identifier that evaluates merging by estimating completion time of tasks and assessing the impact of merging on other tasks in a scheduling queue; one independent claim additionally includes a Position Finder as part of the merge-appropriateness evaluation.
Stated Advantages
Documented Applications
No documented applications found
Interested in licensing this patent?