11.5. Network Optimization
The next level of generalization comes when we consider one of the following:
Concurrent routing of multiple connection requests between different sources and destinations in some “optimal” fashion.
Optimization of some measure while simultaneously ensuring that a minimum acceptable quantity of another measure is satisfied.
A combination of the previous two.
As an example of case 2, consider an optimization to find the least cost path based on economic link weights while simultaneously ensuring that the path has a failure probability below a given threshold (based on the individual link failure probabilities). To see why case 1 is important, consider the following example illustrated in Figure 11-14. This figure depicts a network consisting of OC-192 links interconnected via switching nodes or ADMs. Assume that the network is not carrying any traffic initially, and that the following requests for STS-192c connections are received subsequently in the order shown:
1: from NE2 to NE3,
2: from NE1 to NE4,
3: from NE3 to NE4, and
4: from NE4 to NE5.
Figure 11-14. Network of OC-192 Links Supporting Only 2 of 4 STS-192c Connection Requests
Suppose that each of these connections have be routed over the shortest path, that is, we want to optimize the placement of connections in some respect. Unfortunately, due to the scarcity of bandwidth, setting up the first connection (from NE2 to NE3) over the shortest path prevents the establishment of the second connection (from NE1 to NE4). In addition, the third connection request (from NE3 to NE4) being accepted prevents the fourth (from NE4 to NE5) from being satisfied. Hence, only half of the STS-192c connection requests can be satisfied. Could things have been different? Yes.
Figure 11-15 depicts the result of successive shortest path placements if the connection requests are received in the following order: (from NE 4 to NE 5), (from NE 1 to NE 4), (from NE 2 to NE 3) and (from NE 3 to NE 4). In this case, all the connections are successfully routed.
Figure 11-15. Network of Figure 11-14 with STS-192c Connection Requests Arriving in a Different Order
It is seen from this example that if connections are routed along the shortest path independently of each other, then the order in which a set of connection requests are processed could determine the number of requests that are satisfied. When connection requests are received over a long period of time, it may be necessary to reoptimize connection routing to maximize the number of accepted connections [Bouillet+02b]. Reoptimization means that existing connections are periodically reordered and rerouted to optimize network utilization. Reoptimization requires more sophisticated techniques than the shortest path schemes discussed so far.
11.5.1. Batch Processing
The placement of multiple connections concurrently requires the application of certain optimization techniques. In this regard, the optimization problem to be solved can be expressed in standard mathematical language. In general, the problem consists of maximizing or minimizing some function of several variables subject to a number of constraints on those variables. Such a problem is usually called a mathematical programming problem, and there is a great deal of work devoted to various classes of these problems and their solutions. Before describing the general batch processing approach, we first return to the shortest path problem and show how to formulate the mathematical equations describing it.
11.5.2. Shortest Path: Mathematical Formulation
Given a directed graph with link weights ai,j, let xi,j denote the amount of flow on link (i, j) from node i to node j. The first set of constraint equations capture the requirement that the flow variables are non-negative, that is.,
Equation 1
With this assumption, we are interested in minimizing the following function:
Equation 2
At the source node, we have:
Equation 3
where bs is the amount of flow entering the network at the source node. This simply indicates that the traffic from the source to the destination enters at the source node and it is equal to bs. In the case of the shortest path problem, bs =1. Similarly, at the destination node, the net outflow from the node is given by:
Equation 4
Finally at intermediate nodes, i, we have:
Equation 5
This equation just indicates that at intermediate nodes there is no loss or gain of flow. Equations (3-5) are called node balance equations.
For example, considering the network shown in Figure 11-1, there are 13 links and 7 nodes. Hence, with the above formulation, a linear equation in 13 variables subject to 20 constraint equations (13 non-negativity constraints and the 7 node balance equations) has to be mimimized. Given the efficiency of Bellman-Ford and the Dijkstra algorithms, it is little wonder that this non-graph-oriented approach is never used for finding individual shortest paths.
11.5.3. Multicommodity Flow: Mathematical Formulation
Now, let us consider the case where a batch of connections has to be set up between various source and destination pairs. Since each connection is unique between a given source-destination pair, it can be considered as a separate “commodity” in our model. Hence, we will deal with the flow variables xi,j (k,m) where (i,j) ∊ A, ranges over the links in the network and (k,m) ranges over all the source-destination pairs. As before, the non-negativity constraint is
Equation 6
And, the set of N (source, destination) node balance constraint equations are
Equation 7
Equation 8
Equation 9
To make it easier to keep track of constraints and the minimization function, we introduce the flow variable, (i,j), yi,j. for each link (i, j). This is related to the xi,j(k,m) variables as follows:
Equation 10
The bandwidth constraints for the links can be written as
Equation 11
and the function to be minimized is then
Equation 12
If the signals and links are bidirectional, then we will also have the additional symmetry constraints
Equation 13
As an example, consider the network depicted in Figure 11-14. This network has 7 bidirectional links (SONET OC-192), which have to be formulated as 14 unidirectional links in the above equations. There are 4 bidirectional (source, destination) connection pairs, or 8 unidirectional (source, destination) pairs. Thus, there are a total of 112 flow variables. There are also 14 link constraint equations and 40 node balance equations. This formulation is quite impractical to solve by hand. The approach, clearly, should be to automate the solution procedure as described next.
11.5.4. Formulating and Solving Multicommodity Optimizations
In the previous section, the batch path computation problem was formulated in terms of a mathematical programming problem. It was seen that even with a small network consisting of a small number of source-destination pairs, this formulation could produce too many equations and variables to be amenable to manual solution. In general, there are two main parts to solving these problems: (1) setting up the equations, and (2) solving the resulting optimization problem based on these equations.
Descriptions of techniques for solving optimization problems such as these can be found in many books on linear programming [Chvátal83]. A fairly sophisticated and thorough coverage of algorithms is given in [Bertsekas98]. We will therefore not attempt to cover any of this material here.[1]
[1] It should be noted that the linear programming problems mentioned here are actually integer linear programs since the variables can only assume integer values.
In a reasonably sized, multicommodity network problem, it would not be unusual to deal with tens to hundreds or thousands of variables and equations. Hence, generating these equations can be somewhat tricky. Although custom software can be written to do this, special purpose languages can make the job significantly easier and quicker.[2] As an example, the following program, coded in the language AMPL [Fourer+93], formulates the multicommodity flow equations (6-13).
[2] Easier after the “learning curve” of yet another computer language has been scaled.
In this program, the network-specific information and connection demands have been separated from the general model formulation. First, the fundamental variables are defined, that is, the set of NODES (line 3), the set of source-destination pairs, SD_PAIRS, (line 6), and the set of LINKS (line 12). The specific values that these variables will assume are taken from a separate data file. Next, the “demand” parameters for each source destination pair (line 8) are defined. These are the bi,j variables in equations 7 and 8. The flow variables in line 18 are just the xi,j(k,m) parameters of equation 6. The link weights have been named usage_cost and are defined on line 32. The values for these are specified in a separate data file. In this example, the total usage cost of the network is being minimized (see lines 34 and 35). Finally, the node balance equations and link capacity constraint equations are given in lines 36–49. Comments start with '#'.
1 # The nodes in the network will be listed in a data
2 # file.
3 set NODES;
4 # The set of source-destination pair traffic demand to
5 # be routed
6 set SD_PAIRS within {NODES, NODES};
7 # The traffic demand between the source and destination
8 param demand {SD_PAIRS};
9 check {(s,d) in SD_PAIRS }: demand[s,d] = demand[d,s];
10 # The set of unidirectional links. This must be a sym-
11 # metric set.
12 set LINKS within {NODES, NODES};
13 check {(i,j) in LINKS }: ( (j,i) in LINKS);
14 #(i,j) in LINKS and
15 # The set of flow variables, i.e., the amount of traf-
16 # fic on a particular link dedicated to a particular
17 # source-destination communication path.
18 var flow {LINKS, SD_PAIRS}>=0;
19 # Bi-directional constraint, the flow between s and d
20 # over link (i,j) must be the same as the flow between
21 # d and s over link (j,i).
22 subject to Bidirectional {(s,d)in SD_PAIRS, (i,j) in LINKS }:
23 flow[i,j,s,d] = flow[j,i,d,s];
24 var total_flow {LINKS} >= 0;
25 # Total flow variable is just the flow over the link.
26 subject to TotalFlow { (i, j) in LINKS }:
27 total_flow[i,j] = sum { (s, d) in SD_PAIRS }
28 flow[i,j,s,d];
29 # Minimize over the sum of all flows:
30 param usage_cost{LINKS} >= 0;
31 # Normal cost of using the link
32 param link_size > 0;
33 # Size of the links, e.g., 48 for OC-48
34 minimize UsageCost: sum {(i,j) in LINKS}
35 usage_cost[i,j]*total_flow[i,j];
36 # Node balance equations. These are needed at every
37 # node for every source-destination pair.
38 Subject to BalanceNull {n in NODES, (s,d) in SD_PAIRS:
39 s<>n and d<>n }:
40 sum {(n, i) in LINKS} flow[n,i,s,d] - sum {(i,n) in
41 LINKS} flow[i,n,s,d] = 0;
42 subject to BalanceSource {n in NODES, (n,d) in SD_PAIRS}:
43 sum {(n, i) in LINKS} flow[n,i,n,d] - sum {(i,n) in
44 LINKS} flow[i,n,n,d] = demand[n,d];
45 subject to BalanceDest {n in NODES, (s, n) in SD_PAIRS}:
46 sum {(n, i) in LINKS} flow[n,i,s,n] - sum {(i,n) in
47 LINKS} flow[i,n,s,n] = -demand[s,n];
48 subject to LinkConstraint {(i, j) in LINKS }:
49 total_flow[i,j] <= link_size;
The next AMPL code segment describes the network of Figure 11-14, along with demands for two (bidirectional) connections, one from NE 2 to NE 3 and the other from NE3 to NE 4.
set NODES := N1 N2 N3 N4 N5; set SD_PAIRS := (N2, N3) (N3, N2) (N3, N4) (N4, N3) ; set LINKS := (N1, N2) (N2, N1) (N1, N3) (N3, N1) (N2, N3) (N3, N2) (N2, N4) (N4, N2) (N3,N4) (N4, N3) (N3, N5) (N5, N3) (N4, N5) (N5, N4); param demand := N2 N3 192 N3 N2 192 N3 N4 192 N4 N3 192; param usage_cost := N1 N2 1 N2 N1 1 N1 N3 1 N3 N1 1 N2 N3 3 N3 N2 3 N2 N4 2 N4 N2 2 N3 N4 3 N4 N3 3 N3 N5 1 N5 N3 1 N4 N5 1 N5 N4 1; param link_size = 192;
The following code sample shows the results of running the network flow model and the above data through AMPL and a solver/optimizer called MINOS 5.5. The results are displayed in terms of the links involved with a particular source destination flow. The display is in the form of a matrix in which the row Ni and column Nj define the link (NE i, NE j). For example, for the NE 2 to NE 3 connection, the links (NE 1, NE 2) and (NE 1, NE 3) are used while for the NE3 to NE4 connection, links (NE 3, NE 5) and (NE 4, NE 5) are used. Note that these are the paths shown in Figure 11-14.
ampl: model c:GregdesignMpsfifth.mod; ampl: data c:GregdesignMpsfourth.dat; ampl: solve; MINOS 5.5: optimal solution found. 8 iterations, objective 1536 ampl: display flow; flow [*,*,N2,N3] : N1 N2 N3 N4 N5 := N1 . 0 192 . . N2 192 . 0 0 . N3 0 0 . 0 0 N4 . 0 0 . 0 N5 . . 0 0 . [*,*,N3,N4] : N1 N2 N3 N4 N5 := N1 . 0 0 . . N2 0 . 0 0 . N3 0 0 . 0 192 N4 . 0 0 . 0 N5 . . 0 192 .
The results obtained in the previous example were not all that surprising. In particular, since the two connection requests did not interfere with each other, these results correspond to running a shortest path algorithm twice. Now, suppose that all four connection requests shown in Figure 11-14 are presented together. The following code shows the network model with the demands enlarged to include four bidirectional connections requests.
set NODES := N1 N2 N3 N4 N5; set SD_PAIRS := (N1,N4) (N4, N1) (N2, N3) (N3, N2) (N3, N4) (N4, N3) (N4, N5) (N5, N4); set LINKS := (N1, N2) (N2, N1) (N1, N3) (N3, N1) (N2, N3) (N3, N2) (N2, N4) (N4, N2) (N3,
The results of running the network flow model with the above data through AMPL and a solver are shown below. As before, the matrices display the flow on the links corresponding to each connection.
ampl: model c:GregdesignMpsfifth.mod; ampl: data c:GregdesignMpsfourth2.dat; ampl: solve; MINOS 5.5: optimal solution found. 16 iterations, objective 3840 ampl: display flow; flow [*,*,N1,N4] : N1 N2 N3 N4 N5 := N1 . 192 0 . . N2 0 . 0 192 . N3 0 0 . 0 0 N4 . 0 0 . 0 N5 . . 0 0 . [*,*,N2,N3] : N1 N2 N3 N4 N5 := N1 . 0 0 . . N2 0 . 192 0 . N3 0 0 . 0 0 N4 . 0 0 . 0 N5 . . 0 0 . [*,*,N3,N4] : N1 N2 N3 N4 N5 := N1 . 0 0 . . N2 0 . 0 0 . N3 0 0 . 192 0 N4 . 0 0 . 0 N5 . . 0 0 0 [*,*,N4,N5] : N1 N2 N3 N4 N5 := N1 . 0 0 . . N2 0 . 0 0 . N3 0 0 . 0 0 N4 . 0 0 . 192 N5 . . 0 0 .
From this, we see that the connection from NE 4 to NE 5 is supported by the link, (NE 4, NE 5); the connection from NE 3 to NE 4 is supported by the link, (NE 3, NE 4); the connection from NE 1 to NE 4 is supported by links (NE 2, NE 4) and (NE 1, NE 2); and the connection from NE 2 to NE 3 is supported by the link (NE 2, NE 3). Note that this solution is the same as that shown in Figure 11-15, which was obtained using a different ordering of the connection requests into a shortest path algorithm. Changing the order of connection requests into a shortest path algorithm, however, is in general not a useful way to find an optimal solution. This is because the number of permutations of the ordering grows exponentially, that is, as N!, where N is the number of connection requests.
Although the last example involves 112 flow variables, 14 link constraint equations and 40 node balance equations, it would only take a second or less to run on a typical desktop PC. This is partly due to the fact that the equations generated for realistic networks tend to be rather sparse, that is, they contain mostly zero entries. This reflects the fact that the average degree of a node in a network graph, that is, the number of links connected to the node, tends to be much less than the number of nodes in the network. Another aspect of the problem, as formulated in equations (6)-(13), is that it only involves linear functions and linear constraints of real valued variables. The sparseness, combined with the linearity of these equations, allows for extremely efficient numerical solution via linear programming methods and sparse matrix techniques.