1. Introduction
Telecommunication networks have become strategic resources for private- and state-owned institutions, and its economic importance continuously increases. There are series of recent tendencies that have a considerable impact on the economy evolution such as growing integration of networks in the productive system, integration of different services in the same communication system, and important modification in the telephone network structure. Such evolutions accompany a significant growth of the design complexity of these systems. The integration of different sorts of traffics and services and the necessity of a more accurate management of the service quality are factors that make this type of systems very hard to design, to dimension, and therefore to optimize. This situation is aggravated with a very high competitiveness context in an area of critical strategic importance.
The conception of a WAN is a process in which dozens of sites with different characteristics require to be connected in order to satisfy certain reliability and performance restrictions with minimal costs. This design process involves the terminal site location, the concentrator location, the backbone [central network or kernel] design, the routing procedures, as well as the lines and nodes dimensioning. A key aspect on WAN design is the high complexity of the problem, as much in its globality as in the principal subproblems in which it is necessary to decompose it. Due to the high investment levels, a cost decrease of very few percentage points while preserving the service quality results in high economic benefits.
Typically, a WAN network global topology can be decomposed into two main components: the access network and the backbone network. These components have very different properties, and consequently they introduce specific design problems [although they are strongly interdependent]. On the one hand, this causes complicated problems [particularly algorithmic ones]; on the other hand, it leads to stimulating and difficult research problems.
A WAN access network is composed of a certain number of access subnetworks, having treelike topologies; and the flow concentration nodes allow to diminish the costs. These integrated flows reach the backbone which has a meshed topology, in order to satisfy security, reliability, vulnerability, survivability, and performance criteria. Consequently, the backbone is usually formed by high-capacity communication lines such as optic fiber links.
Modeling a WAN design by means of the formulation of a single mathematical optimization problem is very intricate due to the interdependence of its large amount of parameters. Therefore the design of a WAN is usually divided into different subproblems [1, 2, 3, 4]. A good example of a possible decomposition approach for the WAN design process is the following [5]:
Access and backbone network topologies design. Specific knowledge about the cost of laying lines between different network sites [terminals, concentrators, and backbone] is assumed. Frequently, these costs are independent of the type of line that will effectively be installed since they model the fixed one-time costs [cost of digging trenches in the case of optic fiber, installing cost, placing a fiber cable into service]. A high percentage from the total construction network budget is spent in this phase [6].
Dimensioning of the lines that will connect the different sites of the access and backbone networks and the equipment to be settled in the mentioned sites.
Definition of the routing strategy of the flow on the backbone network.
This work focuses on phase [1] of the decomposition of a WAN design process. More precisely, it deals with the topology planning process concerning the access network. Due to the NP-hard nature of the problem and even though there exist some results, there is still room for improving industrial practices applied today. In this sense, the authors believe it is of strategic importance to design powerful quantitative analysis techniques, potentially easy to integrate into tools. Combinatorial optimization models are introduced that formally define the topological design of the access networks. Moreover, different results related to the topological structure are introduced. Finally, different algorithms are proposed for the topological design which are based on Dynamic Programming and Dynamic Programming with State-Space Relaxation methodology.
2. A model for a WAN design
In this section, a model for the design of a WAN is introduced. The model tries to show the most essential aspects which are considered when designing access and backbone networks. In this model, some parameters are not considered: the operation probability of the lines and equipment, the number of equipment ports, and the memory capacity of the equipment. The objective is to design a WAN with the smallest possible installation cost, so that the constraints are satisfied.
In what follows, the data of the model are presented as well as its formalization as a combinatorial optimization problem on weighted graphs. The goal is to find the optimal topology that satisfies the imposed constraints to the access and backbone networks. Figure 1 shows an example of a wide area network. The information available for each type of equipment [switch and concentrator] and each type of connection line, as well as the line laying, is the following:
Eais the set of types of connection lines available. FurthermoreeEathe following data are given:
ceis the cost by kilometer of the line typee. Here the laying cost is not included.
veis the speed in Kbits/s of the line typee.
Kis the set of types of concentrator equipment available. FurthermorekKthe following data are given:
ckis the installation cost of the concentrator typek.
vkis the speed in Kbits/s of the concentrator typek.
Wis the set of types of switch equipment available. FurthermorewWthe following data are given:
cwis the installation cost of the switcher typew.
vwis the speed in Kbits/s of the switcher typew.
C=FcostL=cij=direct connection costs between the sites ijiSjSCSD; this matrix gives us, for a site ofSand a site ofSCSD, the cost of laying a line among them. When the direct connection among both places is not possible, we assume thatcij=.
Figure 1.
WAN example.
In terms of graph theory, a model for the design of a WAN, based on the problem, is presented as follows. Some notation is introduced next, that is then used to formally define the problem.
E1=ijiSTjSCSD/dij