Competitive buffer management with packet dependencies

DOI10.1016/j.tcs.2013.04.007zbMath1293.68309OpenAlexW1964235381MaRDI QIDQ388119

Boaz Patt-Shamir, Gabriel Scalosub, Alexander Kesselman

Publication date: 19 December 2013

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.04.007

zbMATH Keywords

competitive analysisonline algorithmsbuffer managementpacket dependencies

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Internet topics (68M11) Online algorithms; streaming algorithms (68W27)

Related Items (9)

Buffer Management for Packets with Processing Times ⋮ Scheduling Multipacket Frames with Frame Deadlines ⋮ Better bounds for online \(k\)-frame throughput maximization in network switches ⋮ Online scheduling with interval conflicts ⋮ Scheduling with deadlines and buffer management with processing requirements ⋮ Scheduling multipacket frames with frame deadlines ⋮ Competitive router scheduling with structured data ⋮ Overflow management with self-eliminations ⋮ Optimal Buffer Management for 2-Frame Throughput Maximization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower and upper bounds on FIFO buffer management in QoS switches
• The network as a storage device: dynamic routing with bounded buffers
• Online competitive algorithms for maximizing weighted throughput of unit jobs
• On the complexity of approximating \(k\)-set packing
• Adversarial queuing theory
• Competitive queue policies for differentiated services
• Priority encoding transmission
• Rate vs. buffer size--greedy information gathering on the line
• The zero-one principle for switching networks
• Buffer Overflow Management in QoS Switches
• Optimal smoothing schedules for real-time streams (extended abstract)
• Automata, Languages and Programming
• Algorithms and Computation

This page was built for publication: Competitive buffer management with packet dependencies