We consider a content delivery problem in which jobs are processed in batches and may abandon before their service has been initiated. We model the problem as a Markovian single-server queue and analyze two different settings: (1) the system is cleared as soon as the server is activated, i.e., service rate μ = ∞, and (2) the service speed is exponentially distributed with rate μ <; ∞. The objective is to determine the optimal clearing strategy that minimizes the average cost incurred by holding jobs in the queue, having jobs renege, and performing setups. This last cost is incurred upon activation of the server in the case μ = ∞, and per unit of time the server is active otherwise. Our first contribution is to prove that policies of threshold type are optimal in both frameworks. In order to do so we have used the Smoothed Rate Truncation method which overcomes the problem arising from unbounded transition rates. For our second contribution, we derive the steady-state job-length distribution under threshold policies. The latter yields a characterization of the optimal threshold strategy, which can be easily implemented. Finally, we present numerical results for our solution across a wide range of parameters. We show that the performance of nonoptimal threshold policies can be very poor, which highlights the importance of computing the optimal threshold.
%0 Conference Paper
%1 7277429
%A Larranaga, M.
%A Boxma, O.J.
%A Nunez-Queija, R.
%A Squillante, M.S.
%B Teletraffic Congress (ITC 27), 2015 27th International
%D 2015
%K Computational_modeling Delays Markov_processes Markovian_single-server_queue Mathematical_model Optimization Servers Steady-state average_cost_minimization content_delivery_network exponential_distribution impatient_job itc itc27 network_server network_servers optimal_clearing_strategy queueing_theory smoothed_rate_truncation_method steady-state_job-length_distribution
%P 73-81
%R 10.1109/ITC.2015.16
%T Efficient Content Delivery in the Presence of Impatient Jobs
%U https://gitlab2.informatik.uni-wuerzburg.de/itc-conference/itc-conference-public/-/raw/master/itc27/7277429.pdf?inline=true
%X We consider a content delivery problem in which jobs are processed in batches and may abandon before their service has been initiated. We model the problem as a Markovian single-server queue and analyze two different settings: (1) the system is cleared as soon as the server is activated, i.e., service rate μ = ∞, and (2) the service speed is exponentially distributed with rate μ <; ∞. The objective is to determine the optimal clearing strategy that minimizes the average cost incurred by holding jobs in the queue, having jobs renege, and performing setups. This last cost is incurred upon activation of the server in the case μ = ∞, and per unit of time the server is active otherwise. Our first contribution is to prove that policies of threshold type are optimal in both frameworks. In order to do so we have used the Smoothed Rate Truncation method which overcomes the problem arising from unbounded transition rates. For our second contribution, we derive the steady-state job-length distribution under threshold policies. The latter yields a characterization of the optimal threshold strategy, which can be easily implemented. Finally, we present numerical results for our solution across a wide range of parameters. We show that the performance of nonoptimal threshold policies can be very poor, which highlights the importance of computing the optimal threshold.
@inproceedings{7277429,
abstract = {We consider a content delivery problem in which jobs are processed in batches and may abandon before their service has been initiated. We model the problem as a Markovian single-server queue and analyze two different settings: (1) the system is cleared as soon as the server is activated, i.e., service rate μ = ∞, and (2) the service speed is exponentially distributed with rate μ <; ∞. The objective is to determine the optimal clearing strategy that minimizes the average cost incurred by holding jobs in the queue, having jobs renege, and performing setups. This last cost is incurred upon activation of the server in the case μ = ∞, and per unit of time the server is active otherwise. Our first contribution is to prove that policies of threshold type are optimal in both frameworks. In order to do so we have used the Smoothed Rate Truncation method which overcomes the problem arising from unbounded transition rates. For our second contribution, we derive the steady-state job-length distribution under threshold policies. The latter yields a characterization of the optimal threshold strategy, which can be easily implemented. Finally, we present numerical results for our solution across a wide range of parameters. We show that the performance of nonoptimal threshold policies can be very poor, which highlights the importance of computing the optimal threshold.},
added-at = {2016-07-11T18:20:14.000+0200},
author = {Larranaga, M. and Boxma, O.J. and Nunez-Queija, R. and Squillante, M.S.},
biburl = {https://www.bibsonomy.org/bibtex/2bdacf59f8158460b8d583d17ced40fbc/itc},
booktitle = {Teletraffic Congress (ITC 27), 2015 27th International},
doi = {10.1109/ITC.2015.16},
interhash = {c90ec06183dc13a591456bc8a3f14cdc},
intrahash = {bdacf59f8158460b8d583d17ced40fbc},
keywords = {Computational_modeling Delays Markov_processes Markovian_single-server_queue Mathematical_model Optimization Servers Steady-state average_cost_minimization content_delivery_network exponential_distribution impatient_job itc itc27 network_server network_servers optimal_clearing_strategy queueing_theory smoothed_rate_truncation_method steady-state_job-length_distribution},
month = {Sept},
pages = {73-81},
timestamp = {2020-04-30T18:18:14.000+0200},
title = {Efficient Content Delivery in the Presence of Impatient Jobs},
url = {https://gitlab2.informatik.uni-wuerzburg.de/itc-conference/itc-conference-public/-/raw/master/itc27/7277429.pdf?inline=true},
year = 2015
}