Competitive Analysis of Buffer Management
Policies for QoS Switches
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.
Graphs with tiny vector chromatic numbers and huge
chromatic numbers.
Karger, Motwani and Sudan (JACM 1998) introduced the
notion of a vector
coloring of a graph. In particular they show that
every $k$-colorable
graph is also vector $k$-colorable, and that for
constant $k$, graphs
that are vector $k$-colorable can be colored by
roughly $\Delta^{1 - 2/k}$
colors. Here $\Delta$ is the maximum degree in the
graph. Their results
play a major role in the best approximation
algorithms for coloring and
for maximal independent set.
We show that for every positive integer $k$ there are
graphs that are
vector $k$-colorable but do not have independent sets
significantly larger
than $n/\Delta^{1 - 2/k}$ (and hence cannot be
colored with significantly
less that $\Delta^{1 - 2/k}$ colors). For $k = O(\log
n/\log\log n)$ we
show vector $k$-colorable graphs that do not have
independent sets of size
$(\log n)^c$, for some constant $c$. This shows that
the vector chromatic
number does not approximate the chromatic number
within factors better
than $n/{\mbox{polylog}} n$.
As part of our proof, we analyze ``property testing''
algorithms that
distinguish between graphs that have an independent
set of size $n/k$,
and graphs that are ``far'' from having such an
independent set. Our
bounds on the sample size improve previous bounds of
Goldreich, Goldwasser
and Ron (JACM 1998) for this problem.
Joint work with U. Feige and G. Schechtman.