Computer Science

Computer Science ›› 2021, Vol. 48 ›› Issue (11A): 441-445.doi: 10.11896/jsjkx.201100153

• Network & Communication • Previous Articles     Next Articles

Semi-online Algorithms for Mixed Ring with Two Nodes

XIAO Man, LI Wei-dong   

  1. School of Mathematics and Statistics,Yunnan University,Kunming 650504,China
  • Online:2021-11-10 Published:2021-11-12
  • About author:XIAO Man,born in 1995,master student.His main research interests include discrete optimization,computational complexity,and resource allocation.
    LI Wei-dong,born in 1981,Ph.D,professor .His main research interests include discrete optimization,algorithmic game theory and cloud computing.
  • Supported by:
    National Natural Science Foundation of China(12071417) and Yunnan Innovation Team Project.

PDF (PC)

429

Abstract: Two semi-online scenarios of load balancing problem on a two-point mixed ring are studied.This paper gives a two-point mixed ring and several flow requests,finds a suitable flow transportation method to make the maximum load on the ring as small as possible.When there is a buffer with a capacity of K,the lower bound of 4/3 is given.In particular,when K=1,a lower bound of 3/2 is given,and a semi-online algorithm with a competitive ratio of at most 8/5 is given.When the sum of all flow demands is known,an optimal semi-online algorithm with a competitive ratio of 3/2 is designed.

Key words: Buffer, Competitive ratio, Mixed ring, Online algorithm, Ring loading

CLC Number: 

  • TP301.6
[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] GAO Jie, LIU Sha, HUANG Ze-qiang, ZHENG Tian-yu, LIU Xin, QI Feng-bin. Deep Neural Network Operator Acceleration Library Optimization Based on Domestic Many-core Processor [J]. Computer Science, 2022, 49(5): 355-362.
[2] ZENG De-ze, LI Yue-peng, ZHAO Yu-yang, GU Lin. Reinforcement Learning Based Dynamic Basestation Orchestration for High Energy Efficiency [J]. Computer Science, 2021, 48(11): 363-371.
[3] ZHANG Feng. Node Encounter Interval Based Buffer Management Strategy in Opportunistic Networks [J]. Computer Science, 2019, 46(5): 57-61.
[4] HU Hai-bing, XU Ting, ZHANG Bo, XU Dong-jian, JIN Shi-qun, LU Rong-sheng. Application of Open MP and Ring Buffer Technology in Defects Detection of Glass Substrate [J]. Computer Science, 2019, 46(11A): 562-566.
[5] YOU Zi-qi, REN Yi, LIU Ren-shi, GUAN Jian-bo and LIU Li-peng. Optimization of Co-resident Inter-VM Communication Accelerator XenVMC Based on Multi-core [J]. Computer Science, 2018, 45(3): 102-107.
[6] SHAO Peng, ZHOU Wei, LI Guang-quan, WU Zhi-jian. Improved Anti-aliasing Algorithm Based on Deferred Shading [J]. Computer Science, 2018, 45(11A): 218-221.
[7] FANG Juan, LIU Shi-jian and LIU Si-tong. Routing Algorithm Research on Heterogeneous Network on Chip [J]. Computer Science, 2017, 44(3): 70-72.
[8] XIONG Li-rong, LEI Jing-zhi and JIN Xin. Hybrid Rate Adaptation Algorithm for Adaptive HTTP Streaming [J]. Computer Science, 2017, 44(2): 129-134.
[9] HAN Lin, ZHANG Chun-hai and XU Jian-liang. Data Exchange Based on QR Code in Physically Isolated Internal and External Network Environment [J]. Computer Science, 2016, 43(Z11): 520-522.
[10] MA Xue-bin, LI Ai-li, ZHANG Xiao-juan, JIA Lei-lei and XIAO Jing. Buffer Management Based on Stationary Relay Nodes and Message Correlation in Sparse Opportunistic Networks [J]. Computer Science, 2016, 43(Z11): 296-300.
[11] YAO Zhi-hai, XU Hong-zhe, LI Wen and WU Xia. Research of Cache Management Strategy Based on Splay Tree [J]. Computer Science, 2016, 43(9): 131-134.
[12] JIANG Bo, LI Tao-shen and GE Zhi-hui. Research of Smartphone Energy Saving Based on Buffer Threshold Adaptive Adjustment [J]. Computer Science, 2016, 43(1): 137-140.
[13] LU Xing-hua and CHEN Ping-hua. Traffic Prediction Algorithm in Buffer Based on Recurrence Quantification Union Entropy Feature Reconstruction [J]. Computer Science, 2015, 42(4): 68-71.
[14] DU Wen-feng and WU Zhen. Data Distribution Algorithm with Out-of-order Feedback for CMT over Diversity Network [J]. Computer Science, 2015, 42(3): 60-64.
[15] DING Xiang-wu and ZHANG Guang-hui. PBPP:Pipelined Parallel Processing Based on Passing Buffer in Column-store System [J]. Computer Science, 2014, 41(6): 142-147.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.