基于深度增强学习的数据中心网络coflow调度机制
|
摘要
最小化语义相关流的平均完成时间是数据中心网络流量管理面临的难题之一.受人工智能领域深度增强学习方向的最新研究进展启发,本文提出一种的新的语义相关流调度机制.将带宽约束的语义相关流调度问题转化为连续的学习过程,通过学习以往策略实现最佳调度.引入反向填充和有限复用机制,保证系统的工作保持性和无饥饿性.仿真结果表明,在不同的网络负载下,本文提出的调度机制均使得语义相关流的平均完成时间小于其他调度机制,尤其是网络负载较大时,相比最先进的调度机制,性能提升约50%.
Coflow completion time minimization is one of the challenges of traffic management in data center networks. Inspired by the newest research progress in deep reinforcement learning,which is one direction of artificial intelligence,this paper proposes a novel coflow scheduling mechanism. It translates the coflow scheduling problem with bandwidth constraint into a continuous learning process. By learning the previous decisions,the best scheduling is obtained. By introducing back filling and limited multiplexing mechanisms,the system is work-conserving and starvation-free. Simulation results showthat,under different network load,compared with other scheduling mechanisms,the average coflow completion time is reduced. Especially when the network load is heavy,the proposed mechanism achieves about 50% performance improvement than the state-of-the-art scheduling mechanism.
Coflow completion time minimization is one of the challenges of traffic management in data center networks. Inspired by the newest research progress in deep reinforcement learning,which is one direction of artificial intelligence,this paper proposes a novel coflow scheduling mechanism. It translates the coflow scheduling problem with bandwidth constraint into a continuous learning process. By learning the previous decisions,the best scheduling is obtained. By introducing back filling and limited multiplexing mechanisms,the system is work-conserving and starvation-free. Simulation results showthat,under different network load,compared with other scheduling mechanisms,the average coflow completion time is reduced. Especially when the network load is heavy,the proposed mechanism achieves about 50% performance improvement than the state-of-the-art scheduling mechanism.
引文
[1]DEAN J,GHEMAWAT S.Map Reduce:simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113.
[2]ZAHARIA M,CHOWDHURY M,FRANKLIN M J,et al.Spark:cluster computing with working sets[J].Hot Cloud,2010,10(10-10):95.
[3]ISARD M,BUDIU M,YU Y,et al.Dryad:distributed dataparallel programs from sequential building blocks[A].Proceedings of ACM Euro Sys[C].Lisboa:ACM,2007.59-72.
[4]CHOWDHURY M,ZAHARIA M,MA J,et al.Managing data transfers in computer clusters with orchestra[J].ACM Special Interest Group on Data Communication,2011,41(4):98-109.
[5]CHOWDHURY M,STOICA I.Coflow:A networking abstraction for cluster applications[A].Proceedings of ACM Hot Nets[C].Redmond:ACM,2012.31-36.
[6]SILVER D,HUANG A,MADDISON C,et al.Mastering the game of Go with deep neural networks and tree search[J].Nature,2016,529(7587):484-489.
[7]赵冬斌,邵坤,朱圆恒,等.深度强化学习综述:兼论计算机围棋的发展[J].控制理论与应用,2016,33(6):701-717.ZHAO Dong-bin,SHAO Kun,ZHU Yuan-heng,et al.Reviewof deep reinforcement learning and discussions on the development of computer Go[J].Control Theory&Applications,2016,33(6):701-717.(in Chinese)
[8]MNIH V,KAVUKCUOGLU K,SILVER D,et al.Humanlevel control through deep reinforcement learning[J].Nature,2015,518(7540):529-533.
[9]MAO H,ALIZADEH M,MENACHE I,et al.Resource management with deep reinforcement learning[A].Proceedings of the ACM Hot Nets[C].Atlanta:ACM,2016.50-56.
[10]WILSON C,BALLANI H,KARAGIANNIS T,et al.Better never than late:meeting deadlines in datacenter networks[J].ACM Special Interest Group on Data Communication,2011,41(4):50-61.
[11]HONG C,CAESAR M,GODFREY P B,et al.Finishing flows quickly with preemptive scheduling[J].ACM Special Interest Group on Data Communication,2012,42(4):127-138.
[12]ALIZADEH M,YANG S,SHARIF M,et al.Pfabric:Minimal near-optimal datacenter transport[A].ACM SIGCOM M Computer Communication Review[C].Hong Kong:ACM,2013.435-446.
[13]CHOWDHURY M,ZHONG Y,STOICA I.Efficient coflowscheduling with varys[A].Proceedings of ACM SIGCOM M[C].Chicago:ACM,2014.443-454.
[14]DOGAR F R,KARAGIANNIS T,BALLANI H,et al.Decentralized task-aware scheduling for data center networks[A].Proceedings of the ACM SIGCOMM Computer Communication Review[C].Chicago:ACM,2014.431-442.
[15]ZHAO Y,CHEN K,BAI W,et al.Rapier:Integrating routing and scheduling for coflow-aware data center networks[A].Proceedings of IEEE INFOCOM[C].Hong Kong:IEEE,2015.424-432.
[16]MC KEOWN N,ANDERSON T,BALAKRISHNAN H,et al.Open Flow:enabling innovation in campus networks[J].ACM SIGCOMM Computer Communication Review,2008,38(2):69-74.
[17]JEYAKUMAR V,ALIZADEH M,MAZIèRES D,et al.Eye Q:Practical network performance isolation at the edge[A].Proceedings of NSDI[C].Lombard:USENIX,2013.297-312.
[18]SUTTON R S,BARTO A G.Reinforcement Learning:An Introduction[M].Cambridge:M IT Press,1998.
[19]HAGAN M T,DEMUTH H B,BEALE M H,et al.Neural Network Design[M].USA:PWS Publishing Company Boston,1996.
[20]SUTTON R S,MCALLESTER D A,SINGH S P,et al.Policy gradient methods for reinforcement learning with function approximation[A].Proceedings of NIPS[C].Denver:NIPS,2000.1057-1063.
[21]SCHULMAN J,LEVINE S,ABBEEL P,et al.Trust region policy optimization[A].Proceedings of ICM L[C].Lille:IM LS,2015.1889-1897.
[22]JIANG J,MA S,LI B,et al.Adia:achieving high link utilization with coflow-aware scheduling in data center networks[J].IEEE Transactions on Cloud Computing,2016,99(11):1-10.
[23]MA S,JIANG J,LI B,et al.Chronos:meeting coflowdeadlines in data center networks[A].Proceedings of the IEEE International Conference on Communications(ICC)[C].Kuala Lumpur:IEEE,2016.1-6.
[2]ZAHARIA M,CHOWDHURY M,FRANKLIN M J,et al.Spark:cluster computing with working sets[J].Hot Cloud,2010,10(10-10):95.
[3]ISARD M,BUDIU M,YU Y,et al.Dryad:distributed dataparallel programs from sequential building blocks[A].Proceedings of ACM Euro Sys[C].Lisboa:ACM,2007.59-72.
[4]CHOWDHURY M,ZAHARIA M,MA J,et al.Managing data transfers in computer clusters with orchestra[J].ACM Special Interest Group on Data Communication,2011,41(4):98-109.
[5]CHOWDHURY M,STOICA I.Coflow:A networking abstraction for cluster applications[A].Proceedings of ACM Hot Nets[C].Redmond:ACM,2012.31-36.
[6]SILVER D,HUANG A,MADDISON C,et al.Mastering the game of Go with deep neural networks and tree search[J].Nature,2016,529(7587):484-489.
[7]赵冬斌,邵坤,朱圆恒,等.深度强化学习综述:兼论计算机围棋的发展[J].控制理论与应用,2016,33(6):701-717.ZHAO Dong-bin,SHAO Kun,ZHU Yuan-heng,et al.Reviewof deep reinforcement learning and discussions on the development of computer Go[J].Control Theory&Applications,2016,33(6):701-717.(in Chinese)
[8]MNIH V,KAVUKCUOGLU K,SILVER D,et al.Humanlevel control through deep reinforcement learning[J].Nature,2015,518(7540):529-533.
[9]MAO H,ALIZADEH M,MENACHE I,et al.Resource management with deep reinforcement learning[A].Proceedings of the ACM Hot Nets[C].Atlanta:ACM,2016.50-56.
[10]WILSON C,BALLANI H,KARAGIANNIS T,et al.Better never than late:meeting deadlines in datacenter networks[J].ACM Special Interest Group on Data Communication,2011,41(4):50-61.
[11]HONG C,CAESAR M,GODFREY P B,et al.Finishing flows quickly with preemptive scheduling[J].ACM Special Interest Group on Data Communication,2012,42(4):127-138.
[12]ALIZADEH M,YANG S,SHARIF M,et al.Pfabric:Minimal near-optimal datacenter transport[A].ACM SIGCOM M Computer Communication Review[C].Hong Kong:ACM,2013.435-446.
[13]CHOWDHURY M,ZHONG Y,STOICA I.Efficient coflowscheduling with varys[A].Proceedings of ACM SIGCOM M[C].Chicago:ACM,2014.443-454.
[14]DOGAR F R,KARAGIANNIS T,BALLANI H,et al.Decentralized task-aware scheduling for data center networks[A].Proceedings of the ACM SIGCOMM Computer Communication Review[C].Chicago:ACM,2014.431-442.
[15]ZHAO Y,CHEN K,BAI W,et al.Rapier:Integrating routing and scheduling for coflow-aware data center networks[A].Proceedings of IEEE INFOCOM[C].Hong Kong:IEEE,2015.424-432.
[16]MC KEOWN N,ANDERSON T,BALAKRISHNAN H,et al.Open Flow:enabling innovation in campus networks[J].ACM SIGCOMM Computer Communication Review,2008,38(2):69-74.
[17]JEYAKUMAR V,ALIZADEH M,MAZIèRES D,et al.Eye Q:Practical network performance isolation at the edge[A].Proceedings of NSDI[C].Lombard:USENIX,2013.297-312.
[18]SUTTON R S,BARTO A G.Reinforcement Learning:An Introduction[M].Cambridge:M IT Press,1998.
[19]HAGAN M T,DEMUTH H B,BEALE M H,et al.Neural Network Design[M].USA:PWS Publishing Company Boston,1996.
[20]SUTTON R S,MCALLESTER D A,SINGH S P,et al.Policy gradient methods for reinforcement learning with function approximation[A].Proceedings of NIPS[C].Denver:NIPS,2000.1057-1063.
[21]SCHULMAN J,LEVINE S,ABBEEL P,et al.Trust region policy optimization[A].Proceedings of ICM L[C].Lille:IM LS,2015.1889-1897.
[22]JIANG J,MA S,LI B,et al.Adia:achieving high link utilization with coflow-aware scheduling in data center networks[J].IEEE Transactions on Cloud Computing,2016,99(11):1-10.
[23]MA S,JIANG J,LI B,et al.Chronos:meeting coflowdeadlines in data center networks[A].Proceedings of the IEEE International Conference on Communications(ICC)[C].Kuala Lumpur:IEEE,2016.1-6.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |