search

sachinites / SPFComputation

This project is about building the unicast routing table by performing the Shortest path tree computation on an input Network Topology(Graph)
GNU General Public License v3.0
8 stars 5 forks source link

Optimization for Existing Backup Computation #43

Closed sachinites closed 4 years ago

sachinites commented 5 years ago

Backup computation need to be optimized heavily.

For example , compute_rlfa() fn computes Compute_and_Store_Forward_SPF() and Compute_PHYSICAL_Neighbor_SPFs for each protection enabled link, which is redundant processing. We must invoke Compute_and_Store_Forward_SPF() and Compute_PHYSICAL_Neighbor_SPFs only once for all protecting links during backup computation.

Pls check for other improvements and optimization. Backup Computation Code is unstable.

Optimization Scopes :

  1. Compute_PHYSICAL_Neighbor_SPFs() and Compute_LOGICAL_Neighbor_SPFs() need optimization, these functions runs SPF on nbrs of Computing router as spf-roots. Consider there are multiple links between computing router and its nbr, we would end up running SPF on nbr as many times as no of links between computing node and nbr. This needs to be optimized.

  2. Issue #2 - Already Raised.

Will Add more, as i am doing More analysis.

  1. If there are multiple links on PLR configured for protections, we must run all required SPFs which are not related to link(s) being protected only once for all computations happening on PLR. For that, we need to have a flat on all nodes of the topology and the flag should be maintained per level, per nexthop type, per PLR.
sachinites commented 4 years ago

fixed with commit : d7f74b453333e33ab40e0f70257b5ec47b1e7cca