[1]张重洋,申金媛,刘润杰,等.基于输入排队的高速交换调度算法研究[J].智能系统学报,2008,3(3):265-269.
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.
点击复制
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.
基于输入排队的高速交换调度算法研究
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
3
期数:
2008年第3期
页码:
265-269
栏目:
学术论文—智能系统
出版日期:
2008-06-25
- Title:
- A study on scheduling algorithms for high-speed switching networks based on input-queuing
- 文章编号:
- 1673-4785（2008）03-0265-05
- 分类号:
- TP18
- 文献标志码:
- A
- 摘要:
- 高速交换网络一般采用基于定长信元的交换结构,其性能决定于排队策略和信元调度算法.输入排队策略只有和一个有效的调度算法相结合,才能保证交换结构具有良好的吞吐率和时延等性能.主要阐述了基于VOQ的最大数量匹配算法,最大权重匹配算法,稳定结合算法,神经网络算法等输入排队调度算法,分别从技术特点,性能指标和实现复杂度等多个方面进行比较和分析.分析了分布式和集中式两大类调度算法的工作方式,并根据各类算法的特点提出,神经网络算法可以通过定义其优先级函数实现其余各类算法.
- 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) .
备注/Memo
收稿日期：2007-11-15
基金项目：
河南省杰出青年基金资助项目(512000400);;
教育部留学回国人员科研启动基金资助项目
作者简介：
张重洋 ，男，1984年生，硕士研究生，主要研究方向为人工神经网络与通信信息系统
申金媛，女，1966年生，教授，博士，主要研究方向为人工神经网络 ，光电通信集信息处理，模式识别，已在国内外核心学术期刊上发表论文70余篇，其中被SCI和EI收录引用达60多篇次
通讯作者：申金媛。E-mail:jyshen@zzu.edu.cn
更新日期/Last Update:
2009-05-14