X hits on this document

PDF document

google-cluster-auctions.pdf - page 5 / 8





5 / 8

longer desires anything. Taking the maximum across all buyers gives us a “price ceiling” beyond which the auction must end.

When “traders” are also present, the convergence issue be- comes much more complex. In fact, there are relatively small counterexamples with these types of users in which the clock auction never converges. These, however, are rather contrived and unlikely to be encountered in practice. Moreover, we hypothesize that there exist simple conditions (e.g., “traders” seek to buy more than they sell) which prevent these types of results. Proving these formally, however, is quite tricky and left as a topic for future research.

4) Discussion: Despite its apparent simplicity, the clock auction has a number of highly desirable features. First, and most significantly, it is computationally tractable. All else being equal, the execution time scales linearly in the number of participants and the number of resources. Solving for the prices in our experimental resource auction (having around 100 bidders and 100 system-level resources), for instance, took only a few minutes despite the fact that the underlying code was written in Python and was highly non-optimized. Optimized code written in a lower-level language could reduce this by at least one order of magnitude. See Section V below for more details.

Second, it is extremely robust. Irrespective of the system size, trade-dependencies between resources, the exact starting point, and other parameters, we have observed that it quickly reaches a “reasonable” set of prices and allocations. Unlike other algorithms, whose performance is extremely sensitive to the initial system parameters, the clock auction consistently generates plausible results on the first try.

Third, provided that it converges, the clock auction neces- sarily finds a feasible point for SYSTEM, i.e. a (x, p) pair at which there is no excess demand, prices are uniform, allocations are “fair,” etc. Just getting this is a very hard problem in larger systems, particularly when a significant fraction of participants are traders.

The obvious downside, however, is that this clock procedure does not explicitly optimize anything; while it finds a feasible point, it completely ignores the objective function, f(x, p), in its update steps. If there are multiple feasible points for SYSTEM (as there usually are), then there is no guarantee that the procedure will converge to the optimal one or even to one that is “near optimal.” This suggests that other algorithms, based explicitly on optimization, may be better choices if they can be implemented in a computationally tractable way. This is an exciting area of research, and one that we will detail in a future paper.


The performance of the clock auction depends heavily on the starting / reserve prices, p˜, chosen by the operator. As discussed above, these serve to guide the users as they calculate their bids and also affect the convergence speed of the clock procedure. More broadly, however, the reserve prices form a key input related to the economic engineering of the market for compute resources [13]. Specifically, the reserve


f 1 ( x ) = e x p ( 2 ( x 0 . 5 ) f 2 ( x ) = e x p ( x 0 . 5 ) f 3 ( x ) = 1 / ( 1 . 5 x )


weighted price multiple





  • 0




40 50 60 normalized resource utilization





Fig. 2.

Example utilization-weighted pricing curves.

prices form the basis of a decision support framework in the market economy that allows the operator to steer the system towards particular, desired outcomes. If one resource pool is particularly crowded, for instance, then the operator can set its reserve price high to ensure that users in this pool have the incentive to leave it for another, less crowded one. This also ensures that the operator gets a “fair price” when bringing new resources online. Ideally, the market handles these things automatically; this priming, however, may be necessary as the economy is “started up,” when participation is low and/or users do not fully understand how to optimally set their bids. In such cases of limited liquidity the use of a reserve pricing strategy based on some operator utility function allows the market to degrade gracefully into a market with fixed but differential pricing set to influence bidder behavior in the desired way.

As in [14] and [15], we use an approach that takes into ac- count the resource loads. For each resource pool r, we assume there is a well-defined metric of current (i.e., pre-auction) utilization, ψ(r). Furthermore, assume that each resource pool, r, has a real, known cost c(r). We then define our weighted reserve price for one unit of r as:

p˜r = φr(ψ(r))c(r) where φr(·) is the weighting function for r.


A. Weighting Function Properties

The weighting functions should accurately reflect the scarcity or abundance of resources in individual pools. In particular, we propose the following criteria for constructing these:

1 ) φ r ( · ) i s m o n o t o n i c a l l y i n c r e a s i n g 2 ) φ r ( · ) > 1 . 0 f o r r e s o u r c e s t h a t a r e o v e r u t i l i z e d i n a c l u s t e r 3 ) φ r ( · ) 1 . 0 f o r r e s o u r c e s t h a t a r e u n d e r u t i l i z e d i n a

cluster 4) The relative cost difference of resources in highly con-

gested clusters (e.g. 99% vs 80% utilization) is signif- icantly greater than the cost difference of resources in underutilized clusters (e.g. 40% vs 15% utilization) as

Document info
Document views25
Page views25
Page last viewedTue Jan 17 23:33:03 UTC 2017