Combined channel allocation and routing algorithms

Joint optimization of capacity and flow assignment (CFA) is considered for high-speed packet-switched networks in which multiple trunk links are modeled by parallel M/M/1 queues. A quadratic cost function is considered to reflect both switching and line costs. Queuing, transmission, nodal processing, and propagation delays are all incorporated into the optimization problem. The proposed CFA problem is shown to be a convex optimization problem, thus ensuring a global solution. By invoking optimality of the CFA problem and relaxing the integral channel constraint to a continuous variable, a set of nonlinear equations is derived for the optimal solutions. To circumvent the computational burden involved with the continuous solution approach and to capture the discrete nature of channel allocation, an efficient discrete optimization algorithm is developed based on a marginal analysis approach.