Updated planning

Just wanted to post the (slightly) more detailed schedule I promised on monday.

I will be doing some writing on my thesis for the next few weeks,
albeit that I will have very limited time due to some exams I need to
study for. My goal is to have about 30 pages (medium quality) by the
first week of next semester (which starts on Feb 14th). I also want to
continue improving the prototype; possibly already adding some of the
ideas I have concerning price discovery.

In order to spread the actual writing work for my thesis, I'm going to
try to write about 5-10 pages each week during next semester (which is
a pretty strict planning, I think). I believe doing this will increase
the quality of the thesis.

I might be some time before I update the blog again because of the
afore mentioned exams.

Evaluation of my personal planning

Being 2 weeks after I made my planning, it is time to evaluate how I have done.
I've been able to write about 16 pages for my actual thesis. These 16 pages address various topics concerning both general market design as specifics about the market I'm designing. I will not put these online yet, since I feel that it needs some additional polishing first.
I've also managed to work a bit on the prototype, but have not been able to add any significant new features.
I did spend quite some time on thinking and brainstorming about price discovery mechanisms for the market design I'm proposing. A concise summary of the ideas originating from this can be found in a small document I made. I'm having a meeting with my promotor about this tomorrow afternoon.

Although that I didn't manage to reach the goals I set up before 2 weeks again, I do think that I did rather well considering the fact that I had some important issues in my private life that needed to be taken care of.

The next few weeks, I won't be having much time since I will need to study for some upcoming exams. However, I'll try to complete some of the things I mentioned in the planning but didn't do yet. I'll also post a updated schedule for the next weeks in one of the coming days.

Making some adjustments to the planning

(I wrote this post a couple of days ago, only now got the opportunity to put it online).
Due to some (unforseen) personal issues, I couldn't work full time on my thesis the past couple of days. Although I'm still going to try reach the goals I had set before; I will be making some minor adjustments to the planning. First of all, I will write some parts of the more introductory chapters of my thesis that answer questions such as:

• what is the problem this thesis tries to solve ?
• what are the (dis)analogies with the electricity market models?
• why different types of markets/auctions exists?

Doing this will give me the feeling that I'm getting more work done, since writing these 'context'-chapters is generally easier than writing about my own market model. The fact that writing the chapter about the market model itself progresses slowly is caused by the fact that the model is not complete yet. That is, although I believe that the current model already has some interesting features and ideas, a few critical points remain to be adressed (primarily; the issue of Price Discovery) properly. Already having done some writing about the model, I think the clarifying these issues first is the way to go. Of course, I'll continue working on the chapter; but I'll take more time to evaluate some of the markets components while writing.

Concerning price discovery, I have already a few ideas; but I haven't been able to address the "variable" priced components (such as outgoing bandwidth, etc) yet. Once I have a more complete picture, I'll create a small powerpoint presentation  and put that online.

On a side note, I have continued working on the (evolutionary) market prototype. At this point, all different components (market, consumers, providers) are actual webservices that communicate through WSDL/SOAP. I also managed to get a single service running on Amazon EC2 (this will come in handy, when I want to demo the prototype), but I haven't tested the whole setup on EC2 yet.

'Till next time :-)

Progress update

A quick post to bring you up to speed.
I've been doing some writing (not too much yet) the past couple of days. I wrote about 5-6 pages about some core aspects of the thesis.
I focussed on Dube's resource sets and the generalization to constraint sets. I also wrote a little bit about the problems of using a CDA (as a mentioned in more detail in my previous post) as primary market model. The text itself is only a rough draft and will need some additional iterations (and of course, a lot of additional content) before I'll post a first version here.

I also did some additional integration work on the prototype. This was not without difficulties however. The main problems lied with passing constraints to webservices (I thought I solved this before, but that turned out to be false). I solved this by separating the properties of the constraint from the the code that validates the constraint (the ConstraintValidator). Turns out this allows for even greater flexibility (since the coupling between constraint and constraint validation is much looser now), which is always a plus.

The next few days, I'll rework the prototype to make use of this new mechanism (I've already made some proof of concept code, but I still need to push it to the whole prototype) and write some more.

Planning the next 2 and a half weeks

As I promised in the previous blogpost: a small overview of what I will be doing in the next 2 to 3 weeks.
By the 18th of January (which is a couple of days before I have an exam, so I need to start studying afterwards), I want to have completed several things for my thesis.

A first rough draft of the chapter of my thesis that will talk about the CRA market design. Writing this will allow me to further refine my thoughts on the design and used mechanism, as well as provide a good 'complete picture'. It might also bring some new unresolved issues to my attention. I estimate that this draft will about 20 pages long.

I also want to elaborate the prototype I've been building. Some of this works includes:

• further integrate webservices (this should be rather simple using Spring + JAX-WS)
• finetune the constraint mechanism (primarily code cleanup)
• further implement the provider-specific matching behavior (this may take some time)
• add matches to billboard (price discovery)
• general code cleanup, refactoring, improvements
• very simple user management system (this is more a personal interest to have a look at the Spring Security framework).

I also hope to elaborate a bit on possible price discovery mechanisms for brokers. The goal is to have a small powerpoint presentation with some new ideas.

I know this is a rather ambituous schedule (especially if you know that I also need to take care of some things for other classes), but after 2-3 weeks of working on other projects, I really feel like getting started again :-)

'till one of the next days :-)

My thesis: an update

I know I haven't posted anything in a while here. This has a lot to do with the way I tend to write blogposts. Most of the time they become a lot longer than I first anticipate (such as now). Most of the time, I tend to have many ideas; and writing all of those down takes a lot of time.
I do believe however, that I should revive this blog since blogging is a great way to communicate latest findings fast. When keeping it up to date regularly, it also provides a good overview of the progression that is made. Additionally, my thesis does focus more on the 'ideas part' than on the 'implementation part'. Obviously, writing those ideas down is a good way to reflect on them.

Thus, my new year resolution is to update this blog far more frequently with smaller, but informative blogposts.
Since I haven't posted anything for about 2 months, I thought it was a good idea to create a small overview of the things I have been doing up until now (although nothing appeared on this blog, I have of course continued working on my thesis).

Chronological overview of the past months



A short update on where we are today

As you can see in the overview, I mention the term CRA a few times. The idea of the using the Continous Double Auction as the market mechanism has been somewhat altered to what I like to call a 'Continuous Reverse Auction' (or CRA for short). The idea behind the CRA is to use a Reverse Auction (which relates to some of the ideas I already discussed in a previous blogpost (http://thesisjorisroovers.blogspot.com/2010/10/component-based-offers-and-custom.html) in a continuous way. Rather than having several bidding phases for a single bid (such as in a Reverse Auction), providers will now only provide a single price for a single bid (when a bid comes in, the market contacts all of the providers to ask for a price). A bid is matched against the cheapest offer for that bid.  The price lowering effect that classic Reverse Auction tends to result in, is achieved by having a lot of bids (and matches) at after each other. By publishing anonymized matches to a kind of public billboard, providers will have the tendency to lower their prices in order to 'win' more matches. This means that in time providers will tend to show incentive compatible behavior.
The main benefits of the CRA are that it is continuous (matches happen in real-time), and allows great matching flexibility. The limits of what this model can match is defined by the limits of the used bidding language (in our case, the used constraint mechanism), which is a nice feature to have.
However, when working with the Continuous Reverse Auctions, consumers are price takers (compared to the CDA, when they also influence the price of the match). A disadvantage of this is that maximal market efficiency is not reached. That is, it might be that there are consumers that are willing to pay more for a match than the CRA will ask since they attach more value to it. Although this benefits the consumer in this case, the CRA market clearly is not able to provide an optimal clearing here.

However, in the current market situation; it is difficult to come up with a mechanism that does provider maximum effiency. This is primarily caused by the fact that currently cloud providers claim to provide 'unlimited' capacity, which suggest that resources are never scarce and that fluctuations in demand do not affect the value the provider attaches to its remaining (unused) capacity. This is obviously not true (this idea goes against every demand-supply based market principle); but at the moment, this is what providers try to sell consumers. As long as providers keep using this principle to price their offers (that is, an offer is always priced the same, independently of demand. Additionally consumers that are prepared to pay more than other consumers are not treated differently), maximum market efficiency is not a achievable goal. Note that although Amazon's spot instances do have hourly fluctuating prices according to demand, it does not have admission preferences among consumers.
However, you can ask yourself whether maximum market efficiency is a desirable property in all cases. I believe that in a Business-to-Consumer environment, this is not neccesarily the case. An end-user is probably less interested in always providing a price when wanting to use a utility (even if advanced price discovery tools are available). Bidding/Procurement is more the task of a broker (as is the case in e.g. the electricity market), who later on uses seperate mechanisms (average price, flat fee, day/night tariffs, ...) to bill its clients.

I believe that the CRA model contains some good ideas in the case where the consumers are price takers (as is currently the case in the cloud ecosystem). When consumers also need to influence the prices, we need more a hybrid between CDA and CRA in which brokers take the roll of consumers. In such model, the brokers no longer simple take the price of the cheapest provider; but instead they will submit bids. The bid of the broker will be matched against the offer of the provider that made the cheapest offer. By doing this, we achieve maximum market efficiency for that single bid. When wanting to achieve maximum efficieny among multiple bids, the CRA model (or any other continuous model, such as the CDA, for that matter) can no longer be used since multiple bids then need to be compared with each other. This makes the clearing market a lot more complex. Additionality, since it is impossible in a real-time ecosystem (such as a cloud market) to know whether a better bid or offer will arrive or not, such systems will always need to use heuristics to approximate maximum market efficiency.
The CRA model still needs some more elaboration, and some questions remain to be answered (price discovery stays a big issue), but I think that in terms of flexibility it already passed a first test.

I will continue to work out some of the details in the coming weeks.

So, with this medium-sized post, I updated the blog with the most salient ideas behind the CRA model. More detailed information can be found in the pointers provided by the overview document embedded above.

I'll be writing a post about my plans for the coming weeks later today.

Different scenarios require different markets

Up until now, I've never really blogged about different type of markets as exist in other commodity markets. With different type of markets, I mean markets that trade commodities within different time frames. That is, in a normal commodity market model, a difference is made between a futures market and a spot market. When thinking about a cloud computing resource market, it is not difficult to imagine these market equivalents. That is, in a cloud resources market, cloud computing resources can be traded for a specific time frame in the future or directly on the spot. There is however, also a 3th kind of market that needs to be considered: the on-demand market. The on-demand market trades - as the name implies - cloud resources that are requested on-demand; which means that the resources need to be directly accessible, but that no additional information is given by the consumer on how long the resources will be needed.

While all 3 market types share a lot of ideas (e.g. constraint language), each one also has properties that make them different from the other types. Let's have a more in-depth look at each of these 3 markets.

Futures market
If we take wikipedia's definition of a futures market, we can modify it so that it can be applied to a cloud setting:

A futures exchange is a central cloud resource exchange where people can trade standardized futures contracts; that is, a contract to buy specific quantities of cloud resources at a specified price for a specified time interval in the future.

In other words, if we put this on a timeline, a cloud resource future contract is a contract that is traded on time t, that specifies a specific amount of cloud resources (that meet certain constraints) that need to be available from a time t+x until a time t+y.  

Trading on the futures market allows providers to do better resource provisioning in their datacenters. Since trading resources on the futures market allows providers to reduce risk (that is, they can reduce the risk of having idle resources at some time in the future), future markets usually offer resources cheaper than on the e.g. on-demand market. However, there are many situations in which this can be different (e.g. if the electricity prices are expected to be higher in the future, than the future price of an ask might be higher than the current (on-demand or spot price) price).
Speculating on future prices (either by going short or going long) might result in significant financial gains or losses. These principles are not new, and are an inherit part of any futures commodity market. Making future markets a part of my market model is therefor absolutely necessary, if the model is to be considered economically viable.

It might be interesting to combine the on-demand idea (that is, not obligating the consumer to specify when a resource is no longer needed) with the idea of a futures contract. That is, it might be intersting for a consumer to specify that it he will need a specific set of resources in the future, without needing to specify how long he will need them.

This is however, not very interesting from the provider's point of view since in this scenario he no longer has any garantuee on how long the resources will be used. However, if we allow a user to specify a minimum end time and a maximum end time, we allow the provider to make fairly accurate resource provisioning plans while at the same time giving the consumer more flexibility in time specification. This is especially helpful when it is hard for a consumer to specify exactly how long he will need the resources, while it is fairly easy for him to give a minimum running time.

The futures market model as proposed here fits quite nicely in the market model I've been developing until now. For the futures market, an offer (both ask and bid) should contain:

• metainfo
• a price (minprice for asks, maxprice for bids)
• a timeconstraint (which timeframe is being considered)
• a set of constraints (resources, legal, etc)
• an expiration date (until when is the offer valid)

Spot market
Let's again modify wikipedia's definition of a spot market to get a definition for a cloud spot market:

The cloud spot market is a public cloud computing resource market, in which cloud resources are traded and delivered immediately.

Spot market timeline, a bid starts at a time t and runs until t+3 when the spot price of the provider exceeds the maximum price of the bid

Spot markets typically represent the immediate need of the market, that is, providers will sell current overcapacity on the spot market, while consumers buy current undercapacity on the spot market. If demand is high, spot prices will be high, when demand is low, spot prices will be low.
A spot price is the price of a single unit of trade on the spot market. This unit of trade is always exactly defined. For example, on the gold spot market, gold is always traded per 1000 ounces. The spot price at a given time thus reflects the value the market attaches to 1000 ounces of gold at that moment.
However, as with electricity (to some extent), a cloud computing unit cannot be expressed in a single dimension, since the heterogenity between different cloud resources is so large. Multiple dimensions (price, time and type) are indeed needed to specify a single cloud unit. This makes spot trading more complex. In order to trade on the spot market and keep things simple, we will thus have to set one of these dimensions to a fixed value in order to compare separate offers with each other. For now, I fix the time dimension to a single hour (this is also done in the electricity spot market). This means that the price and constraints can vary between offers, but the timeframe for which on offer is valid is always defined as a single hour.

This also implies that cloud providers and consumers will need to resubmit their offers before the start of the next hour. This allows both providers and consumers to adapt their prices based on their current needs.

Although this model works, it does not take into account that consumers might want to buy resources on the spot market for several hours at once. That is, cloud spot markets (such as Amazon's EC2) are primarily used to run lower-importance applications as long as the current price of the spot market does not exceed a certain threshold. In the model I just described, consumers need to re-buy cloud resources every hour, which implies migrating applications every hour. Obviously, this is not the desired behaviour. We can solve this by adapting our bidding language to reflect cloud spot market principles.

An spot-ask should then contain:

• meta-info
• the current spot price for the hour
• a set of constraints (resources, etc)
• no timeconstraints
• no expiration date (an ask always expires after a single hour)

While a spot-bid contains:

• meta-info
• a maximum price
• a set of constraints (resources, etc)
• no timeconstraints
• no expiration date

A spot-bid will then match with a spot-ask, if the price of the spot-bid is lower than the price of the spot-ask. A match implies a contract between provider and consumer of undefined duration. However, this contract can always be broken by the consumer (on-demand character of spot market), and should only be broken by a provider when it's current spot price becomes higher than the maximum price specified by the consumer in his bid.

Although spot markets allow a lot of immediate flexibility for both consumers and providers, the spot market does not provide consumers with any garantuee on how long their instances will be able to run. That is, it could be that the spot price of a specific provider is very low at a given moment, and very high the next hour (which probably results in a shutdown of the consumers instance, since the spot price would exceed the consumers maximum price). Surely, a slightly more expensive provider that has less volatile spot prices might be more interesting, since the probability that an instance running on that provider is shutdown is a lot lower. This is especially so for jobs that have a high startup cost.

In order to accommodate this desire, I propose to use price history constraints on both spot bids and asks. Such a constraint might for example assert that the average spot price (over a certain time frame) of a specific provider does not exceed a certain value. Using such constraints allows the consumer to have better garantuees over the volatility of the spot price.

Of course, using such constraints raises an issue of trust. Can a provider be trusted to deliver correct history constraints? Probably not. Therefore, cloud providers should use brokers that independently monitor the provider's spot prices and attach the history constraints to the provider's ask when submitting the ask to the market (Note: to bootstrap this mechanism, the data from e.g. cloudexchange.com can be used). Using the custom constraint mechanism discussed in my previous post, these brokers can then distribute their price history constraint to consumers.

On Demand Market
As already said before, on the on-demand market, the traded cloud resources should be directly available, but the consumer does not need to specify how long he will be using these resources.

On demand market

To implement the on-demand market, we again need to slightly adjust our bidding language:
A offer (bid or ask) should contain:

• metainfo
• a unit price
• a unit time granularity
• constraints (resources, etc)
• an expiration date  

That is, an offer should both contain a price as the time indication for which this price is valid. For example, an offer can have a price of 10 ct for a single hour or 100 euro for 1 month. Using this bidding language allows providers with different accounting granularities to participate in the market.

However, if we wish to keep using the price sorted queues (as used by the continous double auction), the market will need to normalize the prices in the queues (e.g. price per minute) and take into account the unit time granularity as an extra timeconstraint when matching offers. Although this makes the matching algorithm more complex, I believe that the improved flexibility for providers justifies this.

Now, the question poses itself, what if the user knows how long he will be using a certain set of resources but also requires his bid to start immediatly. Does this kind of bid that requires a direct start but that also specifies an end time 'belongs' to the futures or on-demand market? The answer is that it can 'belong' to both. However, one would reasonably expect that an offer on the future market is cheaper since the insurance that a resource is used for a specific time frame is worth something for a provider (recall that reducing risk for the provider is the primary idea behind the futures market). By introducing a DurationConstraint alongside timeconstraints in the futures market, we can allow offers on the futures market that need to start directly while garantueeing a minimum resource usage for the provider.

Combining on-demand and futures market

Obviously, an end-user should not need to choose on which market to submit his offer. Brokers should submit a consumers bid on both the futures and on-demand market, and return the cheapest match. Note that in order for this to work, the market must allow matching without obligations for both consumers and providers. Allowing this complicates things, since in such a scenario we need a seperate service that contacts both the provider and consumer to seal the deal. I might shed further thought on this issue in the future since I think it is a good idea to add the match execution verification (do consumer and provider hold their promises?) to the same kind of service.

Component Based Pricing

I'm not entirely sure yet how the component based pricing reverse auction I discussed in the previous blog post fits in the models I just discussed (does every market have a seperate reverse auction, or is there a seperate reverse auction that is shared between the different markets ?). I will be exploring this further in the coming week.

That's about it for now :-) Until soon.