Time-division multiplex arbitration with fractional allocation

• US 7,688,776 B2
• Filed: 11/01/2006
• Issued: 03/30/2010
• Est. Priority Date: 11/01/2006
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Hearn, Alan S., Sexton, William J.
• Primary Examiner(s): Ahmed; Salman
• Assistant Examiner(s): Ghafoerkhan; Faiyazkhan
• Application Number:
  US11/555,503
• Publication Number:
  US 20080101399A1
• Time in Patent Office: 1,245 Days
• Field of Search: None
• US Class Current: 370/322
• 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, 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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