Determining feasibility of a network service using a ring analysis

• US 10,284,449 B2
• Filed: 03/09/2017
• Issued: 05/07/2019
• 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:
  US15/454,538
• Publication Number:
  US 20170187599A1
• Time in Patent Office: 789 Days
• 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 is determined. The determined maximum utilization is used to determine the feasibility of provisioning the requested network service.

Claims

1. A method for determining feasibility of establishing a connection in a mesh network including a plurality of links that connect a plurality of network devices, comprising:

(a) identifying a set of rings from a plurality of rings, the set of rings to be utilized to provide a requested dedicated network connection between at least two locations, wherein each ring of the set of rings is associated with;

(i) a corresponding subset of network devices from the plurality of network devices and (ii) a corresponding subset of links from the plurality of links that connect the corresponding subset of network devices;

for each ring of the set of rings;

(b) determining a maximum clockwise ring utilization associated with the ring;

(c) determining a maximum counterclockwise ring utilization associated with the ring; and

(d) determining an available capacity of the ring based on the maximum clockwise ring utilization and the maximum counterclockwise ring utilization; and

(e) based on the available capacities for the rings determined in (d), determining whether the requested dedicated network connection is feasible.

2. The method of claim 1, wherein the determining of (b) comprises:

(i) determining, for each link from the subset of links associated with the ring, a 95th percentile clockwise link utilization; and

(ii) obtaining a maximum value from the 95th percentile clockwise link utilizations determined in (i),

wherein the maximum clockwise ring utilization is the maximum value obtained in (ii).

3. The method of claim 1, wherein the determining of (c) comprises:

(i) determining, for each link from the subset of links associated with the ring, a 95th percentile counterclockwise link utilization; and

(ii) obtaining a maximum value of the 95th percentile counterclockwise link utilizations determined in (i),

wherein the maximum counterclockwise ring utilization is the maximum value obtained in (ii).

4. The method of claim 1, wherein the available capacity for each ring comprises a normal available capacity, and the determining of (d) comprises:

(i) determining a normal maximum utilization for the ring to be a maximum value between the maximum clockwise ring utilization and the maximum counterclockwise ring utilization;

(ii) obtaining a minimum link capacity from a set of link capacities associated with the ring; and

(iii) subtracting the normal maximum utilization determined in (i) from the minimum link capacity obtained in (ii) to obtain the normal available capacity.

5. The method of claim 4, wherein the available capacity for each ring further comprises a failover available capacity, and the determining of (d) further comprises:

(iv) determining a failover ring utilization for the ring to be a sum of the maximum clockwise ring utilization and the maximum counterclockwise ring utilization; and

(v) subtracting the failover ring utilization determined in (iv) from the minimum link capacity obtained in (ii) to obtain the failover available capacity.

6. The method of claim 5, wherein the connection is associated with a bandwidth requirement, and the determining of (e) comprises:

(vi) obtaining a minimum normal available capacity from the normal available capacities obtained in (iii);

(vii) obtaining a minimum failover available capacity from the failover available capacities determined in (v); and

(viii) determining whether the bandwidth requirement is less than or equal to the minimum normal available capacity and the minimum failover available capacity.

7. The method of claim 5, further comprising, for each ring of the set of rings:

(f) calculating a stress score associated with the ring based on the normal available capacity associated with the ring and the failover available capacity associated with the ring.

8. The method of claim 7, wherein the determining the feasibility in (e) is based on the stress scores obtained in (f).

9. The method of claim 7, further comprising, for each ring of the set of rings:

(g) when the stress score of the ring is determined to be above a pre-determined level, sending an alert to request increasing the capacity of the ring within a pre-determined time interval.

10. A program storage device tangibly embodying a program of instructions executable by at least one machine to perform a method for determining a feasibility of establishing a connection in a mesh network including a plurality of links that connect a plurality of network devices, the method comprising:

(a) identifying a set of rings from a plurality of rings, the set of rings utilized to provide a requested dedicated network connection between at least two locations, wherein each ring of the set of rings is associated with;

(i) a corresponding subset of network devices from the plurality of network devices and (ii) a corresponding subset of links from the plurality of links that connect the corresponding subset of network devices;

for each ring of the set of rings;

(b) determining a maximum clockwise ring utilization associated with the ring;

(c) determining a maximum counterclockwise ring utilization associated with the ring; and

(d) determining an available capacity of the ring based on the maximum clockwise ring utilization and the maximum counterclockwise ring utilization; and

(e) based on the available capacities for the rings determined in (d), determining whether the requested dedicated network connection is feasible.

11. The program storage device of claim 10, wherein the determining of (b) comprises:

(i) determining, for each link from the subset of links associated with the ring, a 95th percentile clockwise link utilization; and

(ii) obtaining a maximum value from the 95th percentile clockwise link utilizations determined in (i),

wherein the maximum clockwise ring utilization is the maximum value obtained in (ii).

12. The program storage device of claim 10, wherein the determining of (c) comprises:

(i) determining, for each link from the subset of links associated with the ring, a 95th percentile counterclockwise link utilization; and

(ii) obtaining a maximum value of the 95th percentile counterclockwise link utilizations determined in (i),

wherein the maximum counterclockwise ring utilization is the maximum value obtained in (ii).

13. The program storage device of claim 10, wherein the available capacity for each ring comprises a normal available capacity, and the determining of (d) comprises:

(i) determining a normal maximum utilization for the ring to be a maximum value between the maximum clockwise ring utilization and the maximum counterclockwise ring utilization;

(ii) obtaining a minimum link capacity from a set of link capacities associated with the ring; and

(iii) subtracting the normal maximum utilization determined, in (i) from the minimum link capacity obtained in (ii) to obtain the normal available capacity.

14. The program storage device of claim 13, wherein the available capacity for each ring further comprises a failover available capacity, and the determining of (d) further comprises:

(iv) determining a failover ring utilization for the ring to be a sum of the maximum clockwise ring utilization and the maximum counterclockwise ring utilization; and

(v) subtracting the failover ring utilization determined in (iv) from minimum link capacity obtained in (ii) to obtain the failover available capacity.

15. The program storage device of claim 14, wherein the connection is associated with a bandwidth requirement, and the determining of (e) comprises:

(vi) obtaining a minimum normal available capacity from the normal available capacities obtained in (iii);

(vii) obtaining a minimum failover available capacity from the failover available capacities determined in (v); and

(viii) determining whether the bandwidth requirement is less than or equal to the minimum normal available capacity and the minimum failover available capacity.

16. The program storage device of claim 14, further comprising, for each ring of the set of rings:

(f) calculating a stress score associated with the ring based on the normal available capacity associated with the ring and the failover available capacity associated with the ring;

wherein the determining the feasibility in (e) is based on the stress scores obtained in (f).

17. The program storage device of claim 16, further comprising, for each ring of the set of rings:

(g) when the stress score of the ring is determined to be, above a pre-determined level, sending an alert to request increasing the capacity of the ring within a pre-determined time interval.