We consider scheduling of colored packets with transition costs which form a general metric space. We design a @math competitive algorithm. Our main result is a hardness result of @math which matches the competitive ratio of the algorithm for each metric space separately. In particular, we improve the hardness result of Azar at el. 2009 for uniform metric spaces. We also extend our result to weighted directed graphs which obey the triangular inequality and show a @math competitive algorithm and a nearly-matching hardness result. In proving our hardness results we use some interesting non-standard embedding.
In the FIFO queue model @cite_14 we are given a sequence of incoming packets. The packets are placed in a FIFO queue with bounded buffer size. The challenges for an online algorithm are to decide whether to accept or discard arriving packet, and to choose a queue for transmission in each time unit. The problem was studied in @cite_0 @cite_9 @cite_6 @cite_27 @cite_10 . Another related problem is the sorting buffer problem @cite_15 . In that problem we are given a server with unbounded capacity and an incoming sequence of requests. Each request corresponds to a point in a metric space. The goal is to serve all requests while minimizing the total distance traveled by the server. This problem can be interpreted as a multi-port device problem. This model was studied in @cite_25 @cite_29 @cite_12 @cite_13 @cite_23 .
@cite_13 @cite_14 @cite_9 @cite_29 @cite_6 @cite_0 @cite_27 @cite_23 @cite_15 @cite_10 @cite_25 @cite_12
2076648698 2169023571 1867520515 2593786213
We consider packet scheduling in a network providing differentiated services, where each packet is assigned a value. We study various queueing models for supporting QoS (Quality of Service). In the nonpreemptive model, packets accepted to the queue will be transmitted eventually and cannot be dropped. The FIFO preemptive model allows packets accepted to the queue to be preempted (dropped) prior to their departure, while ensuring that transmitted packets are sent in the order of arrival. In the bounded delay model, packets must be transmitted before a certain deadline, otherwise it is lost (while transmission ordering is allowed to be arbitrary). In all models the goal of the buffer policy is to maximize the total value of the accepted packets.Let α be the ratio between the maximal and minimal value. For the non-preemptive model we derive a Θ(log &alpha) competitive ratio, both exhibiting a buffer policy and a general lower bound. For the interesting case of two distinct values, we give an 2α--1 α competitive buffer policy, which exactly matches the lower bound. We also analyze a RED-like policy and derive its competitive ratio, which is approximately 2α--0.5 α for two values and Θ(log α) for multiple values. In addition we improve the previous known lower and upper bounds of the Fixed Partition and Flexible Partition policies.For the FIFO preemptive model, we improve the general lower bound and show a tight bound for the special case of queue size 2. We prove that the bounded delay model with uniform delay 2 is equivalent to a modified FIFO preemptive model with queue size 2. We then give improved upper and lower bounds on the 2-uniform bounded delay model. We also give lower bound for the 2-variable bounded delay model, which matches the previously known upper bound. We study a basic problem in Multi-Queue switches. A switch connects m input ports to a single output port. Each input port is equipped with an incoming FIFO queue with bounded capacity B. A switch serves its input queues by transmitting packets arriving at these queues, one packet per time unit. Since the arrival rate can be higher than the transmission rate and each queue has limited capacity, packet loss may occur as a result of insufficient queue space. The goal is to maximize the number of transmitted packets. This general scenario models most current networks (e.g., IP networks) which only support a “best effort” service in which all packet streams are treated equally. A 2-competitive algorithm for this problem was designed in [4] for arbitrary B. Recently, a ( 17 9 1.89 )-competitive algorithm was presented for B>1 in [2]. Our main result in this paper shows that for B which is not too small our algorithm can do better than 1.89, and approach a competitive ratio of ( e e-1 1.58 ). An instance of the sorting buffer problem consists of a metric space and a server, equipped with a finite-capacity buffer capable of holding a limited number of requests. An additional ingredient of the input is an online sequence of requests, each of which is characterized by a destination in the given metric; whenever a request arrives, it must be stored in the sorting buffer. At any point in time, a currently pending request can be served by drawing it out of the buffer and moving the server to its corresponding destination. The objective is to serve all input requests in a way that minimizes the total distance traveled by the server. In this paper, we focus our attention on instances of the problem in which the underlying metric is either an evenly-spaced or a continuous line metric. Our main findings can be briefly summarized as follows: 1. We present a deterministic O(log n) competitive algorithm for n- point evenly-spaced line metrics. This result improves on a randomized O(log2 n) competitive algorithm due to Khandekar and Pandit. 2. We devise a deterministic O(log N log log N) competitive algorithm for continuous line metrics, where N is the input sequence length. 3. We establish the first non-trivial lower bound for the evenly-spaced case, by proving that the competitive ratio of any deterministic algorithm is at least 2+√3 √3 ≅ 2.154. We consider FIFO buffer management for switches providing differentiated services. In each time step, an arbitrary number of packets arrive, and only one packet can be sent. The buffer can store a limited number of packets, and, due to the FIFO property, the sequence of sent packets has to be a subsequence of the arriving packets. The differentiated service model is abstracted by attributing each packet with a value according to its service level. A buffer management strategy can drop packets. The goal is to maximize the sum of values of sent packets. For only two different packet values, we introduce the account strategy and prove that this strategy achieves an optimal competitive ratio of ≈ 1.282, if the buffer size tends to infinity, and an optimal competitive ratio of (√13-1) 2 ≈ 1.303, for arbitrary buffer sizes. For general packet values, the simple preemptive greedy strategy (PG) is studied. We show that PG achieves a competitive ratio of √3 ≈ 1.732 which is the best known upper bound on the competitive ratio of this problem. In addition, we give a lower bound of of 1+1 √2 ≈ 1.707 on the competitive ratio of PG which improves the previously known lower bound. As a consequence, the competitive ratio of PG cannot be further improved significantly.