We consider the problem of managing a bounded size First-In-First-Out (FIFO) queue buffer, where each incoming unit-sized packet requires several rounds of processing before it can be transmitted out. Our objective is to maximize the total number of successfully transmitted packets. We consider both push-out (when the policy is permitted to drop already admitted packets) and non-push-out cases. In particular, we provide analytical guarantees for the throughput performance of our algorithms. We further conduct a comprehensive simulation study which experimentally validates the predicted theoretical behaviour.
@cite_2 were the first to consider buffer management and scheduling in the context of network processors with heterogeneous processing requirements for the arriving traffic. They study both SRPT (shortest remaining processing time) and FIFO (first-in-first-out) schedulers with recycles, in both push-out and non-push-out buffer management cases, where a packet is recycled after processing according to the priority policy (FIFO or SRPT). They showed competitive algorithms and worst-case lower bounds for such settings. Although they considered a different architecture (FIFO with recycles) than the one we consider in this paper, they provided only a lower bound for the push-out FIFO case, and it remains unknown if it can be attained.
@cite_2
2141282318
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 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. 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. Current network processors (NPs) increasingly deal with packets with heterogeneous processing times. In such an environment, packets that require many processing cycles delay low-latency traffic because the common approach in today's NPs is to employ run-to-completion processing. These difficulties have led to the emergence of the Multipass NP architecture, where after a processing cycle ends, all processed packets are recycled into the buffer and recompete for processing resources. In this paper, we provide a model that captures many of the characteristics of this architecture, and we consider several scheduling and buffer management algorithms that are specially designed to optimize the performance of multipass network processors. In particular, we provide analytical guarantees for the throughput performance of our algorithms. We further conduct a comprehensive simulation study, which validates our results. As the Internet becomes more mature, there is a realization that improving the performance of routers has the potential to substantially improve Internet performance in general. Currently, most routers forward packets in a First-In-First-Out (FIFO) order. However, the diversity of applications supported by modern IP-based networks has resulted in unpredictable packet flows, and heterogeneous network traffic. Thus, it is becoming more reasonable to consider differentiating between different types of packets, and perhaps to consider allowing packets to specify a deadline by which it must be processed. These issues have made buffer management at routers a critical issue in providing effective quality of service to the various applications that use the network. In this paper, we study an online problem in which each packet is described by its discrete arrival time, non-negative weight and discrete deadline; arriving packets are buffered for delivery and all packets have the same processing time. The packets arrive online, and our objective is to maximize the sum of weights of those packets that are sent by their deadlines. We describe an online deterministic algorithm with a competitive ratio of 1.854, improving the best previous known competitive ratio of 1.939 ( STACS 2004). The algorithmic framework we use has several interesting features. First, we do not use a potential function. Instead, after each step we modify the adversary's buffer. Second, we introduce "dummy packets" to facilitate the decision making. 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 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. Recent studies of Internet traffic have shown that flow size distributions often exhibit a high variability property in the sense that most of the flows are short and more than half of the total load is constituted by a small percentage of the largest flows. In the light of this observation, it is interesting to revisit scheduling policies that are known to favor small jobs in order to quantify the benefit for small and the penalty for large jobs. Among all scheduling policies that do not require knowledge of job size, the least attained service (LAS) scheduling policy is known to favor small jobs the most. We investigate the M G 1 LAS queue for both, load ? < 1 and ? = 1. Our analysis shows that for job size distributions with a high variability property, LAS favors short jobs with a negligible penalty to the few largest jobs, and that LAS achieves a mean response time over all jobs that is close to the mean response time achieved by SRPT.Finally, we implement LAS in the ns-2 network simulator to study its performance benefits for TCP flows. When LAS is used to schedule packets over the bottleneck link, more than 99 of the shortest flows experience smaller mean response times under LAS than under FIFO and only the largest jobs observe a negligible increase in response time. The benefit of using LAS as compared to FIFO is most pronounced at high load. We consider the online problem of non-preemptive queue management. An online sequence of packets arrive, each of which has an associated intrinsic value. Packets can be accepted to a FIFO queue, or discarded. The profit gained by transmitting a packet diminishes over time and is equal to its value minus the delay. This corresponds to the well known and strongly motivated Naor's model in operations research. We give a queue management algorithm with a competitive ratio equal to the golden ratio (φ a 1.618) in the case that all packets have the same value, along with a matching lower bound. We also derive Θ(1) upper and lower bounds on the competitive ratio when packets have different intrinsic values (in the case of differentiated services). We can extend our results to deal with more general models for loss of value over time. Finally, we re-interpret our online algorithms in the context of selfish agents, producing an online mechanism that approximates the optimal social welfare to within a constant factor. 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 a multiclass multiplexer with support for multiple service classes and dedicated buffers for each service class. Under specific scheduling policies for sharing bandwidth among these classes, we seek the asymptotic (as the buffer size goes to infinity) tail of the buffer overflow probability for each dedicated buffer. We assume dependent arrival and service processes as is usually the case in models of bursty traffic. In the standard large deviations methodology, we provide a lower and a matching (up to first degree in the exponent) upper bound on the buffer overflow probabilities. We introduce a novel optimal control approach to address these problems. In particular, we relate the lower bound derivation to a deterministic optimal control problem, which we explicitly solve. Optimal state trajectories of the control problem correspond to typical congestion scenarios. We explicitly and in detail characterize the most likely modes of overflow. We specialize our results to the generalized processor sharing policy (GPS) and the generalized longest queue first policy (GLQF). The performance of strict priority policies is obtained as a corollary. We compare the GPS and GLQF policies and conclude that GLQF achieves smaller overflow probabilities than GPS for all arrival and service processes for which our analysis holds. Our results have important implications for traffic management of high-speed networks and can be used as a basis for an admission control mechanism which guarantees a different loss probability for each class. 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. It is well known that head-of-line blocking limits the throughput of an input-queued switch with first-in-first-out (FIFO) queues. Under certain conditions, the throughput can be shown to be limited to approximately 58.6 . It is also known that if non-FIFO queueing policies are used, the throughput can be increased. However, it has not been previously shown that if a suitable queueing policy and scheduling algorithm are used, then it is possible to achieve 100 throughput for all independent arrival processes. In this paper we prove this to be the case using a simple linear programming argument and quadratic Lyapunov function. In particular, we assume that each input maintains a separate FIFO queue for each output and that the switch is scheduled using a maximum weight bipartite matching algorithm. We introduce two maximum weight matching algorithms: longest queue first (LQF) and oldest cell first (OCF). Both algorithms achieve 100 throughput for all independent arrival processes. LQF favors queues with larger occupancy, ensuring that larger queues will eventually be served. However, we find that LQF can lead to the permanent starvation of short queues. OCF overcomes this limitation by favoring cells with large waiting times. This article provides a detailed implementation study on the behavior of web serves that serve static requests where the load fluctuates over time (transient overload). Various external factors are considered, including WAN delays and losses and different client behavior models. We find that performance can be dramatically improved via a kernel-level modification to the web server to change the scheduling policy at the server from the standard FAIR (processor-sharing) scheduling to SRPT (shortest-remaining-processing-time) scheduling. We find that SRPT scheduling induces no penalties. In particular, throughput is not sacrificed and requests for long files experience only negligibly higher response times under SRPT than they did under the original FAIR scheduling. Motivated by the optimality of Shortest Remaining Processing Time (SRPT) for mean response time, in recent years many computer systems have used the heuristic of "favoring small jobs" in order to dramatically reduce user response times. However, rarely do computer systems have knowledge of exact remaining sizes. In this paper, we introduce the class of e-SMART policies, which formalizes the heuristic of "favoring small jobs" in a way that includes a wide range of policies that schedule using inexact job-size information. Examples of e-SMART policies include (i) policies that use exact size information, e.g., SRPT and PSJF, (ii) policies that use job-size estimates, and (iii) policies that use a finite number of size-based priority levels. For many e-SMART policies, e.g., SRPT with inexact job-size information, there are no analytic results available in the literature. In this work, we prove four main results: we derive upper and lower bounds on the mean response time, the mean slowdown, the response-time tail, and the conditional response time of e-SMART policies. In each case, the results explicitly characterize the tradeoff between the accuracy of the job-size information used to prioritize and the performance of the resulting policy. Thus, the results provide designers insight into how accurate job-size information must be in order to achieve desired performance guarantees. We study an online unit-job scheduling problem arising in buffer management. Each job is specified by its release time, deadline, and a nonnegative weight. Due to overloading conditions, some jobs have to be dropped. The goal is to maximize the total weight of scheduled jobs. We present several competitive online algorithms for various versions of unit-job scheduling, as well as some lower bounds on the competitive ratios. We first give a randomized algorithm RMix with competitive ratio of e (e-1) 1.582. This is the first algorithm for this problem with competitive ratio smaller than 2. Then we consider s-bounded instances, where the span of each job (deadline minus release time) is at most s. We give a 1.25-competitive randomized algorithm for 2-bounded instances, matching the known lower bound. We also give a deterministic algorithm Edf"@a, whose competitive ratio on s-bounded instances is 2-2 s+o(1 s). For 3-bounded instances its ratio is @f 1.618, matching the known lower bound. In s-uniform instances, the span of each job is exactly s. We show that no randomized algorithm can be better than 1.25-competitive on s-uniform instances, if the span s is unbounded. For s=2, our proof gives a lower bound of 4-22 1.172. Also, in the 2-uniform case, we prove a lower bound of 2 1.414 for deterministic memoryless algorithms, matching a known upper bound. Finally, we investigate the multiprocessor case and give a 1 (1-(mm+1)^m)-competitive algorithm for m processors. We also show improved lower bounds for the general and s-uniform cases. When scheduling single server systems, Shortest Remaining Processing Time (SRPT) minimizes the number of jobs in the system at every point in time. However, a major limitation of SRPT is that it requires job processing times a priori. In practice, it is likely that only estimates of job processing times are available. This paper proposes a policy that schedules jobs with estimated job processing times. The proposed Modified Comparison Splitting Scheduling (MCSS) policy is compared to SRPT when scheduling both single and multi-server systems. In the single server system we observe from simulations that the proposed scheduling policy provides robustness that is crucial for achieving good performance. In contrast, in a multi-server system we observe that robustness to estimation errors is not dependent on the scheduling policy. However, as the number of servers grows, SRPT becomes preferable. The power of two well-known consistency conditions for shared-memory multiprocessors, sequential consistency and linearizability , is compared. The cost measure studied is the worst-case response time in distributed implementations of virtual shared memory supporting one of the two conditions. Three types of shared-memory objects are considered: read write objects, FIFO queues, and stacks. If clocks are only approximately synchronized (or do not exist), then for all three object types it is shown that linearizability is more expensive than sequential consistency. We show that, for all three data types, the worst-case response time is very sensitive to the assumptions that are made about the timing information available to the system. Under the strong assumption that processes have perfectly synchronized clocks, it is shown that sequential consistency and linearizability are equally costly. We present upper bounds for linearizability and matching lower bounds for sequential consistency. The upper bounds are shown by presenting algorithms that use atomic broadcast in a modular fashion. The lower-bound proofs for the approximate case use the technique of “shifting,” first introduced for studying the clock synchronization problem. We consider the problem of maximizing the number of jobs completed by their deadline in an online single processor system where the jobs are preemptable and have release times. So in the standard three field scheduling notation, this is the online version of the problem 1 |ri; pmtn| Σ(1 - Ui). We present a deterministic algorithm Lax, and show that for every instance I, it is the case that either Lax, or the well-known deterministic algorithm SRPT (Shortest Remaining Processing Time), is constant competitive on I. An immediate consequence of this result is a constant competitive randomized algorithm for this problem. It is known that no constant competitive deterministic algorithm exists for this problem. Motivated by providing differentiated services in the Internet, we consider online buffer management algorithms for quality-of-service network switches. We study a multi-buffer model . Packets have values and deadlines; they arrive at a switch over time. The switch consists of multiple buffers whose sizes are bounded. In each time step, only one pending packet can be sent. Our objective is to maximize the total value of the packets sent by their deadlines. We employ competitive analysis to measure an online algorithm's performance. In this paper, we first show that the lower bound of competitive ratio of a broad family of online algorithms is 2. Then we propose a ( @math )-competitive deterministic algorithm, which is improved from the previously best-known result 9.82 (Azar and Levy. SWAT 2006).