Packing problems in the dimensioning of GMPLS-controlled SDH networks

When dimensioning GMPLS-controlled NG-SDH networks several SDH and GMPLS specific requirements must be fulfilled. In SDH there are two different ways for concatenating VC-4 containers, which determine the packing rules of the service inside a frame. GMPLS handles each concatenated SDH connection as a single GMPLS service, thus it has to be placed entirely into one STM frame. To add a new service to a link the controlling node has to find free VC-4 slots for the service. In the paper we assume that it uses a first-fit strategy for this purpose. Furthermore, in GMPLS each service is controlled independently by a distributed intelligence, thus a dimensioning method cannot assume any specific sequence of provisioning steps for different services. The required number of STM frames on the links depends on the sequence of the possible LSP operations, and the very large number of possible LSP operations may cause scalability problems during the calculation of the resources. To overcome the scalability problem a worst-case estimation of the number of required STM frames is needed. In this paper we first prove the theorem that the packing rules are not relevant inside a frame if the sum of SDH service capacities is not more than the capacity of the frame. Based on this and GMPLS specific requirements the dimensioning problem is identical to the Maximum Resource Bin Packing problem. To estimate the maximum number of STM frames on a link we propose an ILP formalization and the application of the results of [1].