System for request aggregation in cloud computing services

Patent metadata

Field	Value
Publication number	US-11522810-B2
Application number	US-201916663535-A
Country	US
Kind code	B2
Filing date	Oct 25, 2019
Priority date	Oct 25, 2018
Publication date	Dec 6, 2022
Grant date	Dec 6, 2022

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%.

First claim

The invention claimed is:

1. A system for server-less cloud computing comprising:
(a) a processor and a computer readable medium operably coupled thereto, the computer readable medium composing a plurality of instructions stored in association therewith that are accessible to, and executable by, the processor in an Admission Control Component, comprising:
(i) a Task Similarity Detector;
(ii) a Merge Appropriateness Identifier;
(iii) a Task Merger;
(iv) at least two tasks;
(v) a hash-table handler; and
(vi) at least one Request Similarity Hash-table;

(b) a Time Estimator; and
(c) a Scheduler;
wherein each at least two tasks comprise a Group of Picture of a requested video stream;
wherein the Task Similarity Detector comprises coding capable of maintaining one or more hash tables, wherein said hash tables comprise on or more entries, wherein each entry comprises a hash-key and a pointer to a corresponding task;
wherein the Merge Appropriateness Identifier comprises coding capable of evaluating the impact of merging two or more tasks on any other tasks in a scheduling queue of the system;
wherein the Merge Appropriateness Identifier comprises:
a Merge Impact Evaluator,
wherein said Merge Impact Evaluator further comprises a Time Estimator, and said Time Estimator estimates the completion time of a task i on a given machine m, denoted as Cr by use of the following equation:

C
i
m

=

τ
+

e
r
m

+

∑

p
=
1

N

⁢

(

μ
p

+

2
⁢

σ
p

)

+

(

μ
i

+

2
⁢

σ
i

)

using the following factors:
(a) current time, denoted τ;
(b) estimated remaining time to complete the currently executing task on machine m denotated e r m ;
(c) sum of the estimated execution times of N tasks pending in machine queue m, ahead of task I, calculated as Σ p=1 N (μ p +2σ p ); and
(d) estimated execution time of task i.

2. The system of claim 1 , wherein the Merge Appropriateness Identifier comprises:
a Position Finder.

3. The system of claim 1 , wherein the mergeability of two tasks is achieved on a task level or an operational level.

4. A system for server-less cloud computing comprising:
a processor and a computer readable medium operably coupled thereto, the computer readable medium composing a plurality of instructions stored in association therewith that are accessible to, and executable by, the processor:
(a) a Task Similarity Detector;
(b) a Merge Appropriateness Identifier;
(c) a Task Merger; and
(d) at least two tasks;
wherein the Task Similarity Detector comprises coding capable of maintaining one or more hash tables, wherein said hash tables comprise on or more entries, wherein each entry comprises a hash-key and a pointer to a corresponding task;
wherein the Merge Appropriateness Identifier comprises coding capable of evaluating the impact of merging two or more tasks on any other tasks in a scheduling queue of the system;
wherein the Merge Appropriateness Identifier comprises:
(a) a Position Finder; and
(b) a Merge Impact Evaluator;
wherein said Merge Impact Evaluator further comprises a Time Estimator, and said Time Estimator estimates the completion time of a task i on a given machine m, denoted as C i m by use of the following equation:

C
i
m

=

τ
+

e
r
m

+

∑

p
=
1

N

⁢

(

μ
p

+

2
⁢

σ
p

)

+

(

μ
i

+

2
⁢

σ
i

)

using the following factors:
(a) current time, denoted τ;
(b) estimated remaining time to complete the currently executing task on machine m, denoted e r m ;
(c) sum of the estimated execution times of N tasks pending in machine queue m, ahead of task i, calculated as Σ p=1 N (μ p +2σ p ); and
(d) estimated execution time of task i.

5. The system of claim 1 , wherein said system for server-less cloud computing is used as part of a video streaming service.

6. The system of claim 2 , wherein the Position Finder comprises functionality to locate a suitable position for at least one merged task in the scheduling queue.

7. The system of claim 4 , wherein said system for server-less cloud computing is used as part of a video streaming service.

8. The system of claim 4 , wherein the Position Finder comprises functionality to locate a suitable position for at least one merged task in the scheduling queue.

9. The system of claim 4 , wherein the mergeability of two tasks is achieved on a task level or an operational level.

Assignees

• Univ Louisiana At Lafayette

Inventors

• Denninnart Chavit
• Salehi Mohsen Amini

Classifications

• H04L47/808

  User-type aware · CPC title

• H04L47/827

  Aggregation of resource allocation or reservation requests · CPC title

• H04L47/821

  Prioritising resource allocation or reservation requests · CPC title

• G06F9/4887 Primary

  involving deadlines, e.g. rate based, periodic · CPC title

• H04L47/826

  Involving periods of time · CPC title