present or future: optimal pricing for spot instances文章阅读笔记

问题挑战：

        如何给竞价型实例定价，当前定价过高，可获得当前较高收益，但会导致将来实例价格过低，从而使将来的收益过低。目标是在保证用户服务质量的前提下，合理定价获取整体较高收益。

两个模型：

        1、In the basic model, assuming that all requests cannot be dropped.

        2、Extending the basic model to achieve worst-case delay guarantees.

        基本模型参数定义：t--time slot. P(t)--实例价格。 N(t)--相应价格对应的实例数量(launched instances意思是当前时间价格为P(t)，因此相应及以上价格的实例能够被服务)。 S(t)--可提供服务实例数量（有限的）。Ps(t)--需求个数等于S(t)时的实例定价。Q(t)--instances in pending state(当前时间在搁置队列里的实例个数)。A(t)--新到来的实例需求个数（有限的）。R(t)--P(t) * N(t)（收益）。

        第四部分Lyapunov function表示积压的工作量大小，即代表了用户服务质量，目标是使这个函数尽可能的小，并且使总体收益尽可能的大。公式（13）是这两者的权衡表达式，（13）越小越好，即找到公式（13）的上界来衡量模型的好坏。

        公式（14）推导过程弄明白了。

        C部分假设了一种简单情况，并以这个情况为例分析各个算法的表现，在这个简单例子上实现了离线最优算法，文中算法在一定程度上接近于离线最优算法，这个举例子可以让读者更好更快地理解算法。

        第五部分扩展的模型没仔细看。

        实验数据用的谷歌集群数据，根据波动情况分为四组(Assuming that the requests with higher latency-sensitive value have higher maximum price.)，假设每组中价格一致。实验中有两个基准算法：Match All（baseline）、Single Slot. 再加上文中提到的基本模型算法和扩展模型算法，共有四种算法。Single Slot 在某些情况下表现不错（图7表5），收益居中，延迟居中。但价格波动较大时，Single Slot虽然可以取得最好的收益，但是其延迟也是巨大的。

        另外一个点：Lyapunov optimization，还不懂。。。