US5748631A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Asynchronous transfer mode cell processing system with multiple cell source multiplexing
Assignee: Mindspeed Technologies LLC
•
Filing: 1996-05-09
•
Granted: 1998-05-05
•
Expires: 2016-05-09
Abstract
Abstract Methods and apparatus for processing cells in an asynchronous transfer mode (ATM) communication system. An ATM cell processor implements a "bubble" count technique which efficiently accommodates multiple layers of scheduling requests and/or external cell sources. In the case of multiple layers of scheduling requests, first and second primary scoreboards are provided for scheduling/servicing of, for example, higher and lower priority traffic, higher and lower cell rate traffic, or externally and internally generated traffic, respectively. A bubble count is maintained for the second scoreboard, and the count is incremented each time the first scoreboard is serviced and decremented each time an idle slot is encountered on the second scoreboard but not queued for transmission. Scheduling requests for the second scoreboard are then made at a target time plus the bubble count. In the case of multiplexing external and internal cell sources, the bubble count may represent the number of cells that have been sent on a given transmission link but not scheduled in the primary scoreboard, and may be incremented each time the primary scoreboard is serviced, and decremented each time an idle slot on the primary scoreboard is encountered but not queued for transmission.
Inventors
- 👤 Paul V. Bergantino
- 👤 Daniel J. Lussier
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 12:46
CPC Classifications
H; H04; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5629; H04L2012/5631; H04L2012/5636; H04L2012/5638; H04L2012/5646; H04L2012/5652; H04L2012/5672; H04L2012/5678; H04L2012/5679
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
185 words
A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of: providing first and second groups of bits with each bit in the first and second groups representing a cell time slot, wherein the value of a given bit in the first and second group of bits indicates whether or not the corresponding cell time slot has been scheduled for transmission; servicing the scheduled time slots by checking the first group of bits for a bit corresponding to an available time slot, and if no bit corresponding to an available time slot is found, checking the second group of bits for a bit corresponding to an available time slot; maintaining a count which is incremented each time a cell time slot represented by a bit in the first group is serviced, and decremented each time a bit in the second group corresponding to an idle slot is encountered but an idle slot is not transmitted; and scheduling the available time slots represented by bits of the second group at a time determined in part by the count.
Claim 2
Independent Claim
185 words
A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of: providing first and second groups of bits with each bit in the first and second groups representing a cell time slot, wherein the value of a given bit in the first and second group of bits indicates whether or not the corresponding cell time slot has been scheduled for transmission; servicing the scheduled time slots by checking the first group of bits for a bit corresponding to an available time slot, and if no bit corresponding to an available time slot is found, checking the second group of bits for a bit corresponding to an available time slot; maintaining a count which is incremented each time a cell time slot represented by a bit in the first group is serviced, and decremented each time a bit in the second group corresponding to an idle slot is encountered but an idle slot is not transmitted; and scheduling the available time slots represented by bits of the second group at a time determined in part by the count.
Claim 3
Dependent Claim
23 words
The method of claim 1 wherein the first and second groups of bits relate to higher priority traffic and lower priority traffic, respectively.
Claim 4
Dependent Claim
25 words
The method of claim 1 wherein the first and second groups of bits relate to higher cell rate traffic and lower cell rate traffic, respectively.
Claim 5
Dependent Claim
25 words
The method of claim 1 wherein the first and second groups of bits relate to external cell source traffic and internal cell source traffic, respectively.
Claim 6
Independent Claim
139 words
A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of: providing a group of bits with each bit in the group of bits representing a cell time slot, wherein the value of a given bit in the group of bits indicates whether or not the corresponding cell time slot has been scheduled for transmission; maintaining a count, wherein the count is incremented each time a cell not scheduled using a bit in the group of bits is sent on a transmission link of the communication system, and decremented each time a bit in the group corresponding to an idle slot is encountered but an idle slot is not transmitted; and scheduling the available time slots represented by bits of the group at a time determined in part by the count.
Claim 7
Independent Claim
139 words
A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of: providing a group of bits with each bit in the group of bits representing a cell time slot, wherein the value of a given bit in the group of bits indicates whether or not the corresponding cell time slot has been scheduled for transmission; maintaining a count, wherein the count is incremented each time a cell not scheduled using a bit in the group of bits is sent on a transmission link of the communication system, and decremented each time a bit in the group corresponding to an idle slot is encountered but an idle slot is not transmitted; and scheduling the available time slots represented by bits of the group at a time determined in part by the count.
Claim 8
Independent Claim
215 words
A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of: providing first and second groups of bits with each bit in the first and second groups representing a cell time slot, wherein the value of a given bit in the first and second group of bits indicates whether or not the corresponding cell time slot has been scheduled for transmission; servicing the scheduled time slots by checking the first group of bits for a bit corresponding to an available time slot, and if no bit corresponding to an available time slot is found, checking the second group of bits for a bit corresponding to an available time slot; maintaining a count which is incremented each time a cell time slot represented by a bit in the first group is serviced, and decremented each time a bit in the second group corresponding to an idle slot is encountered but an idle slot is not transmitted; and scheduling the available time slots represented by bits of the second group at a time determined in part by scheduling a time slot at a time corresponding to the sum of a target time for the corresponding scheduling request and the count value at the time the scheduling request is received.
Claim 9
Independent Claim
215 words
A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of: providing first and second groups of bits with each bit in the first and second groups representing a cell time slot, wherein the value of a given bit in the first and second group of bits indicates whether or not the corresponding cell time slot has been scheduled for transmission; servicing the scheduled time slots by checking the first group of bits for a bit corresponding to an available time slot, and if no bit corresponding to an available time slot is found, checking the second group of bits for a bit corresponding to an available time slot; maintaining a count which is incremented each time a cell time slot represented by a bit in the first group is serviced, and decremented each time a bit in the second group corresponding to an idle slot is encountered but an idle slot is not transmitted; and scheduling the available time slots represented by bits of the second group at a time determined in part by scheduling a time slot at a time corresponding to the sum of a target time for the corresponding scheduling request and the count value at the time the scheduling request is received.
Claim 10
Independent Claim
238 words
A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of: providing first and second groups of bits with each bit in the first and second groups representing a cell time slot, wherein the value of a given bit in the first and second group of bits indicates whether or not the corresponding cell time slot has been scheduled for transmission; servicing the scheduled time slots by checking the first group of bits for a bit corresponding to an available time slot, and if no bit corresponding to an available time slot is found, checking the second group of bits for a bit corresponding to an available time slot; maintaining a count which is incremented each time a cell time slot represented by a bit in the first group is serviced, and decremented each time a bit in the second group corresponding to an idle slot is encountered but an idle slot is not transmitted; and scheduling the available time slots represented by bits of the second group at a time determined by executing an instruction which specifies a target address in the second group of bits and returns an indication as to whether or not a scheduled time slot exists in the second group in a range from the bit corresponding to the target address to the bit corresponding to the sum of the target address and the count.
Claim 11
Independent Claim
238 words
A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of: providing first and second groups of bits with each bit in the first and second groups representing a cell time slot, wherein the value of a given bit in the first and second group of bits indicates whether or not the corresponding cell time slot has been scheduled for transmission; servicing the scheduled time slots by checking the first group of bits for a bit corresponding to an available time slot, and if no bit corresponding to an available time slot is found, checking the second group of bits for a bit corresponding to an available time slot; maintaining a count which is incremented each time a cell time slot represented by a bit in the first group is serviced, and decremented each time a bit in the second group corresponding to an idle slot is encountered but an idle slot is not transmitted; and scheduling the available time slots represented by bits of the second group at a time determined by executing an instruction which specifies a target address in the second group of bits and returns an indication as to whether or not a scheduled time slot exists in the second group in a range from the bit corresponding to the target address to the bit corresponding to the sum of the target address and the count.
Claim 12
Independent Claim
172 words
A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of: providing a first group of bits with each bit in the group of bits representing a cell time slot, wherein the value of a given bit in the first group of bits indicates whether or not the corresponding cell time slot has been scheduled for transmission; maintaining a count, wherein the count is incremented each time a cell not scheduled using a bit in the first group of bits is sent on a transmission link of the communication system, and decremented each time a bit in the first group corresponding to an idle slot is encountered but an idle slot is not transmitted; and scheduling the available time slots represented by bits of the first group at a time determined by scheduling a time slot at a time corresponding to the sum of a target time for the corresponding scheduling request and the count value at the time the scheduling request is received.
Claim 13
Independent Claim
172 words
A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of: providing a first group of bits with each bit in the group of bits representing a cell time slot, wherein the value of a given bit in the first group of bits indicates whether or not the corresponding cell time slot has been scheduled for transmission; maintaining a count, wherein the count is incremented each time a cell not scheduled using a bit in the first group of bits is sent on a transmission link of the communication system, and decremented each time a bit in the first group corresponding to an idle slot is encountered but an idle slot is not transmitted; and scheduling the available time slots represented by bits of the first group at a time determined by scheduling a time slot at a time corresponding to the sum of a target time for the corresponding scheduling request and the count value at the time the scheduling request is received.
Claim 14
Independent Claim
215 words
A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of: providing a first group of bits with each bit in the group of bits representing a cell time slot, wherein the value of a given bit in the first group of bits indicates whether or not the corresponding cell time slot has been scheduled for transmission; maintaining a count, wherein the count is incremented each time a cell not scheduled using a bit in the first group of bits is sent on a transmission link of the communication system, and decremented each time a bit in the first group corresponding to an idle slot is encountered but an idle slot is not transmitted; scheduling the available time slots represented by bits of the first group at a time determined in part by the count; and servicing the available time slots represented by the bits of the first group by executing an instruction which specifies a target address in the first group of bits and returns an indication as to whether or not a scheduled time slot exists in the a group in a range from the bit corresponding to the target address to the bit corresponding to the sum of the target address and the count.
Claim 15
Independent Claim
215 words
A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of: providing a first group of bits with each bit in the group of bits representing a cell time slot, wherein the value of a given bit in the first group of bits indicates whether or not the corresponding cell time slot has been scheduled for transmission; maintaining a count, wherein the count is incremented each time a cell not scheduled using a bit in the first group of bits is sent on a transmission link of the communication system, and decremented each time a bit in the first group corresponding to an idle slot is encountered but an idle slot is not transmitted; scheduling the available time slots represented by bits of the first group at a time determined in part by the count; and servicing the available time slots represented by the bits of the first group by executing an instruction which specifies a target address in the first group of bits and returns an indication as to whether or not a scheduled time slot exists in the a group in a range from the bit corresponding to the target address to the bit corresponding to the sum of the target address and the count.
References Cited (Backward Citations)
US4589087A
Cited
US5008807A
Cited
US5247627A
Cited
US4926374A
Cited
US5130975A
Cited
US5463622A
Cited
US5136584A
Cited
US5249178A
Cited
US5379295A
Cited
US5420859A
Cited
US5271005A
Cited
US5280475A
Cited
US5253247A
Cited
US5274641A
Cited
US5265091A
Cited
US5365519A
Cited
US5241536A
Cited
US5394397A
Cited
US5381407A
Cited
US5467347A
Cited
US5521915A
Cited
US5544172A
Cited
US5526352A
Cited
US5450400A
Cited
US5448567A
Cited
US5500851A
Cited
US5446726A
Cited
US5528592A
Cited
US5577035A
Cited
US5610914A
Cited
US5455826A
Cited
US5598541A
Cited
US5533020A
Cited
US5530806A
Cited
US5598410A
Cited
US5541918A
Cited
US5548588A
Cited
US5563884A
Cited
US5535201A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-04 | 2001-11-03 | 2002-05-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-04 | 2005-11-03 | 2006-05-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-04 | 2009-11-03 | 2010-05-05 | $7700.00 | Window Closed / Lapsed |