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

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

All Implemented Interfaces:

RoutingAlg<V,E>, WithEnvParams

public class SWP<V,E>
extends RoutingAlgBase<V,E>
implements RoutingAlg<V,E>

Implements the SWP (Shortest Widest Path) routing algorithm. The implementation is based on the (rather vague) descriptions given in:

• Q. Ma and P. Steenkiste, "On path selection for traffic with bandwidth guarantees," in Proc. IEEE Int. Conf. Network Protocols (ICNP), Atlanta, GA, Oct. 1997, pp. 191-202.
• J. Li and K. L. Yeung, "A Novel Two-Step Approach to Restorable Dynamic QoS Routing," J. Lightwave Technol. 23, 3663- (2005).
  (This gives a clearer description of the algorithm).

In the paper titled "On path selection for..." above, SWP is defined as...

a path with the maximum bandwidth among all feasible paths. If there are several such paths, the one with the minimum hop count is selected. If there are several such paths with the same hop count, one is randomly selected.

Unlike what may seem at first, SWP and WSP are not simply the opposite of each other.

Note: In this implementation, each call to run() implies the execution of two "Dijkstra"s.

Author:

Juan Segovia S.

Constructor Summary

SWP()
Default constructor.

SWP(TED<V,E> ted, Environ env)
Creates a new instance and passes the parameters to setup.

Method Summary

Path<V,E>

run(V src, V dest, int rq_cap) Returns a SWP path whose links have residual capacity at least equal to rq_cap.

Methods inherited from class bcds.phison.ra.RoutingAlgBase

buildPathFromParentNodes, commitBackupPath, commitWorkingPath, dumpState, getBackupPath, getCost, getEnviron, getEnvParams, getName, getTED, getWorkingPath, offersProtection, setBackupPath, setRequest, setup, setWorkingPath, topologyHasChanged, uncommitBackupPath, 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, setup, topologyHasChanged, uncommitBackupPath, uncommitWorkingPath

Methods inherited from interface bcds.phison.WithEnvParams

getEnviron, getEnvParams

Constructor Detail

SWP

public SWP()

Default constructor. To complete the initialization, RoutingAlgBase.setup(TED, Environ) must be called.

SWP

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

Creates a new instance and passes the parameters to setup. The parameter env may be null but the first one must not. No environment parameter is expected or used by this class.

Method Detail

run

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

Returns a SWP path whose links have residual capacity at least equal to rq_cap. If more than one candidate path exists, one of them is chosen arbitrarily.

Specified by:

run in interface RoutingAlg<V,E>