Project topics and materials
Get Complete Project Material File(s) Now! »
Sub-problem 1: Designing spanning trees
There are di erent ways to model spanning trees as a MIPs. In this section, we present two MIP formulations, that model the design of multiple spanning trees. These build on Formulations 1.7 and 1.8, proposed for the MST problem and described in Section 1.4. Note that in this thesis, we do not consider single commodity ow models for the TE-MSTP problem. As it was seen in Section 1.4, these tend to be weak formulations. In addition, in our preliminary tests we veri ed that these models were not e cient in solving instances of the TE-MSTP problem. The set of variables that are used in the proposed formulations are de ned as follows:
• xuvta = 1 if arc a 2 A is used on the unique path from node u to node v, in VLAN t 2 T ; 0 otherwise;
• zaut = 1 if arc a = (i; j) 2 A is used on the unique path from root node u to node j, in VLAN t 2 T ; 0 otherwise;
• wet = 1 if edge e 2 E is used in VLAN t 2 T ; 0 otherwise.
Note that the rst two set of variables are de ned in the directed graph G0, whereas variables w are de ned on the original graph. The latter are common to both formula-tions; in constraints (2.1), we de ne them as binary. The rst model is a multicommodity ow formulation, that extends Formulation 1.7 in order to design multiple spanning trees. Moreover, we take into attention that we wet 2 f0; 1g; e 2 E; t 2 T (2.1) Formulation 2.1: TE-MSTP SP1: de ning design variables w.
also extend that formulation, so as to have multiple sources of commodities, in addition to multiple destinations. The reason for this will become apparent further on. Given the set of variables fxuvsa; wesg, any feasible solution for the problem must verify the set of constraints in 2.2, in addition to (2.1).
Sub-problem 2: Routing the tra c demands
Once the design for each VLAN is established, it is possible to route the tra c ows according to the demands. To properly model this routing, we can look at the tra c demands in each VLAN in two distinct ways: either by considering the tra c demands between each pair of nodes separately, or by aggregating tra c that shares a single origin (or destination). As seen in Section 2.2.1, the x variables describe a path between each pair of nodes. Therefore, it is natural to associate the rst above-mentioned strategy with the use of these variables, as they allow for the immediate calculation of the load in each edge, of VLAN t 2 T : u;v2N:u<v uvt (xijuvt + xjiuvt). In this sense, to model this second subproblem, we need to de ne for every VLAN, the unique path between each pair of nodes, P in constraints 2.6 X xauvt = 1; u; v 2 N : u < v; t 2 T (2.2a) a2 +(u) a2X(j) a2X(j) u; v; i 2 N : u < v; i 6= fu; vg; t 2 T xauvt xauvt = 0; (2.2b) + xijuvt 2 f0; 1g; (i; j) 2 A; u; v 2 N : u < v; j 6= u; i 6= v; t 2 T (2.2e) Formulation 2.6: TE-MSTP SP2: multi-source-multi-destination routing. Observe that the constraints in 2.6 are the same as in 2.2. We repeat them here for the sake of completeness, since they are also used to model the routing of the tra c demands. Nevertheless, when the two sub-problems are combined, the redundancy is naturally omitted.
Test sets for the TE-MSTP problem
These experiments were conducted using two distinct test sets of randomly generated instances, which aim at emulating two di erent types of network topologies. Instances in both test sets were created such that they span di erent values for the number of nodes and number of VLANs. In the rst test set, Trand, the set of available edges was randomly distributed in the network; the number of edges is calculated according to a given network density. Each edge was given a tra c capacity value of either 50, 75 or 100 Mbps. For each VLAN, the tra c demands (in Mbps) between nodes were generated following an adaptation of the formula proposed in [FT04]: t = (Ot Dt + Ot Dt )Rt e L2(u;v) (2.15) 2 uv u v v u uv For each node u 2 N and VLAN t 2 T , two random numbers, Out and Dvt are randomly generated in the interval [0; 1]. These values re ect, respectively, the attrac-tiveness of each node as a sender and as a receiver. Another value, Ruvt, is generated in the same interval, for each pair of nodes. is a parameter given as input. In these tests, the Euclidian distance (L2) was substituted by the length of the shortest path between each pair of nodes, with respect to the number of edges. is the largest distance in the network. The nal values were rounded to the nearest integer. The second test set, T3tc, follows the 3-Tier Cisco architecture, which is a common network topology in private enterprise data centers [Inf07, HDBF11]. This hierarchical architecture consists in a core, an aggregation and an edge tier. The core, at the top of the hierarchy, provides a gateway to the data center, from the extranet, wide area network, or Internet edge. The switches in the second tier, serve as a bridge between the core and the nodes in the edge tier, aggregating the in and out ows. At the lowest level, the edge tier consists of racks of servers, interconnect by a Top of Rack (ToR) switch. We mimic this topology by generating a tripartite graph, in which around 1% of the nodes belong to the set representing the core tier, around 15% belong to the set representing the aggregation tier, and the remaining nodes stand for the ToR switches, in the edge tier. For each ToR we assign between 20 and 80 servers. As each server is only connected to the respective ToR switch, it is not necessary to represent them in the graph. Nevertheless, they are relevant for the generation of the tra c demands. Each ToR has 2 to 8 uplinks, depending on the size of the network. Each core node is connected to every node in the aggregation tier. Every link has a capacity value of 10 Gbps. For each VLAN, the tra c demands between the core nodes and the servers, or between servers, were calculated using the formula described above. All the tra c demands directed at (originating from) servers belonging to a given rack, are considered to have as a destination (origin) the node representing the corresponding ToR switch. For each class of instances, Trandk 2 Trand, T3ktc 2 T3tc , ve instances were generated and tested. Table 2.2 describes these classes of instances, in terms of number of nodes in the network (#nodes), network density (for Trand only), and number of VLANs in the network (#VLANs). was given a value of 0.1 for every instance in Trand, and of 10 for every instance in T3tc, so that there was a low chance of having infeasible instances
Table of contents :
Acknowledgements
Abstract
Resume
List of Figures
List of Tables
List of Formulations
Glossary
Introduction
1 Background and related work
1.1 An introduction to switching protocols
1.1.1 Data Centers and switched Ethernet networks
1.1.2 Spanning Tree Protocol
1.1.3 Multiple Spanning Tree Protocol
1.2 Review of methods for the MSTP
1.3 Notation and denitions
1.4 MIPs for problems with spanning trees
1.4.1 Minimum spanning tree problem
1.4.2 Optimum communication spanning tree problem
1.5 MIPs for problems with MSTP
1.6 Benders’ decomposition
2 MSTP: minimization of worst-case link utilization
2.1 Problem complexity
2.2 Problem formulation
2.2.1 Sub-problem 1: Designing spanning trees
2.2.2 Sub-problem 2: Routing the trac demands
2.2.3 Sub-problem 3: Edge utilization and capacity constraints .
2.2.4 Objective function
2.2.5 Complete formulations
2.3 Polyhedral comparison of formulations
2.4 Computational experiments
2.4.1 Test sets for the TE-MSTP problem
2.4.2 Analysis of the results of test set Trand
2.4.3 Analysis of the results of test set T3tc
2.5 B&C algorithm
2.5.1 Benders’ decomposition
2.5.2 Computational experiments for the B&C algorithm
2.6 Summary and remarks
3 MSTP: minimization of total load
3.1 Problem formulation
3.2 Computational experiments for the COCMST problem
3.2.1 Analysis of the results for = 0:2
3.2.2 Analysis of the results for = 0:05
3.2.3 Analysis of the results for = 0:01
3.2.4 Using the COCMST problem to nd feasible solutions for the TEMSTP problem
3.2.5 Using the COCMST problem to nd lower bounds for the TEMSTP problem
3.3 Binary search algorithm
3.3.1 Obtaining a rst upper bound
3.3.2 Obtaining a rst lower bound
3.3.3 Obtaining a feasible solution
3.3.4 Local branching
3.3.5 Parameters conguration
3.4 Computational experiments for the BSA
3.5 Summary and remarks
4 Piecewise linear unsplittable multicommodity ow problems
4.1 Problem complexity
4.2 Problem formulation
4.2.1 Basic formulations
4.2.2 Ideal formulation for jKj = 1
4.2.3 Strong formulation for jKj 1
4.3 Computational experiments
4.3.1 Test sets for the PUMF problem
4.3.2 Results for test set T1
4.3.3 Results for test set T2
4.4 B&C algorithm
4.4.1 Benders’ decomposition
4.4.2 Computational experiments for the B&C algorithm
4.5 Strengthened aggregated formulation
4.5.1 Benders’ decomposition II
4.5.2 Valid inequalities for BM1
4.6 Non-convex case
4.7 Summary and remarks
5 MSTP: minimization of piecewise linear ow cost functions
5.1 Problem formulation
5.2 Computational experiments
5.2.1 Analysis of the results of test set Trand
5.2.2 Analysis of the results of test set T3tc
5.3 B&C algorithm
5.3.1 Benders’ decomposition
5.3.2 Computational experiments for the B&C algorithm
5.4 Summary and remarks
6 Conclusion
References
