计算机科学 ›› 2021, Vol. 48 ›› Issue (11A): 441-445.doi: 10.11896/jsjkx.201100153
肖满, 李伟东
XIAO Man, LI Wei-dong
摘要： 文中研究了两点混合环上负载均衡问题的两种半在线情形。给定一个两点混合环和若干流量需求,寻找合适的流量运输方式,使得环上的最大负载尽可能地小。当存在一个容量为K的缓冲区时,证明了该半在线情形的下界为4/3。特别地,当K=1时,证明了下界为3/2,并给出了一个竞争比至多为8/5的半在线算法。当所有流的需求之和已知时,设计了一个竞争比为3/2的最优半在线算法。
中图分类号:
| [1]COSARES S,SANIEE I.An optimization problem related tobalancing loads on sonet rings[J].Telecommunication Systems,1994,3(2):165-181. [2]SCHRIJVER A,SEYMOUR P.The ring loading problem[J].Siam Review,1999,41(4):777-791. [3]SCHRIJVER A,SEYMOUR P,WINKLERP.The ring loading problem[J].Siam Journal on Discrete Mathematics,1998,11(1):1. [4]SKUTELLA M.A note on the ring loading problem[J].SiamJournal on Discrete Mathematics,2016,30(1):327-342. [5]KHANNA S.A polynomial time approximation scheme for the sonet ring loading problem[J].Bell LabsTechnical Journal,1997,2(2):36-41. [6]LI W D,LIJ P,GUAN L.Approximation algorithms for the ring loading problem with penaltycost[J].Information Processing Letters,2014,14(1/2):56-59. [7]NONG Q Q,YUAN J J,LIN Y X.The weighted link ring loading problem[J].Journal of Combinatorial Optimization,2009,18(1):38-50. [8]WILFONG G,WINKLER P.Ring routing and wavelengthtranslation[C]//Proceedings of the NinthAnnual ACM-SIAM Symposium on Discrete Algorithms.1998:333-341. [9]MYUNG S Y,HU G K,DONG W T.Optimal load balancing on sonet bidirectional rings[J].Operations Research,1997,45(1):148-152. [10]MYUNGS Y,HU G K.On the ring loading problem with de-mand splitting[J].Operations Research Letters,2004,32(2):167-173. [11]WANG B F.Linear time algorithms for the ring loading problem with demand splitting[J].Journal ofAlgorithms,2005,54(1):45-57. [12]BECCHETTI L,IANNI M D,MARCHETTI-SPACCAMELAA.Approximation algorithms for routingand call scheduling in all-optical chains and rings[J].Theoretical Computer Science,2002,287(2):429-448. [13]GUAN L,LI J P,ZHANG X J,et al.The directed ring loading with penalty cost[C]//International Workshop on Algorithms and Computation.Springer,Cham,2015:20-31. [14]HAVILL J T,HUTSON K R.Optimal online ring routing[J].Networks,2010,57(2):187-197. [15]GUAN L,LI W D,XIAO M.Online algorithms for the mixed ring loading problem with two nodes[J].Optimization Letters,2021,15(4):1229-1239. [16]CHEN X,DING N,DOSA G,et al.Online hierarchical scheduling on two machineswith known total size of low-hierarchy jobs[J].International Journal of Computer Mathematics,2015,92(5/6):873-881. [17]KARHI S,SHABTAY D.Online scheduling of two job types on a set of multipurpose machines[J].International Journal of Production Economics,2014,150:155-162. |
| [1] | 曾德泽, 李跃鹏, 赵宇阳, 顾琳. 基于强化学习的高能效基站动态调度方法 Reinforcement Learning Based Dynamic Basestation Orchestration for High Energy Efficiency 计算机科学, 2021, 48(11): 363-371. https://doi.org/10.11896/jsjkx.201000008 |
| [2] | 游资奇,任怡,刘仁仕,管剑波,刘礼鹏. 基于多核的共生虚拟机通信加速机制XenVMC的优化 Optimization of Co-resident Inter-VM Communication Accelerator XenVMC Based on Multi-core 计算机科学, 2018, 45(3): 102-107. https://doi.org/10.11896/j.issn.1002-137X.2018.03.017 |
| [3] | 陆兴华,陈平华. 基于定量递归联合熵特征重构的缓冲区流量预测算法 Traffic Prediction Algorithm in Buffer Based on Recurrence Quantification Union Entropy Feature Reconstruction 计算机科学, 2015, 42(4): 68-71. https://doi.org/10.11896/j.issn.1002-137X.2015.04.012 |
| [4] | 杜文峰,吴 真. 基于乱序反馈的差异化多路径并发传输模型数据分配算法 Data Distribution Algorithm with Out-of-order Feedback for CMT over Diversity Network 计算机科学, 2015, 42(3): 60-64. https://doi.org/10.11896/j.issn.1002-137X.2015.03.013 |
| [5] | 丁祥武,张光辉. PBPP:列存储系统中基于传递块缓冲区的流水线并行处理 PBPP:Pipelined Parallel Processing Based on Passing Buffer in Column-store System 计算机科学, 2014, 41(6): 142-147. https://doi.org/10.11896/j.issn.1002-137X.2014.06.028 |
| [6] | 史飞悦,傅德胜. 缓冲区溢出漏洞挖掘分析及利用的研究 Research of Buffer Overflow Vulnerability Discovering Analysis and Exploiting 计算机科学, 2013, 40(11): 143-146. |
| [7] | 张媛，于冠龙，李仁见. 一种基于模型检验的缓冲区溢出检测方法 Buffer Overflow Detection Method Based on Model Checking 计算机科学, 2012, 39(Z6): 31-34. |
| [8] | 王震,徐博,解永平,孙加奉. 单客户机一多服务器模式下IOCP的应用与研究 Application and Study of IOCP in Single Client-mufti Server Model 计算机科学, 2011, 38(Z10): 385-388. |
| [9] | 严芬,袁赋超,沈晓斌,殷新春,茅兵. 防御缓冲区溢出攻击的数据随机化方法 Data Randomization to Defend Buffer Overflow Attacks 计算机科学, 2011, 38(1): 73-77. |
| [10] | 王得利,高德远,王党辉,孙华锦. 存储器行缓冲区命中预测研究 Research on Row Buffer Hit Prediction for Memory Access 计算机科学, 2010, 37(6): 297-302. |
| [11] | 王沁,潘光荣,杜立国. 基于竞争请求的CM上行发送缓冲区大小的计算方法 Method for Calculating the Upstream Buffer Size of the CM Based on Contention Request Mode 计算机科学, 2009, 36(9): 32-35. |
| [12] | 许俊杰 蔡皖东. 一种远程缓冲区溢出漏洞检测模型及系统实现 计算机科学, 2008, 35(6): 60-62. |
| [13] | . 视频会议中的同步缓冲设计 计算机科学, 2008, 35(4): 82-84. |
| [14] | 李毅超 刘丹 韩宏 卢显良. 缓冲区溢出漏洞研究与进展 计算机科学, 2008, 35(1): 87-89. |
| [15] | 刘通平. 栈溢出的动态检测技术 计算机科学, 2007, 34(9): 282-286. |
|
||
首页