|
|||
|
IMADA - Department of Mathematics and Computer Science |
|
Cable capacities in the backbone networks have increased tremendously over the last decades. This makes it possible for a lot of people to use the same cable at the same time for telephone calls, video and data-transmission. Since many people share the expenses for digging down cables and expenses for transmission-equipment, the cost per person is rather low. On the other hand, if a single cable is cut, this may affect a lot of people and thus cable cuts should be avoided whenever possible. It does, however, seem impossible to avoid cable cuts in general, so the network should include some additional redundant cables that can take over in such cases. I.e. the network should be protected. This presentation concerns capacity-efficient protection of networks by means of so called Preconfigured/Protection-cycles or just P-cycles. By investigating real-world networks, it is experimentally verified that P-cycles are much more capacity-efficient than e.g. rings, regardless that rings are widely used. To achieve this result, we need to design networks and protect them with P-cycles. This is formulated as an integer linear programming model. Previous attempts to solve this problem have enumerated all or a subset of all cycles in the network. Instead, column generation can be used to implicitly represent all cycles in the network. It turns out that generating cycles is a traveling salesman like problem, which can be solved by branch-and-cut. The presentation will contain a brief introduction to networks with focus on protection and P-cycles in particular. An integer linear programming model is presented for the problem of designing networks with P-cycles and the algorithm used for solving this problem. The algorithms are explained in some detail. Finally the efficiency of the P-cycles are compared with other protection methods. Host: Jørgen Bang Jensen SDU HOME | IMADA HOME | Previous Page Last modified: October 20, 2004. Joan Boyar (joan@imada.sdu.dk) |