US7688776B2
Active / In Force
US
⏱️ 0.0 years remaining
Time-division multiplex arbitration with fractional allocation
Assignee: Texas Instruments Inc
•
Filing: 2006-11-01
•
Granted: 2010-03-30
•
Expires: 2026-11-01
Abstract
Abstract Disclosed embodiments reveal techniques for efficiently allocating time slots in a time-division multiplex (TDM) cycle among multiple channels of varying size, particularly when the channels do not all desire an integer number of time slots. TDM cycles can only allocate an integer number of time slots to each channel. So when at least one channel does not desire an integer number of time slots, then the disclosed embodiments allocate a number of time slots equal to the integer portion to each channel, rolling any fractional remainder over to the next cycle. This cumulative cyclical fractional summing process efficiently allocates time slots among the channels, allowing the average allocation per cycle to approach the true non-integer desired amount over time.
Inventors
- 👤 William J. Sexton
- 👤 Alan S. Hearn
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 01:57
CPC Classifications
H; H04; H04J; H04J3/00; H04J3/16; H04J3/1682
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
127 words
A method for allocating time slots for time-division multiplex (TDM) cycles associated with a TDM data stream, the time slots being allocated amongst a plurality of channels to be multiplexed onto the TDM data stream, a router performing the method comprising: determining each channel's standard desired allocation of time slots, wherein each channel's standard desired allocation of time slots is normalized, with one channel's standard desired allocation being set as an integer number and all other channels'standard desired allocations being set in proportion to the relative size of their bandwidths; allocating to each channel a number of time slots equal to the integer portion of the channel's standard desired allocation; and rolling a fractional remainder portion of each channel's standard desired allocation over into the next cycle.
Claim 2
Independent Claim
127 words
A method for allocating time slots for time-division multiplex (TDM) cycles associated with a TDM data stream, the time slots being allocated amongst a plurality of channels to be multiplexed onto the TDM data stream, a router performing the method comprising: determining each channel's standard desired allocation of time slots, wherein each channel's standard desired allocation of time slots is normalized, with one channel's standard desired allocation being set as an integer number and all other channels'standard desired allocations being set in proportion to the relative size of their bandwidths; allocating to each channel a number of time slots equal to the integer portion of the channel's standard desired allocation; and rolling a fractional remainder portion of each channel's standard desired allocation over into the next cycle.
Claim 3
Dependent Claim
30 words
A method as in claim 1 , wherein each channel's standard desired allocation of time slots is determined based on the TDM data stream's burst size and the channel's bandwidth.
Claim 4
Dependent Claim
34 words
A method as in claim 2 , wherein each channel's standard desired allocation of time slots is determined by dividing the channel's bandwidth by an integer multiple of the TDM data stream's burst size.
Claim 5
Dependent Claim
34 words
A method as in claim 1 , further comprising: accumulating rolled-over fractional remainders for each channel across multiple cycles; and allocating additional time slots based on the accumulated rolled-over fractional remainder for each channel.
Claim 6
Dependent Claim
56 words
A method as in claim 4 , wherein the rolled-over fractional remainder for each channel is accumulated by being added to the standard desired allocation each cycle, such that additional time slots would be allocated to each channel to address the accumulated rolled-over fractional remainder based on the integer portion of the channel's standard desired allocation.
Claim 7
Dependent Claim
24 words
A method as in claim 4 , wherein only one additional time slot may be actually allocated among the plurality of channels per cycle.
Claim 8
Dependent Claim
37 words
A method as in claim 6 , wherein any additional time slots accumulated by the plurality of channels in excess of the one additional time slot allocated per cycle would be rolled over into the next cycle.
Claim 9
Dependent Claim
42 words
A method as in claim 1 , further comprising: accumulating rolled-over fractional remainders for each channel across multiple cycles; and allocating an additional time slot to any channel whose accumulated rolled-over fractional remainder is greater than or equal to one time slot.
Claim 10
Dependent Claim
22 words
A method as in claim 8 , further comprising allocating time slots among the plurality of channels on a repeating, rotating basis.
Claim 11
Dependent Claim
33 words
A method as in claim 8 , wherein the plurality of channels access the TDM data stream, further comprising granting each channel access to the TDM data stream based on allocated time slots.
Claim 12
Dependent Claim
22 words
A method as in claim 10 , further comprising allocating time slots among the plurality of channels on a repeating, rotating basis.
Claim 13
Dependent Claim
31 words
A method as in claim 11 , wherein the average number of time slots allocated to each channel per cycle approaches the standard desired allocation across an increasing number of cycles.
Claim 14
Independent Claim
109 words
A method for allocating time slots for time-division multiplex (TDM) cycles associated with a TDM data stream, the time slots being allocated amongst a plurality of channels to be multiplexed onto the TDM data stream, a router performing the method comprising: determining each channel's standard desired allocation of time slots; initializing each channel's fractional remainder; determining the total desired allocation for each channel by adding the fractional remainder to the standard desired allocation; allocating each channel a number of time slots equal to the integer portion of the channel's total desired allocation; and rolling the fractional remainder portion of each channel's total desired allocation over into the next cycle.
Claim 15
Independent Claim
109 words
A method for allocating time slots for time-division multiplex (TDM) cycles associated with a TDM data stream, the time slots being allocated amongst a plurality of channels to be multiplexed onto the TDM data stream, a router performing the method comprising: determining each channel's standard desired allocation of time slots; initializing each channel's fractional remainder; determining the total desired allocation for each channel by adding the fractional remainder to the standard desired allocation; allocating each channel a number of time slots equal to the integer portion of the channel's total desired allocation; and rolling the fractional remainder portion of each channel's total desired allocation over into the next cycle.
Claim 16
Dependent Claim
22 words
A method as in claim 13 , further comprising allocating time slots among the plurality of channels on a repeating, rotating basis.
Claim 17
Dependent Claim
33 words
A method as in claim 13 , wherein the plurality of channels access the TDM data stream, further comprising granting each channel access to the TDM data stream based on allocated time slots.
Claim 18
Dependent Claim
30 words
A method as in claim 13 , wherein each channel's standard desired allocation of time slots is determined based on the TDM data stream's burst size and the channel's bandwidth.
Claim 19
Dependent Claim
36 words
A method as in claim 16 , wherein each channel's standard desired allocation of time slots is determined by dividing the channel's bandwidth by an integer multiple of the burst size of the TDM data stream.
Claim 20
Dependent Claim
22 words
A method as in claim 16 , further comprising allocating time slots among the plurality of channels on a repeating, rotating basis.
Claim 21
Dependent Claim
33 words
A method as in claim 18 , wherein the plurality of channels access the TDM data stream, further comprising granting each channel access to the TDM data stream based on allocated time slots.
Claim 22
Dependent Claim
31 words
A method as in claim 18 , wherein the average number of time slots allocated to each channel per cycle approaches the standard desired allocation across an increasing number of cycles.
Claim 23
Independent Claim
143 words
A device comprising: a plurality of source channels; a TDM data stream; and a router linking the plurality of channels to the TDM data stream, operable to allocate time slots in a time-division multiplex cycle among the channels in order to coordinate each channel's access to the TDM data stream on a rotating, repeating basis by: determining each channel's standard desired allocation of time slots, wherein each channel's standard desired allocation of time slots is normalized, with one channel's standard desired allocation being set as an integer number and all other channels'standard desired allocations being set in proportion to the relative size of their bandwidths; assigning each channel a number of time slots per cycle equal to the integer portion of the channel's standard desired allocation; and rolling a fractional remainder portion of each channel's standard desired allocation over to the next cycle.
Claim 24
Independent Claim
143 words
A device comprising: a plurality of source channels; a TDM data stream; and a router linking the plurality of channels to the TDM data stream, operable to allocate time slots in a time-division multiplex cycle among the channels in order to coordinate each channel's access to the TDM data stream on a rotating, repeating basis by: determining each channel's standard desired allocation of time slots, wherein each channel's standard desired allocation of time slots is normalized, with one channel's standard desired allocation being set as an integer number and all other channels'standard desired allocations being set in proportion to the relative size of their bandwidths; assigning each channel a number of time slots per cycle equal to the integer portion of the channel's standard desired allocation; and rolling a fractional remainder portion of each channel's standard desired allocation over to the next cycle.
Claim 25
Dependent Claim
30 words
A device as in claim 21 , wherein each channel's standard desired allocation of time slots is determined based on the TDM data stream's burst size and the channel's bandwidth.
Claim 26
Dependent Claim
45 words
A device as in claim 21 , wherein the means for allocating time slots among the channels further operates by: accumulating rolled-over fractional remainders for each channel across multiple cycles; and allocating additional time slots based on the accumulated rolled-over fractional remainder for each channel.
Claim 27
Dependent Claim
24 words
A device as in claim 23 , wherein only one additional time slot may be actually allocated among the plurality of channels per cycle.
Claim 28
Dependent Claim
37 words
A device as in claim 24 , wherein any additional time slots accumulated by the plurality of channels in excess of the one additional time slot allocated per cycle would be rolled over into the next cycle.
Claim 29
Dependent Claim
53 words
A device as in claim 21 , wherein the means for allocating time slots among the channels further operates by: accumulating rolled-over fractional remainders for each channel across multiple cycles; and allocating an additional time slot to any channel whose accumulated rolled-over fractional remainder is greater than or equal to one time slot.
Claim 30
Independent Claim
138 words
A device comprising: a plurality of source channels; a TDM data stream; and a router linking the plurality of channels to the TDM data stream, operable to allocate time slots in a time-division multiplex cycle among the channels in order to coordinate each channel's access to the TDM data stream on a rotating, repeating basis by: determining each channel's standard desired allocation of time slots; initializing each channel's fractional remainder; determining the total desired allocation for each channel by adding the fractional remainder to the standard desired allocation; allocating each channel a number of time slots equal to the integer portion of the channel's total desired allocation; granting each channel access to the TDM data stream based on allocated time slots; and rolling the fractional remainder portion of each channel's total desired allocation over into the next cycle.
Claim 31
Independent Claim
138 words
A device comprising: a plurality of source channels; a TDM data stream; and a router linking the plurality of channels to the TDM data stream, operable to allocate time slots in a time-division multiplex cycle among the channels in order to coordinate each channel's access to the TDM data stream on a rotating, repeating basis by: determining each channel's standard desired allocation of time slots; initializing each channel's fractional remainder; determining the total desired allocation for each channel by adding the fractional remainder to the standard desired allocation; allocating each channel a number of time slots equal to the integer portion of the channel's total desired allocation; granting each channel access to the TDM data stream based on allocated time slots; and rolling the fractional remainder portion of each channel's total desired allocation over into the next cycle.
Claim 32
Dependent Claim
27 words
A device as in claim 27 , wherein each channel's standard desired allocation is determined based on the TDM data stream's burst size and the channel's bandwidth.
Claim 33
Dependent Claim
34 words
A device as in claim 27 , wherein each channel's standard desired allocation of time slots is determined by dividing the channel's bandwidth by an integer multiple of the TDM data stream's burst size.
References Cited (Backward Citations)
US6842437B1
Cited
US20030067653A1
Cited
US20060147208A1
Cited
US7443790B2
Cited
US20030095562A1
Cited
US7369491B1
Cited
US20050036505A1
Cited
US20080101399A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2013-03-29 | 2013-09-28 | 2014-03-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2017-03-29 | 2017-09-28 | 2018-03-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2021-03-29 | 2021-09-28 | 2022-03-30 | $7700.00 | Window Closed / Lapsed |