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 2155749359 1964235381 2033562126 2136340918 1537647641 2120354662 1897771984 2022590452
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. Motivated by the quality-of-service (QoS) buffer management problem, we consider online scheduling of packets with hard deadlines in a finite capacity queue. At any time, a queue can store at most b isin Z + packets. Packets arrive over time. Each packet is associated with a non-negative value and an integer deadline. In each time step, only one packet is allowed to be sent. Our objective is to maximize the total value gained by the packets sent by their deadlines in an online manner. Due to the Internet traffic's chaotic characteristics, no stochastic assumptions are made on the packet input sequences. This model is called a finite-queue model. We use competitive analysis to measure an online algorithm's performance versus an unrealizable optimal offline algorithm who constructs the worst possible input based on the knowledge of the online algorithm. For the finite-queue model, we first present a deterministic 3-competitive memoryless online algorithm. Then, we give a randomized (Phi 2 = (1+radic(5) 2) 2 ap 2.618)-competitive memoryless online algorithm. The algorithmic framework and its theoretical analysis include several interesting features. First, our algorithms use (possibly) modified characteristics of packets; these characteristics may not be same as those specified in the input sequence. Second, our analysis method is different from the classical potential function approach. We use a simple charging scheme, which depends on a clever modification (during the course of the algorithm) on the packets in the queue of the optimal offline algorithm. We then prove that a set of invariants holds at the end of each time step. Finally, we analyze the two proposed algorithm in a relaxed model, in which packets have no hard deadlines but an order. We conclude that both algorithms have the same competitive ratios in the relaxed model. Abstract We introduce the problem of managing a FIFO buffer of bounded space, where arriving packets have dependencies among them. Our model is motivated by the scenario where large data frames must be split into multiple packets, because maximum packet size is limited by data-link restrictions. A frame is considered useful only if sufficiently many of its constituent packets are delivered. The buffer management algorithm decides, in case of overflow, which packets to discard and which to keep in the buffer. The goal of the buffer management algorithm is to maximize throughput of useful frames. This problem has a variety of applications, e.g., Internet video streaming, where video frames are segmented and encapsulated in IP packets sent over the Internet. We study the complexity of the above problem in both the offline and online settings. We give upper and lower bounds on the performance of algorithms using competitive analysis. We consider the setting of a network providing differentiated services. As is often the case in differentiated services, we assume that the packets are tagged as either being a high priority packet or a low priority packet. Outgoing links in the network are serviced by a single FIFO queue.Our model gives a benefit of α ≥ 1 to each high priority packet and a benefit of 1 to each low priority packet. A queue policy controls which of the arriving packets are dropped and which enter the queue. Once a packet enters the queue it is eventually sent. The aim of a queue policy is to maximize the sum of the benefits of all the packets it sends.We analyze and compare different queue policies for this problem using the competitive analysis approach, where the benefit of the online policy is compared to the benefit of an optimal offline policy. We derive both upper and lower bounds for the policies we consider. We believe that competitive analysis gives important insight to the performance of these queuing policies. We consider the problem of resource allocation in downlink OFDMA systems for multi service and unknown environment. Due to users' mobility and intercell interference, the base station cannot predict neither the Signal to Noise Ratio (SNR) of each user in future time slots nor their probability distribution functions. In addition, the traffic is bursty in general with unknown arrival. The probability distribution functions of the SNR, channel state and traffic arrival density are then unknown. Achieving a multi service Quality of Service (QoS) while optimizing the performance of the system (e.g. total throughput) is a hard and interesting task since it depends on the unknown future traffic and SNR values. In this paper we solve this problem by modeling the multiuser queuing system as a discrete time linear dynamic system. We develop a robust H∞ controller to regulate the queues of different users. The queues and Packet Drop Rates (PDR) are controlled by proposing a minimum data rate according to the demanded service type of each user. The data rate vector proposed by the controller is then fed as a constraint to an instantaneous resource allocation framework. This instantaneous problem is formulated as a convex optimization problem for instantaneous subcarrier and power allocation decisions. Simulation results show small delays and better fairness among users. We study the online problem of multiplexing packets with arbitrary deadlines in bounded multi-buffer switch. In this model, a switch consists of m input buffers each with bounded capacity B and one output port. Each arriving packet is associated with a value and a deadline that specifies the time limit till the packet can be transmitted. At each time step the switch can select any non-empty buffer and transmit one packet from that buffer. In the preemptive model, stored packets may be preempted from their buffers due to lack of buffer space or discarded due to the violation of the deadline constraints. If preemption is not allowed, every packet accepted and stored in the buffer must be transmitted before its deadline has expired. The goal is to maximize the benefit of the packets transmitted by their deadlines. To date, most models for packets with deadlines assumed a single buffer. To the best of our knowledge this is the first time a bounded multi-buffer switch is used with arbitrary deadline constraints Our main result is a 9.82-competitive deterministic algorithm for packets with arbitrary values and deadlines. Note that the greedy algorithm is not competitive. For the non-preemptive model we present a 2-competitive deterministic algorithm for the unit value packets. For arbitrary values we present a randomized algorithm whose competitiveness is logarithmic in the ratio between the largest and the smallest value of the packets in the sequence We consider a network providing Differentiated Services (Diffserv) which allow Internet service providers (ISP) to offer different levels of Quality of Service (QoS) to different traffic streams. We study FIFO buffering algorithms, where packets must be transmitted in the order they arrive. The buffer space is limited, and packets are lost if the buffer is full. Each packet has an intrinsic value, and the goal is to maximize the total value of transmitted packets. Our main contribution is an algorithm for arbitrary packet values that for the first time achieves a competitive ratio better than 2, namely 2-e for a constant e> 0. We consider the online problem of active queue management. In our model, the input is a sequence of packets with values v ∈ [1,α] that arrive to a queue that can hold up to B packets. Specifically, we consider a FIFO non-preemptive queue, where any packet that is accepted into the queue must be sent, and packets are sent by the order of arrival. The benefit of a scheduling policy, on a given input, is the sum of values of the scheduled packets. Our aim is to find an online policy that maximizes its benefit compared to the optimal offline solution. We consider the dispatching problem in a size- and state-aware multi-queue system with Poisson arrivals and queue-specific job sizes. By size- and state-awareness, we mean that the dispatcher knows the size of an arriving job and the remaining service times of the jobs in each queue. By queue-specific job sizes, we mean that the time to process a job may depend on the chosen server. We focus on minimizing the mean sojourn time (i.e., response time) by an MDP approach. First we derive the so-called size-aware relative values of states with respect to the sojourn time in an M G 1 queue operating under FIFO, LIFO, SPT or SRPT disciplines. For FIFO and LIFO, the size-aware relative values turn out to be insensitive to the form of the job size distribution. The relative values are then exploited in developing efficient dispatching rules in the spirit of the first policy iteration.