Quality of service aware scheduling for composite web service workflows
First Claim
1. A computer-implemented method of assigning a web service request to a plurality of service providers comprising:
- sending a web service request from a requesting computer to a first network;
sending the web service request from the first network to a network server;
sending the web service request from the network server to an application server;
performing by a computer processor on the application server;
decomposing, by the computer processor, a web service request received by the application server from the first network into a plurality of workflows;
analyzing, by the computer processor, the plurality of workflows using a computer to determine a plurality of business processes;
associating, by the computer processor, a plurality of web service types with each of the plurality of business processes, wherein the web service types describe one of the plurality of web service providers;
assigning, by the computer processor, a business value including average completion time of one of the business processes to each of the plurality of business processes;
evaluating, by the computer processor, the plurality of web service types with respect to the business value of each of the plurality of business processes;
maximizing, by the computer processor, the business value for one of the plurality of business processes by selecting one of the plurality of business processes;
creating, by the computer processor, an aggregated business process by combining partially completed ones of the plurality of business processes with an unstarted one of the plurality of business processes;
queueing, by the computer processor, the plurality of business processes for execution, in response to the queueing, searching for an assignment of said plurality of business processes and the aggregated business process to said plurality of service providers based on a minimum completion time for executing the web service request across all service providers, wherein the searching further comprises solving a combinatorial optimization problem utilizing a genetic search algorithm comprising;
selecting initial chromosomes, wherein a chromosome is an assignment of one of the plurality of business processes to one of the plurality of service providers;
mutating the selected chromosomes responsive to a mutation rate, wherein the selected chromosomes mutate only when a random number generator provides a non-negative integer that is less than or equal to a current number of the plurality of workflows; and
iteratively,recombining the mutated chromosomes;
evaluating a cost for recombined chromosomes;
selecting recombined chromosomes with a lowest value of the cost;
until all the workflows have been evaluated;
performing, by the computer processor, those of the plurality of workflows that are independent of each other in non-sequential order using the assigned one of said plurality of service providers;
adjusting, by the computer processor, workload for one of the plurality of workflows among the plurality of service providers by balancing the workload for the one of the plurality of workflows on a plurality of web servers based on a maximum concurrency of the plurality of workflows, wherein for workloads that exceed the maximum concurrency, an expected average completion time for the workload varies with expected completion time, workload size, and average performance under workload;
categorizing, by the computer processor, a first one of the plurality of workflows as a success when a completion time of the one of the plurality of workflows is less than a predetermined quality value; and
categorizing, by the computer processor, a second one of the plurality of workflows as a failure when the completion time of the one of the plurality of workflows is greater than a constant times the predetermined quality value, andoutputting, by the computer processor, the plurality of business processes to a second network.
1 Assignment
0 Petitions
Accused Products
Abstract
A method of assigning web service requests to service providers includes searching for an optimal assignment from all possible assignments using a genetic algorithm (GA) that represents possible assignments as chromosomes, and converging towards an assignment of web service request to service providers that maximizes overall business value for all workflows to the service providers. An adaptive mutation scheme is used to introduce mutation into populations of chromosomes. The mutation scheme includes a mutation rate that increases when chromosomes under evaluation fail to improve its workload against the metric over a certain number of generations.
-
Citations
25 Claims
-
1. A computer-implemented method of assigning a web service request to a plurality of service providers comprising:
-
sending a web service request from a requesting computer to a first network; sending the web service request from the first network to a network server; sending the web service request from the network server to an application server; performing by a computer processor on the application server; decomposing, by the computer processor, a web service request received by the application server from the first network into a plurality of workflows; analyzing, by the computer processor, the plurality of workflows using a computer to determine a plurality of business processes; associating, by the computer processor, a plurality of web service types with each of the plurality of business processes, wherein the web service types describe one of the plurality of web service providers; assigning, by the computer processor, a business value including average completion time of one of the business processes to each of the plurality of business processes; evaluating, by the computer processor, the plurality of web service types with respect to the business value of each of the plurality of business processes; maximizing, by the computer processor, the business value for one of the plurality of business processes by selecting one of the plurality of business processes; creating, by the computer processor, an aggregated business process by combining partially completed ones of the plurality of business processes with an unstarted one of the plurality of business processes; queueing, by the computer processor, the plurality of business processes for execution, in response to the queueing, searching for an assignment of said plurality of business processes and the aggregated business process to said plurality of service providers based on a minimum completion time for executing the web service request across all service providers, wherein the searching further comprises solving a combinatorial optimization problem utilizing a genetic search algorithm comprising; selecting initial chromosomes, wherein a chromosome is an assignment of one of the plurality of business processes to one of the plurality of service providers; mutating the selected chromosomes responsive to a mutation rate, wherein the selected chromosomes mutate only when a random number generator provides a non-negative integer that is less than or equal to a current number of the plurality of workflows; and iteratively, recombining the mutated chromosomes; evaluating a cost for recombined chromosomes; selecting recombined chromosomes with a lowest value of the cost; until all the workflows have been evaluated; performing, by the computer processor, those of the plurality of workflows that are independent of each other in non-sequential order using the assigned one of said plurality of service providers; adjusting, by the computer processor, workload for one of the plurality of workflows among the plurality of service providers by balancing the workload for the one of the plurality of workflows on a plurality of web servers based on a maximum concurrency of the plurality of workflows, wherein for workloads that exceed the maximum concurrency, an expected average completion time for the workload varies with expected completion time, workload size, and average performance under workload; categorizing, by the computer processor, a first one of the plurality of workflows as a success when a completion time of the one of the plurality of workflows is less than a predetermined quality value; and categorizing, by the computer processor, a second one of the plurality of workflows as a failure when the completion time of the one of the plurality of workflows is greater than a constant times the predetermined quality value, and outputting, by the computer processor, the plurality of business processes to a second network. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A computer program product for assigning a web service request to a plurality of service providers, the computer program product comprising:
-
a non-transitory computer readable storage medium on an application server computer having computer readable program code embodied therewith, when executed by a computer processor causes the computer processor to receive computer executable instructions from a first network, and causes the computer processor to perform the steps comprising; decomposing a web service request into a plurality of workflows, wherein the web service request is received from a requesting computer through a first network to a network server, and from the network server to the application server computer; analyzing the plurality of workflows using a computer to determine a plurality of business processes; associating a plurality of web service types with each of the plurality of business processes, wherein the web service types describe one of the plurality of service providers; assigning a business value including average completion time to each of the plurality of business processes; evaluating the plurality of web service types with respect to the business value of each of the plurality of business processes; maximizing the business value for one of the plurality of business processes by selecting one of the plurality of web service types for one of the plurality of business processes; creating an aggregated business process by combining partially completed ones of the plurality of business processes with an unstarted one of the plurality of business processes; queueing the plurality of business processes for execution, in response to the queueing, searching for an assignment of said plurality of business processes and the aggregated business process to said plurality of service providers based on a minimum completion time for executing the web service request across all of the plurality of service providers, wherein the searching further comprises solving a combinatorial optimization problem utilizing a genetic search algorithm comprising; selecting initial chromosomes wherein a chromosome is an assignment of one of the plurality of business processes to one of the plurality of service providers; mutating the selected chromosomes responsive to a mutation rate, wherein the selected chromosomes mutate only when a random number generator provides a non-negative integer that is less than or equal to a current number of the plurality of workflows; and iteratively, recombining the mutated chromosomes; evaluating a cost for the recombined chromosomes; selecting recombined chromosomes with lowest value of the cost; until all the workflows have been evaluated; performing the plurality of workflows that are independent of each other in non-sequential order; adjusting workload for one of the plurality of workflows and balancing the workload on a plurality of web servers based on a maximum concurrency of the plurality of workflows, wherein for workloads that exceed the maximum concurrency of the plurality of workflows, an expected average completion time for the workload varies with expected completion time, workload size, and average performance under workload; categorizing a first one of the plurality of workflows as a success when a completion time of the one of the plurality of workflows is less than a predetermined quality value; and categorizing a second one of the plurality of workflows as a failure when the completion time of the one of the plurality of workflows is greater than a constant times the predetermined quality value, wherein the computer processor is configured to output the plurality of business processes to a second network. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
23. An electronic commerce system comprising:
-
a requesting computer configured to send a web service request with respect to a web service through a first network to a network server computer; an application server computer configured to support the web service; the network server computer configured to output computer executable instructions from the first network to the application server computer; a memory device configured to store the computer executable instructions, that when stored on the application server computer and executed by the application server computer, the computer executable instructions comprise; a decomposition module that is configured to decompose a web service request into a plurality of workflows; an analysis module that is configured to analyze the plurality of workflows using a computer to determine a plurality of business processes; an association module that is configured to associate a plurality of web service types with each of the plurality of business processes; an assignment module that is configured to assign a business value including average completion time to each of the plurality of business processes; an evaluation module configured to select one of the plurality of web service types for each of the plurality of business processes, and maximize the business value for one of the plurality of business processes by selecting one of the plurality of web service types for one of the plurality of business processes; an aggregation module configured to create an aggregated business process by combining partially completed ones of the plurality of business processes with an unstarted one of the plurality of business processes; a search module that is configured to queue the plurality of business processes for execution, in response to the queue, searching for an assignment of said plurality of business processes and the aggregated business process to a plurality of service providers based on a minimum completion time executing the web service request across all the plurality of service providers, wherein the searching further includes solving a combinatorial optimization problem utilizing a genetic search algorithm comprising; selecting initial chromosomes, wherein a chromosome is an assignment of one of the plurality of business processes to one of the plurality of service providers; mutating the selected chromosomes responsive to a mutation rate, wherein the selected chromosomes mutate only when a random number generator provides a non-negative integer that is less than or equal to a current number of the plurality of workflows; and iteratively, recombining the mutated chromosomes; evaluating a cost for the recombined chromosomes; selecting recombined chromosomes with lowest value of the cost; until all the workflows have been evaluated; a performance module that is configured to perform the plurality of workflows that are independent of each other in non-sequential order, wherein the performance module performs workload balancing by performing the plurality of workflows among a plurality of web servers in a balanced manner; an adjustment module that is configured to adjust workload for one of the plurality of workflows based on a maximum concurrency of the plurality of workflows, wherein for workloads that exceed the maximum concurrency, an expected average completion time for the workload varies with expected completion time, workload size, and average performance under workload; a categorization module that is configured to categorize a first one of the plurality of workflows as a success when a completion time of the one of the plurality of workflows is less than a predetermined quality value; and the categorization module further is configured to categorize a second one of the plurality of workflows as a failure when the completion time of the one of the plurality of workflows is greater than a constant times the predetermined quality value, wherein the performance module outputs the plurality of business processes for execution on a second network. - View Dependent Claims (24, 25)
-
Specification