Method for configuring a statistical multiplexer to dynamically allocate communication channel bandwidth

• US 5,506,844 A
• Filed: 05/20/1994
• Issued: 04/09/1996
• Est. Priority Date: 05/20/1994
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Compression Labs Incorporated (Asure Software)
• Inventors: Rao, R. Padmanabha
• Primary Examiner(s): Kizou, Hassan
• Application Number:
  US08/246,442
• Time in Patent Office: 690 Days
• Field of Search: 370/56, 370/60, 370/60.1, 370/80, 370/84, 370/94.1, 370/94.2, 370/112, 370/118, 328/104, 328/154, 307/243, 327/407
• US Class Current: 370/468
• 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: H04N 19/126 Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/154 Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion use of rate-distortion criteria H04N19/147
• CPC Class Codes: H04N 19/196 being specially adapted for the computation of encoding parameters, e.g. by averaging previously computed encoding parameters processing of motion vectors H04N19/513
• CPC Class Codes: H04N 19/197 including determination of the initial value of an encoding parameter H04N19/56 takes precedence
• CPC Class Codes: H04N 19/198 including smoothing of a sequence of encoding parameters, e.g. by averaging, by choice of the maximum, minimum or median value
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 21/2365 Multiplexing of several video streams
• 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/4347 Demultiplexing of several video streams
• CPC Class Codes: H04N 21/6377 directed to server one-way streaming services wherein the source is controlled by the destination H04L65/613
• CPC Class Codes: H04N 21/658 Transmission by the client directed to the server

Abstract

A statistical multiplexer selectively passes packets of encoded data from a plurality of encoders to a communication channel so as to maximize the quality of the encoded data. The statistical multiplexer determines what fraction of the communication channel capacity should be allocated to an application so as to optimize the quality of the decoded signals of the applications processed by the statistical multiplexer. A table is stored in a memory of the statistical multiplexer that has an entry for each unit of encoded data that can be transmitted over the communication channel in a predetermined time interval. The statistical multiplexer accesses each entry in the table to obtain a pointer, e.g., an address, to an encoder that can transmit the next unit of encoded data to the communication channel. The statistical multiplexer dynamically adjusts the data compression rate for each variable rate application so that the quality of all the encoded data streams are optimized over a window, and builds a new table that reflects the adjusted rates. In one application, the table is broken into a static table and a dynamic table. The static table is built at configuration time and while one dynamic table is being used for a window, a new dynamic table is built for the next window.

Claims

1. A statistical multiplexing process for a plurality of data streams competing for access to a communication channel comprising the steps of:

a) populating a static table in a memory of a statistical multiplexer wherein said static table has an entry for each unit of data that can be sent over said communication channel in a predetermined time period wherein said static table populating step further comprises;

i) allocating an entry in said static table to one of said plurality of data streams;

ii) storing a predetermined code in said entry if said entry is allocated to a data stream that has a variable rate;

iii) storing a pointer in said entry if said entry is allocated to a data stream that has a fixed rate wherein said pointer identifies the fixed rate data stream; and

iv) repeating steps i) to iii) for each entry in said static table; and

b) using each table entry in said static table in selecting the data stream in said plurality of data streams that sends the next unit of data to the communication channel.

2. The statistical multiplexing process of claim 1 further comprising the step of:

populating a dynamic table wherein said dynamic table populating step further comprises;

i) allocating an entry in said dynamic table to one of A) one of a plurality of variable rate data streams in said plurality of data streams and B) a variable rate data stream of idle units of data;

ii) storing in said entry a pointer to said variable rate data stream upon allocation of said entry to said variable rate data stream; and

iii) repeating steps i) to ii) for each entry in said dynamic table.

3. The statistical multiplexing process of claim 2 wherein said step of using each entry in said static table further comprises:

accessing an entry in said dynamic table, upon detecting an entry in said static table containing said predetermined code, to select the variable rate data stream that sends the next unit of data to the communication channel.

4. The statistical multiplexing process of claim 3 further comprising the step of:

adjusting a number of units of data allocated for transmission over said communication channel for each of said variable rate data streams that has a quality measurement parameter outside a predetermined range.

5. The statistical multiplexing process of claim 4 further comprising the step of:

populating a second dynamic table using said adjusted number of units of data allocated for transmission over said communication channel wherein said second dynamic table populating step further comprises;

i) allocating an entry in said second dynamic table to one of A) one of said plurality of variable rate data streams in said plurality of data streams and B) a variable rate data stream of idle units of data;

ii) storing in said entry a pointer to said variable rate data stream upon said entry being allocated to said variable rate data stream; and

iii) repeating steps i) to ii) for each entry in said second dynamic table.

6. The statistical multiplexing process of claim 5 further comprising the step of:

switching from said dynamic table to said second dynamic table so that said second dynamic table is available for use in another predetermined time window following a predetermined time window in which said dynamic table is used.

7. The statistical multiplexing process of claim 2 wherein said step of populating a dynamic table is done once in a predetermined time window.

8. The statistical multiplexing process of claim 3 further comprising the step of:

collecting data for each variable rate data stream to generate a parameter that characterizes said variable rate data stream.

9. The statistical multiplexing process of claim 8 further comprising the step of:

generating for each variable rate data stream said parameter that characterizes said variable rate data stream.

10. The statistical multiplexing process of claim 8 wherein said parameter comprises a measure of distortion.

11. The statistical multiplexing process of claim 9 further comprising the step of:

adjusting a number of units of data allocated for transmission over said communication channel for each of said variable rate data streams with said parameter outside a predetermined range.

12. The statistical multiplexing process of claim 11 wherein a lower limit of said predetermined range is a product of a first hysteresis coefficient and a distortion parameter.

13. The statistical multiplexing process of claim 11 wherein an upper limit of said predetermined range is a product of a second hysteresis coefficient and a distortion parameter.

14. The statistical multiplexing process of claim 11 further comprising the step of:

populating a second dynamic table using said adjusted number of units of data allocated for transmission over said communication channel for each of said variable rate data streams wherein said second dynamic table populating step further comprises;

i) allocating an entry in said second dynamic table to one of A) one of said plurality of variable rate data streams in said plurality of data streams and B) a variable rate data stream of idle units of data;

ii) storing in said entry a pointer to said variable rate data stream upon said entry being allocated to said variable rate data stream; and

iii) repeating steps i) to ii) for each entry in said second dynamic table.

15. The statistical multiplexing process of claim 14 further comprising, the step of:

switching from said dynamic table to said second dynamic table so that said second dynamic table is available for use in another predetermined time window following a predetermined time window in which said dynamic table is used.

16. The statistical multiplexing process of claim 3 wherein said plurality of data streams includes an encoded video data stream.

17. A statistical multiplexing process for a plurality of encoded data streams sharing access to a communication channel comprising the steps of:

assigning a rate to each variable rate encoder that generates one of said plurality of encoded data streams, and to each fixed rate encoder that generates one of said plurality of encoded data streams;

populating a table having a predetermined number of entries using said assigned rates

wherein each entry in said table is allocated to one of (i) one of said plurality of encoded data streams and (ii) a variable rate data stream of idle packets; and

using each table entry in said table to select an encoded data stream that sends the next packet to the communication channel.

18. The statistical multiplexing process of claim 17 wherein said assigning a rate step is performed in an initialization step and each fixed rate encoder is assigned an actual rate and each variable rate encoder is assigned a guaranteed rate.

19. The statistical multiplexing process of claim 18 wherein in said initialization step, each variable rate encoder is assigned a distortion threshold.

20. The statistical multiplexing process of claim 18 wherein said step of populating a table further comprises:

i) storing a predetermined code in said entry if said entry is allocated to an encoded data stream that has a variable rate;

ii) storing a pointer in said entry if said entry is allocated to an encoded data stream that has a fixed rate wherein said pointer identifies the fixed rate data stream; and

iii) repeating steps i) to ii) for each entry in said table.

21. The statistical multiplexing process of claim 20 further comprising the step of:

populating a second table wherein said second table populating step further comprises;

i) allocating an entry in said second table to one of A) one of a plurality of variable rate encoded data streams in said plurality of encoded data streams and B) a variable rate data stream of idle packets;

ii) storing in said entry a pointer to said variable rate encoded data stream upon said entry being allocated to said variable rate encoded data stream; and

iii) repeating steps i) and ii) for each entry in said second table.

22. The statistical multiplexing process of claim 21 wherein said step of using each entry in said first-mentioned table further comprises:

accessing an entry in said second table, upon detecting an entry in said first-mentioned table containing said predetermined code, to select the variable rate data stream that sends the next packet to the communication channel.

23. The statistical multiplexing process of claim 21 further comprising the step of:

collecting data for each variable rate encoded data stream from a variable rate encoder to generate a distortion parameter that characterizes said variable rate encoded data stream from said variable rate encoder.

24. The statistical multiplexing process of claim 23 further comprising the step of:

generating said distortion parameter that characterizes a quality of said variable rate encoded data stream.

25. The statistical multiplexing process of claim 24 further comprising the step of:

adjusting a number of packets allocated to each of said variable rate encoded data streams using said distortion parameter if said distortion parameter is outside a predetermined range.

26. The statistical multiplexing process of claim 25 wherein a lower limit of said predetermined range is a product of a first hysteresis coefficient and a distortion threshold.

27. The statistical multiplexing process of claim 25 wherein an upper limit of said predetermined range is a product of a second hysteresis coefficient and a distortion threshold.

28. The statistical multiplexing process of claim 25 further comprising the step of:

populating a third table using said adjusted number of packets allocated for transmission over said communication channel wherein said third table populating step further comprises;

i) allocating an entry in said third table to one of A) one of said plurality of variable rate encoded data streams in said plurality of encoded data streams and B) a variable rate data stream of idle packets;

ii) storing in said entry a pointer to said variable rate encoded data stream upon said entry being allocated to said variable rate data stream; and

iii) repeating steps i) to ii) for each entry in said third table.

29. The statistical multiplexing process of claim 28 further comprising the step of:

switching from said second table to said third table so that said third table is available for use in another predetermined time window following a predetermined time window in which said second table is used.

30. The statistical multiplexing process of claim 21 wherein said plurality of data streams includes an encoded video data stream.

31. A statistical multiplexing process for a plurality of encoded data streams sharing a communication channel comprising the steps of:

collecting data for each variable rate encoded data stream from a variable rate encoder in said plurality of encoded data streams to generate a distortion parameter that characterizes said variable rate encoded data stream;

generating for each variable rate encoded data stream said distortion parameter that characterizes a quality of said variable rate encoded data stream;

adjusting a number of packets allocated to each of said variable rate encoded data streams in a selected time period if said distortion parameter is outside a predetermined range;

populating a table using said adjusted number of allocated packets wherein said table populating step further comprises;

i) allocating an entry in said table to one of A) a variable rate encoded data stream in a plurality of variable rate encoded data streams that are included in said plurality of encoded data streams and B) a variable encoded data stream of idle packets;

ii) storing in said entry a pointer to said variable rate encoded data stream upon said entry being allocated to said variable rate encoded data stream; and

iii) repeating steps i) to ii) for each entry in said table;

switching to said table so that said table is used by a statistical multiplexer to determine the variable rate encoded data stream that sends the next packet to said communication channel.