|Table of Contents|

[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
吴俊 罗军舟
东南大学计算机科学与工程系, 南京 210096
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.
对输入队列随机调度算法的取样问题进行了分析, 指出由于输入队列的记忆特性, 当前时隙的调度决策若具有最大权值, 那么选取与这个最大权值相近的匹配作为下个时隙调度决策时的样点将以较大概率找到最大权值匹配.基于此本文设计了一种新的随机调度算法GALSA, GALSA利用演化策略来跟踪与每个时隙决策具有相近权值的匹配点.GALSA算法所需样点是O(N), 因此其复杂性大大低于现有随机算法APSARA.且仿真结果表明GALSA的延迟性能与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.
Last Update: 2005-03-20