US 5,640,569 A · Diverse goods arbitration system and method for allocating resources in a distributed computer system

Abstract

A diverse goods arbitration system and method allocates computer resources among bidding requesters. Bid slates are transmitted to an arbiter by users (requesters) requesting use of specified portions of the available computer resources. Each bid slate may contain a plurality of bids, each bid representing a requested set of resources and a bid price. The arbiter selects combinations of bids from the bid slates, where each bid combination consists of no more than one bid from each of the received bid slates. The arbiter rejects all bid combinations whose constituent bids exceed an established maximum allocation level for any computer resource. It then selects as a winning bid combination the bid combination having the highest total bid price. Computer resources are then allocated for a next time period based on the winning bid. Costs are allocating to each successful requester in accordance with a predefined opportunity cost function. In particular, for each successful requester, the arbitration process is repeated while excluding that successful requester's bid slate from the set of bid slates considered, resulting in the selection of a second winning bid that excludes the successful requester. The successful requester is then assessed a cost corresponding to the difference between the winning bid's total bid prices, excluding the price in the successful requester's granted bid, and the total bid prices associated with the second winning bid.

Claims8

Dependent claims

A method of allocating a plurality of computer resources among a plurality of users, comprising the steps of:

(A) transmitting to an arbiter bid slates from ones of said users (requesters) requesting use of specified portions of said computer resources, at least a plurality of said bid slates including a plurality of bids, each bid in each bid slate representing a requested set of resources, composing a specified subset of said plurality of computer resources, and a bid price;
(B) at said arbiter:
(B1) storing data representing a maximum allocation level for each of said plurality of computer resources,
(B2) receiving said bid slates;
(B3) selecting for analysis combinations of bids from said bid slates, where each bid combination consists of no more than one bid from each of said received bid slates, rejecting all those of said bid combinations whose constituent bids include requests for one or more of said computers resources in excess of the corresponding maximum allocation levels for those computer resources, and selecting as a winning bid combination one non-rejected bid combination that includes bids which place highest value on use of said plurality of computer resources;
(B4) allocating to each successful requester having a non-zero bid included in said winning bid combination a cost in accordance with a predefined opportunity cost function;
and
(C) allocating said computer resources among said successful requesters in accordance with said winning bid.

5 more elements

An arbiter for allocating a plurality of computer resources among a plurality of users, comprising:

a receiver for receiving bid slates from ones of said users (requesters) requesting use of specified portions of said computer resources, at least a plurality of said bid slates including a plurality of bids, each bid in each bid slate representing a requested set of resources, composing a specified subset of said plurality of computer resources, and a bid price;
arbitration apparatus, including:
memory for storing data representing a maximum allocation level for each of said plurality of computer resources and for storing said received bid slates;
bid selection means for selecting combinations of bids from said bid slates, where each bid combination consists of no more than one bid from each of said received bid slates, rejecting all those of said bid combinations whose constituent bids include requests for one or more of said computers resources in excess of the corresponding maximum allocation levels for those computer resources, and selecting as a winning bid combination one non-rejected bid combination that includes bids which place highest value on use of said plurality of computer resources;
and
cost allocation means for allocating to each successful requester having a non-zero bid included in said winning bid combination a cost in accordance with a predefined opportunity cost function;
and
a transmitter for transmitting one or messages that allocate said computer resources among said successful requesters in accordance with said winning bid.

5 more elements

Dependencies are inferred from the claim text.

Diverse goods arbitration system and method for allocating resources in a distributed computer system

Life of this patent

Diverse goods arbitration system and method for allocating resources in a distributed computer system

Life of this patent

Abstract

Claims8