I have started a research line to develop techniques helping in the design of the global architecture of a WAN. This means solving very complex high-dimensional optimization problems set in terms of weighted graphs. The design of a WAN is usually decomposed into two main phases, the design of the core network or backbone (usually with a meshed topology) and the design of the access network (usually a tree-like or forest-like topology). Basically, designing a backbone assume that the offered traffic arriving to specific edge nodes is known, together with the destination of the flows (that is, the traffic matrix); the potential nodes that can be built and the cost (in some sense) of the potential links are also available; the problem consists of finding a minimal cost graph satisfying some supplementary constraints (for instance, connectivity constraints, or delay-based properties). Designing the access network is similar; the easiest way of thinking of it is to assume the backbone available; the problem is then to select an appropriate set of concentrators and the set of links connecting the terminals to the backbone through the concentrators sub-network, given the terminal sites, and again the traffic matrix. As for the backbone, the access network is designed looking for a minimal cost topology satisfying supplementary constraints. In some of the procedures we propose for the access network design, we use the Random Network Model as a local search tool (see the papers).
The approaches we propose allow integrating performance or dependability objectives into the optimization process. For instance, we developed a variant of the Greedy Randomized Adaptive Search Procedure (GRASP) for the design of a core network with reliability (connectivity) restrictions (see
See also
for an extended version. Always for backbone design, in
a different local search technique is used. In this last paper, some interesting (favorable) comparisons with well known previous results (obtained among others by Grötshel et al.) are given.
We also followed the same global approach for the design of the access network, adapting the key phases of GRASP to this context, and exploring different local search methods. See
and
Finding Steiner trees with degree 1 terminal
nodes,
IEIEC Transactions 2005 (to appear)
for two different efficient techniques. In these papers we show how effective are our procedures using a known database of benchmarks originally designed for the Traveling Salesman Problem (TSP), the SteinLib repository; we adapted many of the examples in this set of test cases to our problem (which is more complex than TSP), and use them to illustrate the performances of our algorithms.
Some synthesis of our findings together with handling more constraints in the procedures are described in
Designing low-cost
access network topologies,
INOC'2005 (International Network Optimization Conference), pp. 825-832, March 20-23, 2005, Lisbon, Portugal.