Determining feasibility of a network service using a ring analysis

• US 8,699,328 B1
• Filed: 09/24/2013
• Issued: 04/15/2014
• Est. Priority Date: 09/24/2013
• Status: Active Grant

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: TW Telecom Holdings Incorporated (Lumen Technologies, Inc.)
• Inventors: Sella, William Thomas
• Primary Examiner(s): Jagannathan, Melanie
• Application Number:
  US14/034,707
• Time in Patent Office: 203 Days
• US Class Current: 370/224
• 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 evaluating utilization of a mesh network including a plurality of switching devices, comprising:

(a) recording, on a computing device and at a plurality of time slices during a plurality of previous time cycles, utilization of bidirectional links connecting the plurality of switching devices, the time cycles representing periodic time intervals having a pattern of repeated utilization and the time slices representing sub-intervals in the periodic time intervals;

(b) for both directions of each of the links and during each of the plurality of time slices, determining, on the computing device, a predicted utilization of the link in the direction based on the recorded utilization of the link during the time slice in the previous time cycles;

for each of a plurality of rings in the mesh network and for each of the time slices;

(c) determining, on the computing device, a clockwise maximum of the predicted utilizations of the links in the ring in the clockwise direction of the ring during the time slice in the previous time cycles;

(d) determining, on the computing device, a counterclockwise maximum of the predicted utilizations of the links in the ring in the counterclockwise direction of the ring during the time slice in the previous time cycles;

(e) determining, on the computing device, a predicted utilization of the ring for the time slice based on the clockwise maximum and the counterclockwise maximum; and

(f) for each of the plurality of rings, determining, on the computing device, an overall predicted utilization of the ring based on the predicted utilizations for the ring determined in (e) for the respective time slices.

2. The computer-implemented method of claim 1, wherein the determining (e) further comprises determining a predicted utilization of the ring for the time slice under normal operating conditions to be the greater of the clockwise maximum and the counterclockwise maximum.

3. The computer-implemented method of claim 1, wherein the determining (e) further comprises determining a predicted utilization of the ring for the time slice under failover operating conditions to be:

(i) when the clockwise maximum and the counterclockwise maximum are on different edges, the sum of the clockwise maximum and the counterclockwise maximum, and

(ii) when the clockwise maximum and the counterclockwise maximum are on the same edge, the greater of;

(I) the sum of the clockwise maximum and a next highest utilization in the counterclockwise direction and (II) the sum of the counterclockwise maximum and a next highest utilization in the clockwise direction.

4. The computer-implemented method of claim 1, further comprising:

(g) segmenting the mesh network to determine the plurality of rings such that each ring representing a closed loop of switching devices is connected by links.

5. The computer-implemented method of claim 1, further comprising:

(g) segmenting the mesh network to determine an intermediate plurality of rings such that each ring representing a closed loop of switching devices is connected by links; and

(h) determining the plurality of rings based on the intermediate plurality of rings such that each ring representing a closed loop of the intermediate plurality of rings is connected by overlapping switching devices.

6. The computer-implemented method of claim 1, further comprising:

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

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

(i) determining whether the requested dedicated network connection is feasible based on the overall predicted utilizations determined in (f) for the plurality of rings identified in (h).

7. The computer-implemented method of claim 1, further comprising:

(g) determining whether the overall predicted utilization for a ring in the plurality of rings exceeds a threshold; and

(h) when the overall predicted utilization of the ring is determined to exceed the threshold, sending an alert indicating that the ring needs to be modified to accommodate additional traffic.

8. A system for evaluating utilization of a mesh network including a plurality of switching devices, comprising:

a computing device;

a monitor module, implemented on the computing device, that records, at a plurality of time slices during a plurality of previous time cycles, the utilization of bidirectional links connecting the plurality of switching devices, the time cycles representing periodic time intervals having a pattern of repeated utilization and the time slices representing sub-intervals in the periodic time intervals;

a link predictor module, implemented on the computing device, that, for both directions of each of the links and during each of the plurality of time slices, determines a predicted utilization of the link in the direction based on the recorded utilization of the link during the time slice in the previous time cycles; and

a slice evaluator module, implemented on the computing device, that, for each of a plurality of rings in the mesh network and for each of the time slices;

(i) determines a clockwise maximum of the predicted utilizations of the links in the ring in the clockwise direction of the ring during the time slice in previous time cycles, (ii) determines a counterclockwise maximum of the predicted utilizations of the links in the ring in the counterclockwise direction of the ring during the time slice in previous time cycles, and (iii) determines a predicted utilization of the ring for the time slice based on the clockwise maximum and the counterclockwise maximum; and

a ring evaluator module, implemented on the computing device, that, for each of a plurality of rings in the mesh network, determines an overall predicted utilization for the ring based on the predicted utilizations for the ring determined by the slice evaluator module for the respective time slices.

9. The system of claim 8, wherein the slice evaluator module determines a predicted utilization of the ring for the time slice under normal operating conditions to be the greater of the clockwise maximum and the counterclockwise maximum.

10. The system of claim 8, wherein the slice evaluator module determines a predicted utilization of the ring for the time slice under failover operating conditions to be:

(i) when the clockwise maximum and the counterclockwise maximum are on different edges, the sum of the clockwise maximum and the counterclockwise maximum, and

(ii) when the clockwise maximum and the counterclockwise maximum are on the same edge, the greater of;

(I) the sum of the clockwise maximum and a next highest utilization in the counterclockwise direction and (II) the sum of the counterclockwise maximum and a next highest utilization in the clockwise direction.

11. The system of claim 8, further comprising:

a segmentation module that segments the mesh network to determine the plurality of rings such that each ring representing a closed loop of switching devices is connected by links.

12. The system of claim 8, further comprising:

a segmentation module that segments the mesh network to determine an intermediate plurality of rings such that each ring representing a closed loop of switching devices is connected by links; and

a ring aggregation module that determines the plurality of rings based on the intermediate plurality of rings such that each ring representing a closed loop of the intermediate plurality of rings is connected by overlapping switching devices.

13. The system of claim 8, further comprising:

a feasibility module 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 overall predicted utilizations for the plurality of identified rings.

14. The system of claim 8, further comprising:

an alert module that;

(i) determines whether the overall predicted utilization for a ring in the plurality of rings exceeds a threshold, and (ii) when the overall predicted utilization of the ring is determined to exceed the threshold, sends an alert indicating that the ring needs to be modified to accommodate additional traffic.

15. 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) recording, on a computing device and at a plurality of time slices during a plurality of previous time cycles, utilization of bidirectional links connecting the plurality of switching devices, the time cycles representing periodic time intervals having a pattern of repeated utilization and the time slices representing sub-intervals in the periodic time intervals;

(b) for both directions of each of the links and during each of the plurality of time slices, determining, on the computing device, a predicted utilization of the link in the direction based on the recorded utilization of the link during the time slice in the previous time cycles;

for each of a plurality of rings in the mesh network and for each of the time slices;

(c) determining, on the computing device, a clockwise maximum of the predicted utilizations of the links in the ring in the clockwise direction of the ring during the time slice in the previous time cycles;

(d) determining, on the computing device, a counterclockwise maximum of the predicted utilizations of the links in the ring in the counterclockwise direction of the ring during the time slice in the previous time cycles;

(e) determining, on the computing device, a predicted utilization of the ring for the time slice based on the clockwise maximum and the counterclockwise maximum; and

(f) for each of the plurality of rings, determining, on the computing device, an overall predicted utilization of the ring based on the predicted utilizations for the ring determined in (e) for the respective time slices.

16. The program storage device of claim 15, wherein the determining (e) further comprises determining a predicted utilization of the ring for the time slice under failover operating conditions to be the sum of the clockwise maximum and the counterclockwise maximum.

17. A computer-implemented method for evaluating utilization of a mesh network including a plurality of switching devices, comprising:

(a) recording, on a computing device and at a plurality of time slices during a plurality of previous time cycles, utilization of bidirectional links connecting the plurality of switching devices, the time cycles representing periodic time intervals having a pattern of repeated utilization and the time slices representing sub-intervals in the periodic time intervals;

(b) for both directions of each of the links and during each of the plurality of time slices, determining, on the computing device, a predicted availability of the link in the direction based on the recorded utilization of the link during the time slice in the previous time cycles;

for each of a plurality of rings in the mesh network and for each of the time slices;

(c) determining, on the computing device, a clockwise minimum of the predicted availability of the links in the ring in the clockwise direction of the ring during the time slice in previous time cycles;

(d) determining, on the computing device, a counterclockwise minimum of the predicted availability of the links in the ring in the counterclockwise direction of the ring during the time slice in previous time cycles;

(e) determining, on the computing device, a predicted availability of the ring for the time slice based on the clockwise and counterclockwise minimums; and

(f) for each of the plurality of rings, determining, on the computing device, an overall predicted availability of the ring based on the predicted availabilities for the ring determined in (e) for the respective time slices.