Method and apparatus for congestion control for packet-based networks using call blocking

• US 6,747,953 B1
• Filed: 05/24/2000
• Issued: 06/08/2004
• Est. Priority Date: 05/24/2000
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Wang, Yung-Terng, Park, Kun I., Hernandez-Valencia, Enriq, Qureshi, Muhammed A.
• Primary Examiner(s): Yao, Kwang Bin
• Application Number:
  US09/578,071
• Time in Patent Office: 1,476 Days
• Field of Search: 370/229, 370/230, 370/230.1, 370/231, 370/232, 370/233, 370/234, 370/235, 370/395.2, 370/395.21
• US Class Current: 370/235
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from 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/2416 Real-time traffic
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/745 Reaction in network
• CPC Class Codes: H04L 47/781 Centralised allocation of resources
• CPC Class Codes: H04L 47/801 Real time traffic
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data

Abstract

The invention pertains to methods and apparatus for determining when and how to perform communication network congestion control tactics, such as call blocking, with respect to packet-based networks.

Claims

1. A method of determining call blocking parameters for relieving congestion in a packet-based network that is used to interconnect a plurality of other networks through a plurality of gateways, said method comprising the steps of:

(1) identifying calls that are experiencing performance below a predetermined threshold;

(2) identifying a set of pairs of gateways corresponding to said calls experiencing performance below said predetermined threshold;

(3) calculating an average performance of all calls between each gateway pair in said set; and

(4) generating, for each gateway pair in said set, data indicating that it should reject new calls between said gateway pair if said average performance is below said threshold and admit new calls if said average performance exceeds said threshold.

2. The method set forth in claim 1 wherein said threshold comprises a delay jitter parameter.

3. The method set forth in claim 1 wherein said threshold comprises a packet loss parameter.

4. The method set forth in claim 1 wherein said threshold comprises a delay jitter parameter and a packet loss parameter.

5. The method set forth in claim 1 wherein said threshold comprises a delay jitter parameter or a packet loss parameter.

6. The method set forth in claim 4 further comprising the step of:

(5) for each gateway pair having no calls having performance below said threshold, admitting new calls.

7. The method set forth in claim 6 wherein said network is an internet protocol network.

8. The method set forth in claim 7 wherein said network operates using the Real time Protocol:

RFC 1889, “

RTP;

A Transport Protocol for Real-time Applications.”

9. The method set forth in claim 1 further comprising the step of:

(6) forwarding information as to whether new calls should be admitted or rejected to said gateways for implementation.

10. The method set forth in claim 1 further comprising the step of:

(7) remotely controlling said gateways to admit or reject new calls based on said data generated in step (4).

11. The method set forth in claim 1 wherein step (4) comprises setting a flag corresponding to each gateway pair in said set.

12. A method for implementing call blocking to relieve congestion in a packet-based network that is used to interconnect a plurality of other networks through a plurality of gateway nodes, said network comprising a plurality of ports through which network traffic travels, said method comprising the steps of:

(1) for each port in said network, identifying a set of pairs of gateway nodes contributing traffic to said port; and

(2) identifying ports that are experiencing congestion above a predetermined threshold;

(3) for each pair of gateway nodes contributing traffic to a port identified in step (2), assigning a call blocking probability to said pair of gateway nodes, said call blocking probability being a function of the fraction of calls between said pair of gateway nodes that would need to be blocked to meet said threshold corresponding to a port to which that pair of gateway nodes contributes traffic that is most congested.

13. The method set forth in claim 12 wherein said threshold is a function of accumulated number of calls that can pass through said port and wherein step (2) comprises:

(2.1) determining the accumulated number of calls passing through said port; and

(2.2) comparing said accumulated number of calls to said threshold.

14. The method set forth in claim 13 wherein step (2.1) comprises summing the number of calls between each pair of gateway nodes contributing traffic to said port.

15. The method set forth in claim 13 wherein step (3) comprises:

(3.1) for each port identified in step (2), determining the number of calls per second that can be accommodated at said port without exceeding said threshold;

(3.2) for each port that is experiencing congestion above a predetermined threshold, determining the ratio by which the actual number of calls per second through said port exceeds said threshold;

(3.3) for each pair of gateway nodes that is contributing traffic to at least one congested port, assigning to said pair of gateway nodes the call blocking probability corresponding to the port to which it is contributing traffic that is most congested.

16. The method set forth in claim 15 wherein step (3.1) comprises solving:

$T=\frac{{\left({\mathrm{\alpha <br><br>}}_c/\mathrm{\mu <br><br>}\right)}^c/C!}{\underset{n=0}{\overset{c}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left({\mathrm{\alpha <br><br>}}_c/\mathrm{\mu <br><br>}\right)}^n/n!}$

for α

_C, where

C is a number of calls that can be accommodated at the port as determined by said threshold,

1/μ

is an average holding time per call,

α

_C is said number of calls per second that can be accommodated at that port; and

T=a blocking interval.

17. The method set forth in claim 16 wherein step (3.2) comprises the step of solving ${\alpha }_{}$

A=∑

j=0m-1

λ

Ri,j

where α

_A is an average arrival rate for calls between pairs of gateway nodes, R_i, in said set of gateway nodes contributing traffic to said port, i;

λ

=call arrival rate

R_i=gateway node pair contributing traffic to port i; and

m=number of gateway node pairs contributing traffic to port i.

18. The method set forth in claim 17 wherein said threshold is a fraction of said accumulated number of calls that can pass through said port.

19. The method set forth in claim 17 wherein said blocking probability is determined via:

$B_{i^{\underset{\_}{k}}}=\frac{\left({\mathrm{\lambda <br><br>}}_i/\mathrm{\mu <br><br>}\right)<br><br>M_{i<br><br>\underset{\_}{k}}/M_{i<br><br>\underset{\_}{k}}!}{\underset{n=0}{\overset{M_{i<br><br>\underset{\_}{k}}}{\sum <br><br>}}<br><br>{\left({\mathrm{\lambda <br><br>}}_{i<br><br>\underset{\_}{k}}/\mathrm{\mu <br><br>}\right)}^n/n!}$

wherein M_k is a number of channels corresponding to said call blocking probability for PVG pair k determined in step (3);

λ

_k=call arrival rate for k^th PVG pair; and

B_k=blocking probability assigned to the k^th PVG pair.

20. The method set forth in claim 17 wherein said network is an Internet protocol network.

21. The method set forth in claim 17 further comprising the steps of:

(4) identifying ports that are experiencing traffic below said predetermined threshold;

(5) for each pair of gateway nodes contributing traffic to a port identified in step (4), assigning a call blocking probability to said pair of gateway nodes, said call blocking probability being a function of the fraction of calls that would need to be added between said pair of gateway nodes in order to exceed said threshold corresponding to the port to which that pair of gateway nodes contributes traffic that is most congested.

22. The method set forth in claim 12 further comprising the step of:

(6) forwarding information as to whether new calls should be admitted or rejected to said gateways for implementation.

23. The method set forth in claim 12 further comprising the step of:

(7) remotely controlling said gateways to admit or reject new calls based on said data generated in step (3).

24. An apparatus for implementing call blocking to relieve congestion in a packet-based network that is used to interconnect a plurality of other networks through a plurality of gateways, said apparatus comprising:

means for identifying calls that are experiencing performance below a predetermined threshold;

means for identifying a set of pairs of gateways corresponding to calls experiencing performance below said predetermined threshold;

means for calculating an average performance of all calls between each gateway pair in said set; and

means for generating, for each gateway pair in said set, data indicating that it should reject new calls between said gateway pair if said average performance is below said threshold and admitting new calls if said average performance exceeds said threshold.

25. The apparatus set forth in claim 24 wherein said threshold comprises a delay jitter parameter.

26. The apparatus set forth in claim 24 wherein said threshold comprises packet loss parameter.

27. The apparatus set forth in claim 24 wherein said threshold comprises a delay jitter parameter and a packet loss parameter.

28. The apparatus set forth in claim 24 wherein said threshold comprises a delay jitter parameter or a packet loss parameter.

29. The apparatus set forth in claim 27 further comprising:

(5) means for admitting new calls for each gateway pair having no calls having performance below said threshold.

30. The apparatus set forth in claim 29 wherein said network is an internet protocol network.

31. The apparatus set forth in claim 30 wherein said network operates using the Real time Protocol:

RFC 1889, “

RTP;

A Transport Protocol for Real-time Applications.”

32. The method set forth in claim 24 wherein each of said means is comprises of a data processing device.

33. The apparatus set forth in claim 24 further comprising:

means for forwarding information as to whether new calls should be admitted or rejected to said gateways for implementation.

34. The apparatus set forth in claim 24 further comprising:

means for remotely controlling said gateways to admit or reject new calls based on said data generated in said means for generating.

35. An apparatus for implementing call blocking to relieve congestion in a packet-based network that is used to interconnect a plurality of other networks through a plurality of gateway nodes, said network comprising a plurality of ports through which network traffic travels, said apparatus comprising:

means for identifying ports that are experiencing congestion above a predetermined threshold;

first means for identifying, for each gateway node identified by said means for identifying ports, a set of pairs of gateway nodes contributing traffic to said port; and

means for assigning to each pair of nodes identified by said first means for identifying pairs of gateway nodes a call blocking probability to said pair of gateway nodes, said call blocking probability being a function of the fraction of calls between said pair of gateway nodes that would need to be blocked to meet said threshold corresponding to the port to which that pair of gateway nodes contributes traffic that is most congested.

36. The apparatus set forth in claim 35 wherein said means for identifying ports comprises:

means for determining the accumulated number of calls passing through said port; and

means for comparing said accumulated number of calls to said threshold.

37. The apparatus set forth in claim 36 wherein said means for assigning comprises:

means for determining, for each port identified by said means for identifying ports, the number of calls per second that can be accommodated at said port without exceeding said threshold;

means for determining, for each port identified by said means for identifying ports, the ratio by which the actual number of calls per second through said port exceeds said threshold;

means for assigning to each pair of gateway nodes contributing traffic to said port the call blocking probability corresponding to the port to which it is contributing traffic that is most congested.

38. The apparatus set forth in claim 37 wherein said number of calls per second that can be accommodated at said port without exceeding said threshold is determined by solving:

$T=\frac{{\left({\mathrm{\alpha <br><br>}}_c/\mathrm{\mu <br><br>}\right)}^c/C!}{\underset{n=0}{\overset{c}{\sum <br><br>}}<br><br>{\left({\mathrm{\alpha <br><br>}}_c/\mathrm{\mu <br><br>}\right)}^n/n!}$

for α

_C, where

C is a number of calls that can be accommodated at the port as determined by said threshold,

1/μ

is an average holding time per call,

α

_C is said number of calls per second that can be accommodated at that port; and

T=a blocking interval.

39. The method set forth in claim 38 wherein said means for determining the ratio by which the actual number of calls per second through said port exceeds said threshold solves ${\alpha }_{}$

A=∑

j=0m-1_

λ

Ri,j

where α

_A is an average arrival rate of calls between pairs of gateway nodes, R_i, in said set of pairs of gateway nodes, contributing traffic to said port i;

λ

=call arrival rate;

R_i=gateway node pair contributing traffic to port i;

m=number of gateway node pairs contributing traffic to port i.

40. The apparatus set forth in claim 39 wherein said threshold is a fraction of said capacity of said port.

41. The apparatus set forth in claim 39 wherein said blocking probability is determined via:

${B_i}_{{\text{\hspace{1em}<br><br>}}^{\underset{\_}{k}}}=\frac{{\left({\mathrm{\lambda <br><br>}}_i/\mathrm{\mu <br><br>}\right)}^{M_{i<br><br>\underset{\_}{k}}}/M_{i<br><br>\underset{\_}{k}}!}{\underset{n=0}{\overset{M_{i<br><br>\underset{\_}{k}}}{\sum <br><br>}}<br><br>{\left({\mathrm{\lambda <br><br>}}_{i<br><br>\underset{\_}{k}}/\mathrm{\mu <br><br>}\right)}^n/n!}$

wherein M_k is a number of channels corresponding to said call blocking probability for PVG pair k;

λ

=call arrival rate for K^th PVG pair; and

B_k=blocking probability assigned to the k^th PVG pair.

42. The apparatus set forth in claim 39 wherein said network is an Internet protocol network.

43. The apparatus set forth in claim 39 further comprising:

means for identifying ports that are experiencing traffic below said predetermined threshold;

second means for identifying, for each port experiencing traffic below said predetermined threshold, a set of pairs of gateway nodes contributing traffic to said port; and

means for assigning a call blocking probability to each pair of gateway nodes identified by said second means for identifying pairs of gateway nodes said call blocking probability being a function of the fraction of calls between said pair of gateway nodes that would need to be blocked to meet said utilization threshold corresponding to the port to which that pair of gateway nodes contributes traffic that is least congested.

44. The method set forth in claim 35 further comprising:

means for forwarding information as to whether new calls should be admitted or rejected to said gateways for implementation.

45. The method set forth in claim 35 further comprising:

means for remotely controlling said gateways to admit or reject new calls based on said data generated by said means for assigning.