Using a receiver model to multiplex variable-rate bit streams having timing constraints

• US 6,052,384 A
• Filed: 03/21/1997
• Issued: 04/18/2000
• Est. Priority Date: 03/21/1997
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Scientific-Atlanta Incorporated (Cisco Systems, Inc.)
• Inventors: Birch, Christopher H., Huang, Si Jun
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): Duong, Frank
• Application Number:
  US08/823,007
• Time in Patent Office: 1,124 Days
• Field of Search: 370/385, 370/387, 370/390, 370/398, 370/423, 370/465, 370/476, 370/477, 370/537, 370/538, 370/468, 348/404, 348/405, 348/419
• US Class Current: 370/468
• CPC Class Codes: H04B 7/2612 Arrangements for wireless medium access control, e.g. by allocating physical layer transmission capacity H04B7/2615 - H04B7/2643 take precedence; provision for broadband connection H04Q11/0478
• CPC Class Codes: H04J 3/1682 Allocation of channels according to the instantaneous demands of the users, e.g. concentrated multiplexers, statistical multiplexers
• CPC Class Codes: H04J 3/1688 the demands of the users being taken into account after redundancy removal, e.g. by predictive coding, by variable sampling reducing bandwidth of signals in general H04B1/66; in PCM-systems H04B14/046; removal of redundancy in telegraph communication H03M7/30
• CPC Class Codes: H04J 3/247 ATM or packet multiplexing
• CPC Class Codes: H04N 21/23406 involving management of server-side video buffer
• CPC Class Codes: H04N 21/23655 Statistical multiplexing, e.g. by controlling the encoder to alter its bitrate to optimize the bandwidth utilization
• CPC Class Codes: H04N 21/2385 Channel allocation H04N21/266 takes precedence; Bandwidth allocation H04N21/24 takes precedence ; allocation of channels according to the instantaneous demands of the users in time-division multiplex systems H04J3/1682; admission control, resource allocation in open networks H04L12/5692; arrangements for maintenance or administration in data switching networks involving bandwidth and capacity management H04L41/0896; negotiating bandwidth in wireless networks H04W28/16
• CPC Class Codes: H04N 21/2402 Monitoring of the downstream path of the transmission network, e.g. bandwidth available traffic monitoring in data switching networks H04L43/00; monitoring data switching networks utilization H04L43/0876

Abstract

Techniques for determining an output rate for a bit stream, the output rate being determined by applying information read from the bit stream to a model of a receiver for the bit stream. The techniques are employed to construct a statistical multiplexer that multiplexes varying bit-rate MPEG-2 bit streams onto a satellite up-link. Minimum and maximum output rates for each MPEG-2 bit stream are determined such that neither a queue for the bit stream in the multiplexer nor the bit stream'"'"'s decoder will underflow or overflow. The rates with regard to the decoder are determined using timing information read from the bit stream and a general model of an MPEG-2 decoder. The multiplexer first allocates each bit stream its minimum bandwidth and then allocates any remaining bandwidth to the bit streams in proportion to the difference between the minimum and maximum output rates for the bit streams, with no bit stream receiving more than its maximum output rate. If there is not enough bandwidth to give every bit stream its minimum rate, bit rates are allocated according to priorities assigned to the bit streams.

Claims

1. An apparatus for controlling a rate at which a bit stream encoded at a variable rate is output, the apparatus comprising:

a queue for receiving and storing the bit stream;

a processor for applying a model of a receiver for the bit stream to information read from the bit stream to determine an output rate for outputting the bit stream;

a bit stream analyzer for analyzing at least timing information and picture size information in said bit stream; and

output apparatus responsive to the output rate for outputting the bit stream from the queue.

2. The apparatus set forth in claim 1 wherein:

the processor determines the output rate such that the receiver of the model will neither overflow nor underflow.

3. The apparatus set forth in claim 2 wherein:

the processor is further responsive to a state of the queue and further determines the output rate such that the queue will not overflow.

4. The apparatus set forth in claim 3 wherein:

the processor further determines the output rate such that the queue will not underflow.

5. The apparatus set forth in any of claims 1 through 4 wherein:

the bit stream is a sequence of components, the components having varying lengths and each component including timing information indicating when the receiver must process the component and

the model includes

a current set of components which is the set of the components in the queue together with the set of the components that have been sent to but not yet processed by the receiver,

the timing information for the components in the current set,

the sizes of the components in the current set, and

a size of a bit buffer in the receiver of the model.

6. The apparatus set forth in claim 5 wherein:

the components are digitally-encoded video images.

7. The apparatus set forth in claim 6 wherein:

the video images are encoded according to the MPEG-2 standard.

8. The apparatus set forth in claim 2 wherein:

the bit stream is a sequence of components, the components having varying lengths and each component including timing information indicating when the receiver must process the component;

the model includes

a current set of components which is the set of the components in the queue together with the set of the components that have been sent to but not yet processed by the receiver,

the timing information for the components in the current set,

the sizes of the components in the current set, and

a size of a bit buffer in the receiver of the model; and

the processor determines the output rate for a given period of time by determining a minimum rate such that each component is output from the queue before the receiver must process the component and a maximum rate such that the total size of the components in the set of the components that have been sent to but not yet processed by the receiver does not exceed the size of the bit buffer in the receiver of the model.

9. The apparatus set forth in claim 8 wherein:

the processor increases the minimum rate for the given time period according to the number of bits that remain in the queue from a current component that is currently being output from the queue and the amount of time remaining until the current component must have been output from the queue and

the processor decreases the maximum rate for the given time period as the total size of the components in the set of components that have been sent to the receiver and not yet processed approaches the size of the bit buffer in the receiver of the model.

10. The apparatus set forth in claim 1, further including a bandwidth portion controller coupled to said output apparatus.

11. The apparatus set forth in claim 10, wherein said bandwidth portion controller dynamically determines a variable portion of said bit stream to be output to a medium.

12. The apparatus set forth is claim 10, wherein said bandwidth portion controller is coupled to a plurality of output apparatus.

13. A method of dynamically determining an output rate at which a bit stream encoded at a variable rate is output to a receiver, the method comprising the steps of:

receiving and storing the bit stream in a queue;

analyzing said bit stream for at least timing information and picture size information;

in a processor, applying a model of the receiver to information read from the bit stream to determine the output rate; and

outputting the bit stream from the queue at the output rate.

14. The method set forth in claim 13 wherein:

the output rate is determined such that the receiver of the model will neither overflow nor underflow.

15. The method set forth in claim 14 wherein the method further comprises the step of:

determining a state of the queue; and

the step of determining the output rate further determines the output rate such that the queue will not overflow.

16. The method set forth in claim 15 wherein:

the step of determining the output rate further determines the output rate such that the queue will not underflow.

17. The method set forth in any of claims 13 through 16 wherein

the bit stream is a sequence of components, the components having varying lengths and each component including timing information indicating when the receiver must process the component,

the model includes

a current set of components which is the set of the components in the queue together with the set of the components that have been sent to but not yet processed by the receiver,

the timing information for the components in the current set,

the sizes of the components in the current set, and

a size of a bit buffer in the receiver of the model, and

the step of determining the output rate is done for a given period of time and comprises the steps of

determining a minimum rate such that the component is output from the queue before the receiver must process the component and

determining a maximum rate such that the total size of the components in the set of the components that have been sent to but not yet processed by the receiver does not exceed the size of the bit buffer in the receiver of the model.

18. The method set forth in claim 17 wherein:

the step of determining the minimum rate increases the minimum rate for the given time period according to the number of bits that remain in the queue from a current component that is currently being output from the queue and the amount of time remaining until the current component must have been output from the queue and

the step of determining the maximum rate decreases the maximum rate for the given time period as the total size of the components in the set of components that have been sent to the receiver and not yet processed approaches the size of the bit buffer in the receiver of the model.

19. The method set forth in claim 17 wherein:

the components are digitally-encoded video images.

20. The method set forth in claim 19 wherein:

the video images are encoded according to the MPEG-2 standard.

21. An apparatus for controlling a rate at which an encoder encodes a bit stream, the apparatus comprising:

a queue for receiving and storing the bit stream from the encoder;

a bit stream analyzer for analyzing at least timing information and picture size information in said bit stream; and

a processor coupled to the bit stream and to the encoder for applying a model of a receiver for the bit stream to the information read from the bit stream to determine the rate at which the encoder encodes the bit stream.

22. The apparatus as set forth in claim 21, further including a bandwidth portion controller.

23. The apparatus as set forth in claim 22, wherein said bandwidth portion controller dynamically determines a variable portion of said bit stream to be output to a medium.