Example: 'Generic provisioning algorithm based on restoration'

Brief description

Algorithm which implements several restoration mechanisms: path/subpath/link restoration, and fast restoration.

Algorithm description table

Algorithm inputs

A complete network design.

Algorithm parameters:

  • revertiveMode: Indicates whether routes are restored to their primary paths when become available. Default: true
  • restorationMode: Restoration mode: path restoration (from ingress node to egress node), subpathRestoration (from the first node before the first failure to the first node after the last failure), linkRestoration (from the first node before a failure to the next available one), fastReroute (from first node before the failure to egress node). Default: pathRestoration
Algorithm outputsA set of provisioning actions: rerouting, restore to primary path, block route
Required librariesNone
KeywordsMPLS, Restoration algorithm
AuthorsPablo Pavón Mariño, José Luis Izquierdo Zaragoza
DateMarch 2013
CodeNRSim_AA_genericRestorationAlgorithm.java

Detailed description

For any of the implemented mechanisms, we use the following terminology:

  • Point of local repair (PLR): Node that redirectes the traffic onto the backup path
  • Merge point (MP): Downstream node where the backup path rejoins to the primary path

Implemented mechanisms:

  • Path restoration: Try to find a path with enough capacity from the ingress node (PLR) to the egress node (MP)
  • Subpath restoration: Try to find a path with enough capacity from the first available node before any failure (PLR) to the first available node after any failure (MP)
  • Link restoration: Try to find a path with enough capacity from the first available node before a failure (PLR) to the first available node after a failure (MP). In case of multiple failures, multiple link restorations are tried sequentially
  • Fast reroute: Try to find a path with enough capacity from the first available node before any failure (PLR) to the egress node (MP)

Important: Local restoration mechanisms (all but path restoration) considers as spare capacity that available after reducing the amount of traffic expected to be carried through ingressNode-to-PLR and MP-to-egressNode segments, since some loops may appear.

Upon reparation, try to restore each rerouted connection to their original path, using a make-before-break strategy, only in case 'revertiveMode' is enabled. Then, still-failing routes are tried to be restored as under failure events.