Market- Based Resource Allocation for Content Delivery in the Internet

Abstract

The Internet has evolved into a worldwide information backbone with vast user base. Internet users are diverse and they receive varying utilities from their network connections. In many cases high-level user decisions appear to have direct consequences on the network performance. In this thesis, our motivation is to characterize the effects of user behaviors in terms of lower layer network metrics such as network latency. We consider the Content Delivery Networks for our analysis, since they are the interconnection of network elements at the application layer and thus are directly affected by the user preferences.<p>It has been a common practice to use caches to store the most popular data in order to improve user latency and reduce the network load. Recently, a more systematic approach to the caching has been developed in the framework of Content Delivery Networks. Content Delivery Networks (CDNs) are the networks of caches that are distributed throughout the Internet serving user requests directed to their subscriber web sites (publishers). They distribute the publisher's original content intelligently to the caching servers (surrogates) all over the world. Users receive their information from the surrogates, which are closer and usually much less loaded than the origin server. The objective is to minimize the user latency by intelligently distributing the content and serving the user requests from the most efficient surrogates. We use price-directed market based algorithms to achieve this goal. As it is the case in the current Internet, we model the agents with a selfish self-maximizing behavior and define the problem as a non-cooperative game played among the publishers and the surrogates. We show that the system has an equilibrium and if this equilibrium is unique, even though the agents are non-cooperative we achieve the global optimum. We also determine a uniqueness condition, which states that if the publishers are not willing to pay high amounts and the cache sizes are sufficiently small, then the equilibrium is unique. We noticed that the global system optimum that minimizes total average user latency requires the publishers to make very high investments, which in practice may prohibit the applicability of the distributed market method. Thus, we consider an investment strategy, which leads to a near-optimum system solution at much lower investments. <p>The abovementioned method gives publishers infinite granularity to determine their quality of service. Next, we investigated the case where the publishers can offer only finite number of QoS classes. In this model, surrogate partitions its total capacity among different service classes and among each class publishers receive equal shares of the resources. In our model, publishers try to get as large cache space as possible, while the surrogate is required to achieve fair allocation among the publishers. Specifically, each publisher should be charged the same if they receive equal share of caching space. We determine the optimal pricing strategy of the surrogate maximizing its revenue. We also analyzed the competition among two surrogates under this model and determined the condition that leads to a Nash equilibrium. We showed that at equilibrium surrogates peer as if they are a single combined surrogate server.