Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.tcs.2018.02.035
Title: Online buffer management for transmitting packets with processing cycles
Authors: Yang, YH
Liao, CS
Han, X
Zhang, L 
Issue Date: 2-May-2018
Publisher: Elsevier BV
Citation: Yang, YH, Liao, CS, Han, X, Zhang, L (2018-05-02). Online buffer management for transmitting packets with processing cycles. Theoretical Computer Science 723 : 73-83. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2018.02.035
Abstract: © 2018 Elsevier B.V. We study an online buffer management problem under the model introduced by Azar and Gilon (2015) [5] recently. Unit-sized packets arrive and are kept in a First-In-First-Out buffer of size B in an online fashion at a network server. Each packet is associated with an arrival time, a value and a processing cycle time in the buffer. The density of a packet is defined to be the ratio of its value to processing time. It is assumed that every packet can be transmitted only after its processing cycle is completed and only the packet at the head of the buffer can be processed. A packet is allowed to be preempted and then discarded from the buffer. But, the value of a packet is attained only if it is successfully transmitted. Under the model, the objective of online buffer management is to maximize the total value of transmitted packets. This model finds applications to packet scheduling in communication networks. In this study, we consider the model with constant density from a theoretical perspective. We first propose some lower bounds for the problem. Azar and Gilon obtained a 4-competitive algorithm for the online buffer management problem for packets with constant density. Here, we present a (2+[Formula presented])-competitive algorithm for the case B>1 as well as its generalization to the multi-buffer model. Moreover, we prove that the competitive ratio of a deterministic online algorithm is at least four when the buffer size is one. We also conduct experiments to demonstrate the superior performance of the proposed online algorithm against the previous approach.
Source Title: Theoretical Computer Science
URI: https://scholarbank.nus.edu.sg/handle/10635/156496
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2018.02.035
Appears in Collections:Staff Publications
Elements

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
TCS_paper-main.pdf419.65 kBAdobe PDF

CLOSED

Published

Page view(s)

71
checked on Mar 19, 2020

Download(s)

1
checked on Mar 19, 2020

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.