Path Computation and Network Optimization

Throw-bandwidth-at-it is the most common methodology to fix all sorts of network issues with performance, service restoration or capacity for new services.  As the name suggests, it relies on adding capacity to solve a wide range of problems associated with resources in the network.  It is a simple strategy but also expensive in terms of initial capital investment, operational cost and increases network complexity making it less flexible to accommodate new business requirements.  Let’s take a look at a different strategy based on network routing to reduce cost and complexity of optical and connection-oriented layer 2 technologies, e.g. MPLS and carrier Ethernet.

Routing is one of the most useful tools to efficiently use network resources and lower the capex and opex.  Most network architects and engineers understand importance of routing but often lack tools or data or both to effectively perform routing analysis to optimize the network.  Here I will present a simple example of a network to illustrate the importance of routing to efficiently use network resources, mainly bandwidth on links.

Figure 1 shows a network of 14 nodes and 17 links, each link has 1 unit of capacity (in a SONET network the unit could be an OC-n, in DWDM network the unit would be a lambda i.e. a wavelength and in MPLS network it could be some number of bits/second). To keep things simple let’s make the cost of each link the same. In this example, we need to route 1 unit of flow from A to M and another from A to N

Figure 1

Figure 2 shows shortest paths for each flow.  A simple algorithm to route flows is to iteratively route each flow on shortest path and remove fully utilized links before each iteration.  Order of the flows can make a very big difference in end result.  In the above example it does not matter whether A-M is routed first or A-N.  Either way some links will be over utilized.

Figure 2

Figure 3 shows a better or ‘smarter’ routing solution.  Although neither of the flows is routed on its shortest path, yet no link is over-utilized (in the transport network, SONET or DWDM, over-utilization is not an option so only one flow can be routed on its shortest path and the other will be blocked until more capacity of added to the network).

Figure 3

In real network scenarios where networks are larger with more end-to-end flows and different link capacities and other properties, finding optimal routes quickly becomes complicated and impractical without effective tools.