Time-division multiplex arbitration with fractional allocation

• US 20080101399A1
• Filed: 11/01/2006
• Published: 05/01/2008
• Est. Priority Date: 11/01/2006
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Sexton, William J., Hearn, Alan S.
• Granted Patent: US 7,688,776 B2
• Time in Patent Office: Days
• US Class Current: 370/461
• CPC Class Codes: H04J 3/1682 Allocation of channels according to the instantaneous demands of the users, e.g. concentrated multiplexers, statistical multiplexers

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.

Claims

1. 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, the method comprising:

determining each channel'"'"'s standard desired allocation of time slots;

allocating to each channel a number of time slots equal to the integer portion of the channel'"'"'s standard desired allocation; and

rolling the fractional remainder portion of each channel'"'"'s standard desired allocation over into the next cycle.

2. 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.

3. 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.

4. A method as in claim 1, 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.

5. 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.

6. A method as in claim 5, 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.

7. A method as in claim 5, wherein only one additional time slot may be actually allocated among the plurality of channels per cycle.

8. A method as in claim 7, 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.

9. 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.

10. A method as in claim 9, further comprising allocating time slots among the plurality of channels on a repeating, rotating basis.

11. A method as in claim 9, 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.

12. A method as in claim 11, further comprising allocating time slots among the plurality of channels on a repeating, rotating basis.

13. A method as in claim 12, wherein the average number of time slots allocated to each channel per cycle approaches the standard desired allocation across an increasing number of cycles.

14. 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, 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.

15. A method as in claim 14, further comprising allocating time slots among the plurality of channels on a repeating, rotating basis.

16. A method as in claim 14, 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.

17. A method as in claim 14, 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.

18. A method as in claim 17, 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.

19. A method as in claim 17, further comprising allocating time slots among the plurality of channels on a repeating, rotating basis.

20. A method as in claim 19, 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.

21. A method as in claim 19, wherein the average number of time slots allocated to each channel per cycle approaches the standard desired allocation across an increasing number of cycles.

22. 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;

assigning each channel a number of time slots per cycle equal to the integer portion of the channel'"'"'s standard desired allocation; and

rolling the fractional remainder portion of each channel'"'"'s standard desired allocation over to the next cycle.

23. A device as in claim 22, 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.

24. A device as in claim 22, 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.

25. A device as in claim 24, wherein only one additional time slot may be actually allocated among the plurality of channels per cycle.

26. A device as in claim 25, 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.

27. A device as in claim 22, 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.

28. 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.

29. A device as in claim 28, wherein each channel'"'"'s standard desired allocation is determined based on the TDM data stream'"'"'s burst size and the channel'"'"'s bandwidth.

30. A device as in claim 28, 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.