High-speed packet switching scheduling algorithm

被引：0
|
作者：
Wang J.-F. [1 ]
Zhang S.-D. [1 ]
机构：
[1] School of Electronics and Information Engineering, Beijing Jiaotong University
来源：
Dianzi Keji Daxue Xuebao/Journal of the University of Electronic Science and Technology of China | 2010年 / 39卷 / 01期
关键词：
I-CPRR algorithm; ISLIP; Matching; Packet switching; Scheduling algorithm; Virtual output queuing;
D O I：
10.3969/j.issn.1001-0548.2010.01.017
中图分类号：
学科分类号：
摘要：
On the basis of iSLIP (iterative slip) algorithm, a VOQ (virtual output queuing) based high speed switching scheduling algorithm, i-CPRR (iterative-correlatived pointer round-robin) algorithm is presented. In this algorithm, the math principle of uncontested diagonal data in bipartite graphs matching is utilized and the correlative pointer processing method is adopted. This algorithm simplifies the round-robin mode of the pointer and reduces the design difficulty. The simulation results show that the algorithm decreases the iterative times in the scheduling procedure, improves the bandwidth utilization under heavy load, reduces the time delay and the depth of VOQ queue in the switching system. It has wide application prospective in high speed switching systems.
引用
收藏
页码：69 / 73
页数：4
相关论文
共 12 条
  • [1] Ma X.-J., Lan J.-L., Emulating output queueing with the central-stage buffered clos packet switching network, IEEE Conference on High Performance Switching and Routing, pp. 98-103, (2008)
  • [2] Mekkittikul A., Mckeown N., A practical scheduling algorithm to achieve 100% throughput in input-queued switches, Proceedings of the 17th Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 792-799, (1998)
  • [3] Chiussi F., Gerla M., Sivaraman V., Traffic shaping for end-to-end delay guarantees with EDF scheduling, The 8th International Workshop on Quality of Service, pp. 10-18, (2000)
  • [4] Ma X.-J., Li X.-Q., Lan J.-L., Et al., A novel scheduling scheme with bandwidth guarantees in the multiple-plane and multiple-stage packet switching fabric, Journal of Electronics & Information Technology, 31, 6, pp. 1475-1478, (2009)
  • [5] Zhu P.-D., High-Performance Router, pp. 55-57, (2005)
  • [6] Hopcroft J.E., Karp R.M., An n5/2 algorithm for maximum matching in bipartite graphs, SIAM Journal on Computing, 1, 2, pp. 225-231, (1983)
  • [7] Mckeown N., Mekkittikl A., Anantharam V., Et al., Achieving 100% throughput in an input-queued switch, IEEE Transactions on Communications, 47, 8, pp. 1260-1267, (1999)
  • [8] Sun Z.-G., Research and implementation of scheduling algorithms in high-speed router switches, (2000)
  • [9] Nick M., Scheduling algorithms for input-queued switches, (1995)
  • [10] Li Q., Qi Y.-L., Improvement and comparison of input queue iSLIP algorithm, Journal of North China Electric Power University, 36, 2, pp. 106-109, (2009)
12