BLOCK PARTITIONING FOR A DATA STREAM

• US 20100211690A1
• Filed: 02/12/2010
• Published: 08/19/2010
• Est. Priority Date: 02/13/2009
• Status: Abandoned Application

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Luby, Michael G., Pakzad, Payam
• Application Number:
  US12/705,202
• Publication Number:
  US 20100211690A1
• Time in Patent Office: Days
• US Class Current: 709/231
• CPC Class Codes: H04L 65/70 Media network packetisation
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04N 21/4384 involving operations to reduce the access time, e.g. fast-tuning for reducing channel switching latency
• CPC Class Codes: H04N 21/8456 by decomposing the content in the time domain, e.g. in time segments

Abstract

A method for serving a data stream from a transmitter to a receiver includes: determining an underlying structure of the data stream; determining at least one objective, selected from a group of (1) reducing a start-up delay between when the receiver first starts receiving the data stream from the transmitter and when the receiver can start consumption of blocks of the data stream without interruption, according to the underlying structure, (2) reducing a transmission bandwidth needed to send the data stream, and (3) ensuring that the blocks of the data stream satisfy predetermined block constraints; and transmitting the blocks of the data stream consistent with the at least one objective and the underlying structure.

Claims

1. A method for serving a data stream from a transmitter to a receiver, comprising:

determining an underlying structure of the data stream;

determining at least one objective, selected from a group of (1) reducing a start-up delay between when the receiver first starts receiving the data stream from the transmitter and when the receiver can start consumption of blocks of the data stream without interruption, according to the underlying structure, (2) reducing a transmission bandwidth needed to send the data stream, and (3) ensuring that the blocks of the data stream satisfy predetermined block constraints; and

transmitting the blocks of the data stream consistent with the at least one objective and the underlying structure.

2. The method of claim 1, wherein the predetermined block constraints include a constraint that each block is of size greater than a given minimum block size and less than a given maximum block size.

3. A method for determining a block partition for serving a data stream of bits from a transmitter to a receiver, comprising:

defining a start position of a first block of the data stream as a first bit position in the data stream;

iteratively determining for each block, from the first block to a last possible block of the data stream, a first set of candidate start positions of a next consecutive block following a present block given that the first block starts at the first bit position of the data stream, until a first bit position after a last bit position of the data stream is in the first set of candidate start positions determined for the next consecutive block, and define a last block of the data stream as the present block;

defining an end-point of the last block of the data stream as the first bit position after the last bit position of the data stream;

for each block, from a block before the last block to the first block of the data stream,

determining an intersection of (1) the first set of candidate start positions of a next consecutive block following a present block given that the first block starts at the first bit position of the data stream; and

(2) a second set of candidate start positions of the next consecutive block following the present block given that a block immediately following the next consecutive block starts at the end-point of the next consecutive block; and

defining an end-point of the present block of the data stream as a bit position in the intersection; and

determining the block partition as the end-points of each block in the data stream.

4. The method of claim 3, wherein the last possible block of the data stream is determined from a size of the data stream and a minimum block size for the blocks of the data stream.

5. The method of claim 3, wherein

the data stream is defined by a cumulative stream size function, and a communication link for serving the data stream is defined by a cumulative link capacity function;

and

the block partition is determined with a reduced start-up delay for uninterrupted presentation of the data stream, given the cumulative stream size function and the cumulative link capacity function.

6. The method of claim 3, wherein

the data stream is defined by a cumulative stream size function, and a target start-up delay is determined for serving the data stream;

and

the block partition is determined with a reduced transmission bandwidth that ensures uninterrupted presentation of the data stream, given the cumulative stream size function and the target start-up delay.

7. The method of claim 3, wherein

a communication link for serving the data stream is defined by a cumulative link capacity function, and a target start-up delay is determined for serving the data stream;

and

the block partition is determined with a highest quality encoding of the data stream, from a set of possible encodings, that ensures uninterrupted presentation of the data stream, given the cumulative link capacity function and the target start-up delay.

8. A method for determining a global block partition for serving a data stream of bits from a transmitter to a receiver, the data stream defined by a global cumulative stream size function and having a plurality of seek-points, each seek-point being a point in the data stream where the receiver can begin consuming the data stream within a predetermined start-up delay, comprising:

dividing the data stream into a plurality of seek-blocks, each seek-block defined by a respective local cumulative stream size function, wherein data on one side of a particular seek-point is decoding independent of data on another side of the particular seek-point;

recursively defining, for each seek-block of the plurality of seek-blocks, a respective effective start-up delay that is less than or equal to the predetermined start-up delay;

determining, for each seek-block of the plurality of seek-blocks, a local block partition that ensures uninterrupted presentation of the respective seek-block with the respective effective start-up delay; and

determining the global block partition as the local block partitions of each seek-block of the plurality of seek-blocks in the data stream.

9. A server for serving a data stream, the server comprising:

a processor configured to determine an underlying structure of the data stream, and to determine at least one objective, selected from a group of (1) reducing a start-up delay between when a receiver first starts receiving the data stream from a transmitter and when the receiver can start consumption of blocks of the data stream without interruption, according to the underlying structure, (2) reducing a transmission bandwidth needed to send the data stream, and (3) ensuring that the blocks of the data stream satisfy predetermined block constraints; and

a transmitter coupled to the processor and configured to transmit the blocks of the data stream consistent with the at least one objective and the underlying structure.

10. The server of claim 9, wherein the predetermined block constraints include a constraint that each block is of size greater than a given minimum block size and less than a given maximum block size.

11. The server of claim 9, wherein the data stream comprises video content, and the blocks of the data stream are transmitted using User Datagram Protocol.

12. A server for determining a block partition for serving a data stream of bits from a transmitter to a receiver, the server comprising:

a processor configured to define a start position of a first block of the data stream;

determine a last block of the data stream by iteratively determining for each block, from the first block to a last possible block of the data stream, a first set of candidate start positions of a next consecutive block following a present block;

define an end-point of the last block of the data stream;

iteratively defining, for each block, from a block before the last block to the first block of the data stream, an end-point of a present block of the data stream as a bit position in an intersection of the first set and a second set of candidate start positions of a next consecutive block following the present block; and

determine the block partition as the end-points of each block in the data stream.

13. The server of claim 12 further comprising a memory coupled to the processor for storing the first set of candidate start positions.

14. The server of claim 12 further comprising a storage device coupled to the processor for storing content to be served as the data stream.

15. The server of claim 12 wherein

the data stream is defined by a cumulative stream size function, and a communication link for serving the data stream is defined by a cumulative link capacity function;

and

the block partition is determined with a reduced start-up delay for uninterrupted presentation of the data stream, given the cumulative stream size function and the cumulative link capacity function.

16. The server of claim 12 wherein

the data stream is defined by a cumulative stream size function, and a target start-up delay is determined for serving the data stream;

and

the block partition is determined with a reduced transmission bandwidth that ensures uninterrupted presentation of the data stream, given the cumulative stream size function and the target start-up delay.

17. The server of claim 12 wherein

a communication link for serving the data stream is defined by a cumulative link capacity function, and a target start-up delay is determined for serving the data stream;

and

the block partition is determined with a highest quality encoding of the data stream, from a set of possible encodings, that ensures uninterrupted presentation of the data stream, given the cumulative link capacity function and the target start-up delay.

18. A server for determining a global block partition for serving a data stream of bits from a transmitter to a receiver, the data stream defined by a global cumulative stream size function and having a plurality of seek-points, each seek-point being a point in the data stream where the receiver can begin consuming the data stream within a predetermined start-up delay, the apparatus comprising:

a processor configured to divide the data stream into a plurality of seek-blocks, each seek-block defined by a respective local cumulative stream size function, wherein data on one side of a particular seek-point is decoding independent of data on another side of the particular seek-point;

recursively define, for each seek-block of the plurality of seek-blocks, a respective effective start-up delay that is less than or equal to the predetermined start-up delay;

determine, for each seek-block of the plurality of seek-blocks, a local block partition that ensures uninterrupted presentation of the respective seek-block with the respective effective start-up delay; and

determine the global block partition as the local block partitions of each seek-block of the plurality of seek-blocks in the data stream.

19. A computer program product comprising:

a processor-readable medium storing processor-readable instructions configured to cause a processor to;

determine an underlying structure of a data stream;

determine at least one objective, selected from a group of (1) reducing a start-up delay between when a receiver first starts receiving the data stream from a transmitter and when the receiver can start consumption of blocks of the data stream without interruption, according to the underlying structure, (2) reducing a transmission bandwidth needed to send the data stream, and (3) ensuring that the blocks of the data stream satisfy predetermined block constraints; and

determine a block partition for serving the data stream from the transmitter to the receiver, wherein the block partition ensures that transmitting and receiving the blocks of the data stream is consistent with the at least one objective and the underlying structure.

20. The computer program product of claim 19, wherein the predetermined block constraints include a constraint that each block is of size greater than a given minimum block size and less than a given maximum block size.

21. A computer program product comprising:

a processor-readable medium storing processor-readable instructions configured to cause a processor to;

define a start position of a first block of a data stream as a first bit position in the data stream;

iteratively determine for each block, from the first block to a last possible block of the data stream, a first set of candidate start positions of a next consecutive block following a present block given that the first block starts at the first bit position of the data stream, until a first bit position after a last bit position of the data stream is in the first set of candidate start positions determined for the next consecutive block, and define a last block of the data stream as the present block;

define an end-point of the last block of the data stream as the first bit position after the last bit position of the data stream;

for each block, from a block before the last block to the first block of the data stream,

determine an intersection of (1) the first set of candidate start positions of a next consecutive block following a present block given that the first block starts at the first bit position of the data stream; and

(2) a second set of candidate start positions of the next consecutive block following the present block given that a block immediately following the next consecutive block starts at the end-point of the next consecutive block; and

define an end-point of the present block of the data stream as a bit position in the intersection; and

determine the block partition as the end-points of each block in the data stream.

22. The computer program product of claim 21, wherein the last possible block of the data stream is determined from a size of the data stream and a minimum block size for the blocks of the data stream.

23. The computer program product of claim 21, wherein

the data stream is defined by a cumulative stream size function, and a communication link for serving the data stream is defined by a cumulative link capacity function;

and

the block partition is determined with a reduced start-up delay for uninterrupted presentation of the data stream, given the cumulative stream size function and the cumulative link capacity function.

24. The computer program product of claim 21, wherein

the data stream is defined by a cumulative stream size function, and a target start-up delay is determined for serving the data stream;

and

the block partition is determined with a reduced transmission bandwidth that ensures uninterrupted presentation of the data stream, given the cumulative stream size function and the target start-up delay.

25. The computer program product of claim 21, wherein

a communication link for serving the data stream is defined by a cumulative link capacity function, and a target start-up delay is determined for serving the data stream;

and

the block partition is determined with a highest quality encoding of the data stream, from a set of possible encodings, that ensures uninterrupted presentation of the data stream, given the cumulative link capacity function and the target start-up delay.

26. A computer program product comprising:

a processor-readable medium storing processor-readable instructions configured to cause a processor to;

divide a data stream having a plurality of seek-points into a plurality of seek-blocks, each seek-point being a point in the data stream where the receiver can begin consuming the data stream within a predetermined start-up delay, wherein data on one side of a particular seek-point is decoding independent of data on another side of the particular seek-point;

recursively define, for each seek-block of the plurality of seek-blocks, a respective effective start-up delay that is less than or equal to the predetermined start-up delay;

determine, for each seek-block of the plurality of seek-blocks, a local block partition that ensures uninterrupted presentation of the respective seek-block with the respective effective start-up delay; and

determine a global block partition for serving the data stream as the local block partitions of each seek-block of the plurality of seek-blocks in the data stream.

27. An apparatus configured to serve a data stream from a transmitter to a receiver, the apparatus comprising:

means for determining an underlying structure of the data stream;

means for determining at least one objective, selected from a group of (1) reducing a start-up delay between when the receiver first starts receiving the data stream from the transmitter and when the receiver can start consumption of blocks of the data stream without interruption, according to the underlying structure, (2) reducing a transmission bandwidth needed to send the data stream, and (3) ensuring that the blocks of the data stream satisfy predetermined block constraints; and

means for transmitting the blocks of the data stream consistent with the at least one objective and the underlying structure.

28. The apparatus of claim 27, wherein the predetermined block constraints include a constraint that each block is of size greater than a given minimum block size and less than a given maximum block size.

29. An apparatus configured to determine a block partition for serving a data stream of bits from a transmitter to a receiver, the apparatus comprising:

means for defining a start position of a first block of the data stream as a first bit position in the data stream;

means for iteratively determining for each block, from the first block to a last possible block of the data stream, a first set of candidate start positions of a next consecutive block following a present block given that the first block starts at the first bit position of the data stream, until a first bit position after a last bit position of the data stream is in the first set of candidate start positions determined for the next consecutive block, and define a last block of the data stream as the present block;

means for defining an end-point of the last block of the data stream as the first bit position after the last bit position of the data stream;

for each block, from a block before the last block to the first block of the data stream,

means for determining an intersection of (1) the first set of candidate start positions of a next consecutive block following a present block given that the first block starts at the first bit position of the data stream; and

(2) a second set of candidate start positions of the next consecutive block following the present block given that a block immediately following the next consecutive block starts at the end-point of the next consecutive block; and

means for defining an end-point of the present block of the data stream as a bit position in the intersection; and

means for determining the block partition as the end-points of each block in the data stream.

30. The apparatus of claim 29, wherein the last possible block of the data stream is determined from a size of the data stream and a minimum block size for the blocks of the data stream.

31. The apparatus of claim 29, wherein

the data stream is defined by a cumulative stream size function, and a communication link for serving the data stream is defined by a cumulative link capacity function;

and

the block partition is determined with a reduced start-up delay for uninterrupted presentation of the data stream, given the cumulative stream size function and the cumulative link capacity function.

32. The apparatus of claim 29, wherein

the data stream is defined by a cumulative stream size function, and a target start-up delay is determined for serving the data stream;

and

the block partition is determined with a reduced transmission bandwidth that ensures uninterrupted presentation of the data stream, given the cumulative stream size function and the target start-up delay.

33. The apparatus of claim 29, wherein

a communication link for serving the data stream is defined by a cumulative link capacity function, and a target start-up delay is determined for serving the data stream;

and

the block partition is determined with a highest quality encoding of the data stream, from a set of possible encodings, that ensures uninterrupted presentation of the data stream, given the cumulative link capacity function and the target start-up delay.

34. An apparatus configured to determine a global block partition for serving a data stream of bits from a transmitter to a receiver, the data stream defined by a global cumulative stream size function and having a plurality of seek-points, each seek-point being a point in the data stream where the receiver can begin consuming the data stream within a predetermined start-up delay, the apparatus comprising:

means for dividing the data stream into a plurality of seek-blocks, each seek-block defined by a respective local cumulative stream size function, wherein data on one side of a particular seek-point is decoding independent of data on another side of the particular seek-point;

means for recursively defining, for each seek-block of the plurality of seek-blocks, a respective effective start-up delay that is less than or equal to the predetermined start-up delay;

means for determining, for each seek-block of the plurality of seek-blocks, a local block partition that ensures uninterrupted presentation of the respective seek-block with the respective effective start-up delay; and

means for determining the global block partition as the local block partitions of each seek-block of the plurality of seek-blocks in the data stream.