7.4 Traffic Engineering: A Four-Node Illustration
7.4.2 Shortest Path Routing and Network Flow
In an IP network based on the OSPF or IS-IS protocol, the shortest path is computed based on the link weight (cost or metric) that is exchanged through flooding. It is important to note that this computation does not consider the traffic volume or capacity of the network.
Thus, the general question is: how is shortest path routing related to network flow modeling?
To understand this problem, we consider the four-node problem again, first starting with special cases of capacity illustrated above. We will denote the link weights by the notation w; thus,w1is the link weight for link-id 1 (i.e., link 1-3) ,w2for link-id 2 (i.e., link 3-2), and so on.
Example 7.3 Optimal flow decision with shortest path routing.
Consider again the case in which all links have the same capacity, i.e., 100 Mbps. In this case, the optimal decision from network flow optimization was to split the traffic volume
equally among the two paths. Recall that OSPF allows equal-cost multipath (ECMP) (see Section 6.2.7); thus, if we can pick the link weight in such a way that an equal splitting of traffic can be achieved, we achieve the same optimal flow as network flow optimization. This can be realized if we pick the link weight to be 1 on each link (i.e.,w1=w2=w3=w4=1);
we then achieve this splitting since each path cost is 2 and with ECMP, the traffic volume will be equally split. In other words, a hop-based metric will work in this case.
What if the links are of different size, i.e., 10 Mbps for links 1-3 and 3-2 and 100 Mbps for links 1-4 and 4-2? If we still keep the link weight at 1 each, then of the total traffic volume of 60 Mbps, half will try to use path 1-3-2 due to ECMP. However, the capacity limit on this path is 10 Mbps; that is, a 30 Mbps data traffic on this path will cause massive overflow! This means that we need to use some other link weights so that this does not happen. Essentially, we want traffic flow to veer away from path 1-3-2 since the capacity of this path is much smaller than the other path. A way to accomplish this would be to set the link weight as the inverse of the link capacity, i.e.,
w1=w2=1/10, w3=w4=1/100.
This would imply that the path cost for path 1-3-2 is 2/10 while the path cost for path 1-4-2 is 2/100; thus, all of traffic volume, 60 Mbps, will be allocated to path 1-4-2 since 1-4-2 is the shortest path with this set of link weights. In fact, under shortest path routing this is the best we can do, and the maximum link utilization is60/100=0.6. In other words, it is not possible to achieve the optimality that was achieved with pure network flow optimization
where the optimal flows were proportional flows.
From the above illustration, we can see that link weights is really driving the flow. While it seems thatx11is dependent only on link weightsw1andw2, the actual values of the other link weights w3, w4 do also matter in the allocation of flow to x11; this is similar for x12. That is, flowsx11 and x12 are really dependent on all link weightsw1,w2,w3,w4. If we use w=(w1,w2,w3,w4)to denote the array of link weights for all links, then we can write the dependency asx11(w)andx12(w). Since the total flow needs to be equal to the traffic demand volume, we can write
x11(w)+x12(w)=h1. (7.4.7)
Now compare Eq. (7.4.7) to Eq. (7.4.1); they are almost the same except for the dependency onw. Similarly, the link-flow requirements can be written for dependent flow variables as
x11(w)≤c1, x11(w)≤c2, x12(w)≤c3, x12(w)≤c4. (7.4.8) Again compare Eq. (7.4.8) to Eq. (7.4.2), and note the difference due to dependency onw. In regard to the link weight systemw, there are some restrictions on what values a link metric can take; for example, in OSPF, the range is from1to216−1while in IS-IS the range is from0 to63. While in the above illustration we chose link metric also as the inverse of link speed, we can use a normalization factor to change the link metrics to an acceptable range; for example, if we multiply by 100, then the metric for a link with speed 10 Mbps would be 10 (=100/10) while the metric for a link with speed 100 Mbps would be 1 (=100/100). For simplicity, we
denote the set of allowable values for link metrics asW. Thus, similar to Eq. (7.4.4), we can write the following optimization problem:
minimize{w,r} F=r
subject to x11(w)+x12(w)=h1
x11(w)≤c1r, x11(w)≤c2r, x12(w)≤c3r, x12(w)≤c4r x11(w)≥0, x12(w)≥0 w1,w2,w3,w4∈W.
(7.4.9)
We will refer to the above formulation as the single-commodity shortest path routing–based flow (SCSPRF) problem, to distinguish it from the single-commodity network flow problem presented in Eq. (7.4.4). As noted earlier for Eq. (7.4.4), capacity constraintsx11(w)≤c1randx11(w)≤ c2rcan be combined into a single constraint by considering the smaller of the link capacities c1andc2indicating the tighter constraint; this is similar for the other two capacity constraints.
It is important to note the following observations in regard to Eq. (7.4.4) and Eq. (7.4.9):
• In Eq. (7.4.9), the main variables are link weightswand maximum link utilization,r; flow variablesx(w)are dependent variables while in Eq. (7.4.4), the main variables arexandr.
• If we denote the optimal objective cost for the network flow problem Eq. (7.4.4) byFnetflow∗ , and the optimal objective cost due to shortest path–based flow problem Eq. (7.4.9) byFSPR∗ , then we can write
Fnetflow∗ ≤FSPR∗ . (7.4.10)
Intuitively, we can see this relation since the restriction on flow variables due to the link weight can be thought of as additional restrictions/constraints on the original network flow problem; thus, any additional restrictions can/may increase the optimal cost of the original network flow problem.
In addition, there is an important difference to note. While Eq. (7.4.4) is a linear program- ming problem, Eq. (7.4.9) is not. In addition, Eq. (7.4.9) is not a standard nonlinear program- ming problem due to implicit functional dependency of flows,x, on the link weight systemw.
More importantly, Eq. (7.4.9) cannot be directly solved as we have already noticed. Note that so far, we have used two simple rules for choosing link weights in illustrating Example 7.3.
We start by summarizing these two rules:
Rule-1: Choose the link weights to be based on hop count, to be referred to as a hop-based metric
Rule-2: Choose the link weights to be based on the inverse of the link speed, to be referred to as an inverse-of-the-link speed metric.
We digress a bit further with these two rules in relation to earlier examples by considering certain variations.
Example 7.4 Changing the traffic volume in Example 7.3.
Consider reducing the traffic volume for pair 1:2 from 60 Mbps to 5 Mbps. In this case, we note that even if we use Rule 1 on the link capacity as given in Figure 7.6, we do not face the overflow problem discussed earlier in Example 7.3. This would cause the maximum link utilization to be 0.25 since 2.5 Mbps of traffic volume would be allocated to path 1-3-2 with the remaining 2.5 Mbps allocated to path 1-4-2 due to ECMP. If Rule 2 is used, then all traffic would be allocated to path 1-4-2, and thus, the maximum link utilization in this case is 0.05.
With either rule, we can see that when traffic volume is low compared to network capacity, the utilization remains low.
Now consider the topology with all links being 100 Mbps (Figure 7.5). In this case with 5 Mbps of network traffic, we will arrive at the same maximum link utilization (= 0.025) with
either rule for link weight.
From the above illustration, it is easy to see that if all links in a network are of the same speed, then the link weight based on the inverse-of-the-link speed is the same as the hop- based metric. Thus, Rule 1 can be thought of as a special case of Rule 2. We next consider an example where due to an anticipated increase in network traffic, a new link is added;
this actually falls under the network dimensioning problem. It should be noted that there are systematic ways to address the network dimensioning problem in terms of where to add capacity and if new links should be added; for a detailed discussion, see [564]. Here, we present a simple illustration to address the impact on the link weight selection rules.
Example 7.5 Topology change in anticipation of increase in traffic volume.
Consider the network shown in Figure 7.7. Note that there is one key change from the topology shown in Figure 7.5: a new direct link between node 1 and node 2 is added; we will identify this link as link number 5, and the link weight as w5, while keeping the link numbering for other links as before. Suppose that this link was added in anticipation of an increase in traffic volume. Now we have one more path possible from node 1 to node 2; we label this path as path number 3 with the flow variable labeled asx13. Formulation (7.4.9) will now change to the following:
F I G U R E 7.7 A four-node network example with five links.
minimize{w,r} F=r
subject to x11(w)+x12(w)+x13(w)=60 x11(w)≤100 r
x12(w)≤100 r x13(w)≤100 r
x11(w),x12(w),x13(w)≥0 w1,w2,w3,w4,w5∈W.
(7.4.11)
Note the difference between Eq. (7.4.9) and Eq. (7.4.11). In the latter, specific values of ca- pacity and traffic volumes are shown along with the new path; furthermore, since the link capacities are the same, only a single-capacity constraint is shown for path number 1 and path number 2.
We can easily see that regardless of whether we use Rule 1 or Rule 2, all traffic will be allocated to the direct link path on link number 5 with shortest path routing since the direct link is the shortest path under either rule for the link weight. In this case, the maximum link
utilization isr=60/100=0.6.
From the above illustration, we note that Rule 2 does not always work well since in this instance, by adding a new link, we have syphoned all traffic to take the new link, instead of equally splitting flow allocation among the three paths. This means that we have increased maximum link utilization, thereby increasing average network delay for a traffic volume of 60 Mbps by adding new link/capacity compared to when the direct link did not exist. This is certainly counterintuitive. In road transportation networks, an analogous situation has long been known; it states that under certain load conditions the travel cost can increase with the addition of a new link (road), which is known as Braess’ Paradox ([91], [280], [447]). A phenom- enon similar to Braess’ paradox can be induced in IP networks if link weights are not chosen properly.
Going back to the network shown in Figure 7.7, an important question is: can we choose a better set of link weights that will reduce maximum link utilization compared to when Rule 2 is used, i.e., a better solution to Eq. (7.4.11)? This is possible if we choose the link weights as follows (see Figure 7.8):
w1=w2=w3=w4=1, w5=2.
This way, the path cost for all paths are 2; thus, due to ECMP, traffic volume will be equally split among the three paths, thereby reducing maximum link utilization, r, to 0.2
F I G U R E 7.8 A four-node network example with link weights.
from 0.6. In fact, this set of link weights is optimal for the SCSPRF problem, Eq. (7.4.11).
It should be noted that the optimal link weights are not unique; for example, if we choose
w1=w2=w3=w4=2, w5=4,
it will result in the same optimal maximum link utilization value,r∗=0.2.
While for Eq. (7.4.11), we have found an optimal set of link weights by inspecting the data for the problem, this is not always easy, especially for a large network problem. In the next sections, we discuss the general problem and possible solutions.