A Market Design for IaaS Cloud Resources

It has been some time since I last posted on this blog. The reason for that is that I've been very busy actually writing my thesis.
After completing the introductory chapter, I continued writing on the other chapters and I'm proud to say that as of 2 days ago, the thesis document and accompanyning prototype have been completed. The document itself can be viewed below, while the implementation of the market prototype can be found online.




I wish to thank everybody who helped me during the writing on this thesis. In particular, my promoter Prof. Dr. Jan Broeckhove, my co-promoter Dr. Kurt Vanmechelen and my mentor Ruben Van den Bossche. I also wish to thank my family and close friends for their continued support.

If you have any questions about the thesis, don't hesitate to contact me.

Writing the introductory chapter - final part

As it turns out, writing that introductory chapter took more time than anticipated (probably because I wanted it to be of a good quality). With a lot of hard work, I have finished it now. Next up: chapter 2! Chapter 2 deals with general market design principles. It starts with a definition of 'a market' and subsequently gives a short overview of some existing financial markets and their workings. Some desirable market properties are discussed (incentive compatibility, individual rationality, allocative efficiency, computational tractability), and some considerations about commodity market design are outlined. The chapter will finish with some first more concrete ideas about the IaaS market, based on the previous commidity market design considerations.

It is imperative that I finish this chapter this week if I don't want to get behind on schedule. With that in mind, I already did some work during the weekend. However, as the next week is already rather busy (I also need to make a rather elaborate assignment for an other course), a lot of hard work will be required to finish chapter 2 this week. But, as always, I'm eager to work hard and make it happen :-)

I'll post an update as soon as I know something more (=when I finish chapter 2).

Writing the introductory chapter - part 2

The last week I've had a bit of a writer's block, as I tried to get something on paper multiple times without a lot of success. Writing went a bit better during the weekend, but I cannot say that it went really well. The result of this is that I did not finish the first version of the introductory chapter yet, although I have made good progress.

As the next week is rather busy, it is difficult to make accurate projections for next week (and as it turns out, not every week goes according to plan...), but I will definitely finish the introductory chapter by then.

Not every day can be as productive as the others, but let's make the next days count :-)

Writing the introductory chapter - part 1

I planned to both work on the prototype and write on my thesis this week, but that didn't work out as I had to spend quite some time on an unexpected assignment for a course on webinformation systems. However, by putting in some extra effort over the weekend, I did manage to write 8 pages about cloud computing (what is it?, Iaas/PaaS/Saas, public/private/hybrid, challenges). Writing went rather smooth because I was able to reuse some parts I had already written last year in a general introduction on cloud computing.

In the coming week I'd like to finish the introductory chapter (which is a bit of a bold statement, as that would probably involve writing more than the usual 5 pages a week) as well as work a bit on the prototype (secondary objective). I will be focusing on some examples of real world cloud providers for the different cloud computing types (IaaS, PaaS, SaaS), as well as write about the power industry and it's resemblances to cloud computing. I will also try to write a clear problem statement for the thesis.

Let's make it a productive week :-)

Price Discovery and Prototype

The last week I turned up working on different topics than expected. With hindsight, I think I was righteously cautious when I said last week that it was maybe still a bit early to make any real statements about the price discovery mechanisms I have spend time on in the past weeks. As it turns out (without going into to much detail; that would require a rather long blogpost), although valuable, in practice some of the price discovery mechanisms I proposed have some difficult issues to solve. However, helped by the writing I did the last few weeks, I believe I found a valid, far simpler alternative. That is, since the a consumer can always choose to refuse or accept a proposed price, the CRA already provides a sufficient form of price discovery as part of the market as consumers can always discover prices by submitting a bid and subsequently refusing the matching offer. Although it may seem that I have been looking for a far more difficult solution before, it is only quite recently that I am quite certain that giving the consumer the possibility to reject matches does not have a negative impact on the market. The reason I doubted this before was because of a potential loss of allocative efficiency in a mostly consumer oriented market. However, I have come to understand that this is not necessarily the case in an environment such as the cloud computing market where there is an seemingly unlimited supply of resources (again, going into much detail would require a far lengthier post).
I discussed this with my co-promoter this week (overview of my preparations), and we agreed that at least for now it is indeed a good idea to go with this form of price discovery.

We also decided that it is valuable to put some more effort into the prototype, as I've always put much emphasis on the real world applicability of the market model. In the past few days, I have thus primarily been focusing on that prototype, while also having done some writing. Concerning that writing; I focussed some more about how the CRA model can be implemented (this helped me out when implementing the prototype), and I also wrote a bit about compound bids.

I worked quite a lot the past week, and although I've only written my weekly 5 pages, I think my efforts on the prototype will pay off in the coming weeks.

In the coming week, I'll start writing on the introduction chapter of my thesis (about cloud computing and the power industry and their markets), as well as continue to work on the prototype (still a lot to do!).

Slides and the Constraint Lookup Service

This post comes to you with a bit of unexpected delay. Nevertheless, with this post I want to give you a status update. On Wednesday 23Feb, I had to given a presentation covering my progress so far. The fact that the audience seemed to agree with most of my ideas, is another indicator that the use of the CRA mechanism is probably a solid choice.
The slides can be found on https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B2ZFuPHiC22wYmU0M2Q0OTktYjA1NS00NzcyLWI1OGYtYzM0YTVhN2ExOGQ4&hl=en_GB

About the writing on the thesis itself: this week I started writing on the 'Implementation of the CRA' section. I managed to meet my 5 pages/week deadline again by writing about how seperate lookup services should be used to implement the constraint operations. The figure below gives an idea of how such a service interacts with the other market actors.

I also made a first rudimentary price discovery prototype. Although the prototype still needs a lot of work (I'll be improving on it this week), the first results look promising (maybe it is still a bit early to make any such statements).

Besides improving upon the pricediscovery prototype, I'll continue to write about the implementation details of the CRA this week. Update next week!

About problem specification and powerpoint slides

As the week comes to an end, I'm providing you with another update.
This week I've concentrated on clearly specifying the problems that occur when trying to use Dube's market model in the current cloud computing market. I must admit that I had more difficulties with this than I had anticipated. Although the problems in itself are not very difficult, they do tend to become rather complex (as many different factors play a role). This makes clearly explaining what the exact problem is hard, as the problem itself is composed of different subproblems, of which some are also hard to define.
However, I do believe that I have succeeded in clearly defining some of the issues (a lot of work is still to be done). The result of this is now part of my thesis document (I succeeded in adding another 5 pages to the document this week).

I've also created a slideshow presentation for the presentation I mentioned last week. I will put the slides online after I've given the presentation (which will take on Wednesday, Feb 23th).

Although creating the slideshow has helped me to (re)gain a better overview over some parts, it has also made me more aware of the fact that I should invest enough time to thoroughly explaining some concepts and ideas in the thesis itself. In particular, I think I should re-evaluate the time I spend building a working prototype, the time I spend exploring new topics and the time I spend on elaborating on existing ideas. After this week, I believe that the elaboration of existing topics should get some more attention.

Since I also have to give a presentation about my research internship on Wednesday, and I still have some preparation to do for that, I think it is safer not to make to many specific plans for the coming week. I *am* going to try and work on the price discovery issue (which I didn't get to in the past week), as well as write an additional 5 pages for the thesis itself.

As already mentioned, I will be posting the slideshow of Wednesday's presentation in the second half of the week.

Start of the new semester - status update

The past few weeks I've been writing parts of my thesis. I am happy to say that I succeeded in finishing the 30 pages I set out to write in my previous blogpost. Most of what I've written is more general information about (financial/commodity) markets and some parts about Dube's constraint sets and my ideas concerning the more generic constraint sets.
Although I initially planned to put the parts I already finished online, I've decided not to do that anymore. This is mainly caused by the fact that the overal quality of the text needs a lot of extra polish and I don't want to put an half finished product online.

I've also worked a bit on the prototype, but for now, I don't have anything new to report on that.

In the coming days, I will be looking further into the price discovery issue, writing some more (to meet the 5 pages/week goal I set before) and prepare a presentation I'll be giving in the next few weeks.
I'll probably also be doing some work on my research internship which deals with desktop clouds.

Expect an update before the end of the week.

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.