## The CSPF Algorithm

CSPF stands for Constraint Shortest Path First.
This constraint-based routing is executed online by Ingress Router.
The CSPF calculates an optimum explicit route (ER), based on
specific constraints. CSPF relies on a Traffic Engineering Database (TED)
to do those calculations. The resulting route is then used by RSVP-TE.

The CSPF in particular and any constraint based routing process requires following
inputs:

- Attributes of the traffic trunks, e.g., bandwidth, link affinities
- Attributes of the links of the network, e.g. bandwidth, delay
- Attributes of the LSRs, e.g. types of signaling protocols supported
- Other topology state information.

There has been no standard for CSPF so far. The implementation of CSPF in
the simulation is based on the concept of "induced graph" introduced in RFC
2702. An induced graph is analogous to a virtual topology in an overlay
model. It is logically mapped onto the physical network through the
selection of LSPs for traffic trunks. CSPF is similar to a normal SPF,
except during link examination, it rejects links without capacity or links
that do not match color constraints or configured policy. The CSPF
algorithm used in the simulation has two phases. In the first phase, all
the links that do not satisfy the constraints of bandwidth are excluded
from the network topology. The link affinity is also examined in this
phase. In the second phase, Dijkstra algorithm is performed.

Dijkstra Algorithm:

Dijkstra(G, w, s):
Initialize-single-source(G,s);
S = empty set;
Q = V[G];
While Q is not empty {
u = Extract-Min(Q);
S = S union {u};
for each vertex v in Adj[u] {
relax(u, v, w);
}
}

In which:

- G: the graph, represented in some way (e.g. adjacency list)
- w: the distance (weight) for each edge (u,v)
- s (small s): the starting vertex (source)
- S (big S): a set of vertices whose final shortest path from s have already been determined
- Q: set of remaining vertices, Q union S = V