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

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

All Implemented Interfaces:

RoutingAlg<V,E>, WithEnvParams

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

Implements the LIOA routing algorithm. It is based on the following paper:

Bagula A.B., Botha M., and Krzesinski A.E., "Online Traffic Engineering: The Least Interference Optimization Algorithm," in Proc. 2004 IEEE International Conference on Communications, 2004.

LIOA uses a parameter called "alpha" (0 ≤ alpha ≤ 1), that represents the trade-off between the "least intefering optimization" effort and a simple capacity constrained shortest path. The effect of the extreme alpha values on link cost is as follows:

• when alpha = 1, it is the number of paths traversing the links.
• when alpha = 0, it is the inverse of the residual capacity.

A good compromise, in terms of blocking ratio and capacity utilization, seems to be alpha=0.45, which is the default value in this implementation. This default value can be overriden at instantiation time through the environment parameter passed to the constructor.

Notes:

• The paper says "... S_l = R_l - r_e where R_l is the maximum reservable bandwidth of link l, r_l is the total bandwidth reserved by the LSPs traversing the link...". I interpret this as a convulted description of residual capacity.
• LIOA is just a Dijkstra with a new cost function.
• This implementation relies on the TED object to obtain the number of "flows" passing thourgh each link. Therefore, if more than one routing algorithm (RA) is being employed on the same topology/TED, the flows created by the other(s) RA are automatically taken into account.

Author:

Juan Segovia S.

Nested Class Summary

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

DijkstraAll.PathExpansionInfo

Constructor Summary

LIOA()
Default constructor.

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

Method Summary

double	getCost(E e) Returns the cost of link e.
java.lang.Object[]	getEnvParams() Returns the environment parameter used by LIOA.
void	setup(TED<V,E> ted, Environ env) Resets all internal data structures.

Methods inherited from class bcds.phison.ra.DijkstraAll

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

Methods inherited from class bcds.phison.ra.RoutingAlgBase

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

Methods inherited from interface bcds.phison.WithEnvParams

getEnviron

Constructor Detail

LIOA

public LIOA()

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

LIOA

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

Creates a new instance. The parameter ted must not be null. If env is not null, the environment parameter LIOA.alpha can be used to replace the default value returned by getEnvParams.

The cost map embedded in ted is never used. Instead, getCost(E) is overriden to return the values as prescribed by the LIOA algorithm.

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>

getEnvParams

public java.lang.Object[] getEnvParams()

Returns the environment parameter used by LIOA. Only one parameter is used: alpha=0.45.

Specified by:

getEnvParams in interface WithEnvParams

Overrides:

getEnvParams in class RoutingAlgBase<V,E>

getCost

public double getCost(E e)

Returns the cost of link e. The cost function is:

   cost(e) = (F(e) ^ alpha) / res_cap(e) ^ (1-alpha)
 

where F(e) is the number of flows (connections) passing through link e and res_cap(e) is that link's residual capacity.

Specified by:

getCost in interface RoutingAlg<V,E>

Overrides:

getCost in class RoutingAlgBase<V,E>