Systems and methods that employ process algebra to specify contracts and utilize performance prediction implementations thereof to measure the specifications

• US 20050131978A1
• Filed: 07/30/2004
• Published: 06/16/2005
• Est. Priority Date: 12/10/2003
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Richter, David, Brown, Allen L. Jr., Meredith, Lucius G.
• Application Number:
  US10/903,959
• Publication Number:
  US 20050131978A1
• Time in Patent Office: Days
• US Class Current: 708/446
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 41/5006 Creating or negotiating SLA contracts, guarantees or penalties
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]

Abstract

The systems and methods of the present invention utilize stochastic calculus (e.g., pi calculus) to determine (e.g., specify, predict, etc.) quality of service that includes at least one of rate, uptime and capacity. The quality of service can be indicative of a level of service provided and/or required by an agent (e.g., a web service). The quality of service can be obtained by representing an agent'"'"'s contract via a model (e.g., state diagram or mathematical algorithm) and decorating the model with cost functions that are utilized to compute transition costs that are employed to predict associated rates for respective transitions. The model can further be decorated with error states to determine uptime and employed to determine channel capacity. In general, the quality service of a requesting agent and a providing agent can be compared to determine whether the providing agent can satisfy the level of performance of the requesting agent.

Claims

1. A system that employs process algebra and performance predicting techniques to specify and check contracts, comprising:

a first component that employs the process algebra to specify a contract in at least a fragment of the process algebra, and

a second component that compares the specified contract with an implementation generated via the performance predicting techniques, wherein a result of the comparison determines whether the implementation satisfies the contract.

2. The system of claim 1, wherein the process algebra is a stochastic pi calculus.

3. The system of claim 1, wherein the process algebra explicitly associates rates to actions.

4. The system of claim 1, wherein the process algebra is associated with semantics that provide for a Gillespie-style stochastic agent-based simulation.

5. The system of claim 1, wherein the process algebra includes operational semantics that associate proof-trees with transitions in a labeled transition system corresponding to an execution of process algebra based process.

6. The system of claim 5, wherein the process algebra based process is a pi calculus process.

7. The system of claim 1, further comprising a component that employs a cost function to compositionally map proof-trees to numbers that represent rates.

8. A method that employs process algebra and performance predicting techniques to specify and check contracts, comprising:

specifying a contract in at least a fragment of the process algebra;

employing the performance predicting techniques to predict an implementation of the contract; and

measuring the implementation of the contract against the specified contract to determine whether the specified contract and implementation thereof satisfy each other.

9. The method of claim 8, wherein the process algebra is a stochastic pi calculus with semantics that provide for a Gillespie-style stochastic agent-based simulation.

10. The method of claim 8, further comprising utilizing the process algebra to explicitly associate rates to actions.

11. The method of claim 8, further comprising employing the process algebra to associate proof-trees with transitions in a labeled transition system that corresponds to an execution of a pi calculus process.

12. The method of claim 8, further comprising utilizing a cost function to compositionally map proof-trees to numbers that represent rates.

13. A system that expresses a quality of service, comprising:

a description component that stores a definition of a level of performance for a first entity; and

a service manager that utilizes the definition to determine whether a second entity satisfies the level of performance of the first entity.

14. The system of claim 13, wherein the level of performance comprises at least one of a rate, an uptime and a capacity performance metric.

15. The system of claim 14, wherein the rate metric is predicted with process algebra.

16. The system of claim 15, wherein the process algebra is pi calculus.

17. The system of claim 14, wherein the rate metric is predicted by determining one or more costs of performance and correlating the one or more costs with respective rates.

18. The system of claim 17, wherein the one or more costs are computed by recursively applying respective cost functions over state transitions in the definition.

19. The system of claim 13, wherein a rate metric associated with the first entity is compared with a rate metric of the second entity to determine whether the second entity satisfies the level of performance of the first entity.

20. The system of claim 14, wherein the uptime metric indicates a frequency of error that is associated with one of down time and an exception state.

21. The system of claim 14, wherein the uptime metric is computed by decorating transitions to error states with rates and determining a frequency associated with transitions to the error states.

22. The system of claim 14, wherein the uptime metric associated with the first entity is compared with an uptime metric of the second entity to determine whether the second entity satisfies the level of performance of the first entity.

23. The system of claim 14, wherein the capacity metric indicates a quantity of data that is processed at a given time.

24. The system of claim 14, wherein the capacity metric is computed by applying Shannon'"'"'s theorem over a channel.

25. The system of claim 13, wherein the first and second entities are web services.

26. The system of claim 13, wherein the definition of the entity is compared with an implementation of a definition of the second entity through a conformance algorithm to facilitate determining whether the second entity satisfies the level of performance.

27. The system of claim 13, wherein the definition associated with the first entity is compared with a definition of a level of performance of the second entity with a compliance algorithm to determine whether the definitions are functional equivalents.

28. A method that utilizes a level of performance to facilitate selecting a service, comprising:

employing a stochastic math-based algorithm to predict a performance rate for an agent; and

comparing the predicted performance rate with an advertised performance rate of a service providing agent to determine whether the service providing agent is capable of satisfying the predicted rate.

29. The method of claim 28, further comprising transmitting the predicted performance rate to a plurality of service providing agents that compete to service a task associated with the predicted performance rate.

30. The method of claim 28, further comprising receiving one or more advertised performance rates from a plurality of service providing agents that compete to service a task associated with the predicted performance rate.

31. The method of claim 28, further comprising employing a stochastic algorithm to specify uptime for the agent, wherein the uptime is utilized to facilitate determining whether the service providing agent can satisfy a level of performance of the agent.

32. The method of claim 28, further comprising employing a stochastic algorithm to specify capacity for the agent, wherein the capacity is utilized to facilitate determining whether the service providing agent can satisfy a level of performance of the agent.

33. The method of claim 28, further comprising specifying the predicted performance rate in a contract that comprises at least one of a message content description, an agent location, and a communication protocol..

34. A data packet transmitted between two or more computer components that facilitates service related negotiations between agents, comprising:

a quality of performance, wherein the quality of performance includes rate, uptime and capacity metrics for the first agent that is compared with rate, uptime and capacity metrics of a second agent to determine whether the first agent satisfies the quality of performance of second first agent.

35. A computer readable medium storing computer executable components that facilitate specifying a level of performance, comprising:

a component that represents a web service as states;

a component that decorates associated state transitions with cost functions;

a component that utilizes the cost functions to predict a rate for respective state transitions; and

a component that compares the predicted rates to offered rates to determine whether an offered rate satisfies the predicted rate.

36. A system that employs a quality of performance as a negotiation tool between agents, comprising:

means for determining a quality of performance for respective agents;

means for comparing the quality of performance of the respective agents; and

means for matching at least two agents based on the comparison.