Balancing Traffic Flows in Resilient Packet Rings

Resilient Packet Ring (RPR) is a new telecommunication transport technology that combines (a) high bandwidth utilization usually associated with Ethernet and (b) the 50ms protection schemes (in the case of segment /node failures) associated with SONET rings. The RPR is in essence, a distributed Ethernet switch, in which the RPR nodes are connected with two counter-rotating rings (clockwise and counter-clockwise ring). The ring spans are either SONET of Gbit Ethernet. The (unidirectional) point-to-point traffic demands (10/100/1000 Ethernet and/or TDM) can be carried on either ring. In this paper, a ring-loading problem is considered which arises in engineering and planning of the RPR systems. Specifically, for a given set of non-splitable and uni-directional commodities (point-to-point demands), the objective is to find the routing for each commodity (i.e., assignment of the commodity to either clockwise or counter-clockwise ring) so that the maximum link segment load is minimized. In the stochastic scenario, when the objective is to minimize the maximum packet delay, we will show how to formulate an optimization model which can be solved analytically as well. In both the deterministic and stochastic case, the RPR loading problem is formulated as an Integer Programming (IP) problem and two simple heuristics (namely: (i) Greedy and (ii) LP relaxation) are proposed to solve it. The computational experience with these heuristics is reported and results compared with the optimal (integer programming) solution are presented.