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

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

All Implemented Interfaces:

RoutingAlg<V,E>, WithEnvParams

public class WSP<V,E>
extends DijkstraAll<V,E>

Implements the WSP (Widest-Shortest Path) routing algorithm. WSP is a variation of Dijkstra where the main selection criterion is "cost" (for example, hop count, or distance) and the second is maximum residual capacity. This implementation loosely follows the description given in these two publications:

1. R. Guerin, A. Orda, and D. Williams, "QoS routing Mechanisms and OSPF Extensions," In Proc. IEEE GLOBECOM'97, 1997.
2. 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.

None of these publicacions give enough implementation details, but it can be guessed. The RFC 2676 repeats exactly the same words present in (1) above, and the draft implementation also lacks details.

Author:

Juan Segovia S.

Nested Class Summary

Nested classes/interfaces inherited from class bcds.phison.ra.DijkstraAll

DijkstraAll.PathExpansionInfo

Constructor Summary

WSP()
Default constructor.

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

Method Summary

DijkstraAll.PathExpansionInfo	evalEdge(E e) Evaluates the path whose last hop is e and determines if it leads to target(e) through a shorter path.
void	initialize() Initialize internal data structures.
void	setup(TED<V,E> ted, Environ env) Resets all internal data structures.

Methods inherited from class bcds.phison.ra.DijkstraAll

dumpEvalEdgeState, filterGraph, generalizedDijkstra, getParent, getTotalCost, getVisitSequence, obtain, obtain, outgoingEdgesOf, run, runAll

Methods inherited from class bcds.phison.ra.RoutingAlgBase

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

Methods inherited from interface bcds.phison.WithEnvParams

getEnviron, getEnvParams

Constructor Detail

WSP

public WSP()

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

WSP

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

Creates a new a WSP object 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

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 DijkstraAll<V,E>

initialize

public void initialize()

Initialize internal data structures. Each entry in this.max_rc is set to +INF.

Overrides:

initialize in class DijkstraAll<V,E>

evalEdge

public DijkstraAll.PathExpansionInfo evalEdge(E e)

Evaluates the path whose last hop is e and determines if it leads to target(e) through a shorter path. Basically, node reparenting should be performed if:

    total_cost[source(e)] + cost[e] < total_cost[target(e)]
    or they are equal but the residual capacity through e
    is larger than whas target(e) currently has, i.e.,
 

If reparenting is necessary (that is, the field is_shorter will be returned set to true, this method updates the min max-flow entry for target(e) so that

   this.max_rc[target(e)] = new min max-flow through link e.
 

The field prioq_key is always set to

    (total_cost[source(e)] + cost[e]) + (1 / redidual_cap[e])
 

Overrides:

evalEdge in class DijkstraAll<V,E>