An optimal lower bound for buffer management in multi-queue switches
From MaRDI portal
Publication:476433
DOI10.1007/S00453-012-9677-8zbMATH Open1317.68056arXiv1007.1535OpenAlexW3015166168MaRDI QIDQ476433FDOQ476433
Authors: Marcin Bienkowski 
Publication date: 2 December 2014
Published in: Algorithmica (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1007.1535
Recommendations
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)
Cites Work
- Lower and upper bounds on FIFO buffer management in QoS switches
- Maximizing throughput in multi-queue switches
- Competitive queue policies for differentiated services
- Title not available (Why is that?)
- Buffer Overflow Management in QoS Switches
- Optimal smoothing schedules for real-time streams
- Online scheduling with partial job values: does timesharing or randomization help?
- Title not available (Why is that?)
- On the Performance of Greedy Algorithms in Packet Buffering
- Management of multi-queue switches in QoS networks
- Competitive management of non-preemptive queues with multiple values
- Improved competitive guarantees for QoS buffering
- Online competitive algorithms for maximizing weighted throughput of unit jobs
- An optimal online algorithm for packet scheduling with agreeable deadlines
- Better online buffer management
- Considering suppressed packets improves buffer management in QoS switches
- Loss-bounded analysis for differentiated services
- Nearly optimal FIFO buffer management for two packet classes.
- One to rule them all: a general randomized algorithm for buffer management with bounded delay
- Randomized algorithm for agreeable deadlines packet scheduling
- Analysis of queueing policies in QoS switches
- Collecting weighted items from a dynamic queue
- Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers
- STACS 2005
- Randomized competitive algorithms for online buffer management in the adaptive adversary model
- An experimental study of new and known online packet buffering algorithms
Cited In (14)
- Algorithms – ESA 2004
- Algorithms – ESA 2004
- Better bounds for online \(k\)-frame throughput maximization in network switches
- Tight Analysis of Priority Queuing for Egress Traffic
- Optimum Scheduling and Memory Management in Input Queued Switches With Finite Buffer Space
- Algorithms and Computation
- Maximizing throughput in multi-queue switches
- Euro-Par 2004 Parallel Processing
- Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers
- Online packet scheduling for CIOQ and buffered crossbar switches
- Better bounds for online \(k\)-frame throughput maximization in network switches
- An optimal lower bound for buffer management in multi-queue switches
- Buffer management for packets with processing times
- Competitive buffer management for multi-queue switches in QoS networks using packet buffering algorithms
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)
