Multiplex communications – Communication techniques for information carried in plural... – Combining or distributing information via time channels
Reexamination Certificate
1999-02-26
2002-12-03
Kizou, Hassan (Department: 2662)
Multiplex communications
Communication techniques for information carried in plural...
Combining or distributing information via time channels
C370S537000, C370S395400, C370S232000, C370S235000
Reexamination Certificate
active
06490298
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to apparatus and methods of multiplexing data to a communication channel.
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.
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.
SUMMARY OF THE INVENTION
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.
Embodiments may include one or more of the following features.
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.
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.
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.
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.
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.
Among the advantages of the invention are the following.
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).
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.
In addition, because the outputs of higher bit rate sources tend to be more regular than the outputs
Chin Amanda L.
Haskell Paul E.
Helms William L.
Fish & Richardson P.C.
Harmonic Inc.
Kizou Hassan
Spafford Tim
LandOfFree
Apparatus and methods of multiplexing data to a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and methods of multiplexing data to a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and methods of multiplexing data to a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2980761