×

Quality of service aware scheduling for composite web service workflows

  • US 9,020,829 B2
  • Filed: 05/07/2008
  • Issued: 04/28/2015
  • Est. Priority Date: 05/07/2008
  • Status: Expired due to Fees
First Claim
Patent Images

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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×