MNCM

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

MNCM: a critical node matching approach to scheduling for input buffered switches with no speedup

Full text

Pdf (479 KB)

Source

IEEE/ACM Transactions on Networking (TON) archive
Volume 17 , Issue 1 (February 2009) table of contents

Pages 294-304

Year of Publication: 2009

ISSN:1063-6692

Authors

Vahid Tabatabaee	Institute for Systems Research, University of Maryland, College Park, MD
Leandros Tassiulas	Computer Engineering and Telecommunication Department, University of Thessaly, Volos, Greece

Publisher

IEEE Press Piscataway, NJ, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 56, 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:	10.1109/TNET.2008.925091

ABSTRACT

In this paper, we use fluid model techniques to es-tablish new results for the throughput of input-buffered switches. Dai and Prabhakar have shown that any maximal size matching algorithm with speedup of 2 achieves 100% throughput. We introduce the maximum node containing matching (MNCM), which is a new class of matching algorithms that achieve 100% throughput with no speedup. The only assumption on the arrival processes is they satisfy the strong law of large numbers (SLLN). The MNCM policies only need to include ports whose weight (backlog) are above a threshold in the matching rather than finding a matching with maximum total weight. This simplified requirement enables us to introduce a new matching algorithm, maximum first matching (MFM), with O(N^2.5) complexity. We show that MFM is a low-complexity algorithm with good delay performance. We also provide a deterministic upper bound for the buffering requirement of a switch with an MNCM scheduler, when the ports incoming traffic are admissible and (σ, ρ) regulated.

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	Thomas E. Anderson , Susan S. Owicki , James B. Saxe , Charles P. Thacker, High-speed switch scheduling for local-area networks, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.319-352, Nov. 1993 [doi>10.1145/161541.161736]
	2	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	3	J. G. Dai, "Stability of fluid and stochastic processing networks," Mis-cellanea Publication, Denmark, 1999 [Online]. Available: http:/www. maphysto.dk/
	4	J. G. Dai and B. Prabhakar, "The throughput of data switches with and without speedup," in Proc. IEEE INFOCOM, Tel Aviv, Israel, Mar. 2000, pp. 556-564.
	5	Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
	6	P. Giaccone, B. Prabhakar, and D. Shah, "Towards simple, high-per-formance schedulers for high-aggregate bandwidth switches," in Proc. IEEE INFOCOM, New York, Jun. 2002, pp. 1160-1169.
	7	J. E. Hopcroft and R. M. Karp, "An n^5/2 algorithm for maximum matching in bipartite graphs," SIAM J. Computing, vol. 2, no. 4, pp. 225-231, 1973.
	8	M. J. Karol, M. G. Hluchyj, and S. P. Morgan, "Input versus output queueing on a space-division packet switch," IEEE Trans. Commun., vol. 35, no. 10, pp. 1347-1356, Oct. 1987.
	9	N. McKeown, V. Anantharam, and J. Warland, "Achieving 100% throughput in an input-queued switch," in Proc. IEEE INFOCOM, San Francisco, CA, Mar. 1996, pp. 296-302.
	10	A. Mekkittikul and N. McKeown, "A practical scheduling algorithm to achieve 100% throughput in input-queued switches," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 1998, pp. 792-799.
	11	A. Mekkittikul and N. McKeown, "Scheduling VOQ switches under non-uniform traffic," Stanford Univ., Stanford, CA, CSL Technical Re-port, CSL-TR-97-747, 1997.
	12	Nick McKeown, The iSLIP scheduling algorithm for input-queued switches, IEEE/ACM Transactions on Networking (TON), v.7 n.2, p.188-201, April 1999 [doi>10.1109/90.769767]
	13	M. Rosenblum, M. X. Goemans, and V. Tarokh, "Universal bounds on buffer size for packetizing fluid policies in input queued, crossbar switches," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004, pp. 1127-1135.
	14	K. Ross and N. Bambos, "Local search scheduling algorithms for max-imal throughput in packet switches," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004, pp. 1159-1170.
	15	G. L. Frazier and Y. Tamir, "The design and implementation of a multi-queue buffer for VLSI communication switches," in Proc. Int. Conf. Comput. Design, Cambridge, MA, 1989, pp. 466-471.
	16	Vahid Tabatabaee , Leonidas Georgiadis , Leandros Tassiulas, QoS provisioning and tracking fluid policies in input queueing switches, IEEE/ACM Transactions on Networking (TON), v.9 n.5, p.605-617, October 2001 [doi>10.1109/90.958329]
	17	V. Tabatabaee and L. Tassiulas, "MNCM: A new class of scheduling algorithms for input-buffered switches with no speedup," in Proc. IEEE INFOCOM, San Francisco, CA, Mar. 2003, pp. 1406-1413.
	18	V. Tabatabaee and L. Tassiulas, "Max-min fair self-randomized sched-uler for input-buffered switches," in Proc. IEEE Workshop High Per-formance Switching Routing, Apr. 2004, pp. 299-303.
	19	L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks," IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936-1948, Dec. 1992.
	20	L. Tassiulas, "Linear complexity algorithms for maximum throughput in radio networks and input queued switches," in Proc. IEEE IN-FOCOM, San Francisco, CA, Apr. 1998, pp. 533-539.