[1] Wu Jun, Luo Junzhou,. Randomized scheduling algorithm for input-queued switches [J]. Journal of Southeast University (English Edition), 2005, 21 (1): 6-10. [doi:10.3969/j.issn.1003-7985.2005.01.002]

Copy

Randomized scheduling algorithm for input-queued switches()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

21

Issue:

2005 1

Page:

6-10

Research Field:

Computer Science and Engineering

Publishing date:

2005-03-30

Info

Title:

Randomized scheduling algorithm for input-queued switches

Author(s):

Wu Jun;  Luo Junzhou

Department of Computer Science and Engineering, Southeast University, Nanjing 210096, China

Keywords:

switches;  input-queued;  randomized algorithm

PACS:

TP301

DOI:

10.3969/j.issn.1003-7985.2005.01.002

Abstract:

The sampling problem for input-queued(IQ)randomized scheduling algorithms is analyzed.We observe that if the current scheduling decision is a maximum weighted matching(MWM), the MWM for the next slot mostly falls in those matchings whose weight is closed to the current MWM.Using this heuristic, a novel randomized algorithm for IQ scheduling, named genetic algorithm-like scheduling algorithm(GALSA), is proposed.Evolutionary strategy is used for choosing sampling points in GALSA.GALSA works with only O(N)samples which means that GALSA has lower complexity than the famous randomized scheduling algorithm, APSARA.Simulation results show that the delay performance of GALSA is quite competitive with respect to that of APSARA.

References:

[1] Karol M J, Hluchyj M, Morgan S.Input versus output queueing on a space-division packet switch [J].IEEE Transactions on Communications, 1987, 35(12):1347-1356.
[2] Mckeown N, Mekkittikul A, Anantharam V, et al.Achieving 100% throughput in an input-queued switch [J].IEEE Transactions on Communications, 1999, 47(8):1260-1267.
[3] Mekkittikul A, Mckeown N.A practical scheduling algorithm to achieve 100% throughput in input-queued switches[A].In:Guerin R, ed.Proceedings of the IEEE INFOCOM [C].San Francisco:IEEE Computer Society Press, 1998. 792-799.
[4] Tabatabaee V, Tassiulas L.MNCM a new class of efficient scheduling algorithms for input buffered switches with no speedup[A].In:Matta I, ed.Proceedings of the IEEE INFOCOM[C].San Francisco:IEEE Communications Society, 2003.1406-1413.
[5] McKeown N.The iSLIP scheduling algorithm for input-queued switches [J].IEEE Transactions on Networking, 1999, 7(2):188-201.
[6] Serpanos D N, Antoniadis P I.FIRM:a class of distributed scheduling algorithms for high-speed ATM switches with multiple input queues[A].In:Katzela I, ed.Proceedings of the IEEE INFOCOM[C].Tel Aviv:IEEE Communications Society, 2000.548-555.
[7] Li Y, Panwar S, Chao H J.The dual round robin matching switch with exhaustive service[A].In:Gunner C, ed.Proceedings of IEEE Workshop on High Performance Switching and Routing[C].Kobe, Japan:IEEE Communications Society, 2002. 58-63.
[8] Tassiulas L.Linear complexity algorithms for maximum throughput in radio networks and input queued switches [A].In:Guerin R, ed.Proceedings of the IEEE INFOCOM [C].San Francisco:IEEE Computer Society Press, 1998.533-539.
[9] Giaccone P, Shah D, Prabhakar B.An implementable parallel scheduler for input-queued switches[J].IEEE Micro, 2002, 22(1):19-25.
[10] Shah D, Giaccone P, Prabhakar B.An efficient randomized algorithm for input-queued switch scheduling [J].IEEE Micro, 2002, 22(1):10-18.
[11] Marsan M A, Bianco A, Giaccone P, et al.Packet scheduling in input-queued cell-based switches[A].In:Ammar M, ed.Proceedings of the IEEE INFOCOM[C].Anchorage:IEEE Communications Society, 2001.1085-1094.

Memo

Memo:

Biographies: Wu Jun(1970—), male, graduate;Luo Junzhou(corresponding author), male, doctor, professor, jluo@seu.edu.cn.

Common functions