Optimization in stochastic models of network applications

Tan, Bo

Permalink

https://hdl.handle.net/2142/34431 Copy

Description

Title

Optimization in stochastic models of network applications

Author(s)

Tan, Bo

Issue Date

2012-09-18T21:16:32Z

Director of Research (if dissertation) or Advisor (if thesis)

Srikant, Rayadurgam

Doctoral Committee Chair(s)

Srikant, Rayadurgam

Committee Member(s)

• Basar, Tamer
• Hajek, Bruce
• Veeravalli, Venugopal V.

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Content Distribution Networks
• Online Advertising
• Stochastic Models
• Optimization
• Resource Allocation

Abstract

In this dissertation, we propose stochastic models and develop optimal or near-optimal algorithms for resource allocation, for two important network applications: 1) video-on-demand (VoD) services in content distribution networks (CDNs) and 2) online advertising. For the first application, we address the problem of content placement in VoD CDNs, with the objective of maximizing the utilization of CDN servers' uplink bandwidth resources. We consider system performance under a large network asymptotic. We first study the case of a finite content catalog, and distinguish two scenarios, namely a common ``service-only'' CDN for which requests are exogenous to the system, and an ``ISP-managed peer-to-peer CDN'' for which requests emanate from the servers (peers) themselves. For both scenarios, we consider a loss network model of performance, and determine asymptotically-optimal content placement strategies. We then turn to an alternative ``large catalog model'' where the content catalog size scales with the network size. Under this model, we establish that storage space per server must necessarily grow unboundedly if bandwidth utilization is to be maximized. We then identify a content placement strategy and a request acceptance policy which jointly maximize bandwidth utilization, provided storage space per server grows unboundedly, although arbitrarily slowly, with system size. For the second application, which is online advertising, we propose a stochastic model to describe how search service providers charge client companies based on users' queries for the keywords related to these companies' ads by using certain advertisement assignment strategies. We formulate an optimization problem to maximize the long-term average revenue for the service provider under each client's long-term average budget constraint, and design an online algorithm which captures the stochastic properties of users' queries and click-through behaviors. We solve the optimization problem by making connections to scheduling problems in wireless networks, queueing theory and stochastic networks. Unlike prior models, we do not assume that the number of query arrivals is known. Due to the stochastic nature of the arrival process considered here, either temporary ``free'' service, i.e., service above the specified budget (which we call ``overdraft'') or under-utilization of the budget (which we call ``underdraft'') is unavoidable. We prove that our online algorithm can achieve a revenue that is within $O(\epsilon)$ of the optimal revenue while ensuring that the overdraft or underdraft is $O(1/\epsilon)$, where $\epsilon$ can be arbitrarily small. With a view towards practice, we can show that one can always operate strictly under the budget. In addition, we extend our results to a click-through rate maximization model, and also show how our algorithm can be modified to handle non-stationary query arrival processes and clients with short-term contracts. Our algorithm also allows us to quantify the effect of errors in click-through rate estimation on the achieved revenue. We show that we lose at most $\frac{\Delta}{1+\Delta}$ fraction of the revenue if $\Delta$ is the relative error in click-through rate estimation. We further show that in the long run, an expected overdraft level of $\Omega(\log(1/\epsilon))$ is unavoidable (a universal lower bound) under any stationary ad assignment algorithm which achieves a long-term average revenue within $O(\epsilon)$ of the offline optimum.

Graduation Semester

2012-08

Permalink

http://hdl.handle.net/2142/34431

Copyright and License Information

Copyright 2012 Bo Tan

Owning Collections