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

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

public class TED<V,E>
extends java.lang.Object

Implements a minimal "traffic engineering database" for path-oriented networks/routing.

Essentially, a TED instance puts together in a single object a topology (a SimGraph), a map of link costs and a map of link capacities. Besides, it registers the acceptance and release of connections, and updates the residual capacities on each link based on the capacity requested by connections.

When a connection is registered (that is, accepted), the object describing it must specify several pieces of information such as the working path (optionally, the backup path), the requested capacity, a reference to the algorithm that was used to find the paths, and a unique id for the connection. The class ConnectionInfo serves a connection descriptor for TED objects. Other functions offered are:

• keeping the list of connections passing through each link.
• registering which links have failed and when (in virtual time), and the time each one has been repaired.

In general, the information associated to each link (cost, residual capacity, connection passing through it, etc) is kept (and expected) considering separate entries for each link direction. When a method operates simultaneously on both link directions, "bidi" appears in its name, as in getConnPerBidiLink(E).

Note that a TED object only registers the fact that a failure has happened; it does not automatically remove connections, adjusst residual capacity or trigger path switching (from working to backup path), or perform reversion when a link is restored. These are the duties of the entity that uses the TED object.

There may be any number of instances of this class, but given that the information kept here is global for a given topology, quite usually a single instance is shared among several entities. For example, if two routing algorithms are used concurrently over the same topology (one per demand/service type, for example), one TED instance would be created and passed to the constructors of the two routing algorithm

Author:

Juan Segovia S.

Field Summary

SimGraph<V,E>

g The graph associated to this TED.

Constructor Summary

TED(SimGraph<V,E> g, java.util.Map<E,java.lang.Integer> link_cap, java.util.Map<E,? extends java.lang.Number> cost)
Creates a new TED instance for the topology g with the link capacities and costs in link_cap and cost respectively.

TED(TED<V,E> r)
A shallow copy constructor.

Method Summary

boolean	bidiLinkIsFailed(E e) Returns true if link e (either itself or its reverse) is registered as failed.
SimGraph<V,E>	filterByCap(int min_cap) Returns a subgraph where links with residual capacity less than min_cap are (virtually) removed.
int	getConnCount() Returns the number of connections.
ConnectionInfo<V,E>	getConnection(int id) Returns the connection descriptor object for the given connection id, or null if a connection with that id does not exist.
java.util.Collection<ConnectionInfo<V,E>>	getConnections() Returns an unmodifiable view of the connection descriptor objects.
java.util.Set<java.lang.Integer>	getConnIDs() Returns an unmodifiable view (as a set) of the connection ids.
java.util.List<ConnectionInfo<V,E>>	getConnPerBidiLink(E e) Returns a copy of the list of connections passing thourgh a link e in its both directions.
java.util.List<ConnectionInfo<V,E>>	getConnPerLink(E e) Returns a copy of the list of connections passing thourgh a link e.
double	getCost(E e) Returns the cost of link e.
java.util.Set<E>	getFailedLinks() Returns an unmodifiable view of the set of links registered as failed.
E	getFirstFailedBidiLink(Path<V,E> path) Returns the first link of path that is currently registered as failed, or null if all links are operative.
int	getLinkCap(E e) Returns the capacity of link e.
int	getResidualCap(E e) Returns the residual capacity of link e.
void	initLinkInstallationTime() Resets the link installation time of each link to zero.
void	initResidualCap() Sets the residual capacity of each link to its link (full) capacity.
void	recoverBidiLink(E e, int clock) Registers that both e and reverse(e) are not in the failed state anymore.
void	registerBidiLinkFailure(E e) Registers the failure of links e and reverse(e).
void	registerConnection(ConnectionInfo<V,E> cnx) Register the acceptance of a connection, updates the internal information and informs the corresponding routing algorithm that a connection has been accepted.
void	registerConnPerLink(ConnectionInfo<V,E> cnx, Path<V,E> path) Updates the list of connections using the links of a given path.
void	reinstallBidiLinks(java.util.Collection<E> links, int clock) Calls recoverBidiLink(E, int) for each element in links and sets the residual capacity of both link directions to the valure returned by getLinkCap(E).
void	releaseConnection(int id) Release the connection identified by id.
void	retireBidiLinks(java.util.Collection<E> failed) Calls registerBidiLinkFailure(E) for each link in failed and sets the residual capacity of both link directions to zero.
void	setCost(E e, java.lang.Number n) Sets the cost of link e to n.
void	setCostMap(java.util.Map<E,? extends java.lang.Number> cost) Replaces the current cost map with the parameter cost.
void	setLinkCap(E e, int cap) Sets the total capacity of link e to cap.
void	setResidualCap(E e, int cap) Sets the residual capacity of link e to cap.
void	unregisterConnPerLink(ConnectionInfo<V,E> cnx, Path<V,E> path) Removes connection cnx from the list of connections passing through the links in path.
void	updateResidualCap(ConnectionInfo<V,E> cnx, Path<V,E> path, int delta) Updates the residual capacity of links on a given path.
void	updateResidualCap(ConnectionInfo<V,E> cnx, Path<V,E> path, int delta, boolean bidir) Updates the residual capacity of links on a given path.

Methods inherited from class java.lang.Object

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

Field Detail

g

public final SimGraph<V,E> g

The graph associated to this TED. It can only be set through the constructor. It is used very often in client code, thus it is made public (but read-only).

Constructor Detail

TED

public TED(SimGraph<V,E> g,
           java.util.Map<E,java.lang.Integer> link_cap,
           java.util.Map<E,? extends java.lang.Number> cost)

Creates a new TED instance for the topology g with the link capacities and costs in link_cap and cost respectively. If these maps are null, empty (non-null) maps are created for them.

Residual capacity is set to link capacity, that is, each link is considered fully available.

The installation time of each link is set to 0 and all links are marked as operational.

The cost map can hold values of any Number-derived class (for example Integer). Nevertheless, take into account that

• getCost(E) always returns a double value.
• certain type-safety issues must be considered; see setCost(E, java.lang.Number) for details.

TED

public TED(TED<V,E> r)

A shallow copy constructor. This is typically used to create a partial copy of a given TED object. Note that the only attribute that can be changed once an instance is created is the cost map, through setCostMap(Map).

Method Detail

initResidualCap

public void initResidualCap()

Sets the residual capacity of each link to its link (full) capacity. Any previous information is lost.

initLinkInstallationTime

public void initLinkInstallationTime()

Resets the link installation time of each link to zero.

setResidualCap

public void setResidualCap(E e,
                           int cap)

Sets the residual capacity of link e to cap. The previous value, if any, is replaced. No checking is performed to make sure that the given link is in the set of links of the topology. The new capacity can be any integer (positive, negative, zero).

getResidualCap

public int getResidualCap(E e)

Returns the residual capacity of link e. If the given link does not exist, a NullPointerException is thrown (by the JVM).

setCostMap

public void setCostMap(java.util.Map<E,? extends java.lang.Number> cost)

Replaces the current cost map with the parameter cost.

setLinkCap

public void setLinkCap(E e,
                       int cap)

Sets the total capacity of link e to cap. The previous value, if any, is replaced. The new capacity can be any integer (positive, negative, zero).

getLinkCap

public int getLinkCap(E e)

Returns the capacity of link e. If the given link does not exist, a NullPointerException is thrown (by the JVM).

setCost

public void setCost(E e,
                    java.lang.Number n)

Sets the cost of link e to n. The previous value, if any, is replaced. The new cost can be any value.

Note that the values in the cost map can be of any Number derived type, for example Integer, but formal parameter of this method is Number. This opens the possibility to type system violations:

    Map cost = new HashMap();
    ...
    cost.put(a, 100);
    cost.put(b, 200);
    ...
    ted.setCostMap(cost);
    // There would be a type violation here (map holds Integer,
    // cost passed is double).
    ted.setCost(b, 200.5);
    ...
 

This situation is impossible to avoid completely in the today's Java (due to type erasure). To mitigate the possibility of error, this method performs the following before updating the cost map:

• If it is not empty, the new value n must be assignment-compatible to one of the existing values (one element chosen arbitrarily). If not, a runtime exception is thrown.
• If the map is empty, the value is inserted unconditionally. Thus, the caller might find the newly inserted is not of the declared type in that context.

In any case, updating the values of the cost map through a TED instance is rare, since the caller usually already holds a type-safe reference that is easier to use.

Throws:

java.lang.ClassCastException - if the new value (n) is not assignment-compatible with some other value already present in the map.

getCost

public double getCost(E e)

Returns the cost of link e. If the given link does not exist, a NullPointerException is thrown (by the JVM). The value returned is always a double, irrespective of the element's actual type.

getConnection

public ConnectionInfo<V,E> getConnection(int id)

Returns the connection descriptor object for the given connection id, or null if a connection with that id does not exist.

getConnections

public java.util.Collection<ConnectionInfo<V,E>> getConnections()

Returns an unmodifiable view of the connection descriptor objects.

getConnIDs

public java.util.Set<java.lang.Integer> getConnIDs()

Returns an unmodifiable view (as a set) of the connection ids.

getConnCount

public int getConnCount()

Returns the number of connections.

registerConnPerLink

public void registerConnPerLink(ConnectionInfo<V,E> cnx,
                                Path<V,E> path)

Updates the list of connections using the links of a given path. Links are treated as directed, that is, if a connection uses path a--b--c, only links a--b and b--c are considered, never b--a.

unregisterConnPerLink

public void unregisterConnPerLink(ConnectionInfo<V,E> cnx,
                                  Path<V,E> path)

Removes connection cnx from the list of connections passing through the links in path. It does nothing if cnx is null.

registerConnection

public void registerConnection(ConnectionInfo<V,E> cnx)

Register the acceptance of a connection, updates the internal information and informs the corresponding routing algorithm that a connection has been accepted. First, the connection is registered with id cnx.id. Then registerConnPerLink(ConnectionInfo, Path) is called for cnx.wrk_path and cnx.bkp_path.

If cnx.ra is not null, the methods RoutingAlg.commitWorkingPath(ConnectionInfo) and RoutingAlg.commitBackupPath(ConnectionInfo) are called. Note that these methods are ultimately responsible for assigning capacity, typically by calling arranging a call to updateResidualCap(). Thus, with cnx.ra, residual capacity is not maintained.

After registerconnection, the connection descriptor should be treated by the caller as a constant.

releaseConnection

public void releaseConnection(int id)

Release the connection identified by id. If the given connection is not registered, it just returns. If it does exist, performs the actions so as to reverse what is performed in registerConnection(bcds.phison.ra.ConnectionInfo).

updateResidualCap

public void updateResidualCap(ConnectionInfo<V,E> cnx,
                              Path<V,E> path,
                              int delta,
                              boolean bidir)

Updates the residual capacity of links on a given path. Replaces the current residual capacity of the links along path with current_value + delta where delta can be positive or negative.

A link is skipped (its residual capacity is not updated) if:

• It is marked as failed (in any of its two directions)
• It has been repaired (reinstalled) after the connection cnx had been created.

The argument in favour of not updating the residual capacity in the second case above is as follows: Let's suppose a connection uses link e1, which was installed at the beginning (clock=0). The connection creation time is c1 (c1 > 0). If link e1 fails a time f1, but is restored at f2 (f2 > c1 and < connection release time), releasing the connection must not increase the residual capacity, because e1 might have already been started with residual_capacity = link capacity at time f2 (that is, reinstalled anew). If residual capacity is updated ignoring this, bookkeeping errors can easily appear. It is preferable to leave the value in a "sane" state and let the calling entity to handle the whole restoration process.

Parameters:

cnx - the field cnx.clock will be used as the time reference (this is the only field of cnx used in this method. In the future, it might be replaced by a "clock" parameter directly).

path - the residual capacities of the links included in this path are the ones to be updated.

delta - the increment (positive or negative).

bidir - update each link e as well as reverse(e).

updateResidualCap

public void updateResidualCap(ConnectionInfo<V,E> cnx,
                              Path<V,E> path,
                              int delta)

Updates the residual capacity of links on a given path. It is equivalent to the following: updateResidualCap(cnx, path, delta, true);

filterByCap

public SimGraph<V,E> filterByCap(int min_cap)

Returns a subgraph where links with residual capacity less than min_cap are (virtually) removed.

getConnPerLink

public java.util.List<ConnectionInfo<V,E>> getConnPerLink(E e)

Returns a copy of the list of connections passing thourgh a link e.

getConnPerBidiLink

public java.util.List<ConnectionInfo<V,E>> getConnPerBidiLink(E e)

Returns a copy of the list of connections passing thourgh a link e in its both directions.

registerBidiLinkFailure

public void registerBidiLinkFailure(E e)

Registers the failure of links e and reverse(e). The capacities (both residual and link capacity) are left unchanged. Likewise, the list of connections passing through e (in both directions) remains intact.

bidiLinkIsFailed

public boolean bidiLinkIsFailed(E e)

Returns true if link e (either itself or its reverse) is registered as failed.

recoverBidiLink

public void recoverBidiLink(E e,
                            int clock)

Registers that both e and reverse(e) are not in the failed state anymore. The link installation time is set to clock. It does nothing if neither e nor reverse(e) are registered as failed.

retireBidiLinks

public void retireBidiLinks(java.util.Collection<E> failed)

Calls registerBidiLinkFailure(E) for each link in failed and sets the residual capacity of both link directions to zero.

reinstallBidiLinks

public void reinstallBidiLinks(java.util.Collection<E> links,
                               int clock)

Calls recoverBidiLink(E, int) for each element in links and sets the residual capacity of both link directions to the valure returned by getLinkCap(E). The link recovery time is set to clock.

For a link e in links to be reinstalled, bidiLinkIsFailed(e) must return true. Otherwise, the link is just skipped.

getFirstFailedBidiLink

public E getFirstFailedBidiLink(Path<V,E> path)

Returns the first link of path that is currently registered as failed, or null if all links are operative. This method returns the first link of path for which bidiLinkIsFailed(E) returns true, or null if all such calls return false. It also returns null if path is null.

getFailedLinks

public java.util.Set<E> getFailedLinks()

Returns an unmodifiable view of the set of links registered as failed.