点击次数：

论文类型：期刊论文

发表时间：2018-05-02

发表刊物：THEORETICAL COMPUTER SCIENCE

收录刊物：SCIE、EI、Scopus

卷号：723

页面范围：73-83

ISSN号：0304-3975

关键字：Buffer management; Competitive analysis; Online scheduling; Run-to-completion

摘要：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 + 1/B-1)-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. (C) 2018 Elsevier B.V. All rights reserved.