مدیریت بافر FIFO تقریبا بهینه برای دو طبقه بسته

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.

Buffers can be found in almost all computer systems: they serve as a basic coupling component that enables communication without rigid synchronization. Packets enter with one traffic characteristic, and leave with another. The existence and importance of buffers is more pronounced in data communication networks, where buffers are found essentially in each connection point: a computer’s network adapter (NIC), a switch’s interface (port), etc. In most settings the buffers are required to adhere to FIFO ordering as part of the correctness specifications. In many cases, the traffic into and out of the buffer obeys certain known restrictions that allow the designer to choose a buffer that will accommodate all possible scenarios (e.g., leaky bucket constrained traffic [6]). In many other cases, however, incoming traffic does not have a deterministic upper bound, or, equivalently, the only upper bounds known require more resources than available. In these cases a buffer management policy is called for to handle overflow events. The simplest and most popular approach to overflow management is “tail drop”: new packets are dropped if there’s no room in the buffer. If all packets are equally important, this policy is good enough. The situation is more interesting when different packets have different values, as is the case when different levels of service are to be supported. Let us give two basic examples for different packet values. First, there is the obvious scenario where each delivered packet has a cash value: In the Internet, many pricing mechanisms have been proposed (see, for example, [5], [8] and [14] and references therein), and one of the basic approaches to pricing is a per-packet fee. In the case of two levels of service, we may assume that we have two packet prices: a “regular” packet of value 1, and a “valuable” packet of value α>1. Another scenario where a two-value model seems to make sense is in the context of constrained incoming streams: For example, in ATM some incoming streams commit to a limiting traffic envelope. Packets––called “cells” in this context––violating the constraint are marked (using the cell loss priority bit). Since it is preferable to deliver even violating packets if possible, we may assume that a packet complying with its traffic descriptor has some intrinsic value α>1, and other (violating) packets have value 1, where the parameter α>1 represents the “strictness” of the system. In this paper, we analyze a simple abstraction of a buffer, that can be roughly described as follows. We are given a buffer that can hold at most B packets. In each time step, an arbitrary set of packets arrives at the buffer, and at most one packet may leave the buffer. Each packet p has value View the MathML source. We concentrate on the special case where packets may have only two values: 1 and α>1. The buffer management algorithm decides which packets to drop from the buffer and which packets to send. At each step, any packet from among those currently stored in the buffer and from among the newly arriving packets may be dropped (this is the push out buffer model). FIFO order must be maintained over the sent packets, in the sense that if p arrived before q and both are sent, then p is sent before q. (Note that FIFO buffers ensure bounded delivery time for packets that are not dropped.) The goal of the algorithm is to maximize the total value of delivered packets. We use competitive analysis [3] and [17] to evaluate algorithm performance. Specifically, the competitive ratio of an algorithm alg is an upper bound, over all possible arrival sequences, on the ratio of the value sent by an optimal (off-line) algorithm to the value sent by alg. Let us summarize briefly some results directly relevant to our work. First, note that if packet values are in the range [1,α], then any work-conserving policy that does not drop packets while there’e room in the buffer (including the tail-drop policy) is α-competitive.1 This is because all these algorithms send the maximal possible number of packets. It is straightforward to see that in some cases, tail-drop actually sends only 1/α value of the value sent by the optimal algorithm. On the other hand, it is known that no deterministic on-line algorithm can have competitive ratio smaller than 1.28 [15] and [18]. The lower bound is proved using two packet values. The most natural buffer management policy is the greedy policy, that drops the cheapest packets when an overflow occurs. Mansour et al. [15] give a relatively simple proof that the greedy policy is 4-competitive. Kesselman et al. [9] give a much more subtle proof that shows that the competitive ratio of the greedy policy is in fact 2−2/(α+1), for any packet values in the range [1,α]. It is also shown in [9] that the “greedy head-drop” policy (the greedy algorithm which prefers dropping old packets in case of a tie) is the best greedy policy. For the model of two possible values {1,α}, Kesselman and Mansour [10] propose a more “proactive” algorithm with competitive ratio View the MathML source for α>4. Combining the results of the greedy algorithm with the latter, one gets an algorithm with worst-case competitive ratio about 1.888 for any α in the two-value case. Our results. In this work, we significantly reduce the competitive ratio of buffer management for the two packet values model. We do it with a new algorithm, whose competitive ratio is View the MathML source, and never more than 1.30 for any α. The algorithm is memoryless, i.e., its action depends only on the current state of the buffer, and no additional persistent state is required. More about related work. Many research papers deal with packet drop policies in communication networks––see, for example, the survey of [11] and references therein. Some drop mechanisms, such as RED [7], are designed to signal congestion to the sending end. The approach abstracted in our model, where packets have values and the goal is to maximize the total throughput value, is implicit in DiffServ [2] and [4] and ATM [19]. There has been work on analyzing various aspects of the model using classical queuing theory, and assuming Poisson arrivals [16]. The Poisson arrival model has been seriously undermined by the discovery of the heavy tail nature of data traffic [12] and the chaotic nature of TCP [20]. Another model studied in [1] assumes that one cannot discard a packet already in the buffer, and thus the algorithm may only control admission into the buffer. Aiello et al. [1] give tight bounds on the competitive factor of various algorithms for the two value model. In [15], the question of video smoothing is studied. Among the results in that paper, they prove an upper bound of 4 on the competitive ratio of the greedy algorithm and a lower bound of 1.25 on the ratio of any on-line algorithm (the lower bound was later improved to about 1.28 [13] and [18]). The work of [10] studies competitive ratio of the lost value rather than the throughput value we use here. Paper organization. The remainder of this paper is organized as follows. In Section 2 we define the model and the notation we use. In Section 3 we specify our on-line algorithm mf and a reference optimal algorithm. In Section 4 we analyze the competitive factor of mf. We conclude with a few comments in Section 5.

We have presented a buffer management algorithm for the DiffServ model, where only two packet values are possible. The obvious open question is whether the upper bound can be improved to meet the lower bound (we believe that the lower bound is the best possible). Another important open problem is finding an algorithm for the general model, where packet values may be any number in [1,α]. In fact, it is not clear even how to generalize our algorithm to more than two values. Lastly, we remark that from the implementation point of view, head-drop and tail-drop are extremely more efficient than push-out queues. We believe that our algorithm can be extended to the head-drop model.