Competitive buffer management with packet dependencies

DOI10.1016/J.TCS.2013.04.007MaRDI QIDQ388119zbMATH OpenOpenAlexFDO

Authors Boaz Patt-Shamir, Gabriel Scalosub, Alex 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

online algorithmsbuffer managementcompetitive analysispacket dependencies

Mathematics Subject Classification ID

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

Recommendations

• Nearly optimal FIFO buffer management for two packet classes.
• Optimal buffer management for 2-frame throughput maximization
• Nearly optimal FIFO buffer management for DiffServ
• Better online buffer management
• Online buffer management for transmitting packets with processing cycles

Cites work

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

Cited in

(13)

• Buffer management for packets with processing times
• Optimal buffer management for 2-frame throughput maximization
• TCP is competitive with resource augmentation
• Competitive router scheduling with structured data
• scientific article; zbMATH DE number 2172789 (Why is no real title available?)
• Scheduling multipacket frames with frame deadlines
• Better bounds for online \(k\)-frame throughput maximization in network switches
• Online scheduling with interval conflicts
• Non-preemptive buffer management for latency sensitive packets
• Scheduling multipacket frames with frame deadlines
• STACS 2005
• Scheduling with deadlines and buffer management with processing requirements
• Overflow management with self-eliminations

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

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