Heuristic Algorithms for Load Balancing in Ring Networks

Ring networks are suited to deliver a large amount of bandwidth in a reliable and inexpensive way. An optimal load balancing is of paramount importance because it increases the system capacity and improves the overall ring performance. In this context an important optimization problem is the Weighted Ring Loading Problem. That is the design of a direct path for each request, in a communication network, in a way that high load on the arcs/edges will be avoided, where an arc is an edge endowed with a direction. We study two variants of this problem without demand splitting. The work presented in this document is also focused in other two problems that arise in the design of optical telecommunication networks, namely the Synchronous optical network Ring Assignment Problem (SRAP) and the Intraring synchronous optical network Design Problem (IDP). In SRAP, the objective is to minimize the number of rings and in IDP, the objective is to minimize the number of Add-Drop Multiplexers. Both problems are subject to a ring capacity constraint. To solve these four NP-hard problems, are proposed several metaheuristic algorithms including bio-inspired randomized search heuristics.