Management of Multi-Queue Switches in QoS Networks

The concept of Quality of Service (QoS) networks has gainedgrowing attention recently, as the traffic volume in the Internetconstantly increases, and QoS guarantees are essential to ensureproper operation of most communication-based applications. A QoSswitch serves m incoming queues by transmitting packets arrivingto these queues through one output port, one packet per time step.Each packet is marked with a value indicating its priority in thenetwork. Since the queues have bounded capacities and the rate ofarriving packets can be much higher than the transmission rate,packets can be lost due to insufficient queue space. The goal isto maximize the total value of transmitted packets. This problemencapsulates two dependent questions: buffer management, namelywhich packets to admit into the queues, and scheduling, i.e. whichqueue to use for transmission in each time step. We usecompetitive analysis to study online switch performance in QoS-based networks. Specifically, we provide a novel generic techniquethat decouples the buffer management and scheduling problems. Ourtechnique transforms any single-queue buffer management policy(preemptive or non-preemptive) to a scheduling and buffermanagement algorithm for our general m queues model, whosecompetitive ratio is at most twice the competitive ratio of thegiven buffer management policy. We use our technique to deriveconcrete algorithms for the general preemptive and non-preemptivecases, as well as for the interesting special cases of the 2-valuemodel and the unit-value model. We also provide a1.58-competitive randomized algorithm for the unit-value case.This case is interesting by itself since most current networks(e.g. IP networks) do not yet incorporate full QoS capabilities, andtreat all packets equally.