北京航空航天大学学报 ›› 2016, Vol. 42 ›› Issue (11): 2481-2487.doi: 10.13700/j.bh.1001-5965.2015.0688

• 论文 • 上一篇    下一篇

CICQ结构中逼近work-conserving的分组调度算法

张元昊, 熊庆旭   

  1. 北京航空航天大学 电子信息工程学院, 北京 100083
  • 收稿日期:2015-10-23 修回日期:2016-01-22 出版日期:2016-11-20 发布日期:2016-04-11
  • 通讯作者: 熊庆旭,Tel.:010-82338616,E-mail:qxxiong@buaa.edu.cn E-mail:qxxiong@buaa.edu.cn
  • 作者简介:张元昊,男,硕士研究生。主要研究方向:卫星交换机。E-mail:zyh_demon@163.com;熊庆旭,男,博士,教授,博士生导师。主要研究方向:通信网络、无线通信等。Tel.:010-82338616,E-mail:qxxiong@buaa.edu.cn
  • 基金资助:
    国家自然科学基金(61271196)

Work-conserving-based packet scheduling algorithm for CICQ switches

ZHANG Yuanhao, XIONG Qingxu   

  1. School of Electronic and Information Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China
  • Received:2015-10-23 Revised:2016-01-22 Online:2016-11-20 Published:2016-04-11

摘要: 联合输入交叉点排队(CICQ)结构的分组调度算法是一个得到了充分研究的领域,但已有算法在吞吐率和分组平均时延方面与输出排队(OQ)的结果相比,依然不够令人满意,其关键在于OQ交换机可以工作于work-conserving状态。不同于已有的研究,本文提出了以使得交换机最大程度工作于work-conserving状态为目标的新的研究思路,给出并证明了CICQ交换机实现work-conserving状态的充分且必要条件。以此为基础,提出了一种新的CICQ输入调度的算法即交叉缓存队列均衡(CQB)算法,并将经典的最大队长优先(LQF)算法用于输出调度,结合得到CQB-LQF算法。仿真结果显示,与经典的及最新的CICQ分组调度算法相比,CQB-LQF算法显著提高了吞吐率及分组平均时延性能。

关键词: 分组交换, 联合输入交叉点排队(CICQ), work-conserving, 调度算法, 时延性能

Abstract: Although packet scheduling for combined input-crosspoint-queued (CICQ) switches has been extensively investigated, the performance in terms of throughput and average delay of packets is not satisfied, especially compared to the results obtained by employing output queued architecture. The key reason is that output queneing(OQ) switch can operate in work-conserving state. Different from the popular approaches appeared in the literatures, our work focuses on scheduling packet so that the switch works approximately in work-conserving state to the largest extent. First, the sufficient and necessary conditions for the switch with CICQ architecture to work in work-conserving state are investigated and proved. Then, a new CICQ input scheduling algorithm called crossbuffer queue balance (CQB) is put forward, which is combined with the classical longest queue first (LQF) scheduling used for output arbiter to obtain CQB-LQF algorithm. Simulation results show that the performance in terms of throughput and average packet delay obtained by CQB-LQF is much better than the classical and popular algorithms.

Key words: packet switching, combined input-crosspoint-queued (CICQ), work-conserving, scheduling algorithm, delay performance

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发