The online buffer management problem formulates the problem of queuing policies of network switches supporting QoS (Quality of Service) guarantee. In this paper, we consider one of the most standard models, called multi-queue switches model. In this model, Albers et al. gave a lower bound , and Azar et al. gave an upper bound on the competitive ratio when m, the number of input ports, is large. They are tight, but there still remains a gap for small m. In this paper, we consider the case where m=2, namely, a switch is equipped with two ports, which is called a bicordal buffer model. We propose an online algorithm called Segmental Greedy Algorithm (SG) and show that its competitive ratio is at most ( 1.231), improving the previous upper bound by ( 1.286). This matches the lower bound given by Schmidt.

The recent burst growth of the Internet use overloads networking systems and degrades the quality of communications, e.g., bandwidth loss, packet drops, delay of responses, etc. To overcome such degradation of communication quality, the notion of Quality of Service (QoS) has received attention in practice. In general, QoS switches have several queues and each queue has several slots to store arriving packets. Since network traffic changes frequently, QoS switches need to control arriving packets to maximize the total priorities of transmitted packets, where the priorities are given by nonnegative values and correspond to the quality of service required to each packet. In this paper, we first derive the upper bounds for the competitive ratio of multi-queue preemptive QoS problem with priority between 1/α and 1, i.e., for any α ≥ 1, the algorithm TLH is (3-1/α)-competitive. This is a generalization of known results--for the case that packets have only priority 1 (α =1), the algorithm GREEDY (or TLH) is 2-competitive; for the case that packets have priorities between 0 and 1 (α = ∞), the algorithm TLH is 3-competitive. Then we consider the lower bounds for the competitive ratio of multi-queue preemptive QoS problem with priority between 0 and 1, and show that the competitive ratio of any multi-queue preemptive QoS algorithm is at least 1.514.

The recent burst growth of the Internet use overloads networking systems and degrades the quality of communications, e.g., bandwidth loss, packet drops, delay of responses, etc. To overcome such degradation of the communication quality, the notion of Quality of Service (QoS) has received attention in practice. In general, QoS switches have several queues and each queue has several slots to store arriving packets. Since network traffic changes frequently, QoS switches need to control arriving packets to maximize the total priorities of transmitted packets, where the priorities are given by nonnegative values and correspond to the quality of service required for each packet. In this paper, we derive lower bounds for the competitive ratio of deterministic multi-queue nonpreemptive QoS problem of priorities 1 and α 1: 1 + /α ln if α α*; 1/(1 - e-τ0) if 1 α < α*, where α* 1.657 and τ0 is a root of the equality that e-τ(1/α + τ)=1 - e-τ. As an immediate result, this shows a lower bound 1.466 for the competitive ratio of deterministic multi-queue nonpreemptive QoS problem of single priority, which slightly improves the best known lower bound 1.366.