An optimal lower bound for buffer management in multi-queue switches
From MaRDI portal
Publication:476433
DOI10.1007/S00453-012-9677-8zbMATH Open1317.68056OpenAlexW3015166168MaRDI 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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)
- 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)
