gov.nist.antd.ospf_te
Class PathOptical

java.lang.Object
  |
  +--SSF.OS.ProtocolSession
        |
        +--gov.nist.antd.ospf_te.PathOptical

All Implemented Interfaces:

com.renesys.raceway.DML.Configurable

public class PathOptical

extends ProtocolSession

Dijkstra's shortest path algorithm. Most of the algorithm is taken from Introduction to Algorithms by Cormen, Leiserson and Rivest.

Nested Class Summary

(package private) class

PathOptical.Vertex A node corresponding to a vertex in a graph upon which Dijkstra's algorithm is being run.

Field Summary

(package private) int	count Field count - XXX
(package private) boolean	initialized Field initialized - XXX
private int	num_vertices Total number of vertices in the graph.
(package private) sOSPF_TE	ospf Field ospf - XXX
private java.util.Vector	pq A vector to be used as a priority queue of vertices by distance.
(package private) int	rtrid Field rtrid - XXX
TERoutingTable	TEtable Field TEtable - XXX
private java.util.Hashtable	vertices An table of vertices in the graph upon which Dijkstra's algorithm is being run.

Fields inherited from class SSF.OS.ProtocolSession

name, use

Constructor Summary

PathOptical()

Method Summary

boolean	computed() Returns true if all information initiated and shortest paths calculated.
void	config(com.renesys.raceway.DML.Configuration cfg) Method config Configuration for Constraint Path Computation
void	createDijkstra(java.util.Hashtable G, java.lang.String s, int type) Method createDijkstra XXX
void	createDijkstra(java.util.Hashtable G, java.lang.String s, int type, java.util.Vector ctrt) Constructs a new instance of a Dijkstra's algorithm execution given a graph (where vertices are routers and edges are links) and a source vertex.
private PathOptical.Vertex	extractMax() Extract the node that has the minimum distance from the root.
private PathOptical.Vertex	extractMin() Extract the node that has the minimum distance from the root.
boolean	findAllPaths(int index) Returns the true if all the shortest paths can be found.
java.util.Vector	getRoute(int dest) Method getRoute This routine is to get an explicit route information.
java.util.Vector	getRoute(int dest, java.util.Vector ctrt) Compute the Constraint shortest path tree using the databases and return path lists.
double	getTEweight(java.lang.String nhipref) Returns the distance from the source to the given vertex.
void	init() Method init
void	lsdbcheck() Method lsdbcheck
java.lang.String	nextHop(java.lang.String src, java.lang.String dest) Returns the NHI prefix of the next hop given a destination NHI prefix.
boolean	push(ProtocolMessage message, ProtocolSession fromSession) Method push No action
private void	Relax(PathOptical.Vertex src, PathOptical.Vertex dest, double weight)

Methods inherited from class SSF.OS.ProtocolSession

close, closed, debugIdentifier, inGraph, open, opened, pushAfterDelay, pushAfterDelayFailed, setGraph, version

Methods inherited from class java.lang.Object

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

Field Detail

num_vertices

private int num_vertices

Total number of vertices in the graph.

vertices

private java.util.Hashtable vertices

An table of vertices in the graph upon which Dijkstra's algorithm is being run.

pq

private java.util.Vector pq

A vector to be used as a priority queue of vertices by distance.

rtrid

int rtrid

Field rtrid - XXX

TEtable

public TERoutingTable TEtable

Field TEtable - XXX

count

int count

Field count - XXX

ospf

sOSPF_TE ospf

Field ospf - XXX

initialized

boolean initialized

Field initialized - XXX

Constructor Detail

PathOptical

public PathOptical()

Method Detail

config

public void config(com.renesys.raceway.DML.Configuration cfg)
            throws com.renesys.raceway.DML.configException

Method config Configuration for Constraint Path Computation

Specified by:

config in interface com.renesys.raceway.DML.Configurable

Overrides:

config in class ProtocolSession

Parameters:

cfg - - XXX

Throws:

com.renesys.raceway.DML.configException

init

public void init()
          throws ProtocolException

Method init

Overrides:

init in class ProtocolSession

Throws:

ProtocolException

lsdbcheck

public void lsdbcheck()

Method lsdbcheck

push

public boolean push(ProtocolMessage message,
                    ProtocolSession fromSession)

Method push No action

Specified by:

push in class ProtocolSession

Parameters:

message - - XXX

fromSession - - XXX

Returns:

boolean - XXX

createDijkstra

public void createDijkstra(java.util.Hashtable G,
                           java.lang.String s,
                           int type,
                           java.util.Vector ctrt)

Constructs a new instance of a Dijkstra's algorithm execution given a graph (where vertices are routers and edges are links) and a source vertex.

createDijkstra

public void createDijkstra(java.util.Hashtable G,
                           java.lang.String s,
                           int type)

Method createDijkstra XXX

Parameters:

G - - XXX

s - - XXX

type - - XXX

findAllPaths

public boolean findAllPaths(int index)

Returns the true if all the shortest paths can be found. Returns false otherwise. Refer to RFC2328:16.1.

getTEweight

public double getTEweight(java.lang.String nhipref)

Returns the distance from the source to the given vertex.

Parameters:

nhipref - The NHI prefix address of the router (vertex) to find the distance to.

nextHop

public java.lang.String nextHop(java.lang.String src,
                                java.lang.String dest)

Returns the NHI prefix of the next hop given a destination NHI prefix.

Parameters:

src - The NHI prefix address of the router to find the next hop from.

dest - The NHI prefix address of the router toward which the next hop is to be determined.

extractMin

private PathOptical.Vertex extractMin()

Extract the node that has the minimum distance from the root. If there are ties, take the one with the NHI address which has the smallest lexicographic value.

extractMax

private PathOptical.Vertex extractMax()

Extract the node that has the minimum distance from the root. If there are ties, take the one with the NHI address which has the smallest lexicographic value.

Relax

private void Relax(PathOptical.Vertex src,
                   PathOptical.Vertex dest,
                   double weight)

computed

public boolean computed()

Returns true if all information initiated and shortest paths calculated.

getRoute

public java.util.Vector getRoute(int dest,
                                 java.util.Vector ctrt)

Compute the Constraint shortest path tree using the databases and return path lists.

getRoute

public java.util.Vector getRoute(int dest)

Method getRoute This routine is to get an explicit route information.

Parameters:

dest - - destination IP address

Returns:

Vector - list of Explicit Route