Path Computation Capability and Use Cases

Path computation tackles routing of flows across a network and allocates bandwidth resources to flows.   Routing can improve (or degrade) network performance and in my previous post I used an example to illustrate effectiveness of routing to optimize network resource utilization and manage service performance by preventing uneven utilization links. While control mechanisms and protocols to distribute and configure paths have consistently matured overtime, path computation is still mostly done manually or with early stage shortest path algorithms.  This is like having a sleek sports car with high-performance tires and a Ford Model-T with 20 hp engine – a great car in its time but inadequate today. The capability to compute paths is critical to optimize network performance and is a key enabler of routine activities that network operators undertake.  Let’s look at characteristics of path computation capability and its use cases.

Ford Model T launched the automotive age

Systems and processes to configure paths have many aspects – access to data, command or graphical interfaces for manual configuration or protocols to request and distribute paths, resource reservation etc.   One important but neglected aspect is the capability to compute paths, not a trivial problem but for which efficient algorithms exist.  Shortest path algorithms have done the heavy lifting to compute paths in the early packet networks but are widely recognized to be insufficient for multi-service networks today.

Sophisticated path computation algorithms can

1. Work with more parameters besides link costs, especially link capacities.
2. Simultaneously compute paths for multiple end-to-end flows (iterative one-by-one path calculation for each flow is ineffective as shown previously)
3. Compute paths over realistic networks in near real-time — in seconds or minutes

Such algorithms are highly effective in improving network performance and are ripe to be employed in network engineering tools and systems.  Before diving into use cases, I want to mention its relevance in Software Defined Networks (SDN) that logically centralizes control and are especially suited for robust and sophisticated PC function.  The use cases below will not lose their relevance in SDN and in case of traffic engineering, PC will become even more relevant in wide area SDN (perhaps a topic for a future post).

Network Planning goal is to develop capital budget and future state of the network.  Activities such as capacity planning, design and deployment of new technologies and expansion of network coverage are part of network planning.   Effective what-if analysis by modeling network scenarios provides insight into decision choices.  Tools with path computation allow planners to build cost effective solutions and help build business cases for network expansion projects.  Access to data about current network state, forecast and market assumptions are supported by systems and processes that are also subject of standards,  such as TMF Frameworx.   Figure 1 shows a high-level view of sources/types of inputs and outputs of the process

Figure 1

An indirect but substantial benefit of planning tools is the use of network models that perform path computation, which helps clearly define required subset from a sea of data in enterprise systems such as inventory management, ERP etc.

Traffic Engineering (TE): Deployments of new capacity in the network are multi-step processes that require coordination and time.  Often in the normal operation of the network, capacity additions are not feasible.  Traffic engineering allows traffic routing to conform to existing resources in the network.  Note: TE does not route traffic or improve performance automagically but provides the means to configure paths that can improve network performance.  To exploit the TE features and improve network performance path computation is a pre-requisite.

A Path Computation Element (PCE) – Based Architecture (RFC 4655) lays out an architecture to automate TE where specialized path computation algorithms can be used to optimize network performance.

Network Restoration: The final use case of path computation capability is restoration of circuits/trunks/flows after an outage.  In optical layer, e.g. DWDM, the service impact of a link outage is large and repairs could take hours or longer, for example splicing a fiber cut at a remote location.  The ability to restore service quickly is an important part of planning and operations of all networks.  In mesh networks provisions are made to reroute flows on alternative paths that avoid outages.

Impacted flows are re-routed over spare capacity that either sits idle or carries best effort services that can be bumped off to route flows with stringent service level agreements (and higher margins).  Path Computation capability is critical to strategically deploy spare capacity and plan reroutes for link outage scenarios.