M
denote a generic "machine" in the NCS.
by
Alok Gupta
Department of Management Science and Information Systems
University of Texas at Austin
Dale O. Stahl
Department of Economics
University of Texas at Austin
and
Andrew B. Whinston
Department of Management Science and Information Systems
University of Texas at Austin
December 1994
The operation of a networked computing system (NCS), such as Internet, can be viewed as a resource allocation problem, and can be analyzed using the techniques of mathematical economics. We define a general NCS and translate that setup into a model of an economy. The preferences of users are taken as primitives, and servers (providing database services including entertainment and news or computational services) in the network are viewed as productive firms with priority input queues. Each server charges a rental price for its services by priority class. We characterize optimal system allocations, and derive formulae for supporting rental prices and priority premia such that the aggregated individual user demands do not exceed optimal levels and waiting-time expectations are correct. We propose and implement a decentralized price adjustment process. Some results from a simulation study are presented and discussed. Profit measures for each server can be used to guide investment decisions.
1.Introduction
A networked computing system (NCS) offers the potential for harnessing the power of a large number of possibly specialized computers linked through a network. The scientific community is currently exploring the development of a nation-wide network of computers with diverse software to enhance the opportunities for scientific research. In the business world there is a continuing shift away from exclusive reliance on mainframe computing. Companies are rapidly investing in a vast array of computers interconnected through a network to support distributed computing. The explosive growth of worldwide networks and their interconnection through Internet are already well recognized. There are already reports of substantial service delays on the Internet [Markoff, 1993]. The projected growth in commercial services that will appeal to both the home and business areas will make networking a major commercial development during the remainder of this decade.
Broadly defined a NCS consists of a network of heavy-duty computers (such as mainframes and minicomputers) called "servers", and smaller user-interface processors (such as PCs, Macintoshes, workstations, and eventually a computer that will be marketed as an enhanced home television system) called "clients",[1] along with other equipment (such as storage devices, printers, ethernet cabling, microwave channels, routers, etc.), the operating systems and communication protocols. Servers respond to queries or commands from clients and provide a shared computing environment, application control, distributed databases, computation management, heavy-duty computation, and network communication services. The services offered by individual servers can be quite diverse. For example, a server may have specialized software to perform large-matrix inversions, another may have a specialized data base containing information on Japanese electronic companies, while another server may contain interactive games or home shopping information.
A client, unlike a dumb terminal, is capable of modestly sophisticated processing and computation tasks for the user, including security and access control, running local application programs, and relaying user requests for services to appropriate servers. Clients could also have software designed to assist the user in achieving optimal performance from the NCS, and it is this potential that we exploit in this paper. [For a more detailed discussion of NCSs, see Sinha (1992).]
While a NCS offers the potential for substantial gains in productivity, inefficient pricing of NCS services (such as free service, average cost pricing, or profit center delegation) can lead to substantial problems, including: inefficient utilization of NCS services, excessive congestion which imposes excessive delay costs on all users, inappropriate investment decisions and poor system design due to distorted benefit-cost assessments.
A major challenge is how to effectively manage such systems in a diverse and changing environment. As a corporate-wide service: which users should have dedicated clients and which clients should have access to what server resources, during what times? Another important issue is the basis for financial support. How should users be charged for services? Should some of the costs of the system be a corporate expense? How do we justify altering the size of the network? Attaining efficient utilization of a NCS is a challenging research area with significant potential payoff. The goal is to design an overall mechanism that coordinates the use of the NCS so that total net benefits are maximized. Since this task is essentially a resource allocation problem, economic theory has the potential to help solve the problem [e.g. Chaudhury, Stahl and Whinston, 1990; Hogg, 1990; Ferguson, Yemini, and Nikolaou, 1988].
The economic approach we take can be viewed as an extension of the literature on performance evaluation of computing systems. The computer science branch of that literature assumes fixed steady-state arrival rates of jobs and analyzes the resulting steady state queue lengths in the system. A summary of the results and extensive biography can be found in [e.g. Kleinrock (1975, 1976), and Chu and Lan (1987)]. While we draw upon results from the queuing field, our contribution is in the economic analysis of NCSs.
Rather than specify fixed arrival rates, the management literature has explored the potential for prices to affect the arrival rates and thereby the steady state queue length. Naor (1969) introduced the possibility of controlling the steady state length of a single-server case queue by introducing prices for the service. Mendelson (1985) extended and applied Naor's model to study computer resource allocation for the single processor case. Prices were determined to allocate computing services under various organizational objectives, including maximal welfare of users, revenues generated by the prices used to cover the cost of the computing system and pricing to maximize the profits derived from selling computer services. Sanders (1988a) applied this approach to the problem of allocating links in a communication network, and Sanders (1988b) derived an incentive compatible reporting scheme to achieve the optimal allocation. Mendelson and Whang (1990) extended Mendelson's (1985) model to derive optimal incentive compatible priority pricing for the single processor case with Poisson arrivals [see also Dolan (1978).] The case of a general NCS with priority queues and general price-sensitive stochastic arrivals is the subject of our paper.
Our approach is to apply the analytical tools of general economic equilibrium theory. We first develop a formal model of a NCS that lends itself to economic analysis, in which the servers are analogous to producers in an economy, and the clients are analogous to competitive middlemen arranging for supplies to satisfy consumer demands. To each server is attached a priority queue system.
Recognizing that a NCS does not exist in isolation, we view the needs for NCS services as arising from their usefulness outside the NCS. For example, organizations need services such as issuance of financial statements, calculation of bridge loads or simulation of guidance systems, while other users want to access specific data bases stored at various servers. We assume that the stochastic arrival process of these needs can be adequately characterized by an "average flow" rate. [This approach is standard in computer science; e.g. see Dijkstra (1973) and Kleinrock (1975, 1976).] Ultimately the expressed demand for services depends not only on the benefits from the average flow of services but also on the expected throughput time of the NCS and the monetary
costs.
A rental price and an expected waiting time are associated with each priority class at each server. Given this data, a user's client evaluates and selects a cost-minimizing program and priority class. The demand (flow rate) of service requests from a client depends on the net benefits to the user, and hence is sensitive to the rental prices. Optimal service demands are then translated into loads on individual servers by priority class and aggregated over all clients.
With a system of queues, there is a trade-off between greater throughput volume and longer waiting times. An optimal allocation of resources will maximize total welfare of all users. We prove that there is a unique welfare-maximizing allocation, and we derive the rental prices by priority class that support this optimum as a "stochastic equilibrium". That is: (i) client flow rates are optimal for each user given the rental prices and anticipated waiting times; (ii) the anticipated waiting times are the correct ex ante expected waiting times given the average flow rates; and (iii) the aggregate average flow rates are equal to the welfare-maximizing rates.
Notice that our concept of a stochastic equilibrium is quite different from an Arrow-Debreu equilibrium with complete markets in which the rights to each processing cycle at each server for all time would be auctioned off, and the precise loads for each moment of time would be determined. That approach would be hopelessly unrealistic and infeasible. Our concept also differs substantially from a Nash equilibrium [e.g. Lee and Cohen (1985)] in which every user must know every other user's preferences and demands for all time and must choose a strategy for submitting requests that is a best response to all other users' strategies. That approach is also unrealistic in its informational demands.
Rather than an exact allocation that these two familiar concepts seek, we seek a stochastic allocation - a determination of average flow rates - that permits some imperfections manifested by queues with positive expected waiting times, and we adjust rental prices to optimize the tradeoff between greater throughput volume and longer waiting times. We take for granted that the first-best solutions cannot be implemented in real time because they require infeasible computational and informational resources. Our solution, while "second-best", is an optimal solution within the constraints of having only spot prices rather than complete Arrow-Debreu contracts and limited common knowledge among the users. Further, we maintain that our solution is feasible from an informational and computational point of view.
Next, we turn to the question of implementing this solution. That is, how do we find the equilibrium rental prices by priority class? One approach would be centralized computation. However, in the interest of developing a decentralized mechanism, we favor the alternative approach based on the classic tatonnement process [Hahn, 1982]. We have conducted simulation testing of our proposed price-adjustment process and have found very encouraging results. Some results are presented here, a detailed report will be the focus of a future paper.
Finally, assuming successful implementation of equilibrium pricing, NCS managers can use the profitability of each server (based on rental prices) to guide investment and design decisions so a NCS can evolve over time to more effectively serve the clients. While numerous assumptions are made to rationalize the existence and determination of prices, the ultimate evaluation of the effectiveness must await further testing, implementation and comparison with other resource allocation mechanisms designed to manage a NCS.
The paper is organized as follows. Section 2 presents the formal model of the NCS that lends itself to economic analysis. Section 3 describes user preferences, and choice of optimal computation plans. Section 4 derives our main theorems and shows how a welfare optimum can be supported as a stochastic equilibrium. All proofs are relegated to an Appendix. Section 5 presents implementation methods, and Section 6 discusses our simulation study. Finally, Section 7 concludes with an assessment of the power and practicality of our economic approach to the design and management of large-scale NCSs such as Internet, and a brief indication of areas for future research.
2. Description of a NCS.
We consider a NCS consisting of a finite number of clients, servers and other
hardware units with well-defined, commonly known, possibly diverse
capabilities. Examples of specialized hardware units include an ethernet
system, multi-server queues that route services to the next available
processing unit, external disk storage devices and controllers, and output
interfaces. Clients and servers are computers with diverse capabilities, with
servers generally having more computational capacity, speed and often having
specialized software, including business and home oriented data bases. Let M
denote the set of all clients, servers and hardware units, and let m
M
denote a generic "machine" in the NCS.
We assume that each machine is equipped with a priority queue system. For
notional simplicity, we assume that each machine offers K classes of
non-interruptable priority service, K
{1,
..., K}, with k = 1 being the first (or highest) priority.[2] For analytical simplicity, we assume
unlimited queue capacity. We hasten to point out, however, that in equilibrium,
the expected queue lengths are finite, so for practical purposes, sufficient
finite queue capacity would suffice and yield qualitatively similar results.
The machines are connected with each other through a network. We model shared
communication devices (such as data bases and ethernets) as distinct machines.
Thus, the Internet is a special case of a general NCS. Given this modeling
trick, the abstract network will consist of direct connections only; that is,
if m and m' are directly connected in the network representation, then there
exists a dedicated physical linkage between m and m' that is not shared by any
other machine. Let
denote the set of machines from which m can receive direct input, and let
denote the set of machines to which m can send direct output. We can formally
represent the abstract network as
.
In addition, let C denote the subset of "clients" machines: the machines where
users interface with the NCS.
A typical NCS will support many programming languages. Let P denote the set of all finite "programs" in the languages of the NCS system. While a program could be a specification of required computations in a multi-processor network, it could also be interpreted as a specification of a collection of high-level services desired by a user, such as different news services, leaving to the client machine or a server the task of specifying the detailed code and routing. We can always structure programs so there are two distinguishable components: instructions and data. The instructions specify (among other things) the client machine where the program starts. A machine reads the instructions, carries out whatever operations are called for on the data (and instructions), and then routes the output according to the instructions. Machines also pass through to the output, instructions which are then carried out by successor machines. Thus, inputs to machines are viewed as "batch" programs complete with all relevant data and output disposition instructions.
A machine m
M can be represented by a triplet
,
where
is
the processing speed in cycles per second,
gives the output when p
P is the input, and
gives the expected number of cycles required to process input p. Then,
is the expected execution time of program p at machine m. Note that restricted
access to a particular machine (such as a user's client) can be represented by
a production function that performs the desired function only if p contains a
specific access password, and otherwise outputs an access-denied message. In a
similar vein, a machine not capable of executing some program, outputs an
unable-to-read message, and if the run time exceeds the limit (if any)
specified in the program, then it outputs a time-exceeded message.
Given a stationary stochastic arrival process for services, let
denote the vector of expected queue waiting times at the machines. As just
illustrated, a program may access a given machine several times in the course
of executing. Let
,
the number of intermediate programs of p that must be processed at machine m.
Then, program p of priority class k has an expected waiting time of
at machine m.[5]
Finally, assuming that a user chooses a single priority class, say k, for all phases of the execution of a program p started at the machine specified by the program's instructions, the total expected throughput time is
3. Users, Preferences and Demands.
Let I denote the set of users, and for each i
I let
denote the set of client machines to which user i has direct access. While
there is a close linkage of users and clients, we will continue to employ both
terms in specific contexts. The user is a human (or group of humans in an
organizational team) with preferences which form the basis for choice. In
contrast, the client is a machine, and as such, has no preferences of its own.
While we may endow the client machines with sophisticated software to automate
many of the decision-making functions, the source of value resides with the
human user. For example, in the case of home use, a family member may want a
collection of services from the network (a bundled product). The client
machine in the home, configured for this family, would figure out the best way
to obtain the desired services, and might give options such as: "you may obtain
these services now for a cost of $75, but if you can wait until after 5 PM, it
will cost you only $25."
It is extremely useful to think of users as desiring some specific NCS service
(such as a financial report) while being indifferent over alternative programs
that can deliver that service satisfactorily. We can then focus on the task of
identifying efficient programs for given services. Let S denote the class of
services potentially provided by the NCS. Services s
S can be viewed as subroutines which operate on the specific data, provided
that the characteristics of the data (such as size and format) are compatible
with the subroutine. Different qualities (such as precision) are represented
formally as different services.
Since programs specify the client machine at which they must start, the set of
feasible programs for user i is a subset of all possible programs. We let
denote the subset of programs that will successfully deliver service s for user
i; that is, if a user i initiates execution of program
at the appropriate machine
,
then the NCS will execute the program and return a satisfactory output.
We model the NCS service needs of a user as a stochastic process with a
specific arrival rate (or "average flow" rate). One setting that makes this
assumption quite plausible is that a user is a group of individuals (such as a
team of engineers or accountants), so the flow of service needs are the sum of
the service needs from many individuals. Let
denote the vector of average flow rates for user i, where
denotes the average flow rate by user i for program
of priority class k.[6]
We assume that the user benefits of NCS services depend only on this average
flow rate. We represent the instantaneous value to user i of
by a continuously differentiable concave function
.
This general representation encompasses substitutabilities and
complementarities among different services. In other words, it allows users to
evaluate qualities of alternative programs and services, and to link the value
of several service needs (such as payroll processing and financial statements).
Given our definition of a service, all
and k
K are perfect substitutes in terms of user benefits. Accordingly, we assume
that
depends only on
,
the flow rate for service s, and that
is strictly concave in
.
The net benefit to the user is less than
because services take time to execute and it costs money to use the NCS.
Different programs in
may have different costs, so consider each program
separately. The expected throughput time of program p and priority k is
,
as defined in equation (1). Let
denote user i's delay cost per unit time for service s, so
is the total expected cost of delay of using program p.
Expected money costs are determined by the expected load imposed by the
program p, the priority class k, and the rental prices of the machines. Let
,
where
is the rental price for q units of work with priority k at machine m. This
general form allows the rental prices to depend on the job size in a general
non-linear manner (e.g., quadratic in a M/G/C system). Then, the expected
monetary cost of program p and priority class k is
.
It is convinient to derive an alternative equivalent expression for this
expected cost.
This task of finding the minimum-cost program could be subsumed by software in
the user's client machine.[7] Let
denote the set of pairs of programs and priority classes that minimize total
expected costs for services.[8] By standard
arguments,
is a continuous convex function.
We assume that user i does not anticipate how his service demands and choice of programs may affect expected waiting times w and rental prices r. This simplifying assumption corresponds to the standard competitive price-taking assumption of economic theory, and can be justified in this context in several ways. First, in a large-scale NCS such as the Internet, the number of clients is so large that the influence of one client on expected waiting times and rental prices is negligible. Second, a user can be a group or team, so the total number of individual humans interacting with the NCS can be substantially larger than the number of client machines. While team members may share common preferences, it is also realistic to model their individual decisions as essentially independent. Then, given a large NCS with many independent human decision-makers, each such decision-maker will have a negligible effect on expected waiting times and rental prices. Third, the user's decision must be based on expected waiting time and rental price data at the time of submittal, and because the actual waiting time a job will experience depends on what all users have submitted in the recent past and in the future, it would be impossible for the user to predict precisely how future waiting times and rental prices will differ from their current values. In a large NCS, the actual influence of a user's submittal on future waiting times and prices will be minuscule in comparison to the variance induced by other users. Thus, it is a reasonable and computational-cost-saving assumption to take expected waiting times and rental prices as fixed at their current values.
Accordingly, each user i is assumed to choose
to maximize
[9]
taking (r,w) as fixed, and we let
denote the set of optimal demands.[10]
Specifically,
is characterized by
Then the demand function for services,
,
is finite, single-valued and continuous for all non-negative (r,w).[11 ]
We pause to interpret the act of choosing flow rates
.
We envision a world in which questions or desires (that might require NCS
services) arise from some natural process (for example, a manager needs some
special financial report, an engineer needs some design calculation, a family
member desires information about various products, etc.). These
questions/desires, in turn can be translated into requests for NCS services.
Thus, we model the arrival of potential NCS service requests as an exogenous
stochastic process that is independent of the pricing of the NCS. Suppose the
exogenous arrival rate of questions requiring NCS service s is
,
with the interpretation that if the minimum cost of delivering s were 0, then
would be the average flow demand for service s. A user receiving one of these
questions must decide whether or not to actually request NCS service. Let
denote the probability of accepting the question and submitting service request
s. Given the exogenous arrival rate
,
the average flow demand for s from this user will be
.
Thus, the choice of
is equivalent to the choice of an average flow rate
.
The optimal choice maximizes equation (3) and equates the marginal benefit
with the cost
.
Figure 1 illustrates this optimization graphically. The downward-sloping
"demand" curve gives the marginal benefit of service s as a function of the
average flow rate of service s. For example, the marginal benefit of quarterly
financial reports may be $500 each, while the marginal benefit of monthly
reports may be only $200 each. The horizontal "supply" curve gives the cost
.
An exogenous change in
would shift these curves, thereby causing a change in the optimal
.
Observe that we have resolved the well-known integer nature of computation
problems. While each service s is an indivisible entity, we have treated the
demand choice as if it could be subdivided in any matter to accommodate the
certainty-equivalent flow rate of
.
However, in actual implementation, the service requests enter the NCS as
indivisible units. We accommodate this integer requirement by modeling the
arrival process as a stochastic process with arrival rate
,
and we hold input in the machine queues until ready to be processed. The
resulting delays are reflected in the waiting times w.
4. Optimal Resource Allocation and Stochastic Equilibrium.
To derive the optimal trade-off we need to define a system-wide welfare function. It is natural to take the sum of non-pecuniary user benefits:
We assume here that there are no costs to operating the NCS and the services, so the only social costs are due to congestion. However, it would be a trivial matter to extend the analysis to include positive operating costs.
We now seek an allocation of demands,
,
and waiting times w, that maximize W(x,w) subject to equation (6). The
Kuhn-Tucker conditions of this welfare maximization are [see the Appendix]:
where
is
the Lagrangian multiplier for equation (6). Equation (9) defines the shadow
price of waiting time for priority class k at m. Equations (8) requires the
marginal net benefit of service s at priority class k to be less than or equal
to the total shadow cost of the induced incremental waiting times; if less,
then the optimal
= 0.
Let
.
In the Appendix, we prove:
5. Implementation: Price Determination.
The solution to the NCS resource allocation problem we propose is to charge welfare-maximizing rental prices for each machine in the NCS. Given such prices, the charges could easily be implemented by adding to each user's client software the capability of computing the appropriate charge for each service, or by dedicating a central NCS machine to the task of billing.
The task of determining the welfare-maximizing prices requires information
about (i) the flow rates,
,
(ii) the expected waiting times,
,
and (iii) the user's cost of delay parameters
.
The choice of priority classes by users reveals their underlying delay
parameters. A sampling and estimation procedure could be developed to extract
this information from data on those choices.
Our recommended approach to finding equilibrium prices is motivated by the classic tatonnement process [Hahn, 1982]. Heuristically, one wants to raise the rental price when the social costs of delays at a queue are excessive, and vice versa. We first describe the method of obtaining the required information for the tatonnement process.
To ensure stability, the time required to measure accurately the statistics of the stochastic flows and queues should be small relative to the time between rental price adjustments, which in turn should be small relative to changes in the external environment (e.g. exogenous changes in NCS services demanded).
Although stability is more likely to be attainable for stationary environments (users and services), simulation testing could be employed to experiment with gradually changing environments. There will be a trade-off between rapid adjustment to the equilibrium on the one hand, and the stability of the process on the other. In addition, simulations would provide evidence of the potential gains in NCS efficiency from optimal rental prices.
We have begun simulation testing in specific environments to explore these stability issues. Preliminary testing is very encouraging. For a NCS consisting of ten processors, five distinct services, a distribution of user delay costs and demand elasticities, we have had little difficulty in achieving rapid convergence of rental prices accompanied by significant reductions in expected waiting times and significant increases in net user welfare. We present a description of simulation study and some results in the next section, the complete study will be reported in a future paper.
6. Simulation Results.
In this section, we present a simple simulation model of a NCS and explore preliminary results to investigate the issues of stability and convergence of the rental prices. Additionally, we offer a comparison of system performance with rental prices and system performance without any prices (zero prices). Note that simulations without prices are equivalent to the minimization of throughput times, where queue waiting time information is updated from time to time. For the preliminary simulation study, we developed a small model of a NCS, this model has 10 machines with capacities ranging from 10 to 100 cycles/time-unit and supports multiple-priority, non-interruptable programs. In the results presented here, we limit our discussion to single priority (non-priority) and two priority cases. The NCS provides 5 services and there are 100 programs which can provide a given service. The period length was fixed at 100 units of time and the simulation length was fixed at 500 updates or 50,000 units of simulation time. The computer simulation model has been developed under the framework of CISM[13] simulation programming language under the HP-UX operating system on HP workstations.
Table 1 provides information associated with the services. Column 2 provides the probability that an incoming request is for a particular service, e.g., 0.1 for service 1. Different service types require different cycles of work at the machines of NCS; for a given service, we generate the amount of work required, at every machine, from a discrete uniform distribution. Column 3 of Table 1 provides the parameters of the uniform distributions (used for generation of units of work at a machine / visit) for different services. For example, in the schemes for service 4, we will have 25 to 100 cycles of work (per visit) at a particular machine. Table 2 provides an example program for service 4.
We specify an aggregate exogenous Poisson arrival rate,
,16
and then the type of the service desired is identified using the probability
distribution given in Table 2. Then a minimum cost program is chosen from the
100 available programs. Next, we use a cost sensitive demand function to
decide whether the job should actually be submitted to the NCS. We use a
linear demand function of the following form:
where
is
the flow rate of service type j = 1, ..., 5,
is
the probability as defined in Table 2,
is the sensitivity of demand to cost, and
is the estimated minimum cost for completing the job. Clearly, the maximum
flow occurs when
is
zero and this maximum flow is
.
The choice of constant
was
based on the cost data accumulated over test runs; the constant values,
,
for all the 5 services was 1200. We use equation (14) to determine whether a
given request is actually submitted to the NCS.
It can be easily verified that the demand function used here, i.e., equation (13), is derived from a utility function of the following form:
Now, following the arguments presented in Section 5, the net benefits to the system can be computed as:
where the last summation in the equation is total cost of delay suffered by the customers. We use the net benefits to evaluate the system performance with and without pricing for several different arrival rates.
We approximate the queues at all the machines by a M/G/1 queue with priority
classes. In this simulation model a program provides the cycles of work to be
done at each machine and the routing. If q cycles of work has to be done at
machine m, with capacity
,
during some particular visit, then the service time is deterministic and is
equal to q/
.
Thus, the waiting time function
at
machine m becomes
where
,
is the utilization ratio of machine m in priority class k, rest of the
parameters are the same as defined in earlier sections. The partial
derivatives of
are
then computed and used in calculating estimates of new prices in the each
period as described in the last section.
There are several factors which affect the stability of the rental prices: (i)
the length of time interval between successive updates, (ii) amount of
historical data used to estimate the performance parameters of the
machines(e.g., utilization ratio), and (iii) the price adjustment parameter
. After some experimentation, we decided to use an update interval of
100 time units and the historical data for the past 15 updates to estimate the
performance parameters. Figure 3 shows the behavior of the rental prices at
machine 1 for two values of the adjustment parameter , namely 0.1 and
0.2. The figure indicates that the rental prices converge, i.e., they vary in
a small neighborhood of a mean value. Clearly, at
= 0.1 the variation of rental price is significantly lower than that at
= 0.2. In general, a higher value of
may be associated with quicker convergence, but will have a higher variation.
Thus, the choice of an adjustment parameter depends upon the environment being
modeled. For example, if the exogenous arrival rate changes rapidly then a
higher value of
might be desired, and more variability in the rental prices has to be
tolerated. However, if the arrival rate is reasonably stable then a smaller
value of
may be desired, since once the prices converge, the rental prices will have
small variance. In the rest of this section we use
= 0.1.
We now present a comparison of system performance with and without the suggested pricing scheme. Table 3 compares the mean waiting times for cases: (i) without pricing, (ii) pricing with one priority class, and (ii) pricing with two priority classes. Clearly, the mean waiting time is significantly reduced with pricing for all the machines. Thus, pricing improves the system performance from the standpoint of mean waiting time suffered by each job.
Figure 4 presents the cost of delay suffered by the customers (per unit time) for several different arrival rates for the three cases mentioned above. It can be seen that cost of delay is greater at all the different arrival rates when the pricing scheme is not used, furthermore, the cost of delay is marginally smaller with two priority pricing as compared to single priority pricing. Figure 5 presents the benefits accrued (per unit of time) for several different arrival rates. The net benefits (equation 15) and private benefits (net benefits - rental cost) are smaller in all the cases when the pricing scheme is not used.[14] Again, the two priority pricing provides marginally better benefits than single priority case. As the arrival rate decreases, the improvement due to pricing becomes smaller; this is consistent with our contention that, as the congestion becomes smaller, the net benefits realized (due to pricing) would be smaller.
The results from the simulation experiments can be summarized as follows:
(i) the iterative approach proposed in Section 6 converges to provide stable rental prices,
(ii) the choice of the adjustment parameter depends upon the environment,
i.e., if the external demand environment is highly variable, a relatively high
value of
might be desirable and vice versa,
(iii) introducing the pricing mechanism results in better system performance by reducing the waiting time suffered by the jobs in the queues. This results in lower delay costs and higher net and private benefits to the system.
We believe that these results are encouraging and indicate that a stable rental pricing scheme can be developed and implemented. As indicated earlier, there are still many issues to be studied, for example: how will a rental pricing mechanism such as this react to gradually changing arrival rates? What strategies could be used to determine the appropriate update time and amount of historical-data for parameter estimation? How do we identify problem areas, e.g., a machine that should be removed? We are pursuing an extensive simulation study to explore these issues and will present these results in the future.
7. Conclusions.
The coordination of users of a NCS to achieve efficient utilization of the resource is a complex and important problem. With the expected growth of NCS an inefficient coordination mechanism will cause significant economic losses. Computer scientists have considerable experience in creating coordinating mechanisms that are part of a networked operating system. While these mechanisms do coordinate the different processors, there has been no attempt to develop optimal solutions. The issue we explored is the design of a mechanism that can potentially achieve the highest level of resource allocation. To achieve this goal, we have successfully modeled a NCS with priority queues and general stochastic arrivals as an economic resource allocation problem.
The social welfare maximization problem was specified and solved to define the
optimal allocation of resources. We then derived rental prices for each
priority class at each machine that would support the optimal allocation as a
decentralized stochastic equilibrium. Given optimal expected queue waiting
times
and optimal rental prices
,
users independently choose when and how many service requests to submit. The
aggregation of these submittals constitutes a stochastic process that generates
queue waiting times
.
Moreover, the average flow rates and queue waiting times maximize social
welfare.
We suggested a dynamic tatonnement process for implementing this pricing solution. We implement this dynamic tatonnement process using simulation, the results are very promising. However, further study involving simulations is needed to determine how to ensure desirable dynamic properties, improve prediction mechanisms, and explore investment issues.
We underscore the need to develop user-interface software that would be installed in client machines to perform many of the crucial programming and evaluation functions. A user of any NCS must translate his service needs into NCS code, and automated user-friendly methods of accomplishing this task are being developed and improved all the time. We suggest enhancing this function by including the ability to estimate the load requirements. Given NCS provided information about current rental prices and expected waiting times, it is a simple matter to compute the expected cost of alternative programs and priority classes. We note that peak-load pricing of existing mainframe systems induces significant changes in user behavior, and we argue that users will have considerable incentives to use this cost information when designing programs and requesting services, thereby bringing about significant improvements in NCS resource utilization.
Our economic approach has the added benefit of providing a sound basis for evaluating NCS investment alternatives, using a process analogous to free entry and exit in free-enterprise economies. In other words, a by-service of optimal pricing is an economic approach to engineering design. All of these theoretical advantages motivate further study. In addition, the system impact and profitability of a new service installed on a server, such as home shopping, could be investigated via simulation in much the same way as for infrastructure investments
In future research we will consider alternative priority queue systems and incentive compatibility issues.[15] We will also extend the theoretical model to account for organizational constraints such as the need to recover the cost of operating the NCS. In this context, notice that the optimal rental prices could generate significant revenue, perhaps adequate enough to cover operating costs. In any event, introducing additional constraints to the welfare optimization will lead to a different expression for the rental prices and will raise questions about the role of these prices and their determination.
There are many issues yet to be explored before a pricing mechanism can be successfully integrated into a networked operating system. Some of these issues deal with the determination of prices and the development of adequate software for clients to enable them to quickly price alternatives. Once we have an operational system, we can compare, using simulation techniques, the performance of a NCS, using our coordination mechanism, with other allocative mechanisms. Clearly, the discovery and validation of a superior mechanism would have great significance.
REFERENCES
Arrow, K., and Intriligator, M. (ed), Handbook of Mathematical Economics, Volumes I-II, North- Holland, 1982.
Chaudhury, A., Stahl, D., and Whinston, A., "The Economic Theory Foundation for Neural Computing Systems," in A. Whinston and J. Johnson (eds.), Advances in Artificial Intelligence in Economics, Finance and Management, J.A.I. Press, 1992.
Chu, W., and Lan, M., "Task Allocation and Precedence Relations for Distributed Real-Time Systems," IEEE Transactions on Computers, 36, 667-679, 1987.
Cinlar, E., "Superposition of Point Processes," in Stochastic Point Processes: Statistical Analysis, Theory and Applications, 549-606, P. Lewis (ed), Wiley, 1972.
Debreu, G., The Theory of Value, Yale University Press, 1959.
Dijkstra, E. "Self-stabilizing Systems in Spite of Distributed Control," Communications of the ACM, 17, 643-644, 1973.
Dolan, R. J., "Incentive Mechanisms for Priority Queueing Problems," Bell J. of Economics, 9, Autumn 1978.
Ferguson, D., Yemini, Y., and Nikalson, C., "Microeconomic Algorithms for Load Balancing in Distributed Computer Systems," Research Report, T.J. Watson Research Center, Yorktown Heights, New York, October 1989.
Francis, Bob, "Client/Server: The Model for the 90's," Datamation, 34-50, February 1990.
Hahn, F., "Stability," in Handbook of Mathematical Economics, II, Ch. 16, Arrow, K. and Intriligator, M. (ed), North-Holland, 1982.
Hogg, T., "Primed for Performance," Byte, 241-250, June 1990.
Intriligator, M., "Mathematical Programming with Applications to Economics," in Handbook of Mathematical Economics, II, Ch. 2, Arrow, K. and Intriligator, M. (eds), North-Holland, 1982.
Kleinrock, L., Queueing Systems, Volumes 1 and 2, Wiley, 1975 and 1976.
Lee, L.L., and Cohen, M.A., "Multi-Agent Customer Allocation in a Stochastic Service System," Management Science, 31, 752-763, June 1985.
Markoff, J., "Traffic Jams Already on the Information Highway," New York Times, November 3, 1993, page 1.
Mendelson, H. "Pricing Computer Services: Queuing Effects," Commun. ACM, 28, 312-321, 1985.
Mendelson, H., and Whang, S. "Optimal Incentive-Compatible Priority Pricing for the M/M/1 Queue," Operations Research, 38, 870-83, 1990.
Naor, P., "On the Regulation of Queue Size by Levying Tolls," Econometrica, 37, 15-24, 1969.
Sanders, B., "An Asynchronous, Distributed Flow Control Algorithm for Rate Allocation in Computer Networks," IEEE Transactions on Computers, 37, 779-787, 1988.
Sanders, B., "An Incentive Compatible Flow Control Algorithm for Rate Allocation in Computer Networks," IEEE Transactions on Computers, 37, 1067-1072, 1988.
Sinha, A., "Client-Server Computing," Communications of the ACM, 35, 77-98, July 1992.
Stahl, D., "Stochastic Decentralization of Competitive Allocations," Economics Letters, 22 (2), 111-113, 1986.
