Resource allocation for multiple applications

[0001] The present disclosure generally relates to the allocation of resources to various applications.

[0002] Large data centers are often used to provide computing services to a number of organizations who may have varied computing requirements. A data center generally includes a collection of server-class data processing systems (“servers”) that are configured and networked to accommodate various application needs. Service Level Agreements (SLAs) define the level of computing capacity that the data center is expected to provide to an application. The SLA may address storage requirements, transaction throughput, availability and many other variables.

[0003] A data center allows multiple applications to be hosted on a collection of shared computing resources based on the resource needs of the applications. The resources may be configured for sharing while protecting each resource domain against unauthorized access from another domain. The resources may be configured based on applications' resource needs and the architecture of each application. For example, a common architecture for a web service system is a tiered structure including a first tier of web servers, a second tier of application servers, and a third tier of database servers. Within each tier multiple machines may be provisioned to share the incoming workload.

[0004] The success of a data center may be judged not only by the level of service provided to the customer organizations, but also by the level of efficiency with which the data center is able to meet customer demands. It may be desirable for a data center to assemble the amount of resources required by the SLAs, plus some reserve capacity to allow for temporary needs for additional resources or to allow for some small amount of growth. However, the amount of resources required by a customer for some periods of time may be less than the amount specified in the SLA, which may imply that the data center has idle resources for these periods. A data center having too many idle resources may be unprofitable or unable to compete with other data centers with respect to cost of services. The present invention may address various issues related to effectively managing the resources of a data center.

[0005] The disclosure describes various methods and apparatus for allocating resources to a plurality of applications. In various embodiments instrumentation data may be gathered for work requests processed by the applications. An associated workload level may be determined for work requests processed by the applications. For each application an application resource requirement may be determined as a function of the workload levels and a service level metric associated with the application. For each application an assigned subset of resources may be determined as a function of the application resource requirement, a minimization of communication delays between resources, and a bandwidth capacity requirement of the application. The resources may be automatically reconfigured consistent with the assigned subset of resources for each application.

[0006] It will be appreciated that various other embodiments are set forth in the Detailed Description and claims which follow.

[0013] FIG. 1 is a functional block diagram that illustrates at a high level the resources of a data center 102 in relation to clients 104, 106, and 108 that access applications hosted by the data center. A data center may have thousands of servers that are distributed in different geographical regions and that collectively run hundreds of different applications, even though data center 102 is illustrated as a block with a collection of servers.

[0014] The servers of a data center may provide computational, storage, communications, or other basic services depending on application needs and data center priorities. Servers may be shared or dedicated to applications depending on resource requirements. For example, server 112 may be shared by multiple applications 114, while server 116 may be dedicated to a single application 118.

[0015] Clients access the applications via a network such as the Internet 120. Certain clients may have access to selected applications depending on application requirements. A client may be a web browser responding to user input, an application that is processing a distributed web service request that requires access to an application hosted in the data center or generally another other type of program seeking access to an application in the data center.

[0016] As the needs of applications change, the resources or the data center may be reconfigured to provide the needed level of service to the applications using the minimum amount of hardware resources deemed desirable. Depending on application requirements, applications may be reassigned to share certain servers, servers may be added to the data center, or certain servers may be dedicated to certain applications.

[0017] FIG. 2 is a flow chart of an example process that supports planning for needed capacity of a data center and automatically assigning resources in accordance with various embodiments of the invention. The various embodiments of the invention may be applied to different types of application architectures as deployed on various configurations of servers in a data center. However, for purposes of explanation, the processing of web transactions from browsers to web servers to any additional backend application servers is used to illustrate operations of the various embodiments.

[0018] As part of an ongoing effort to see that application requirements are being satisfied by a data center and that the data center is allocating resources efficiently, various transaction data is collected (step 202). This transaction or instrumentation data may include data that identify transactions, classify transactions, identify requesters, and quantify responsiveness of various components involved in processing the transaction. Data collected at various components involved in processing the transactions may be correlated by transactions as further explained below.

[0019] For performance characterization, the instrumentation data gathered in processing web transactions may be classified according to user and transaction (steps 204 and 206). In classifying users, the subset of the user population from which a Web transaction originates is identified. For example, users may be classified as human or robots. Another class of users may be made based on purchasing behavior. For example, humans who make frequent purchases versus humans whose purchases are infrequent.

[0020] Various techniques are known for classifying users. In an example application of one technique, the inter-arrival times in long sessions are analyzed to identify transactions that appear as though they originated from a shopping robot, as well as some which may have originated from multiple human users connected through a proxy server. Various methods may be employed to classify users as explained in the following paragraphs.

[0021] The inter-arrival times of requests generated by a typical robot have different characteristics from those generated by a human. A robot that explores a site systematically to catalog its pages will generate in quick succession many requests, numbering in the tens or hundreds. In contrast, a human will typically generate only a small number of requests, usually fewer than ten, that are further spaced-out because of the time to read the returned page.

[0022] Another method of classifying users employs the IP address of the client (the originator of the request). Robots of the common search engines (Google, Yahoo, etc.) have readily identifiable IP addresses.

[0023] A third method of classifying users employs the “agent string” of the HTTP request. For example, a group of multiple human users connected through a common proxy server (like WebTV) will appear to have the IP address of the proxy and will generate long sessions, and thus might be mistaken for a robot. By looking at the agent string, for example, “Mozilla/3.0 WebTV/1.2 (compatible; MSIE 2.0)”, one may correctly classify the session as arising from the WebTV proxy.

[0024] Preliminary classifications may be confirmed by the agent strings appearing in those sessions. The ability to predict the characteristics of an incoming session may be used in load balancing of web and application servers.

[0025] In transaction classification, a given URI is mapped into a transaction class. For example, a URI www. shop. com/estore/browse?item=1 may be classified as a browse transaction, and a URI www. shop. com/estore/purchase?product=2 may be classified as a purchase transaction. In an example embodiment, a URI may belong to only one class. When a transaction belonging to a particular transaction class is detected, the process increases the count for that class of transaction. It will be appreciated that a timestamp may also be recorded in association with the transaction class for each transaction so that the volume of transactions of a particular class may be determined over a selected interval of time.

[0026] It will be appreciated that collecting and classifying the instrumentation data may continue to run in the background as the other steps (208, 210, 212, 214) for allocating resources are performed.

[0027] Based on the user classifications, workload mix, and workload levels the load balancing policies may be adjusted (step 208). In the context of web transactions, workload refers to transactions. In a data center having web servers and application servers, the policy of one load balancer may be adjusted to better distribute the workload between the various web servers. This may involve, for example, routing human-generated requests in a different way from routing of robot-generated requests. Similarly, traffic with resource-intensive requirements may be routed different from traffic with light resource requirements.

[0028] An example objective of a load distribution policy is to minimize some criterion such as the mean response time of a request and minimize the number of application servers allocated for a given SLA. There are several known load distribution policies. For example, the load may be distributed based on a round-robin, random, least-work-remaining or size-based policy. In an example embodiment, sessions are considered in load balancing. A session is a sequence of related Web requests. In the example policy, the assignment for routing is performed once per session. To implement a minimizing-variance aspect of the size-based policy, at the initial Web request of a session an estimation of the size of subsequent requests is made. Sessions comprising mostly small requests may be assigned to different servers from those comprising mostly large requests.

[0029] The benefits of a sophisticated distribution policy based on user and URI classification may be sufficient to merit reassigning a session after the request in the session have been observed over some period of time. This may provide a more accurate estimate of the sizes of subsequent requests in the session. For example, if shortly into a session it is determined that the session is driven by a robot that will issue one type of request a large number of times, it might be worthwhile to reassign the session to a server dedicated to those types of requests.

[0030] In addition to adjusting load balancing policies, the instrumentation data may also be used in estimating and optimizing server requirements (step 210). In one embodiment, a queuing model is used to approximate the average response time for a given number of servers at each tier, and an optimization process determines the minimum number of total servers required for the application average response time to be within the range of a specific SLA. It will be appreciated, however, that other models and or techniques may be used to perform the estimation. These models and techniques include simulation and closed-loop control based on actual measurements. The simulation method achieves the same purpose for estimating the average response time by mimicking the system operation in software codes; while closed-loop control measures the actual average response time and then compares to the range of response time specified in the SLA. If the actual measured response time is longer than that specified in the SLA, servers (resources) are added; otherwise if measured is shorter than specified, servers (resources) are taken away. The example queuing model has advantages over the simulation and the control techniques in that it achieves computationally fast predictions of resources required to fulfill the SLA and is amenable for easy automation.

[0031] In the queueing model, the problem is to determine the probability distribution function of the response time to a request given: (1) the numbers of servers at the backend tiers, N_web, N_app, and N_DB (the backend tiers including web servers, applications servers, and database servers) where N_web, N_app, and N_DB are number of web servers, applications servers, and database servers respectively; and (2) the mix and volume of the incoming requests (λ₁, λ₂, . . . ). That is, a function ƒ(.) is sought such that Pr(R≦r)=ƒ(r|N_web, N_app, N_DB, λ₁, λ₂, . . . ), where R is the random variable response time (or system residence time) of a request, r is any arbitrary level such as 0.1 second or 2 seconds.

[0032] The system may be modeled in the aggregate, with a simplified representation of the routing of requests through the system. Specifically, the system may be modeled as an open queueing network, with three tiers arranged in series, and parallel, identical servers within each tier. With this assumption, the multiple-pass processing of returned requests is aggregated into a one-pass simplified flow (from web server to an application server to a database server to exiting the system). Furthermore, each server is represented as a processor-sharing queue with one critical resource (e.g., a CPU or disk). The service demand of a request at a server is the sum of processing times of the multiple passes of this request at the server.

[0033] The expected response time may be described as the sum of response times at each of the three tiers:

[0034] $\begin{array}{c}E\left[R\right]=\frac{E\left[S_{\mathrm{web}}\right]}{1-{\lambda }_{\mathrm{web}}E\left[S_{\mathrm{web}}\right]/N_{\mathrm{web}}}+\frac{E\left[S_{\mathrm{App}}\right]}{1-{\lambda }_{\mathrm{App}}E\left[S_{\mathrm{App}}\right]/N_{\mathrm{App}}}+\\ \frac{E\left[S_{\mathrm{DB}}\right]}{1-{\lambda }_{\mathrm{DB}}E\left[S_{\mathrm{DB}}\right]/N_{\mathrm{DB}}}\end{array}$
where λ_web is the arrival rate of new requests into the web server tier, which is the sum of all customer request types that require processing at the web server tier; E[S_web] is the average service demand at the web server tier averaged over all request types and including multiple passes of processing; and N_web is the number of servers at the web server tier. Similar notation applies to the application and database server tiers.

[0035] The formula above assumes a processor-sharing queue at each server. It is also assumed that the servers within each tier are identical and share approximately the same workload, which implies that the arrival rate at each server is λ_web/N_web.

[0036] It is possible that only a fraction of all customer requests require routing into the application or database server tiers. In this situation it may generally be the case that λ_DB≦λ_app≦λ_web. These arrival rate parameters may be determined from the input workload mix and volume (λ₁, λ₂, . . . ).

[0037] To obtain an estimation of the service demand at the web server tier E[S_web], the relationship u_web=λ_web E[S_web]/N_web, where u_web is the average utilization rate of the critical resource (e.g., CPU) at the web server tier, to write E[S_web]=u_webN_web/λ_web.

[0038] The average queuing time of the multi-tiered system then becomes the response time of the tiered system (after possibly adding to it some fixed “overhead” delays at non-bottleneck resources such as the fixed processing time at the load balancer). A mathematical optimization model is next formulated to find the optimal number of servers at each of the tiers. The mathematical optimization model is described as follows.

[0039] The decision variables on which optimization is performed is the number of servers at each tier in the multi-tiered system. The objective function is the weighted sum of the number of servers at each tier, where the weights are the “costs” per server. A special case is when all weights are equal to 1, signaling that all servers at different tiers are equal, in which case the objective function is simply the total number of systems in the multi-tiered system.

[0040] The optimization model has one constraint: E[R]≦SLA_R, where SLA_R is the response time limit (such as 1 second) required by the SLA. Additionally, the number of servers at each tier is constrained to be an integer greater than or equal to one.

[0041] The resulting mathematical optimization model has a linear objective function but a non-linear, inequality-type constraint with integer-valued decision variables. A concavity property of the average response E[R] function is used with respect to the decision variables in formulating an efficient bounding procedure. The bounding procedure first ignores the integer-value requirements on the decision variables and solves the 2-tiered problem. The solution is then rounded to integer values. Then the 3-tiered problem is solved using the solution to the 2-tiered problem, and recursively to the general n-tiered problem.

[0042] Once the server requirements have been estimated and optimized, in one embodiment an assignment of applications to servers may be determined as a function of the optimal server requirements predicted in such a way communications delays are minimized and bandwidth capacity constraints are satisfied (step 212). The bandwidth capacity constraints are the actual bandwidth of the physical resources in the data center, for example. In one embodiment the physical topology of the resources is represented as a hierarchical tree, and for a given application with a tiered architecture and the estimated and optimized resource requirements of the application, the approach determines how to assign servers from the topology into the tier architecture in such a way that application resource requirements are satisfied and network latency is minimized. In one embodiment the servers may be assigned to the applications considering one application at a time. The discussion that accompanies FIG. 5 further explains various example embodiments for allocating resources for a specific example physical topology, and FIG. 6 is a flowchart of an example process for determining the allocation.

[0043] Once a solution has been arrived at for assigning the servers to the different tiers of the application, the solution may be implemented by reconfiguring the servers accordingly (step 214). The reconfiguration tasks may include removing and installing application software, changing registry settings, editing of configuration files, and running a command to start the application software. The various scripts and sequences of operations needed for reconfiguration will vary according to the type of server and characteristics of the application software. However, it will be appreciated that such scripts may use the information from the solution as input to automatically reconfigure the appropriate servers.

[0044] The adjusting load balancing policies, determining an allocation of resources, and automatically reconfiguring may be repeated as often as deemed necessary to achieve desired levels of performance and efficiency. Gathering of instrumentation data may continue to run in the background so that the necessary data is available for analysis when desired.

[0045] FIG. 3 is a functional block diagram of an example arrangement for gathering data to be used in analyzing resource requirements and allocations for applications hosted by a data center. The example data center resources are configured in support of a tiered architecture for processing web transactions. It will be appreciated, however, that the invention may be adapted and applied to other architectures and arrangements of data center resources. Generally, a web transaction begins at a client, for example a browser or Internet access device, or as web service (block 302). The web transaction flows through the Internet 304 to a load balancer 306.

[0046] The load balancer 306 may be a resource of the data center and may be the first tier of the web transaction processing architecture. The load balancer submits the web transaction to one of the servers in web server farm 308, which is the second tier. The load balancer may be configured to distribute the work amongst the servers 308 in any of a number of techniques suitable for the data center and application requirements. For example, the load balancer distribute transactions in a manner that minimizes response time and maximizes resource utilization.

[0047] The web servers 308 may each have an associated load balancer. For example, web server 310 has an associated load balancer 312. Each web server load balancer balances the workload between the servers in the application server farm 314, which is the third tier. The application servers 314 host the application logic that processes web transactions. For example, the application logic may read from or write to database 316 in processing the transaction.

[0048] File system 318 may be used to store the web pages that are served to the user, and also store the configuration information for the web and application servers. So, when processing a transaction, the application logic will read information from the file system. When an application server or a web server starts execution, it obtains its configuration information from the file system.

[0049] Collector 332 gathers instrumentation data pertaining to web transactions as the transactions are processed by each component from block 302 to database 316. Example data include the beginning and ending times of web page requests. The collector also correlates the instrumentation data by web transaction. The dashed lines indicate that the instrumentation data is coming from a particular point in the transaction flow to the collector.

[0050] Analyzer-optimizer block 342 generally analyzes the correlated instrumentation data, determines a desired configuration, and initiates reconfiguration of the load balancer 306, servers and load balancers in the web server farm 308, and servers in application server farm 314 as may be desirable. In an example embodiment, the analyzer-optimizer uses a queueing model to estimate and optimize server requirements of the applications based on mix of transaction types, the volume of the different transaction types, and a level of service that the data center is expected to provide. A mixed-integer programming technique may be used to allocate the resources of the data center from the optimized server requirements.

[0051] FIG. 4 illustrates a sensor arrangement used to provide instrumentation data to the collector. Sensors are typically shared libraries or script components that intercept the actual processing of a transaction request. Each sensor is logically composed of two parts: a start part and an end part. For example, the sensor of browser 402 includes start part 404 and the corresponding end part 406. The start part performs the correlation aspects of the monitoring, and the end part forwards monitored data to collector 332 via measurement server 408.

[0052] The measurement server 408 acts as a surrogate web server to get measurement information from the browser. This is because the web browser is typically not allowed to pass any information to a server like a collector directly.

[0053] Because a web transaction flows through various heterogeneous components, for example browser 402, web server 410, and application server 412, the sensors may be implemented differently for the components. The solid directional lines between components 402, 410, and 412 illustrate the flow of a web transaction, and the dashed directional lines represent instrumentation data that is provided to the collector 332 from the sensors.

[0054] In an example embodiment, a browser sensor may be implemented using JavaScript code that is sent with each instrumented page. The instrumented page instructs the browser to inject the start and end parts of a sensor as the event handlers for selected events for the browser. The start part of the browser sensor generates a request identifier and passes the identifier along with the request to the web server. The end part of the browser sensor sends performance data to the collector 332 via measurement server 408.

[0055] The start part 422 of a web server sensor extracts the identifier from the web transaction and passes the identifier to the application server. The end part 424 of the web server sensor sends performance data and the web transaction to the collector.

[0056] The start part 426 and end part 428 of the application server sensor processes the transaction and sends instrumentation data to the collector 332. The start part and end part are only performing the measurement functions. The actual functionality of the transaction is carried out by the application server itself. The collector correlates the instrumentation data received by the individual components on the basis of the unique identifier associated with each transaction. The following paragraphs describe in more detail various embodiments of the sensors.

[0057] A web browser may be instrumented indirectly by instrumenting the web pages sent to the browser using JavaScript functions. A sensor start function is invoked when a new page is requested, and a sensor end function is invoked after the new page has been loaded. The sensors may be invoked via event handlers that fire when the user selects a URL to follow and when a particular page has finished loading.

[0058] The sensor start function records the time of the event and the current page of the click cookie. In addition to informing the server of the transaction identifier, the click cookie serves a further purpose. After the new page has been loaded and the sensor end function records the end time and uses the click cookie to obtain the transaction identifier (the transaction's start time) and the referrer URL of the transaction. The referrer URL is used as a heuristic to identify the stale click cookies. The instrumentation may be sent to the measurement server using a .wmi request.

[0059] In order to determine the response time of a transaction, excluding the latency imposed by the Internet, the web server is instrumented. The web server's response in combination with the client's response time supports distinguishing between configuration issues of the web site and issues introduced by the Internet.

[0060] The web server sensor may send the instrumentation data to the collector using UDP packets, for example. Different web servers may require different code to implement sensors because of a non-standardized scripting environments in the web servers. For example, different scripts may be employed for Apache web servers, Internet Information servers, and Netscape web servers.

[0061] In an example embodiment, the sensors for application servers are implemented by instrumenting the application pages. The following paragraphs describe instrumentation of Server Side Javascript, Active Server Pages, Java Server Pages, and Servelets.

[0062] Server Side Javascript (SSJS) was developed by Netscape for dynamically generating HTML pages. SSJS is a mixture of HTML and JavaScript, wherein one or more JavaScript fragments are enclosed in a special tag and are processed by the web application server. The fragments are processed in the order in which they appear on the page, potentially creating text that his included in the resulting HTML page.

[0063] SSJS fragments may communicate with other parts of the application hosted by the application server through the use of pre-defined objects. Some of these objects may be provided by the application server and others may be user defined. The mechanism by which user-defined objects are created is platform specific.

[0064] In an example embodiment, two SSJS fragments are included in each page: one at the top of the page and another at the bottom of the page. The top fragment is processed as soon as the page is loaded by the application server, and the bottom fragment is processed after the rest of the page is processed.

[0065] A user-defined object is created to record the start time of the beginning of the transaction. The setClickCookie method is used to pass the click cookie in the HTTP request to the object. This cookie is used to extract the identifier of the transaction of which this event is a part. The nextClickCookie is used to determine the value of the click cookie to be sent back to the client. After the client's request is processed, the reportEnd method sets the end time of the event and sends the instrumentation data to the collector.

[0066] Active Server Pages (ASPs) implement the server-side scripting technology that is used on Internet Information Servers (IISs). ASPs are nearly syntactically identical to SSJS pages, with ASPs accepting Visual Basic as the scripting language. In addition, user-defined objects must be implemented using the Common Object Model (COM). ASP pages may be instrumented using a user-defined COM object along with JavaScript fragments at the top and bottom of each page.

[0067] The foregoing techniques may be similarly adapted to instrument Java Server pages.

[0068] A Java servlet may be instrumented by modifying the web.xml configuration file, which describes the Servlet and specifies its main class that must implement to the HttpServlet interface. The main class may be replaced with a wrapper class that implements the HttpServlet and forwards all requests to the original main class whose name is specified via an additional initialization parameter.

[0069] The following paragraphs describe how the instrumentation data gathered from the various components involved in a web transaction may be correlated in encountering a variety of instrumentation scenarios. The following example definitions may be useful. A web transaction is a request by a user that starts at a browser by the user clicking on or typing a URI, that is transmitted via the Internet to a web server, and that may be processed by one or more back-end application servers. A requested page is the HTML page that is the object of a web transaction. A referrer page is the HTML page, if any, in which the user clicked to obtain the requested page.

[0070] In the example embodiment, the correlation technique takes into account that instrumentation may not be in place at all times. For example, the referrer page may not always be instrumented, the requested page may not always be instrumented, and the web servers or other back-end servers may not always be instrumented. Instrumentation may not be operative to address demands for low overhead in processing web transactions.

[0071] First described is a scenario in which all components are instrumented, followed by a description of a scenario in which one or more components are not instrumented. A configuration involving only one web browser and one web server is used, and the correlation may be extrapolated to various configurations that include application servers.

[0072] Two cookies are used to transmit information among the various components in a web transaction. The click cookie transmits the referrer page and the time at which the user clicked on the link in the referrer page. The load cookie transmits the time at which the requested page was loaded in the client's browser.

[0073] In an example scenario, a user is browsing through an instrumented page, A. Page A is instrumented such that whenever the user clicks on a URI, a JavaScript function records A:t1 (t1 is a timestamp) in the click cookie. Thus, when the user clicks on the URI for a page B, an appropriate click cookie is generated. The HTTP request is then sent to the web server. Because the web server is also instrumented, it records the timestamps before (t2) and after (t3) the processing of the request and sends these times to the collector 332 along with the start time t1 from the click cookie, which is used as the transaction identifier. The web server then sends its response back to the browser.

[0074] After the browser receives the requested page, it timestamps the end of the lading phase by noting the end time (t4) in a load cookie. Because this page is instrumented, a spurious requested is added at the end of the page, after setting the load cookie, for a .wmi page. The instrumented web server understands that the .wmi request is a spurious request that is only for the purpose of instrumentation. The web server takes the client's start and stop times, t1 and t4, from the click and load cookies, respectively, and sends the times to the collector 332. The collector is able to correlate these times with those of the web server because it uses t1 as the identifier for the transaction.

[0075] The following paragraphs explain scenarios in which various components are not instrumented. If the referrer page is not instrumented, then the click cookie will not be set. The web server will report its data to the collector using its own start time as the transaction identifier. When the requested page is loaded, the web server will recognize that the click cookie is not set and so will not send a .wmi request. Therefore, no client-side instrumentation data will be obtained for the request.

[0076] If the web server is not instrumented, then no server instrumentation data will be obtained. Client instrumentation data will be gathered and reported to the measurement server in the form of .wmi requests, which will store the client perceived performance and pass the data on to the collector. The measurement server gets the client's instrumentation data so it can compute statistical properties for the client-perceived response times.

[0077] If the requested page is not instrumented, then no instrumentation data will be obtained from the client. The web server will record its beginning and ending processing times and transmit these values to the collector. The web server start time is used as the transaction identifier instead of the client start time.

[0078] If the referrer page is instrumented, the requested page is not instrumented, but a subsequent requested page is instrumented, then the above-described click cookie approach may fail. The click cookie approach may fail because the cookie will incorrectly monitor the start time of the click for the first page as the start time of the second page. To avoid this problem, the referrer:timestamp is used in the click cookie. This allows the load function to check whether the click cookie is stale by comparing the referrer value in the cookie with its own record of the referrer through the history object.

[0079] The collector 332 may be implemented as a server that receives via UDP the data generated by the instrumentation sensors. A basic task may be to correlate the data received by the applications servers' sensors. This may be necessary because the sensors send the instrumentation data in an unprocessed form, and thereby providing some instrumentation data for the current request and some instrumentation data for the previous request. The correlated data may be written to a log file or stored in a relational database, for example.

[0080] In an example embodiment, datagram packets are used to communicate instrumentation data from the sensors to the correlator. The data may be formatted using a keyword:value format, where the keyword identifies the instrumentation data and the value is the actual instrumentation data. The information may include, for example, a request identifier, an identifier of a previous transaction, a name of the requested web page, the name of the referrer web page, the location of the client, the start time of the client, the end time of the client, the location of the web server that processed the request, the start time of the web server, the end time of the web server, the location of the application server that processed the request, the start time of the application server, the end time of the application server, the load cookie sent by the client, and the click cookie sent by the client.

[0081] FIG. 5 is a graph that illustrates a physical topology of a small example set of servers, rack switches, edge switches, and a main switch. The graph is used in to illustrate the application of the various embodiments of the process of determining an allocation of resources for a given set of applications. In one embodiment the layout of the physical topology is a hierarchical tree. The root 502 of the tree represents a mesh switch, and there are two edge switches connected to the mesh switch, as represented by nodes labeled E1 and E2. There are four rack switches represented as nodes R1, R2, R3, and R4 in the graph. Rack switches R1 and R2 are connected to edge switch E1, and rack switches R3 and R4 are connected to edge switch E2. There are 12 servers in the topology, with three connected to each rack switch. The servers are represented as nodes labeled S1 . . . S12.

[0082] Each node other than the mesh node has an associated set of attributes. For example, each of the servers has attributes for CPU speed, memory size, and storage capacity (labeled a1, a2, and a3), along with incoming and outgoing bandwidth capacities (labeled BSI and BSO). Each of the rack switches has an associated pair of incoming and outgoing bandwidth capacities (labeled BRI and BRO), and do each of the edge switches (labeled BEI and BEO). The problem is to identify which servers S1 . . . S12 in the physical topology to allocate to the application architecture in such a way that latency in communications delay between servers is minimized, while bandwidth capacity constraints and Min/Max server attribute requirements are satisfied. The complexity of the problem may be recognized where a data center comprises thousands of geographically dispersed servers hosting hundreds of different applications.

[0083] FIG. 6 is a flowchart of an example process for determining an assignment of resources in a physical topology to an application architecture in accordance with various embodiments of the invention. The first step in the process is to generate an initial, approximate solution (step 602). In the example embodiment, a mixed integer programming model is used to generate the initial solution. The model attempts to minimize the weighted number of rack switches and edge switches in the initial solution. The initial solution may not satisfy all bandwidth capacity constraints.

[0084] Using the initial solution as a starting point, a feasible approximate solution is generated using a non-linear programming model (step 602). Specifically, a quadratic programming approximation (QP) of the original problem is used while relaxing the number of feasible servers at a rack switch required to satisfy application requirements.

[0085] Using the feasible approximate solution as a starting point, the final solution is generated using another mixed integer programming model (step 606). This second mixed integer model intelligently rounds the approximate, feasible solution from the QP model and determines the actual servers to assign to the applications. Steps 602, 604, and 606 are further described in the following paragraphs.

[0086] The mathematical formulation may be based on the following assumptions.

• • [0087] 1. The physical topology is a hierarchical tree.
  • [0088] 2. The application has a tiered architecture.
  • [0089] 3. Servers at the same tier have the same functionality. Consequently, they have the same attribute requirements.
  • [0090] 4. The amount of traffic generated by different servers in the same tier is similar. And the amount of traffic coming into each tier is evenly distributed among all the servers in the tier.
  • [0091] 5. No traffic goes between servers in the same tier.

[0092] When it is necessary to consider applications with more general architecture or traffic characteristics, the mathematical models presented below can be easily extended to deal with these variations.

[0093] The following notation is used in the description to describe the mathematical formulation of the resource allocation problem (RAP).

• • [0094] l∈L: Set of tiers or layers, where |L| represents the number of tiers. [Alternative index i]
  • [0095] s∈S: Set of servers. |S| represents the number of servers. [Alternative index j]
  • [0096] a∈A: Set of attributes for servers. |A| represents the number of attributes.
  • [0097] r∈R: Set of rack switches. |R| represents the number of rack switches. [Alternative index q]
  • [0098] e∈E: Set of edge switches. |E| represents the number of edge switches.

[0099] The network topology of the IDC can be captured using the following sets.

• • [0100] SR_r⊂S: Set of servers connected to rack switch r.
  • [0101] SE_e⊂S: Set of servers connected to edge switch e.
  • [0102] : Set of rack switches connected to edge switch e.

[0103] The attributes of servers in the physical topology are represented by the matrix V, where each element V_as represents the value of the attribute a of server s. The bandwidth capacity of servers, rack and edge switches in the physical topology are represented by the following set of parameters:

• • [0104] BSI_s: The incoming bandwidth of server s.
  • [0105] BSO_s: The outgoing bandwidth of server s.
  • [0106] BRI_r: The incoming bandwidth of rack switch r.
  • [0107] BRO_r: The outgoing bandwidth of rack switch r.
  • [0108] BEI_e: The incoming bandwidth of edge switch e.
  • [0109] BEO_e: The outgoing bandwidth of edge switch e.

[0110] The application architecture requirements are represented by the following parameters. The number of servers to be allocated to tier l is defined by N_l. The maximum and minimum attribute requirements are represented by two matrices VMAX and VMIN, where each element VMAX_la and VMIN_la represent the maximum and minimum level of attribute a for any server in tier l. The matrix T is defined to characterize the traffic pattern of the application, where the element T_li represents the maximum amount of traffic going from each server in tier l to each server in tier i. The numbers T₀₁ and T₁₀ represent the Internet traffic coming into and going out of each server in tier l. Using these traffic parameters, the total amount of incoming and outgoing traffic at each server in different tiers may be calculated, denoted by TI_l and TO_l, respectively.

[0111] Thus far, the input parameters to RAP have been defined. The decision variables are defined next. In the optimization problem the decision to be made is which server in the physical topology should be assigned to which tier. The following matrix of binary variables represents this.

[0112] $x_{\mathrm{ls}}=\{\begin{array}{cc}1& \mathrm{server}s\mathrm{assigned}\mathrm{to}\mathrm{tier}l\\ 0& \mathrm{otherwise}\end{array}$

[0113] In summary, the mathematical optimization problem for RAP is the following.

[0114] $\mathrm{Max}\sum _{r\in R}\sum _{j\in {\mathrm{SR}}_r}\sum _{i\in L}\sum _{l\in L}\sum _{s\in {\mathrm{SR}}_r}{T}_{\mathrm{li}}{x}_{\mathrm{ls}}{x}_{\mathrm{ij}}+\sum _{e\in E}\sum _{j\in {\mathrm{SE}}_e}\sum _{i\in L}\sum _{l\in L}\sum _{s\in {\mathrm{SE}}_e}{T}_{\mathrm{li}}{x}_{\mathrm{ls}}{x}_{\mathrm{ij}}$
Subject to:

[0115] $\begin{array}{cc}\sum _{s\in S}{x}_{\mathrm{ls}}=N_1,l\in L& \left(1\right)\\ \sum _{l\in L}{x}_{\mathrm{ls}}\le 1,s\in S& \left(2\right)\\ \sum _{l\in L}V{\mathrm{MIN}}_{\mathrm{la}}{x}_{\mathrm{ls}}\le \left(\sum _{l\in L}{x}_{\mathrm{ls}}\right)V_{\mathrm{as}}\le \sum _{l\in L}V{\mathrm{MAX}}_{\mathrm{la}}{x}_{\mathrm{ls}},a\in A,s\in S& \left(3\right)\\ \sum _{l\in L}{\mathrm{TO}}_l{x}_{\mathrm{ls}}\le {\mathrm{BSO}}_s,s\in S& \left(4\right)\\ \sum _{l\in L}{\mathrm{TI}}_l{x}_{\mathrm{ls}}\le {\mathrm{BSI}}_s,s\in S& \left(5\right)\\ \sum _{l\in L}\sum _{s\in {\mathrm{SR}}_r}{\mathrm{TO}}_l{x}_{\mathrm{ls}}-\sum _{j\in {\mathrm{SR}}_r}\sum _{i\in L}\sum _{l\in L}\sum _{s\in {\mathrm{SR}}_r}{T}_{\mathrm{li}}{x}_{\mathrm{ls}}{x}_{\mathrm{ij}}\le {\mathrm{BRO}}_r,r\in R& \left(6\right)\\ \sum _{l\in L}\sum _{s\in {\mathrm{SR}}_r}{\mathrm{TI}}_l{x}_{\mathrm{ls}}-\sum _{j\in {\mathrm{SR}}_r}\sum _{i\in L}\sum _{l\in L}\sum _{s\in {\mathrm{SR}}_r}{T}_{\mathrm{li}}{x}_{\mathrm{ls}}{x}_{\mathrm{ij}}\le {\mathrm{BRI}}_r,r\in R& \left(7\right)\\ \sum _{l\in L}\sum _{s\in {\mathrm{SE}}_e}{\mathrm{TO}}_l{x}_{\mathrm{ls}}-\sum _{j\in {\mathrm{SE}}_e}\sum _{i\in L}\sum _{l\in L}\sum _{s\in {\mathrm{SE}}_e}{T}_{\mathrm{li}}{x}_{\mathrm{ls}}{x}_{\mathrm{ij}}\le {\mathrm{BEO}}_e,e\in E& \left(8\right)\\ \sum _{l\in L}\sum _{s\in {\mathrm{SE}}_e}{\mathrm{TI}}_l{x}_{\mathrm{ls}}-\sum _{j\in {\mathrm{SE}}_e}\sum _{i\in L}\sum _{l\in L}\sum _{s\in {\mathrm{SE}}_e}{T}_{\mathrm{li}}{x}_{\mathrm{ls}}{x}_{\mathrm{ij}}\le {\mathrm{BEI}}_e,e\in E{x}_{\mathrm{ls},}{x}_{\mathrm{ij}}\in \left\{0,1\right\},l,i\in D,s,j\in M& \left(9\right)\end{array}$

[0116] This formulation is referred to as the original mathematical optimization problem, labeled as P0. Since the objective function is nonlinear and there are nonlinear constraints, the optimization model is a nonlinear programming problem with binary variables, which cannot be solved efficiently by commercially available mathematical programming solvers.

[0117] To reduce the number of binary variables x_ls in the formulation, a feasibility matrix F is defined as follows.

[0118] $F_{\mathrm{ls}}=\{\begin{array}{cc}1& \mathrm{if}{x}_{\mathrm{ls}}=1\mathrm{satisfies}\left(3\right),\left(4\right)\mathrm{and}\left(5\right)\mathrm{of}\mathrm{P0};\\ 0& \mathrm{otherwise}.\end{array}$

[0119] It is used to pre-screen the servers that are infeasible. An additional constraint x_ls∈{0, F_ls} is imposed.

[0120] In this section, an approach is developed that comprises a series of mathematical optimization formulations that solves RAP heuristically and efficiently. The series of mathematical optimization models are variations and relaxations of the original formulation P0. The approach has three steps. Each step employs a mathematical optimization formulation that may be solved by commercial solvers. The three steps are:

• • [0121] 1. Find a good initial approximate solution. An MIP problem is formulated that minimizes the number of rack switches and edge switches involved. Conceptually, this objective function is a surrogate of the original objective function where latency is minimized. In this formulation, there is no visibility of the specific servers that are feasible in terms of the application requirements, but the number of feasible servers at each rack is visible. The solution generated by this MIP formulation does not consider rack and edge switch bandwidth constraints, which is why it is only an approximate solution. This MIP problem can be solved using CPLEX.
  • [0122] 2. Given the above approximate solution as an initial solution, a relaxation of the original problem is solved by formulating a nonlinear optimization problem in terms of the number of feasible servers at each rack switch allocated to the application. This formulation is equivalent to the original mathematical optimization formulation P0. However, in this case the formulation is a relaxation because all the decision variables can be continuous variables instead of integer variables. Since this nonlinear formulation provides only local optima instead of global ones step 1 is needed. This nonlinear optimization problem can be solved using MINOS.

[0123] 3. Given the local optimal solution from step 2, find a good solution to the original problem. Another MIP is formulated that essentially rounds the local optimal solution and identifies the exact servers that satisfy the requirements of the application. CPLEX solves this MIP problem.

[0124] The following discussion begins with the nonlinear optimization formulation (step 2 above) because this formulation is at the core of the solution approach. Then, the MIP formulation that comprises step 3 is described, which chooses the specific servers. Finally, the MIP formulation in step 1 is described, which determines good initial solutions for input to the nonlinear optimization problem.

[0125] For combinatorial optimization problems with binary variables, it is sometimes advisable, if possible, to reformulate the problem in terms of continuous variables over an interval. This brings convexity to the formulation and helps the continuous relaxation to be stronger, which means that the relaxation will give tighter bounds. For this purpose, a quadratic programming approximation of the original problem is formulated, referred to as QP.

[0126] A new decision variable is defined as follows.

• • [0127] xr_lr: Number of feasible servers connected to rack switch r that are allocated to tier l.
  • [0128] xr_lr∈[0, N_l].

[0129] For a given rack r,

[0130] ${\mathrm{xr}}_{\mathrm{lr}}=\sum _{s\in {\mathrm{SR}}_r}{F}_{\mathrm{ls}}{x}_{\mathrm{ls}}.$

[0131] The variable xr_lr appears in the QP formulation if and only if

[0132] $\sum _{s\in {\mathrm{SR}}_r}{F}_{\mathrm{ls}}\ge 1,$
which means the rack switch r has a feasible server for tier l. To simplify the notation, a new set is defined, which is the set of servers connected to rack switch r that are feasible for tier l. Each constraint in the original problem P0 is reformulated in terms of xr_lr. The resulting QP formulation follows.

[0133] $\begin{array}{cc}\mathrm{Max}\mathrm{ZQP}=\sum _{r\in R}\sum _{i\in L}\sum _{l\in L}{T}_{\mathrm{li}}{\mathrm{xr}}_{\mathrm{lr}}{\mathrm{xr}}_{\mathrm{ir}}+\sum _{e\in E}\sum _{r\in R_e}\sum _{i\in L}\sum _{l\in L}{T}_{\mathrm{li}}{\mathrm{xr}}_{\mathrm{lr}}{\mathrm{xr}}_{\mathrm{ir}}& \left(0\right)\end{array}$
Subject to:

[0134] $\begin{array}{cc}\sum _{r\in R}{\mathrm{xr}}_{\mathrm{lr}}=N_l,l\in L& \left(1\right)\end{array}$

[0135] Constraints (2). A 3-tier architecture is assumed; extensions to other number of tiers can be easily considered. For all r∈R,

[0136] $\begin{array}{cc}{\mathrm{xr}}_{\mathrm{l1r}}+{\mathrm{xr}}_{\mathrm{l2r}}+{\mathrm{xr}}_{\mathrm{l3r}}\le {\mathrm{FSR}}_{\mathrm{l1r}}\bigcup {\mathrm{FSR}}_{\mathrm{l2r}}\bigcup {\mathrm{FSR}}_{\mathrm{l3r}}{\mathrm{xr}}_{\mathrm{l1r}}+{\mathrm{xr}}_{\mathrm{l2r}}\le {\mathrm{FSR}}_{\mathrm{l1r}}\bigcup {\mathrm{FSR}}_{\mathrm{l2r}}{\mathrm{xr}}_{\mathrm{l1r}}+{\mathrm{xr}}_{\mathrm{l3r}}\le {\mathrm{FSR}}_{\mathrm{l1r}}\bigcup {\mathrm{FSR}}_{\mathrm{l3r}}{\mathrm{xr}}_{\mathrm{l2r}}+{\mathrm{xr}}_{\mathrm{l3r}}\le {\mathrm{FSR}}_{\mathrm{l2r}}\bigcup {\mathrm{FSR}}_{\mathrm{l3r}}0\le {\mathrm{xr}}_{\mathrm{l1r}}\le {\mathrm{FSR}}_{\mathrm{l1r}}0\le {\mathrm{xr}}_{\mathrm{l2r}}\le {\mathrm{FSR}}_{\mathrm{l2r}}0\le {\mathrm{xr}}_{\mathrm{l3r}}\le {\mathrm{FSR}}_{\mathrm{l3r}}\sum _{l\in L}{\mathrm{TO}}_l{\mathrm{xr}}_{\mathrm{lr}}-\sum _{i\in L}\sum _{l\in L}{T}_{\mathrm{li}}{\mathrm{xr}}_{\mathrm{lr}}{\mathrm{xr}}_{\mathrm{ir}}\le {\mathrm{BRO}}_r,r\in R& \left(6\right)\\ \sum _{l\in L}{\mathrm{TI}}_l{\mathrm{xr}}_{\mathrm{lr}}-\sum _{i\in L}\sum _{l\in L}{T}_{\mathrm{li}}{\mathrm{xr}}_{\mathrm{lr}}{\mathrm{xr}}_{\mathrm{ir}}\le {\mathrm{BRI}}_r,r\in R& \left(7\right)\\ \sum _{r\in R_e}\sum _{l\in L}{\mathrm{TO}}_l{\mathrm{xr}}_{\mathrm{lr}}-\sum _{q\in R_e}\sum _{r\in R_e}\sum _{i\in L}\sum _{l\in L}{T}_{\mathrm{li}}{\mathrm{xr}}_{\mathrm{ls}}{\mathrm{xr}}_{\mathrm{iq}}\le {\mathrm{BEO}}_e,e\in E& \left(8\right)\\ \sum _{r\in R_e}\sum _{l\in L}{\mathrm{TI}}_l{\mathrm{xr}}_{\mathrm{lr}}-\sum _{q\in R_e}\sum _{r\in R_e}\sum _{i\in L}\sum _{l\in L}{T}_{\mathrm{li}}{\mathrm{xr}}_{\mathrm{ls}}{\mathrm{xr}}_{\mathrm{iq}}\le {\mathrm{BEI}}_e,e\in E{\mathrm{xr}}_{\mathrm{lr}}\ge 0,l\in L,r\in R\ni \sum _{s\in {\mathrm{SR}}_r}{F}_{\mathrm{ls}}\ge 1& \left(9\right)\end{array}$

[0137] The next portion of the discussion describes a Mixed Integer Programming problem, MIP2, to intelligently round the local optimal solution generated by the QP model. The MIP2 model defines the actual servers to allocate to the application. The decision variables are the same as those in the original problem P0.

[0138] $x_{\mathrm{ls}}=\{\begin{array}{cc}1& \mathrm{server}s\mathrm{assigned}\mathrm{to}\mathrm{tier}l\\ 0& \mathrm{otherwise}\end{array}$

[0139] The first two constraints of the model are similar to those for the P0 problem.

[0140] $\begin{array}{cc}\sum _{s\in S}{x}_{\mathrm{ls}}=N_l,l\in L& \left(1\right)\\ \sum _{l\in L}{x}_{\mathrm{ls}}\le 1,s\in S& \left(2\right)\end{array}$

[0141] For each rack switch r and tier l, allocate as many servers as recommended by the local optimal solution, xr*, from the QP model.

[0142] $\begin{array}{cc}\sum _{s\in {\mathrm{SR}}_r}{x}_{\mathrm{ls}}\ge \lfloor {\mathrm{xr}}_{\mathrm{lr}}^{*}\rfloor \mathrm{if}{\mathrm{xr}}_{\mathrm{lr}}^{*}>0& \left(3\right)\end{array}$

[0143] As previously explained, constraints (3), (4) and (5) of the original problem P0 are captured by the feasibility matrix F. Accordingly, another constraint, x_ls∈{0, F_ls}, is imposed to ensure that the variable x_ls appears in the formulation if and only if F_ls=1. Incoming and outgoing bandwidth capacity constraints are not considered because these constraints are satisfied by the solution of the QP model. The MIP2 model is just rounding the QP solution without modifying total traffic going through rack switches and edge switches.

[0144] The objective function is to minimize the number of servers allocated.

[0145] $\begin{array}{cc}\mathrm{Min}\sum _{l\in L}\sum _{s\in S}{x}_{\mathrm{ls}}& \left(0\right)\end{array}$

[0146] It may be observed that the above objective function is a constant,

[0147] $\sum _{l\in L}{N}_l,$
due to constraint (1). The reason why it is imposed is not that the rounding model needs it. Instead, it is because the commercial solver used for mixed integer programming may require that an objective function be specified. Due to the fact that all feasible solutions have the same objective function value, the minimization does not enforce anything, which is desirable in this case. In some other cases, it may be desirable to use the objective function to minimize the total “cost” of allocating servers to the application.

[0148] In summary, the MIP2 formulation is as follows:

[0149] $\begin{array}{cc}\mathrm{Min}\sum _{l\in L}\sum _{s\in S}{x}_{\mathrm{ls}}& \left(0\right)\end{array}$
subject to:

[0150] $\begin{array}{cc}\sum _{s\in S}{x}_{\mathrm{ls}}=N_l,l\in L& \left(1\right)\\ \sum _{l\in L}{x}_{\mathrm{ls}}\le 1,s\in S& \left(2\right)\\ \sum _{s\in {\mathrm{SR}}_r}{x}_{\mathrm{ls}}\ge \lfloor {\mathrm{xr}}_{\mathrm{lr}}^{*}\rfloor \mathrm{if}{\mathrm{xr}}_{\mathrm{lr}}^{*}>0x_{\mathrm{ls}}\in \left\{0,F_{\mathrm{ls}}\right\}& \left(3\right)\end{array}$

[0151] In the following discussion, a Mixed Integer Programming problem, MIP1, is formulated to generate a good initial solution for the QP model. The MIP1 formulation is based on the following intuitions. First, if there is a feasible server assignment under a single rack switch that satisfies constraints (1) to (5) of the original problem P0, then this solution is most likely feasible for the rack and edge switches bandwidth constraints (6) to (9). Second, this feasible server assignment is optimal for P0 because the objective function of P0 is formulated as minimizing the weighted average of the number of hops between each pair of servers, i.e.,
Min {circumflex over (z)}=2F^R+4F^E+6F^M,
where F^R, F^E and F^M are the total amounts of inner traffic at all rack switches, edge switches and mesh switch, respectively. In addition,

[0152] $F^R+F^E+F^M=\sum _{l\in L}\sum _{i\in L}{N}_l{T}_{\mathrm{li}}{N}_i,$
which is a constant. Let it be denoted by C. Hence, {circumflex over (z)}=2C+2F^E+4F^M. Because F^E≧0 and F^M>0, {circumflex over (z)}≧2C follows. The optimum is achieved if and only if F^R=C and F^E=F^M=0, which is the case when only servers under one rack switch are chosen. Furthermore, even if more than one rack switch is needed, the intention will be to minimize F^E and F^M as much as possible. Observer that F^E is larger when more rack switches are involved, and F^M is larger when more edge switches are involved. Therefore, the idea in the MIP1 model is to try to allocate servers that are in the same rack or that are in “closer” racks, where two racks are considered to be close if they are connected to the same edge switch.

[0153] Based on the above discussion, the objective function of the MIP1 formulation is a surrogate function of the objective function of P0. Roughly speaking, the objective of MIP1 is to minimize the total weighted usage of rack and edge switches. Consequently, the MIP1 problem is formulated as a “Facility Location Optimization Problem”. The following “location” variables are defined:

[0154] $\mathrm{For}\mathrm{each}e\in E,u_e=\{\begin{array}{cc}1& \mathrm{if}\mathrm{edge}\mathrm{switch}e\mathrm{is}\mathrm{used}\\ 0& \mathrm{otherwise}\end{array}\mathrm{For}\mathrm{each}r\in R,v_r=\{\begin{array}{cc}1& \mathrm{if}\mathrm{rack}\mathrm{switch}r\mathrm{is}\mathrm{used}\\ 0& \mathrm{otherwise}\end{array}$

[0155] The weights for these location variables are chosen so that the minimization of the objective function emulates the direction of optimality in the original problem P0. In particular, the weight for each switch used is defined to be the latency measure (number of hops) for that switch, i.e., CR_r=2, and CE_e=4.

[0156] The main issue with the original formulation P0 is that the combinatorial optimization problem has binary variables, quadratic constraints, and a quadratic objective function. Having removed the nonlinearity from the objective function in MIP1 already, the quadratic bandwidth constraints may be removed for rack and edge switches to linearize the problem. Therefore, the MIP1 formulation is an approximation of the original problem P0. It is not guaranteed to generate a feasible solution for P0. However, this is acceptable since the goal of the MIP1 model is to generate good initial solutions for the QP model, which explicitly considers the quadratic constraints removed in the MIP1 formulation.

[0157] As in the QP model, a 3-tier architecture for the application is assumed. Extensions to other number of tiers are easy to implement. Similar to the QP formulation, x_lr is defined as the number of feasible servers in rack switch r allocated to tier l. The x_lr appears in the formulation if and only if rack switch r has a feasible server for tier l. The constraints of the MAP1 formulation are as follows.

[0158] Constraint 1) The total number of servers allocated to tier l is N_l.

[0159] $\begin{array}{cc}\sum _{r\in R}{\mathrm{xr}}_{\mathrm{lr}}=N_i,l\in L& \left(1\right)\end{array}$

[0160] Constraint 2) Allocate at most one server to a tier and ensure that no server allocated is double counted.
xr_l1r+xr_l2r+xr_l3r≦|FSR_l1r∪FSR_l2r∪FSR_l3r|
xr_l1r+xr_l2r≦|FSR_l1r∪FSR_l2r|
xr_l1r+xr_l3r≦|FSR_l1r∪FSR_l3r|
xr_l2r+xr_l3r≦|FSR_l2r∪FSR_l3r|
0≦xr_l1r≦|FSR_l1r|, 0≦xr_l2r≦|FSR_l2r|, 0≦xr_l3r≦|FSR_l3r|

[0161] Constraint 3) These are logical constraints over the binary variables u_e and v_r that ensure that these variables behave as intended. If servers are to be allocated from rack switch r to tier l then rack switch r needs to be “used”. That is,

• • [0162] v_r=l if xr_lr>0;
  • [0163] v_r=0 if xr_lr=0.
    Therefore, the following constraint is defined:
    N_lv_r≧xr_lr, FSR_lr≠Ø  (3.1)
    where the coefficient of the variable v_r is an upper bound of the variable xr_lr. Note that condition 1 is satisfied by constraint (3.1), and condition 2 is satisfied by this constraint and because the weighted summation of v_r variables are being minimized, at optimality v_r=0 if xr_lr=0.

[0164] Now, if rack switch r is to be “used”, the edge switch e connected to this rack switch needs to be “used.” That is,

• • [0165] u_e=1 if v_r=1;
  • [0166] u_e=0 if v_r=0.
    Thus, the following constraint is defined:
    u_e≧v_r, e∈E, r∈R_e  (3.2)
    This constraint ensures condition 1 is satisfied, and condition 2 is satisfied at optimality.

[0167] The objective function of the MIP1 formulation is to minimize the total cost of “using” rack and edge switches, and is defined as follows

[0168] $\begin{array}{cc}\mathrm{Min}\sum _{e\in E}^{}{\mathrm{CE}}_e{u}_e+\sum _{r\in R}^{}{\mathrm{CR}}_r{v}_r& \left(0\right)\end{array}$

[0169] In summary, the formulation of the MIP1 model is

[0170] $\begin{array}{cc}\mathrm{Min}\sum _{e\in E}^{}{\mathrm{CE}}_e{u}_e+\sum _{r\in R}^{}{\mathrm{CR}}_r{v}_r& \left(0\right)\end{array}$
subject to:

[0171] $\begin{array}{cc}\sum _{r\in R}^{}{\mathrm{xr}}_{\mathrm{lr}}=N_1,l\in L{\mathrm{xr}}_{\mathrm{l1r}}+{\mathrm{xr}}_{\mathrm{l2r}}+{\mathrm{xr}}_{\mathrm{l3r}}\le {\mathrm{FSR}}_{\mathrm{l1r}}\bigcup {\mathrm{FSR}}_{\mathrm{l2r}}\bigcup {\mathrm{FSR}}_{\mathrm{l3r}}{\mathrm{xr}}_{\mathrm{l1r}}+{\mathrm{xr}}_{\mathrm{l2r}}\le {\mathrm{FSR}}_{\mathrm{l1r}}\bigcup {\mathrm{FSR}}_{\mathrm{l2r}}{\mathrm{xr}}_{\mathrm{l1r}}+{\mathrm{xr}}_{\mathrm{l3r}}\le {\mathrm{FSR}}_{\mathrm{l1r}}\bigcup {\mathrm{FSR}}_{\mathrm{l3r}}{\mathrm{xr}}_{\mathrm{l2r}}+{\mathrm{xr}}_{\mathrm{l3r}}\le {\mathrm{FSR}}_{\mathrm{l2r}}\bigcup {\mathrm{FSR}}_{\mathrm{l3r}}0\le {\mathrm{xr}}_{\mathrm{l1r}}\le {\mathrm{FSR}}_{\mathrm{l1r}},0\le {\mathrm{xr}}_{\mathrm{l2r}}\le {\mathrm{FSR}}_{\mathrm{l2r}},0\le {\mathrm{xr}}_{\mathrm{l3r}}\le {\mathrm{FSR}}_{\mathrm{l3r}}& \left(1\right)\\ N_l{v}_r\ge {\mathrm{xr}}_{\mathrm{lr}},{\mathrm{FSR}}_{\mathrm{lr}}\ne \varnothing & \left(3.1\right)\\ u_e\ge v_r,e\in E,r\in R_e{u}_e,v_r\in \left\{0,1\right\},e\in E,r\in R{\mathrm{xr}}_{\mathrm{ls}}\ge 0,l,r\in L\times R,\mathrm{and}\sum _{s\in {\mathrm{SR}}_r}^{}{F}_{\mathrm{ls}}\ge 1& \left(3.2\right)\end{array}$

[0172] Those skilled in the art will appreciate that various alternative computing arrangements would be suitable for hosting the processes of the different embodiments of the present invention. In addition, the processes may be provided via a variety of computer-readable media or delivery channels such as magnetic or optical disks or tapes, electronic storage devices, or as application services over a network.

[0173] The present invention is believed to be applicable to a variety of application architectures and has been found to be particularly applicable and beneficial in web service architectures. Other aspects and embodiments of the present invention will be apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. It is intended that the specification and illustrated embodiments be considered as examples only, with a true scope and spirit of the invention being indicated by the following claims.