be.ac.ulg.montefiore.run.totem.repository.CSPF
Class CSPF

java.lang.Object
  be.ac.ulg.montefiore.run.totem.repository.CSPF.CSPF

All Implemented Interfaces:

LSPBackupRouting, LSPBypassRouting, LSPDetourRouting, LSPPrimaryRouting, SPF, TotemAlgorithm

Direct Known Subclasses:

CSPFHopCount, CSPFInvCap, CSPFInvFreeBw, CSPFTEMetric

public class CSPF
extends java.lang.Object
implements SPF, LSPPrimaryRouting, LSPDetourRouting, LSPBypassRouting

This class implements a Constraint Shortest Path First algorithm. This implementation supports equal cost multi path. This algorithm uses a priority queue to store the temporary node list under processing.

There is no specific parameter required by this routing algorithm.

Creation date: 1-Jan-2004

Author:

Fabian Skivee (skivee@run.montefiore.ulg.ac.be), Olivier Delcourt (delcourt@run.montefiore.ulg.ac.be), Jean Lepropre (lepropre@run.montefiore.ulg.ac.be), Gaël Monfort (monfort@run.montefiore.ulg.ac.be)

Field Summary

protected java.util.Set<Link>

avoidLinks Links to avoid in the next CSPF computation

Constructor Summary

CSPF()

Method Summary

protected java.util.HashMap<java.lang.String,CSPFElem>	computeCSPF(Domain domain, int priority, Node srcNode, Node dstNode, float bw, boolean stopToSourceOrDestination, boolean computeFromSourceToDestination) Computes the CSPF between a source node and a destination node with a bandwidth requirement
java.util.List<Path>	computeFullMeshSPF(Domain domain) Computes a unique shortest path between all nodes in the topology
java.util.List<Path>	computeFullMeshSPF(Domain domain, boolean ECMP) Computes the shortest paths between all nodes in the topology
java.util.List<Path>	computeSPF(Domain domain, boolean isSource, java.lang.String node) Computes a unique shortest path from (resp.
java.util.List<Path>	computeSPF(Domain domain, boolean isSource, java.lang.String node, boolean ECMP) Computes the shortest paths from (resp.
java.util.List<Path>	computeSPF(Domain domain, java.lang.String src) Computes a unique shortest path from a source node to all destination node
java.util.List<Path>	computeSPF(Domain domain, java.lang.String src, boolean ECMP) Computes the shortest paths from a source node to all destination node
Path	computeSPF(Domain domain, java.lang.String src, java.lang.String dst) Computes a unique shortest path between two nodes
java.util.List<Path>	computeSPF(Domain domain, java.lang.String src, java.lang.String dst, boolean ECMP) Computes the shortest path between two nodes.
protected void	displayPath(java.util.HashMap<java.lang.String,CSPFElem> path) Debug method for displaying the Path
protected void	displayTent(CSPFPriorityQueue tent) Debug method for displaying the TENT list
boolean	equals(java.lang.Object o)
protected java.util.List<Path>	extractPath(Domain domain, java.util.HashMap<java.lang.String,CSPFElem> path, Node node, boolean ECMP, boolean computeFromSourceToDestination)
protected java.util.List<Path>	extractPath(Domain domain, java.util.HashMap<java.lang.String,CSPFElem> path, Node srcNode, Node dstNode, boolean ECMP, boolean computeFromSourceToDestination)
java.util.List<ParameterDescriptor>	getBypassRoutingParameters() Returns a list of available algorithm specfic parameters that can be passed to the routeBypass method.
java.util.List<ParameterDescriptor>	getDetourRoutingParameters() Returns a list of available algorithm specfic parameters that can be passed to the routeDetour method.
protected float	getMetric(Link link)
java.util.List<ParameterDescriptor>	getPrimaryRoutingParameters()
java.util.HashMap	getRunningParameters() Returns the parameters given when the algorithm was started
java.util.List<ParameterDescriptor>	getStartAlgoParameters() Returns the optional parameters that can be given when starting the algorithm
int	hashCode()
protected void	initComputation(Domain domain)
protected void	relax(Link link, int priority, boolean computeFromSourceToDestination)
TotemActionList	routeBypass(Domain domain, LSPBypassRoutingParameter param) Computes a bypass based on the specified parameters.
TotemActionList	routeDetour(Domain domain, LSPDetourRoutingParameter param) Computes a detour backup for a LSP.
TotemActionList	routeLSP(Domain domain, LSPPrimaryRoutingParameter param) Computes a path for a LSP
TotemActionList	routeNLSP(Domain domain, java.util.List<LSPPrimaryRoutingParameter> param) Computes paths for a list of LSPs specified by a list of LSPPrimaryRoutingParameter
void	start()
void	start(java.util.HashMap params) Nothing to do
void	stop() Nothing to do

Methods inherited from class java.lang.Object

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

Field Detail

avoidLinks

protected java.util.Set<Link> avoidLinks

Links to avoid in the next CSPF computation

Constructor Detail

CSPF

public CSPF()

Method Detail

initComputation

protected void initComputation(Domain domain)

routeLSP

public TotemActionList routeLSP(Domain domain,
                                LSPPrimaryRoutingParameter param)
                         throws RoutingException,
                                NoRouteToHostException

Description copied from interface: LSPPrimaryRouting

Computes a path for a LSP

Specified by:

routeLSP in interface LSPPrimaryRouting

Returns:

the LSP path computed

Throws:

RoutingException

NoRouteToHostException

routeNLSP

public TotemActionList routeNLSP(Domain domain,
                                 java.util.List<LSPPrimaryRoutingParameter> param)
                          throws RoutingException,
                                 NoRouteToHostException

Description copied from interface: LSPPrimaryRouting

Computes paths for a list of LSPs specified by a list of LSPPrimaryRoutingParameter

Specified by:

routeNLSP in interface LSPPrimaryRouting

param - a list of LSPPrimaryRoutingParameter

Returns:

a list of the LSPs path

Throws:

RoutingException

NoRouteToHostException

computeSPF

public Path computeSPF(Domain domain,
                       java.lang.String src,
                       java.lang.String dst)
                throws RoutingException,
                       NoRouteToHostException

Description copied from interface: SPF

Computes a unique shortest path between two nodes

Specified by:

computeSPF in interface SPF

src - the source node

dst - the destination node

Returns:

a Path

Throws:

RoutingException

NoRouteToHostException

computeSPF

public java.util.List<Path> computeSPF(Domain domain,
                                       java.lang.String src,
                                       java.lang.String dst,
                                       boolean ECMP)
                                throws RoutingException,
                                       NoRouteToHostException

Description copied from interface: SPF

Computes the shortest path between two nodes.

Specified by:

computeSPF in interface SPF

src - the source node

dst - the destination node

ECMP - true if multipath activated

Returns:

a list of equal cost multi path

Throws:

RoutingException

NoRouteToHostException

computeSPF

public java.util.List<Path> computeSPF(Domain domain,
                                       java.lang.String src)
                                throws RoutingException,
                                       NoRouteToHostException

Description copied from interface: SPF

Computes a unique shortest path from a source node to all destination node

Specified by:

computeSPF in interface SPF

src - the source node

Returns:

a list of N-1 (N = number of nodes) Path

Throws:

RoutingException

NoRouteToHostException

computeSPF

public java.util.List<Path> computeSPF(Domain domain,
                                       boolean isSource,
                                       java.lang.String node)
                                throws RoutingException,
                                       NoRouteToHostException

Description copied from interface: SPF

Computes a unique shortest path from (resp. to) a node to (resp. from) all the other nodes depending on the value of isSource. If isSource is true, node is considered as the source node and the method computes a shortest path from this node to all the other nodes.

Specified by:

computeSPF in interface SPF

Parameters:

domain - The domain on which the paths have to be computed.

isSource - true if node is the source and false otherwise.

node - The source or destination node.

Returns:

The shortest paths from or to node.

Throws:

RoutingException

NoRouteToHostException

computeSPF

public java.util.List<Path> computeSPF(Domain domain,
                                       java.lang.String src,
                                       boolean ECMP)
                                throws RoutingException,
                                       NoRouteToHostException

Description copied from interface: SPF

Computes the shortest paths from a source node to all destination node

Specified by:

computeSPF in interface SPF

src - the source node

ECMP - true if multipath is activated

Returns:

a list of N-1 (N = number of nodes) Path

Throws:

RoutingException

NoRouteToHostException

computeSPF

public java.util.List<Path> computeSPF(Domain domain,
                                       boolean isSource,
                                       java.lang.String node,
                                       boolean ECMP)
                                throws RoutingException,
                                       NoRouteToHostException

Description copied from interface: SPF

Computes the shortest paths from (resp. to) a node to (resp. from) all the other nodes depending on the value of isSource. If isSource is true, node is considered as the source node and the method computes a shortest path from this node to all the other nodes.

Specified by:

computeSPF in interface SPF

Parameters:

domain - The domain on which the paths have to be computed.

isSource - true if node is the source and false otherwise.

node - The source or destination node.

ECMP - true if multipath is activated

Returns:

The shortest paths from or to node.

Throws:

RoutingException

NoRouteToHostException

computeFullMeshSPF

public java.util.List<Path> computeFullMeshSPF(Domain domain)
                                        throws RoutingException,
                                               NoRouteToHostException

Description copied from interface: SPF

Computes a unique shortest path between all nodes in the topology

Specified by:

computeFullMeshSPF in interface SPF

Returns:

a list of N * N-1 Path (N = number of nodes)

Throws:

RoutingException

NoRouteToHostException

computeFullMeshSPF

public java.util.List<Path> computeFullMeshSPF(Domain domain,
                                               boolean ECMP)
                                        throws RoutingException,
                                               NoRouteToHostException

Description copied from interface: SPF

Computes the shortest paths between all nodes in the topology

Specified by:

computeFullMeshSPF in interface SPF

ECMP - true if multipath is activated

Returns:

a list of N * N-1 Path (N = number of nodes)

Throws:

RoutingException

NoRouteToHostException

getMetric

protected float getMetric(Link link)

computeCSPF

protected java.util.HashMap<java.lang.String,CSPFElem> computeCSPF(Domain domain,
                                                                   int priority,
                                                                   Node srcNode,
                                                                   Node dstNode,
                                                                   float bw,
                                                                   boolean stopToSourceOrDestination,
                                                                   boolean computeFromSourceToDestination)
                                                            throws RoutingException,
                                                                   NoRouteToHostException,
                                                                   NodeNotFoundException

Computes the CSPF between a source node and a destination node with a bandwidth requirement

Parameters:

srcNode - the source node

dstNode - the destination node

bw - the bandwidth demand

Returns:

the hashmap of the path exploration

Throws:

RoutingException

NoRouteToHostException

NodeNotFoundException

relax

protected void relax(Link link,
                     int priority,
                     boolean computeFromSourceToDestination)
              throws NodeNotFoundException

Throws:

NodeNotFoundException

extractPath

protected java.util.List<Path> extractPath(Domain domain,
                                           java.util.HashMap<java.lang.String,CSPFElem> path,
                                           Node srcNode,
                                           Node dstNode,
                                           boolean ECMP,
                                           boolean computeFromSourceToDestination)
                                    throws RoutingException,
                                           NodeNotFoundException,
                                           NoRouteToHostException

Throws:

RoutingException

NodeNotFoundException

NoRouteToHostException

extractPath

protected java.util.List<Path> extractPath(Domain domain,
                                           java.util.HashMap<java.lang.String,CSPFElem> path,
                                           Node node,
                                           boolean ECMP,
                                           boolean computeFromSourceToDestination)
                                    throws RoutingException,
                                           NodeNotFoundException,
                                           NoRouteToHostException

Throws:

RoutingException

NodeNotFoundException

NoRouteToHostException

start

public void start()

start

public void start(java.util.HashMap params)

Nothing to do

Specified by:

start in interface TotemAlgorithm

stop

public void stop()

Nothing to do

Specified by:

stop in interface TotemAlgorithm

displayTent

protected void displayTent(CSPFPriorityQueue tent)

Debug method for displaying the TENT list

Parameters:

tent -

displayPath

protected void displayPath(java.util.HashMap<java.lang.String,CSPFElem> path)

Debug method for displaying the Path

Parameters:

path -

getStartAlgoParameters

public java.util.List<ParameterDescriptor> getStartAlgoParameters()

Description copied from interface: TotemAlgorithm

Returns the optional parameters that can be given when starting the algorithm

Specified by:

getStartAlgoParameters in interface TotemAlgorithm

Returns:

the list of algorithm parameters

getRunningParameters

public java.util.HashMap getRunningParameters()

Description copied from interface: TotemAlgorithm

Returns the parameters given when the algorithm was started

Specified by:

getRunningParameters in interface TotemAlgorithm

Returns:

getPrimaryRoutingParameters

public java.util.List<ParameterDescriptor> getPrimaryRoutingParameters()

Specified by:

getPrimaryRoutingParameters in interface LSPPrimaryRouting

getDetourRoutingParameters

public java.util.List<ParameterDescriptor> getDetourRoutingParameters()

Description copied from interface: LSPDetourRouting

Returns a list of available algorithm specfic parameters that can be passed to the routeDetour method.

Specified by:

getDetourRoutingParameters in interface LSPDetourRouting

Returns:

equals

public boolean equals(java.lang.Object o)

Specified by:

equals in interface SPF

Overrides:

equals in class java.lang.Object

hashCode

public int hashCode()

Specified by:

hashCode in interface SPF

Overrides:

hashCode in class java.lang.Object

routeBypass

public TotemActionList routeBypass(Domain domain,
                                   LSPBypassRoutingParameter param)
                            throws RoutingException,
                                   NoRouteToHostException

Computes a bypass based on the specified parameters.

Specified by:

routeBypass in interface LSPBypassRouting

Parameters:

param - specifies the parameters for the backup routing algorithm

Returns:

the bypass computed

Throws:

RoutingException

NoRouteToHostException

getBypassRoutingParameters

public java.util.List<ParameterDescriptor> getBypassRoutingParameters()

Description copied from interface: LSPBypassRouting

Returns a list of available algorithm specfic parameters that can be passed to the routeBypass method.

Specified by:

getBypassRoutingParameters in interface LSPBypassRouting

Returns:

routeDetour

public TotemActionList routeDetour(Domain domain,
                                   LSPDetourRoutingParameter param)
                            throws RoutingException,
                                   NoRouteToHostException

Computes a detour backup for a LSP. The backups try to avoid the link to protect and also the reverse link (see Domain.getReverseLink(be.ac.ulg.montefiore.run.totem.domain.model.Link) to see how the reverse link is chosen).
Global backups are calculated as the shortest path that avoid all links of the primary and also the reverse links.
For local backups, see the options.

Specified by:

routeDetour in interface LSPDetourRouting

Parameters:

domain -

param - specifies the parameters for the backup routing algorithm

Returns:

the necessary list of action to add the detour to the network

Throws:

RoutingException

NoRouteToHostException