Open Access Open Access  Restricted Access Subscription or Fee Access

Critical Node Matching Algorithm for Scheduling Switches with Input Queues

R. Ramathilagam, Dr. Kannan Balasubramanian

Abstract


Packet switches are used in the Internet to forward information between a sender and receiver and are the critical bottleneck in the Internet. Without faster packet switch designs, the Internet cannot continue to scale-up to higher data rates. Packet switches must be able to achieve high throughput and low delay. In addition, they must be stable for all traffic loads, must efficiently support variable length packets, and must be scalable to higher link data rates and greater numbers of ports. Some unbalanced traffic loads result in instability for input queued (IQ) switches. Crossbars are main components of communication switches used to construct interconnection networks. Scheduling algorithms control contention in switch architecture. Several scheduling algorithms were proposed for input-queued crossbar switch architectures. This paper suggests a Critical Node Matching algorithm based on Maximum Node Containing matching (MNCM). This algorithm is the lowest complexity deterministic algorithm with good delay performance that delivers 100% throughput.

Keywords


Crossbars, Input-Queued Switches, Scheduling.

Full Text:

PDF

References


V. Tabatabaee and L. Tassiulas, “MNCM: A new class of scheduling algorithms for input-buffered switches with no speedup,” IEEE/ACM Trans. Networking, Vol.17, No.1, Feb.2009, pp. 294–304.

Saad Mneimneh and Kai-Yeung Siu,” On Achieving throughput in an Input-Queued Switch”, IEEE/ACMtTrans.Networking, vol.11, no.5, pp. 858- 867, Oct.2003

Mckeown.N, Mekkittikul.A, Anantharam.V, Walrand.J, “Achieving 100%throughput in an input-queued switch,” IEEE Trans.Commun., vol.47, no.8, Aug. 1999, pp. 1260-1267.

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.

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.

D.Banovic, I.Radusinovic, “VOQ Simulator – Software Tool for Performance Analysis of VOQ Switches”, accepted for IEEE AICT 2006, February 2006.

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.

Cormen, T.; Leiserson C.E.; Rivest R.L. “Introduction to algorithms,” The MIT Press, Cambridge, Massachusetts, March 1990.

N. McKeown, “Scheduling algorithms for input-queued cell switches”, Ph.D. Thesis, UC Berkeley, May 1995. http://klamath.stanford.edu/tools

J. E. Hopcroft and R. M. Karp, “An n5/2 algorithm for maximum matching in bipartite graphs,” SIAM J. Computing, vol. 2, no. 4, pp.sss 225–231, 1973.

A. Mekkittikul and N. McKeown, “Scheduling VOQ switches under non-uniform traffic,” Stanford Univ., Stanford, CA, CSL Technical Report, CSL-TR-97-747, 1997.

N. McKeown, “iSLIP: A scheduling algorithm for input-queued switches,” IEEE/ACM Trans. Networking, vol. 7, no. 2, pp. 188–201, Apr. 1999.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.