Design and dimensioning of dual-homing hierarchical multi-ring networks

A network design study employing multiple interconnected rings which exploit the merits of ring topologies is presented. Near-optimal dual-homing structures are obtained using a novel partition, construct and perturb (PCP) network design method that considers both total ring length and intra-ring traffic. In order to address survivability issues, two bi-connected hierarchical topology schemes are identified, depending on the selection of the interconnecting ring nodes. A routing algorithm that attempts to minimise the maximum flow on the rings, specifically designed for dual-homing structures, is described, which aims for both lower capacity and more balanced solutions than shortest-path routing. The PCP design method is shown to give both better results than an earlier heuristic for various network sizes and demand patterns, and close to the optimal solutions obtained by an integer-linear programming formulation for small problems. Dimensioning of networks is also performed, and the effects of interconnection strategy on total ring length, the ratio of intra-ring to total traffic, overall capacity and average path length of different topologies are discussed.