Balancing Loads on SONET Rings without Demand Splitting

Abstract: The Self Healing Ring (SHR) is one of the most intriguig schemes which provide survivability for telecommunication networks. To design a cost effective SONET ring it is necessary to consider load balancing problems by which the link capacity is determined.
 The load balancing problem in SONET ring when demand splitting is not allowed is considered in this paper. An efficient algorithm is presented which provides the best solution starting from varous initial solutions. The initial solution is obtained by routing all demands such that no demands pass through an arc in the ring. The proposed algorithm iteratively improves the initial solution by examining each demand and selectiong the maximum load arc in its path. The demand whose maximum arc load is biggest is selected to be routed in opposite direction. Computational results show that the proposed algorithm is excellent both in the solution quality and in the computational time  requirement. The average error bound of the algorithm is 0.11% of the optimum and compared to dual-ascent approach which has good computational results than other heuristics.