[1]ZHANG Chong-yang,SHEN Jin-yuan,LIU Run-jie,et al.A study on scheduling algorithms for high-speed switching networks based on input-queuing[J].CAAI Transactions on Intelligent Systems,2008,3(3):265-269.
Copy
A study on scheduling algorithms for high-speed switching networks based on input-queuing
CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume:
3
Number of periods:
2008 3
Page number:
265-269
Column:
学术论文—智能系统
Public date:
2008-06-25
- Title:
- A study on scheduling algorithms for high-speed switching networks based on input-queuing
- CLC:
- TP18
- DOI:
- -
- Abstract:
- Most high2speed switching networks adop t a switching fabric with fixed2length cells, and their perform2 ance depends heavily upon queuing strategies and the cell scheduling algorithm. Onlywhen the input2queuing strat2 egy is combined with a p roper switching algorithm can throughput and time delay for the switching fabric be op ti2 mized. This paper mainly discusses virtual output queuing (VOQ) 2based algorithms, among them the maximum numbermatching algorithm, the maximum weightmatching algorithm, the stable combination matching algorithm, and the Hopfield neural network (HNN) scheduling algorithm. The mechanisms, performance and imp lementation2 al comp lexity of these algorithms are compared and analyzed. The working modes of distributed and centralized scheduling algorithms are analyzed. Finally, from the findings in our research, it is concluded that the HNN algo2 rithm can realize other algorithms by defining a p riority functi
- References:
-
[1] McKeown N. A fast switched backplane for a gigabit switched router .Business Communications Review. 1997,2712, 27(12) :1-30 .
[2] MCKeown N,Annantharam V,Walrand J,et al. Achieving 100%throughput in an input-queued switch[J] .IEEE Trans.Commun, 1999,47, 47 (8) :1260-1267 .
[3] Gale D,Shapley L S. College admission and the stabili-ty of marriage[J] .American Mathematical Monthly, 1962,69, 69 (5) :19 .
[4] S Chuang, A Goel, N McKeown, et al. Matching output queuing with a combined input/output-queued switch .IEEE J Sel Areas in Communications. 1999,176, 17(6) :1030-1039 .
[5] C. Kam and Kai-Yeung Siu. Linear complexity algorithms for Qos support in input-queued switches with no speedup .IEEE Journal on selected areas in communications. 1999,176, 17(6) :1040-1056 .
[6] SU Xiao-xing,CHSNG Sheng-jiang,MA Tian-bing,et al. Aneural network model for traffic prediction in ATM net-work .Journal of Optoelectronics.laser(光电子.激光). 2003,148, 14(8) :842-845 .
[7] Marrakchi A,Troudet T. A neural net arbitrator for large crossbar packet-switches .IEEE Transactions on Circuits and Systems, 1989,36, 36 (7) :1039～1041 .
[8] ANDERSON T,OWICKI S,SAXES J,THACKER C. High speed switches scheduling for local area network[J] .ACM Transactions on Computer Systems, 1993,11, 11 (4) :319-352 .
[9] MEKKITTIKUI A,MCKEOWN N. A practical scheduling algorithm to achieve100%throughout in input-queued swit-ches[C] .IEEE INFOCOM‘98. San Francisco,CA. 1998, :23-28 .
[10] MCKEOWN N. The iSLIP scheduling algorithm for input-queued switches[J] .IEEE/ACM Transactions on Networ-king, 1999,7, 7 (2) :188-201 .
[11] MCKEOWN N. Scheduling algorithms for input-queued cell switch[D] .Berkeley: University of California at Berkeley, 1995 .
[12] PRABHAKAR P,MCKEOWN N. On the speed-up re-quired for combined input and output queued switching[R] .Stanford CSL-TR-97-738. 1997, .
[13] KRISHNA P,PATEL N,CHARNY A,SIMCOE R. On the speed-up required for work-conserving crossbar swit-ches[J] .IEEE Journal on Selected Areas in Communica-tions, 1999,17, 17 (6) :1057-1066 .
[14] Cisco Inc. Cisco12000series-Internet Router.Product O-verview[EB/OL] .http://www.Cisco.com. [2001-10-10], .
[15] KAROL M,HLUCHYJ M,MORGAN S. Input versus out-put queuing on a space-division packet switch[J] .IEEE Trans on Communications, ,12, 12 (35) :1347-1356 .
[16] MCKEOWN N,IZZARD M,MEKKITTIKUL A,et al. The tiny-tera:a packet switches core[J] .IEEE Micro Maga-zine, 1997,17, 17 (1) :26-33 .
[17] HOPCROFTJ E,KARP R M. An O(n5/2)algorithm for maximum matching in bipartite graphs[J] .Society for In-dustrial and Applied Mathematics Comput, 1973, (1) :225-231 .
[18] TARJAN R E. Data structures and network algorithms[C] .Conference on society for Industrial and Applied Mathematics. Pennsylvania. 1983, :105-109 .
[19] STOICA I,ZHANG H. Exact emulation of an output queu-ing switch by a combinedinput andoutput queuing switch[C] .Proceedings of the IEEE IWQoS. Napa: IEEE Communications Society, 1998, :218-224 .
[20] ALI M NGUYENH. Neural network implementation of an input accessscheme in a high speed packet switch[C] .Dallas,USA: IEEE GLOBECOM, 1989, :1192-1196
. [21] 张便利,常胜江,李江卫,熊涛,郜洪云,申金媛,张延炘. 实现虚拟输出队列调度的神经网络方法[J]光电子.激光, 2005,(11) .
- Similar References:
Memo
-
Last Update:
2009-05-14