Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers

DOI10.1007/978-3-540-78773-0_22zbMath1136.68349OpenAlexW1544516749MaRDI QIDQ5458533

Marcin Bienkowski, Aleksander Mądry

Publication date: 15 April 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78773-0_22

zbMATH Keywords

online algorithmsnetwork problemspacket buffering

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Randomized algorithms (68W20)

Related Items (5)

Tight Analysis of Priority Queuing for Egress Traffic ⋮ An optimal lower bound for buffer management in multi-queue switches ⋮ Competitive buffer management for multi-queue switches in QoS networks using packet buffering algorithms ⋮ Online packet scheduling for CIOQ and buffered crossbar switches ⋮ Buffer management of multi-queue QoS switches with class segregation

Cites Work

• Unnamed Item
• Improved competitive guarantees for QoS buffering
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• On the performance of greedy algorithms in packet buffering
• On the k -server conjecture
• Lower and Upper Bounds on FIFO Buffer Management in QoS Switches
• STACS 2005
• Management of multi-queue switches in QoS networks

This page was built for publication: Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers