Successive max–min connection-ratio problem: Routing with fairness and efficiency in circuit telecommunication networks

This paper considers a new routing problem, successive max–min connection ratio problem (SMCRP), arised in circuit telecommunication networks such as SONET and WDM optical transport network. An optimization model for SMCRP is established based on link-flow formulation. Its first optimization process is an integral version of maximum concurrent flow problem. Integer condition does not give the same connection-ratio of each node-pair at an optimal solution any more. It is also an integral multi-commodity flow problem with fairness restriction. In order to guarantee fairness to every node-pair the minimum of connection ratios to demand is maximized. NP-hardness of SMCRP is proved and a heuristic algorithm with polynomial-time bound is developed for the problem. Augmenting path and rerouting flow are used for the algorithm. The heuristic algorithm is implemented and tested for networks of different sizes. The results are compared with those given by GAMS/OSL, a popular commercial solver for integer programming problem.