Example: 'Shortest path (uncapacitated) routing, and link-disjoint backup path protection'

Brief description

Algorithm for flow assignment problems which routes all traffic of each demand, through the shortest path, and then creates a backup path, measured in number of hops or in km, being this an user-defined parameter

Algorithm description table

Algorithm inputs

Requires a topology (nodes and links) and a demand set within the netPlan object.

Algorithm parameters:

  • shortestPathType: Each demand is routed according to the shortest path according to this type ('km' or 'hops'). Default: "hops"
Algorithm outputsRoutes and path protection segments are added to netPlan object. Any previous routes and protection segments are removed
Required librariesNone
KeywordsFlow assignment (FA), Protection algorithm
AuthorsPablo Pavón Mariño, José Luis Izquierdo Zaragoza
DateMarch 2013
CodeFA_shortestPath_11pathProtection.java

Detailed description

For each traffic demands, the algorithm computes the shortest path between ingress and egress nodes (in hops or km), and routes all the traffic over that path. A dedicated link-disjount backup path is also reserved. Please note that capacity values along path are not checked, so some links may become over-saturated