Power spectrum-based connection admission control for ATM networks

• US 6,075,770 A
• Filed: 11/20/1996
• Issued: 06/13/2000
• Est. Priority Date: 11/20/1996
• Status: Expired due to Term

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Wang, Yao-Tzung, Chi, Hung-Ming, Cheng, Ray-Guang, Chang, Chung-Ju, Lin, Tzung-Pao
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): YAO, KWANG BIN
• Application Number:
  US08/749,371
• Time in Patent Office: 1,301 Days
• Field of Search: 370/229, 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/238, 370/252, 370/253, 370/395, 370/396, 370/398, 370/412, 370/413, 370/415, 370/417, 370/465
• US Class Current: 370/395.21
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5634 In-call negotiation
• CPC Class Codes: H04L 2012/5684 Characteristics of traffic flows
• CPC Class Codes: H04L 49/309 Header conversion, routing tables or routing tags
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method and system are disclosed for constructing a power spectrum based connection admission control table and using such a table in a communications network, such as an ATM network. Power spectrum parameters, such as the power spectrum DC component γ, half power bandwidth B_w and average power Ψ_w are transformed to γ, an equivalent half power bandwidth B_e and an equivalent average power Ψ_e, where B_e is a predetermined constant. Since B_e is constant, the transformation reduces the memory requirements for constructing a connection admission control table.

Claims

1. A method for constructing a power spectrum based connection admission control table including the steps of:

(a) using a predetermined scheduling policy and a predetermined quality of service for communications, determining a maximum equivalent aggregate average power Ψ

_max of an arrival rate of cells for all calls admitted to a node, which maintains said predetermined quality of service, as a function of at least an aggregate power spectrum DC component γ

_T but not as a function of a constant equivalent half-power bandwidth B_e of said arrival rate of cells for all calls, for which B_e individual component equivalent average powers Ψ

_e are determined for all calls,

(b) storing the value of Ψ

_max determined in step (a) in a table entry that is indexed by at least the value of γ

_T used to determined said stored value of Ψ

_max, and

(c) repeating steps (a)-(b) for multiple different values of γ

_T in a range of expected values for γ

_T.

2. The method of claim 1 further comprising the step of using a queue-least threshold scheduling policy.

3. The method of claim 1 wherein said step (a) further comprises the step of determining said constant B_e as a value less than each expected half power bandwidth value B_w of each call set up request.

4. The method of claim 1 wherein said connection admission control table is used to admit type-1 traffic calls for streamed communications and type-2 traffic calls for transactional communications, wherein received type-1 traffic cells of admitted calls are buffered in said node in a separate queue from received type-2 traffic cells until said admitted cells are routed onto an outgoing link from said node, said method further comprising the steps of:

(d) prior to performing step (a), determining a maximum aggregate cell arrival rate Γ

_max of all type-2 traffic calls that can be accommodated by said node, and

(e) repeating steps (a)-(c) for same multiple values of γ

_T once for each of multiple different values of an aggregate cell arrival rate Γ

_T for all admitted type-2 traffic calls between 0 and Γ

_max,

wherein said step (a) comprises determining Ψ

_max as a function of a value of Γ

_T for admitted type-2 traffic calls as well as said value of γ

_T for admitted type-1 traffic calls,

wherein said step (b) comprises storing said value Ψ

_max in a table entry that is indexed by said value of Γ

_T as well as said value of γ

_T used to determine said value of Ψ

_max in said step (a).

5. A method for admitting calls using a power spectrum based connection admission control table comprising the steps of:

(a) producing power spectrum DC component γ

, half power bandwidth B_w, and average power Ψ

_w parameters of a cell arrival rate of a new call,

(b) transforming the three parameters γ

, B_w, Ψ

_w to two parameters γ and

an equivalent average power Ψ

_e, for a predetermined constant B_e,

(c) retrieving from a predetermined table, a maximum aggregate equivalent average power Ψ

_max that can be accommodated by a node for all admitted calls which Ψ

_max is indexed by at least a sum of an aggregate power spectrum DC component γ

_T for all calls currently admitted at said node and γ

, and

(d) determining whether or not to admit said new call by comparing a sum of an aggregate average power Ψ

_T of all calls currently admitted to said node and Ψ

_e to Ψ

_max.

6. The method for claim 5 further comprising the steps of:

(e) receiving in a call set up request from a cell source one or more parameters of said cell arrival rate in the time domain, and

(f) transforming the time domain parameters to the frequency domain to produce said parameters γ

, B_w, Ψ

_w.

7. The method of claim 5 wherein said constant B_e is selected so as to be less than each expected value of B_w, said method further comprising the step of:

(e) low pass filtering and integrating Ψ

_w to produce Ψ

_e.

8. The method of claim 5 further comprising the step of:

in response to admitting a call to said node;

(e) increasing γ

_T and Ψ

_T by the values γ and

Ψ

_e of said admitted call, and

(f) storing in a second table entry said values of γ and

Ψ

_e of said admitted call if there is at least one said admitted call.

9. The method of claim 8 further comprising the step of:

in response to disestablishing a call previously admitted to said node;

(g) retrieving said parameters γ and

Ψ

_e of the disestablished call, and

(h) reducing γ

_T and Ψ

_T by the retrieved values of γ and

Ψ

_e from step (g).

10. The method of claim 5 wherein said node admits both type-1 traffic calls for streamed communications and type-2 traffic calls for transactional communications, said method further comprising the steps of:

(e) maintaining an aggregate cell arrival rate parameter Γ

_max of all type-2 traffic calls admitted to said node and said parameters γ

_T and Ψ

_T for all type-1 traffic calls admitted to said node,

wherein said step (c) further comprises the step of using a value Γ

_max as well as the sum of γ

_T and γ

to retrieve Ψ

_max for determining whether or not to admit a type-1 traffic call, where said value Γ

_max being a maximum aggregate cell arrival rate.

11. The method of claim 10 further comprising the steps of:

admitting a new type-2 traffic call by;

(f) receiving a cell arrival rate Γ

_new for said admitted type-2 traffic call,

(g) retrieving from said predetermined table a value of Ψ

_max contained in a table entry indexed by the sum of Γ

_T and Γ

_new and γ

_T, and

(h) determining whether or not to admit said new type-2 traffic call by comparing a sum of Γ

_T and Γ

_new to a maximum aggregate cell arrival rate for type-2 traffic calls Γ

_max and by comparing Ψ

_T to the value of Ψ

_max retrieved in said step (g).

12. An apparatus for constructing a power spectrum based connection admission control table comprising:

a processor for, using a predetermined scheduling policy and a predetermined quality of service for communications, determining a maximum equivalent aggregate average power Ψ

_max of an arrival rate of cells for all calls admitted to a node, which maintains said predetermined quality of service, as a function of at least an aggregate power spectrum DC component γ

_T but not as a function of a constant equivalent half-power bandwidth B_e of said arrival rate of cells for all calls, for which B_e individual component equivalent average powers Ψ

_e are determined for all calls, and

a memory for storing each value of Ψ

_max determined by said processor in a table entry that is indexed by at least the value of γ

_T used by said processor to determined said stored value of Ψ

_max, and wherein said processor determines a value of Ψ

_max for multiple different values of γ

_T in a range of expected values for γ

_T.

13. The apparatus of claim 12 wherein said processor uses a queue-least-threshold scheduling policy.

14. The apparatus of claim 12 wherein said processor determines said constant B_e as a value less than each expected half power bandwidth value B_w of each call set up request.

15. The apparatus of claim 12 wherein said table stored in said memory is used to admit type-1 traffic calls for streamed communications and type-2 traffic calls for transactional communications, wherein received type-1 traffic cells of admitted calls are buffered in said node in a separate queue from received type-2 traffic cells until said admitted cells are routed onto an outgoing link from said node,

wherein prior to determining Ψ

_max, said processor determines a maximum aggregate cell arrival rate Γ

_max of all type-2 traffic calls that can be accommodated by said node,

wherein said processor determines Ψ

_max for the same multiple values of γ

_T once for each of multiple different values, between 0 and Γ

_max, of an aggregate cell arrival rate Γ

_T for all admitted type-2 traffic calls,

wherein said processor determines Ψ

_max as a function of a value of Γ

_T for admitted type-2 traffic calls as well as said value of γ

_T for admitted type-1 traffic calls, and

wherein said memory stores said value Ψ

_max in a table entry that is indexed by said value of Γ

_T as well as said value of γ

_T used to determine said value of Ψ

_max.

16. A node in a communications network comprising:

(a) a first circuit for producing power spectrum DC component γ

, half power bandwidth B_w, and average power Ψ

_w parameters of a cell arrival rate of a new call,

(b) a second circuit for transforming the three parameters γ

, B_w, Ψ

_w to two parameters γ and

an equivalent average power Ψ

_e, for a predetermined constant B_e,

(c) a predetermined power spectrum based connection admission control table for retrieving a maximum aggregate equivalent average power Ψ

_max that can be accommodated by said node for all admitted calls, which Ψ

_max is indexed by at least a sum of an aggregate power spectrum DC component γ

_T for all calls currently admitted at said node and γ

, and for determining whether or not to admit a new call by comparing a sum of an aggregate average power Ψ

_T of all calls currently admitted to said node and Ψ

_e to Ψ

_max.

17. The apparatus of claim 16 wherein said first circuit receives in a call set up request from a cell source one or more parameters of said cell arrival rate in the time domain, and transforms the time domain parameters to the frequency domain to produce said parameters γ

, B_w, Ψ

_w.

18. The apparatus of claim 16 wherein said constant B_e is selected so as to be less than each expected value of B_w, said second circuit further comprising:

(d) a low pass filter and integrator for low pass filtering and integrating Ψ

_w to produce Ψ

_e.

19. The apparatus of claim 16 further comprising:

(e) an accumulator for, in response to admitting a call to said node, increasing γ

_T and Ψ

_T by the values γ and

Ψ

_e of said admitted call, and

(f) a user information table for storing in an entry thereof said values of γ and

Ψ

_e of said admitted call if there is at least one said admitted call.

20. The apparatus of claim 19 wherein in response to disestablishing a call previously admitted to said node, said user information table retrieves said parameters γ

and Ψ

_e of the disestablished call, and said accumulator reduces γ

_T and Ψ

_T by the retrieved values of γ and

Ψ

_e.

21. The apparatus of claim 16 wherein said node admits both type-1 traffic calls for streamed communications and type-2 traffic calls for transactional communications, said apparatus further comprising:

(d) a register maintaining an aggregate cell arrival rate parameter Γ

_T of all type-2 traffic calls admitted to said node and said parameters γ

_T and Ψ

_T for all type-1 traffic calls admitted to said node,

wherein said power spectrum based admission control table uses Γ

_T as well as the sum of γ

_T and γ

to retrieve Ψ

_max for determining whether or not to admit a type-1 traffic call.

22. The apparatus of claim 21 wherein in admitting a new type-2 traffic call, said first circuit produces a cell arrival rate Γ

_new for said admitted type-2 traffic call, said predetermined power spectrum based connection admission control table retrieves a value of Ψ

_max contained in an entry indexed by the sum of Γ

_T and Γ

_new and γ

_T, and produces an indication indicating whether or not to admit said new type-2 traffic call by comparing a sum of Γ

_T and Γ

_new to a maximum aggregate cell arrival rate for type-2 traffic calls Γ

_max and by comparing Ψ

_T to the value of Ψ

_max.