Management of Multi-Queue Switches in QoS Networks |
| |
Authors: | Yossi Azar Yossi Richter |
| |
Affiliation: | (1) School of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel |
| |
Abstract: | The concept of Quality of Service (QoS) networks has gained
growing attention recently, as the traffic volume in the Internet
constantly increases, and QoS guarantees are essential to ensure
proper operation of most communication-based applications. A QoS
switch serves m incoming queues by transmitting packets arriving
to these queues through one output port, one packet per time step.
Each packet is marked with a value indicating its priority in the
network. Since the queues have bounded capacities and the rate of
arriving packets can be much higher than the transmission rate,
packets can be lost due to insufficient queue space. The goal is
to maximize the total value of transmitted packets. This problem
encapsulates two dependent questions: buffer management, namely
which packets to admit into the queues, and scheduling, i.e. which
queue to use for transmission in each time step. We use
competitive analysis to study online switch performance in QoS-based networks. Specifically, we provide a novel generic technique
that decouples the buffer management and scheduling problems. Our
technique transforms any single-queue buffer management policy
(preemptive or non-preemptive) to a scheduling and buffer
management algorithm for our general m queues model, whose
competitive ratio is at most twice the competitive ratio of the
given buffer management policy. We use our technique to derive
concrete algorithms for the general preemptive and non-preemptive
cases, as well as for the interesting special cases of the 2-value
model and the unit-value model. We also provide a
1.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, and
treat all packets equally. |
| |
Keywords: | On-line algorithms Competitive ratio Competitiveness Multi-queue switch Packet switching Buffer management Quality of Service |
本文献已被 SpringerLink 等数据库收录! |
|