bcds.phison.ra
Class ProtDPP_MinCost<V,E>

java.lang.Object
  bcds.phison.ra.RoutingAlgBase<V,E>
      bcds.phison.ra.ProtectionAlgBase<V,E>
          bcds.phison.ra.ProtDPP_MinCost<V,E>

All Implemented Interfaces:

RoutingAlg<V,E>, WithEnvParams

public class ProtDPP_MinCost<V,E>
extends ProtectionAlgBase<V,E>
implements RoutingAlg<V,E>

Provides Dedicated dath Protection (DPP) using DijkstraAll as the search algorithm. It employs a two-step approach to find the primary and backup paths. The primary and backup paths are either node- or link-disjoint, depending on the parameter passed to the constructor or the environment parameter ProtDPP_MinCost.node_disjoint.

The following diagram illustrates a primary (==) and backup path (--) that are not node-disjoint. The nodes are a, b, c, d and e. The protected path goes from a to e.

     --- b ---    --- d ---
    /         \  /         \
   a ========= c ========== e
 

This topology is (in .sgf):

  [netname]
  dummy
  
  [nodenum]
  5
  
  [coordinates]
  0 0 0   # a
  0 0 1   # b
  0 0 2   # c
  0 0 3   # d
  0 0 4   # e
  
  [capacity]
  0 = 1 10
  0 = 2 10
  1 = 2 10
  2 = 3 10
  2 = 4 10
  3 = 4 10
  
  [cost]
  0 = 1 1
  0 = 2 1
  1 = 2 1
  2 = 3 1
  2 = 4 1
  3 = 4 1
  
  [traffic]
  # empty
 

You can test the algorith with the following traffic file (.trf)

  # -- Format:
  # c id dem_type src dest cap holding_time clock (conn_request)
  # r id clock (conn_release)
  # fl src dest duration clock (link_failure)
  # flr src dest clock (link_repair)
  # fn node duration clock (node_failure)
  # fnr node clock (node_repair)
  # --
  c         0 *   0   4       1     7 1
 

Author:

Juan Segovia S.

Constructor Summary

ProtDPP_MinCost()
Default constructor.

ProtDPP_MinCost(TED<V,E> ted, Environ env)
Creates a new instance.

ProtDPP_MinCost(TED<V,E> ted, Environ env, Disjoinness dj)
Creates a new instance with the disjointness type set to dj.

Method Summary

java.lang.Object[]	getEnvParams() Returns the environment parameter used by this class.
Path<V,E>	run(V src, V dest, int rq_cap) Returns a path between src and dest, or null if such path cannot be found.
void	setup(TED<V,E> ted, Environ env) Resets all internal data structures.

Methods inherited from class bcds.phison.ra.ProtectionAlgBase

commitBackupPath, getBackupPath, offersProtection, uncommitBackupPath

Methods inherited from class bcds.phison.ra.RoutingAlgBase

buildPathFromParentNodes, commitWorkingPath, dumpState, getCost, getEnviron, getName, getTED, getWorkingPath, setBackupPath, setRequest, setWorkingPath, topologyHasChanged, uncommitWorkingPath

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface bcds.phison.ra.RoutingAlg

commitBackupPath, commitWorkingPath, dumpState, getBackupPath, getCost, getName, getWorkingPath, offersProtection, topologyHasChanged, uncommitBackupPath, uncommitWorkingPath

Methods inherited from interface bcds.phison.WithEnvParams

getEnviron

Constructor Detail

ProtDPP_MinCost

public ProtDPP_MinCost()

Default constructor.

ProtDPP_MinCost

public ProtDPP_MinCost(TED<V,E> ted,
                       Environ env)

Creates a new instance. It is equivalent to ProtDPP_MinCost(ted, env, Disjoinness.LINK_DISJOINT).

ProtDPP_MinCost

public ProtDPP_MinCost(TED<V,E> ted,
                       Environ env,
                       Disjoinness dj)

Creates a new instance with the disjointness type set to dj. The parameter ted must not be null.

Method Detail

setup

public void setup(TED<V,E> ted,
                  Environ env)

Resets all internal data structures.

Specified by:

setup in interface RoutingAlg<V,E>

Overrides:

setup in class ProtectionAlgBase<V,E>

run

public Path<V,E> run(V src,
                     V dest,
                     int rq_cap)

Description copied from interface: RoutingAlg

Returns a path between src and dest, or null if such path cannot be found. Null can be returned because there is not enough capacity or for any other reason or constraint, including topology disconnection.

The path retuned by this method is automatically the working path, that is, run() followed by RoutingAlg.getWorkingPath() must return the same path.

Specified by:

run in interface RoutingAlg<V,E>

getEnvParams

public java.lang.Object[] getEnvParams()

Returns the environment parameter used by this class. Only one parameter is used: node_disjoint=false. That is, by default, working and backup paths are link-disjoint.

Specified by:

getEnvParams in interface WithEnvParams

Overrides:

getEnvParams in class RoutingAlgBase<V,E>