Regression-based system and method for determining resource costs for composite transactions

A method comprises receiving a representative workload of a computing system, where the representative workload comprises at least one composite transaction. In certain embodiments, the representative workload is a historical workload of a computing system. In general, a composite transaction refers to a transaction that comprises a plurality of transactions. For instance, a given transaction for serving a client's request for information (e.g., a web page) may include embedded therein a plurality of requests/responses for objects (e.g., images, etc.) that form the information (e.g., that form the requested web page). The method further comprises determining, based at least in part on a statistical regression-based analysis, a resource cost for the at least one composite transaction, where the resource cost reflects an amount of utilization of at least one resource of the computing system, such as CPU utilization, in serving the at least one composite transaction.

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is related to concurrently filed and commonly assigned U.S. patent application Ser. No. 11/684,567 entitled “SYSTEM AND METHOD FOR DETERMINING A SUBSET OF TRANSACTIONS OF A COMPUTING SYSTEM FOR USE IN DETERMINING RESOURCE COSTS”, and concurrently filed and commonly assigned U.S. patent application Ser. No. 11/684,569 entitled “SYSTEM AND METHOD FOR CAPACITY PLANNING FOR COMPUTING SYSTEMS”, the disclosures of which are hereby incorporated herein by reference.

TECHNICAL FIELD

The following description relates generally to capacity planning for computer systems, and more particularly to systems and methods for determining resource costs for composite transactions included an a representative workload.

DESCRIPTION OF RELATED ART

Today, computer systems are delivering (e.g., via computer networks, such as the Internet) a large array of business, government, and personal services. Similarly, mission critical operations, related to scientific instrumentation, military operations, and health services, are making increasing use of computer systems and computer networks for delivering information and distributed coordination. For example, many users are accessing service providers' computer systems via the Internet seeking such services as personal shopping, airline reservations, rental car reservations, hotel reservations, on-line auctions, on-line banking, stock market trading, as well as many other services being offered by service providers via computer networks, such as the Internet. Therefore, many service providers are competing in such electronic forum. Accordingly, it is important for such service providers (sometimes referred to as “content providers”) to provide high-quality services. To do so, it has become desirable for such service providers to perform appropriate capacity planning to ensure that they can adequately service the demands placed on their systems by their clients in a desired manner (e.g., provide responses to requests in sufficiently fast time, etc., such as by serving responsive web pages to a requesting client within 8 seconds and/or satisfy some other quality of service target).

As information technology (“IT”) and application infrastructures, such as those employed by the above-mentioned service providers for serving their clients, have become more complex, predicting and controlling the issues surrounding system performance and capacity planning have become a difficult (and sometimes overwhelming) task to many organizations. For larger IT projects, it is not uncommon for the cost factors related to performance tuning, performance management, and capacity planning to result in the largest and least controlled expense. Application performance issues have an immediate impact on customer satisfaction. A sudden slowdown of an enterprise-wide application can affect a large population of customers, can lead to delayed projects, and ultimately can result in company financial loss.

Large-scale enterprise development projects are increasingly relying on Service-Oriented Architecture (SOA) design. This approach provides a collection of mechanisms and interfaces for a dynamic enterprise IT environment to connect applications where the classic, data-processing legacy systems can be integrated with agile web-based front-end applications. Application servers have emerged to provide a standardized platform for developing and deploying scalable enterprise systems. The application servers are often considered a core component of an enterprise system and an integral part of a new trend toward building SOAs.

Multi-tier architectures are also commonly being employed. For instance, the three-tier architecture paradigm has become an industry standard for building scalable client-server applications. In a typical three-tier architecture for an application, the application comprises the following three tiers: 1) an interface tier (sometimes referred to as the presentation tier), 2) an application tier (sometimes referred to as the logic or business logic tier), and 3) a data tier (e.g., database tier). The first tier provides a user interface, such as a graphical user interface (GUI), with which the user may interact with the other tiers. The second tier provides functional process logic, which may comprise one or more separate modules running on a workstation or application server, for example. The application tier may, in some implementations, be multi-tiered itself (in which case the overall architecture may be called an “n-tier architecture”). The third tier manages the storage and access of data for the application. Typically, a relational database management system (RDBMS) on a database server or mainframe contains the data storage logic of the third tier. The three tiers are developed and maintained as independent modules, often on separate platforms. Quite often the first and second tiers may be implemented on common hardware (i.e., on a common platform), while the third tier is implemented on a separate platform, but any arrangement of the three tiers (i.e., either on common hardware or across separate hardware) may be employed in a given implementation. The three-tier architecture is generally intended to allow any of the three tiers to be upgraded or replaced independently as requirements, desires, and/or technology change. For example, a change of operating system from Microsoft Windows™ to Unix™ may only affect the user interface code.

As an example, suppose that a service provider develops a web application that provides banking services to clients via the web. In this example, the banking application may comprise a user interface tier that defines the user interface with which the clients interact to perform desired banking transactions. The banking application may further comprise an application tier that defines the business logic and functionality of the banking application. The banking application may further comprise a data tier that is operable to manage access of the clients' respective account balance data, for example. In such multi-tiered systems, frequent calls to application servers and data storage (e.g., databases) may place a heavy load on these resources and may cause throughput bottlenecks and high server-wide processing latency.

Traditionally, preliminary system capacity estimates are performed for service provider systems by using synthetic work-load or benchmarks which are created to reflect a “typical application behavior” for “typical client requests”. While this performance evaluation approach can be useful at the initial stages of design and development of a future system, it is often inadequate for answering more specific questions about an existing system that is deployed in a service provider's environment. In many cases, the workload actually encountered by a deployed system does not correspond with the synthetic workload that was expected for the system, and thus the preliminary system capacity estimates may be inadequate. Further, the techniques used for arriving at the preliminary system capacity estimates are unable to answer specific capacity planning questions that a given service provider may have about the capacity of the deployed system. Further still, evaluating the capacity of a deployed system based on a representative workload of the deployed system, such as an actual historical workload encountered by the deployed system, may be difficult and/or compute-intensive, particularly when the representative workload includes composite transactions. In general, a composite transaction refers to a transaction that comprises a plurality of transactions. For instance, a given transaction for serving a client's request for information (e.g., a web page) may include embedded therein a plurality of requests/responses for objects (e.g., images, etc.) that form the information (e.g., that form the requested web page), and thus the given transaction for serving the information may be considered a composite transaction as it involves various transactions for serving the objects that form such information. Determining a resource cost associated with serving such composite transactions may be desired for evaluating capacity of a computing system, but techniques for so determining such resource costs, particularly in a manner that is not compute prohibitive, are lacking in traditional capacity planning systems.

DETAILED DESCRIPTION

Various embodiments of the present invention are now described with reference to the above figures, wherein like reference numerals represent like parts throughout the several views. As described further below, the present invention provides a regression-based system and method for determining resource costs associated with serving composite transactions. As described further below, such resource costs reflect an amount of utilization of at least one resource (e.g., CPU utilization) for serving a corresponding composite transaction.

As described further below, in certain embodiments, a representative workload of a system under analysis (e.g., a service provider's deployed system) is received, which contains at least one composite transaction. The representative workload may, in some embodiments, be data representing an actual historical workload encountered by the system under analysis. Thus, embodiments of the present invention may be employed to analyze a “lived” workload of a deployed system, which may enable more accurate analysis and planning for the system beyond the traditional preliminary system capacity estimates mentioned above. In certain embodiments, the resource costs may be determined for different tiers of a multi-tier architecture. Thus, exemplary embodiments are disclosed that enable a resource cost (e.g., CPU cost) of different client transactions at different tiers to be determined (e.g., approximated). Further, in certain embodiments, the determined resource costs may be further analyzed for performing planning, such as for answering capacity planning questions about the computing system under analysis. Thus, in certain embodiments, the determined cost functions may be used for evaluating the resource requirement of a scaled or modified transaction workload mix in order to accurately size the future system, for example.

FIG. 1shows an exemplary system100according to an embodiment of the present invention. As shown in this example, a representative workload101comprises one or more composite transactions, such as composite transactions102A-102B (referred to collectively herein as composite transactions102). In general, a composite transaction refers to a transaction that comprises a plurality of transactions. For instance, a given transaction for serving a client's request for information (e.g., a web page) may include embedded therein a plurality of requests/responses for objects (e.g., images, etc.) that form the information (e.g., that form the requested web page), and thus the given transaction for serving the information may be considered a composite transaction as it involves various transactions for serving the objects that form such information. A more detailed example of a composite transaction is described further below with reference toFIG. 2.

In the exemplary embodiment ofFIG. 1representative workload101may be an actual historical workload collected for a service provider (referred to herein as a “live workload”), for example. That is, representative workload101may comprise data representing an actual historical workload collected for a system under analysis over a given period of time, say a preceding 3-month period for example. Representative workload101may comprise data stored to a computer-readable medium, such as memory, hard drive, peripheral data storage drive, optical data storage (e.g., CD, DVD, etc.), magnetic data storage, tape storage, etc. Representative workload101may be stored in the form of any suitable data structure, such as to a database, file, table, etc. Again, in certain embodiments, such data may represent an actual historical workload of the service provider's computing system.

The representative workload data101may be collected through well-known application logs and system usage metrics, such as CPU utilization measured at a defined time scale (e.g., 5 minutes or so). As one example, the data collected in access logs generated by Hewlett-Packard's Open View Service Desk (OVSD) application server may be used in forming representative workload101. Other types of access logs, which may be customized for their respective applications, may be used in accordance with embodiments of the present invention. As an illustrative example, such access logs typically collect such data as the following for each transaction: date and a time stamp of the request, session ID, transaction URL, and referrer field. According to one embodiment of the present invention, the timestamp, session ID, and transaction URL fields of the access log are used for the analysis.

System100further comprises a composite transaction resource cost calculator (“CTRCC”)103, which receives representative workload101. Such CTRCC103is operable to analyze the received representative workload101and determine a corresponding resource “cost”105for each of the composite transactions102. In general, the resource cost of a composite transaction reflects an amount of utilization of at least one resource in serving the composite transaction. For example, the resource cost that is computed in certain embodiments is a CPU cost, which is reflective of an amount of CPU utilization attributable to serving the corresponding composite transaction. In certain embodiments, such CPU utilization may be a corresponding amount of CPU utilization of a given tier of multi-tier architecture that is attributable to serving the corresponding composite transaction. In certain embodiments, CTRCC103may periodically receive a representative workload101for a service provider and provide an analysis of resource costs105for the transactions included in such workload101. For instance, workload101may, in some embodiments, be a historical workload encountered by the service provider's system (e.g., over the preceding 3-month period), and CTRCC103may therefore provide an updated analysis over time as the number of clients supported by the service provider and/or the client activities may change over time.

As described further herein, in certain embodiments, CTRCC103employs a regression-based solver104for determining the resource cost105for the composite transactions102. An exemplary statistical regression-based analysis that may be employed by such regression-based solver104is described further below in connection withFIG. 4. In certain embodiments, the representative workload101may comprise certain transactions that are not composite transactions, and CTRCC103may also be operable to determine a resource cost for such non-composite transactions.

CTRCC103and/or regression-based solver104may be implemented as computer-executable software code stored to a computer-readable medium and/or as hardware logic, as examples. Once determined, resource cost105may be stored to a computer-readable medium, such as memory, hard drive, peripheral data storage drive, optical data storage (e.g., CD, DVD, etc.), magnetic data storage, tape storage, etc. The resource cost105may be stored in the form of any suitable data structure, such as to a database, file, table, etc.

In certain embodiments, CTRCC103is implemented as part of a capacity planning tool106. In certain embodiments, such a capacity planning tool106may be operable to further analyze computed resource costs105to provide capacity planning analysis for the system under analysis, such as by answering certain capacity planning questions that the service provider may have, such as discussed further below in connection withFIG. 5. Such capacity planning tool106may be implemented as computer-executable software code stored to a computer-readable medium and/or as hardware logic, as examples.

Turning toFIG. 2, an exemplary client-server system200is shown in which certain embodiments of the present invention may be implemented. As shown, one or more servers201A-201D may provide services (information) to one or more clients, such as clients A-C (labeled204A-204C, respectively), via communication network203. Communication network203is preferably a packet-switched network, and in various implementations may comprise, as examples, the Internet or other Wide Area Network (WAN), an Intranet, Local Area Network (LAN), wireless network, Public (or private) Switched Telephony Network (PSTN), a combination of the above, or any other communications network now known or later developed within the networking arts that permits two or more computers to communicate with each other.

In a preferred embodiment, servers201A-201D comprise web servers that are utilized to serve up web pages to clients A-C via communication network203in a manner as is well known in the art. Accordingly, system200ofFIG. 2illustrates an example of servers201A-201D serving, up web pages, such as web page202, to requesting clients A-C. Of course, embodiments of the present invention are not limited in application to determining resource costs for serving web pages, but may likewise be implemented for determining resource costs for other types of composite transactions. Thus, while various examples are provided herein for determining resource costs for client accesses of web pages, it should be understood that such examples are intended to render the disclosure enabling for determining resource costs associated with various other types of composite transactions.

In the example ofFIG. 2, web page202comprises an HTML (or other mark-up language) file202A (which may be referred to herein as a “main page”), and several embedded objects (e.g., images, etc.), such as Object1, and Object2. Techniques for serving up such web page202to requesting clients A-C are well known in the art, and therefore such techniques are only briefly described herein. In general, a browser, such as browsers205A-205C, may be executing at a client computer, such as clients A-C. To retrieve a desired web page202, the browser issues a series of HTTP requests for all objects of the desired web page. For instance, various client requests and server responses are communicated between client A and server201A in serving web page202to client A, such as requests/responses206A-206F (referred to collectively herein as requests/responses206). Requests/responses206provide a simplified example of the type of interaction typically involved in serving a desired web page202from server201A to client A. As those of skill in the art will appreciate, requests/responses206do not illustrate all interaction that is involved trough TCP/IP communication for serving a web page to a client, but rather provides an illustrative example of the general interaction between client A and server201A in providing web page202to client A.

When a client clicks a hypertext link (or otherwise requests a URL) to retrieve a particular web page, the browser first establishes a TCP connection with the web server by sending a SYN packet (not shown inFIG. 2). If the server is ready to process the request, it accepts the connection by sending back a second SYN packet (not shown inFIG. 2) acknowledging the client's SYN. At this point, the client is ready to send HTTP requests206to retrieve the HTML file202A and all embedded objects (e.g., Object1and Object2), as described below.

First, client A makes an HTTP request206A to server201A for web page202(e.g., via client A's browser205A). Such request may be in response to a user inputting the URL for web page202or in response to a user clicking on a hyperlink to web page202, as examples. Server201A receives the HTTP request206A and sends HTML file202A (e.g., file “index.html”) of web page202to client A via response206B. HTML file202A typically identifies the various objects embedded in web page202, such as Object1and Object2. Accordingly, upon receiving HTML file202A, browser205A requests the identified objects, Object1and Object2, via requests206C and206E. Upon server201A receiving the requests for such objects, it communicates each object individually to client A via responses206D and206F, respectively. As illustrated by the generic example ofFIG. 2, each object of a requested web page is retrieved from a server by an individual HTTP request made by the client. Thus, a given client access of web page202may comprise a plurality of request/response pairs (or “transactions”), and thus such an access of web page202may be referred to herein as a “composite transaction.” For instance an access of web page202is a composite of the request/response pairs for accessing the various objects that make up the web page202.

Again, the above interactions are simplified to illustrate the general nature of requesting a web page, from which it should be recognized that each object of a web page is requested individually by the requesting client and is, in turn, communicated individually from the server to the requesting client. The above requests/responses206may each comprise multiple packets of data. Further, the HTTP requests can, in certain implementations, be sent from a client through one persistent TCP connection with server201A, or, in other implementations, the requests may be sent through multiple concurrent connections. Server201A may also be accessed by other clients, such as clients B and C ofFIG. 2, and various web page objects may be communicated in a similar manner to those clients through packet communication207and208, respectively.

In many instances, a service provider deploys a web service as a multi-tier client-server application. In such instances, a client typically communicates with the web service via a web interface tier, where the unit of activity at the client-side corresponds to a download of a web page generated by the application. As mentioned above a web page is generally composed of an HTML file and several embedded objects such as images. A browser retrieves a web page by issuing a series of HTTP requests for all objects: first it retrieves the main HTML file and then after parsing it, the browser retrieves the embedded images. It is very common that a web server and application server reside on the same hardware, and shared resources are used by the application and web servers to generate web pages as well as to retrieve page-embedded objects. In the access logs from Hewlett-Packard's Open View Service Desk (OVSD) application server, for example, there are both types of entries: web page requests and consequent entries for embedded images.

According to one embodiment, the client web page requests, also called web page views, are of interest in determining resource costs105. Thus, in one embodiment, a web page accessed by the client and generated by the application is considered as a composite transaction, as such web page access includes the various transactions for serving the embedded objects that form such web page.

According to certain embodiments, a service provider collects the server access logs, reflecting processed client requests and client activities at the site. Again, any suitable usage logging applications now known (such as Hewlett-Packard's Open View Service Desk) or later developed, may be used for monitoring the service provider's system and collecting the access logs. According to one embodiment, in the CTRCC103's analysis, it considers a reduced trace that contains only composite transactions (web page views) as discussed above. All the embedded images, style sheets, and other format-related primitives contained in any composite transactions are omitted, as effectively being absorbed into their respective composite transaction. Moreover, in certain embodiments, the CTRCC103further distinguishes a set of unique transaction types and a set of client accesses to them. For static web pages, for example, the URL uniquely defines a file accessed by clients. For dynamic pages, the requests from different users to the same web page URL may appear as requests to different URLs due to the client-specific extension or a corresponding parameter list. Thus, in certain embodiments, the CTRCC103carefully filters out these client-specific extensions in the reduced trace.

In certain embodiments, the above-mentioned filtering of transactions to result in a representative workload that contains composite transactions (eliminating the individual web requests for objects that form a composite transaction) and containing an identification of a corresponding transaction type of each composite transaction, is performed (e.g., by filtering logic) as part of processing access logs for preparing representative workload101to be received by CTRCC103. In this manner, such filtering logic processes the access logs to form the representative workload101in a form that is convenient for transaction analysis and further processing performed by the CTRCC103as described herein. Thus, the representative workload101shown inFIG. 1as being received by CTRCC103may, in certain embodiments, comprise data that has been previously filtered and organized by filtering logic. In other embodiments, such filtering logic may be included as part of CTRCC103, wherein CTRCC103may receive raw data from access logs and perform the above-mentioned filtering and then the processing for determining the resource costs105as described further herein.

FIG. 3shows an exemplary operational flow according to one embodiment of the present invention. In operational block301, CTRCC103receives a representative workload101that comprises at least one composite transaction (e.g., composite transactions102A-102B ofFIG. 1). As mentioned above, the representative workload101may comprise data that represents a representative workload of a computing system under analysis (e.g., represents an actual historical workload of the computing system), and such data may be input in any suitable way to CTRCC103. For instance, CTRCC103may read the data from a data structure (e.g., file, database, table, etc.) that is stored to a computer-readable medium, or the data may otherwise be received by CTRCC103.

In block302, CTRCC103determines, based at least in part on a statistical regression-based analysis (e.g., of regression-based solver104), a resource cost105for the at least one composite transaction. For instance, as described further herein, a statistical regression-based analysis may be employed by regression-based solver104to determine (e.g., estimate) a corresponding resource cost105for each composite transaction included in a received workload101.

An exemplary statistical regression-based analysis that is employed by regression-based solver104according to one embodiment of the present invention is now described with reference toFIG. 4. This exemplary regression-based analysis is described for computing CPU costs of a server for serving web pages, and thus according to this exemplary embodiment, a client web page request is considered as the main, basic unit of client/server activity. However, the exemplary regression-based analysis may likewise be employed for computing CPU (and/or other resource) costs associated with serving other types of composite transactions, and thus is not limited in application to analysis of web page accesses.

As mentioned above, often an application server is also responsible for serving the embedded objects of a page (e.g., embedded images, etc.). Thus, it may be desirable for the capacity planning tool106to evaluate the overall CPU resources consumed by the application server for corresponding transaction processing, e.g., for generating the requested web page and also retrieving and serving all the embedded objects in the above example. In other words, it may be desirable to evaluate the overall CPU resources utilized by a given tier of a multi-tier architecture (e.g., by the application server of a three-tier architecture) in serving a composite transaction.

There are no common tools for effectively measuring the service times for all these objects, while the accurate CPU consumption estimates are required for capacity planning of the systems operating under real workload mix. While one may build such a tool by explicitly instrumenting the application with additional measurements, this would be an application-dependent and obtrusive solution that might lead to significant overhead, and is thus not used in practice. On the other hand, it should be recognized that embodiments of the present invention described herein are not application dependent and do not require modification of the applications for inclusion of additional logic for explicit instrumentation (and thus do not lead to significant overhead in the operation of the applications for determining resource costs).

According to certain embodiments of the present invention, the exemplary method for determining resource costs of composite transactions, which is based on a statistical regression technique, provides an efficient and simple way to accurately approximate the CPU cost (e.g., overall CPU service time) of different composite transactions. This exemplary method has a unique ability to “absorb” some level of uncertainty or noise present in real-world data. Thus, it can be effectively employed for evaluating an actual historical workload of a computing system that is under analysis. As described below, combining the knowledge of critical workload features of a system under analysis with a statistical regression technique provides an elegant and powerful solution for performance evaluation of complex systems with real workloads.

According to this exemplary embodiment, a number of different transactions are observed over fixed-length time intervals, denoted as monitoring windows, in order to capture the changes in user behaviors. Thus, a monitoring window is defined in operational block401ofFIG. 1, and a number of different composite transactions are observed in one of more of such monitoring windows in operational block402. The time length of the monitoring window should preferably be selected intelligently. The monitoring window should not be too small (in order to avoid the representative workload contained therein from being too noisy), and the monitoring window should not be too big (in order to avoid overlooking the variance of user activities). In the experiments described herein, we consider 1 hour as a reasonable window length, but the monitoring window length may be determined to be set to some other time period based on the above-mentioned factors.

The transaction mix and system utilization are recorded at the end of each monitoring window, such as shown in the example of Table 1 below. Thus, for each monitoring window, the transactions observed therein are organized by transaction type in block403, and the resource utilization (e.g., CPU utilization) is recorded for each monitoring window in operational block404. In general, the different transaction types, refer to different activities/functionalities of the application and/or different web pages related to the site and processed by the service provider's hardware under study. The different transaction types are typically present in the application logs. As an example, one type of transaction for a banking application may be a transaction in which a client views his account balance, while a client transferring funds between accounts might be a second transaction type of the banking application.

In the example of Table 1, 5 monitoring windows are shown that are each 1 hour in length. In each monitoring window, the number of transactions of a given type are recorded, wherein one or more of the transaction types may be composite transactions. For instance, in the example of Table 1, there are 756 different types of transactions, and the number of occurrences of each transaction type within each monitoring window is recorded. Also, the CPU utilization of each monitoring window is recorded. For instance, the CPU of the system under analysis was utilized 13.3201% of the 1-hour period of time of the first monitoring window shown in Table 1.

As an exemplary application of this representative embodiment, let us assume that there are a total of M transaction types processed by the server (or other computing system) under analysis. Let us use the following denotations.T is the length of the monitoring window;Niis the number of transactions of the i-th type, where 1≦i≦M;UCPU,nis the average CPU utilization during this monitoring window at the n-th tier of an application;Di,nis the average service time of transactions of the i-th type at the n-th tier, where 1≦i≦M; andD0,nis the average CPU overhead related to “keeping the system up” activities at the n-th tier. For example, there are generally some OS processes and/or background jobs that consume CPU time even when there is no transaction to be serviced in the system. Thus, D0can be defined to represent such overhead that is typically present in the system under analysis.

From the utilization law, Equation (1) below can be obtained for each of the monitoring windows:

It is practically infeasible to get accurate service times Di,nbecause this is an overconstrained problem. That is, the exact solution (accurate service times) is feasible for M number of equations with M unknowns (variables). In the above analysis, on the other hand, there are N number of equations where N>K, and is thus an overconstrained problem, wherein it becomes desirable to find an approximate solution that leads to a small error. Since it is practically infeasible to get accurate service times Di,n, we let Ci,ndenote the approximated CPU cost of Di,nfor 1≦i≦M. Then an approximated utilization U′CPU,ncan be calculated as

A statistical regression-based analysis may be employed to solve for Ci,n. Thus, in operational block405ofFIG. 4, a regression-based analysis is used to approximate Ci,nto determine the average CPU cost of transactions of the i-th type for each monitoring window. According to certain embodiments, to solve for Ci,n, one can choose a regression method from a variety of known methods in the literature, such as the regression methods described in “Algorithms” by R. Sedgewick, Addison-Wesley Publishing Company, Second Edition (see e.g. description beginning at page 551 thereof), the disclosure of which is hereby incorporated herein by reference. A typical objective for a regression method is to minimize either the absolute error:

∑j⁢UCPU,n′-UCPU,nj
or the squared error:

∑j⁢(UCPU,n′-UCPU,n)j2,
where j is the index of the monitoring window over time.

Finding the best fitting method is outside the scope of this disclosure, and is not described in great detail so as not to unnecessarily detract attention away from the invention. Although, as one example, in some of our experiments we use the Non-negative Least Squares Regression (Non-negative LSQ) provided by MATLAB to get Ci,n. This non-negative LSQ regression is to minimize the error

e=∑j⁢(UCPU,n′-UCPU,n)j2
such that Ci,n≧0.

The exemplary statistical regression-based analysis proposed above works very well for estimating the CPU demands of composite transactions that themselves might represent a collection of smaller objects, whereas direct measurement methods (e.g., explicitly instrumenting the application under analysis with additional measurements) are not practical, as discussed above.

While the above description has concentrated on evaluating the CPU capacity required for support of a given workload, application of the concepts described herein are not limited to determining such CPU costs. Rather, the regression-based analysis methods described herein may likewise be efficiently applied for evaluating other shared system resources that have an “additive” capacity nature. As one example, embodiments of the present invention may be applied for estimating the latency of the different links on the network path when end-to-end measurements are given but the link's delay of the path is unknown. As another example, the above-described embodiments may be employed for evaluating transactions' memory usage estimates.

In certain embodiments, the above-mentioned technique may be optimized for efficiency by determining a set of “core” transactions present in a representative workload for which the above-described regression-based analysis is performed to determine resource costs associated therewith, such as described further in co-pending and commonly assigned U.S. patent application Ser. No. 11/684,567 entitled “SYSTEM AND METHOD FOR DETERMINING A SUBSET OF TRANSACTIONS OF A COMPUTING SYSTEM FOR USE IN DETERMINING RESOURCE COSTS”, the disclosure of which is incorporated herein by reference.

In certain embodiments, once the resource cost105for composite transactions is determined, such resource cost may be used for further analysis, such as for answering capacity planning questions about a system under analysis. For instance,FIG. 5shows an exemplary system500which may be employed for using determined resource costs105. As with system100ofFIG. 1, system500includes CTRCC103having regression-based solver104for receiving representative workload101and determining resource costs105for composite transactions in the manner described above. In this example, capacity planning tool106may further comprise capacity planning analyzer501, which may receive the determined resource costs105and further analyze the capacity of the system under analysis. For instance, in certain embodiments, capacity planning analyzer501may also receive input (e.g., from a user) indicating QoS desires502. Such QoS desires502may specify, for example, a target QoS that is desired to be provided by the service provider, such as serving web pages to clients with response times no longer than 8 seconds. Capacity planning analyzer501may also receive certain planning parameters503, which may specify a desired modification to the workload of the service provider. For instance, planning parameter503may specify an additional number of clients desired to be supported by the service provider. In this manner, the capacity planning analyzer501may analyze the received resource costs105determined for the representative workload101to answer such capacity planning questions that a service provider may have as:how many additional clients can be supported by the existing system i) while still providing the same performance guarantees (QoS desires502), e.g., response time under 8 seconds, and ii) assuming that new clients perform similar activities as already existing clients in the system, i.e., the system processes the same type of workload?does the existing system have enough available capacity for processing an additional service for N number of clients (defined by planning parameters503) where the client activities and behaviors are specified as a well-defined subset of the current system activities?if the current client population doubles, then what is the expected system response time?

The answers to such questions and/or other capacity planning information may be determined by capacity planning analyzer501and output as capacity planning analysis504. Thus, the determined resource costs105may be used to perform further analysis, such as for analyzing the capacity of the computing system under analysis by capacity planning analyzer501, such as described further in co-pending and commonly assigned U.S. patent application Ser. No. 11/684,569 titled “SYSTEM AND METHOD FOR CAPACITY PLANNING FOR COMPUTING SYSTEMS”, the disclosure of which is incorporated herein by reference.

When implemented via computer-executable instructions, various elements of embodiments of the present invention are in essence the software code defining the operations of such various elements. The executable instructions or software code may be obtained from a readable medium (e.g., a hard drive media, optical media, EPROM, EEPROM, tape media, cartridge media, flash memory, ROM, memory stick, and/or the like) or communicated via a data signal from a communication medium (e.g., the Internet). In fact, readable media can include any medium that can store or transfer information.

FIG. 6illustrates an exemplary computer system600on which the CTRCC103(and/or capacity planning tool106) may be implemented according to one embodiment of the present invention. Central processing unit (CPU)601is coupled to system bus602. CPU601may be any general-purpose CPU. The present invention is not restricted by the architecture of CPU601(or other components of exemplary system600) as long as CPU601(and other components of system600) supports the inventive operations as described herein. CPU601may execute the various logical instructions according to embodiments of the present invention. For example, CPU601may execute machine-level instructions according to the exemplary operational flows described above in conjunction withFIGS. 3 and 4.

Computer system600also preferably includes random access memory (RAM)603, which may be SRAM, DRAM, SDRAM, or the like. Computer system600preferably includes read-only memory (ROM)604which may be PROM, EPROM, EEPROM, or the like. RAM603and ROM604hold user and system data and programs, as is well known in the art.

Computer system600also preferably includes input output (I/O) adapter605, communications adapter611, user interface adapter608, and display adapter609. I/O adapter605, user interface adapter608, and/or communications adapter611may, in certain embodiments, enable a user to interact with computer system600in order to input information, such as QoS desires502and/or planning parameters503of a service provider.

I/O adapter605preferably connects to storage device(s)606, such as one or more of hard drive, compact disc (CD) drive, floppy disk drive, tape drive, etc. to computer system600. The storage devices may be utilized when RAM603is insufficient for the memory requirements associated with storing data for operations of the CTRCC103(e.g., representative workload101and/or values of the variables computed according the exemplary embodiment described in connection withFIG. 4). Communications adapter611is preferably adapted to couple computer system600to network612, which may enable information to be input to and/or output from system600via such network612(e.g., the Internet or other wide-area network, a local-area network, a public or private switched telephony network, a wireless network, any combination of the foregoing). For instance, a representative workload101may be input to system600via network612from a remote computer (e.g., from the computing system under analysis), and/or a determined resource cost105may be output and communicated via network612to a remote computer. User interface adapter608couples user input devices, such as keyboard613, pointing device607, and microphone614and/or output devices, such as speaker(s)615to computer system600. Display adapter609is driven by CPU601to control the display on display device610to, for example, display information regarding the determined resource cost105and/or capacity planning analysis504according to certain embodiments of the present invention.

It shall be appreciated that the present invention is not limited to the architecture of system600. For example, any suitable processor-based device may be utilized for implementing CTRCC103, including without limitation personal computers, laptop computers, computer workstations, and multi-processor servers. Moreover, embodiments of the present invention may be implemented on application specific integrated circuits (ASICs) or very large scale integrated (VLSI) circuits. In fact, persons of ordinary skill in the art may utilize any number of suitable structures capable of executing logical operations according to the embodiments of the present invention.