US5506844A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for configuring a statistical multiplexer to dynamically allocate communication channel bandwidth
Assignee: Google Technology Holdings LLC
•
Filing: 1994-05-20
•
Granted: 1996-04-09
•
Expires: 2014-05-20
Abstract
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.
Inventors
- 👤 R. Padmanabha Rao
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 20:17
CPC Classifications
H; H04; H04N; H04N21/00; H04N21/20; H04N21/23; H04N21/236; H04N21/2365; H04N21/23655; H04J; H04J3/00; H04J3/16; H04J3/1682; H04J3/1688; H04N19/00; H04N19/10; H04N19/102; H04N19/124; H04N19/126; H04N19/134; H04N19/146; H04N19/147; H04N19/154; H04N19/189; H04N19/196; H04N19/197; H04N19/198; H04N19/60; H04N19/61; H04N21/40; H04N21/43; H04N21/434; H04N21/4347; H04N21/60; H04N21/63; H04N21/637; H04N21/6377; H04N21/65; H04N21/658
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
180 words
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.
Claim 2
Dependent Claim
180 words
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.
Claim 3
Dependent Claim
101 words
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.
Claim 4
Dependent Claim
57 words
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.
Claim 5
Dependent Claim
44 words
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.
Claim 6
Dependent Claim
120 words
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.
Claim 7
Dependent Claim
49 words
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.
Claim 8
Dependent Claim
23 words
The statistical multiplexing process of claim 2 wherein said step of populating a dynamic table is done once in a predetermined time window.
Claim 9
Dependent Claim
31 words
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.
Claim 10
Dependent Claim
28 words
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.
Claim 11
Dependent Claim
15 words
The statistical multiplexing process of claim 8 wherein said parameter comprises a measure of distortion.
Claim 12
Dependent Claim
41 words
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.
Claim 13
Dependent Claim
27 words
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.
Claim 14
Dependent Claim
27 words
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.
Claim 15
Dependent Claim
128 words
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.
Claim 16
Dependent Claim
49 words
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.
Claim 17
Dependent Claim
19 words
The statistical multiplexing process of claim 3 wherein said plurality of data streams includes an encoded video data stream.
Claim 18
Dependent Claim
121 words
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.
Claim 19
Dependent Claim
121 words
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.
Claim 20
Dependent Claim
39 words
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.
Claim 21
Dependent Claim
21 words
The statistical multiplexing process of claim 18 wherein in said initialization step, each variable rate encoder is assigned a distortion threshold.
Claim 22
Dependent Claim
83 words
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.
Claim 23
Dependent Claim
103 words
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.
Claim 24
Dependent Claim
55 words
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.
Claim 25
Dependent Claim
44 words
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.
Claim 26
Dependent Claim
27 words
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.
Claim 27
Dependent Claim
40 words
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.
Claim 28
Dependent Claim
27 words
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.
Claim 29
Dependent Claim
27 words
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.
Claim 30
Dependent Claim
115 words
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.
Claim 31
Dependent Claim
47 words
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.
Claim 32
Dependent Claim
19 words
The statistical multiplexing process of claim 21 wherein said plurality of data streams includes an encoded video data stream.
Claim 33
Dependent Claim
237 words
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.
Claim 34
Dependent Claim
237 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-04-09 | 1999-10-09 | 2000-04-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-04-09 | 2003-10-09 | 2004-04-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-04-09 | 2007-10-09 | 2008-04-09 | $7700.00 | Window Closed / Lapsed |