Designing tributary networks with multiple ring families

A common architecture for a telecommunications network consists of several tributary (often called access) networks, which connect locations to hubs, and a backbone network, which interconnects the hubs. This paper describes a heuristic approach for designing tributary networks based on self-healing rings (SHRs). The tributary network consists of multiple ring families, and each of those is comprised of one or more SHRs, called ‘stacked’ rings. The SHRs in a given ring family are routed over the same cycle of optical fiber cables, but each SHR serves only a subset of the locations along the cycle. Each demand location is assigned to a single SHR on one of the ring families, whereas the hub is assigned to all SHRs on all ring families. A link that is used by some ring family incurs a fixed cost plus a variable cost per SHR associated with that family. Each SHR is constrained by the demand volume it can handle and by the number of locations it can serve. This tributary ring network design problem can be viewed as a complex version of a vehicle routing problem with a single-depot and multiple vehicles. Our algorithm is initiated with numerous ring families. It then attempts to merge these families, while ensuring that savings are realized in terms of the sum of fixed and variable costs.