Efficient software bitstream rate generator for video server

• US 7,904,931 B2
• Filed: 09/10/2002
• Issued: 03/08/2011
• Est. Priority Date: 09/12/2001
• Status: Active Grant

• Current Assignee: Cox Communications Incorporated (Cox Enterprises Incorporated)
• Original Assignee: Cox Communications Incorporated (Cox Enterprises Incorporated)
• Inventors: Frederickson, James, Taylor, Clement G.
• Primary Examiner(s): Koenig; Andrew Y
• Assistant Examiner(s): Chin; Ricky
• Application Number:
  US10/238,398
• Publication Number:
  US 20030115609A1
• Time in Patent Office: 3,101 Days
• Field of Search: 725/86, 725/93, 725/97, 370/429, 370/395.4
• US Class Current: 725/93
• CPC Class Codes: H04N 21/23805 Controlling the feeding rate to the network, e.g. by controlling the video pump
• CPC Class Codes: H04N 21/64769 for rate control flow control in packet networks H04L47/10
• CPC Class Codes: H04N 7/17318 Direct or substantially direct transmission and handling of requests

Abstract

An apparatus and a method for constraining the delivery rate of a plurality of bitstreams, such as MPEG bitstreams using a single software process.

Claims

1. A method of processing data streams, comprising:

receiving a plurality of data streams having a plurality of bit rates and comprising packets of data, each of the plurality of data streams comprising only a constant bit rate;

determining a bit rate associated with each packet of data of the plurality of data streams;

providing a priority queue including a plurality of queues in memory for queuing the received plurality of data streams, each queue in the priority queue being associated with a single data stream, each of the queues in the priority queue having a stream deadline element associated therewith, wherein each stream deadline element has a stream identifier for identifying a data stream in the queue corresponding to the stream deadline element and a deadline key for identifying a deadline based on the determined bit rate associated with packets of the identified data stream for forwarding packets associated with the steam deadline element;

arranging in priority order the queues in the priority queue holding content streams from a highest priority queue to a lowest priority queue based on the deadline keys in each of the plurality of queues;

retrieving, from the highest priority queue in the priority queue, a stream deadline element including a respective stream deadline key and a stream identifier identifying the data stream associated with highest priority queue;

examining a deadline identified by the deadline key from the retrieved stream deadline element of the highest priority queue to determine whether the deadline associated with the highest priority queue has expired; and

transmitting at least one packet in the highest priority queue associated with the data stream identified by the stream identifier only when the deadline has expired;

wherein data streams having a relatively low bit rate according to the deadline identified by the deadline keys are processed less frequently than data streams having a relatively high bit rate according to the deadline identified by the deadline keys and wherein the examining the deadline identified by the deadline key from the retrieved stream deadline element of the highest priority queue enables the plurality of data streams to be transmitted at different rates based on the bit rate of each data stream.

2. The method of claim 1 further comprising enabling a processing element to perform an alternate task when the deadline has not expired.

3. The method of claim 2, wherein said alternate task is exited when the deadline has expired.

4. The method of claim 1, further comprising:

calculating, after transmitting said at least one packet, a new deadline of at least one next packet associated with said identified data stream; and

inserting, into said priority queue, a new stream deadline element for said identified data stream including a respective stream deadline key using said new calculated deadline.

5. The method of claim 4, wherein said new deadline is calculated using the determined bit rate of the identified data stream and said stream deadline element is inserted into the priority queue based upon the relative priority of the at least one next packet.

6. The method of claim 1, further comprising:

calculating, for at least one packet of a new data stream to be transmitted, a deadline associated with said new data stream; and

inserting, into said priority queue, a new stream deadline element for said new stream including a respective stream deadline key using said new calculated deadline.

7. The method of claim 1, wherein said stream deadline elements operate to provide a rate generator function within a multiple stream delivery system.

8. The method of claim 7, wherein said multiple stream delivery system also comprises a multiple bit rate delivery system.

9. The method of claim 1, wherein a priority indicative position of a stream deadline element within said priority queue is adapted in response to changes in the respective deadline key of the stream deadline element.

10. The method of claim 1, wherein said stream deadline elements operate to provide a rate generator function within a multiple stream, multiple bit rate delivery system.

11. A method of regulating the delivery time of content, comprising:

receiving a plurality of content streams having a plurality of bit rates and comprising packets of data, each of the plurality of data streams comprising only a constant bit rate;

determining a bit rate associated with each packet of data of the plurality of data streams;

providing a priority queue including a plurality of queues in memory for queuing the received plurality of data streams, each queue in the priority queue being associated with a single data stream, each of the queues in the priority queue having a stream deadline element associated therewith, wherein each stream deadline element has a stream identifier for identifying a data stream in the queue corresponding to the stream deadline element and a deadline key for identifying a deadline based on the determined bit rate associated with packets of the identified data stream for forwarding packets associated with the steam deadline element;

arranging in priority order the queues in the priority queue holding content streams from a highest priority queue to a lowest priority queue based on the deadline keys in each of the plurality of queues;

retrieving, from the highest priority queue in the priority queue, a stream deadline element including a respective stream deadline key and a stream identifier identifying the data stream associated with highest priority queue;

examining a deadline identified by the deadline key from the retrieved stream deadline element of the highest priority queue to determine whether the deadline associated with the highest priority queue has expired;

when the deadline has not expired, performing tasks other than transmitting packets;

when the deadline has expired, performing the steps of;

transmitting at least one packet in the highest priority queue associated with the data stream identified by the stream identifier;

calculating, after transmitting at least one packet in the highest priority queue associated with the data stream identified by the stream identifier, a new deadline of at least one next packet associated with an identified content stream including said transmitted packet, wherein said new deadline is calculated using the determined bit rate of said identified content stream;

inserting, into said priority queue, a new stream deadline element for said identified content stream including a respective stream deadline key using said new calculated deadline; and

inserting said at least one next packet into the priority queue according to its relative streaming deadline, said at least one next packet comprising a next portion of said identified content stream including said transmitted packet;

wherein examining the deadline identified by the deadline key from the retrieved stream deadline element of the highest priority queue enables the plurality of content streams to be transmitted at different rates based on the bit rate of each content stream.

12. The method of claim 11, further comprising:

inserting a new stream packet into the priority queue according to its relative streaming deadline, said new stream packet comprising a packet of a new content stream to be transmitted.

13. The method of claim 12, further comprising:

calculating, using the determined bit rate of said new content stream, a new streaming deadline of said new stream packet using the determined bit rate of said new content stream.