Please use this identifier to cite or link to this item:
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.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.
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.contributor.departmentDEPT OF MATHEMATICS
dc.description.sourcetitleTheoretical Computer Science
Appears in Collections:Staff Publications

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



Page view(s)

checked on May 29, 2020


checked on May 29, 2020

Google ScholarTM



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