Competitive buffer management for multi-queue switches in qos networks using packet buffering algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Competitive buffer management for multi-queue switches in qos networks using packet buffering algorithms

Full text

Pdf (571 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures table of contents

Calgary, AB, Canada

SESSION: Scheduling and resource management table of contents

Pages 328-336

Year of Publication: 2009

ISBN:978-1-60558-606-9

Authors

Koji Kobayashi	Kyoto University, Kyoto, Japan
Shuichi Miyazaki	Kyoto University, Kyoto, Japan
Yasuo Okabe	Kyoto University, Kyoto, Japan

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 23, Downloads (12 Months): 38, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1583991.1584070 What is a DOI?

ABSTRACT

The online buffer management problem formulates the problem of queuing policies of network switches supporting QoS (Quality of Service) guarantee. We focus on multi-queue switches in QoS networks proposed by Azar et al. They introduced so-called "the relaxed model". Also, they showed that if the competitive ratio of the single-queue model is at most c, and if the competitive ratio of the relaxed model is at most c2, then the competitive ratio of the multi-queue switch model is cc2. They proved that c2d2, and obtained upper bounds on the competitive ratios for several multi-queue switch models.

In this paper, we propose an online algorithm called DS (Dual Scheduling) for the competitive ratio of the relaxed model and obtain some better competitive ratios of the 2-value multi-queue switch model, where the value of packets is restricted to 1 and α(e1). DS uses as subroutine any online algorithms A for the non-preemptive unit-value switch model, which has also been extensively studied. We prove that if the competitive ratio of A is at most c, then the competitive ratio of DS is at most αc(2--c) + c²--2c+2Dα(2--c)+c--1, which is strictly better than 2.

The followings are a couple of examples of the improvement on the competitive ratios of the 2-value multi-queue switch models using our result: (i) We have improved the competitive ratio of deterministic algorithms for the non-preemptive 2-value multi-queue switch model from 4 to 3.177 for large enough B, where B is the number of packets each queue can simultaneously store. (ii) We have proved that the competitive ratio of randomized algorithms for the non-preemptive 2-value multi-queue switch model is at most 17D2--30≈3.023 for large enough B.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	William A. Aiello , Yishay Mansour , S. Rajagopolan , Adi Rosén, Competitive queue policies for differentiated services, Journal of Algorithms, v.55 n.2, p.113-141, May 2005 [doi>10.1016/j.jalgor.2004.04.004]
	2	Susanne Albers , Markus Schmidt, On the Performance of Greedy Algorithms in Packet Buffering, SIAM Journal on Computing, v.35 n.2, p.278-304, 2005 [doi>10.1137/S0097539704446268]
	3	Nir Andelman, Randomized qeue management for DiffServ, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073972]
	4	N. Andelman and Y. Mansour, "Competitive management of non-preemptive queues with multiple values," In Proc. of the 17th International Symposium on Distributed Computing, pp. 166--180, 2003.
	5	Nir Andelman , Yishay Mansour , An Zhu, Competitive queueing policies for QoS switches, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	6	Yossi Azar , Arik Litichevskey, Maximizing throughput in multi-queue switches, Algorithmica, v.45 n.1, p.69-90, April 2006 [doi>10.1007/s00453-005-1190-x]
	7	Y. Azar and Y. Richter, "Management of multi-queue switches in QoS networks," Algorithmica, Vol.43, No. 1--2, pp, 81--96, 2005,
	8	Yossi Azar , Yossi Richter, The zero-one principle for switching networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007369]
	9	Yossi Azar , Yossi Richter, An improved algorithm for CIOQ switches, ACM Transactions on Algorithms (TALG), v.2 n.2, p.282-295, April 2006 [doi>10.1145/1150334.1150342]
	10	Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
	11	Matthias Englert , Matthias Westermann, Lower and upper bounds on FIFO buffer management in QoS switches, Proceedings of the 14th conference on Annual European Symposium, p.352-363, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_33]
	12	Ellen L. Hahne , Alexander Kesselman , Yishay Mansour, Competitve buffer management for shared-memory switches, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.53-58, July 2001, Crete Island, Greece [doi>10.1145/378580.378589]
	13	Toshiya Itoh , Takanobu Nagumo, Improved Lower Bounds for Competitive Ratio of Multi-Queue Switches in QoS Networks*, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E88-A n.5, p.1155-1165, May 2005 [doi>10.1093/ietfec/e88-a.5.1155]
	14	Toshiya Itoh , Noriyuki Takahashi, Competitive Analysis of Multi-Queue Preemptive QoS Algorithms for General Priorities*Supported in part by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research on Priority Areas, 16092205, 2005., IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E89-A n.5, p.1186-1197, May 2006 [doi>10.1093/ietfec/e89-a.5.1186]
	15	Alexander Kesselman , Zvi Lotker , Yishay Mansour , Boaz Patt-Shamir , Baruch Schieber , Maxim Sviridenko, Buffer Overflow Management in QoS Switches, SIAM Journal on Computing, v.33 n.3, p.563-583, 2004 [doi>10.1137/S0097539701399666]
	16	Alexander Kesselman , Yishay Mansour, Harmonic buffer management policy for shared memory switches, Theoretical Computer Science, v.324 n.2-3, p.161-182, 20 September 2004 [doi>10.1016/j.tcs.2004.05.014]
	17	A. Kesselman, Y. Mansour and R. Stee, "Improved competitive guarantees for QoS buffering," In Proc. of the 11th Annual European Symposium on Algorithms, pp. 361--372, 2003.
	18	Alex Kesselman , Adi Rosén, Scheduling policies for CIOQ switches, Journal of Algorithms, v.60 n.1, p.60-83, July 2006 [doi>10.1016/j.jalgor.2004.09.003]
	19	Alex Kesselman , Kirill Kogan , Michael Segal, Packet mode and QoS algorithms for buffered crossbar switches with FIFO queuing, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400796]
	20	Alex Kesselman , Kirill Kogan , Michael Segal, Best Effort and Priority Queuing Policies for Buffered Crossbar Switches, Proceedings of the 15th international colloquium on Structural Information and Communication Complexity, June 17-20, 2008, Villars-sur-Ollon, Switzerland [doi>10.1007/978-3-540-69355-0_15]
	21	Alex Kesselman , Kirill Kogan , Michael Segal, Improved Competitive Performance Bounds for CIOQ Switches, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_48]
	22	Koji Kobayashi , Shuichi Miyazaki , Yasuo Okabe, A tight bound on online buffer management for two-port shared-memory switches, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248437]
	23	K. Kobayashi, S. Miyazaki and Y. Okabe, "Competitive buffer management for multi-queue switches in QoSnetworks using packet buffering algorithms," unpublished manuscript(http://www.net.ist.i.kyoto-u.ac.jp/kobaya/spaa09.pdf.), 2009.
	24	Zvi Lotker , Boaz Patt-Shamir, Nearly optimal FIFO buffer management for two packet classes, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.42 n.4, p.481-492, 15 July 2003 [doi>10.1016/S1389-1286(03)00197-X]
	25	M. Schmidt, "Packet buffering: Randomization beats deterministic algorithms," In Proc. of the 22nd International Symposium on Theoretical Aspects of Computer Science, pp. 293--304, 2005.
	26	Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
	27	M. Sviridenko, "A lower bound for on-line algorithms in the FIFO model," unpublished manuscript, 2001.