Network capacity planning based on buffers occupancy monitoring

• US 6,690,646 B1
• Filed: 06/27/2000
• Issued: 02/10/2004
• Est. Priority Date: 07/13/1999
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Fichou, Aline, Galand, Claude, Le Pennec, Jean-Francois
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): SHAND, ROBERTA A
• Application Number:
  US09/603,710
• Time in Patent Office: 1,323 Days
• Field of Search: 370/229, 370/230, 370/231, 370/235, 370/236, 370/237, 370/252, 370/253, 370/351, 370/389, 370/395.1, 370/400, 370/412, 370/413, 370/428, 370/429, 709/220, 709/223, 709/224, 709/232, 709/238
• US Class Current: 370/231
• CPC Class Codes: H04L 2012/5623 Network design, dimensioning, topology or optimisation
• CPC Class Codes: H04L 2012/5626 Network management, e.g. Intelligent nets
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/0858 One way delays
• CPC Class Codes: H04L 43/087 Jitter
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method and a system of network capacity planning for use in a high speed packet switching network. The network comprises a plurality of switching nodes interconnected through a plurality of communication links, each of the switching nodes comprises means for switching packets from at least one input link to at least one output link. Each of the output links is coupled to at least one buffer in the switching node for queuing packets before they are transmitted over the output link. In each of the switching nodes and for each of the output links, a time distribution of the occupancy of each buffer during a predetermined monitoring time period is measured, and stored in a centralized memory location. Then, the buffer occupancy time distribution data are retrieved from the centralized memory location in all the switching nodes, gathered and stored in a network dedicated server. These buffer occupancy time distribution data for all the nodes are transmitted from the dedicated network server to a network monitoring center. In the network monitoring center, the buffer occupancy time distribution data are integrated on a larger time scale, and stored. Finally, the integrated buffer occupancy time distribution data are used to apply network capacity planning actions to the network resources.

Claims

1. A network capacity planning method for use in a high speed packet switching network having a plurality of switching nodes interconnected through a plurality of communication links, each of the switching nodes having means for switching packets from at least one input link to at least one output link, each of the at least one output link being coupled to at least one buffer in the switching node for queuing packets before they are transmitted over the output link, comprising the steps of:

in each of the switching nodes and for each of the output links, measuring a time distribution of the occupancy of the at least one buffer during a predetermined monitoring time period; and

storing the buffer occupancy time distribution data measured for each output link in a centralized memory location;

retrieving the buffer occupancy time distribution data stored in the centralized memory location in all the switching nodes,

gathering and storing the retrieved data in a dedicated network server;

transmitting the buffer occupancy time distribution data for all the nodes from the dedicated server to a network monitoring center;

in the network monitoring center, integrating the buffer occupancy time distribution data on a larger time scale, and storing the integrated buffer occupancy time distribution data; and

using the integrated buffer occupancy time distribution data to apply network capacity planning actions.

2. The network capacity planning method of claim 1, wherein the step of measuring in each of the switching nodes and for each of the output link, the time distribution of the occupancy of the at least one buffer during a predetermined monitoring time period, includes, for each of the at least one buffer:

defining a plurality N, with N being an integer, of buffer occupancy thresholds T(1) to T(N), each of the thresholds being indicative of a ratio of the total occupancy of the buffer;

defining a plurality N of buffer states ST(1) to ST(N), each of the states being indicative of the amount of packets stored in the buffer at a given instant in relation to the thresholds T(1) to T(N);

defining a plurality N of counters, PT(1) to PT(N), each of which, PT(i) with i being an integer comprised between 1 and N, being incremented when the buffer state is determined to be at any of the states ST(i) to ST(N).

whereby the step of measuring the time distribution of the occupancy of the at least one buffer during a predetermined monitoring time period is achieved by obtaining a set of N values PT(1) to PT(N) indicating respectively the percentage of packets that have arrived during the monitoring period while the amount of packets stored in the buffer at the packet arrival instant was equal or greater than respectively threshold T(1) to T(N).

3. The network capacity planning method of claim 2, wherein the number N of buffer occupancy thresholds, of buffer states, and counters is four, and wherein the buffer states ST(1) to ST(4) are defined as follows:

ST(1);

Buffer state when T(1)<

=Qsize<

T(2);

ST(2);

Buffer state when T(2)<

=Qsize<

T(3);

ST(3);

Buffer state when T(3)<

=Qsize<

T(4);

ST(4);

Buffer state when Qsize>

=T(4),

wherein “

<

=”

stands for “

less or equal to”

, and “

>

=”

stands for “

greater or equal to”

, and where “

Qsize”

refers to the amount of packets stored in the buffer at a given instant.

4. The network capacity planning method of claim 3, wherein the buffer occupancy thresholds T(1) to T(4) are indicative respectively of 5 percent, 20 percent, 40 percent, and 70 percent of the total occupancy of the buffer.

5. The network capacity planning method of claim 1, wherein the step of integrating the buffer occupancy time distribution data on a larger time scale in the network monitoring center includes averaging the buffer occupancy time distribution measured for each predetermined time period measurement over a long time period, before they are available to be used for applying capacity planning actions.

6. The network capacity planning method of claim 5, wherein the long time period is a day, a week, or a month.

7. The network capacity planning method of claim 2, wherein the step of using the integrated buffer occupancy time distribution data to apply network capacity planning actions includes:

for each of the output link, comparing each one of the plurality N of integrated counters values, PT(1) to PT(N), to respectively at least one predetermined buffer occupancy ratio (FIG. 7A, P1-P7), the result of the comparison determining a type of capacity planning action to be applied to the link.

8. The network capacity planning method of claim 1, further comprising the steps of:

computing and storing in the network monitoring center an average link utilization data for each of the links, the average link utilization data relying on the counting of packets during the predetermined monitoring time period before they are boarded on the link; and

combining, for each communication link, the average link utilization data and the buffer occupancy time distribution data to determine the type of network capacity planning action to be applied to the link.

9. The network capacity planning method of claim 8, wherein for each network output link, the percentage of packet discarded (Packet_Loss) during the predetermined monitoring time period is used, in combination with the average link utilization data and the buffer occupancy time distribution data, to determine the type of network capacity planning action to be applied to the link.

10. The network capacity planning method of claim 1, wherein the network capacity planning actions to be applied to each of the output links, includes at least one of:

rerouting the connections boarded on the link;

stop boarding new connections on the link;

keeping the link monitored;

stop boarding new bursty connections on the link;

boarding new bursty connections if a predetermined condition is fulfilled;

boarding any new non-bursty connection;

boarding new non-bursty connections if a predetermined condition is fulfilled; and

boarding any new connection.

11. The network capacity planning method of claim 1, wherein the network capacity planning actions are applied to the plurality of communication links through a network management console, the network management console transmitting commands corresponding to the capacity planning actions to the centralized memory location in each of the switching nodes.

12. A network capacity planning method for use in a high speed packet switching network having a plurality of switching nodes interconnected through a plurality of communication links, each of the switching nodes having means for switching packets from at least one input link to at least one output link, each of the at least one output link being coupled to at least one buffer in the switching node for queuing packets before they are transmitted over the output link, comprising the steps of:

in each of the switching nodes and for each of the output links, measuring a time distribution of the occupancy of the at least one buffer during a predetermined monitoring time period;

transmitting the buffer occupancy time distribution data for all the nodes to a network monitoring center;

in the network monitoring center, integrating the buffer occupancy time distribution data on a larger time scale, and storing the integrated buffer occupancy time distribution data; and

managing the capacity and utilization of the network according to the integrated buffer occupancy time distribution data.

13. A data processing system network comprising:

a plurality of switching nodes interconnected through a plurality of communication links, each of the switching nodes having means for switching packets from at least one input link to at least one output link, each of the at least one output link being coupled to at least one buffer in the switching node for queuing packets before they are transmitted over the output link;

means for measuring a time distribution of the occupancy of the at least one buffer during a predetermined monitoring time period, in each of the switching nodes and for each of the output links;

means for transmitting the buffer occupancy time distribution data for all the nodes to a network monitoring center;

means for integrating the buffer occupancy time distribution data on a larger time scale, and storing the integrated buffer occupancy time distribution data; and

means for managing the capacity and utilization of the network according to the integrated buffer occupancy time distribution data.