Method for delivering large amounts of data with interactivity in an on-demand system

• US 7,174,384 B2
• Filed: 07/31/2001
• Issued: 02/06/2007
• Est. Priority Date: 07/31/2001
• Status: Expired due to Fees

• Current Assignee: Dinastech IPR Limited
• Original Assignee: Dinastech IPR Limited
• Inventors: Chan, Gin-Man, Chan, Kwong-Wing Raymond, Lam, Wing-Kai, Cheung, Kwok-Wai
• Primary Examiner(s): PWU, JEFFREY C
• Application Number:
  US09/917,638
• Publication Number:
  US 20030074667A1
• Time in Patent Office: 2,016 Days
• Field of Search: 709/231, 348/388.1, 348/412.1, 375/240.24, 375/240.12, 717/174, 717/178, 725/87, 725/101, 725/102, 725/100, 715/723, 715/720, 386/68
• US Class Current: 709/231
• CPC Class Codes: H04N 21/26233 involving content or additional data duration or size, e.g. length of a movie, size of an executable file
• CPC Class Codes: H04N 21/26275 for distributing content or additional data in a staggered manner, e.g. repeating movies on different channels in a time-staggered manner in a near video on demand system
• CPC Class Codes: H04N 21/26616 for merging a unicast channel into a multicast channel, e.g. in a VOD application, when a client served by unicast channel catches up a multicast channel to save bandwidth data multicast over packet-switching network H04L12/18
• CPC Class Codes: H04N 21/47202 for requesting content on demand, e.g. video on demand
• CPC Class Codes: H04N 21/8456 by decomposing the content in the time domain, e.g. in time segments
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

A method and system for delivering data over a network to a large number of clients, which may be suitable for building large-scale Video-on-Demand (VOD) systems. In current VOD systems, the client may suffer from a long latency before starting to receive requested data that is capable of providing sufficient interactive functions, or the reverse, without significantly increasing the network load. The method utilizes two groups of data streams, one responsible for minimizing latency while the other provides the required interactive functions. In the anti-latency data group, uniform, or non-uniform or hierarchical staggered stream intervals may be used. The system may have a relatively small startup latency while users may enjoy most of the interactive functions that are typical of video recorders including fast-forward, forward-jump, and so on. Furthermore, the system can maintain the number of data streams, and therefore the bandwidth, required.

Claims

1. A method for transmitting data over a network to at least one client having a latency time to initiate transmission of said data to the client, including the steps of:

generating M anti-latency data streams containing at least a leading portion of data for receipt by the client, wherein said data is fragmented into K segments each requiring a time T to transmit over the network, and wherein each of the M anti-latency data streams contains substantially identical data having J segments that are repeated continuously within said anti-latency data stream, and each successive anti-latency data stream is staggered by an anti-latency time interval ≧

T; and

generating N interactive data streams containing at least a remaining portion of said data for the client to merge into after receiving at least a portion of an anti-latency data stream, wherein each of the N interactive data streams repeats continuously within said interactive data stream, and each successive interactive data stream is staggered by an interactive time interval;

wherein;

J, K, M and N are integers,

T is a length of time, and

M=N=J=√

R/T,

where R is the length of time required to transmit said data over the network.

2. A method for transmitting data over a network to at least one client having a latency time to initiate transmission of said data to the client, including the steps of:

generating M anti-latency data streams containing at least a leading portion of data for receipt by the client, wherein said data is fragmented into K segments each requiring a time T to transmit over the network, wherein each anti-latency data stream includes;

a leading data stream containing at least one leading segment of the leading portion of said data being repeated continuously within the leading data stream; and

a plurality of finishing data streams each having J segments, each of the finishing data streams containing the rest of the leading portion of said data; and

being repeated continuously within said finishing data stream, and wherein each successive finishing data stream is staggered by an anti-latency time interval ≧

T; and

generating N interactive data streams containing at least a remaining portion of said data for the client to merge into after receiving at least a portion of an anti-latency data stream, wherein each of the N interactive data streams is repeated continuously within said interactive data stream, and each successive interactive data stream is staggered by an interactive time interval;

wherein;

J, K, M and N are integers,

T is a length of time,

M=(J/2)+1, and

J=√

2K.

3. A method for transmitting data over a network to at least one client having a latency time to initiate transmission of said data to the client, including the steps of:

generating M anti-latency data streams containing at least a leading portion of data for receipt by the client, wherein said data is fragmented into K segments each requiring a time T to transmit over the network, and wherein the anti-latency data streams are generated such that an m^th anti-latency data stream has F_m segments, wherein F_m is an m^th Fibonacci number; and

the F_m segments are repeated continuously within the m^th anti-latency data stream; and

generating N interactive data streams containing at least a remaining portion of said data for the client to merge into after receiving at least a portion of an anti-latency data stream, wherein each of the N interactive data streams repeats continuously within said interactive data stream, and each successive interactive data stream is staggered by an interactive time interval=KT/N;

wherein m starts from 4 and the repeating 1^st, 2^nd, and 3^rd anti-latency data streams have the following configuration;

and wherein;

K, M and N are integers, and

T is a length of time.

4. A method for transmitting data over a network to at least one client having a latency time to initiate transmission of said data to the client, including the steps of:

generating M anti-latency data streams containing at least a leading portion of data for receipt by the client, wherein said data is fragmented into K segments each requiring a time T to transmit over the network, and wherein in the M anti-latency data streams the leading portion of said data contains 1 to J leading labeled data segments, and the leading data segments are distributed in the M anti-latency data streams such that a j^th leading segment is repeated by an anti-latency time interval ≦

jT within the anti-latency data streams; and

generating N interactive data streams containing at least a remaining portion of said data for the client to merge into after receiving at least a portion of an anti-latency data stream, wherein each of the N interactive data streams repeats continuously within said interactive data stream, and each successive interactive data stream is staggered by an interactive time interval=KT/N;

wherein;

J, K, M and N are integers,

T is a length of time,

J=K/N, and

$M\ge <br><br>\underset{j=1}{\overset{j=J}{\sum <br><br>}}<br><br>\left(\frac{1}{j}\right)<br><br><br><br>\mathrm{and}<br><br><br><br>J=\frac{K}{N}.$

5. A method for transmitting data over a network to at least one client having a latency time to initiate transmission of said data to the client, including the steps of:

generating M anti-latency data streams containing at least a leading portion of data for receipt by the client, wherein said data is fragmented into K segments each requiring a time T to transmit over the network, and wherein in the M anti-latency data streams the leading portion of said data contains 1 to J leading labeled data segments, and the leading data segments are distributed in the M anti-latency data streams such that a j^th leading segment is repeated by an anti-latency time interval ≦

JT within the anti-latency data streams; and

generating N interactive data streams containing at least a remaining portion of said data for the client to merge into after receiving at least a portion of an anti-latency data stream, wherein each of the N interactive data streams repeats continuously within said interactive data stream, and each successive interactive data stream is staggered by an interactive time interval=KT/N;

wherein;

J, K, M and N are integers,

T is a length of time,

J=K/N,

and wherein six of the M anti-latency data streams containing the leading data segments are arranged as follows;

wherein blank segments contain any data.

6. A method for transmitting data over a network to at least one client having a latency time to initiate transmission of said data to the client, including the steps of:

generating M anti-latency data streams containing at least a leading portion of data for receipt by the client, wherein said data is fragmented into K segments each requiring a time T to transmit over the network, and wherein the M anti-latency data streams contain the leading portion of said data, and further include two batches of data streams comprising a first set of anti-latency data streams and a second set of anti-latency data streams, such that

the first anti-latency data streams have A first anti-latency data streams from I to A, wherein an a^th anti-latency data stream has F_a segments, where F_a is an a^th Fibonacci number, and the F_a segments are repeated continuously within the a^th first anti-latency data stream

the second anti-latency data streams have B second anti-latency data streams wherein each of the B second anti-latency data streams contains substantially identical data repeated continuously within said second anti-latency data stream, and wherein each successive second anti-latency data stream is staggered by a coarse-jump frame period, such that the client can perform a coarse-jump function when the client is connected to a second anti-latency data steam; and

generating N interactive data streams containing at least a remaining portion of said data for the client to merge into after receiving at least a portion of an anti-latency data stream;

wherein;

A, B, K, M and N are integers, and

T is a length of time.

7. The method of claim 6, further including the steps of:

connecting the client to at least the a^th and (a+1)^th first anti-latency data streams when the client raises a request for said data;

buffering the data in at least the a^th and (a+1)^th first anti-latency data streams in the client;

subsequently connecting the client to successive first anti-latency data streams; and

repeating the previous steps until all data in the A first anti-latency data streams is received by the client.

8. The method of claim 7, further including the steps of:

connecting the client to any one of the B second anti-latency data streams after all data in the first anti-latency data streams is received by the client; and

connecting the client to anyone of the N interactive data streams after all data in the connected B second anti-latency data stream is received by the client.

9. The method of claim 6, wherein each of the N interactive data streams contains the whole set of said data having K segments.

10. The method of claim 6, wherein each of the N interactive data streams contains the remaining portion of said data only.

11. The method of claim 6, wherein said coarse-jump frame period includes E data segments, and F_a≧

2E.

12. The method of claim 6, wherein a starts from 1.

13. The method of claim 6, wherein a starts from 4 and the repeating first, second, and third anti-latency data streams have the following configuration:

14. A method for transmitting data over a network to at least one client having a latency time to initiate transmission of said data to the client, including the steps of:

generating M anti-latency data streams containing at least a leading portion of data for receipt by the client, wherein said data is fragmented into K segments each requiring a time T to transmit over the network, and wherein the M anti-latency data streams contain the leading portion of said data, and further include two batches of data streams comprising a first set of anti-latency data streams and a second set of anti-latency data streams, such that

the first anti-latency data streams have A first anti-latency data streams from 1 to A, wherein an a^th anti-latency data stream has F_a segments, and F_a is an a^th Fibonacci number; and

the F_a segments are repeated continuously within the a^th first anti-latency data stream, and

the second anti-latency data streams have B second anti-latency data streams including a leading data stream containing at least one leading segment of the leading portion of said data being repeated continuously within the leading data stream; and

a plurality of finishing data streams, each of the finishing data streams containing the rest of the leading portion of said data; and

being repeated continuously within said finishing data stream, wherein each successive finishing data steam is staggered by a coarse-jump frame period such that the client can perform a coarse-jump interactive function when the client is connected to a second anti-latency data stream; and

generating N interactive data streams containing at least a remaining portion of said data for the client to merge into after receiving at least a portion of an anti-latency data stream;

wherein;

A, B, K, M and N are integers, and

T is a length of time.

15. The method of claim 14, further including the steps of:

connecting the client to at least the a^th and (a+1)^th first anti-latency data streams when the client raises a request for said data;

buffering the data in at least the a^th and (a+1)^th first anti-latency data streams in the client;

subsequently connecting the client to successive first anti-latency data streams; and

repeating the previous steps until all data in the A first anti-latency data streams is received by the client.

16. The method of claim 15, further including the steps of:

connecting the client to the leading data stream after all data in the first anti-latency data streams is received by the client;

subsequently connecting the client to any one of the finishing data streams; and

connecting the client to any one of the N interactive data streams after all data in the B second anti-latency data streams is received by the client.

17. The method of claim 14, wherein each of the N interactive data steams contains the whole set of said data having K segments.

18. The method of claim 14, wherein each of the N interactive data streams contains the remaining portion of said data only.

19. The method of claim 14, wherein said coarse-jump frame period includes E data segments, and F_a≧

2E.

20. The method of claim 14, wherein a starts from 1.

21. The method of claim 14, wherein a starts from 4 and the repeating first, second, and third data streams of the A first anti-latency data streams have the following configuration:

22. A method for transmitting data over a network to at least one client having a latency time to initiate transmission of said data to the client, including the steps of:

generating M anti-latency data streams containing at least a leading portion of data for receipt by the client, wherein said data is fragmented into K segments each requiring a time T to transmit over the network, and wherein the M anti-latency data streams contain the leading portion of said data, and further include two batches of data streams comprising a first set of anti-latency data streams and a second set of anti-latency data streams, such that

the first anti-latency data streams have A first anti-latency data streams, wherein, I. the A first anti-latency data streams contains 1 to C first data segments; and

II. the first data segments are distributed in the A first anti-latency data streams such that an c^th leading segment is repeated by an anti-latency time interval ≦

cT within the A first anti-latency data streams, and

the second anti-latency data streams have B second anti-latency data streams, wherein each of the B second anti-latency data streams contains substantially identical data repeated continuously within said second anti-latency data stream, and wherein each successive second anti-latency data stream is staggered by a coarse-jump frame period;

such that the client can perform a coarse-jump interactive function when the client is connected to a second anti-latency data stream; and

generating N interactive data streams containing at least a remaining portion of said data for the client to merge into after receiving at least a portion of an anti-latency data stream;

wherein;

A, B, C, K, M and N are integers, and

T is a length of time.

23. The method of claim 22, further including the steps of:

connecting the client to all of the A first anti-latency data streams when the client raises a request for said data; and

buffering data in the A first anti-latency data streams in the client until all data in the A first anti-latency data streams is received by the client.

24. The method of claim 23, further including the steps of:

connecting the client to any one of the B second anti-latency data streams after all data in the first anti-latency data streams is received by the client; and

connecting the client to anyone of the N interactive data streams after all data in the connected B second anti-latency data stream is received by the client.

25. The method of claim 22, wherein each of the N interactive data streams contains the whole set of said data having K segments.

26. The method of claim 22, wherein each of the N interactive data streams contains the remaining portion of said data only.

27. The method of claim 22, wherein said coarse-jump frame period includes E data segments, and

$A\ge$

∑

c = 1 c = E ⁢

( 1 c ) .

28. The method of claim 22, wherein six of the A first anti-latency data streams are arranged as follows:

wherein blank segments contain any data.

29. A method for transmitting data over a network to at least one client having a latency time to initiate transmission of said data to the client, including the steps of:

generating M anti-latency data streams containing at least a leading portion of data for receipt by the client, wherein said data is fragmented into K segments each requiring a time T to transmit over the network, and wherein the M anti-latency data streams contain the leading portion of said data, and further include two batches of data streams comprising a first set of anti-latency data streams and a second set of anti-latency data streams, such that

the first anti-latency data streams have A first anti-latency data steams, wherein the A first anti-latency data streams contain 1 to C first data segments, and the first data segments are distributed in the A first anti-latency data streams such that an c^th leading segment is repeated by an anti-latency time interval ≦

cT within the A first anti-latency data streams, and

the second anti-latency data streams have B second anti-latency data stream including a leading data stream containing at least one leading segment of the leading portion of said data being repeated continuously within the leading data stream, and a plurality of finishing data streams, each of the finishing data streams connecting the rest of the leading portion of said data, and being repeated continuously with said finishing data stream, and wherein each successive finishing data stream is staggered by a coarse-jump frame period such that the client can perform a coarse-jump interactive function when the client is connected to a second anti-latency data stream; and

generating N interactive data streams containing at least a remaining portion of said data for the client to merge into after receiving at least a portion of an anti-latency data stream;

wherein;

A, B, C, K, M and N are integers, and

T is a length of time.

30. The method of claim 29, further including the steps of:

connecting the client to all of the A first anti-latency data streams when the client raises a request for said data; and

buffering data in the A first is anti-latency data streams in the client until all data in the A first anti-latency data streams is received by the client.

31. The method of claim 30, further including the steps of:

connecting the client to the leading data stream of the B second anti-latency data streams after all data in the first anti-latency data streams is received by the client;

subsequently connecting the client to any one of the finishing data streams; and

connecting the client to any one of the N interactive data streams after all data in the second anti-latency data stream is received by the client.

32. The method of claim 31, wherein six of the A first anti-latency data steams are arranged as follows:

wherein blank segments contain any data.

33. The method of claim 29, wherein each of the N interactive data streams contains the whole set of said data having K segments.

34. The method of claim 29, wherein each of the N interactive data streams contains the remaining portion of said data only.

35. The method of claim 29, wherein said coarse-jump frame period includes E data segments, and

$A\ge$

∑

c = 1 c = E ⁢

( 1 c ) .

36. A method for transmitting data over a network to at least one client including the step of generating M anti-latency data streams from 1 to M, wherein an m^th anti-latency data stream has F_m segments, and F_m is an m^th Fibonacci number;

and said F_m segments are repeated continuously within the m^th anti-latency data stream, and wherein m starts from 4 and the repeating first, second, and third anti-latency data streams have the following configuration;

37. A method for transmitting data over a network to at least one client, said data being fragmented into K segments each requiring a time T to transmit over the network, including the steps of:

generating M anti-latency data streams containing 1 to K anti-latency data segments, wherein the anti-latency data segments are distributed in the M anti-latency data streams such that an k^th leading segment is repeated by an anti-latency time interval ≦

kT within the anti-latency data streams, and wherein six of the M anti-latency data streams containing the leading data segments are arranged as follows;

wherein blank segments contain any data.

38. A method for transmitting data over a network to at least one client having a latency time to initiate transmission of said data to the client, including the steps of:

generating M anti-latency data streams containing at least a leading portion of data for receipt by the client, wherein said data is fragmented into K segments each requiring a time T to transmit over the network;

generating N interactive data streams containing at least a remaining portion of said data for the client to merge into after receiving at least a portion of an anti-latency data stream;

raising a request for said data;

connecting the client to the M anti-latency data streams and receiving data in the M anti-latency data streams;

pre-fetching at least a portion of data in the M anti-latency data streams in the client as pre-fetched data; and

refreshing the pre-fetched data during a refresh time period, wherein the refresh time period is 01;

00–

06;

00,

and wherein;

K, M and N are integers, and

T is a length of time.

39. A method for transmitting data over a network to at least one client having a latency time to initiate transmission of said data to the client, including the steps of:

generating M anti-latency data streams containing at least a leading portion of data for receipt by the client, wherein said data is fragmented into K segments each requiring a time T to transmit over the network;

generating N interactive data streams containing at least a remaining portion of said data for the client to merge into after receiving at least a portion of an anti-latency data stream;

raising a request for said data;

connecting the client to the M anti-latency data streams and receiving data in the M anti-latency data streams;

pre-fetching at least a portion of data in the M anti-latency data streams in the client as pre-fetched data; and

refreshing the pre-fetched data during a refresh time period, wherein the refresh time period is 10;

00–

15;

00,

and wherein;

K, M and N are integers, and

T is a length of time.