The power 2 ring loading problem.

摘要

Optical fiber has the potential for vast data transmission rates in the order of terabits per second. However, the cost and technological development of the optical components that connect optical fiber into data networks limit the availability of optical capacity. This limitation requires the ability to route optical connections to maximize cost effective utilization of available optical bandwidth.; The optical ring is currently the preferred optical network configuration. The Synchronous Optical NETwork (SONET) is the technological standard for optical networks in the United States. The congestion of an optical network is the optical load on the maximum load link. For the cost-effective design of SONET ring networks, a significant issue is to route a set of requests for optical connections to minimize the optical congestion. This problem is referred to as the Ring Loading Problem (RLP). Optical ring network designs are selected based on their ability to minimize network congestion.; RLP is NP-complete. Moreover, network-planning software requires large numbers of iterations of ring loading software modules to determine effective network designs. Therefore, a requirement for routing algorithms is that they be computationally fast. There is a tradeoff between algorithmic precision and computational effectiveness. Therefore, this thesis defines the Power 2 Ring Loading Problem (RLP2) as a subproblem of RLP. RLP2 limits all connection request demands to integer powers of 2. The research contained herein studies RLP2 by finding solutions to two RLP2 subproblems, which limit the shortest path for connection requests to a maximum of 1 and 2 optical links respectively. The solutions to these subproblems are intended to provide insight into possible solutions or approximations for the general form of RLP2.