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

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

All Implemented Interfaces:

RoutingAlg<V,E>, WithEnvParams

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

Implements the LMIR routing algorithm as described in:

• Gustavo B. Figueiredo, Nelson L. S. da Fonseca, Jose A. S. Monteiro, "A minimum interference routing algorithm with reduced computational complexity," in: Computer Networks, Elsevier, v.50, n.11, 2006.
• Gustavo B. Figueiredo, Nelson L. S. da Fonseca, Jose A. S. Monteiro, "A Minimum Interference Routing Algorithm," in: IEEE International Conference on Communications, 2004.

NOTES

• The first paper (2006, submitted in 2004) is a little bit more complete (explains the algorithm better).
• This algorithm considers only link "capacity" (both total and residual); "cost" (for example distance) is not taken into account. Therefore, no user-provided "cost" is used or altered. A "cost" map is created for internal use.
• The algorithm finds the least-expensive path from the source to a given node. If, during path exploration, more then one possible "shortest" path exists, the one with the fewer number of hops is chosen.

Author:

Juan Segovia S.

Constructor Summary

LMIR()
Default constructor.

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

Method Summary

void	dumpState() Prints to stdout internal variables.
Path<V,E>	run(V src, V dest, int rq_cap) Returns al LMIR path from src to dest whose links have residual capacity at least equal to rq_cap, or null if no path can be found.
void	setup(TED<V,E> ted, Environ env) Resets all internal data structures.

Methods inherited from class bcds.phison.ra.RoutingAlgBase

buildPathFromParentNodes, commitBackupPath, commitWorkingPath, 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, getBackupPath, getCost, getName, getWorkingPath, offersProtection, topologyHasChanged, uncommitBackupPath, uncommitWorkingPath

Methods inherited from interface bcds.phison.WithEnvParams

getEnviron, getEnvParams

Constructor Detail

LMIR

public LMIR()

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

LMIR

public LMIR(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

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

run

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

Returns al LMIR path from src to dest whose links have residual capacity at least equal to rq_cap, or null if no path can be found. Each invocation of this method implies a full recomputation of the weights. Despite it is a "light" MIRA, LMIR is still much slower than other algorithms, for example Dijkstra.

Specified by:

run in interface RoutingAlg<V,E>

dumpState

public void dumpState()

Prints to stdout internal variables.

Specified by:

dumpState in interface RoutingAlg<V,E>

Overrides:

dumpState in class RoutingAlgBase<V,E>