Design algorithms for reconfigurable networks
Ming-Jeng Lee · University of Southern California Digital Library · 2017
This dissertation addresses four interrelated problems. In the first problem, we consider the joint problem of topological design, discrete capacity assignment and routing in traditional reconfigurable networks which transmit data packets. In the optimization model, the two types of constraints are (i) capacity constraints that describe all possible logical configurations and (ii) traditional flow conservation constraints. The objective is to minimize the average packet delay. We developed a partial branch and bound algorithm to solve the problem. It is shown that reconfiguration capability may reduce average packet delay by more than 66%. In the second problem, we consider a flow model for Asynchronous Transfer Mode (ATM) networks. We show that the flows and losses of ATM cells in an ATM network can be represented by a nonlinear system of equations. We then provide a sufficient condition to guarantee that the nonlinear system of equations has a unique solution and this unique solution can be determined by our proposed iterative method. With the solution, end-to-end cell loss probabilities and end-to-end delays can be computed. In the third problem, we consider the routing problem in ATM networks where the objective is to minimize the largest link cell loss probability. We develop an algorithm to determine a global optimal solution to the problem. So far, this is the only formulation of the routing problem in ATM networks for which determining a global optimal solution is computationally tractable. In the fourth problem, we consider a design problem for reconfigurable ATM networks. We first show how the reconfiguration capability can be implemented in ATM switches. We formulate the topological design, capacity assignment and routing problem in reconfigurable ATM networks. The objective is to minimize total ATM cell losses. We develop an algorithm to solve this problem. In the computational experiments, the average cell loss probabilities were reduced by more than 50% by reconfiguration capability. (Copies available exclusively from Micrographics Department, Doheny Library, USC, Los Angeles, CA 90089-0182.)