Binary-tree multiplexing scheduling

• US 7,499,467 B2
• Filed: 05/05/2005
• Issued: 03/03/2009
• Est. Priority Date: 06/13/2001
• Status: Expired due to Term

• Current Assignee: Rakuten Group, Inc.
• Original Assignee: Interdigital Technology Corporation (InterDigital, Inc.)
• Inventors: Chao, Yi-Ju
• Primary Examiner(s): Levitan, Dmitry
• Application Number:
  US11/122,538
• Publication Number:
  US 20050201377A1
• Time in Patent Office: 1,398 Days
• Field of Search: 370/437, 370442-445, 370/447, 370/458, 370/461, 370/462, 370/537, 370/538, 370/540
• US Class Current: 370/437
• CPC Class Codes: H04J 3/1629 Format building algorithm
• CPC Class Codes: H04W 72/1221 based on age of data to be sent
• CPC Class Codes: H04W 72/569 of the traffic information

Abstract

A method for multiplexed scheduling of information blocks from multiple sources on a single communication channel divided into multiple address positions. The information block from each source has a repetition period and is divided into a number of segments. A bandwidth adequacy verification is performed for expected information blocks to be scheduled on the channel. Mapping positions are assigned corresponding to nodes in a binary tree, whereby each layer of the binary tree corresponds to a repetition period of the respective information block. Assignment of the information blocks to the binary tree is based on a priority order of repetition period of the respective information block, starting with the smallest repetition period. As each binary tree position node is assigned, all child nodes of the assigned position node are also marked as assigned.

Claims

1. A method for multiplexed scheduling of information blocks from multiple sources on a single communication channel divided into multiple address positions, the information block from each source having a repetition period and a number of segments, comprising the steps of:

checking for adequate channel bandwidth for a plurality of information blocks according to a summed ratio of number of segments per repetition period for each respective information block;

mapping channel positions in a non-sequential order corresponding to a binary tree, whereby each layer of the binary tree corresponds to a repetition period; and

assigning information segments of each information block to unassigned channel positions corresponding to binary tree nodes of a layer on the binary tree associated with the repetition period of the information block.

2. The method of claim 1 wherein the checking step is performed such that the ratio satisfies the following equation:

$\underset{r=1}{\overset{R}{\sum <br><br>}}<br><br>\frac{{\mathrm{INFO}}_r<br><br>\left(\mathrm{SC}\right)}{{\mathrm{INFO}}_r<br><br>\left(\mathrm{RP}\right)}\le <br><br>1,$

where R is the number of information blocks, INFO_r(SC) is the segment count of the respective information block, and INFO_r(RP) is the repetition period of the respective information block.

3. The method of claim 2 wherein the binary tree has N layers represented by N=log₂(max INFO_r(RP)), where maxINFO_r(RP) is the maximum repetition period of all information blocks.

4. The method of claim 3 wherein the number of positions P is represented by P=2^N−

1, where N is the number of binary tree layers.

5. The method of claim 1, wherein the assigning of information blocks is according to a priority order, the information blocks include a header block of information which is first in the priority order, and the segments of the header information block are assigned to numerically consecutive initial channel positions.

6. The method of claim 5, wherein assigning of each information block occurs at a layer k, where k=log₂(INFO_r(RP)) and INFO_r(RP) represents the repetition period of the respective information block.

7. The method of claim 5, wherein segments of subsequent blocks of information are assigned to unassigned positions with the least numerical values and as consecutively as possible.

8. The method of claim 5, wherein segments of subsequent blocks of information are assigned to unassigned positions with the greatest numerical values and as consecutively as possible.

9. The method of claim 1, further comprising:

identifying and marking as assigned all child nodes of the node in the layer corresponding to the repetition period.

10. A method for scheduling information blocks from multiple sources on a single communication channel divided into multiple address positions, the information block from each source having a repetition period and a number of segments, comprising the steps of:

verifying adequate channel bandwidth according to a ratio of number of segments per repetition period for each respective information block;

creating a first list comprising information blocks sorted by a priority order according to ascending repetition period;

creating a second list containing mapping positions for assignment of information block segments corresponding to nodes in a binary tree, the binary tree having a plurality of layers, each layer corresponding to a repetition period;

assigning information segments of each block according to the order of the first list at unassigned positions in the layer corresponding with the repetition period of the block and to all corresponding child nodes down to the bottom layer on the binary tree.

11. The method of claim 10, wherein the information blocks include a header block of information which is first in the priority order, wherein segments of the header information block are assigned to numerically consecutive initial channel positions.

12. The method of claim 11, wherein segments of subsequent blocks of information are assigned to unassigned positions with the least numerical values and as consecutively as possible.

13. The method of claim 11, wherein segments of subsequent blocks of information are assigned to unassigned positions with the greatest numerical values and as consecutively as possible.