Buffer management of multi-queue QoS switches with class segregation

DOI10.1016/J.TCS.2015.04.010MaRDI QIDQ2346374zbMATH OpenOpenAlexFDO

Authors Toshiya Itoh, Seiji Yoshimoto

Publication date 1 June 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.3172

zbMATH Keywords

buffer managementcompetitive ratioonline algorithmsquality of service (QoS)

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27)

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<\mathrm{...}<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=ma{x}_{1leqileqm-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.

Recommendations

• Buffer overflow management with class segregation
• Competitive buffer management for multi-queue switches in QoS networks using packet buffering algorithms
• Management of multi-queue switches in QoS networks
• Comparison-based buffer management in QoS switches
• Buffer Overflow Management in QoS Switches

Cites work

• Algorithms – ESA 2004
• An optimal lower bound for buffer management in multi-queue switches
• Buffer overflow management in QoS switches
• Buffer overflow management with class segregation
• Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• Management of multi-queue switches in QoS networks
• On the performance of greedy algorithms in packet buffering
• Optimal smoothing schedules for real-time streams (extended abstract)
• The zero-one principle for switching networks

Cited in

(4)

• scientific article; zbMATH DE number 2088521 (Why is no real title available?)
• Competitive buffer management for multi-queue switches in QoS networks using packet buffering algorithms
• Algorithms – ESA 2004
• Management of multi-queue switches in QoS networks

This page was built for publication: Buffer management of multi-queue QoS switches with class segregation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2346374)