Genie's Tech Blog

Where knowledge has no dimensions

CSPF - The TE Algorithm

Hello Everyone,

Today I thought of sharing with you some understanding on 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. The path is computed using traffic engineering database which takes the extensions of OSPF and IS-IS as input. The resulting route is then used by RSVP-TE. The CSPF in particular and any constraint based routing process requires following inputs:

  1. Bandwidth requirements
  2. Hop limitations
  3. Administrative groups (link colors)
  4. Priority (setup and hold)
  5. Explicit route
  6. Link attributes
  7. Reservable bandwidth of the links (static bandwidth minus the currently reserved bandwidth
Lets now discuss how CSPF works. The following steps are involved in the CSPF process:

The implementation of CSPF in the simlulation is based on the concept of "induced graph" introduced in RFC 2702, which is analogous to a virtual topology. 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

As per Manayya draft "draft-manayya-cspf-00" below is the CSPF process:

  1. CSPF process begins at ingress router with parameters of bandwidth, setup priority, hold priority and method used incase of equal cost multipath such as random, least fill or most-fill. It determines the final destination (Egress router).
  2. It checks for maximum hop count, include and exclude constraints configured.
  3. Check each node for metric and hop count starting with Ingress.
  4. For each node check if endpoint is already visited ,if yes then skip the verification. if not check the link for metric, color and bandwidth (for constraints). The information on each node includes administrative groups (Color), metrics, static bandwidth, reservable bandwidth, and available bandwidth priority level. The information contained in the traffic engineering database should be the same across all routers in the same traffic engineering domain.
  5. If it fails then remove this link.
  6. If it passes then select the link with shortest path to neighbor router, go to next link and repeat the step 4.
  7. Repeat the steps 3 to 5 for all nodes
  8. The result of the CSPF algorithm is formed into a strict-hop ERO (Explicit Route Object)
  9. When the ERO is completed, the ERO is passed to the RSVP (Resource Reservation Protocol) process, where it is used for signaling and establishing the LSP in the network.
  10. If it is not possible to find the path then indicate about not finding a route then retry after retry interval.

 

Courtesy:

http://tools.ietf.org/html/draft-manayya-cspf-00

Hope you enjoyed it.

Cheers...!!!

Comments (1) -

  • Tarique

    10/15/2012 7:51:56 PM |

    Dear Genie,

    Solid post!  Could you give an explanation of Affinity attribute and how CSPF uses this attribute.

    Thanks for all your wonderful efforts!

Comments are closed