Design of private backbone networks-II: Time varying grouped traffic

In an earlier companion paper, the authors have developed a model to assign transmission capacities in private backbone networks, for multi busy-hour point-to-point circuit requirements. In this paper, they consider the situation when point-to-point demands between backbone nodes consist of one or more circuit groups, where each circuit group has one or more circuits. the granularity of routing is a circuit group. Grouping may arise due to multiplexing or heterogeniety of traffic types. The additional difficulties posed by grouping are (i) all circuits in a group are required to follow the same route during a busy-hour and (ii) circuits in the same group cannot be split across different high capacity lines even on the same edge of the backbone network. The 3-phase heuristic developed in the earlier paper is modified to accommodate grouping of circuits. Computational results on practical sizes are compared to a lower bound obtained from an LP relaxation of the problem.