Patent JPS5080853A successfully refreshed from Google Patents.
US5561663A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for performing communication rate control using geometric weighted groups
Assignee: Cisco Technology Inc
•
Filing: 1994-12-30
•
Granted: 1996-10-01
•
Expires: 2014-12-30
Abstract
Abstract A method for performing rate control for digital communication systems. A server serves N connection queues where each connection queue has accumulation rate a i . Each credit accumulation rate a i is divided into a set of binary coefficients. The connections are then divided into connection groups wherein each connection group has group accumulation rate created using the binary coefficients. The connection group accumulation rate is used to maintain a group credit balance c j . To select a connection to be served, the server examines the group credit balances and selects the group with the greatest credit balance. A connection within the selected group is chosen using a round-robin system. Thus the server selects a connection to serve without performing a linear scan over all the connections.
Inventors
- 👤 Daniel E. Klausmeier
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 23:27
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/50; H04L47/62; H04L47/621; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L47/52; H04L47/527; H04L47/622; H04L47/6225; H04L49/00; H04L49/30; H04L49/3081; H04L49/90; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L2012/5614; H04L2012/5615; H04L2012/5629; H04L2012/5631; H04L2012/5636; H04L2012/5638; H04L2012/5678; H04L2012/5679
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
113 words
A method of performing rate control on a set of N connections, each of said N connections sharing an available bandwidth of P by having an assigned bandwidth of a i such that each connections' fraction of the total bandwidth is equal to a i /P, said method comprising the steps of: dividing said set of N connections into a set of M connection groups wherein each connection can be added to more than one connection group j; assigning an connection group bandwidth a j to each of said M connection groups; and selecting connection groups to serve such that each connection group receives its assigned connection group bandwidth of a j .
Claim 2
Independent Claim
113 words
A method of performing rate control on a set of N connections, each of said N connections sharing an available bandwidth of P by having an assigned bandwidth of a i such that each connections' fraction of the total bandwidth is equal to a i /P, said method comprising the steps of: dividing said set of N connections into a set of M connection groups wherein each connection can be added to more than one connection group j; assigning an connection group bandwidth a j to each of said M connection groups; and selecting connection groups to serve such that each connection group receives its assigned connection group bandwidth of a j .
Claim 3
Dependent Claim
70 words
The method as claimed in claim 1 further comprising the steps of: assigning an connection group credit balance c j for each connection group j; adding the connection group bandwidth a j of each connection group j to the connection group credit balance c j of each connection group j; and selecting an connection group to serve using the connection group credit balances c j of said M connection groups.
Claim 4
Dependent Claim
29 words
The method as claimed in claim 2 wherein said step of selecting an connection group to be served comprises selecting an connection group that exceeds an associated service threshold.
Claim 5
Dependent Claim
29 words
The method as claimed in claim 3 wherein said step of selecting an connection group to be served further comprises selecting an connection group with the greatest credit balance.
Claim 6
Dependent Claim
25 words
The method as claimed in claim 2 wherein only one connection is served from a connection group when that connection group is selected for service.
Claim 7
Dependent Claim
28 words
The method as claimed in claim 5 wherein said step of serving an connection group comprises serving one connection in said selected connection group using a round-robin approach.
Claim 8
Dependent Claim
26 words
The method as claimed in claim 2 wherein more than one connection is served from a connection group when that connection group is selected for service.
Claim 9
Dependent Claim
73 words
The method as claimed in claim 1 further comprising the steps of: dividing the assigned bandwidth a i for each connection i into a set of sub bandwidths a ij wherein ##EQU6## and w j =A weight factor for connection group j i ; placing connection i into connection group j if a ij does not equal zero; and setting the connection group bandwidth a j for each connection group j using ##EQU7##
Claim 10
Dependent Claim
70 words
The method as claimed in claim 8 further comprising the steps of: assigning an connection group credit balance c j for each connection group j; adding the connection group bandwidth a j of each connection group j to the connection group credit balance c j of each connection group j; and selecting an connection group to serve using the connection group credit balances c j of said M connection groups.
Claim 11
Dependent Claim
14 words
The method as claimed in claim 8 wherein w j equals 2 j .
Claim 12
Dependent Claim
14 words
The method as claimed in claim 8 wherein w j equals n j .
Claim 13
Dependent Claim
45 words
The method as claimed in claim 8 further comprising the step of: serving each connection i in each connection group j such that each connection i receives a fraction of connection group j's assigned bandwidth equal to [(a ij ×W j )/a j ] ##EQU8##
Claim 14
Dependent Claim
56 words
The method as claimed in claim 11 wherein the number M of connection groups required is defined by ##EQU9## wherein bw max = the maximum bandwidth that may be assigned to any given connection; gran min = the minimum desired granularity of the assigned connection bandwidths; and [] = indicates round up to the nearest integer.
Claim 15
Independent Claim
129 words
An apparatus for performing rate control on a set of N connections, each of said N connections having an bandwidth of a i , said apparatus comprising: a front end circuit for receiving incoming data cells; a plurality of queues for storing incoming data cells from said N connections; a server for serving said incoming data cells on said queues; and a service controller, said service controller comprising means for dividing said set of N connections into a set of M connection groups wherein each of said connections may be added to more than one connection group; means for assigning a group bandwidth a j for each connection group; and means for servicing said connection groups such that each connection group receives its assigned group bandwidth a j .
Claim 16
Independent Claim
129 words
An apparatus for performing rate control on a set of N connections, each of said N connections having an bandwidth of a i , said apparatus comprising: a front end circuit for receiving incoming data cells; a plurality of queues for storing incoming data cells from said N connections; a server for serving said incoming data cells on said queues; and a service controller, said service controller comprising means for dividing said set of N connections into a set of M connection groups wherein each of said connections may be added to more than one connection group; means for assigning a group bandwidth a j for each connection group; and means for servicing said connection groups such that each connection group receives its assigned group bandwidth a j .
Claim 17
Dependent Claim
67 words
The apparatus as claimed in claim 14 wherein said service controller further comprises: a group credit balance c j counter for each connection group j; means for adding the group bandwidth a j of each connection group j to the group credit balance c j counter of each connection group j; and means for selecting a group to serve using said group credit balance c j counters.
Claim 18
Dependent Claim
96 words
The apparatus as claimed in claim 14 wherein said service controller further comprises: means for dividing the bandwidth a i for each connection i into a set of sub bandwidth rates a ij wherein ##EQU10## and w j =A weight factor for connection group j i means for placing each connection i into at least one connection group j wherein connection i is assigned to connection group j if a ij does not equal zero; and means for assigning a group bandwidth a j to each connection group j, said group bandwidth rate defined by ##EQU11##
Claim 19
Dependent Claim
15 words
The apparatus as claimed in claim 16 wherein each w j equals 2 j .
Claim 20
Dependent Claim
15 words
The apparatus as claimed in claim 16 wherein each w j equals n j .
Claim 21
Dependent Claim
28 words
The apparatus as claimed in claim 15 wherein said means for selecting a connection group to be served selects a connection group that exceeds an associated service threshold.
Claim 22
Dependent Claim
28 words
The apparatus as claimed in claim 19 wherein said means for selecting a connection group to be served selects a connection group that has the greatest credit balance.
Claim 23
Dependent Claim
30 words
The apparatus as claimed in claim 19 wherein said means for serving a connection serves a single connection in said selected connection group to be served using a round-robin approach.
Claim 24
Dependent Claim
24 words
The apparatus as claimed in claim 19 wherein said means for serving a connection serves more than one connection in said selected connection group.
Claim 25
Dependent Claim
55 words
The apparatus as claimed in claim 18 wherein the number M of connection groups required is defined by ##EQU12## wherein bw max = the maximum bandwidth that may be assigned to any given channel; gran min = the minimum desired granularity of the assigned channel bandwidths; and []= indicates round up to the nearest integer.
References Cited (Backward Citations)
US5224099A
Cited
US5381407A
Cited
EP0598485A2
Cited
US5274643A
Cited
US5359592A
Cited
US5392280A
Cited
US5455826A
Cited
US5432824A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-10-01 | 2000-04-01 | 2000-10-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-10-01 | 2004-04-01 | 2004-10-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-10-01 | 2008-04-01 | 2008-10-01 | $7700.00 | Window Closed / Lapsed |