US6160818A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Traffic management in packet communication networks having service priorities and employing effective bandwidths
Assignee: AT&T Inc
•
Filing: 1997-07-17
•
Granted: 2000-12-12
•
Expires: 2017-07-17
Abstract
Abstract A method is provided for admitting new requests for service in a shared resource having a capacity. The new request has service priority levels associated therewith. In one embodiment of the invention, for example, the shared resource may be a packet communications network and the service request may be a request to admit a new connection. The method proceeds as follows. First, for each service priority level on said shared resource, a total effective bandwidth is generated which is represented by a sum of individual effective bandwidths of previously admitted requests for service. Subsequent to receiving a new request for service having a specified priority of service level, a plurality of effective bandwidths are accessed for the new request. The plurality of effective bandwidths are respectively associated with the specified service priority level and service priority levels therebelow. The new request is admitted if, for the specified service priority level and for each service priority level therebelow, the sum of (i) said total effective bandwidth for a given service priority level and (ii) for said new request, the effective bandwidth at the given service priority is less than the capacity.
Inventors
- 👤 Arthur W. Berger
- 👤 Ward Whitt
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 06:39
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L2012/5629; H04L2012/5631; H04L2012/5632
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
181 words
A method for admitting a new connection having a given service priority level in a packet communications network that includes a plurality of constrained resources including switching nodes and transmission links, each having a capacity, said method comprising the steps of: generating, for each constrained resource that may be selected to effect said new connection, and for each service priority level, a total effective bandwidth represented by a sum of individual effective bandwidths of previously admitted connections; determining a plurality of effective bandwidths for said new connection, said plurality of effective bandwidths respectively being associated with said given service priority level and lower service priority levels, and being based on a loss criterion; admitting said new connection if constrained resources can be selected from among those of said constrained resources for which said step of generating developed said total effective bandwidth, such that for each of the selected resources, for said given priority level of said new connection and for all lower priority levels, the sum of said total effective bandwidth and said determined effective bandwidth is less than said capacity.
Claim 2
Independent Claim
181 words
A method for admitting a new connection having a given service priority level in a packet communications network that includes a plurality of constrained resources including switching nodes and transmission links, each having a capacity, said method comprising the steps of: generating, for each constrained resource that may be selected to effect said new connection, and for each service priority level, a total effective bandwidth represented by a sum of individual effective bandwidths of previously admitted connections; determining a plurality of effective bandwidths for said new connection, said plurality of effective bandwidths respectively being associated with said given service priority level and lower service priority levels, and being based on a loss criterion; admitting said new connection if constrained resources can be selected from among those of said constrained resources for which said step of generating developed said total effective bandwidth, such that for each of the selected resources, for said given priority level of said new connection and for all lower priority levels, the sum of said total effective bandwidth and said determined effective bandwidth is less than said capacity.
Claim 3
Dependent Claim
23 words
The method of claim 1 wherein said plurality of effective bandwidths of said new connection is based on a network end-to-end delay criterion.
Claim 4
Dependent Claim
26 words
The method of claim 1 wherein said plurality of effective bandwidths of said new connection is determined in accordance with an empty-buffer effective bandwidth (EBEB) approximation.
Claim 5
Dependent Claim
30 words
The method of claim 1 wherein said determining step includes the step of retrieving from a database previously calculated values of said plurality of effective bandwidths of said new connection.
Claim 6
Dependent Claim
26 words
The method of claim 1 wherein said determining step includes the step of obtaining measured values for said plurality of effective bandwidths of said new connection.
Claim 7
Dependent Claim
25 words
The method of claim 1 wherein a plurality of said effective bandwidths of at least one type of a new connection have the same value.
Claim 8
Dependent Claim
40 words
The method of claim 1 wherein admitted connections and said new connection are classified into source-types such that connections of a given source-type and a given service priority level have the same respective values for said plurality of effective bandwidths.
Claim 9
Dependent Claim
32 words
The method of claim 1 wherein at least one of said transmission links is defined in terms of the portion of bandwidth on a transmission path that is dedicated to said connections.
Claim 10
Independent Claim
168 words
A method for updating bandwidths upon releasing a connection in a packet communications network that includes a plurality of switching nodes interconnected by transmission links having a capacity, said method comprising the steps of: receiving a request to terminate a connection having a specified level of service priority; for said specified level of service priority and for each service priority level therebelow, accessing a total effective bandwidth represented by a sum of effective bandwidths of previously admitted connections, accessing a plurality of effective bandwidths for said connection to be terminated, said plurality of effective bandwidths respectively representing said specified level of service priority and service priority levels therebelow; for said specified level of service priority and for each service priority level therebelow, generating an updated total effective bandwidth by subtracting, for said connection to be terminated, the effective bandwidth for the given service priority level; and releasing said connection to be terminated wherein said plurality of effective bandwidths of said new connection is based on a loss criterion.
Claim 11
Independent Claim
168 words
A method for updating bandwidths upon releasing a connection in a packet communications network that includes a plurality of switching nodes interconnected by transmission links having a capacity, said method comprising the steps of: receiving a request to terminate a connection having a specified level of service priority; for said specified level of service priority and for each service priority level therebelow, accessing a total effective bandwidth represented by a sum of effective bandwidths of previously admitted connections, accessing a plurality of effective bandwidths for said connection to be terminated, said plurality of effective bandwidths respectively representing said specified level of service priority and service priority levels therebelow; for said specified level of service priority and for each service priority level therebelow, generating an updated total effective bandwidth by subtracting, for said connection to be terminated, the effective bandwidth for the given service priority level; and releasing said connection to be terminated wherein said plurality of effective bandwidths of said new connection is based on a loss criterion.
Claim 12
Dependent Claim
21 words
The method of claim 9 wherein said plurality of effective bandwidths of said new connection is based on a delay criterion.
Claim 13
Dependent Claim
25 words
The method of claim 9 wherein said plurality of effective bandwidths of said new connection is determined in accordance with an empty-buffer effective bandwidth approximation.
Claim 14
Dependent Claim
30 words
The method of claim 9 wherein said accessing step includes the step of retrieving from a database previously calculated values of said plurality of effective bandwidths of said new connection.
Claim 15
Dependent Claim
39 words
The method of claim 9 wherein admitted connections and said released connection are classified into source-types such that connections of a given source-type and a given service priority level have the same values for said plurality of effective bandwidths.
Claim 16
Dependent Claim
32 words
The method of claim 9 wherein at least one of said transmission links is defined in terms of the portion of bandwidth on a transmission path that is dedicated to said connections.
Claim 17
Independent Claim
189 words
A method for dimensioning a link in a packet communications network given: (i) an initial value for capacity of the link, (ii) a classification of possible connections into a given specified level of service priority and source type, (iii) a plurality of effective bandwidths for each said classified connection, said plurality of effective bandwidths respectively being associated with said connection's service priority level and service priority levels therebelow (iv) an offered load vector for said classification of connections, and (v) a blocking criterion, said method comprising the steps of: a. for the capacity of said link and the said plurality of effective bandwidths for each said classified connection, determining an admissible set of said connections; b. determining the fraction of connections that are blocked for each service priority level and each source type, given said admissible set and said offered load vector; c. repeating steps (a)-(b) wherein said link capacity is increased if said fraction of blocked connections exceeds said blocking criterion and said link capacity is decreased if said blocking criterion is satisfied until an incremental decrease in said capacity would cause said blocking criterion to be violated.
Claim 18
Independent Claim
189 words
A method for dimensioning a link in a packet communications network given: (i) an initial value for capacity of the link, (ii) a classification of possible connections into a given specified level of service priority and source type, (iii) a plurality of effective bandwidths for each said classified connection, said plurality of effective bandwidths respectively being associated with said connection's service priority level and service priority levels therebelow (iv) an offered load vector for said classification of connections, and (v) a blocking criterion, said method comprising the steps of: a. for the capacity of said link and the said plurality of effective bandwidths for each said classified connection, determining an admissible set of said connections; b. determining the fraction of connections that are blocked for each service priority level and each source type, given said admissible set and said offered load vector; c. repeating steps (a)-(b) wherein said link capacity is increased if said fraction of blocked connections exceeds said blocking criterion and said link capacity is decreased if said blocking criterion is satisfied until an incremental decrease in said capacity would cause said blocking criterion to be violated.
Claim 19
Dependent Claim
26 words
The method of claim 15 wherein said fraction of connections determined in step (b) is determined in accordance with an algorithm employed in a FIFO network.
Claim 20
Dependent Claim
28 words
The method of claim 10 wherein said link is defined in terms of the portion of bandwidth on a transmission path to be dedicated to the said connections.
Claim 21
Independent Claim
172 words
A method for admitting new requests for service in a shared resource having a capacity, said new requests having service priority levels, said method comprising the steps of: generating, for each service priority level on said shared resource, a total effective bandwidth represented by a sum of individual effective bandwidths of previously admitted requests for service; subsequent to receiving a new request for service having a specified priority of service level, accessing a plurality of effective bandwidths for said new request, said plurality of effective bandwidths respectively being associated with said specified service priority level and service priority levels therebelow; and admitting said new request if, for said specified service priority level and for each said service priority level therebelow, the sum of (i) said total effective bandwidth for a given service priority level and (ii) for said new request, the said effective bandwidth at said given service priority is less than said capacity wherein said plurality of effective bandwidths of said new request for service is based on a loss criterion.
Claim 22
Independent Claim
172 words
A method for admitting new requests for service in a shared resource having a capacity, said new requests having service priority levels, said method comprising the steps of: generating, for each service priority level on said shared resource, a total effective bandwidth represented by a sum of individual effective bandwidths of previously admitted requests for service; subsequent to receiving a new request for service having a specified priority of service level, accessing a plurality of effective bandwidths for said new request, said plurality of effective bandwidths respectively being associated with said specified service priority level and service priority levels therebelow; and admitting said new request if, for said specified service priority level and for each said service priority level therebelow, the sum of (i) said total effective bandwidth for a given service priority level and (ii) for said new request, the said effective bandwidth at said given service priority is less than said capacity wherein said plurality of effective bandwidths of said new request for service is based on a loss criterion.
Claim 23
Dependent Claim
23 words
The method of claim 18 wherein said plurality of effective bandwidths of said new request for service is based on a delay criterion.
Claim 24
Dependent Claim
28 words
The method of claim 18 wherein said plurality of effective bandwidths of said new request for service is determined in accordance with an empty-buffer effective bandwidth (EBEB) approximation.
Claim 25
Dependent Claim
32 words
The method of claim 18 wherein said accessing step includes the step of retrieving from a database previously calculated values of said plurality of effective bandwidths of said new request for service.
Claim 26
Dependent Claim
28 words
The method of claim 18 wherein said accessing step includes the step of obtaining measured values for said plurality of effective bandwidths of said new request for service.
Claim 27
Dependent Claim
14 words
The method of claim 18 wherein said shared resource is a packet communications network.
Claim 28
Independent Claim
145 words
A method for updating occupancy of a shared resource upon releasing a service having a specified level of service priority, in the shared resource having a capacity, said method comprising the steps of: receiving a request to terminate said service; for said specified level of service priority and for each service priority level therebelow, accessing a total effective bandwidth represented by a sum of effective bandwidths of previously admitted services, and accessing a plurality of effective bandwidths for said service to be terminated, said plurality of effective bandwidths respectively representing said specified level of service priority and service priority levels therebelow; generating an updated total effective bandwidth by subtracting from said sum said plurality of effective bandwidths accessed in said step of accessing; and releasing said service to be terminated wherein said plurality of effective bandwidths of said service is based on a loss criterion.
Claim 29
Independent Claim
145 words
A method for updating occupancy of a shared resource upon releasing a service having a specified level of service priority, in the shared resource having a capacity, said method comprising the steps of: receiving a request to terminate said service; for said specified level of service priority and for each service priority level therebelow, accessing a total effective bandwidth represented by a sum of effective bandwidths of previously admitted services, and accessing a plurality of effective bandwidths for said service to be terminated, said plurality of effective bandwidths respectively representing said specified level of service priority and service priority levels therebelow; generating an updated total effective bandwidth by subtracting from said sum said plurality of effective bandwidths accessed in said step of accessing; and releasing said service to be terminated wherein said plurality of effective bandwidths of said service is based on a loss criterion.
Claim 30
Dependent Claim
20 words
The method of claim 24 wherein said plurality of effective bandwidths of said service is based on a delay criterion.
Claim 31
Dependent Claim
24 words
The method of claim 24 wherein said plurality of effective bandwidths of said service is determined in accordance with an empty-buffer effective bandwidth approximation.
Claim 32
Dependent Claim
29 words
The method of claim 24 wherein said accessing step includes the step of retrieving from a database previously calculated values of said plurality of effective bandwidths of said service.
Claim 33
Independent Claim
202 words
A method for dimensioning a shared resource given: (i) an initial value for capacity of the shared source, (ii) a classification of service requests into a given specified level of service priority and source type, (iii) a plurality of effective bandwidths for each of said service requests, where said plurality of effective bandwidths for a service request respectively being associated with a service priority level of said service request and service priority levels lower than the service priority level of said service request (iv) an offered load vector for said classification of service requests, and (v) a blocking criterion, said method comprising the steps of: a. for said capacity and said plurality of effective bandwidths for each of said classified service requests, determining an admissible set of said connections; b. determining a fraction of service requests that are blocked for each service priority level and each source type, given said admissible set and said offered load vector; c. repeating steps (a)-(b) wherein said capacity is increased if said fraction of blocked requests exceeds said blocking criterion and said capacity is decreased if said blocking criterion is satisfied until an incremental decrease in said capacity would cause said blocking criterion to be violated.
Claim 34
Independent Claim
202 words
A method for dimensioning a shared resource given: (i) an initial value for capacity of the shared source, (ii) a classification of service requests into a given specified level of service priority and source type, (iii) a plurality of effective bandwidths for each of said service requests, where said plurality of effective bandwidths for a service request respectively being associated with a service priority level of said service request and service priority levels lower than the service priority level of said service request (iv) an offered load vector for said classification of service requests, and (v) a blocking criterion, said method comprising the steps of: a. for said capacity and said plurality of effective bandwidths for each of said classified service requests, determining an admissible set of said connections; b. determining a fraction of service requests that are blocked for each service priority level and each source type, given said admissible set and said offered load vector; c. repeating steps (a)-(b) wherein said capacity is increased if said fraction of blocked requests exceeds said blocking criterion and said capacity is decreased if said blocking criterion is satisfied until an incremental decrease in said capacity would cause said blocking criterion to be violated.
Claim 35
Dependent Claim
27 words
The method of claim 28 wherein said fraction of service requests determined in step (b) is determined in accordance with an algorithm employed in a FIFO network.
References Cited (Backward Citations)
US5040176A
Cited
US5267232A
Cited
US5121383A
Cited
US5313454A
Cited
US5233604A
Cited
US5309433A
Cited
US5289462A
Cited
US5311513A
Cited
US5347511A
Cited
US5408465A
Cited
US5367523A
Cited
US5359593A
Cited
US5521971A
Cited
US5434848A
Cited
US5790522A
Cited
US5719854A
Cited
US5687167A
Cited
US5838663A
Cited
US5781624A
Cited
US5828653A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-12-12 | 2004-06-12 | 2004-12-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-12-12 | 2008-06-12 | 2008-12-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-12-12 | 2012-06-12 | 2012-12-12 | $7700.00 | Window Closed / Lapsed |