Localized congestion mitigation for interior gateway protocol (IGP) networks

Abstract

Data defining egress bandwidth utilization on an interface of a node may be obtained and a congestion event may be detected based at least in part on an average interface utilization (Y) being greater than a first threshold (X1). A plurality of alternate links that can accommodate excess bandwidth without exceeding the first threshold may be identified. Flows associated with the plurality of alternate links may be filtered based at least in part on business logic macro flow filtering. It may be determined whether the plurality of alternate links pass a diffusing update algorithm (DUAL)-based loop-free path-finding algorithm (LPA) analysis for the destination node prefixes whether the destination node prefixes pass the DUAL-based LPA analysis for the at least one of the plurality of alternate links and a plurality of next hops associated with the at least one of the plurality of alternate links.

What is claimed is: 
     
       1. A non-transitory computer-readable medium storing instructions that, when executed, causes a processor to perform operations, comprising:
 obtaining data defining egress bandwidth utilization on an interface of a node; 
 detecting a congestion event based at least in part on an average interface utilization (Y) being greater than a first threshold (X 1 ); 
 determining a plurality of alternate links that can accommodate excess bandwidth without exceeding the first threshold; 
 identifying destination node prefixes of first filtered flows associated with the plurality of alternate links that are filtered based at least in part on business logic macro flow filtering; 
 determining if the plurality of alternate links pass a diffusing update algorithm (DUAL)-based loop-free path-finding algorithm (LPA) analysis for the destination node prefixes; 
 based at least in part on at least one of the plurality of alternate links passes the DUAL-based LPA analysis for the destination node prefixes, determining if the destination node prefixes pass the DUAL-based LPA analysis for the at least one of the plurality of alternate links and a plurality of next hops associated with the at least one of the plurality of alternate links; 
 based at least in part on the destination node prefixes passing the DUAL-based LPA analysis for the at least one of the plurality of alternate links and the plurality of next hops associated with the at least one of the plurality of alternate links, calculating a flow bandwidth for the first filtered flows; 
 filtering the first filtered flows based at least in part on the flow bandwidth to obtain second filtered flows, the second filtered flows defining a first link among the at least one of the plurality of alternate links; and 
 implementing a mitigation plan based at least in part on the first link. 
 
     
     
       2. The non-transitory computer-readable medium of  claim 1 , the operations further comprising restoring the mitigation plan to a pre-mitigation state comprising:
 capturing egress bandwidth utilization on the interface for which the mitigation plan is implemented; 
 initializing a congestion check interval (T C ); 
 determining if the average interface utilization (Y) at the interface is less than a second threshold (X 2 ) relatively lower than the first threshold (X 1 ); 
 based at least in part on a determination that the average interface utilization (Y) is less than the second threshold (X 2 ), capturing user input for a revertive response; 
 based at least in part on a determination that the average interface utilization (Y) is not less than the second threshold (X 2 ), capturing egress bandwidth utilization metrics on the interface; 
 based at least in part on the user input for the revertive response:
 reverting traffic moving through the first link to a pre-mitigation link; and 
 removing an access list from the node. 
 
 
     
     
       3. The non-transitory computer-readable medium of  claim 1 , the operations further comprising:
 capturing egress bandwidth utilization metrics on the interface of the node; and 
 initializing a congestion check interval (T C ) during which the detecting of the congestion event is performed. 
 
     
     
       4. The non-transitory computer-readable medium of  claim 1 , wherein the detecting of the congestion event further comprises:
 based at least in part on the average interface utilization (Y) being greater than the first threshold (X 1 ), identifying the congestion event; and 
 based at least in part on the average interface utilization (Y) not being greater than the first threshold (X 1 ), capturing egress bandwidth utilization metrics on the interface based at least in part on the average interface utilization (Y) being not greater than first threshold (X 1 ). 
 
     
     
       5. The non-transitory computer-readable medium of  claim 1 , the operations further comprising:
 identifying the alternate links on the node; 
 based at least in part on a determination that the plurality of alternate links cannot accommodate excess bandwidth without exceeding the first threshold (X 1 ), recording the interface of the node for consideration for exclusion as one of the plurality of alternate links; and 
 excluding the interface of the node as a candidate one of the plurality of alternate links. 
 
     
     
       6. The non-transitory computer-readable medium of  claim 1 , the operations further comprising:
 capturing user input for mitigation response; 
 based at least in part on a response to the user input, identifying excess bandwidth (Z) where the excess bandwidth (Z) is equal to the average interface utilization (Y) minus the first threshold (X 1 ); and 
 identifying all flows passing through the interface during a congestion check interval (T C ); 
 obtaining destination addresses of the first filtered flows; and 
 identifying the destination node prefixes from the destination addresses. 
 
     
     
       7. The non-transitory computer-readable medium of  claim 1 , the operations further comprising:
 capturing user input for mitigation response; 
 based at least in part on a response to the user input, identifying excess bandwidth (Z) where the excess bandwidth (Z) is equal to the average interface utilization (Y) minus the first threshold (X 1 ); and 
 identifying all flows passing through the interface in a congestion check interval (T C ); and 
 identifying the destination node prefixes for the first filtered flows using flow top label to prefix mapping. 
 
     
     
       8. The non-transitory computer-readable medium of  claim 1 , the operations further comprising:
 based at least in part on the plurality of alternate links not passing the DUAL-based LPA analysis for the destination node prefixes:
 recording the interface of the node for consideration for exclusion as one of the plurality of alternate links; and 
 excluding the interface of the node as a candidate one of the plurality of alternate links. 
 
 
     
     
       9. The non-transitory computer-readable medium of  claim 1 , the operations further comprising, based at least in part on a first one of the destination node prefixes not passing the DUAL-based LPA analysis for the plurality of alternate links and the plurality of next hops associated with the plurality of alternate links, excluding at least one of the first filtered flows corresponding to the first one of the destination node prefixes. 
     
     
       10. The non-transitory computer-readable medium of  claim 1 , the operations further comprising:
 based at least in part on a first one of the destination node prefixes passing the DUAL-based LPA analysis for the plurality of alternate links and the plurality of next hops associated with the plurality of alternate links, recording at least one of the first filtered flows corresponding to the first one of the destination node prefixes as a candidate for flow mitigation; 
 calculating flow bandwidths for the recorded first filtered flows in a congestion check interval (T C ) time window; 
 arranging the recorded first filtered flows in ascending order of the flow bandwidths; 
 presenting the mitigation plan to a user; 
 based at least in part on a response from the user regarding the mitigation plan:
 pushing flow information to an access list of the node; and 
 enabling the mitigation plan based on the access list. 
 
 
     
     
       11. The non-transitory computer-readable medium of  claim 1 , wherein the filtering of the first filtered flows based at least in part on the flow bandwidth to obtain the second filtered flows comprises filtering the first filtered flows that have bandwidth that is cumulatively equal to or rounded to a higher value of excess traffic (Z). 
     
     
       12. A network controller comprising:
 a processor; and 
 a non-transitory computer-readable media storing instructions that, when executed by the processor, causes the processor to perform operations comprising:
 obtaining data defining egress bandwidth utilization on an interface of a node; 
 detecting a congestion event based at least in part on an average interface utilization (Y) being greater than a first threshold (X 1 ); 
 determining a plurality of alternate links that can accommodate excess bandwidth without exceeding the first threshold; 
 identifying destination node prefixes of first filtered flows associated with the plurality of alternate links that are filtered based at least in part on business logic macro flow filtering; 
 determining if the plurality of alternate links pass a diffusing update algorithm (DUAL)-based loop-free path-finding algorithm (LPA) analysis for the destination node prefixes; 
 based at least in part on at least one of the plurality of alternate links passes the DUAL-based LPA analysis for the destination node prefixes, determining if the destination node prefixes pass the DUAL-based LPA analysis for the at least one of the plurality of alternate links and a plurality of next hops associated with the at least one of the plurality of alternate links; 
 based at least in part on the destination node prefixes passing the DUAL-based LPA analysis for the at least one of the plurality of alternate links and the plurality of next hops associated with the at least one of the plurality of alternate links, calculating a flow bandwidth for the first filtered flows; 
 filtering the first filtered flows based at least in part on the flow bandwidth to obtain second filtered flows, the second filtered flows defining a first link among the at least one of the plurality of alternate links; and 
 implementing a mitigation plan based at least in part on the first link. 
 
 
     
     
       13. The network controller of  claim 12 , the operations further comprising restoring the mitigation plan to a pre-mitigation state comprising:
 capturing egress bandwidth utilization on the interface for which the mitigation plan is implemented; 
 initializing a congestion check interval (T C ); 
 determining if the average interface utilization (Y) at the interface is less than a second threshold (X 2 ) relatively lower than the first threshold (X 1 ); 
 based at least in part on a determination that the average interface utilization (Y) is less than the second threshold (X 2 ), capturing user input for a revertive response; 
 based at least in part on a determination that the average interface utilization (Y) is not less than the second threshold (X 2 ), capturing egress bandwidth utilization metrics on the interface; 
 based at least in part on the user input for the revertive response:
 reverting traffic moving through the first link to a pre-mitigation link; and 
 removing an access list from the node. 
 
 
     
     
       14. The network controller of  claim 12 , the operations further comprising:
 capturing egress bandwidth utilization metrics on the interface of the node; 
 initializing a congestion check interval (T C ) during which the detecting of the congestion event is performed; 
 based at least in part on the average interface utilization (Y) being greater than the first threshold (X 1 ), identifying the congestion event; 
 based at least in part on the average interface utilization (Y) not being greater than the first threshold (X 1 ), capturing egress bandwidth utilization metrics on the interface based at least in part on the average interface utilization (Y) being not greater than first threshold (X 1 ); 
 capturing user input for mitigation response; 
 based at least in part on a response to the user input, identifying excess bandwidth (Z) where the excess bandwidth (Z) is equal to the average interface utilization (Y) minus the first threshold (X 1 ); 
 identifying all flows passing through the interface during a congestion check interval (T C ); and 
 identifying the destination node prefixes. 
 
     
     
       15. The network controller of  claim 12 , the operations further comprising:
 based at least in part on a first one of the destination node prefixes passing the DUAL-based LPA analysis for the plurality of alternate links and the plurality of next hops associated with the plurality of alternate links, recording at least one of the first filtered flows corresponding to the first one of the destination node prefixes as a candidate for flow mitigation; 
 calculating flow bandwidths for the recorded first filtered flows in a congestion check interval (T C ) time window; 
 arranging the recorded first filtered flows in ascending order of the flow bandwidths; 
 presenting the mitigation plan to a user; 
 based at least in part on a response from the user regarding the mitigation plan:
 pushing flow information to an access list of the node; and 
 enabling the mitigation plan based on the access list. 
 
 
     
     
       16. A method of congestion mitigation, comprising:
 obtaining data defining egress bandwidth utilization on an interface of a node; 
 detecting a congestion event based at least in part on an average interface utilization (Y) being greater than a first threshold (X 1 ); 
 determining a plurality of alternate links that can accommodate excess bandwidth without exceeding the first threshold; 
 identifying destination node prefixes of first filtered flows associated with the plurality of alternate links that are filtered based at least in part on business logic macro flow filtering; 
 determining if the plurality of alternate links pass a diffusing update algorithm (DUAL)-based loop-free path-finding algorithm (LPA) analysis for the destination node prefixes; 
 based at least in part on at least one of the plurality of alternate links passes the DUAL-based LPA analysis for the destination node prefixes, determining if the destination node prefixes pass the DUAL-based LPA analysis for the at least one of the plurality of alternate links and a plurality of next hops associated with the at least one of the plurality of alternate links; 
 based at least in part on the destination node prefixes passing the DUAL-based LPA analysis for the at least one of the plurality of alternate links and the plurality of next hops associated with the at least one of the plurality of alternate links, calculating a flow bandwidth for the first filtered flows; 
 filtering the first filtered flows based at least in part on the flow bandwidth to obtain second filtered flows, the second filtered flows defining a first link among the at least one of the plurality of alternate links; and 
 implementing a mitigation plan based at least in part on the first link. 
 
     
     
       17. The method of  claim 16 , further comprising restoring the mitigation plan to a pre-mitigation state comprising:
 capturing egress bandwidth utilization on the interface for which the mitigation plan is implemented; 
 initializing a congestion check interval (T C ); 
 determining if the average interface utilization (Y) at the interface is less than a second threshold (X 2 ) relatively lower than the first threshold (X 1 ); 
 based at least in part on a determination that the average interface utilization (Y) is less than the second threshold (X 2 ), capturing user input for a revertive response; 
 based at least in part on a determination that the average interface utilization (Y) is not less than the second threshold (X 2 ), capturing egress bandwidth utilization metrics on the interface; 
 based at least in part on the user input for the revertive response:
 reverting traffic moving through the first link to a pre-mitigation link; and 
 removing an access list from the node. 
 
 
     
     
       18. The method of  claim 16 , further comprising:
 capturing egress bandwidth utilization metrics on the interface of the node; 
 initializing a congestion check interval (T C ) during which the detecting of the congestion event is performed; 
 based at least in part on the average interface utilization (Y) being greater than the first threshold (X 1 ), identifying the congestion event; 
 based at least in part on the average interface utilization (Y) not being greater than the first threshold (X 1 ), capturing egress bandwidth utilization metrics on the interface based at least in part on the average interface utilization (Y) being not greater than first threshold (X 1 ); 
 capturing user input for mitigation response; 
 based at least in part on a response to the user input, identifying excess bandwidth (Z) where the excess bandwidth (Z) is equal to the average interface utilization (Y) minus the first threshold (X 1 ); 
 identifying all flows passing through the interface during a congestion check interval (T C ); and 
 identifying the destination node prefixes. 
 
     
     
       19. The method of  claim 16 , further comprising:
 based at least in part on a first one of the destination node prefixes passing the DUAL-based LPA analysis for the plurality of alternate links and the plurality of next hops associated with the plurality of alternate links, recording at least one of the first filtered flows corresponding to the first one of the destination node prefixes as a candidate for flow mitigation; 
 calculating flow bandwidths for the recorded first filtered flows in a congestion check interval (T C ) time window; 
 arranging the recorded first filtered flows in ascending order of the flow bandwidths; 
 presenting the mitigation plan to a user; 
 based at least in part on a response from the user regarding the mitigation plan:
 pushing flow information to an access list of the node; and 
 enabling the mitigation plan based on the access list. 
 
 
     
     
       20. The method of  claim 16 , wherein the filtering of the first filtered flows based at least in part on the flow bandwidth to obtain the second filtered flows comprises filtering the first filtered flows that have bandwidth that is cumulatively equal to or rounded to a higher value of excess traffic (Z).