LOGICALLY REARRANGABLE MULTIHOP LIGHTWAVE NETWORKS

The multihop architecture for local and metropolitan area networks provides a way of tapping the vast capacity potential available in lightwave networks. Within this architecture, each network node is equipped with some small number of transmitters and receivers, each of which can communicate on one wavelength. Transmitters and receivers are connected to an optical medium, which is physically configured in such a way that the entire spectrum of wavelengths in use is potentially accessible by each node. Then, an assignment of transmit and receive wavelengths to each user defines the logical connectivity among users. Furthermore, the use of optically agile transceivers (i.e., slowly tunable lasers or optical filters) permits the logical connectivity to be updated in response to changing traffic patterns and failure/recovery of nodal transmitters and receivers. This independence between physical topology and logical connectivity provides challenging opportunities in the field of telecommunications. Since total achievable throughput is a critical performance measure for local and metropolitan area networks, a possible design objective consists of finding the network connectivity (achieved by wavelength assignment) and partitioning the flow of traffic among the links created (the routing problem) such that the largest flow on any link is minimized. Such a design would accommodate the greatest scaled version of the externally offered, nonuniform node-to-node traffic. In this paper, we cast these problems into a mixed integer optimization formulation. We proceed by decomposing the joint problem into two independent, but suboptimal subproblems, with the connectivity subproblem heuristically formulated through the choice of a meaningful objective function. This yields an integer linear programming problem whose integer constraints can be dropped. The routing subproblem can then be cast and solved as a multicommodity flow problem. An algorithm is proposed which iterates between connectivity and routing to further improve the solution. We tested our algorithm on illustrative traffic matrices for an 8 node network with two transmitters and two receivers per node, and show an improvement in achievable throughput over the Perfect Shuffle interconnection pattern in all cases. We also derive bounds against which the performance of our heuristic solution may be compared.