Rings Each customer is connected to one or more rings, and can send, receive and relay messages using an add-drop-multiplexer (ADM). There are two bidirectional links connecting each customer to his neighboring customers on the ring. In a bidirectional ring the traffic between two nodes can be sent clockwise or counterclockwise. This topology allows an enhanced survivability of the network, specifically if a failure occurs on a link, the traffic originally transmitted on this link will be sent on the surviving part of the ring. The volume traffic on any ring is limited by the link capacity, called B. The cost of this kind of network is defined by the cost of the different components used in it.

There are different ways to represent a network. In this paper, we consider two network topologies described by R. Aringhieri and M. Dell'Amico in 2005 in [2]. In both topologies the goal is to minimize the cost of the network while guaranteeing that the customers' demands, in term of bandwidth, are satisfied.

The model associated to these topologies are based on graphs. Given an undirected graph G = (V,E),
V = {1*,...,*n}, the set of nodes represent the customers and E, the set of edges, stand for the customers' traffic demands. A communication between two customers u and v corresponds to the weighted edge
(u, v) in the graph, where the weight duv is the fixed traffic demand. Note that duv = dvu, and that duu = 0.

## 1.1.1 First Topology (Srap)

In the first topology, each customer is connected to exactly one ring. All of these *local rings* are connected with a device called digital cross connector (DXC) to a special ring, called the *federal ring*. The traffic between two rings is transmitted over this special ring. Like the other rings, the federal ring is limited by the capacity B. Because DXCs are so much more expensive than ADMs we want to have the smallest possible number of them. As there is a one-to-one relationship between the ring and the DXC, minimizing the number of rings is equivalent to minimizing the number of DXCs. The problem associated to this topology is called *SONET Ring Assignment Problem* (SRAP) *with capacity constraint*.

Figure 1 shows an example of this topology.

![0_image_0.png](0_image_0.png)

Model This topology is modeled by a decomposition of the set of nodes V into a partition, each subset of the partition representing a particular ring. Assigning a node to a subset of the partition in the model is then equivalent to assigning a customer to a ring.

Formally, let V1,V2*,...,*Vk be a partitioning of V in k subsets. Each customer in the subset Viis assigned to the i-th local ring. As each customer is connected with an ADM to one and only one ring, and each local ring is connected to the federal ring with a DXC, there are exactly |V| AMD and k DXC
used in the corresponding SRAP network.