期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

输入排队Crossbar架构下的矩阵模型及MM-LQF调度策略 被引量：1

Matrix Model for Input-queued Crossbar Fabric and MM-LQF Scheduling Scheme
下载PDF
导出
摘要 输入排队Crossbar交换是高性能交换设备最为常用而关键的技术之一.本文建立了IQ-Crossbar架构下的矩阵模型,给出了IQ-Crossbar的状态矩阵、队长矩阵、到达矩阵和匹配矩阵的数学定义,并通过分析IQ-Crossbar的信元排队机理,提出和证明了队长矩阵迭代定理和状态矩阵迭代定理.该矩阵模型为分析IQ-Crossbar架构下的调度算法提供了理论依据.基于所建立的矩阵模型,在分析现有LQF调度算法优缺点的基础上,本文提出了一种新的调度策略MM-LQF,该策略的运算效率是LQF的3.72倍,支持的端口门限速率是LQF的2.35倍,在贝努利均匀流量重载条件下平均时延是LQF的1/2;在贝努利Diagonal流量条件下吞吐率为100%. The input-queued Crossbar Switching is one of the most popular and crucial technologies of the high-performance switching systems. The matrix model for IQ-Crossbar fabric is given in this paper, which has provided and well-defined the precise concepts of IQ-Crossbar fabric, such as the state matrix, the queueing length matrix, the arriving matrix, and the matching matliX. Based on analyzing the mechanism of the cell＇s queueing in the IQ-Crossbar, two matrix theorems of queueing length iteration as well as the state iteration are discussed and proved, The matrix model given in this paper provides the theoretical reference to IQ-Crossbar scheduling algorithms. Based on the matrix model set up in this paper and the analysis of the advantages and disadvantages of LQF algorithm, a new scheduling scheme of MM-LQF is provided, which has 3.72 times of operational efficiency,2.35 times of port gate rates,0.5 times of cell delay under heavy Bemoulli uniform load, 100% throughput under Bemoulli diagonal load of the LQF algorithm.
作者 马祥杰 毛军鹏 兰巨龙 张百生
机构地区 解放军信息工程大学信息工程学院 国家数字交换系统工程技术研究中心
出处 《电子学报》 EI CAS CSCD 北大核心 2008年第1期9-16,共8页 Acta Electronica Sinica
基金 国家863信息技术领域重大专项项目(No.2005AA121210) 国家973重点基础研究发展计划(No.2007CB307102)
关键词 输入排队交叉开关 矩阵模型 队长矩阵 调度策略 最长队列优先 input queued crossbar matrix model queueing length matrix scheduling scheme longest queue first
分类号 TN919.21 [电子电信—通信与信息系统]
  • 相关文献

参考文献26

  • 1M A Bonuccelli, A Urpi. A multicast FCFS output queued switch without speedup[A]. In Second IFIP conference in Networking[C]. Pisa, Italy, 2002. 1057 - 1068.
  • 2Amit Prakash, Sadia Sharif, Adnan Aziz. An O (log2 N) parallel algorithm for output queuing[A]. In Proceedings IEEE INFOCOM[C] .New York,USA,2002. 127 - 136.
  • 3N McKeown. Scheduling Algorithms for Input-Queued Cell Switches[D]. PhD Thesis, University of California, Berkeley, California, USA, 1995.
  • 4N McKeown, A Melddttikui, V Ananthararn, J Walrand. Achieving 100% throughput in an input-queued switch[J]. in IEEE Transactions on Communication, 1999, 47 (8) : 1260 - 1267.
  • 5N McKeown. The iSLIP scheduling algorithm for input-queued switches[J]. IEEE/ACM Transactions on Networking, 1999,7 (2) : 188 - 201.
  • 6N McKeown, V Anantharam, J Walrand. Achieving 100% throughput in an input-queued switch[A]. In IEEE Proceedings of INFOCOM[C]. San Francisco, USA, 1996. 296 - 302.
  • 7N McKeown, Anderson TE. A quantitative comparison of scheduling algorithms for input-queued switches[J]. Computer Networks and ISDN Systems, 1998,30(24) : 2309 - 2326.
  • 8A Mekkittikul, N McKeown. A practical scheduling algorithm to achieve 100% throughput in input-queued switches [A]. In IEEE Proceedings of INFOCOM [ C ]. San Francisco, USA, 1998,2:792- 799.
  • 9E Altman, Z Liu, R Righter. Scheduling of an input-queued switch to achieve maximal throughput [J]. Probability in the Engineering and Informational Sciences, 2000,14: 327 - 334.
  • 10C S Chang, W J Chen, H Y Huang. On service guarantees for input buffered crossbar switches: A capacity, decomposition approach by Birkhoff and von Neumann[ A ]. In IEEE IWQoS' 99[ C]. London, UK, 1999.79 - 86.

同被引文献18

  • 1CAPONE A, ELIAS J, MARTIGNON F. Routing and resource opti- mization in service overlay networks[J]. Elsevier Computer Networks, 2009, 53(2):180-190.
  • 2YU M, YI Y, REXFORD J. Rethinking virtual network embedding: substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communications Review, 2008, 38(2): 17-29.
  • 3ZHUGE B, YU C, LIU K E Research on internal flow control mecha- nism of ForCES routers[J]. Information Technology Journal 2011 Asian Network for Scientific Information, 2011, 10(3):626-638.
  • 4KESIDIS G, MCKEOWN N. Output-buffer ATM packet switching for integrated-services comrnunicateon networks[A]. Proceedings of IEEE ICC'97[C]. Montreal, Canada, 1997. 342-350.
  • 5MEKKITTIKUL A, MCKEOWN N. A practical scheduling algorithm for achieving 100% throughput in input-queued switches[A]. INFO- COM'98[C]. San Francisco, CA, 1998.792-799.
  • 6MEKKrITIKUL A. Scheduling Non-uniform Traffic in High Speed Packet Switches and Routers[D]. Stanford University, 1998. 17-20.
  • 7GIACCONE P, PRABHAKAR B, SHAH D. Towards simple high- performance schedulers for high-aggregate bandwidth switches[A]. IEEE INFOCOM2002[C]. New York, USA, 2002. 120-127.
  • 8LEE Y, LOU J Y, LUO J Z. An efficient packet scheduling algorithm with deadline guarantees for input-queued switches[J]. Journal IEEE/ACM Transitions on Networking, 2007, 15(1): 212-225.
  • 9LEONARDI E, MELLIA M, NERI F. Design and implementation of a fast VOQ scheduler for a switch sabric[J]. IJCSNS International Jour- nal of Computer Science and Network Security, 2008, 8(9):32-36.
  • 10CAPRITA B, NIEH J, CHAN W C. Group round robin: improving the fairness and complexity of packet scheduling[A]. Proc of the ACM/ IEEE ANCS[C]. Princeton, New Jersey, USA, 2005.29-40.

引证文献1

二级引证文献1

电子学报
2008年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部