基于邻端口调度信息的反馈型两级交换结构
|
摘要
FTSA (feedback mechanism based two-stage switch architecture)对调度算法执行时间的限制过于苛刻使其优异的理论性能无法实现.针对这一问题,该文提出一种基于邻端口调度信息的反馈型两级交换结构AFTSA (adjacent-port scheduling information and feedback mechanism based two-stage switch architecture), AFTSA引入前置反馈模式将目标缓存的状态数据提前反馈至输入端口;利用邻端口信息传输机制使得任意输入端口均能获得邻端口的调度结果;利用预处理机制修正调度算法所需要的基础信息;利用"裁决"模式的调度机制选择在下一时隙将要转发的信元.理论分析表明在相同的交换环境中AFTSA和FTSA具有等同的时延性能且能够为算法提供接近一个时隙的执行时间,AFTSA可有效提高两级交换结构的实践可行性.
The scheduling algorithm of FTSA(feedback mechanism based two-stage switch architecture)must be completed within the crossbar reconfiguration time. Such harsh time limitation makes it impossible to achieve its very excellent theoretical performance. For this problem, a novel switch architecture called AFTSA(adjacent-port scheduling information and feedback mechanism based two-stage switch architecture) was proposed in this paper. The front-feedback mode was introduced into AFTSA, which enabled the input port to obtain the queue information of the destination middle-port one time-slot ahead.Furthermore, a dedicated communication links between the adjacent input ports was proposed and thus makes any input port can distribute the local scheduling results to its adjacent input port. Based on the scheduling results, the middle-queuing information can be corrected. Every time slot, a scheduling algorithm using the adjudication model will be executed to choice a cell to be forwarded to the middle-port in the next time slot. Theoretical analysis shows that the AFTSA can provide close to a time slot of execution time for the scheduling algorithm and thus will enhance its feasibility of practice. Beyond that, AFTSA has the equivalent delay performance as FTSA does in the same switching environment.
The scheduling algorithm of FTSA(feedback mechanism based two-stage switch architecture)must be completed within the crossbar reconfiguration time. Such harsh time limitation makes it impossible to achieve its very excellent theoretical performance. For this problem, a novel switch architecture called AFTSA(adjacent-port scheduling information and feedback mechanism based two-stage switch architecture) was proposed in this paper. The front-feedback mode was introduced into AFTSA, which enabled the input port to obtain the queue information of the destination middle-port one time-slot ahead.Furthermore, a dedicated communication links between the adjacent input ports was proposed and thus makes any input port can distribute the local scheduling results to its adjacent input port. Based on the scheduling results, the middle-queuing information can be corrected. Every time slot, a scheduling algorithm using the adjudication model will be executed to choice a cell to be forwarded to the middle-port in the next time slot. Theoretical analysis shows that the AFTSA can provide close to a time slot of execution time for the scheduling algorithm and thus will enhance its feasibility of practice. Beyond that, AFTSA has the equivalent delay performance as FTSA does in the same switching environment.
引文
[1] Xiao J, Yeung K L, Jamin S. Pipelined scheduler for unicast and multicast traffic in input-queued switches[C]//Proceedings of the IEEE Global Communications Conference, Washington, 2016:1-6.
[2] Hu B, Yeung K L, Zhou Q, et al. On iterative scheduling for input-queued switches with a speedup of 2-1/N[J].IEEE/ACM Trans on Networking, 2016, 24(6):3565-3577.
[3]蒋泳波,杨春,高雅,等.一种低复杂度的单多播集成调度算法[J].西安电子科技大学学报,2013, 40(4):42-47.Jiang Y B, Yang C, Gao Y, et al. Integration of unicast and multicast scheduling with low complexity[J]. Journal of Xidian University, 2013, 40(4):42-47.
[4] Cerutti I, Corvera J A, Dumlao S M, et al. Simulation and FPGA-based implementation of iterative parallel schedulers for optical interconnection networks[J]. IEEE/OSA Journal of Optical Communications and Networking, 2017, 9(4):C76-C87.
[5] Kartashevskiy V, Kireeva N, Buranova M, et al. Approximation of distributions in the problems of the analysis of self-similar traffic[C]//Proceedings of the Third International Scientific-Practical Conference Problems of Infocommunications Science and Technology, Kharkiv, 2016:105—108.
[6] Chang C S, Lee D S, Jou Y S. Load balanced Birkhoff-von Neumann switches[C]//Proceedings of the IEEE Workshop on High Performance Switching and Routing, Dallas, 2001:276-280.
[7] Ye T, Zhang J, Lee T T, et al. Deflection-compensated Birkhoff-von-Neumann Switches[J]. IEEE/ACM Trans on Networking, 2017, 25(2):879-895.
[8] Durkovic S, Cica Z. Birkhoff-von-Neumann switch with deflection based load balancing[C]//Proceedings of the Telecommunications Forum, Belgrade, 2016:1-4.
[9] Keslassy I, Mckeown N. Maintaining packet order in two-stage switches[C]//Proceedings of the IEEE International Conference on Computer Communications, New York, 2002:1032—1041.
[10] Keslassy I, Chuang S, Yu K, et al. Scaling internet routers using optics[C]//Proceedings of the ACM SIGCOMM,Karlsruhe, 2003:189-200.
[11] Chang C S, Lee D S, Shin Y J, et al. Mailbox switch:A scalable two-stage switch architecture for conflict resolution of ordered packets[J]. IEEE Transactions on Communications, 2008, 56(1):136-149.
[12] Yu C L, Chang C S, Lee D S. CR switch:A load-balanced switch with contention and reservation[J]. IEEE/ACM Transactions on Networking, 2009, 17(5):1659-1671.
[13] Shen Y M, Panwar S S, Chao H J. Design and performance analysis of a practical load-balanced switch[J]. IEEE Transactions on Communications, 2009, 57(8):2420—2429.
[14]扈红超,郭云飞,庞琳,等.动态均衡的LB-BvN分组保序调度机制[J].通信学报,2011,32(4):57-65.Hu H C, Guo Y F, Pang L, et al. Dynamic traffic balancing scheme for LB-BvN to guarantee in-order packet delivering[J]. Journal on Communications, 2011, 32(4):57-65.
[15]戴艺,苏金树,孙志刚.基于流映射的负载均衡调度算法研究[J].计算机学报,2Ol2, 35(2):2218-2228.Dai Y, Su J S, Sun Z G. Research of a load-balanced algorithm based on flow mapping[J]. Chinese Journal of Computers, 2012, 35(2):2218-2228.
[16] Hu B, Yeung K L. Feedback-based scheduling for load-balanced two-stage switches[J]. IEEE/ACM Transactions on Networking, 2010, 18(4):1077-1090.
[17] Cai Y, Wang X L, Gone W B, et al. A study on the performance of a three-stage load-balancing switch[J].IEEE/ACM Transactions on Networking, 2014, 22(1):52-65.
[18] He C Z, Hu B, Yeung K L. FTMS:An efficient multicast scheduling algorithm for feedback-based two-stage switch[C]//Proceedings of the IEEE Global Communications Conference, Anaheim, 2012:2541-2546.
[19] Doukovic S, Cica Z. Birkhoff-von Neumann switch based on greedy scheduling[J]. IEEE Computer Architecture Letters, 2018, 17(1):13-16.
[20] Huang A, Hu B. The optimal joint sequence design in the feedback-based two-stage switch[J]. Journal of Network&Computer Applications, 2014, 45(4):27-34.
[21] Lin Y S, Shung C B. Quasi-pushout cell discarding[J]. IEEE Communication Letters, 1997, 1(5):146-148.
[22]申志军,曾华燊,夏羽.基于前置反馈的两级交换结构[J].通信学报,2011,32(5):56-62.Shen Z J, Zeng H S, Xia Y. Front-feedback-based two-stage switch architecture[J]. Journal on Communications,2011, 32(5):56-62.
[2] Hu B, Yeung K L, Zhou Q, et al. On iterative scheduling for input-queued switches with a speedup of 2-1/N[J].IEEE/ACM Trans on Networking, 2016, 24(6):3565-3577.
[3]蒋泳波,杨春,高雅,等.一种低复杂度的单多播集成调度算法[J].西安电子科技大学学报,2013, 40(4):42-47.Jiang Y B, Yang C, Gao Y, et al. Integration of unicast and multicast scheduling with low complexity[J]. Journal of Xidian University, 2013, 40(4):42-47.
[4] Cerutti I, Corvera J A, Dumlao S M, et al. Simulation and FPGA-based implementation of iterative parallel schedulers for optical interconnection networks[J]. IEEE/OSA Journal of Optical Communications and Networking, 2017, 9(4):C76-C87.
[5] Kartashevskiy V, Kireeva N, Buranova M, et al. Approximation of distributions in the problems of the analysis of self-similar traffic[C]//Proceedings of the Third International Scientific-Practical Conference Problems of Infocommunications Science and Technology, Kharkiv, 2016:105—108.
[6] Chang C S, Lee D S, Jou Y S. Load balanced Birkhoff-von Neumann switches[C]//Proceedings of the IEEE Workshop on High Performance Switching and Routing, Dallas, 2001:276-280.
[7] Ye T, Zhang J, Lee T T, et al. Deflection-compensated Birkhoff-von-Neumann Switches[J]. IEEE/ACM Trans on Networking, 2017, 25(2):879-895.
[8] Durkovic S, Cica Z. Birkhoff-von-Neumann switch with deflection based load balancing[C]//Proceedings of the Telecommunications Forum, Belgrade, 2016:1-4.
[9] Keslassy I, Mckeown N. Maintaining packet order in two-stage switches[C]//Proceedings of the IEEE International Conference on Computer Communications, New York, 2002:1032—1041.
[10] Keslassy I, Chuang S, Yu K, et al. Scaling internet routers using optics[C]//Proceedings of the ACM SIGCOMM,Karlsruhe, 2003:189-200.
[11] Chang C S, Lee D S, Shin Y J, et al. Mailbox switch:A scalable two-stage switch architecture for conflict resolution of ordered packets[J]. IEEE Transactions on Communications, 2008, 56(1):136-149.
[12] Yu C L, Chang C S, Lee D S. CR switch:A load-balanced switch with contention and reservation[J]. IEEE/ACM Transactions on Networking, 2009, 17(5):1659-1671.
[13] Shen Y M, Panwar S S, Chao H J. Design and performance analysis of a practical load-balanced switch[J]. IEEE Transactions on Communications, 2009, 57(8):2420—2429.
[14]扈红超,郭云飞,庞琳,等.动态均衡的LB-BvN分组保序调度机制[J].通信学报,2011,32(4):57-65.Hu H C, Guo Y F, Pang L, et al. Dynamic traffic balancing scheme for LB-BvN to guarantee in-order packet delivering[J]. Journal on Communications, 2011, 32(4):57-65.
[15]戴艺,苏金树,孙志刚.基于流映射的负载均衡调度算法研究[J].计算机学报,2Ol2, 35(2):2218-2228.Dai Y, Su J S, Sun Z G. Research of a load-balanced algorithm based on flow mapping[J]. Chinese Journal of Computers, 2012, 35(2):2218-2228.
[16] Hu B, Yeung K L. Feedback-based scheduling for load-balanced two-stage switches[J]. IEEE/ACM Transactions on Networking, 2010, 18(4):1077-1090.
[17] Cai Y, Wang X L, Gone W B, et al. A study on the performance of a three-stage load-balancing switch[J].IEEE/ACM Transactions on Networking, 2014, 22(1):52-65.
[18] He C Z, Hu B, Yeung K L. FTMS:An efficient multicast scheduling algorithm for feedback-based two-stage switch[C]//Proceedings of the IEEE Global Communications Conference, Anaheim, 2012:2541-2546.
[19] Doukovic S, Cica Z. Birkhoff-von Neumann switch based on greedy scheduling[J]. IEEE Computer Architecture Letters, 2018, 17(1):13-16.
[20] Huang A, Hu B. The optimal joint sequence design in the feedback-based two-stage switch[J]. Journal of Network&Computer Applications, 2014, 45(4):27-34.
[21] Lin Y S, Shung C B. Quasi-pushout cell discarding[J]. IEEE Communication Letters, 1997, 1(5):146-148.
[22]申志军,曾华燊,夏羽.基于前置反馈的两级交换结构[J].通信学报,2011,32(5):56-62.Shen Z J, Zeng H S, Xia Y. Front-feedback-based two-stage switch architecture[J]. Journal on Communications,2011, 32(5):56-62.