text: 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_30: We study a basic buffer management problem that arises in network switches. Consider @math input ports, each of which is equipped with a buffer (queue) of limited capacity. Data packets arrive online and can be stored in the buffers if space permits; otherwise packet loss occurs. In each time step the switch can transmit one packet from one of the buffers to the output port. The goal is to maximize the number of transmitted packets. Simple arguments show that any work-conserving algorithm, which serves any nonempty buffer, is 2-competitive. Azar and Richter recently presented a randomized online algorithm and gave lower bounds for deterministic and randomized strategies. In practice, greedy algorithms are very important because they are fast, use little extra memory, and reduce packet loss by always serving a longest queue. In this paper we first settle the competitive performance of the entire family of greedy strategies. We prove that greedy algorithms are not better than 2-competitive no matter how ties are broken. Our lower bound proof uses a new recursive construction for building adversarial buffer configurations that may be of independent interest. We also give improved lower bounds for deterministic and randomized online algorithms. In this paper we present the first deterministic online algorithm that is better than 2-competitive. We develop a modified greedy algorithm, called semigreedy, and prove that it achieves a competitive ratio of @math . The new algorithm is simple, fast, and uses little extra memory. Only when the risk of packet loss is low does it not serve the longest queue. Additionally we study scenarios when an online algorithm is granted additional resources. We consider resource augmentation with respect to memory and speed; i.e., an online algorithm may be given larger buffers or higher transmission rates. We analyze greedy and other online strategies.
  @cite_18: The problem of maximizing the weighted throughput in various switching settings has been intensively studied recently through competitive analysis. To date, the most general model that has been investigated is the standard CIOQ (Combined Input and Output Queued) switch architecture with internal fabric speedup S ≥ 1. CIOQ switches, that comprise the backbone of packet routing networks, are N × N switches controlled by a switching policy that incorporates two components: Admission control and scheduling. An admission control strategy is essential to determine the packets stored in the FIFO queues in input and output ports, while the scheduling policy conducts the transfer of packets through the internal fabric, from input ports to output ports. The online problem of maximizing the total weighted throughput of CIOQ switches was recently investigated by Kesselman and Rosen [2003]. They presented two different online algorithms for the general problem that achieve non-constant competitive ratios (linear in either the speedup or the number of distinct values, or logarithmic in the value range). We introduce the first constant-competitive algorithm for the general case of the problem, with arbitrary speedup and packet values. Specifically, our algorithm is 8-competitive, and is also simple and easy to implement.
  @cite_26: We study a basic problem in Multi-Queue switches. A switch connects m input ports to a single output port. Each input port is equipped with an incoming FIFO queue with bounded capacity B. A switch serves its input queues by transmitting packets arriving at these queues, one packet per time unit. Since the arrival rate can be higher than the transmission rate and each queue has limited capacity, packet loss may occur as a result of insufficient queue space. The goal is to maximize the number of transmitted packets. This general scenario models most current networks (e.g., IP networks) which only support a “best effort” service in which all packet streams are treated equally. A 2-competitive algorithm for this problem was designed in [4] for arbitrary B. Recently, a ( 17 9 1.89 )-competitive algorithm was presented for B>1 in [2]. Our main result in this paper shows that for B which is not too small our algorithm can do better than 1.89, and approach a competitive ratio of ( e e-1 1.58 ).
  @cite_4: 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.
  @cite_28: 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.
  @cite_21: 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.
  @cite_3: 
  @cite_6: 
  @cite_27: 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.
  @cite_5: 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 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 performance guarantee is provided for all traffic patterns. Azar and Richter [8] proposed an algorithm β-PG(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 β-PGis at most @math and at least @math -competitive.
  @cite_25: 
  @cite_11: 
summary: Various models have been proposed and studied, including, among others, QoS-oriented models where packets have weights @cite_25 @cite_11 @cite_21 @cite_27 and models where packets have dependencies @cite_4 @cite_3 . A related field that has received much attention in recent years focuses on various switch architectures and aims at designing competitive algorithms for such multi-queue scenarios; see, e.g., @cite_30 @cite_18 @cite_26 @cite_5 @cite_6 . Some other works also provide experimental studies of these algorithms and further validate their performance @cite_28 .