混合优化的CICQ交换结构调度算法

doi:10.3724/SP.J.1087.2012.01791

计算机应用 ›› 2012, Vol. 32 ›› Issue (07): 1791-1795.DOI: 10.3724/SP.J.1087.2012.01791

混合优化的CICQ交换结构调度算法

高志江,曾华燊,申志军

西南交通大学信息科学与技术学院，成都610031

收稿日期:2011-12-26 修回日期:2012-02-14 发布日期:2012-07-05 出版日期:2012-07-01
通讯作者: 高志江
作者简介:高志江(1985-),男,甘肃漳县人,博士研究生，主要研究方向：高速交换结构；曾华燊(1945-),男,四川成都人,教授,博士生导师,博士,主要研究方向：网络体系结构、高速交换结构、路由器测试；申志军(1976-),男，河南信阳人，讲师，博士，主要研究方向：网络与通信、高速交换技术。
基金资助:
国家自然科学基金资助项目(61102123);“中国工程科技中长期发展战略研究”联合基金资助项目(U0970122);四川大学基金资助项目(下一代Internet体系结构)

Hybrid optimization packet scheduling algorithm for CICQ switches

GAO Zhi-Jiang,ZENG Hua-shen,SHEN Zhi-Jun

School of Information Science and Technology, Southwest Jiaotong University, Chengdu Sichuan 610031, China

Received:2011-12-26 Revised:2012-02-14 Online:2012-07-05 Published:2012-07-01
Contact: GAO Zhi-Jiang

摘要/Abstract

摘要： 联合输入端和交叉点排队（CICQ）的Crossbar是一种性能优于传统结构的交换结构，对CICQ交换结构的特点进行了讨论并提出一种新的混合优化调度（HOPS）算法，算法在输入端调度时采取混合优化的策略，首先尽力保证系统的吞吐率性能，然后根据长队列优先的原则优化系统的时延性能。算法以轮询调度为基础，最多只在输入端进行一次比较操作，其算法复杂度仅为O(1)，实现简单。通过流体模型证明该算法对满足强大数定律的许可输入流量能够达到100%的吞吐率性能。仿真结果进一步表明HOPS调度算法在各种流量模型下都能稳定运行，且具有良好的时延和吞吐率性能。

关键词: CICQ交换结构, 调度算法, 混合优化, 稳定性, 吞吐率

Abstract: Combined Input-Crosspoint-Queued (CICQ) Crossbar outperforms traditional switch fabrics. In this paper, the features of CICQ switches were discussed and a new scheduling algorithm called Hybrid Optimization Packet Scheduling (HOPS) was proposed. This algorithm was based on a hybrid optimization method. The throughput of the algorithm was guaranteed in the first stage of input scheduling and the delay performance was improved by serving the longer queue in the second stage. HOPS was mainly based on Round-Robin (RR) mechanism and at most one comparison operation was done at input port, so it had a complexity of O(1) and easy to implement in hardware. With fluid model techniques, it was proved that HOPS algorithm can achieve 100% throughput for any admissible traffic without using speed-up. The simulation results show that HOPS algorithm exhibits favorable delay, throughput performance and stability under any admissible traffic.

Key words: Combined Input-Crosspoint-Queued (CICQ) switch fabric, scheduling algorithm, hybrid optimization, stability, throughput

中图分类号:

TP393.07

高志江曾华燊申志军. 混合优化的CICQ交换结构调度算法[J]. 计算机应用, 2012, 32(07): 1791-1795.

GAO Zhi-Jiang ZENG Hua-shen SHEN Zhi-Jun. Hybrid optimization packet scheduling algorithm for CICQ switches[J]. Journal of Computer Applications, 2012, 32(07): 1791-1795.

参考文献

［1］ ABEL F, MINKENBERG C, ILIADIS I, et al. Design issues in next-generation merchant switch fabrics ［J］. IEEE/ACM Transactions on Networking, 2007, 15(6): 1603-1615.

［2］ KAROL M, HLUCHYJ M, MORGAN S. Input versus output queueing on a space division switch ［J］. IEEE Transactions on Communications, 1988, 35(12): 1347-1356.

［3］ McKEOWN N, MEKKITTIKUL A, ANANTHARAM V, et al. Achieving 100% throughput in an input-queued switch ［J］. IEEE Transactions on Communications, 1999, 47(8): 1260-1267.

［4］ CHUANG S T, IYER S, McKEOWN N. Practical algorithms for performance guarantees in buffered crossbars ［C］// Proceedings of IEEE International Conference on Computer Communications. Piscataway: IEEE, 2005: 981-991.

［5］ TURNER J. Strong performance guarantees for asynchronous crossbar schedulers ［C］// Proceedings of IEEE International Conference on Computer Communications. Piscataway: IEEE, 2006: 1-11.

［6］ McKEOWN N. The iSLIP scheduling algorithm for input-queued switches ［J］. IEEE/ACM Transactions on Networking, 1999, 7(2): 188-201.

［7］ ROJAS-CESSA R, OKI E, JING Z, et al. CIXB-1: Combined input one-cell-crosspoint buffered switch ［C］// Proceedings of IEEE High Performance Switching and Routing. Piscataway: IEEE, 2001: 324-329.

［8］ PAN DENG, YANG YUANYUAN. Localized independent packet scheduling for buffered crossbar switches ［J］. IEEE Transactions on Computers, 2009, 58(2): 260-274.

［9］ NABESHIMA M. Performance evaluation of a combined input-and crosspoint-queued switch ［J］. IEICE Transactions on Communications, 2000, 83(3): 737-741.

［10］ JAVIDI T, MAGILL R, HRABIK T. A high-throughput scheduling algorithm for a buffered crossbar switches fabric ［C］// Proceedings of the IEEE International Conference on Communications. Piscataway: IEEE, 2001: 1586-1591.

［11］ DAIJ G, PRABHAKAR B. The throughput of data switches with and without speedup ［C］// Proceedings of IEEE International Conference on Computer Communications. Piscataway: IEEE, 2000: 556-564.

［12］ MHAMDI L, HAMDI M. MCBF: A high-performance scheduling algorithm for buffered crossbar switches ［J］. IEEE Communications Letters, 2003, 7(9): 451-453.

［13］ ZHANG XIAO, BHUYAN L N. An efficient scheduling algorithm for combined input-crosspoint-queued (CICQ) switches ［C］// Proceedings of IEEE Global Communications Conference. Piscataway: IEEE, 2004: 1168-1173.

[1]	邓文瀚, 张铭, 王李进, 钟一文. 混合群体增量学习算法求解闭环布局问题[J]. 计算机应用, 2021, 41(1): 95-102.
[2]	刘风. 基于防治策略的毒品滥用流行病学模型[J]. 计算机应用, 2020, 40(9): 2768-2773.
[3]	刘艳, 张玉. 基于Logistic映射的射频识别防碰撞算法[J]. 计算机应用, 2020, 40(8): 2334-2339.
[4]	李明, 胡江平, 曹晓莉, 彭鹏. 面向差异化覆盖的异构有向传感器节点调度算法[J]. 计算机应用, 2020, 40(12): 3563-3570.
[5]	吴三柱, 李鹏, 吴三斌. 移动无线传感器网络中抑制病毒传播模型[J]. 计算机应用, 2020, 40(1): 129-135.
[6]	谭鑫, 李晓卉, 刘振兴, 丁月民, 赵敏, 王琦. 基于电网的采样感知加权循环调度算法[J]. 计算机应用, 2019, 39(7): 2061-2064.
[7]	刘风. 毒品滥用流行病模型的稳定性分析[J]. 计算机应用, 2019, 39(5): 1534-1539.
[8]	杨继东, 孙兆琦, 王飞龙. 基于视觉抓取的并联桁架机器人最优路径控制[J]. 计算机应用, 2019, 39(3): 913-917.
[9]	纪艺, 史昕, 赵祥模. 基于多前车信息融合的智能网联车辆跟驰模型[J]. 计算机应用, 2019, 39(12): 3685-3690.
[10]	赵玉婷, 韩宝玲, 罗庆生. 基于deep Q-network双足机器人非平整地面行走稳定性控制方法[J]. 计算机应用, 2018, 38(9): 2459-2463.
[11]	蔡秀梅, 刘超, 黄贤英, 刘小洋, 杨宏雨. 网络垃圾信息ILDR传播模型[J]. 计算机应用, 2018, 38(8): 2316-2322.
[12]	樊佳庆, 宋慧慧, 张开华. 通道稳定性加权补充学习的实时视觉跟踪算法[J]. 计算机应用, 2018, 38(6): 1751-1754.
[13]	陈晨, 赵建伟, 曹飞龙. 基于四通道卷积稀疏编码的图像超分辨率重建方法[J]. 计算机应用, 2018, 38(6): 1777-1783.
[14]	孙美东, 刘勤让, 刘冬培, 燕昺昊. 面向非全互连3D NoC的自适应单播路由算法[J]. 计算机应用, 2018, 38(5): 1470-1475.
[15]	王珍珍, 吴英杰. 基于Logistic-Volterra模型的制造企业与物流企业联动发展稳定性分析[J]. 计算机应用, 2018, 38(2): 589-595.

混合优化的CICQ交换结构调度算法

Hybrid optimization packet scheduling algorithm for CICQ switches

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics