Buffer Management of Multi-Queue QoS Switches with Class Segregation

Toshiya Itoh; Seiji Yoshimoto

doi:10.1016/j.tcs.2015.04.010

paper

Buffer Management of Multi-Queue QoS Switches with Class Segregation

arXiv:1304.3172 · doi:10.1016/j.tcs.2015.04.010

Abstract

In this paper, we focus on buffer management of multi-queue QoS switches in which packets of different values are segregated in different queues. Our model consists of $m$ queues and $m$ packet values $0 < v_{1} < v_{2} < ... < v_{m}$ . Recently, Al-Bawani and Souza [IPL 113(4), pp.145-150, 2013] presented an online algorithm GREEDY for buffer management of multi-queue QoS switches with class segregation and showed thatif $m$ queues have the same size, then the competitive ratio of GREEDY is $1 + r$ , where $r = max_{1 \leq i \leq m - 1} v_{i} / v_{i + 1}$ . In this paper, we precisely analyze the behavior of GREEDY and show that it is $(1 + r)$ -competitive for the case that $m$ queues do not necessarily have the same size.

12 pages, 2 tables, 2 figures. arXiv admin note: substantial text overlap with arXiv:1109.6060