11.3. Routing with Simple Constraints
The shortest path algorithms described above allow us to select an optimal path based on a set of chosen link weights. We can combine the shortest path technique with a simple graph pruning approach to include certain classes of constraints. In general, this approach is applicable when specific nodes or links can be excluded from the path based on their attributes. This is illustrated in the following examples.
11.3.1. Link Protection Constraints Example
Consider the network shown in Figure 11-2, where each link is assigned a cost and unprotected links are indicated by dashed lines. The shortest path from NE 1 to NE 7, regardless of individual link protection capabilities, is (NE 1, NE 3, NE 6, NE 7), as shown.
Figure 11-2. Network Graph with Unprotected Links Indicated by Dashed Lines
If, however, it is desired that a path be found from NE 1 to NE 7 that only traverses protected links, then the unprotected links must first be pruned from the graph. This pruned network graph is shown in Figure 11-3 along with the new least cost protected path from NE 1 to NE 7, that is, the path (NE 1, NE 2, NE 4, NE 7).
Figure 11-3. Graph after Pruning the Unprotected Links in Figure 11-2
11.3.2. Bandwidth Constraints
Consider the network shown in Figure 11-4, consisting of OC-192 links. There is initially no traffic in this network. Suppose that at time t0, a request is received to establish an STS-1 connection from NE 1 to NE 7. Based on the economic link costs, the shortest path is computed as (NE 1, NE 3, NE 6, NE 7). Hence, after routing this connection, the links (NE 1, NE 3), (NE 3, NE 6), and (NE 6, NE 7) carry an STS-1 signal and they have room for 191 additional STS-1s.
Figure 11-4. An OC-192 Mesh Network with Initially No Traffic
Now suppose at a later time t1, another request is received to establish an STS-192c connection from NE 1 to NE 7. This signal needs 192 STS-1 slots and hence any link that cannot support it should be pruned from the network graph. In particular, the links that are carrying the STS-1 that were set up at time t0 must be pruned. The pruned network graph is shown in Figure 11-5 along with the optimal path computed for the STS-192c connection, that is, (NE 1, NE 2, NE 4, NE 7).
Figure 11-5. Network of Figure 11-4 with All Links that Cannot Support an STS-192c Removed
Let us now examine the total cost to the network provider of supporting these two signals. The STS-1 path has a total cost of 6, obtained by adding the link weights along the path, whereas the STS-192c path has a total cost of 8. If we consider the total cost times bandwidth, we have (6 cost units)*(1 STS) + (8 cost units)*(192 STS) = 1542 (cost units*STS). Now suppose that the connection requests came in the opposite order, that is, the STS-192c and the STS-1 requests were received at time t0 and t1, respectively. It then turns out that the STS-192c will be routed over the path (NE 1, NE 3, NE 6, NE 7), and the STS-1 will be routed over the path (NE 1, NE 2, NE 4, NE 7). In this case, the total cost times bandwidth product will be (6 cost units)*(192 STS) + (8 cost units)*(1 STS) = 1160. Hence, the order in which connections are established can be important to the overall economic efficiency of the network.