الگوریتم آنلاین حافظه نزدیک بهینه برای میانگیری دو طبقه FIFO

We consider scheduling packets with values in a capacity-bounded buffer in an online setting. In this model, there is a buffer with limited capacity BB. At any time, the buffer cannot accommodate more than BB packets. Packets arrive over time. Each packet has a non-negative value. Packets leave the buffer only because they are either sent or dropped. Those packets that have left the buffer will not be reconsidered for delivery any more. In each time step, at most one packet in the buffer can be sent. The order in which the packets are sent should comply with the order of their arrival time. The objective is to maximize the total value of the packets sent in an online manner. In this paper, we study a variant of this FIFO buffering model in which a packet’s value is either 1 or α>1α>1. We present a deterministic memoryless 1.304-competitive algorithm. This algorithm has the same competitive ratio as the one presented in Lotker and Patt-Shamir [Z. Lotker, B. Patt-Shamir, Nearly optimal FIFO buffer management for DiffServ, in: Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing, PODC, 2002, pp. 134–142; Z. Lotker, B. Patt-Shamir, Nearly optimal FIFO buffer management for DiffServ, Computer Networks 17 (1) (2003) 77–89]. However, our algorithm is simpler and does not employ any marking bits. The idea used in our algorithm is novel and different from all previous approaches that have been applied for the general model and its variants. We do not proactively preempt one packet when a new packet arrives. Instead, we may preempt more than one 1-value packet at the time when the buffer contains sufficiently many αα-value packets.

We consider online algorithms to schedule packets with values in a capacity-bounded buffer. There is a buffer with a limited size B ∈ Z+. At any time, the buffer can accommodate at most B packets. Packets arrive over time. The buffer is preemptive: packets already in the buffer are allowed to be dropped at any time before they are delivered. We use rp ∈ R+ and vp ∈ R+ to denote the release time (arriving time) and the value of a packet p respectively. Packets leave the buffer only because they are either sent or dropped. Those sent and dropped packets will not be reconsidered for delivery any more. Time is discrete. In each time step, at most one packet in the buffer can be sent. The order of the packets being sent should comply with the order in which they are released. The objective is to maximize the total value of the packets sent in an online manner. We call this model a FIFO buffering model; this model has attracted a lot of attention in the past ten years and has been studied extensively [1–5]. In this paper, we study a variant of this model in which packets have value either 1 or α > 1: 1-value packets and α-value packets. This variant is called a two-valued model and has been investigated in [6,3,5].Without knowing the future input, an online algorithm has to make its decision over time based on the input information that it has seen so far. If an online algorithm decides which packet to send only based on the contents of its current buffer and independent of the packets that have already been released and processed, we call this algorithm memoryless. Consider a maximization problem as an example. A deterministic online algorithm is called k-competitive if its objective value on any instance is at least 1/k times of the objective of an optimal offline algorithm applied on the same instance [7]. The upper bounds of competitive ratio are achieved by some known online algorithms. A competitive ratio less than the lower bound cannot be reached by any online algorithm [7]. For the two-valued model, the previously known results include a 1.544- competitive memoryless algorithm [6], a 1.304-competitive algorithm [3] which uses marking bits for all pending packets in the buffer [3], and a non-memoryless optimal 1.282-competitive algorithm [5] which applies to the case when the buffer size B goes to infinity. In this paper, we present a 1.304-competitive memoryless algorithm. Our algorithm is simpler than the one in [3] and it does not use marking bits. It is instructive to compare and contrast the algorithm in [3] with ours since both have the same competitive ratio 1.304. Based on the definition of memoryless algorithms [8,9] (a memoryless online algorithm should make the decisions independent of any packets that it has processed), we know that the marking bits used by [3] reflect the packets that the online algorithm has processed and they affect the marking and flush procedure for later arriving α-value packets. Hence the algorithm in [3] is not memoryless. In Section 2, we describe a deterministic memoryless online algorithm called ON. In Section 3, we give the algorithm’s analysis, showing that it is 1.304-competitive. Related work and conclusion remarks are presented in Section 4.

Mansour et al. [10] initiated the study of competitive online algorithms for the FIFO buffering model. They designed a simple greedy deterministic algorithm with a tight competitive ratio 2 [1,11]. The first algorithm with a competitive ratio strictly less than 2 called PG was presented by Kesselman et al. [4]. Englert and Westermann [5] showed that PG is 1.732- competitive but no better than 1.707-competitive. The lower bound of competitive ratio for deterministic algorithms is 1.419 [4]. For the two-valued model in which packets have value either 1 or α > 1, Kesselman and Mansour [6] proposed a1.544-competitive memoryless algorithm. Englert and Westermann [5] presented an optimal 1.282-competitive algorithm for the case when the buffer size goes to infinity. This algorithm [5] meets the lower bound [1]. However, the algorithm in [5] is not memoryless.In this paper, we present a 1.304-competitive memoryless algorithm for the two-valued model. In [3], an algorithm using marking bits achieves the same competitive ratio 1.304. The algorithm that we present in this paper is simpler and it does not use marking bits. All previous work proactively preempt packets. On the contrary, our algorithm drops packets in a ‘lazy’ manner. For this 2-valued model , closing or shrinking the gaps of [1.282, 1.304] for memoryless online algorithms remains an open problem. We hope that the idea presented in this paper will motivate an improved algorithm for the general FIFO model in which packets are with arbitrary values.