Speaker: Alex Kesselman

Title: Competitive Analysis of Buffer Management Policies for QoS
Switches.

Abstract: We consider buffer management policies for shared memory
packet switches supporting Quality of Service (QoS).  There are two
interesting dimensions in which the setting may differ. The first is
whether or not the policy is allowed to preempt packets that have been
already admitted to the buffer.  The second is the value of the
packets, do all packets have the same value (Best Effort) or do
different packets have different values (DiffServ). We study the
performance of a buffer management policy by means of competitive
analysis, where the goal is to maximize the total value of packets
transmitted.

For preemptive model with fixed value packets we show that the well
known Longest Queue Drop (LQD) policy is $2$-competitive and present a
lower bound of $4/3$.  For the case of variable value packets we
derive a partition policy whose competitive ratio is logarithmic on
the ratio of the maximal to minimal value.  For non-preemptive model
we introduce a general buffer management scheme and propose a new
Harmonic policy, based on this scheme.  We demonstrate that its
throughput competitive ratio is almost optimal for the case of fixed
value packets.