The Multiple(Multidimensional) Load Balancing Problem On The Ring

The Synchronous Optical NETwork(SONET)is an important component of op-tical fiber communication network.In the communication network,this structure can avoid line faults effectively.According to the geometric characteristics of the com-munication ring,all traffic demands can be routed clockwise or counterclockwise.A good routing scheme can reduce the network load and improve the utilization rate of the resources.Given a ring R =(V,E)and a set of point pairs U,there is a traffic demand between each point pair,connect the given point pairs clockwise or counterclockwise through the ring,the load on each edge of the ring is the sum of the demands rounted through that edge,and the goal is to minimize the largest load on the edges.In this paper,the ring loading problem is extended,and the ring loading problem of multiple demands and multi-dimensional demands are proposed.For multiple de-mand ring loading problems,a 2-approximation algorithm and a heuristic algorithm are designed based on the solution of linear programming.Then,a 2-approximation combinational algorithm is designed.For the multidimensional demand ring loading problem,a 2-approximation algorithm is designed based on the solution of linear pro-gramming.Then,a 2M-approximate combinational algorithm and a heuristic algorithm are designed.For these two problems,the solution of the algorithm with better over-all performance is taken as the initial solution of the particle swarm algorithm,and the feasible solution of the problem is obtained by the particle swarm alforithm.