Determining feasibility of a network service using a ring analysis

• US 9,596,161 B2
• Filed: 11/20/2015
• Issued: 03/14/2017
• Est. Priority Date: 09/24/2013
• Status: Active Grant

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Inventors: Sella, William Thomas
• Primary Examiner(s): Jagannathan, Melanie
• Application Number:
  US14/947,897
• Publication Number:
  US 20160080234A1
• Time in Patent Office: 480 Days
• US Class Current: 1/1
• CPC Class Codes: H04B 10/032 using working and protection systems H04J14/0287 takes precedence
• CPC Class Codes: H04J 3/085 for ring networks, e.g. SDH/SONET rings, self-healing rings, meashed SDH/SONET networks
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 41/0681 Configuration of triggering conditions
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 41/5019 Ensuring fulfilment of SLA
• CPC Class Codes: H04L 43/067 using time frame reporting
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/091 Measuring contribution of individual network components to actual service level
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/745 Reaction in network
• CPC Class Codes: H04L 67/141 Setup of application sessions admission control or resource allocation in data switching networks H04L47/70

Abstract

A mesh network (such as a mesh Ethernet network) is subdivided into rings. For each ring, a network utilization is assessed in both the clockwise and counter-clockwise directions around the ring. A user requests a particular network service. The network rings that would be utilized by the network service are determined. A maximum utilization of all the network rings utilized by the network service in both clockwise and counter-clockwise directions is determined. The determined maximum utilization is used to determine the feasibility of provisioning the requested network service.

Claims

1. A computer-implemented method for determining feasibility of establishing a connection in a mesh network including a plurality of bidirectional links with different capacities, and a plurality of switching devices, comprising:

(a) monitoring, on a computing device, utilization of bidirectional links connecting the plurality of switching devices;

(b) for both directions of each of the links, determining, on the computing device, a predicted utilization of the link in the direction based on the utilization of the link monitored in (a);

for each of a plurality of rings in the mesh network;

(c) determining, on the computing device, a clockwise bottleneck link in the ring;

(d) determining, on the computing device, a counterclockwise bottleneck link in the ring;

(e) determining, on the computing device, an available bandwidth of the ring based on the clockwise bottleneck link and the counterclockwise bottleneck link;

(f) identifying a set of rings from the plurality of rings to be utilized to provide a requested dedicated network connection between at least two locations; and

(g) determining whether the requested dedicated network connection is feasible based on the available bandwidth determined in (e).

2. The computer-implemented method of claim 1, wherein the determining the available bandwidth (e) comprises determining a normal available bandwidth under normal operation conditions by selecting a minimum of a clockwise available bandwidth and a counterclockwise available bandwidth.

3. The computer-implemented method of claim 2, wherein the clockwise available bandwidth is computed by subtracting a predicted utilization of the clockwise bottleneck link from a capacity of the clockwise bottleneck link, and wherein the counterclockwise available bandwidth is computed by subtracting a predicted utilization of the counterclockwise bottleneck link from a capacity of the counterclockwise bottleneck link.

4. The computer-implemented method of claim 3, wherein the determining (e) further comprises determining a failover available bandwidth under failover operating conditions by performing steps comprising:

(A) identifying a worst-case predicted utilization in the counterclockwise direction by;

(i) identifying a link with the lowest capacity in the counterclockwise direction from among the links in the ring,

(ii) adding a maximum predicated link utilization in the clockwise direction among predicted utilizations of the links in the ring in the clockwise direction, to the predicted link utilization in the counterclockwise direction for each link in the ring,

(iii) subtracting the worst-case predicted utilization in the counterclockwise direction from a capacity of the link with the lowest capacity in the counterclockwise direction,

and

(B) identifying a worst-case predicted utilization in the clockwise direction by;

(i) identifying a link with the lowest capacity in the clockwise direction from among the links in the ring,

(ii) adding a maximum predicted link utilization in the counterclockwise direction, among all predicted utilizations of the links in the ring in the counterclockwise direction, to the predicted link utilization in the clockwise direction for each link in the ring,

(iii) subtracting the worst-case predicted utilization in the clockwise direction from a capacity of the link with the lowest capacity in the clockwise direction, and

(C) selecting a minimum of the worst-case predicted utilization in the counterclockwise direction and the worst-case predicted utilization in the clockwise direction as the available bandwidth for the requested dedicated network connection under failover operation conditions.

5. The computer-implemented method of claim 4, wherein the determining (g) comprises indicating the dedicated network connection as feasible if a minimum of the normal available bandwidth and the failover available bandwidth is greater than a bandwidth requirement specified by the pre-determined service level agreement.

6. The computer-implemented method of claim 1, wherein the dedicated network connection is required to meet a pre-determined service level, the service level comprising a pre-determined bandwidth.

7. The computer-implemented method of claim 1, wherein the pre-determined service level further comprises one or more of latency and jitter.

8. The computer-implemented method of claim 1, wherein the identifying the set of rings (f) is performed using a routing algorithm, wherein the routing algorithm is one of a shortest path algorithm and a weighted shortest path algorithm.

9. The computer-implemented method of claim 4, wherein the determining (g) is further based on a stress score each of the set of rings identified in (f), wherein the stress score for a ring during a time slice is determined based on a predicted utilization of the ring for the time slice under normal operating conditions and a predicted utilization of the ring for the time slice under failover operating conditions.

10. The computer-implemented method of claim 9, further comprising:

(h) in response to determining that the stress score of a ring among the set of rings is above a first pre-determined level, sending an alert to request increasing the capacity of the ring within a pre-determined time interval.

11. The computer-implemented method of claim 9, further comprising:

(h) in response to determining that the stress score of a ring among the plurality of rings is between the first pre-determined level and a second pre-determined level, sending an alert to request immediately increasing the capacity of the ring.

12. The computer-implemented method of claim 10, wherein increasing capacity is performed by one or more of altering the network configuration, adding circuits, and adding switches.

13. A program storage device tangibly embodying a program of instructions executable by at least one machine to perform a method for evaluating utilization of a mesh network including a plurality of switching devices, the method comprising:

(a) monitoring, on a computing device, utilization of bidirectional links connecting the plurality of switching devices;

(b) for both directions of each of the links, determining, on the computing device, a predicted utilization of the link in the direction based on the utilization of the link monitored in (a);

for each of a plurality of rings in the mesh network;

(c) determining, on the computing device, a clockwise bottleneck link in the ring;

(d) determining, on the computing device, a counterclockwise bottleneck link in the ring;

(e) determining, on the computing device, an available bandwidth of the ring based on the clockwise bottleneck link and the counterclockwise bottleneck link;

(f) identifying a set of rings from the plurality of rings to be utilized to provide a requested dedicated network connection between at least two locations; and

(g) determining whether the requested dedicated network connection is feasible based on the available bandwidth determined in (e).

14. The program storage device of claim 13, wherein the determining the available bandwidth (e) comprises determining a normal available bandwidth under normal operation conditions by selecting a minimum of a clockwise available bandwidth and a counterclockwise available bandwidth.

15. The program storage device of claim 14, wherein the clockwise available bandwidth is computed by subtracting a predicted utilization of the clockwise bottleneck link from a capacity of the clockwise bottleneck link, and wherein the counterclockwise available bandwidth is computed by subtracting a predicted utilization of the counterclockwise bottleneck link from a capacity of the counterclockwise bottleneck link.

16. The program storage device of claim 15, wherein the determining (e) further comprises determining a failover available bandwidth under failover operating conditions by performing steps comprising:

(A) identifying a worst-case predicted utilization in the counterclockwise direction by;

(i) identifying a link with the lowest capacity in the counterclockwise direction from among the links in the ring,

(ii) adding a maximum predicated link utilization in the clockwise direction among predicted utilizations of the links in the ring in the clockwise direction, to the predicted link utilization in the counterclockwise direction for each link in the ring,

(iii) subtracting the worst-case predicted utilization in the counterclockwise direction from a capacity of the link with the lowest capacity in the counterclockwise direction,

and

(B) identifying a worst-case predicted utilization in the clockwise direction by;

(i) identifying a link with the lowest capacity in the clockwise direction from among the links in the ring,

(ii) adding a maximum predicted link utilization in the counterclockwise direction, among all predicted utilizations of the links in the ring in the counterclockwise direction, to the predicted link utilization in the clockwise direction for each link in the ring,

(iii) subtracting the worst-case predicted utilization in the clockwise direction from a capacity of the link with the lowest capacity in the clockwise direction, and

(C) selecting a minimum of the worst-case predicted utilization in the counterclockwise direction and the worst-case predicted utilization in the clockwise direction as the available bandwidth for the requested dedicated network connection under failover operation conditions.

17. The program storage device of claim 16, wherein the determining (g) comprises indicating the dedicated network connection as feasible if a minimum of the normal available bandwidth and the failover available bandwidth is greater than a bandwidth requirement specified by the pre-determined service level agreement.

18. The program storage device of claim 13, wherein the dedicated network connection is required to meet a pre-determined service level comprising a pre-determined bandwidth.

19. A system for determining feasibility of establishing a connection in a mesh network including a plurality of bidirectional links with different capacities and a plurality of switching devices comprising:

a computing device;

a monitor module, implemented on the computing device, that monitors the utilization of bidirectional links connecting the plurality of switching devices;

a link predictor module, implemented on the computing device, that, for both directions of each of the links, determines a predicted utilization of the link in the direction based on the monitored utilization of the link; and

a ring evaluator module, implemented on the computing device, that for each of a plurality of rings in the mesh network, (i) determines a clockwise bottleneck link in the ring, (ii) determines a counterclockwise bottleneck link in the ring, and (iii) determines an available bandwidth of the ring based on the clockwise bottleneck link and the counterclockwise bottleneck link.

20. The system of claim 19, further comprising:

a feasibility module, implemented on the computing device, that;

(i) receives a request for a dedicated network connection to be provided by the mesh network between at least two locations;

(ii) identifies which of the plurality of rings would be utilized to provide the requested dedicated network connection between the at least two locations; and

(iii) determines whether the requested dedicated network connection is feasible based on the determined the available bandwidth determined for the plurality of identified rings.