A Hayekian self-organization approach to service allocation in computing systems

1 A Hayekian Self-Organization Approach to Service Allocation in Computing Systems Torsten Eymann (corresponding author), Michael Reinicke Chair of Information Systems (BWL VII), University of Bayreuth, 95440 Bayreuth, Tel. +49-921-55-2807, Fax +49-921-55-2216. {torsten.eymann, michael.reinicke}@uni-bayreuth.de Felix Freitag, Leandro Navarro, Oscar Ardaiz, Pau Artigas Computer Architecture Department, Polytechnic University of Catalonia, Spain {oardaiz, partigas, felix, leandro}@ac.upc.es Abstract Future “on-demand” computing systems, often depicted as potentially large scale and complex Service-Oriented Architectures, will need innovative management approaches for controlling and matching services demand and supply. Centralized optimization approaches reach their bounds with increasing network size and number of nodes. The search for decentralized approaches has led to build on self-organization concepts like Autonomic Computing, which draw their inspiration from Biology. This article shows how an alternative self-organization concept from Economics, the Catallaxy concept of F.A. von Hayek, can be realized for allocating service supply and demand in a distributed “on-demand” web services network. Its implementation using a network simulator allows evaluating the approach against a centralized resource broker, by dynamically varying connection reliability and node density in the network. Exhibiting Autonomic Computing properties, the Catallaxy realization outperforms a centralized broker in highly dynamic environments. 2 Keywords Autonomic Computing, Digital Business Agents, Agent-Based Computational Economics, Catallaxy, Service-Oriented Architecture, Resource Brokering 1. Introduction The focus of this article is on the presentation and evaluation of a self-organization mechanism for allocating resources in a Grid-like Application Layer Network (ALN). ALNs are software architectures that allow the provisioning of services requiring larger amounts of resources, which can be obtained from computing systems connected over simple communication infrastructures such as the Internet. In general, Grid computing, Peer-to-Peer networks, On-Demand Computing and Service-oriented Architectures can be subsumed under this category. A particular resource allocation problem in these concepts is how to match the distributed demand for a service, with an existing, but unclear supply situation. Using self-organization for such computing system problems, instead of a centralized matchmaker, has recently gained attention by the start of large industrial research concepts like IBM’s Autonomic Computing or HP’s Adaptive Computing initiatives. The key motivation aspect for self-organization lies in the increasing size and complexity of today’s information systems, which has led to a non-negligible growth of their control costs. Autonomic Computing uses a biological paradigm as a design and control metaphor, the autonomic nervous system {Kephart #111}. The core properties of the Autonomic Computing concept, the CHOP circle of self-configuring, self-healing, self-organization and self-protection is an electronic realization of the respective mechanisms of the human body. Abundant biological paradigms distract from the existence of self-organizing resource allocation mechanisms elsewhere, which could, and have been used for engineering and controlling computer systems. In the physical world, for example, the proven ability of a free- 3 market economy to adjudicate and satisfy the conflicting needs of millions of human agents recommends it as a decentralized organizational principle {Eymann, 2004 #95; Kephart #1094; Wellman #1715}. Applying Economic concepts to allocating or scheduling resources in computing systems is not a new idea (see {Huberman, 1988 #1012; Clearwater #625} for overviews). An early attempt at using economic ideas have been Agoric Open Systems (AOS) {Lavoie #118; Miller #1241}. AOS were defined as software systems that use market mechanisms for resource allocation, and encapsulate information, access paths and resources in objects traded by economic actor processes. Similar projects have been Mariposa {Stonebraker #1807}, Popcorn {Regev #1808}, and Spawn {Waldspurger #1809}. The basic problem can be characterized by having a number of processors, supplying computing power to a demand situation composed of computation jobs. The particular question is how supply and demand can be matched to each other, if the actual situation on both sides is unclear. In closed environments, e.g. parallel computing, this question usually can be assumed away, as the number of processors is fixed and the arrival of computational jobs is deterministic. However, the advent of large, open distributed networks of processors, like in Grid computing, has spurred new interest in this question. Generalizing, to match a particular computation request to a processor service in a Grid, four phases have to be conducted: service discovery, matching requests to services, scheduling the matched services and finally execution {Krauter, 2001 #1}. Existing sophisticated approaches for service discovery have been realized using flooding algorithms or distributed hash tables (DHT) {Ratnasamy, 2001 #129; Balakrishnan, 2003 #2}. The result of the service discovery phase is a list of candi- 4 date service provider instances. In this article, we assume that more than one service can provide access rights, and more than one client demands access - otherwise, the matching phase would be trivial. In the matching phase, either the client (decentralized case) or a resource broker (centralized case) have to select a match out of several possible pairings, which satisfies both parties. A typical implementation of service selection, out of a list of discovered candidates, is a centralized matchmaker or resource broker {Chandra #601; Foster #827; Rabinovich #1406}. The matchmaker instance selects the apparently optimal match from the list, and the requesting client receives only the resulting name. Clients and service providers update the centralized resource broker in a continuous frequency about their requests and effective availability. Satisfaction can be ideally measured either by technical parameters (fast execution time, low bandwidth usage, minimal communication overhead) or by translating these to economic metrics, e.g. utility as minimal direct access costs or as a function of waiting time saved. In principle, existing service matching mechanisms can thus be visualized as a 2x2 matrix shown in Figure 1. 5 Matching by a Coordinator Instance Match selection by Peer Client Ranking using technical parameters Resource Auctioneers, e.g. EcoGrid, Nimrod/G Usual Resource Brokers, e.g. Condor File Sharing, e.g. Gnutella Ranking using economic parameters (open) Figure 1: A portfolio of Grid Service matching mechanisms Condor-G {Frey, 2002 #303}, Darwin {Chandra, 2001 #601}, and most Globus-based implementations {Foster, 1999 #827} typically use a centralized matchmaker instance to evaluate the candidate list. The requesting client receives one matching partner, resulting from global optimization on latency, distance or bandwidth usage, according to the current network state. Extended central approaches implement auctioneers, like in EcoGrid or Nimrod/G {Buyya, 2002 #292; Buyya, 2002 #1813}, or electronic marketplace instances {Gomoluch, 2003 #1814}, which collect bids and offers from the Grid nodes, and match supply and demand like a stock market mechanism does. Decentralized mechanisms, like in most file sharing networks, e.g. Gnutella {Adar, 2000 #383} or Kazaa, have no central point to collect supply and demand before matching. Each client decides for himself which service provider to match to based on technical parameters like estimated download time. The up- 6 per right corner of Figure 1, requiring client-based economic decision-making mechanisms with a model-based prediction of the system state {Gomoluch, 2003 #1814} and allocation via bargaining models {Buyya, 2002 #1813}, is only sparsely populated (one failed attempt has been MojoNation {Mojo Nation, 2003 #121}. In the next two sections, we present an implementation of such a decentralized market mechanism concept, Hayek’s Catallaxy, using a multiagent system. A comparative simulation of a Catallaxy resource allocation approach vs. a centralized approach in an application layer network indicates the strengths and weaknesses of the implementation. After that, we discuss related work on using Economic concepts for controlling computer systems, after which the article ends with the issue, whether the Catallaxy concept may be a fruitful alternative for engineering Autonomic Computing systems. 3. The Catallaxy: a self-organization concept from Economics Friedrich August von Hayek {Hayek #952} understood the market as a decentralized coordination mechanism, as opposed to a centralized command economy. Apart from political macroeconomic thoughts, his work also provides concrete insight on the working mechanisms of economic coordination. The emergence of software agent technology and increasing size of information systems leads to the possibility of implementing Hayek’s Catallaxy concept and using the ensuing “spontaneous order” as a concrete proposal for both the design and coordination of information systems. However, a formal description of this selforganizing market mechanism does not so far exist. The Catallaxy concept bases on the explicit assumption of self-interested actions of the participants, who try to maximize their own utility and choose their actions under incomplete information and bounded rationality {Simon #1539}. The term Catallaxy comes from 7 the Greek word “katallatein”, which means, “to barter” and at the same time, “to join a community.” The goal of Catallaxy is to arrive at a state of coordinated actions, the “spontaneous order”, which comes into existence through the bartering and communicating of the Community members with each other and thus, achieving a community goal that no single user has planned for {Hayek, 1989 #952}. The main characteristics of the Catallaxy {Hoppmann #1006} are that 1. Participants work in their own interest to gain income. Every system element is a utility maximizing entity, which requires the definition of utility itself, of means to measure and compare income and utility, and to express a desire to reach a defined goal. For humans, these definitions have not necessarily to be explicit or thoroughly defined; for information system elements, this explicitness is required. 2. Participants subjectively weigh and choose preferred alternatives in order to reach an income or utility maximization goal. In economic theory, the “homo oeconomicus” is a completely rational utility maximizer. He can choose an alternative action out of total knowledge about the environment. Hayek’s claim was that such an “objective” choice is not possible because of "constitutional ignorance”, that it is (inevitably) impossible to know each and every detail of the environment state. For large and very dynamic information systems, this is inherently true, and overcoming it by central means requires synchronization and restriction of possible actions of the single elements. 3. Participants communicate using commonly accessible markets, where they barter about access to resources held by other participants. The development of prices for a specific good, whether they are increasing or decreasing, leads buyers to look for al- 8 ternative sources of procurement and thus enhances the dynamics of the market. Note that a market here is nothing more than a communication bus – it is not a central entity of its own, which collects all information and matches market participants using some optimization mechanisms, which would contradict “constitutional ignorance”. In human economic systems, these institutions are implicit; for a realization in distributed information systems, the properties of utility maximization, strategies and the exchange of offers need to be explicitly specified and implemented. Formal descriptions for using economic mechanisms in distributed computing systems can be found in {Ferguson, 1996 #796}. As a blueprint for other possible forms of Service Grids {Gomoluch, 2003 #1814} or Application Layer Networks, we describe the concept using a simple web services scenario of a PDF conversion service {Catnet Project #85}{T-Online AG #137}: Adobe’s PDF file format is a common exchange file type for mixed text and graphics documents, mostly due to its preservation of layout specifics. The files are created using the (usually locally installed) Acrobat Distiller service, which converts from e.g. Microsoft Word or Postscript files. In an “on-demand” Service Grid, Distiller web services are available in the network, hosted by independent vendors and directly accessible from the software application, competing with each other for the clients’ demand. The wordprocessor client programs transparently address such a networked PDF conversion service instance in the background, without disturbing the user’s course of work. Clients and service provider instances bargain on access prices on a case-by-case basis, taking into account the current and prospective development of supply and demand to increase the mone- 9 tary utility of their respective owners. Services instances are situated on host computers, which, for simplicity, are assumed to provide processor power and storage on a fixed cost basis. Economic actors are straightforwardly implemented as intelligent software agents {Wooldridge #1759}. Agents are embedded in an environment; whose state they experience through sensors; which lead to a comparison of an actual environment state with a desired environment state using an internal world model; and where they try to influence the environment state using effectors towards that more desirable state. Market Environment Agent Sensor: Price Signals Effector: Ask/Bid Offers Adaptation of Price Setting Strategies Figure 2: Properties of Digital Business Agents (cf. {Wooldridge #1759}) Figure 2 shows a Digital Business Agent {Eymann #301} working in a market environment. Sensors and effectors are realized as price signals incoming from and outgoing to the market environment. If the agents’ utility goals are not met by the present ownership situation, they negotiate with each other in order to maximize utility by exchanging resource access rights (e.g. using an alternating offers protocol {Rosenschein #1445}). Bartering forms a sequence of effectors and sensors, this leads under partial and bounded knowledge to an adaptation of the agent’s internal model. Implementing Edgeworth bartering {Varian #1674}, the agents trade bilaterally and secretly with each other, if the internal world model 16 In our simulations, we have analyzed changing ALN environments by varying the network setup using the dimensions of node density and node dynamics. Node density measures the number of service copies available in the network – the more SCs can provide service access, the denser is the network. Node dynamics measures the probability that SCs can become disconnected and reconnected again – a static network shows a constant availability of 100%, while a peer-to-peer network is practically defined by continuous appearance and disappearance of nodes. The intention of choosing these dimensions was to capture different types of ALN environments in one simulation, while restricting the number of simulations that need to be run. In the current model, for each change in the underlying variables, we have run 50 simulations: 25 for Catallactic and 25 for Baseline resource allocation. As simulation input we use a trace of client demands containing service requests. Each service request specifies the amount of service, a price, and the duration of the invocation. All simulations use the same demand trace. 17 Position of Master Service Copy „Backbone“ Outer leaves Inner node ring Figure 4: Network topology The physical network topology used in the simulations is organized in two rings, each having three levels of pentagons with leaves on the outer level (Figure 4). The rings are connected at the inner pentagon nodes; the intention of that topology is to resemble current ALNs, which mainly consist of two networks in North America and Europe, connected by a few backbones. The ALN is built on top of the physical network. Network nodes are instantiated having one of the previously described types, being a client, service copy or resource agent. Depending on the particular simulation, a node may contain several agents or no agent at all. In the second case, the node acts as a router. Table 1 shows the configuration of the simulations. Table 1: Description of the Simulations Input trace - 2000 service requests generated randomly by 150 clients over a time interval of 100 s. - time between issuing requests is 75 ms. 18 - each request is for 1 service unit. - each request message can travel 10 hops distance maximum. - each service invocation has a duration of 5s, in which the SC is blocked. - Cycle time of the master service copy, if active, is 150ms. Topology - 212 physical nodes in 2 rings. Node density Always 150 clients on the leaves of one physical network ring. Different density applies to resource and service copy agents. - Density 0: 6 nodes hold 50 service copies each. - Density 1: 12 nodes hold 25 service copies each. - Density 2: 25 nodes hold 12 service copies each. - Density 3: 50 nodes hold 6 service copies each. - Density 4: 75 nodes hold 4 service copies each. Node dynamics Dynamic behavior: On start, 70% of the service copies are connected. - Dynamics 0 : Service copies do not change their state (static network) - Dynamics 1: Every 200 ms any service copy can change its state (connected/disconnected) with a probability of 0.2. - Dynamics 2: as before with a probability of 0.4 - Dynamics 3: as before with a probability of 0.6 - Dynamics 4: as before with a probability of 0.8 The following results are from the same simulation. The first question is how the system behaves with respect to the Resource Allocation Efficiency (RAE), which measures the percentage of successful negotiations. In an Edgeworth barter setting, every successful negotiation indicates an increase in overall utility. The metric thus allows a statement on the overall performance of the system. The total values of the scale are artifacts of the simulation setup, but the relative performance of Catallaxy vs. Baseline is repeatable. 19 012340 1 2 3 4 0 10 20 30 40 50 60 70 80 90 100 RAE Dynamics Density RAE Catallactic Approach 012340 1 2 3 4 0 10 20 30 40 50 60 70 80 90 100 RAE Dynamics Density RAE Baseline Approach Figure 5: Resource Allocation Efficiency for Catallactic vs. Baseline Simulations The left side of Figure 5 shows the results of the decentralized, Catallactic resource allocation approach. The two axes at the bottom reference to the changes in node density and network dynamics, as explained in Table 1. The RAE performance decreases with increasing dynamics, the worst RAE occurs when density is low (only few nodes exist) and dynamics are high. In comparison with the Baseline approach shown on the right side, the slow decrease in overall performance is notable. For a static network with low dynamics and low density, both mechanisms fare quite well, as there is ample time to discover all available services, negotiate with them and decide on allocation. Changes in the density of the resources have only small effect on the Baseline RAE. As the central Baseline broker does the main work, the geographical layout of the network seems to play only a minor role. With increasing dynamics, however, the Catallactic RAE is less affected. 20 If we look closer at technical parameters, which are known to be inferior for distributed systems and bargaining approaches, we find a different picture. An example is the response time (REST), which marks the time span between issuing a demand request and the final satisfaction or rejection of that request (timed-out negotiation attempts in-between add up to the total). Figure 6 shows average response times for the successful and accepted service negotiations, with the Catallactic approach to the left. When comparing Catallaxy here to Figure 5, the outcome is quite diverse: Except for high dynamics in a low density regime, the outcome seems to be relatively stable. A REST of approx. 600ms is the maximum, which is probable an artefact of the flooding algorithm, searching to get an adequate number of replies. At higher density levels, and seemingly independent of the dynamics level, we find a minimum below 320ms. The decentralized approach would probably benefit from using a revised discovery algorithm like CAN or Chord in low density and dynamics regimes. The right side of Figure 6 shows the response time of the Baseline mechanism, resulting in a rugged landscape. The outcome is determined by the cycle time of the master service copy (MSC), which synchronizes the existing market situation and concentrates it at one location. Dynamics thus has an ample impact on the response time, with a twofold increase over the simulation range. This is probably caused by higher dynamics leading to more misallocations and therefore to time-consuming new requests and allocations. Density variations have only a slight effect on the response time, because the geographical distances in the network are equalized by the MSC. 21 01234 0 1 2 3 4 0 100 200 300 400 500 600 700 800 REST Dynamics Density REST Baseline Approach 0 2 4 01234 0 500 1000 1500 2000 2500 REST Dynamics Density REST Catallactic Approach Figure 6: Response Time for Catallactic vs. Baseline Simulations 6. On implementing Economic Self-Organization in Computing Environments What makes Economics so attractive for computing environments is that its central research question lies in the effective allocation of resources, provided by suppliers and in demand by customers. In computing environments like Grid Computing, the resources in question are processor time or storage space, while the economic actors are computers or web services {Buyya #574; Buyya #292}. It appears that, by just implementing markets in computing environments, the satisfying ability of economics might be viable for creating costeffective computer architectures. 22 However, between the mostly descriptive economic concept and the normative technical implementation lies a fundamental gap, requiring selective choice of how actors, resources, goods, and markets are modelled and embedded in a technical environment. Some researchers call this task “market engineering” {Weinhardt #144}. The basic purpose of market engineering is to capture the inherently decentralized, dynamic coordination nature of the economic concept, and to translate that into a technical realization, which allows optimizing resource allocation. The „market“ as a decentralized, dynamic coordination mechanism Economic Concept Technical Implementation Service-OrientedArchitectures ? Figure 7: Realizing economic concepts in a technical implementation There are several competing descriptive approaches to how economic resource allocation mechanisms work. In general, Economics is essentially all about the coordination of systems consisting of utility-maximizing agents, who satisfy their needs using some mechanism for solving a distributed resource allocation problem. The effect of this mechanism is a 23 state where prices are set, so that supply and demand is perfectly balanced, and the number of transactions is maximized {Kearney #1088}. All implementation attempts try either to recreate the mechanism, or to achieve the effect by using another mechanism, adding some side condition like zero communication costs or a steady environment state. Adam Smith’s proverbial invisible hand {Smith #1551} was a first concept of a decentralised mechanism without a co-ordinator, but Smith gave no implementation of that mechanism. A century later, Leon Walras {Walras #1690} introduced a central auctioneer, who iteratively solved the allocation problem out of total knowledge of supply and demand. With this mechanism, Walras was able to generate the desired equilibrium effect. Most of today’s economic research relies on Walras’ tatônnement process as a valid picture of the mechanism, which influences also the possible realization in computing environments. An example is the realization by Wellman {Wellman #1715}, titled MarketOriented Programming (MOP), in an distributed artificial intelligence (DAI) environment. Wellman takes the notion that „an economy is a multiagent system” literally; the distributed agents individually compute their utility functions and post that information to a centralized Walrasian auctioneer. During the computation process, interrelated markets are successively brought to near-equilibrium by the auctioneer, with the final general equilibrium effect as the „gold standard” to achieve. MOP has been successfully used in electricity markets {Ygge #1771}, for multi-commodity flow problems {Wellman #1714}, supply chain management {Wellman #145} or for negotiations about the quality of service in multimedia networks {Yamaki #1768}. In contrast, Economics research on self-organization still aims at explaining the mechanism of the invisible hand, e.g. Agent-based Computational Economics {Tesfatsion #1611}. Ac- 24 tually, there is growing interest in using self-organization, as indicated by the start of large industrial research concepts like IBM’s Autonomic Computing initiative. Autonomic Computing uses a biological paradigm as a design and control metaphor, the autonomic nervous system {Kephart #111}. If the mechanisms underlying Hayek’s spontaneous order concept {Hayek #952} can be properly understood, it might be possible to build large Autonomic information systems using the Catallaxy approach, where artificial entities coordinate themselves, just as human economy participants do in the real world. For a start, we have to discuss whether the desired effects of Autonomic Computing are achievable (and describable) using economic terms. IBM’s Autonomic Computing Manifesto {IBM #312} describes seven characteristics, which self-adapting systems should exhibit. The core characteristics are contained in the so-called CHOP cycle of self-configuring, self-healing, self-optimizing and self-protection capabilities. The self-configuration property is indicated in the variation of prices when adding or removing service providers (cf. the different density regimes). The self-healing of the system is apparent in case a service provider instance shuts down or a network connection gets broken (cf. the different dynamics regimes). The application is self-optimizing, in that the agents constantly attempt to change their strategies towards the maximum utilityeliciting negotiation positions, which respectively lay on the total supply and demand curves. The self-protection of the application finally can be reached by including security mechanisms like reputation tracking {Eymann #300}, which are effective in separating malicious and underperforming agents. In addition, viewing Autonomic Computing systems as Economic systems has some merits, too. The main applications for AC systems will be deeply rooted in a business context. With a biological background, you need to find biological translations for conceptual data 25 structures and functionality for describing success, utility, or business goals. This is not a trivial process, and may lead to semantic loss underway. For example, the business goal of maintaining availability (to prevent loss of profit in the case of server downtime), may be translated biologically as “staying alive”. However, the semantics of both differ – deliberately shutting down a biological AC system may qualify for murder, while in economic terms, shutting down a system means buying it out of business – with the programmer defining what the currency is. 7. Conclusion The CATNET simulation presented in this article is a generalizable network simulation for application layer networks. We have used its specification and the properties of the resource allocation mechanism to investigate into constructing Autonomic Computing systems using an Economics, rather than a Biology approach. Our simulation results indicate that resource allocation in networks, where many small nodes work in a highly dynamic environment, can be coordinated successfully by the Catallaxy paradigm. The results presented in this article are only the first step towards successfully engineering “economic” autonomic computing systems (see also {Cheliotis #1810}). On the engineering side, we found optimization potential in the design of the negotiation protocol or in the possibility to relocate underperforming service copy instances to other hosts. The key to this semantic shift is to view the „market“ as an emergent mechanism of coordinating and matching supply and demand offers, and market participants as rationallybounded, self-interested individuals, like in Neo-Austrian {Hayek #952} or NeoInstitutional Economics {North #1308}{Furubotn #1811}. As we move on to technology, which allows us to map unstructured semantic knowledge in large and very dynamic sys-