# Sonet Network Design Problems

Marie Pelleau†,‡ Pascal Van Hentenryck‡ Charlotte Truchet†
marie.pelleau@univ-nantes.fr pvh@cs.brown.edu Charlotte.Truchet@univ-nantes.fr

| † Universite de Nantes    | ‡ Brown University   |
|---------------------------|----------------------|
| ´                         |                      |
| Departement informatique  | Computer Science     |
| ´ 2 rue de la Houssiniere | 115 Waterman Street  |
| `                         |                      |
| 44322 Nantes cedex 3      | Providence, RI 02912 |
| France                    | USA                  |

This paper presents a new method and a constraint-based objective function to solve two problems related to the design of optical telecommunication networks, namely the Synchronous Optical Network Ring Assignment Problem (SRAP) and the Intra-ring Synchronous Optical Network Design Problem (IDP). These network topology problems can be represented as a graph partitioning with capacity constraints as shown in previous works. We present here a new objective function and a new local search algorithm to solve these problems. Experiments conducted in COMET allow us to compare our method to previous ones and show that we obtain better results.

## 1 Introduction

This paper presents a new algorithm and an objective function to solve two real-world combinatorial optimization problems from the field of network design. These two problems, the Synchronous Optical Network Ring Assignment Problem (SRAP) and the Intra-ring Synchronous Optical Network Design Problem (IDP), have been shown N P-hard and have already been solved by combinatorial optimization techniques. This work extends the seminal ideas introduced by R. Aringhieri and M. Dell'Amico in 2005 in [2].

This paper is organized as follows. In the sequel of this section we introduce the two problems we have worked on, and the local search techniques which have been used to solve them. We will also introduce the models in a constrained optimization format for the two problems. We then present the previous works on SRAP and IDP in section 2. Section 3 describes the key ingredients necessary to implement the local search algorithms. Finally, the results are shown in Section 4.

## 1.1 Optical Networks Topologies

During the last few years the number of internet based application users has exponentially increased, and so has the demand for bandwidth. To enable fast transmission of large quantities of data, the fiber optic technology in telecommunication is the current solution.

The Synchronous Optical NETwork (SONET) in North America and Synchronous Digital Hierarchy
(SDH) in Europe and Japan are the standard designs for fiber optics networks. They have a ring-based topology, in other words, they are a collection of rings.

Y. Deville and C. Solnon (Eds): Sixth International Workshop on Local Search Techniques in Constraint Satisfaction (LSCS'09).

EPTCS 5, 2009, pp. 81–95, doi:10.4204/EPTCS.5.7 c M. Pelleau & P. Van Hentenryck & C. Truchet arXiv:0910.1255v1 [cs.AI] 7 Oct 2009