Offline Strategic TE Design

The online strategic discussion covered a lot of things that are inherent to either full-mesh architecture. But the online strategic architecture is not very good at a few things that the offline strategic architecture can handle better.

The most important thing to consider is what's known as the packing problem. A packing problem is a type of problem that deals with optimal use of resources. It's worth spending some serious time on this next section if you don't understand it at first pass, because you need to understand the impact this problem has on your network.

Packing Problem

Consider the two links between the two LSRs shown in Figure 9-9. Each link is an OC-3, with a maximum of 150 Mbps of reservable bandwidth. Link 1 has an available bandwidth of 60 Mbps (90 Mbps has already been reserved), and Link 2 has an available bandwidth of 40 Mbps (110 Mbps has already been reserved). Both links have the same IGP cost.

Two tunnels that need to be placed want to get from Router A to Router D. Tunnel1 wants 60 Mbps of bandwidth; Tunnel2 wants 40 Mbps. What happens?

If Tunnel1 comes up first, all is well. Tunnel1 consumes all 60 of the 60 Mbps on Link 1, and Tunnel2 goes to the only other place it can—Link 2. At this point, both links are 100 percent fully reserved, and both LSPs are happy.

However, if Tunnel2 comes up first, it consumes 40 Mbps of the 60 Mbps on Link 1, leaving Link 1 with 20 Mbps of capacity and Link 2 with 40 Mbps. So where does Tunnel1 go? It can't fit on either of these links. If these links are the only way Tunnel1 can get to its destination, Tunnel1 won't come up.

The problem here is that one of the tiebreakers to decide where to place an LSP is to pick the link with the maximum amount of bandwidth available (see Chapter 4). This is often known as max-fill LSP placement. It refers to the tiebreaker of finding the link that has the maximum possible bandwidth.

So one possible fix for this problem is to try to place LSPs on links that have the least amount of available bandwidth; this is min-fill. Cisco IOS Software doesn't allow you to select anything other than max-fill for LSP placement, but as you'll see, min-fill isn't really any better than max-fill.

If you did this for the situation just described, all would be happy. The 40-Mbps LSP would place itself on the 40-Mbps link, and the 60-Mbps LSP would place itself on the 60-Mbps link, regardless of order.

But min-fill doesn't solve all problems.

Assume that the network topology is slightly more complicated and has two links but three LSPs. These LSPs want bandwidth of 20, 30, and 40 Mbps, respectively. Table 9-12 examines min-fill and max-fill algorithms for the different orders tunnels can come up in.

There are six (3 factorial, or 3 * 2 * 1) different orders in which the tunnels can attempt to come up, and two algorithms to try with each order.

The notation used here is as follows:

• min (20,30,40)— Placing LSPs in the order 20, 30, 40, using the min-fill algorithm

• {40,60}— The amount of bandwidth available on each link

• {F}— Failure. None of the three LSPs could be successfully placed

Table 9-12. min-fill and max-fill Algorithms for the Different Orders in Which Tunnels Can Appear

	Start	After the First LSP Is Placed	After the Second LSP Is Placed	After the Third LSP Is Placed
min (20,30,40)	{40,60}	{20,60}	{20,30}	{F}
max (20,30,40)	{40,60}	{40,40}	{10,40}	{10,0}
min (20,40,30)	{40,60}	{20,60}	{20,20}	{F}
max (20,40,30)	{40,60}	{40,40}	{0,40}	{0,10}
min (30,20,40)	{40,60}	{10,60}	{10,40}	{10,0}
max (30,20,40)	{40,60}	{40,30}	{20,30}	{F}
min (30,40,20)	{40,60}	{10,60}	{10,20}	{10,0}
max (30,40,20)	{40,60}	{40,30}	{0,30}	{0,10}
min (40,20,30)	{40,60}	{0,60}	{0,40}	{0,10}
max (40,20,30)	{40,60}	{40,20}	{20,20}	{F}
min (40,30,20)	{40,60}	{0,60}	{0,30}	{0,10}
max (40,30,20)	{40,60}	{40,20}	{10,20}	{10,0}

Stare at this table for a moment. The following facts should become obvious:

• There are two orders for which min-fill works and max-fill doesn't.

• There are two orders for which max-fill works and min-fill doesn't.

• There are two orders for which both max-fill and min-fill work.

In every case, either min-fill or max-fill can find a solution to the problem and successfully place the LSPs. However, for tunnels coming up in different orders, sometimes min-fill works, and sometimes max-fill works.

What you haven't seen yet is that it's possible that LSPs can come up in an order in which neither max-fill nor min-fill works, but those same LSPs could be placed successfully with either algorithm if the LSPs came up in just the right order.

Consider a still more complicated example—links of capacity 66 and 75, and LSPs of size 21, 22, 23, 24, 25, and 26. It's clear that if you placed these LSPs by hand, they could be placed so that all LSPs fit on all links. In fact, there are 36 factorial (3)² possible ways that these could be placed by hand and still work.

There are 1440 possible outcomes here (6! permutations of LSPs times 2 placement algorithms). For brevity, they are not all listed, but the following tables show three possible outcomes:

• Table 9-13 shows the results when a min-fill algorithm works but max-fill fails.

• Table 9-14 shows the results when max-fill works but min-fill fails.

• Table 9-15 shows the results when neither min-fill nor max-fill works.

Table 9-13. min-fill Works, But max-fill Fails

LSPs Placed in This Order	0	21	22	23	24	25	26
min-fill	{66,75}	{45,75}	{23,75}	{0,75}	{0,51}	{0,26}	{0,0}
max-fill	{66,75}	{66,54}	{44,54}	{44,31}	{20,31}	{20,6}	{F}

Table 9-14. max-fill Works, But min-fill Fails

LSPs Placed in This Order	0	26	23	25	22	24	21
min-fill	{66,75}	{40,75}	{17,75}	{17,50}	{17,28}	{17,4}	{F}
max-fill	{66,75}	{66,49}	{43,49}	{43,24}	{21,24}	{21,0}	{0,0}

Table 9-15. Both min-fill and max-fill Fail

LSPs Placed in This Order	0	26	25	24	23	22	21
min-fill	{66,75}	{40,75}	{15,75}	{15,50}	{15,27}	{15,6}	{F}
max-fill	{66,75}	{66,49}	{41,49}	{41,24}	{18,24}	{18,2}	{F}

As you can see, min-fill and max-fill can't guarantee a solution to this packing problem. To work around this problem, you can use a few techniques:

• Use tunnel priority to give larger trunks better priority. The idea here is to divide your tunnel bandwidths into four or five bands, grouped by size. Maybe 0 to 50-Mbps tunnels go in one band, 51 to 150-Mbps in another, 151 to 500-Mbps in another, and 501-Mbps+ in another.

  Give the larger tunnels a better (that is, lower) setup and holding priority with the command tunnel mpls traffic-eng priority. This means that bandwidth-hungry LSPs will push smaller LSPs out of the way, and these smaller LSPs will then coalesce around the larger ones. See Chapter 3, "Information Distribution," for information on the mechanics of tunnel priority.

• The packing problem gets worse as your LSPs get larger. The larger your LSPs are relative to the size of your links, the more likely you are to waste bandwidth. If you have a 100 Mb link and four LSPs of 30 Mb, you can place only three of them across that link, and you have 10 Mb of unused bandwidth. If you have two 60 Mb LSPs instead, you can place only one of them, leaving 40 Mb wasted. Consider making it a rule not to have any LSPs that are more than a fixed percentage of the minimum link size they might cross. If this rule means that you never have any LSPs of more than 300 Mbps in your network, for example, and you need 500 Mbps of LSP bandwidth from one router to another, build two LSPs. It's up to you whether you build them both as 250 Mbps, or one as 300 Mbps and one as 200 Mbps. As long as you fit within CEF's load-balancing rules (see Chapter 5), you're OK.

• Use an offline tool to find the paths your LSPs should take. This is the most efficient solution in terms of network utilization. It's also the most complicated. Not everybody buys into this approach, because it involves an external box that builds your network for you. But even those who don't use external path placement tools agree that external placement is more efficient than having the headend place each LSP.

Using an Offline Tool for LSP Placement

An offline tool can do a much better job of placing LSPs than a router can. Why? Because whereas a router is aware of what traffic requirements its tunnels have, an offline tool is aware of the traffic requirements of all LSPs. For example, consider the packing problem just discussed with LSPs of {21, 22, 23, 24, 25, 26}. None of those LSPs are aware of the others, so you've got a good chance of ending up with suboptimal LSP placement. It comes down to a race condition. If things happen in just the right order, you'll be OK. It helps to divide LSPs into bands (the first of the three options mentioned in the preceding section), but you can still get into contention within a band. In fact, if you follow the suggestion of having a priority band for tunnels of bandwidth 0 to 50, you haven't changed anything for the LSPs in the preceding examples.

An offline tool, which knows all the demands in all the LSPs, can come up with a more efficient method of placing LSPs. However, an offline tool has to deal with a specific type of problem known as a bin-packing problem. Bin-packing problems are known to be NP-complete (if you're not a mathematician, NP-complete means "really, really hard"), but you can come up with alternative approaches involving specific heuristics that make an offline tool better at placing LSPs than can be done by having the routers calculate their own LSP paths.

Discussing the specifics of offline tools and their capabilities would take another chapter. Or book. Or several. You should contact specific tool vendors to figure out if an offline tool is right for you. Here are two of the vendors that make such tools:

• WANDL— www.wandl.com

• OPNET— www.opnet.com

Of course, you're free to write your own, especially if you have specific needs not addressed by commercial tools. Just make sure that you understand how complex this problem is before you start working on it!