ACM Transactions on Algorithms · 2007 · 42 citations · 11 references
ComputingComputer ScienceComputer SystemsAlgorithmsComputer NetworksOptimizationBuffer ManagementNetwork Performance AnalysisQueueing SystemsQueueing TheoryRoutingSwitching TechniquesBuffer OptimizationCompetitive RatioDeterministic Online AlgorithmsNetwork Buffer ManagementSwitch ArchitectureSwitch SchedulingSwitching Algorithm DesignSwitching Algorithms
We consider the following buffer management problem arising in QoS networks: Packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. Packets not forwarded before their deadlines are lost. The main result of the article is an online 64/33 ≈ 1.939-competitive algorithm, the first deterministic algorithm for this problem with competitive ratio below 2. For the 2-uniform case we give an algorithm with ratio ≈ 1.377 and a matching lower bound.
11
Buffer Overflow Management in QoS Switches
Alexander Kesselman, Zvi Lotker, Yishay Mansour et al. · SIAM Journal on Computing · 2004 · 169 citations
Competitive queueing policies for QoS switches
Nir Andelman, Yishay Mansour, An Zhu · 2003 · 114 citations