An optimal lower bound for buffer management in multi-queue switches

DOI10.1007/S00453-012-9677-8MaRDI QIDQ476433zbMATHOpenAlexFDO

Authors Marcin Bienkowski

Publication date 2 December 2014

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

online algorithmsbuffer managementcompetitive analysispacket buffering

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: In the online packet buffering problem (also known as the unweighted FIFO variant of buffer management), we focus on a single network packet switching device with several input ports and one output port. This device forwards unit-size, unit-value packets from input ports to the output port. Buffers attached to input ports may accumulate incoming packets for later transmission; if they cannot accommodate all incoming packets, their excess is lost. A packet buffering algorithm has to choose from which buffers to transmit packets in order to minimize the number of lost packets and thus maximize the throughput. We present a tight lower bound of e/(e-1) ~ 1.582 on the competitive ratio of the throughput maximization, which holds even for fractional or randomized algorithms. This improves the previously best known lower bound of 1.4659 and matches the performance of the algorithm Random Schedule. Our result contradicts the claimed performance of the algorithm Random Permutation; we point out a flaw in its original analysis.

Recommendations

• An optimal lower bound for buffer management in multi-queue switches
• STACS 2005
• On the performance of greedy algorithms in packet buffering
• On the Performance of Greedy Algorithms in Packet Buffering
• Nearly optimal FIFO buffer management for two packet classes.

Cites work

• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 2079410 (Why is no real title available?)
• An experimental study of new and known online packet buffering algorithms
• An optimal online algorithm for packet scheduling with agreeable deadlines
• Analysis of queueing policies in QoS switches
• Better online buffer management
• Buffer Overflow Management in QoS Switches
• Collecting weighted items from a dynamic queue
• Competitive management of non-preemptive queues with multiple values
• Competitive queue policies for differentiated services
• Considering suppressed packets improves buffer management in QoS switches
• Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers
• Improved competitive guarantees for QoS buffering
• Loss-bounded analysis for differentiated services
• Lower and upper bounds on FIFO buffer management in QoS switches
• Management of multi-queue switches in QoS networks
• Maximizing throughput in multi-queue switches
• Nearly optimal FIFO buffer management for two packet classes.
• On the Performance of Greedy Algorithms in Packet Buffering
• One to rule them all: a general randomized algorithm for buffer management with bounded delay
• Online competitive algorithms for maximizing weighted throughput of unit jobs
• Online scheduling with partial job values: does timesharing or randomization help?
• Optimal smoothing schedules for real-time streams
• Randomized algorithm for agreeable deadlines packet scheduling
• Randomized competitive algorithms for online buffer management in the adaptive adversary model
• STACS 2005

Cited in

(14)

• Buffer management for packets with processing times
• Better bounds for online \(k\)-frame throughput maximization in network switches
• Algorithms – ESA 2004
• An optimal lower bound for buffer management in multi-queue switches
• Algorithms and Computation
• Algorithms – ESA 2004
• Optimum Scheduling and Memory Management in Input Queued Switches With Finite Buffer Space
• Tight Analysis of Priority Queuing for Egress Traffic
• Better bounds for online \(k\)-frame throughput maximization in network switches
• Euro-Par 2004 Parallel Processing
• Maximizing throughput in multi-queue switches
• Online packet scheduling for CIOQ and buffered crossbar switches
• Competitive buffer management for multi-queue switches in QoS networks using packet buffering algorithms
• Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers

This page was built for publication: An optimal lower bound for buffer management in multi-queue switches

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