 been dramatically reduced. Phase 2: Multi- Layer Control Phase 1: Centralized TE Network Utilization Distributed TE Deployed FIGURE 13.24 Historical and projected core utilization. Network Core TABLE 13.2 Comparison of Algorithms Multicommodity Flow Algorithm for Bin Packing Fast Heuristic Algorithm for Bin Packing Efficiency: 100% Efficiency: >99% Requires every TE tunnel to be split into Only requires some of the largest TE tunnels to be split into a arbitrarily small parcels, each of which can be small number of equal-sized subtunnels (implementation routed independently (implementation not practical) practical) Requires iterated application of CSPF (constrained shortest Requires solving a linear program (LP) path) routing with rearrangement of order of tunnel routing, Run-time ~10 S of minutes for a typical Internet uses the fact that usually a vast majority of tunnels can go on service provider (ISP) backbone with 5-10K shortest path and finer adjustments are needed only for a tunnels. For a larger backbone or for edge-to- small fraction of tunnels, partial routing (X% of actual edge TE tunnels, run-time can be hours bandwidth of a tunnel with a starting value of X = 100 and If other constraints such as latency upper limits geometrically decreasing X until feasible), a combination of on individual flows or the requirement of higher random reordering of tunnel routing and giving preference to priority traffic to be routed ahead of lower tunnels that were not fully routed previously, keeping track of priority ones are needed, then either the LP best solution obtained SO far and using that after a formulation fails or run-time increases greatly prespecified stopping time Due to long run-times, not suitable to react to Run-time in subseconds to a few seconds for a typical ISP traffic pattern changes or topology changes in backbone and ~10 S for edge-to-edge TE tunnels orders of seconds as is typical in an ISP network Easy to add latency upper limit constraints or routing of It is not feasible to run the algorit