Connections bandwidth right sizing based on network resources occupancy monitoring

• US 6,765,873 B1
• Filed: 06/29/2000
• Issued: 07/20/2004
• Est. Priority Date: 07/13/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Galand, Claude, Le Pennec, Jean-Francois, Fichou, Aline
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Phan, Tri H.
• Application Number:
  US09/607,176
• Time in Patent Office: 1,482 Days
• Field of Search: 370/235, 370/468, 370/230, 370/232, 370/233, 370/234, 370/253, 370/395.21, 370/395.4
• US Class Current: 370/235
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04L 2012/5647 Cell loss
• CPC Class Codes: H04L 2012/5682 Threshold; Watermark
• 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 41/5003 Managing SLA; Interaction between SLA and QoS
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
• CPC Class Codes: H04L 43/091 Measuring contribution of individual network components to actual service level
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/745 Reaction in network
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/826 Involving periods of time
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Disclosed herein is a connection bandwidth management process and system 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 are coupled to at least one buffer in the switching node for queuing packets before they are transmitted over the output link. Each of the communication links supports the traffic of a plurality of user connections statistically multiplexed over the link. Each user connection is allocated an initial agreed-upon bandwidth through the network, with each of the communication links being possibly oversubscribed.

Claims

1. A connection bandwidth management process 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 output links being coupled to at least one buffer in the switching node for queuing packets before they are transmitted over the output link, each of the communication links supporting the traffic of a plurality of user connections statistically multiplexed over the link, each user connection being allocated an initial agreed-upon bandwidth through the network, with each of the communication links being possible oversubscribed, the connection bandwidth management process comprising the steps of:

periodically receiving, in a network monitoring center, link monitoring data on the communication links, and storing the link monitoring data in a computer memory in the network monitoring center;

selecting one monitored link and retrieving the corresponding link monitoring data from the computer memory;

analyzing the link monitoring data for the selected link wherein the link monitoring data includes, for each of the monitored links, a time distribution of the occupancy of the buffer measured during a predetermined monitoring time period;

determining whether the selected link is oversubscribed or not;

upon determining that the selected link is oversubscribed that the link monitoring data for the selected link satisfies at least one predetermined condition, reallocating the bandwidth initially allocated to each of the connections boarded on the selected link, such that the sum of the reallocated bandwidth of the connections boarded on the selected link is less or equal to the total bandwidth capacity of the selected link; and

obtaining the time distribution of the occupancy of the buffer by;

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 measurement of 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 armed during the monitoring period while the amount of packets stored in the buffer at the packet arrival instant was equal or greater than threshold T(1) to T(N), respectively.

2. The connection bandwidth management process of claim 1, 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);

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

3. The connection bandwidth management process of claim 2, 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.

4. The connection bandwidth management process of claim 1, wherein the link monitoring data includes for each of the monitored links an average link utilization data for each of the links, the average link utilization data relying on the counting of packets during a predetermined monitoring time period before they are boarded on the link.

5. The connection bandwidth management process of claim 1, wherein the step of determining whether the link monitoring data for the selected link satisfies at least one predetermined condition, is achieved by testing the buffer occupancy time distribution data and the average link utilization data of the selected link.

6. The connection bandwidth management process of claim 5, further using, for each selected link, the percentage of packets discarded during the predetermined monitoring time period, to determine whether the at least one predetermined condition is satisfied.

7. The connection bandwidth management process of claim 1, further comprising the steps of;

defining, for each communication link, a first parameter indicative of the ratio of oversubscription currently applied to the link, and a second parameter indicative as to whether or not the link has been passed through the connection bandwidth management process, with the first parameter being expressed in percentage of oversubscription and the second parameter being initialized to a value corresponding to the first parameter divided by 100;

defining for each connection a third parameter (CRF) indicative as to whether the connection bandwidth has been already reallocated or not, with the third parameter being initialized to one at connection setup;

comparing for each connection boarded over the selected link, the third parameter to the second parameter of the selected link;

keeping the connection allocated bandwidth unchanged upon determining that the third parameter is equal or greater than the second parameter; and

re-computing the connection bandwidth parameters whereby the connection bandwidth is reallocated, upon determining that the third parameter is equal or greater than the second parameter.

8. The connection bandwidth management process of claim 7, implemented in a Frame Relay network, wherein the connection bandwidth parameters which are recomputed in the re-computing step comprise the committed information rate CIR, the committed burst size Bc, and the excess burst size Be.

9. The connection bandwidth management process of claim 8, wherein the connection bandwidth parameters CIR, Bc, Be are recomputed according to the following formula:

$\mathrm{NCIR}=\frac{\mathrm{CIR}}{\mathrm{LRF}}$

with CIR being the original CIR allocated at connection setup, and NCIR denoting the re-computed CIR; and

$\mathrm{NBc}=\frac{\mathrm{Bc}}{\mathrm{LRF}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{NBe}=\left(\mathrm{Bc}-\mathrm{NBc}\right)+\mathrm{Be}$

with NBc and NBe respectively denoting the re-computed Bc and the re-computed Be, such that the same amount of traffic is accepted through the network for the connection after its committed information rate CIR has been re-computed.

10. The connection bandwidth management process of claim 1, wherein the step of reallocating the bandwidth initially allocated to each of the connections boarded on the selected link is performed through commands transmitted from the network monitoring center to the origin switching node in which the connection was originally set up.

11. A data processing system 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 output links being coupled to at least one buffer in the switching node for queuing packets before they are transmitted over the output link, each of the communication links supporting the traffic of a plurality of user connections statistically multiplexed over the link, each user connection being allocated an initial agreed-upon bandwidth through the network, with each of the communication links being possibly oversubscribed, the data processing system comprising:

means for periodically receiving, in a network monitoring center, link monitoring data on the communication links, and storing the link monitoring data in a computer memory in the network monitoring center;

means for selecting one monitored link and retrieving the corresponding link monitoring data from the computer memory;

means for analyzing the link monitoring data for the selected link, wherein the link monitoring data includes, for each of the monitored links a time distribution of the occupancy of the buffer measured during a predetermined monitoring time period;

means for determining whether the selected link is oversubscribed or not;

means for, upon determining that the selected link is oversubscribed and that the link monitoring data for the selected link satisfies at least one predetermined condition, reallocating the bandwidth initially allocated to each of the connections boarded on the selected link, such that the sum of the reallocated bandwidth of the connections boarded on the selected link is less or equal to the total bandwidth capacity of the selected link; and

means for obtaining the time distribution of the occupancy of the buffer by;

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;

whereby the measurement of 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 threshold T(1) to T(N), respectively.

12. The data processing system of claim 11, 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);

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

13. The data processing system of claim 12, 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.

14. The data processing system of claim 11, wherein the link monitoring data includes for each of the monitored links an average link utilization data for each of the links, the average link utilization data relying on the counting of packets during a predetermined monitoring time period before they are boarded on the link.

15. The data processing system of claim 11, wherein the means for determining whether the link monitoring data for the selected link satisfies at least one predetermined condition, tests the buffer occupancy time distribution data and the average link utilization data of the selected link.

16. The data processing system of claim 15, further including means, for each selected link, that use the percentage of packet discarded during the predetermined monitoring time period to determine whether the at least one predetermined condition is satisfied.

17. The data processing system of claim 11, further comprising.

means for defining, for each communication link, a first parameter indicative of the ratio of oversubscription currently applied to the link, and a second parameter indicative as to whether or not the link has been passed through the connection bandwidth management process, with the first parameter being expressed in percentage of oversubscription and the second parameter being initialized to a value corresponding to the first parameter divided by 100;

means for defining for each connection a third parameter (CRF) indicative as to whether the connection bandwidth has been already reallocated or not, with the third parameter being initialized to one at connection setup;

means for comparing for each connection boarded over the selected link, the third parameter to the second parameter of the selected link;

means for keeping the connection allocated bandwidth unchanged upon determining that the third parameter is equal or greater than the second parameter; and

means for re-computing the connection bandwidth parameters whereby the connection bandwidth is reallocated, upon determining that the third parameter is equal or greater than the second parameter.

18. The data processing system of claim 17, wherein the data processing system is implemented in a Frame Relay network, and wherein the connection bandwidth parameters which are re-computed in the re-computing step comprise the committed information rate CIR, the committed burst size Bc, and the excess burst size Be.

19. The data processing system of claim 18, wherein the connection bandwidth parameters CIR, Bc, Be are re-computed according to the following formula:

$\mathrm{NCIR}=\frac{\mathrm{CIR}}{\mathrm{LRF}}$

with CIR being the original CIR allocated at connection setup, and NCIR denoting the re-computed CIR; and

$\mathrm{NBc}=\frac{\mathrm{Bc}}{\mathrm{LRF}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{NBe}=\left(\mathrm{Bc}-\mathrm{NBc}\right)+\mathrm{Be}$

with NBc and NBe respectively denoting the re-computed Bc and the re-computed Be,

such that the same amount of traffic is accepted through the network for the connection after its committed information rate CIR has been re-computed.

20. The data processing system of claim 11, wherein the means for reallocating the bandwidth initially allocated to each of the connections boarded on the selected link use commands transmitted from the network monitoring center to the origin switching node in which the connection was originally set up.