Capacity planning and routing algorithms for telecommunication networks

Abstract

We consider several designing and routing problems for capacitated telecommunication networks. We present formulations for the problems and algorithms for them which are based on the integer programming approaches. First, we consider the variable sized bin packing problem which arises in Asynchronous Transfer Mode (ATM) Virtual Path (VP)-based leased line networks. The objective of the problem is to minimize the total cost of used bins when the cost of unit size of each bin does not increase as the bin size increases. Two greedy algorithms are described, and analyzed in three special cases: a) the sizes of items and bins are divisible, respectively, b) only the sizes of bins are divisible, and c) the sizes of bins are not divisible. Here, we say that a list of numbers $a_1, a_2, …, a_m$ are divisible when $a_j$ exactly divides $a_{j-1}$, for each 1 ＜ j ≤ m. In the case of a), the algorithms give optimal solutions, and in the case of b), each algorithm gives a solution whose value is less than $\frac{11}{9}C(B^*) +4\frac{11}{9}$, where $C(B^*)$ is the optimal value. In the case of c), each algorithm gives a solution whose value is less than $\frac{3}{2}C(B^*) +1$. Second, we consider the problem of designing an ATM VP-based leased line backbone network. Given point-to-point communication demands having predefined sizes in a network, the problem is to find configurations of demand routes and link facilities installed on each edge satisfying all demands at minimum cost under some constraints. One of the most important constraints is that a single demand cannot be split over multiple link facilities. This is a sort of bin packing constraint. We propose an integer programming formulation of the problem and an algorithm to solve it. An efficient column generation technique to solve the linear programming relaxation is proposed, and a valid inequality is used to strengthen the integer programming formulation. The algorithm incorporates the column generation techniq...