  Motivated by the Quality-of-Service (QoS) buffer management problem, we
consider online scheduling of packets with hard deadlines in a finite capacity
queue. At any time, a queue can store at most $b \in \mathbb Z^+$ packets.
Packets arrive over time. Each packet is associated with a non-negative value
and an integer deadline. In each time step, only one packet is allowed to be
sent. Our objective is to maximize the total value gained by the packets sent
by their deadlines in an online manner. Due to the Internet traffic's chaotic
characteristics, no stochastic assumptions are made on the packet input
sequences. This model is called a {\em finite-queue model}.
  We use competitive analysis to measure an online algorithm's performance
versus an unrealizable optimal offline algorithm who constructs the worst
possible input based on the knowledge of the online algorithm. For the
finite-queue model, we first present a deterministic 3-competitive memoryless
online algorithm. Then, we give a randomized ($\phi^2 = ((1 + \sqrt{5}) / 2)^2
\approx 2.618$)-competitive memoryless online algorithm.
  The algorithmic framework and its theoretical analysis include several
interesting features. First, our algorithms use (possibly) modified
characteristics of packets; these characteristics may not be same as those
specified in the input sequence. Second, our analysis method is different from
the classical potential function approach.
