一种交错编码的多重门限调度算法
作者:
基金项目:

Supported by the National High-Tech Research and Development Plan of China under Grant Nos.2007AA01Z218, 2008AA01Z214 (国家高技术研究发展计划(863)); the National Basic Research Program of China under Grant No.2007CB307102 (国家重点基础研究发展计划(973))

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [19]
  • |
  • 相似文献
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    提出一种交错编码的多重门限调度算法(interleaving coded multi-threshold scheduling,简称ICMTS).该算法将前、后级队列门限标记交错编码作为权值表征输入调度过程前、后两级队列的整体调度需求,根据交错编码的权值对前级虚拟输出队列进行优化调度判决,并通过多重门限机制降低算法的硬件资源开销.采用流模型证明当加速因子为2时,ICMTS算法可获得100%的吞吐量,并给出ICMTS算法的工程简化设计方案,复杂度为O(logN).仿真仿真结果表明,采用ICMTS算法的工程简化方案即可获得比现有算法更优的调度性能.

    Abstract:

    An interleaving coded multi-threshold scheduling (ICMTS) algorithm is proposed in this paper. Since the ICMTS algorithm uses the interleaving coded thresholds of two stage queues as the scheduling weights, it can systematically evaluate the scheduling demands of both the input queues and the crosspoint queues. By segmenting the queue length as multiple thresholds, the hardware resource of this algorithm can be largely decreased. It is proved that a CICQ (combined input-crosspoint-queued) switch operating with the ICMTS algorithm can achieve 100% throughput with a speedup of two. To facilitate hardware implementation, a simplified maximal ICMTS scheme is also presented with a time complexity of O(logN). Simulation results show that even the simplified ICMTS scheme can obtain better performance than the existing algorithms.

    参考文献
    [1] Cisco Systems, Inc. Cisco 12000 series Internet routers. http://www.cisco.com
    [2] Partridge C, Carvey PP, Burgess E, Castineyra I, Clarke T, Graham L, Hathaway M, Herman P, King A, Kohalmi S, Ma T, Mcallen J, Mendez T, Milliken WC, Pettyjohn R, Rokosz J, Seeger J, Sollins M, Storch S, Tober B, Troxel GD, Waitzman D, Winterble S. A 50-Gb/s IP router. IEEE/ACM Trans. on Networking, 1998,6(3):237?248.
    [3] Kesidis G, McKeown N. Output-Buffer ATM packet switching for integrated-services communication networks. In: Proc. of the IEEE ICC’97. Montreal: IEEE, 1997. 1684?1688.
    [4] Anderson TE, Owicki SS, Saxe JB, Thacker CP. High-Speed switch scheduling for local-area networks. ACM Trans. on Computer Systems, 1993,11(4):319?352.
    [5] Chang CS, Chen WJ, Huang HY. On service guarantees for input buffered crossbar switches: A capacity decomposition approach by Birkhoff and von Neumann. In: Proc. of the IEEE IWQoS’99. London: IEEE, 1999. 79?86.
    [6] Chuang ST, Goel A, McKeown N, Prabhakar B. Matching output queueing with a combined input/output-queued switch. IEEE Journal of Selected Areas in Communications, 1999,17(6):1030?1039.
    [7] Stoica I, Zhang H. Exact emulation of an output queueing switch by a combined input output queueing switch. In: Proc. of the 6th IEEE/IFIP IWQoS’98. Napa: IEEE, 1998. 218?224.
    [8] Singhal V, Le R. High-Speed buffered crossbar switch design using Virtex-EM devices. 2000. http://www.xilinx.com/xapp/ xapp240.pdf
    [9] Yi P, Wang BQ, Guo YF. Providing QoS guarantees in buffered crossbars with space-division multiplexing expansion. In: Proc. of the IEEE GLOBECOM 2006. San Francisco: IEEE, 2006. 1?6.
    [10] Magill RB, Rohrs CE, Stevenson RL. Output-Queued switch emulation by fabrics with limited memory. IEEE Journal on Selected Areas in Communications, 2003,21(4):606?615.
    [11] Chuang ST, Iyer S, McKeown N. Practical algorithms for performance guarantees in buffered crossbars. In: Proc. of the IEEE INFOCOM 2005. Miami: IEEE, 2005. 981?991.
    [12] Yi P, Wang BQ, Guo YF, Li H. Providing QoS guarantees in a novel switch architecture. Acta Electronica Sinica, 2007,35(7): 28?35 (in Chinese with English abstract).
    [13] Yoshigoe K, Christensen K, Jacob A. The RR/RR CICQ switch: Hardware design for 10-Gbps link data rate. In: Proc. of the IEEE Int’l Performance, Computing, and Communications Conf. IEEE, 2003. 481?485.
    [14] Nabeshima M. Performance evaluation of a combined input- and crosspoint-queued switch. IEICE Trans. on Communications, 2000,E83-B(3):737?741.
    [15] Javidi T, Magill R, Hrabik T. A high-throughput scheduling algorithm for a buffered crossbar switch fabric. In: Proc. of the IEEE ICC 2001. IEEE, 2001. 1581?1587.
    [16] Zhang X, Bhuyan LN. An efficient algorithm for combined input-crosspoint-queued (CICQ) switches. In: Proc. of the IEEE Globecom 2004. IEEE, 2004. 1168?1173.
    [17] Mhamdi L, Hamdi M. MCBF: A high-performance scheduling algorithm for buffered crossbar switches. IEEE Communications Letters, 2003,7(9):451?453.
    [18] Dai JGJ, Prabhakar B. The throughput of data switches with and without speedup. In: Proc. of the IEEE INFOCOM 2000, Vol.3. IEEE, 2000. 556?564. 附中文参考文献:
    [12] 伊鹏,汪斌强,郭云飞,李挥.一种可提供QoS保障的新型交换结构.电子学报,2007,35(7):28?35.
    相似文献
    引证文献
引用本文

伊鹏,汪斌强,陈庶樵,李挥.一种交错编码的多重门限调度算法.软件学报,2009,20(8):2289-2297

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2007-10-20
  • 最后修改日期:2008-03-14
文章二维码
您是第19938597位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号