US5987031A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for fair dynamic scheduling of available bandwidth rate (ABR) service under asynchronous transfer mode (ATM)
Assignee: Renesas Electronics America Inc
•
Filing: 1997-05-22
•
Granted: 1999-11-16
•
Expires: 2017-05-22
Abstract
Abstract A method for dynamic scheduling of data transmission for a large number of data channels under the available bit rate (ABR) service protocols of asynchronous transfer mode (ATM) uses a schedule table and ready queue. In this method, at each time slot, data channels referenced in the current entry of the schedule table is removed from the schedule table and appended to the ready queue. At each available transmission time slot, an ATM cell is transmitted from the data channel referenced in the record at the head of the ready queue. The data channel is then rescheduled for in the schedule table for the next transmission. The present invention also accommodates data transmission rates related to fractional time slot intervals.
Inventors
- 👤 Michael J. Miller
- 👤 Vladan Djakovic
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 18:45
CPC Classifications
H; H04; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5614; H04L2012/5616; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5635; H04L2012/5678; H04L2012/5679; H04L2012/5681
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
202 words
A method for scheduling data transmission for a plurality of data channels, comprising the steps of: providing a schedule table, said schedule table holding a plurality of entries, each entry of said schedule table being associated with a time slot for data transmission and holding zero or more records of a first type, each record of said first type referencing a data channel having data to be transmitted at said associated time slot; providing a ready queue, said ready queue holding zero or more records of a second type each referencing a data channel having data to be transmitted; at each time slot, (i) removing, from each entry associated with said time slot, any and all said records of said first type, and (ii) including in said ready queue said removed records of said first type as said records of said second type; and whenever data is transmitted, (i) removing, from said ready queue, a record of said second type; (ii) transmitting data from the data channel referenced in said removed record of said second type; (iii) selecting an entry of said schedule table; and (iv) including in said selected entry of said schedule table said removed record of said second type.
Claim 2
Independent Claim
202 words
A method for scheduling data transmission for a plurality of data channels, comprising the steps of: providing a schedule table, said schedule table holding a plurality of entries, each entry of said schedule table being associated with a time slot for data transmission and holding zero or more records of a first type, each record of said first type referencing a data channel having data to be transmitted at said associated time slot; providing a ready queue, said ready queue holding zero or more records of a second type each referencing a data channel having data to be transmitted; at each time slot, (i) removing, from each entry associated with said time slot, any and all said records of said first type, and (ii) including in said ready queue said removed records of said first type as said records of said second type; and whenever data is transmitted, (i) removing, from said ready queue, a record of said second type; (ii) transmitting data from the data channel referenced in said removed record of said second type; (iii) selecting an entry of said schedule table; and (iv) including in said selected entry of said schedule table said removed record of said second type.
Claim 3
Dependent Claim
63 words
A method as in claim 1, wherein each data channel is associated with a transmission time interval representing the number of elapsed time slots between transmissions, said step of selecting an entry of said schedule table selects an entry associated with the time slot which is offset from the time slot at which said transmitting step took place by said transmission time interval.
Claim 4
Dependent Claim
120 words
A method as in claim 1, wherein each data channel is associated with a transmission time interval representing the number of elapsed time slots between transmissions and said record of said second type includes a count representing the time slot at which said record of said second type is included in said ready queue, said step of selecting an entry of said schedule table comprises selecting an entry of said schedule table associated with the time slot which is offset from the time slot at which said transmitting step took place by said transmission time interval, less a difference in elapsed time slots between said count and said time slot at which said transmitting step took place and said count.
Claim 5
Dependent Claim
41 words
A method as in claim 3, wherein if said difference is greater than said transmission time interval, said step of selecting selects an entry associated with the time slot immediately following said time slot at which said transmitting step took place.
Claim 6
Dependent Claim
18 words
A method as in claim 1, wherein said schedule table allocates a single entry to each time slot.
Claim 7
Dependent Claim
53 words
A method as in claim 2, wherein said schedule table allocates a plurality of entries to each time slot, wherein each entry represents, for scheduling purpose, a predetermined fraction of said time slot, and wherein said transmission time interval being expressed in units capable of designating said predetermined fraction of said time slot.
Claim 8
Dependent Claim
53 words
A method as in claim 3, wherein said schedule table allocates a plurality of entries to each time slot, wherein each entry represents, for scheduling purpose, a predetermined fraction of said time slot, and wherein said transmission time interval being expressed in units capable of designating said predetermined fraction of said time slot.
Claim 9
Dependent Claim
58 words
A method as in claim 2, further comprising, prior to each instance of performing said step of selecting an entry from said schedule table, the step of selecting, from a plurality of predetermined values, a value for said transmission time interval, said step of selecting a value selects said plurality of predetermined values according to a predetermined sequence.
Claim 10
Dependent Claim
58 words
A method as in claim 3, further comprising, prior to each instance of performing said step of selecting an entry from said schedule table, the step of selecting, from a plurality of predetermined values, a value for said transmission time interval, said step of selecting a value selects said plurality of predetermined values according to a predetermined sequence.
Claim 11
Dependent Claim
56 words
A method as in claim 1, wherein said records of said second type in said ready queue are maintained in an ordered linked list having a first end and a second end, and wherein said step of removing a record of said second type removes said record from said first end of said ordered linked list.
Claim 12
Dependent Claim
60 words
A method as in claim 1, wherein said records of said second type in said ready queue are maintained in an ordered linked list having a first end and a second end, and wherein said step of including in said ready queue said removed records of first type includes said record at said second end of said ordered linked list.
Claim 13
Dependent Claim
54 words
A method as in claim 1, wherein said step of including in said ready queue said removed record associates in said removed record a skip count, and wherein said step of transmitting data comprises the steps of: updating said skip count; and transmitting said data only when said skip count reaches a predetermined value.
References Cited (Backward Citations)
US5533020A
Cited
US5675576A
Cited
US5748614A
Cited
US5712851A
Cited
US5751709A
Cited
US5706288A
Cited
US5889779A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-15 | 2003-05-17 | 2003-11-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-15 | 2007-05-17 | 2007-11-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-15 | 2011-05-17 | 2011-11-16 | $7700.00 | Window Closed / Lapsed |