Abstract

In the multiple protocol label-switched (MPLS) networks, the commodities are transmitted by the label-switched paths (LSPs). For the sake of reducing the total cost and strengthening the central management, the MPLS networks restrict the number of paths that a commodity can use, for maintaining the quality of service (QoS) of the users, the demand of each commodity must be satisfied. Under the above conditions, some links in the network may be too much loaded, affecting the performance of the whole network drastically. For this problem, in [1] , we proposed two mathematical models to describe it and a heuristic algorithm which quickly finds transmitting paths for each commodity are also presented. In this paper, we propose a new heuristic algorithm which finds a feasible path set for each commodity, and then select some paths from the path set through a mixed integer linear programming to transmit the demand of each commodity. This strategy reduces the scale of the original problem to a large extent. We test 50 instances and the results show the effectiveness of the new heuristic algorithm.

Keywords:MPLS-Network, k-Splittable Flow, Minimum Congestion, Heuristic Algorithm

References

2. Problem Description and Mathematical Models

We describe the problem in a more general case. In the minimum congestion k-splittable multi-commodity flow problem, a directed graph is given with and, with arc capacities,. A set of commodities is denoted by, each commodity has a certain amount of demand to transmit, a source node and a destination node, and the number of paths that commodity can use. The goal is to find a flow that satisfies all demands of the commodities and minimize the congestion: Find the smallest such that there exists a feasible flow satisfying the demands and the path restrictions if all capacities are multiplied by. In [1] , we first propose two different mathematical models, namely the arc-path and arc-flow model. In this paper, we also use the two models to describe our problem.

2.1. The Arc-Path Model

Let denotes the set of all paths of commodity, denotes the flow value on path of commodity, denoting whether or not path is used by commodity. denotes the maximum flow value that path can transmit.

This problem is formulated as follows:

(1)

(2)

(3)

(4)

(5)

(6)

(7)

The objective function is to minimize the factor that each edge can multiply. The first constraints (1) ensure that the flow value on an edge is at most of its capacity, is a constant, if, , otherwise. The constraints (2) ensure that each commodity's demand is satisfied, and constraints (3) indicate that only path is used by commodity, that is, the flow value can be non-negative. The notation is any upper bound of the objective value, which can be selected by with. Constraints (4) limit the number of paths that a commodity can use. Constraints (5)-(7) force the variables to take on feasible values.

2.2. The Arc-Flow Model

The variable refers to the flow value of the -th path of commodity on edge, , and binary variable denotes whether or not edge is used by the -th path of commodity. We use and to denote the outgoing arcs and ingoing arcs of node, respectively. Then the arc-flow model is stated as follows:

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

Constraints (8) ensure that each commodity’s demand is satisfied, and constraints (9) ensure the flow on each edge is at most times of its capacity, constraints (10) indicate that only if edge is used by the -th path of commodity can the variable be positive. Constraints (11) are the flow conservation constraints and (12) are used to prevent cycles connecting to the -th path of commodity for each,. Constraints (13)-(15) force the variables to take on feasible values.

The main difference of the two mathematical models is that in the arc-path model each commodity has a feasible path set which contains all the paths for the commodity in the network and we only need to select some paths from the path set to transmit the demand. Sometimes, determining all the feasible paths for a commodity is not an easy thing. While in the arc-flow model, the transmitting paths for each commodity are found in the network directly. We know that both of the above two formulations are mixed integer linear problems which are NP-hard to solve, especially when the size of the network increases, the number of paths in grows exponentially, and it is impossible to obtain the exact solutions in short time.

We also note that the multi-source k-splittable problem cannot equally transform to the single-source k-splittable problem. If we add a super source node, connecting it to each source node for, each edge has capacity, then a feasible flow in the new graph with flow value may not transform to a feasible flow satisfying all demands in the original graph. For example, a graph with five nodes, five edges with capacities 1, 4, 4, 4, 4, respectively. Two commodities with endpoints and have demands 5 and 4, respectively. We add a super source node as mentioned above and a super sink node. Add two edges and with capacity 5 and 4, respectively. Applying a maximum flow algorithm, such as the Edmonds-Karp Algorithm in [12] , we obtain a maximum flow from to and edge flow values are as follows:, , , , , , , and. We can note that cannot transform to a flow in the original graph that satisfies the two commodities, since in there is no path with positive flow value from to and the flow value from to is only 1.

In this paper, for simplicity, we only consider the single-source multi-commodity k-splittable flow problem, denote the common source node by. We propose a heuristic algorithm which largely reduce the size of the path set for each commodity to a small path set, and solve the arc-path model with replaced by for.

3. The Heuristic Algorithm

In this paper, we assume that there is a feasible splittable flow that satisfies all the demands of the commodities. We know that may not meet all the path number restrictions of the commodities. In [1] , we find at most paths for commodity from, and then reallocate flow to the unsatisfied commodities by solving a series of linear programming. In this paper, we also find paths for commodity from. On the one hand, we finds paths for each commodity until the total path value is equal to its demand, on the other hand, for sake of fairness of different commodities, we find at most one path for each commodity in a round. The steps of the algorithm are as follows and the flow chart of the algorithm is presented in Figure 1.

Step 1: Find a feasible splittable flow in that satisfies all the demands; Initialize for all, denoting the paths found from for commodity;

Step 2: For, if the total path value of the paths in is less than, find a path from the current flow for commodity that carry the largest flow value. Add the new path with its flow value to. Once a path is found, delete its flow from, update the edge flow values in;

Step 3: If there is some edge in with positive flow value, go to step 2; otherwise, solve the arc-path model

with replaced by.

Remarks:

● In step 1, we can add a super sink node to, each sink node, is connected to with capacity, denote the new graph by. Finding that satisfies all the demands of the commodities is equivalent to find the maximum flow in, since we assume the existence of, the maximum flow in is with flow value and we can use any maximum flow algorithm to obtain the maximum flow.

● For each commodity, the number of paths found is at most and so the size of is largely smaller than. Since the existence of a feasible splittable flow satisfying all demands, at the end of step 2 we have that and the total path value of is for each.

● The new algorithm applies the Round Robin strategy to find paths. In each round, each commodity finds at most one path in the current flow, this strategy guarantees some fairness in certain degree. To show the effectiveness of the Round Robin strategy, we compare our algorithm to the one that does not use the strategy in the next section. The computational results show that this strategy does have some advantages for this problem.

4. Computational Results

The testing instances are generated by the Transit Grid generator developed by G.Waissi [13] . The topology of those instances (see Table 1) looks close to the transportation networks and may be well-suited for the MPLS networks. In this paper, we propose some results for the multi-commodity case. Tests were performed on an Intel Core 2.4 GHz processor, 4 GB of RAM. We use CPLEX 12.5.1 to solve the arc-flow model. The running time of the CPLEX-solver is restricted to 50 seconds for each instance. The testing results are reported on Table 2 and Table3

In our testing, the total demands of the commodities in each instance are taken as the largest. While in practice, the demand of each commodity may be much less than the amount we take, hence the congestions we obtained may be larger than 1. For simplicity, we denote the algorithm in [1] by H1. In this section, we also compare our algorithm to the one that not using the Round Robin strategy. That is the one which find paths from for each commodity until the total path values is its demand, and then go to the next commodity, denote the algorithm by H2. The new algorithm proposed in this paper is denoted by H3. In Table 2, for each instance name, the first column followed is the number of commodities, and then followed the number of paths each commodity can use, and the next four columns are the congestions obtained by H1, H2, H3 and the CPLEX-solver in 50 seconds, and the last three columns followed are the ratios between the congestions of each of the three heuristic algorithms and the CPLEX-solver for each instance. The empty positions in Table 2 and Table 3 are because of the size of the instance runs out of memory, and hence no results are given. In Table 3, the last four columns are the corresponding running times for each instance.

From Table 3, we can note that the time spent for H1, H2 and H3 has little differences, all of the three heuristic algorithms run faster than the CPLEX-solver, and when the size of the instance or the number of paths that a commodity can use increases, the time spent for the CPLEX-solver has a big fluctuation, and most of the instances cannot obtain the exact solutions in the given time, we list the congestions obtained by the CPLEXsolver in 50 seconds. From column 4 and column 6 in Table 2, we can see that in the 50 test instances, 64% of the congestion values obtained by H3 is less than H1, and 30% have the same congestion values, and H1 has only 6% of the 50 congestion values that is less than H3. From column 5 and column 6 in Table 2, we note that 34% of the congestion values obtained by H3 are less than H2, and only 16% of the congestion values obtained by H2 are less than H3, this shows that the Round Robin strategy is useful in the heuristic algorithm. From the last three columns of Table 2, we can note that for all the 40 sets of gaps, H1 has 24 instances that have gaps less than or equal to 1.5, while H3 has 31 instances with this property and H2 has 30. We can also note that H1 has 5 instances with gaps larger than 2 and H2 has 2 instances with this property, while H3 has no instance with gaps larger than 2. Hence we conclude that the performance of H3 outperforms H1 and H2. We know that increasing the size of path set for each commodity can minimize the congestion, but too large path set may also increasing the running time. So how to find paths for each commodity efficiently is a big challenge for this problem.

5. Conclusion

In this paper, we consider the problem of minimizing congestion in the MPLS networks. We propose a new heuristic algorithm. This algorithm is based on the strategy that reduces the whole feasible path set for each commodity, and a Round Robin strategy is also used. The computational results show that the new algorithm is

much better than the algorithm that we proposed before. One main limitation of the new algorithm is that it needs to solve a mixed integer linear programming, when the number of commodities is sufficiently large, the running time of the algorithm may be large. However, the idea of the algorithm provides a good feasible direction for solving this problem. In the future, we will continue to do research on how to find better feasible path set for each commodity, not only this, we will design effective strategies to solve the mixed integer linear programming more quickly.

Acknowledgements

The work is supported by the National Natural Science Foundation of China under Grant No. 71171189, the key project of the National Natural Science Foundation under Grant No. 11331012 and the national key basic research development plan (973 Plan) project under Grant No. 2011CB706901.

References

NOTES

^*Corresponding author.