Bids, Offers and Prototype

I'd like to begin this post with an analysis of the necessary properties of bids and offers. In other words, of which parts does an bid or offer exist?

A bid should contain the following information:

• Details about the consumer that made the bid
• A specification of the required set of resources 
• Time constraints (spot/future bid, in which time frame should the requested resources be available)
• Price constraints (max price, price tolerance) 

A offer should contain similar information:

• Details about the provider that made the offer
• A specification of the offered set of resources
• Time constraints (spot/future bid, in which time frame are the offered resources available)
• Price constraints (min price, price tolerance) 

The bids and offers should thus contain the same kind of information.
The 'details about consumers or providers' should contain some general information about the client (name, email, address, etc), accounting information (credit card number), and possibly some more technical consumer details (public keys, certificates, etc).
To define the resources that are part of the bid/offer, I think I'll go for Dube's resource sets (this is the most logic approach).

This means that we define the required resources as a set. Each resource in the set is of a certain type (e.g. cpu_architecture) and has a certain value (e.g. x86). By using sets we can allow the specification of partial resource sets, that is, a resource set does not need to contain a value for all the available resource types.

For example, the following are both valid resource sets:

• {cpu_architecture:x86, cpu_clock: 2.2Ghz, memory: 2GB} 
• {cpu_architecture:x86, cpu_clock: 2.4Ghz, memory: 4GB, disk: 128GB, os: Ubuntu Linux 10.10}

Note that this allows for partial matching between bids and offers (as long as all requirements of the bid are fulfilled). For example, if the in the example above, the first set was a requirement set and the second set an offered set, the first set could be matched with the second set since the second set contains all the necessary resources.Matching the resource set is done by matching each of the items in the set with items in the matching set.

There are 2 different kind of matches that can occur here: exact matches and what I call 'inclusive' matches. An exact match means that the 2 resources need to have the exact same value (e.g. cpu_architecture: x86) in order to have a match. An inclusive match means that a resource is matched by a resource that is better (has a higher value) than the requested resource (e.g. cpu_clock: 2.2 Ghz is matched with cpu_clock: 2.4 Ghz).

This specification of resource sets is good enough to create a first implementation that allows matching. Further iterations can improve on this idea. More details about the other parts of the bids and offers (the time and price constraints in particular) will follow in a new blogpost.

IaaS Market: a first prototype

Based on this first definition of bids and offers, I decided to create a little prototype that already implements some of this functionality. The Java code can be found here. The prototype focuses on the definition of the resource sets. The UML scheme below gives an overview of the implementation of the resource sets.

Notice that I made a difference between Comparable resources (for which there exists a total order on its values; and inclusive matching is thus possible) and the NonComparable resources (for which an exact match is always necessary). By letting the comparable resources implement the Java Comparable interface it is possible to see if a value of a certain resource type is better than another value.

The prototype also includes a very basic emulator implementation that can generate random sets of resources, random bids and offers (at this moment those bids and offers only contain random resource sets, no time or price constraints) and can make bids and offers to a very rudimentary market. This market tries to do a matching using a simple matching algorithm: when a new bid or offer comes in, it searches the offer or bid list (queue) for an offer or bid that has a matching resource set. At this moment, the first match is always chosen. This means that it could be the case that there is a better match available (that would benefit the provider and consumer more), but in the current implementation this match is not returned. In order to do that, we first need to define what the 'best match' is.
I already have a few (unexplored) ideas about defining this 'best match'; I'll probably specify this more in a future post.

Note that all of this is implemented as a local console application; that is, no webservices have been used up to this point.
The zip-file contains a .project file to import the project into Eclipse. The emulator.Emulator class contains the main function.

Expect a post about price- and timeconstraints, possibly with a first definition of the 'best match' within the next few days.