A survey of buffer management policies for packet switches
---
paper_title: Buffer Management Problems

paper_content:

In recent years, there has been a lot of interest in Quality of Service (QoS) networks. In regular IP networks, packets are indistinguishable and in case of overload any packet may be dropped. In a commercial environment, it is much more preferable to allow better service to higher-paying customers or customers with critical requirements. The idea of Quality of Service guarantees is that packets are marked with values which indicate their importance. This naturally leads to decision problems at network switches when many packets arrive and overload occurs. In this paper, we give an overview of several models that have been studied in this area from an online perspective. These models differ by restrictions such as bounded delay, bounded size of queue etc. We first present results for a single buffer in Section 1 and then for multiple buffers in Section 2. This paper is not meant as a comprehensive survey of the work in this area. There are many more variations of these problems that have been studied, for instance, multiple output buffers [14]. Our goal was merely to give a taste of this problem area, and we hope you enjoy it.
---
paper_title: Online Computation and Competitive Analysis

paper_content:

Preface 1. Introduction to competitive analysis: the list accessing problem 2. Introduction to randomized algorithms: the list accessing problem 3. Paging: deterministic algorithms 4. Paging: randomized algorithms 5. Alternative models for paging: beyond pure competitive analysis 6. Game theoretic foundations 7. Request - answer games 8. Competitive analysis and zero-sum games 9. Metrical task systems 10. The k-server problem 11. Randomized k-server algorithms 12. Load-balancing 13. Call admission and circuit-routing 14. Search, trading and portfolio selection 15. Competitive analysis and decision making under uncertainty Appendices Bibliography Index.
---
paper_title: Amortized efficiency of list update and paging rules

paper_content:

In this article we study the amortized efficiency of the “move-to-front” and similar rules for dynamically maintaining a linear list. Under the assumption that accessing the ith element from the front of the list takes t(i) time, we show that move-to-front is within a constant factor of optimum among a wide class of list maintenance rules. Other natural heuristics, such as the transpose and frequency count rules, do not share this property. We generalize our results to show that move-to-front is within a constant factor of optimum as long as the access cost is a convex function. We also study paging, a setting in which the access cost is not convex. The paging rule corresponding to move-to-front is the “least recently used” (LRU) replacement rule. We analyze the amortized complexity of LRU, showing that its efficiency differs from that of the off-line paging rule (Belady's MIN algorithm) by a factor that depends on the size of fast memory. No on-line paging algorithm has better amortized performance.
---
paper_title: Competitive queue management for latency sensitive packets

paper_content:

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.
---
paper_title: Three dozen papers on online algorithms

paper_content:

This column contains a summary of last year's research on online algorithms presented at the STOC, FOCS, ICALP, ESA, and STACS conferences. Unfortunately, due to space constraints, the report could not be entirely exhaustive, and results from other conferences or journal articles are not covered. We hope that all readers will find in the survey something of interest, to fill those long winter evenings. The papers in the report are organized roughly by applications.
---
paper_title: Competitive buffer management with packet dependencies

paper_content:

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.
---
paper_title: Competitive Queue Policies for Differentiated Services

paper_content:

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.
---
paper_title: Competitive queueing policies for QoS switches

paper_content:

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.
---
paper_title: Analysis of queueing policies in QoS switches

paper_content:

It is widely accepted that next-generation networks will provide guaranteed services, in contrast to the "best effort" approach today. We study and analyze queueing policies for network switches that support the QoS (Quality of Service) feature. One realization of the QoS feature is that packets are not necessarily all equal, with some having higher priorities than the others. We model this situation by assigning an intrinsic value to each packet. In this paper we are concerned with three different queueing policies: the nonpreemptive model, the FIFO preemptive model, and the bounded delay model. We concentrate on the situation where the incoming traffic overloads the queue, resulting in packet loss. The objective is to maximize the total value of packets transmitted by the queueing policy. The difficulty lies in the unpredictable nature of the future packet arrivals. We analyze the performance of the online queueing policies via competitive analysis, providing upper and lower bounds for the competitive ratios. We develop practical yet sophisticated online algorithms (queueing policies) for the three queueing models. The algorithms in many cases have provably optimal worst- case bounds. For the nonpreemptive model, we devise an optimal online algorithm for the common 2-value model. We provide a tight logarithmic bound for the general nonpreemptive model. For the FIFO preemptive model, we improve the general lower bound to 1.414, while showing a tight bound of 1.434 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 show an improved lower bound of 1.618 for the 2-variable bounded delay model, matching the previously known upper bound.
---
paper_title: Competitive management of non-preemptive queues with multiple values

paper_content:

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.
---
paper_title: Lower and Upper Bounds on FIFO Buffer Management in QoS Switches

paper_content:

We consider the management of FIFO buffers for network 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, and the goal is to maximize the sum of the 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 if the buffer size tends to infinity and an optimal competitive ratio of 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 which is the best known upper bound on the competitive ratio of this problem. In addition, we give a lower bound of 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.
---
paper_title: Loss-bounded analysis for differentiated services

paper_content:

We consider a network providing Differentiated Services (DiffServ) which allow network service providers to offer different levels of Quality of Service (QoS) to different traffic streams. We focus on loss and first show that only trivial bounds could be obtained by means of traditional competitive analysis. Then we introduce a new approach for estimating loss of an online policy called loss-bounded analysis. In loss-bounded analysis the loss of an online policy is bounded by the loss of an optimal offline policy plus a constant fraction of the benefit of the online policy. We relate the loss-bounded analysis to the throughput-competitive analysis. We derive tight upper and lower bounds for various settings of DiffServ parameters using the new loss-bounded model. We believe that loss-bounded analysis is an important technique that can complement traditional competitive analysis providing new insight and interesting results.
---
paper_title: Buffer Management Problems

paper_content:

In recent years, there has been a lot of interest in Quality of Service (QoS) networks. In regular IP networks, packets are indistinguishable and in case of overload any packet may be dropped. In a commercial environment, it is much more preferable to allow better service to higher-paying customers or customers with critical requirements. The idea of Quality of Service guarantees is that packets are marked with values which indicate their importance. This naturally leads to decision problems at network switches when many packets arrive and overload occurs. In this paper, we give an overview of several models that have been studied in this area from an online perspective. These models differ by restrictions such as bounded delay, bounded size of queue etc. We first present results for a single buffer in Section 1 and then for multiple buffers in Section 2. This paper is not meant as a comprehensive survey of the work in this area. There are many more variations of these problems that have been studied, for instance, multiple output buffers [14]. Our goal was merely to give a taste of this problem area, and we hope you enjoy it.
---
paper_title: Competitive queueing policies for QoS switches

paper_content:

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.
---
paper_title: Loss-bounded analysis for differentiated services

paper_content:

We consider a network providing Differentiated Services (DiffServ) which allow network service providers to offer different levels of Quality of Service (QoS) to different traffic streams. We focus on loss and first show that only trivial bounds could be obtained by means of traditional competitive analysis. Then we introduce a new approach for estimating loss of an online policy called loss-bounded analysis. In loss-bounded analysis the loss of an online policy is bounded by the loss of an optimal offline policy plus a constant fraction of the benefit of the online policy. We relate the loss-bounded analysis to the throughput-competitive analysis. We derive tight upper and lower bounds for various settings of DiffServ parameters using the new loss-bounded model. We believe that loss-bounded analysis is an important technique that can complement traditional competitive analysis providing new insight and interesting results.
---
paper_title: Improved Competitive Guarantees for QoS Buffering

paper_content:

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.
---
paper_title: Analysis of queueing policies in QoS switches

paper_content:

It is widely accepted that next-generation networks will provide guaranteed services, in contrast to the "best effort" approach today. We study and analyze queueing policies for network switches that support the QoS (Quality of Service) feature. One realization of the QoS feature is that packets are not necessarily all equal, with some having higher priorities than the others. We model this situation by assigning an intrinsic value to each packet. In this paper we are concerned with three different queueing policies: the nonpreemptive model, the FIFO preemptive model, and the bounded delay model. We concentrate on the situation where the incoming traffic overloads the queue, resulting in packet loss. The objective is to maximize the total value of packets transmitted by the queueing policy. The difficulty lies in the unpredictable nature of the future packet arrivals. We analyze the performance of the online queueing policies via competitive analysis, providing upper and lower bounds for the competitive ratios. We develop practical yet sophisticated online algorithms (queueing policies) for the three queueing models. The algorithms in many cases have provably optimal worst- case bounds. For the nonpreemptive model, we devise an optimal online algorithm for the common 2-value model. We provide a tight logarithmic bound for the general nonpreemptive model. For the FIFO preemptive model, we improve the general lower bound to 1.414, while showing a tight bound of 1.434 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 show an improved lower bound of 1.618 for the 2-variable bounded delay model, matching the previously known upper bound.
---
paper_title: Nearly optimal fifo buffer management for two packet classes

paper_content:

We consider a FIFO buffer with finite storage space. An arbitrary input stream of packets arrives at the buffer, but the output stream rate is bounded, so overflows may occur. We assume that each packet has value which is either 1 or α, for some α > 1. The buffer management task is to decide which packets to drop so as to minimize the total value of lost packets, subject to the buffer space bound, and to the FIFO order of sent packets. We consider push-out buffers, where the algorithm may eject packets from anywhere in the buffer. The best lower bound on the competitive ratio of on-line algorithms for buffer management is approximately 1.28. In this paper we present an on-line algorithm whose competitive ratio is approximately 1.30 for the worst case α. The best previous general upper bound was about 1.888.
---
paper_title: Nearly optimal FIFO buffer management for DiffServ

paper_content:

We consider a FIFO buffer with finite storage space. An arbitrary input stream of packets arrives at the buffer, but the output stream rate is bounded, so overflows may occur. Motivated by DiffServ, we assume that each packet has value either 1 or α, for some α > 1. The buffer management task is to decide which packets to drop so as to minimize the total value of lost packets, subject to the buffer space bound, and to the FIFO order of sent packets. We consider push-out buffers, where the algorithm may eject packets from anywhere in the buffer. The best lower bound on the competitive ratio of on-line algorithms for buffer management is approximately 1.28. In this paper we present an on-line algorithm whose competitive ratio is approximately 1.30 for the worst case α. The best previous general upper bound was about 1.888.
---
paper_title: An optimal online algorithm for packet scheduling with agreeable deadlines

paper_content:

An important issue in IP-based QoS networks is the effective management of packets at the router level. Specifically, if the arriving packets cannot all be stored in a buffer, or if the packets have deadlines by which they must be delivered, the router needs to identify the packets that should be dropped. In recent work, Kesselman et al. [6] propose a model, called buffer management with bounded delay, which can be thought of as an online scheduling problem on a single machine: packets arrive at a network switch and are stored in a buffer of size B. Each packet has a positive weight and a deadline, with the weight representing the value of transmitting the packet by its deadline. At each integer time step, exactly one packet can be transmitted, and the objective is to maximize the total weight of the transmitted packets. If B = ∞, this is the online version of the scheduling problem 1| p j = 1, r j , d j |Σ w j U j . (We assume that r j and d j are integers.)
---
paper_title: Randomized Algorithms for Buffer Management with 2-Bounded Delay

paper_content:

In the problem of buffer management with bounded delay, packets with weights and deadlines arrive at a network switch over time, and the goal is to send those packets on the outgoing link while maximizing the total weight of the packets that are sent before their deadlines expire. In the 2-bounded delay case, each packet has to be sent either in the step of its release or in the next step. In the deterministic case, the optimal competitive ratio for this case is φ ≅ 1.618. In the randomized case, against oblivious adversaries, the optimal competitive ratio is 1.25. The only yet unresolved case is that of randomized algorithms against adaptive adversaries. For this case, we give a complete solution by proving that the optimal competitive ratio is 4/3. Additionally, we give a lower bound of 1.2 for the 2-uniform case.
---
paper_title: Competitive queueing policies for QoS switches

paper_content:

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.
---
paper_title: Analysis of queueing policies in QoS switches

paper_content:

It is widely accepted that next-generation networks will provide guaranteed services, in contrast to the "best effort" approach today. We study and analyze queueing policies for network switches that support the QoS (Quality of Service) feature. One realization of the QoS feature is that packets are not necessarily all equal, with some having higher priorities than the others. We model this situation by assigning an intrinsic value to each packet. In this paper we are concerned with three different queueing policies: the nonpreemptive model, the FIFO preemptive model, and the bounded delay model. We concentrate on the situation where the incoming traffic overloads the queue, resulting in packet loss. The objective is to maximize the total value of packets transmitted by the queueing policy. The difficulty lies in the unpredictable nature of the future packet arrivals. We analyze the performance of the online queueing policies via competitive analysis, providing upper and lower bounds for the competitive ratios. We develop practical yet sophisticated online algorithms (queueing policies) for the three queueing models. The algorithms in many cases have provably optimal worst- case bounds. For the nonpreemptive model, we devise an optimal online algorithm for the common 2-value model. We provide a tight logarithmic bound for the general nonpreemptive model. For the FIFO preemptive model, we improve the general lower bound to 1.414, while showing a tight bound of 1.434 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 show an improved lower bound of 1.618 for the 2-variable bounded delay model, matching the previously known upper bound.
---
paper_title: Improved online algorithms for buffer management in QoS switches

paper_content:

We consider the following buffer management problem arising in QoS networks: Packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. Packets not forwarded before their deadlines are lost. The main result of the article is an online 64/33 a 1.939-competitive algorithm, the first deterministic algorithm for this problem with competitive ratio below 2. For the 2-uniform case we give an algorithm with ratio a 1.377 and a matching lower bound.
---
paper_title: An optimal online algorithm for packet scheduling with agreeable deadlines

paper_content:

An important issue in IP-based QoS networks is the effective management of packets at the router level. Specifically, if the arriving packets cannot all be stored in a buffer, or if the packets have deadlines by which they must be delivered, the router needs to identify the packets that should be dropped. In recent work, Kesselman et al. [6] propose a model, called buffer management with bounded delay, which can be thought of as an online scheduling problem on a single machine: packets arrive at a network switch and are stored in a buffer of size B. Each packet has a positive weight and a deadline, with the weight representing the value of transmitting the packet by its deadline. At each integer time step, exactly one packet can be transmitted, and the objective is to maximize the total weight of the transmitted packets. If B = ∞, this is the online version of the scheduling problem 1| p j = 1, r j , d j |Σ w j U j . (We assume that r j and d j are integers.)
---
paper_title: An optimal online algorithm for packet scheduling with agreeable deadlines

paper_content:

An important issue in IP-based QoS networks is the effective management of packets at the router level. Specifically, if the arriving packets cannot all be stored in a buffer, or if the packets have deadlines by which they must be delivered, the router needs to identify the packets that should be dropped. In recent work, Kesselman et al. [6] propose a model, called buffer management with bounded delay, which can be thought of as an online scheduling problem on a single machine: packets arrive at a network switch and are stored in a buffer of size B. Each packet has a positive weight and a deadline, with the weight representing the value of transmitting the packet by its deadline. At each integer time step, exactly one packet can be transmitted, and the objective is to maximize the total weight of the transmitted packets. If B = ∞, this is the online version of the scheduling problem 1| p j = 1, r j , d j |Σ w j U j . (We assume that r j and d j are integers.)
---
paper_title: Better online buffer management

paper_content:

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 (Bartal et al. 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.
---
paper_title: Considering suppressed packets improves buffer management in QoS switches

paper_content:

The following buffer management problem arises in network switches providing differentiated services: At the beginning of each time step, one packet can be sent, and afterwards an arbitrary number of new packets arrive. Packets that are not sent can be stored in a buffer. Each packet is attributed by a deadline, and a packet is automatically deleted from the buffer if it is still stored in the buffer by the end of its deadline. The differentiated service model is abstracted by attributing each packet with a value according to its service level. A buffer management strategy determines the packet to be sent in each time step. The goal of a buffer management strategy is to maximize the sum of the values of sent packets. We introduce the concept of suppressed packets and present a deterministic strategy that is based on this concept. We show that this strategy achieves a competitive ratio of 2√2--1 a 1.828, which is the best known competitive ratio in the deterministic case. Further, we present a memoryless version of this strategy that achieves a competitive ratio of a 1.893. This is the first memoryless strategy that achieves a competitive ratio less than 2, and the competitive ratio of this strategy is even better than the ratios of all previously known deterministic strategies. This demonstrates the potential of the concept of suppressed packets. In addition, we present a simple strategy that achieves the optimal competitive ratio of min{(1 + α)/α, 2α/(α+1)} ≤ √2, if only two packet values 1 and α > 1 are possible.
---
paper_title: Randomised Buffer Management with Bounded Delay against Adaptive Adversary

paper_content:

We give a new analysis of the RMix algorithm by Chin et al. for the Buffer Management with Bounded Delay problem (or online scheduling of unit jobs to maximise weighted throughput). Unlike the original proof of e/(e-1)-competitiveness, the new one holds even in adaptive-online adversary model. In fact, the proof works also for a slightly more general problem studied by Bie{\'n}kowski et al.
---
paper_title: Improved online algorithms for buffer management in QoS switches

paper_content:

We consider the following buffer management problem arising in QoS networks: Packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. Packets not forwarded before their deadlines are lost. The main result of the article is an online 64/33 a 1.939-competitive algorithm, the first deterministic algorithm for this problem with competitive ratio below 2. For the 2-uniform case we give an algorithm with ratio a 1.377 and a matching lower bound.
---
paper_title: Harmonic buffer management policy for shared memory switches

paper_content:

In this paper we consider shared-memory switches. We introduce a novel general nonpreemptive buffer management scheme, which considers the queues ordered by their size. We propose a new scheduling policy, based on our general scheme, which we call the Harmonic policy. We analyze the performance of the Harmonic policy by means of competitive analysis and demonstrate that its throughput competitive ratio is at most ln(N) + 2, where N is the number of output ports. We also present a lower bound of Ω(log N/log log N) on the performance of any online deterministic policy. Our simulations also show that the Harmonic policy achieves high throughput and easily adapts to changing load conditions.
---
paper_title: Management of multi-queue switches in QoS networks

paper_content:

The concept of Quality of Service (QoS) networks has gained growing attention recently, as the traffic volume in the Internet constantly increases, and QoS guarantees are essential to ensure proper operation of most communication based applications. A QoS switch serves m incoming queues by transmitting packets arriving at these queues through one output port, one packet per time unit. Each packet is marked with a value indicating its guaranteed quality of service. Since the queues have bounded capacity and the rate of arriving packets can be much higher than the transmission rate, packets can be lost due to insufficient queue space. The goal is to maximize the total value of transmitted packets. This problem encapsulates two dependent questions: admission control, namely which packets to discard in case of queue overflow, and scheduling, i.e. which queue to use for transmission in each time unit. We use competitive analysis to study online switch performance in QoS based networks. Specifically, we provide a novel generic technique that decouples the admission control and scheduling problems. Our technique transforms any single queue admission control strategy (preemptive or nonpreemptive) to a scheduling and admission control algorithm for our general m queues model, whose competitive ratio is at most twice the competitive ratio of the given admission control strategy. We use our technique to derive concrete algorithms for the general preemptive and nonpreemptive cases, as well as for the interesting special cases of the 2-value model and the unit value model. To the best of our knowledge this is the first result combining both scheduling and admission control decisions for arbitrary packets sequences in multi-queue switches. We also provide a 1.58-competitive randomized algorithm for the unit value case. This case is interesting by itself since most current networks (e.g. IP networks) only support a best-effort service in which all packets streams are treated equally.
---
paper_title: Packet buffering: randomization beats deterministic algorithms

paper_content:

We consider the problem of buffering unit value data packets in multi-queue network switches where each of the switch's input ports is equipped with a buffer of limited capacity. At these ports, packets arrive online and can be stored within the space limitations or must be discarded. Our objective is the maximization of the number of forwarded packets where, per time step, at most one packet from the set of buffers can be transmitted to the output port. ::: ::: In this paper, we give a technique for transforming any randomized algorithm for unit buffers into a randomized algorithm for buffers with arbitrary capacities while maintaining the competitiveness. We present the first randomized online algorithm that beats the deterministic lower bound of e/(e – 1) ≈ 1.58. It is 3/2-competitive and thus nearly matches the randomized lower bound of 1.46. For buffers with 2 queues having large capacities, we show a lower bound of 16/13 ≈ 1.23 for any online algorithm and prove that the competitive ratio of greedy algorithms is 9/7 ≈ 1.29, improving the best previously known upper bound of 3/2.
---
paper_title: The zero-one principle for switching networks

paper_content:

Recently, approximation analysis has been extensively used to study algorithms for routing weighted packets in various network settings. Although different techniques were applied in the analysis of diverse models, one common property was evident: the analysis of input sequences composed solely of two different values is always substantially easier, and many results are known only for restricted value sequences. Motivated by this, we introduce our zero-one principle for switching networks which characterizes a wide range of algorithms for which achieving c-approximation (as well as c-competitiveness) with respect to sequences composed of 0's and 1's implies achieving c-approximation. The zero-one principle proves to be very efficient in the design of switching algorithms, and substantially facilitates their analysis. We present three applications. First, we consider the Multi-Queue QoS Switching model and design a 3-competitive algorithm, improving the result from [6]. Second, we study the Weighted Dynamic Routing problem on a line topology of length k and present a (k+1)-competitive algorithm, which improves and generalizes the results from [1,12]. As a third application, we consider the work of [11], that compares the performance of local algorithms to the global optimum in various network topologies, and generalize their results from 2-value sequences to arbitrary value sequences.
---
paper_title: Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers

paper_content:

We study packet buffering, a basic problem occurring in network switches. We construct an optimal 16/13-competitive randomized online algorithm PB for the case of two input buffers of arbitrary sizes. Our proof is based on geometrical transformations which allow to identify the set of sequences incurring extremal competitive ratios. Later we may analyze the performance of PB on these sequences only.
---
paper_title: Competitive buffer management for multi-queue switches in qos networks using packet buffering algorithms

paper_content:

The online buffer management problem formulates the problem of queuing policies of network switches supporting QoS (Quality of Service) guarantee. We focus on multi-queue switches in QoS networks proposed by Azar et al. They introduced so-called "the relaxed model". Also, they showed that if the competitive ratio of the single-queue model is at most c, and if the competitive ratio of the relaxed model is at most c2, then the competitive ratio of the multi-queue switch model is cc2. They proved that c2d2, and obtained upper bounds on the competitive ratios for several multi-queue switch models. In this paper, we propose an online algorithm called DS (Dual Scheduling) for the competitive ratio of the relaxed model and obtain some better competitive ratios of the 2-value multi-queue switch model, where the value of packets is restricted to 1 and α(e1). DS uses as subroutine any online algorithms A for the non-preemptive unit-value switch model, which has also been extensively studied. We prove that if the competitive ratio of A is at most c, then the competitive ratio of DS is at most αc(2--c) + c2--2c+2Dα(2--c)+c--1, which is strictly better than 2. The followings are a couple of examples of the improvement on the competitive ratios of the 2-value multi-queue switch models using our result: (i) We have improved the competitive ratio of deterministic algorithms for the non-preemptive 2-value multi-queue switch model from 4 to 3.177 for large enough B, where B is the number of packets each queue can simultaneously store. (ii) We have proved that the competitive ratio of randomized algorithms for the non-preemptive 2-value multi-queue switch model is at most 17D2--30≈3.023 for large enough B.
---
paper_title: An Experimental Study of New and Known Online Packet Buffering Algorithms

paper_content:

We present the first experimental study of online packet buffering algorithms for network switches. We consider a basic scenario in which m queues of size B have to be maintained so as to maximize the packet throughput. For this model various online algorithms with competitive factors ranging between 2 and 1.5 were developed in the literature. We first develop a new 2-competitive online algorithm, called HSFOD, which is especially designed to perform well under real-world conditions. In our experimental study we have implemented all the proposed algorithms, including HSFOD, and tested them on packet traces from benchmark libraries. We have evaluated the experimentally observed competitiveness, the running times, memory requirements and actual packet throughput of the strategies. The tests were executed for varying values of m and B as well as varying switch speeds. It shows that greedy-like strategies and HSFOD perform best in practice.
---
paper_title: Scheduling policies for CIOQ switches

paper_content:

Combined input and output queued (CIOQ) architectures with a moderate fabric speedup S > 1 have come to play a major role in the design of high performance switches. The switch policy that controls such switches must consist of two components. A buffer management policy that controls admission to buffers, and a scheduling policy that is responsible for the transfer of packets from input butters to output buffers. The goal of the switch policy is to maximize the throughput of the switch. When all packets have a uniform value (or importance), this corresponds to the number of packets sent from the switch. When packets have variable values, this corresponds to the total value of the sent packets.We derive a number of scheduling policies for CIOQ switches and analyze their throughput using competitive analysis. We thus give for these policies a uniform throughput guarantee, regardless of specific traffic patterns. For the case of packets with uniform values we present a switch policy that is 3-competitive for any speedup. For the case of packets with variable values we propose two switch policies. One achieves a competitive ratio of 4S, and the other achieves a competitive ratio of 8 rain(k, 2 ⌈logα⌉), where k is the number of distinct packet values and α is the ratio between the largest and the smallest value.
---
paper_title: CONTROLLING CIOQ SWITCHES WITH PRIORITY QUEUING AND IN MULTISTAGE INTERCONNECTION NETWORKS

paper_content:

Combined input and output queued (CIOQ) architectures with a moderate fabric speedupS > 1 have come to play a major role in the design of high performance switches. In this paper we study CIOQ switches in two settings. The first is a setting of a single CIOQ switch with Priority Queuing (PQ) buffers, which provide better Quality of Service (QoS) guarantees by decreasing the delay experienced by mission-critical and real-time traffic. The second is a setting of a Multistage Interconnection Network (MIN), where each Switching Element (SE) is a CIOQ switch. In the first setting, we consider the case of traffic with packets having variable values. The goal of the switch policy is to maximize the total value of packets sent out of the switch. We present a switch policy that is 6-competitive for any speedup. In the second setting, we study a MIN architecture in which each internal buffer is further divided into virtual buffers, one per each MIN output port reachable from that buffer. We consider the case of traffic with unit value packets, and the goal of the policy managing the MIN is to maximize the total number of packets sent out of the MIN. We give a local memoryless switch policy that uses back pressure and achieves a competitive ratio of (4h + 1), where h is the number of stages of the MIN. The proposed policy is simple and can be efficiently implemented at high speeds. We also demonstrate a lower bound of h/2 on the competitive ratio of any local work-conserving deterministic memoryless switch policy. We further show that without back pressure, no online local work-conserving deterministic switch policy can break the competitive ratio of , where N is the size of the MIN and k is the size of an SE.
---
paper_title: Improved Competitive Performance Bounds for CIOQ Switches

paper_content:

Combined Input and Output Queued (CIOQ) architectures with a moderate fabric speedup S>1 have come to play a major role in the design of high performance switches. In this paper we study CIOQ switches with First-In-First-Out (FIFO) buffers providing Quality of Service (QoS) guarantees. The goal of the switch policy is to maximize the total value of packets sent out of the switch. We analyze the performance of a switch policy by means of competitive analysis, where a uniform worst-case performance guarantee is provided for all traffic patterns. Azar and Richter (ACM Trans. Algorithms 2(2):282–295, 2006) proposed the β-PG algorithm (Preemptive Greedy with a preemption factor of β) that is 8-competitive for an arbitrary speedup value when β=3. We improve upon their result by showing that this algorithm achieves a competitive ratio of 7.5 and 7.47 for β=3 and β=2.8, respectively. Basically, we demonstrate that β-PG is at most $\frac{\beta^{2} + 2\beta}{\beta - 1}$ and at least $\frac{\beta^{2}}{\beta - 1}$ -competitive.
---
paper_title: Packet mode and QoS algorithms for buffered crossbar switches with FIFO queuing

paper_content:

The buffered crossbar switch architecture has recently gained considerable research attention. In such a switch, besides normal input and output queues, a small buffer is associated with each crosspoint. Due to the introduction of crossbar buffers, output and input dependency is eliminated, and the scheduling process is greatly simplified. We analyze the performance of switch policies by means of competitive analysis, where a uniform guarantee is provided for all traffic patterns. We assume that each packet has an intrinsic value designating its priority and the goal of the switch policy is to maximize the weighted throughput of the switch. We consider FIFO queueing buffering policies, which are deployed by the majority of today’s Internet routers. In packet-mode scheduling, a packet is divided into a number of unit length cells and the scheduling policy is constrained to schedule all the cells contiguously, which removes reassembly overhead and improves Quality-of-Service. For the case of variable length packets with uniform value density (Best Effort model), where the packet value is proportional to its size, we present a packet-mode greedy switch policy that is 7-competitive. For the case of unit size packets with variable values (Differentiated Services model), we propose a β-preemptive (β is a preemption factor) greedy switch policy that achieves a competitive ratio of 6 + 4β + β ::: 2 + 3/(β − 1). In particular, its competitive ratio is at most 19.95 for the preemption factor of β = 1.67. As far as we know, this is the first constant-competitive FIFO policy for this architecture in the case of variable value packets. In addition, we evaluate performance of β-preemptive greedy switch policy by simulations and show that it outperforms other natural switch policies. The presented policies are simple and thus can be efficiently implemented at high speeds. Moreover, our results hold for any value of the internal switch fabric speedup.
---
paper_title: Best Effort and Priority Queuing Policies for Buffered Crossbar Switches

paper_content:

The buffered crossbar switch architecture has recently gained considerable research attention. In such a switch, besides normal input and output queues, a small buffer is associated with each crosspoint. Due to the introduction of crossbar buffers, output and input contention is eliminated, and the scheduling process is greatly simplified. We analyze the performance of switch policies by means of competitive analysis, where a uniform guarantee is provided for all traffic patterns. The goal of the switch policy is to maximize the weighted throughput of the switch, that is the total value of packets sent out of the switch. For the case of unit value packets (Best Effort), we present a simple greedy switch policy that is 4-competitive. For the case of variable value packets, we consider the Priority Queueing (PQ) mechanism, which provides better Quality of Service (QoS) guarantees by decreasing the delay of real-time traffic. We propose a preemptive greedy switch policy that achieves a competitve ratio of 18. Our results hold for any value of the switch fabric speedup. Moreover, the presented policies incur low overhead and are amenable to efficient hardware implementation at wire speed. To the best of our knowledge, this is the first work on competitive analysis for the buffered crossbar switch architecture.
---
paper_title: Increasing Machine Speed in On-Line Scheduling of Weighted Unit-Length Jobs in Slotted Time

paper_content:

We consider the following scheduling problem: Given a set of unit-length jobs characterized by release times, deadlines and weights an algorithm must pick at most one job for each unit of time with the goal of maximizing the total weight of the chosen jobs. An on-line algorithm is an algorithm which has no information about a job before its release time. In the basic version of this problem it is known that any on-line algorithm is outperformed by an optimal off-line algorithm by a factor of ${{1+\sqrt{5}}\over{2}}-\varepsilon$ on some instance. In this paper we examine the effect of increasing the on-line algorithm's speed --- that is the number of jobs chosen for each unit of time --- and show that no speedup can fully compensate for the lack of complete information.
---
paper_title: Harmonic buffer management policy for shared memory switches

paper_content:

In this paper we consider shared-memory switches. We introduce a novel general nonpreemptive buffer management scheme, which considers the queues ordered by their size. We propose a new scheduling policy, based on our general scheme, which we call the Harmonic policy. We analyze the performance of the Harmonic policy by means of competitive analysis and demonstrate that its throughput competitive ratio is at most ln(N) + 2, where N is the number of output ports. We also present a lower bound of Ω(log N/log log N) on the performance of any online deterministic policy. Our simulations also show that the Harmonic policy achieves high throughput and easily adapts to changing load conditions.
---
paper_title: Optimal buffer management via resource augmentation

paper_content:

We study a buffer management problem in network switches supporting QoS(Quality of Service) Each input or output port has a buffer of limited capacity which can store up to B packets Packets arrive online and a buffer management policy determines which packets are transmitted through the buffer After admitted into the buffer by the policy, packets are transmitted in FIFO fashion, that is, in the order they arrive Each packet has a value and the goal of the policy is to maximize the total value of packets transmitted. ::: ::: The main contribution is to apply resource augmentation analysis to the problem, investigating the optimality of various online policies The online policy has more resources than the optimal offline policy, that is, additional buffer and a higher transmission rate For two types of models, nonpreemptive and preemptive, we derive optimal online policies with additional buffer or a higher transmission rate Also we prove lower bounds of the resources for any optimal online policy.
---
paper_title: Considering suppressed packets improves buffer management in QoS switches

paper_content:

The following buffer management problem arises in network switches providing differentiated services: At the beginning of each time step, one packet can be sent, and afterwards an arbitrary number of new packets arrive. Packets that are not sent can be stored in a buffer. Each packet is attributed by a deadline, and a packet is automatically deleted from the buffer if it is still stored in the buffer by the end of its deadline. The differentiated service model is abstracted by attributing each packet with a value according to its service level. A buffer management strategy determines the packet to be sent in each time step. The goal of a buffer management strategy is to maximize the sum of the values of sent packets. We introduce the concept of suppressed packets and present a deterministic strategy that is based on this concept. We show that this strategy achieves a competitive ratio of 2√2--1 a 1.828, which is the best known competitive ratio in the deterministic case. Further, we present a memoryless version of this strategy that achieves a competitive ratio of a 1.893. This is the first memoryless strategy that achieves a competitive ratio less than 2, and the competitive ratio of this strategy is even better than the ratios of all previously known deterministic strategies. This demonstrates the potential of the concept of suppressed packets. In addition, we present a simple strategy that achieves the optimal competitive ratio of min{(1 + α)/α, 2α/(α+1)} ≤ √2, if only two packet values 1 and α > 1 are possible.
---
paper_title: Competitive queue management for latency sensitive packets

paper_content:

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.
---
paper_title: Competitive buffer management with packet dependencies

paper_content:

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.
---
paper_title: An optimal online algorithm for packet scheduling with agreeable deadlines

paper_content:

An important issue in IP-based QoS networks is the effective management of packets at the router level. Specifically, if the arriving packets cannot all be stored in a buffer, or if the packets have deadlines by which they must be delivered, the router needs to identify the packets that should be dropped. In recent work, Kesselman et al. [6] propose a model, called buffer management with bounded delay, which can be thought of as an online scheduling problem on a single machine: packets arrive at a network switch and are stored in a buffer of size B. Each packet has a positive weight and a deadline, with the weight representing the value of transmitting the packet by its deadline. At each integer time step, exactly one packet can be transmitted, and the objective is to maximize the total weight of the transmitted packets. If B = ∞, this is the online version of the scheduling problem 1| p j = 1, r j , d j |Σ w j U j . (We assume that r j and d j are integers.)
---
paper_title: Multiplexing packets with arbitrary deadlines in bounded buffers

paper_content:

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.
---
paper_title: Bounded Delay Packet Scheduling in a Bounded Buffer

paper_content:

We study buffer management in QoS-enabled network switches in the bounded delay model where each packet has a weight and a deadline. We consider the more realistic situation where the switch has a finite buffer size. A 9.82-competitive algorithm is known for the case of multiple buffers. Recently, for the single buffer case, a 3-competitive deterministic algorithm and a 2.618-competitive randomized algorithm were found. We give a simple deterministic 2-competitive algorithm for the single buffer case.
---
paper_title: Improved Online Algorithms for Multiplexing Weighted Packets in Bounded Buffers

paper_content:

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 ($3 + \sqrt{3} \approx 4.723$)-competitive deterministic algorithm, which is improved from the previously best-known result 9.82 (Azar and Levy. SWAT 2006).
---
paper_title: Competitive Scheduling of Packets with Hard Deadlines in a Finite Capacity Queue

paper_content:

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.
---
paper_title: An optimal online algorithm for packet scheduling with agreeable deadlines

paper_content:

An important issue in IP-based QoS networks is the effective management of packets at the router level. Specifically, if the arriving packets cannot all be stored in a buffer, or if the packets have deadlines by which they must be delivered, the router needs to identify the packets that should be dropped. In recent work, Kesselman et al. [6] propose a model, called buffer management with bounded delay, which can be thought of as an online scheduling problem on a single machine: packets arrive at a network switch and are stored in a buffer of size B. Each packet has a positive weight and a deadline, with the weight representing the value of transmitting the packet by its deadline. At each integer time step, exactly one packet can be transmitted, and the objective is to maximize the total weight of the transmitted packets. If B = ∞, this is the online version of the scheduling problem 1| p j = 1, r j , d j |Σ w j U j . (We assume that r j and d j are integers.)
---
paper_title: Considering suppressed packets improves buffer management in QoS switches

paper_content:

The following buffer management problem arises in network switches providing differentiated services: At the beginning of each time step, one packet can be sent, and afterwards an arbitrary number of new packets arrive. Packets that are not sent can be stored in a buffer. Each packet is attributed by a deadline, and a packet is automatically deleted from the buffer if it is still stored in the buffer by the end of its deadline. The differentiated service model is abstracted by attributing each packet with a value according to its service level. A buffer management strategy determines the packet to be sent in each time step. The goal of a buffer management strategy is to maximize the sum of the values of sent packets. We introduce the concept of suppressed packets and present a deterministic strategy that is based on this concept. We show that this strategy achieves a competitive ratio of 2√2--1 a 1.828, which is the best known competitive ratio in the deterministic case. Further, we present a memoryless version of this strategy that achieves a competitive ratio of a 1.893. This is the first memoryless strategy that achieves a competitive ratio less than 2, and the competitive ratio of this strategy is even better than the ratios of all previously known deterministic strategies. This demonstrates the potential of the concept of suppressed packets. In addition, we present a simple strategy that achieves the optimal competitive ratio of min{(1 + α)/α, 2α/(α+1)} ≤ √2, if only two packet values 1 and α > 1 are possible.
---
paper_title: Lower and Upper Bounds on FIFO Buffer Management in QoS Switches

paper_content:

We consider the management of FIFO buffers for network 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, and the goal is to maximize the sum of the 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 if the buffer size tends to infinity and an optimal competitive ratio of 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 which is the best known upper bound on the competitive ratio of this problem. In addition, we give a lower bound of 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.
---
paper_title: Loss-bounded analysis for differentiated services

paper_content:

We consider a network providing Differentiated Services (DiffServ) which allow network service providers to offer different levels of Quality of Service (QoS) to different traffic streams. We focus on loss and first show that only trivial bounds could be obtained by means of traditional competitive analysis. Then we introduce a new approach for estimating loss of an online policy called loss-bounded analysis. In loss-bounded analysis the loss of an online policy is bounded by the loss of an optimal offline policy plus a constant fraction of the benefit of the online policy. We relate the loss-bounded analysis to the throughput-competitive analysis. We derive tight upper and lower bounds for various settings of DiffServ parameters using the new loss-bounded model. We believe that loss-bounded analysis is an important technique that can complement traditional competitive analysis providing new insight and interesting results.
---
paper_title: Improved Competitive Guarantees for QoS Buffering

paper_content:

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.
---
paper_title: Competitive queue management for latency sensitive packets

paper_content:

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.
---

Title: A Survey of Buffer Management Policies for Packet Switches

Section 1: Introduction
Description 1: Provide an overview of packet switching and the importance of buffer management policies.

Section 2: FIFO Model
Description 2: Discuss models for managing a single output port with FIFO order including nonpreemptive and preemptive variants.

Section 3: Nonpreemptive Model
Description 3: Analyze the nonpreemptive model with specific scenarios like two-valued cases.

Section 4: Preemptive Model
Description 4: Introduce the preemptive FIFO model and analyze it with respect to value degradation and various competitive scenarios.

Section 5: Bounded-Delay Model
Description 5: Explain a model where each packet has a maximum delay by which it must be transmitted, including its variants and competitive policies.

Section 6: Lower Bounds
Description 6: Present the strongest known lower bounds for various models such as the general model, agreeable deadlines, and uniform cases.

Section 7: Upper Bounds
Description 7: Discuss several policies and their effectiveness in achieving upper bounds for the bounded-delay model and other scenarios.

Section 8: Multiple Input/Output Models
Description 8: Explore models for multi-port switches, multiple output queues with shared memory, and combined input-output queued switches.

Section 9: Resource Augmentation
Description 9: Review the impact of resource augmentation such as increased buffer sizes and transmission rates on the competitiveness of online policies.

Section 10: Closely Related Models
Description 10: Describe recent models related to buffer management including collecting weighted items from a queue and packet dependencies.

Section 11: Open Questions
Description 11: Highlight significant open problems in buffer management for future research.