Apparatus and methods of multiplexing data to a communication channel

[0002] The invention relates to apparatus and methods of multiplexing data to a communication channel.

[0003] In a typical data network, a plurality of data sources deliver their respective data streams to various receivers over the same fixed bandwidth communication channel. A multiplexer receives the data streams from the sources and choreographs the injection of data into the communication channel. The multiplexer is typically designed to efficiently inject as much data into communication channel as possible, without exceeding the capacity of the channel. The data sources typically include encoders for compressing data before delivery to the multiplexer; the receivers decompress and reconstruct the original data signals from the compressed data streams. A data source may be characterized as either a constant bit rate (CBR) source or a variable bit rate (VBR) source: a fixed rate source injects data (bits) into a communication channel at a constant rate, whereas a variable rate source injects bits into a communication channel at a variable rate.

[0004] Transfer of information from the data sources is typically in the form of information packets. The multiplexer schedules data for output to the communication channel one packet at a time, and delivers the scheduled data packets to the channel as an output multiplex. Packet scheduling involves the assignment of a particular source to a timeslot in the output multiplex. A high-performance scheduling algorithm allows each of the sources to be assigned an arbitrary fraction of channel bandwidth, subject to the constraint that the sum of all source bit rates is less than or equal to the bit rate multiplex that they share. Real-time scheduling is desirable because it allows sources to change their bit rates frequently and on-the-fly. High-performance real-time scheduling of multiple sources often requires substantial hardware resources, with the computational complexity increasing with the output bit rate, the number of sources and the resolution with which the route of each source is specified.

[0005] The invention features apparatus and methods for multiplexing data received from a plurality of sources to a communication channel. In accordance with the invention, each of the sources is assigned to one of at least two scheduling layers, including a first layer and a second layer, based at least in part upon one or more bit rate characteristics of the sources.

[0006] Embodiments may include one or more of the following features.

[0007] Each of the sources may be assigned based at least in part on data transmission rates of the sources, bit rate precision levels of the sources or both. The sources may be assigned to the scheduling layers based upon a fixed assignment method that operates independently of changes in data transmission rates of the sources, or based upon a dynamic assignment method that responds to changes in data transmission rates of the sources. The number of sources assigned to the first layer may be fixed or variable.

[0008] In one embodiment, the first layer comprises an entry for each source assigned to the first layer and an entry representative of a source assigned to the second layer, and the second layer comprises an entry for each source assigned to the second layer. The sources represented by entries in the first layer are scheduled for output to the communication channel. The sources represented by entries in the first layer may be scheduled for output based upon a variable bit rate scheduling method. Sources with relatively high bit rates (with relatively high bit rate precision levels) preferably are assigned to the first layer. The sources represented by entries in the second layer are scheduled for assignment to the representative entry of the first layer. The sources represented by entries in the second layer preferably are scheduled sources for assignment to the representative entry of the first layer based upon a variable bit rate scheduling method.

[0009] In another embodiment, each of the sources is assigned to one of three or more scheduling layers, including the first layer, the second layer and a sequence of one or more lower layers, based at least in part on one or more bit rate characteristics of the sources. The second layer preferably comprises, in addition to an entry for each source assigned to the second layer, an entry representative of a source assigned to a first of the one or more lower layers, and each lower layer preferably comprises an entry for each source assigned to that lower layer and an entry representative of a source assigned to the next lower layer in the sequence of one or more lower layers. The sources represented by entries in that first lower layer preferably are scheduled for assignment to the representative entry of the second layer. In some embodiments, the first layer preferably comprises, in addition to the entry for each source assigned to the first layer and the entry representative of a source assigned to the second layer, a representative entry for each of the lower layers, and each lower layer preferably comprises an entry for each source assigned to that lower layer. Lower layer sources preferably are scheduled for assignment to the representative entries of the first layer.

[0010] In another embodiment, each of the sources is assigned to one of three or more scheduling layers, including the first layer, the second layer and a third layer, based at least in part on one or more bit rate characteristics of the sources. The first layer comprises an entry for each source assigned to the first layer. The second layer comprises an entry for each source assigned to the second layer. The third layer comprises an entry representative of a source assigned to the first layer and an entry representative of a source assigned to the second layer. Each of the sources preferably is assigned based at least in part on the data transmission rates of the sources, or on the bit rate precision levels of the sources. Sources with relatively high bit rates (or with relatively high bit rate precision levels) preferably are assigned to the first layer.

[0011] Each source preferably is assigned a data transmission rate and a bit rate precision level. In some embodiments, the same bit rate precision level is assigned to each source. In other embodiments, different bit rate precision levels are assigned to the sources. In a preferred embodiment, relatively high bit rate precision levels are assigned to audio sources, intermediate bit rate precision levels are assigned to video sources, and relatively low bit rate precision levels are assigned to data sources.

[0012] Among the advantages of the invention are the following.

[0013] The invention allows real-time scheduling using high performance scheduling methods, but with reduced computational requirements. Because each of the sources assigned to the first layer has a relatively high bit rate (or high bit rate precision level), the first layer sources typically may be scheduled with a course bit rate granularity. This reduces the computational load at the first layer without degrading the performance of the first layer sources (i.e., source performance is typically not degraded if it operates at 15.000 Mb/s rather than at 14.999 Mb/s, but its performance may be degraded if it operates at 1 kb/s).

[0014] The computational load at the lower (e.g., second) layer is reduced in several ways. The lower layer scheduler only need operate at the rate at which the first layer scheduler selects packets from the lower layer for output to the communication channel—a rate which may be a small fraction of the first layer packet rate. Further, the lower layer may only contain sources with a much smaller maximum bit rate than the first layer. This allows the use of scheduling methods characterized by a relatively fine bit rate granularity without increasing computational complexity. Sources may be assigned to layers depending on their bit rates and on their bit rate resolution requirements.

[0015] In addition, because the outputs of higher bit rate sources tend to be more regular than the outputs of lower bit rate sources, the invention might improve the overall multiplexer output regularity by separately scheduling the higher and lower bit rate sources.

[0016] The invention also reduces implementation complexity by separately scheduling high rate sources and low rate sources, or by separately scheduling fine rate granularity and coarse rate granularity sources, or both.

[0017] Other features and advantages will become apparent from the following description, including the drawings and the claims.

[0018] FIG. 1 is a block diagram of a communication network, including a plurality of sources, a multiplexer, a communication channel, and a receiver.

[0019] FIG. 2A is a block diagram of a multiplexer.

[0020] FIG. 2B is a flow diagram of a method of multiplexing data to a communication channel.

[0021] FIG. 3A is a block diagram of a multiplexer.

[0022] FIG. 3B is a flow diagram of a method of multiplexing data to a communication channel.

[0023] FIG. 4A is a block diagram of a multiplexer.

[0024] FIG. 4B is a flow diagram of a method of multiplexing data to a communication channel.

[0025] FIG. 5A is a block diagram of a multiplexer.

[0026] FIG. 5B is a flow diagram of a method of multiplexing data to a communication channel.

[0027] Referring to FIG. 1, a communication network 10 includes a plurality of data sources A-Z (e.g., video cameras), a multiplexer 12, a communication channel 14 which includes a channel network 16, and a receiver 18. Data sources A-Z typically include encoders configured to compress original data using a compression algorithm based on a standard protocol. In one embodiment, variable bit rate (VBR) encoding techniques, such as the MPEG-1 or the MPEG-2 encoding standards, are used to reduce the amount of data needed by receiver 18 to reconstruct the original data signals. Other variable bit rate encoding techniques, as well as constant bit rate encoding techniques, may be used. The encoded data is delivered to multiplexer 12 as a series of data streams 20. Multiplexer 12 assigns to each source A-Z a time slot 22 in an output multiplex 24. Output multiplex 24 may be immediately broadcast to receiver 18 over channel network 16 or stored in memory for broadcast at a later time.

[0028] As explained below, multiplexer 12 is configured assign each source A-Z to a time slot 22 in real-time to achieve efficient bandwidth utilization with reduced computational complexity and without sacrificing source performance.

[0029] Referring to FIG. 2A, in one embodiment, multiplexer 12 includes a partitioner 30 that receives data streams 20 from sources A-C and X-Z and assigns each source to one of at least two scheduling layers, including a first layer 32 and a second layer 34, based at least in part on one or more bit rate characteristics of the sources—e.g., the data transmission rates of the sources, or the bit rate precision levels (also referred to as the bit rate accuracy or the bit rate granularity) of the sources, or both. For example, in one embodiment, sources characterized by a relatively high data transmission rate (bit rate) are assigned to first layer 32, and the remaining sources are assigned to second layer 34. In another embodiment, sources characterized by relatively high bit rate precision levels are assigned to first layer 32, and the remaining sources are assigned to second layer 34. The number of sources assigned to first layer 32 is restricted to achieve manageable implementation complexity. The number of sources assigned to first layer 32 may be fixed or may vary over time.

[0030] In FIG. 2A, partitioner 30 has partitioned sources A-, X-Z into two groups 36, 38, with sources A-C assigned to first layer 32 and sources X-Z assigned to second layer 34. First layer 32 includes an entry 40-44 for each source assigned to first layer 32 and an entry 46 (φ) which is representative of a source assigned to second layer 34. Thus, entry 46 (φ) serves as an escape code for all of the second layer sources. Second layer 34 includes an entry 48-52 for each source assigned to second layer 34.

[0031] A bit rate controller 53 specifies the bit rates and the bit rate precision levels of sources A-C, X-Z, and delivers this information to partitioner 30 and to the schedulers (discussed below). In one embodiment, bit rate controller 53 assigns the same bit rate precision to each source. In another embodiment, bit rate controller 53 assigns different bit rate precision levels to the sources. For example, audio sources maybe assigned relatively high bit rate precision levels, video sources may be assigned intermediate bit rate precision levels, and data sources may be assigned relatively low bit rate precision levels.

[0032] Multiplexer 12 also includes a first layer scheduler 54 and a second layer scheduler 56. First layer scheduler 54 is configured to schedule the sources represented by entries in first layer 32 for output to communication channel 14. In one embodiment, first layer scheduler 54 schedules sources for output based upon a variable bit rate scheduling method. For example, first layer scheduler may schedule sources based on the virtual clock method, the round robin method, or the first-in-first-out (FIFO) method, as described in Zhang et al., “Comparison of Rate-Based Service Disciplines,” SIGCOMM '91, vol. 21:4, pp. 113-121 (1991), which is incorporated herein by reference. Second layer scheduler 56 is configured to schedule sources represented by entries in second layer 34 for assignment to representative entry 46 (φ) of first layer 32. In one embodiment, second layer scheduler 56 schedules sources for output based upon a variable bit rate scheduling method, such as one of the methods mentioned in connection with first layer scheduler 54.

[0033] In one embodiment, partitioner 30 is configured to assign sources A-C, X-Z to scheduling layers 32, 34 based upon a fixed assignment method that operates independently of changes in the data transmission rates of the sources. For example, sources that are known in advance to be characterized by a relatively high bit rate may be permanently assigned to first layer 32, and all of the remaining sources may be permanently assigned to second layer 34.

[0034] In another embodiment, partitioner 30 is configured to assign sources A-C, X-Z to scheduling layers 32, 34 based upon a dynamic assignment method that responds to changes in the data transmission rates of the sources. For example, partitioner 30 may dynamically assign sources with the highest bit rates to first layer 32 and the remaining sources to second layer 34. Thus, the assignments of each of the sources may change over time depending upon changes in the bit rates of each of the sources. In one embodiment, the number of sources assigned to first layer 32 is fixed and only the sources with the highest bit rates are assigned to first layer 32. In another embodiment, sources with bit rates over a selected threshold value are assigned to first layer 32, in which the number of sources assigned to first layer 32 may vary over time. In another embodiment, a sufficient number of the highest bit rate sources are assigned to first layer 32 so that the sum of the bit rates of the first layer sources just exceeds a threshold value.

[0035] As shown in FIG. 2B, the multiplexer of FIG. 2A is operable to choreograph the multiplexing of data to communication channel 14 as follows. Partitioner 30 partitions sources based at least upon one or more bit rate characteristics of the sources (step 60). First layer scheduler 54 schedules first layer sources entries 40-46 for output to communication channel 14 (step 62). If entry 46 (φ), which is representative of a source assigned to second layer 34, is not scheduled for output (step 64), the scheduled first layer source is output to communication channel 14 (step 66). Otherwise, second layer scheduler 56 schedules second layer source entries 48-52 for assignment to second layer source representative entry 46 (φ) (step 68), and the scheduled second layer source is output to communication channel 14 (step 70).

[0036] As explained above, by separately scheduling the higher and lower bit rate (or bit rate precision level) sources, the multiplexer of FIG. 2A reduces the computational loads at the first and second layers without sacrificing source performance.

[0037] Other embodiments are within the scope of the claims.

[0038] Referring to FIG. 3A, in one embodiment, multiplexer 12 includes a partitioner 80 which receives data streams 20 from sources A-C, K-M and X-Z and assigns each source to one of at least three scheduling layers, including a first layer 82, a second layer 84 and a third layer 86, based at least in part on one or more bit rate characteristics of the sources—e.g., the data transmission rates of the sources, or the bit rate precision levels of the sources, or both. For example, in one embodiment, sources characterized by the highest data transmission rates (bit rate) are assigned to first layer 82, sources with intermediate bit rates are assigned to second layer 84, and the remaining sources are assigned to third layer 86. In another embodiment, sources characterized by the highest bit rate precision levels are assigned to first layer 82, sources with intermediate bit rate precision levels are assigned to second layer 84, and the remaining sources are assigned to third layer 86. The numbers of sources assigned to first layer 82 and second layer 84 may be restricted to achieve manageable implementation complexity. The number of sources assigned to first layer 82 may be fixed or may vary over time.

[0039] In FIG. 3A, partitioner 80 has partitioned sources A-C, K-M, X-Z into three groups 88, 90, 92, with sources A-C assigned to first layer 82, sources K-M assigned to second layer 84, and sources X-Z assigned to third layer 86.

[0040] A bit rate controller 93 specifies the bit rates and the bit rate precision levels of sources A-C, X-Z, and delivers this information to partitioner 30 and to the schedulers (discussed below). In one embodiment, bit rate controller 93 assigns the same bit rate precision to each source. In another embodiment, bit rate controller 93 assigns different bit rate precision levels to the sources. For example, audio sources maybe assigned relatively high bit rate precision levels, video sources may be assigned intermediate bit rate precision levels, and data sources may be assigned relatively low bit rate precision levels.

[0041] First layer 82 includes an entry 94-98 for each source assigned to first layer 82 and an entry 100 (φ₁) which is representative of a source assigned to second layer 84. Thus, entry 100 (φ₁) serves as an escape code for all of the second and third layer sources. Second layer 84 includes an entry 102-106 for each source assigned to second layer 84 and an entry 108 (φ₂) which is representative of a source assigned to third layer 86. Entry 108 (φ₂) therefore serves an escape code for all of the third layer sources. Third layer 86 includes an entry 110-114 for each source assigned to third layer 86.

[0042] Multiplexer 12 also includes a first layer scheduler 116, a second layer scheduler 118, and a third layer scheduler 120. First layer scheduler 116 is configured to schedule the sources represented by entries in first layer 82 for output to communication channel 14. In one embodiment, first layer scheduler 116 schedules sources for output based upon a variable bit rate scheduling method. For example, first layer scheduler may schedule sources based on the virtual clock method, the round robin method, or the first-in-first-out (FIFO) method (mentioned above). Second layer scheduler 118 is configured to schedule sources represented by entries in second layer 84 for assignment to representative entry 100 (φ₁) of first layer 82. In one embodiment, second layer scheduler 118 schedules sources for output based upon a variable bit rate scheduling method, such as one of the methods mentioned in connection with first layer scheduler 116. Third layer scheduler 120 is configured to schedule sources represented by entries 110-114 in third layer 86 for assignment to representative entry 108 (φ₂) of second layer 84. In one embodiment, third layer scheduler 120 schedules sources for output based upon a variable bit rate scheduling method, such as one of the methods mentioned above in connection with first layer scheduler 116.

[0043] In one embodiment, partitioner 80 is configured to assign sources A-C, K-M, X-Z to scheduling layers 82-86 based upon a fixed assignment method that operates independently of changes in the data transmission rates of the sources. For example, sources that are known in advance to be characterized by a relatively high bit rate may be permanently assigned to first layer 82, sources with intermediate bit rates may be permanently assigned to second layer 84, and all of the remaining sources may be permanently assigned to third layer 86.

[0044] In another embodiment, partitioner 80 is configured to assign the sources to the scheduling layer based upon a dynamic assignment method that responds to changes in the data transmission rates of the sources. For example, partitioner 80 may dynamically assign sources with the highest bit rates to first layer 82, sources with intermediate bit rates to second layer 84, and the remaining sources to third layer 86. Thus, the assignments of each of the sources may change over time depending upon changes in the bit rates of each of the sources. In one embodiment, the numbers of sources assigned to first layer 82 and second layer 84 are fixed. In another embodiment, sources with bit rates over a selected threshold value are assigned to first layer 82 and sources with bit rates within an intermediate range are assigned to second layer 84; in which case the numbers of sources assigned to first layer 82 and second layer 84 may vary over time. In another embodiment, a sufficient number of the highest bit rate sources are assigned to first layer 82 so that the sum of the bit rates of the first layer sources just exceeds a threshold value.

[0045] As shown in FIG. 3B, the multiplexer of FIG. 3A is operable to choreograph the multiplexing data to communication channel 14 as follows. Partitioner 80 partitions sources based at least upon one or more bit rate characteristics of the sources (step 130). First layer scheduler 116 schedules first layer sources entries 94-100 for output to communication channel 14 (step 132). If entry 100 (φ₁), which is representative of a source assigned to second layer 84, is not scheduled for output (step 134), the scheduled first layer source is output to communication channel 14 (step 136). Otherwise, second layer scheduler 118 schedules second layer source entries 102-108 for assignment to second layer source representative entry 100 (φ₁) (step 138). If entry 108 (φ₂), which is representative of a source assigned to third layer 86, is not scheduled for output (step 140), the scheduled second layer source is output to communication channel 14 (step 142). Otherwise, third layer scheduler 120 schedules third layer source entries 110-114 for assignment to second layer source representative entry 108 (φ₂) (step 144), and the scheduled third layer source is output to communication channel 14 (step 146).

[0046] In this embodiment, source scheduling is relatively simple to implement. This embodiment also enables managers to finely control route geometry to different sources.

[0047] Referring to FIG. 4A, in another embodiment, multiplexer 12 includes a partitioner 150 which receives data streams 20 from sources A-C, K-M and X-Z and assigns each source to one of at least three scheduling layers, including a first layer 152, a second layer 154 and a third layer 156, based at least in part on one or more bit rate characteristics of the sources—e.g., the data transmission rates of the sources, or the bit rate precision levels of the sources, or both. For example, in one embodiment, sources characterized by the highest data transmission rates (bit rate) are assigned to first layer 152, sources with intermediate bit rates are assigned to second layer 154, and the remaining sources are assigned to third layer 156; alternatively, sources characterized by the highest data transmission rates may be assigned to first layer 152, and the remaining sources may be assigned to second layer 154 and third layer 156 based upon one or more criteria which may or may not depend upon source bit rate (e.g., source bit rate precision levels). In another embodiment, sources characterized by the highest bit rate precision levels are assigned to first layer 152, sources with intermediate bit rate precision levels are assigned to second layer 154, and the remaining sources are assigned to third layer 156; alternatively, sources characterized by the highest bit rate precision levels may be assigned to first layer 152, and the remaining sources may be assigned to second layer 154 and third layer 156 based upon one or more criteria which may or may not depend upon source bit rate precision levels (e.g., source bit rate). The numbers of sources assigned to first layer 152 may be restricted to achieve manageable implementation complexity. The number of sources assigned to first layer 152 may be fixed or may vary over time.

[0048] In FIG. 4A, partitioner 150 has partitioned sources A-C, K-M, X-Z into three groups 158, 30160, 162, with sources A-C assigned to first layer 152, sources K-M assigned to second layer 154, and sources X-Z assigned to third layer 156.

[0049] A bit rate controller 163 specifies the bit rates and the bit rate precision levels of sources A-C, X-Z, and delivers this information to partitioner 30 and to the schedulers (discussed below). In one embodiment, bit rate controller 163 assigns the same bit rate precision to each source. In another embodiment, bit rate controller 163 assigns different bit rate precision levels to the sources. For example, audio sources maybe assigned relatively high bit rate precision levels, video sources may be assigned intermediate bit rate precision levels, and data sources may be assigned relatively low bit rate precision levels.

[0050] First layer 152 includes an entry 160-164 for each source assigned to first layer 152, an entry 166 (φ₁) which is representative of a source assigned to second layer 154, and an entry 168 (φ₂) which is representative of a source assigned to third layer 156. Second layer 154 includes an entry 170-174 for each source assigned to second layer 154. Third layer 156 includes an entry 176-180 for each source assigned to third layer 156.

[0051] Multiplexer 12 also includes a first layer scheduler 182, a second layer scheduler 184, and a third layer scheduler 186. First layer scheduler 182 is configured to schedule the sources represented by entries in first layer 152 for output to communication channel 14. In one embodiment, first layer scheduler 182 schedules sources for output based upon a variable bit rate scheduling method. For example, first layer scheduler 182 may schedule sources based on the virtual clock method, the round robin method, or the first-in-first-out (FIFO) method (mentioned above). Second layer scheduler 184 is configured to schedule sources represented by entries in second layer 154 for assignment to representative entry 166 (φ₁) of first layer 152. In one embodiment, second layer scheduler 184 schedules sources for output based upon a variable bit rate scheduling method, such as one of the methods mentioned in connection with first layer scheduler 182. Third layer scheduler 186 is configured to schedule sources represented by entries in third layer 156 for assignment to representative entry 168 (φ₂) of first layer 152. In one embodiment, third layer scheduler 186 schedules sources for output based upon a variable bit rate scheduling method, such as one of the methods discussed above in connection with first layer scheduler 182.

[0052] In one embodiment, partitioner 150 is configured to assign sources A-C, K-M, X-Z to scheduling layers 152-156 based upon a fixed assignment method that operates independently of changes in the data transmission rates of the sources. For example, sources that are known in advance to be characterized by a relatively high bit rate may be permanently assigned to first layer 152, and all of the remaining sources may be permanently assigned to second layer 154 and third layer 156, with the division of sources between second layer 154 and third layer 156 being 5 determined by one or more factors which may or may not depend upon source bit rate.

[0053] In another embodiment, partitioner 150 is configured to assign sources A-C, K-M, X-Z to scheduling layers 152-156 based upon a dynamic assignment method that responds to changes in the data transmission rates of the sources. For example, partitioner 150 may dynamically assign sources with the highest bit rates to first layer 152, and partition the remaining sources between second layer 154 and third layer 156. Thus, the assignments of each of the sources may change over time depending upon changes in the bit rates of each of the sources. In one embodiment, the number of sources assigned to first layer 152 is fixed. In another embodiment, sources with bit rates over a selected threshold value are assigned to first layer 152; in which the case numbers of sources assigned to first layer 152, second layer 154 and third layer 156 may vary over time. In another embodiment, a sufficient number of the highest bit rate sources are assigned to first layer 152 so that the sum of the bit rates of the first layer sources just exceeds a threshold value.

[0054] As shown in FIG. 4B, the multiplexer of FIG. 4A is operable to choreograph the multiplexing data to communication channel 14 as follows. Partitioner 150 partitions sources based at least upon one or more bit rate characteristics of the sources (step 190). First layer scheduler 182 schedules first layer sources entries 160-168 for output to communication channel 14 (step 1192). If entry 166 (φ₁), which is representative of a source assigned to second layer 154, is scheduled for output (step 194), second layer scheduler 184 schedules second layer source entries 170-174 for assignment to second layer source representative entry 166 (φ₁) and the scheduled second layer source is output to communication channel 14 (step 196). Otherwise, if entry 168 (φ₂) which is representative of a source assigned to third layer 156, is scheduled for output (step 198), third layer scheduler 186 schedules third layer source entries 176-180 for assignment to third layer source representative entry 168 (φ₂) and the scheduled third layer source is output to communication channel 14 (step 200). Otherwise, the scheduled first layer source is output to communication channel 14 (step 202).

[0055] Referring to FIG. 5A, in yet another embodiment, multiplexer 12 includes a partitioner 210 which receives data streams 20 from sources A-C, D-F, U-W and X-Z and assigns each source to one of at least four scheduling layers, including a first layer 212, a second layer 214, a third layer 216 and a fourth layer 218, based at least in part on one or more bit rate characteristics of the sources—e.g., the data transmission rates of the sources, or the bit rate precision levels of the sources, or both. For example, in one embodiment, sources characterized by the highest data transmission rates (bit rate) are assigned to first layer 212 and third layer 216, and the remaining sources are assigned to second layer 214 and fourth layer 218; alternatively, 10 sources characterized by the highest data transmission rates may be assigned to first layer 212, and the remaining sources may be assigned to second layer 214, third layer 216 and fourth layer 218 based upon some other criteria (e.g., source bit rate precision levels). In another embodiment, sources characterized by the highest bit rate precision level are assigned to first layer 212 and third layer 216, and the remaining sources are assigned to second layer 214 and fourth layer 218; alternatively, sources characterized by the highest bit rate precision levels may be assigned to first layer 212, and the remaining sources may be assigned to second layer 214, third layer 216 and fourth layer 218 based upon some other criteria (e.g., source bit rate). The numbers of sources assigned to first layer 212 may be restricted to achieve manageable implementation complexity. The number of sources assigned to first layer 212 may be fixed or may vary over time.

[0056] In FIG. 5A, partitioner 210 has partitioned sources A-C, D-F, U-W, X-Z into four groups 220, 222, 224, 226, with sources A-C assigned to first layer 212, sources D-F assigned to second layer 214, sources U-W assigned to third layer 216, and sources X-Z assigned to fourth layer 218.

[0057] A bit rate controller 227 specifies the bit rates and the bit rate precision levels of sources A-C, D-F, U-W, X-Z, and delivers this information to partitioner 30 and to the schedulers (discussed below). In one embodiment, bit rate controller 227 assigns the same bit rate precision level to each source. In another embodiment, bit rate controller 227 assigns different bit rate precision levels to the sources. For example, audio sources maybe assigned relatively high bit rate precision levels, video sources may be assigned intermediate bit rate precision levels, and data sources may be assigned relatively low bit rate precision levels.

[0058] First layer 212 includes an entry 228-232 for each source assigned to first layer 212. Second layer 214 includes an entry 234-238 for each source assigned to second layer 214. Third layer 1216 includes an entry 240-244 for each source assigned to third layer 216. Fourth layer 218 includes an entry 246-250 for each source assigned to third layer 218.

[0059] Multiplexer 12 also includes first, second, third and fourth layer schedulers 252-258. First layer scheduler 252 is configured to schedule sources A-C represented by entries 228-232 in first layer 212 for assignment to a representative entry 260 (φ₁) of a first intermediate scheduler 262. In one embodiment, first layer scheduler 212 schedules sources for assignment based upon a variable bit rate scheduling method (e.g., the virtual clock method, the round robin method, or the first-in-first-out (FIFO) method; mentioned above). Second layer scheduler 254 is configured to schedule sources D-F represented by entries 234-238 in second layer 214 for assignment to a representative entry 264 (φ₂) of first intermediate scheduler 262. In one embodiment, second layer scheduler 254 schedules sources for output based upon a variable bit rate scheduling method, such as one of the methods mentioned in connection with first layer scheduler 252. Third layer scheduler 256 is configured to schedule sources U-W represented by entries 240-244 in third layer 216 for assignment to a representative entry 266 (φ₃) of a second intermediate scheduler 268. In one embodiment, third layer scheduler 256 schedules sources for assignment based upon a variable bit rate scheduling method (e.g., the virtual clock method, the round robin method, or the first-in-first-out (FIFO) method; mentioned above). Fourth layer scheduler 258 is configured to schedule sources X-Z represented by entries 246-250 in fourth layer 218 for assignment to a representative entry 270 (φ₄) of second intermediate scheduler 268. In one embodiment, fourth layer scheduler 258 schedules sources for output based upon a variable bit rate scheduling method, such as one of the methods discussed above in connection with first layer scheduler 252. First and second intermediate schedulers 262, 268 are configured to respectively schedule representative entries 260, 264 and 266, 270 for assignment to representative entries 272, 274 of a final scheduler 276, which is configured to schedule representative entries 272, 274 for output to communication channel 14. First and second intermediate schedulers 262, 268 and final scheduler 276 may schedule sources based upon the same or different variable bit rate scheduling methods.

[0060] In one embodiment, partitioner 210 is configured to assign sources A-F, U-Z to scheduling layers 212-218 based upon a fixed assignment method that operates independently of changes in the data transmission rates of the sources. For example, sources that are known in advance to be characterized by a relatively high bit rate may be permanently assigned to first layer 212 and third layer 216, and all of the remaining sources may be permanently assigned to second layer 214 and fourth layer 218, with the assignment to either second layer 214 or fourth layer 218 being based on one or more criterion which may or may not depend upon source bit rate.

[0061] In another embodiment, partitioner 210 is configured to assign sources A-F, U-Z to scheduling layers 212-218 based upon a dynamic assignment method that responds to changes in the data transmission rates of the sources. For example, partitioner 210 may dynamically assign sources with the highest bit rates to first layer 212 and third layer 216, and partition the remaining sources between second layer 214 and fourth layer 218. Thus, the assignments of each of the sources may change over time depending upon changes in the bit rates of each of the sources. In one embodiment, the numbers of sources assigned to each of first layer 212 and third layer 216 are fixed. In another embodiment, sources with bit rates that are greater than a first threshold value are assigned to first layer 212, and sources with bit rates that are between the first threshold value and a second threshold value are assigned to third layer 216; in which case the numbers of sources assigned to layers 212-218 may vary over time. In another embodiment, a sufficient number of the highest bit rate sources are assigned to first layer 212 so that the sum of the bit rates of the first layer sources just exceeds a threshold value.

[0062] As shown in FIG. 5B, the multiplexer of FIG. 5A is operable to choreograph the multiplexing data to communication channel 14 as follows. Referring to FIGS. 5A and 5B, partitioner 210 partitions sources based at least upon one or more bit rate characteristics of the sources (step 280). First layer scheduler 252 schedules first layer sources entries 228-232 for assignment to representative entry 260 (φ₁) and second layer scheduler 254 schedules second layer sources entries 234-238 for assignment to representative entry 264 (φ₂) (step 282). Third layer scheduler 256 schedules third layer sources entries 240-244 for assignment to representative entry 266 (φ₃) and fourth layer scheduler 258 schedules fourth layer sources entries 246-250 for assignment to representative entry 270 (φ₄) (step 284). First intermediate scheduler 262 schedules first and second representative entries 260, 264 for assignment to representative entry 272 (φ₅) of final scheduler 276 (step 286). Second intermediate scheduler 268 schedules third and fourth representative entries 266, 270 for assignment to representative entry 274 (φ₆) of final scheduler 276 (step 288). Final scheduler 276 then schedules representative entries 272, 274 for output to communication channel 14 (step 290).

[0063] Still other embodiments are within the scope of the claims.