A Better Memoryless Online Algorithm for FIFO Buffering Packets with Two Values
作者： Fei Li
DOI:
关键词:
摘要: We consider scheduling packets with values in a capacity-bounded buffer an online setting. In this model, there is limited capacity $B$. At any time, the cannot accommodate more than $B$ packets. Packets arrive over time. Each packet associated non-negative value. leave only because they are either sent or dropped. Those that have left will not be reconsidered for delivery more. each time step, at most one can sent. The order which should comply of their arrival objective to maximize total value manner. paper, we study variant FIFO buffering model packet's 1 $\alpha > 1$. present deterministic memoryless 1.304-competitive algorithm. This algorithm has same competitive ratio as presented (Lotker and Patt-Shamir. PODC 2002, Computer Networks 2003). However, our simpler does employ marking bits. idea used novel different from all previous approaches applied general its variants. do proactively preempt when new arrives. Instead, may 1-value contains sufficiently many $\alpha$-value
harvard.edu
arxiv.org参考文章(10)
Ran El-Yaniv, Allan Borodin, Online Computation and Competitive Analysis ,(1998)
Markus Schmidt, Packet buffering: randomization beats deterministic algorithms symposium on theoretical aspects of computer science. pp. 293- 304 ,(2005) , 10.1007/978-3-540-31856-9_24
Alexander Kesselman, Yishay Mansour, Loss-bounded analysis for differentiated services Journal of Algorithms. ,vol. 46, pp. 79- 95 ,(2003) , 10.1016/S0196-6774(02)00270-5
Yishay Mansour, Boaz Patt-Shamir, Ofer Lapid, Optimal smoothing schedules for real-time streams Distributed Computing. ,vol. 17, pp. 77- 89 ,(2004) , 10.1007/S00446-003-0101-0
Zvi Lotker, Boaz Patt-Shamir, Nearly optimal FIFO buffer management for DiffServ principles of distributed computing. pp. 134- 143 ,(2002) , 10.1145/571825.571851
Nir Andelman, Randomized qeue management for DiffServ acm symposium on parallel algorithms and architectures. pp. 1- 10 ,(2005) , 10.1145/1073970.1073972
Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, Maxim Sviridenko, Buffer Overflow Management in QoS Switches SIAM Journal on Computing. ,vol. 33, pp. 563- 583 ,(2004) , 10.1137/S0097539701399666
Matthias Englert, Matthias Westermann, Lower and Upper Bounds on FIFO Buffer Management in QoS Switches Algorithmica. ,vol. 53, pp. 523- 548 ,(2009) , 10.1007/S00453-008-9236-5
Alex Kesselman, Yishay Mansour, Rob van Stee, Improved Competitive Guarantees for QoS Buffering Algorithmica. ,vol. 43, pp. 63- 80 ,(2005) , 10.1007/S00453-005-1158-X
Nikhil Bansal, Lisa K Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, Maxim Sviridenko, Further Improvements in Competitive Guarantees for QoS Buffering Automata, Languages and Programming. pp. 196- 207 ,(2004) , 10.1007/978-3-540-27836-8_19