Method and apparatus for multiplexing video programs for improved channel utilization

A method for multiplexing a set of n program streams to form a multiplex, each program stream in said set having a corresponding channel, each program stream in said set decodeable by a corresponding decoder, each corresponding decoder including a corresponding decoder buffer, said method comprising the steps of:

• (a) partitioning each program stream in said set into packets;
• (b) determining a next packet to append to said multiplex by selecting a channel that has a decoder buffer that is not approaching a full state;
• and
• (c) appending said next packet to said multiplex;
• wherein said determining step includes a loop that terminates when a channel is selected that has a decoder buffer that is not approaching a fall state, said loop including:
• (a) selecting a next channel;
• and
• (b) evaluating whether or not the decoder buffer of said next channel is approaching a full state;
• wherein said step of selecting said next channel substantially balances the decoder buffers;
• wherein said full state is the state of not having enough room for the next available packet to be sent of said next channel;
• further including the steps of deciding if all decoder buffers are approaching a full state, and, if all buffers are approaching a full state, assigning an alternate packet to said next packet.

A method for multiplexing a set of n program streams to form a multiplex, each program stream in said set having a corresponding channel, each program stream in said set decodeable by a corresponding decoder, each corresponding decoder including a corresponding decoder buffer, said method comprising the steps of:

• (a) partitioning each program stream in said set into packets;
• (b) determining a next packet to append to said multiplex by selecting a channel that has a decoder buffer that is not approaching a full state;
• and
• (c) appending said next packet to said multiplex;
• wherein said determining step includes a loop that terminates when a channel is selected that has a decoder buffer that is not approaching a full state, said loop including:
• (a) selecting a next channel;
• and
• (b) evaluating whether or not the decoder buffer of said next channel is approaching a full state;
• wherein said step of selecting said next channel substantially balances the decoder buffers;
• wherein said fall state is the state of not having enough room for the next available packet to be sent of said next channel;
• wherein substantially balancing keeps substantially the same time duration stored in each decoder buffer;
• wherein said step of evaluating includes using one or more time stamps in the program stream of said next packet.

An apparatus for multiplexing a set of n program streams to form a multiplex, each program stream in said set being decodeable by a corresponding decoder, each program stream in said set partitioned into packets, each corresponding decoder including a corresponding decoder buffer, said apparatus comprising:

• (a) a means for determining a next packet of said packets to append to said multiplex, said determining means including means for ascertaining whether or not a decoder buffer is approaching a fall state;
• (b) a means for determining a next packet into said packets to append to said multiplex, said determining means, including means for balancing the decoder buffers;
• and
• (c) a means coupled to said determining means, for appending said next packet to said multiplex.

An apparatus for multiplexing a set of n program streams to form a multiplex, each program stream in said set being decodeable by a corresponding decoder, each program stream in said set partitioned into packets, each corresponding decoder including a corresponding decoder buffer, said apparatus comprising:

• (a) a means for determining a next packet of said packets to append to said multiplex, said determining means including means for ascertaining whether or not a decoder buffer is approaching a full state;
• (b) a means for determining a next packet into said packets to append to said multiplex, said determining means, including means for balancing the decoder buffers;
• and
• (c) a means coupled to said determining means, for appending said next packet to said multiplex,
• wherein said means for ascertaining also ascertains whether or not a buffer is about to empty.

A server system for generating multiplexes of a set of encoded program streams, said server system comprising:

• (a) a controller;
• (b) a plurality of server modules, each server module in said plurality coupled to said controller, each server module in said plurality being capable of storing the compressed data of a program stream, said compressed data partitioned into packets, and each server module in said plurality having an output port for said compressed data;
• (c) a set of one or more MUX modules, each MUX module coupled to said controller, each MUX module in said set being capable of generating a multiplex, and each MUX module in said set having an input port for compressed data;
• and
• (d) a data transmission means coupled to the output ports of said server modules and to the input ports of said MUX modules;
• whereby
• said transmission means under control of said controller enables a selected MUX to form said multiplex of the compressed data from the output ports of a selected subset of one or more server modules, the compressed data from each server port in said selected subset being decodeable by a decoder corresponding to said each server port, each corresponding decoder including a corresponding decoder buffer, and
• said controller determines a next packet for said selected MUX module to append to said multiplex by selecting a channel that has a decoder buffer that is not approaching a full state.

A method of multiplexing a set of n program streams to form a multiplex, each program stream being decodeable by a corresponding decoder having a corresponding decoder buffer, the method comprising the steps of:

• partitioning each program stream into packets;
• maintaining a record of a current level of fullness of each decoder buffer;
• determining a next packet to append to the multiplex by selecting a program stream that the record indicates has a corresponding decoder buffer that is not approaching a full state and using a packet from the selected program stream as the next packet;
• and
• appending the next packet to the multiplex.

A method of multiplexing a set of n program streams to form a multiplex, each program stream being decodeable by a corresponding decoder having a corresponding decoder buffer, the method comprising the steps of:

• partitioning each program stream into packets;
• maintaining a record of a current level of fullness of each decoder buffer;
• determining a next packet to append to the multiplex by checking whether the record indicates that all decoder buffers are full;
• selecting a program stream and using a packet therefrom as the next packet in response to the record indicating that not all decoder buffers are full;
• and appending the next packet to the multiplex.

An apparatus for multiplexing a set of n program streams to form a multiplex, each program stream being decodeable by a corresponding decoder having a corresponding decoder buffer, comprising:

• means for partitioning each program stream into packets;
• means for maintaining a record of a current level of fullness of each decoder buffer;
• means for determining a next packet to append to the multiplex by checking whether the record indicates that all decoder buffers are full;
• means for selecting a program stream and using a packet therefrom as the next packet in response to the record indicating that not all decoder buffers are full;
• and
• means for appending the next packet to the multiplex.

A server system for generating multiplexes of encoded program streams, each program stream being decodeable by a corresponding decoder having a corresponding decoder buffer, the server system comprising:

• a data transmission bus;
• a plurality of server modules that each have an output coupled to the data transmission bus, each server module being configured to store a program stream that has been compressed and partitioned into packets and to provide the program stream to the data transmission bus;
• a set of one or more MUX modules that each have a plurality of input ports coupled to the data transmission bus, each MUX module being configured to receive one or more program streams from the data transmission bus and to generate an output multiplex;
• and
• a controller coupled to the server modules and to the MUX modules, the controller being configured to route program streams from a subset of one or more of the server modules to a selected one of the MUX modules, the controller being further configured to maintain a record of a current level of fullness of each decoder buffer and to determine a next packet to append to the output multiplex of the selected MUX module by selecting a program stream from one of the subset of server modules that the record indicates has a corresponding decoder buffer that is not approaching a fall state and using a packet from the selected program stream as the next packet.