Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.tcs.2018.02.035
DC FieldValue
dc.titleOnline buffer management for transmitting packets with processing cycles
dc.contributor.authorYang, YH
dc.contributor.authorLiao, CS
dc.contributor.authorHan, X
dc.contributor.authorZhang, L
dc.date.accessioned2019-07-08T05:54:20Z
dc.date.available2019-07-08T05:54:20Z
dc.date.issued2018-05-02
dc.identifier.citationYang, 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
dc.identifier.issn0304-3975
dc.identifier.urihttps://scholarbank.nus.edu.sg/handle/10635/156496
dc.description.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.
dc.publisherElsevier BV
dc.sourceElements
dc.typeArticle
dc.date.updated2019-07-08T04:56:49Z
dc.contributor.departmentDEPT OF MATHEMATICS
dc.description.doi10.1016/j.tcs.2018.02.035
dc.description.sourcetitleTheoretical Computer Science
dc.description.volume723
dc.description.page73-83
dc.published.statePublished
Appears in Collections:Staff Publications
Elements

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

CLOSED

Published

Page view(s)

83
checked on May 29, 2020

Download(s)

1
checked on May 29, 2020

Google ScholarTM

Check

Altmetric


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