The Square Root Multipliers Algorithm for Discrete Capacity and Buffer Assignment problems in Elastic Traffic Networks

This paper discusses a novel approach for the dimensioning of packet networks, under the constraints of end-to-end Quality-of-Service (QoS) requirements. The network modeling also considers the dynamic behavior of today's networks traffic. In particular, the proposed approach considers multilink networks where discrete capacities are the decision variables. This Discrete Capacity Assignment (DCA) problem can be classified as a constrained combinatorial optimization problem and therefore it is NP-complete. In order to solve the problem, we propose the Square Root Multipliers Algorithm (SRMA) followed by a Randomized Rounding (RR) method. We also enforce loss probability constraints by properly choosing buffer sizes, therefore facing the Buffer Assignment (BA) problem. To evaluate the performance of our approach, SRMA/RR results are compared with the optimal solutions found by an exhaustive search (ES) procedure. Analytical results for a variety of problem instances are reported, and a verification is performed based on simulations conducted with the software NS-2. The results suggest that the proposed approach provides a quite efficient method to obtain near-optimal solutions with small computational effort.