Bandwidth reduction of on-demand streaming data using flexible merger hierarchies

• US 6,859,839 B1
• Filed: 08/07/2000
• Issued: 02/22/2005
• Est. Priority Date: 08/06/1999
• Status: Active Grant

• Current Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Original Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Inventors: Eager, Derek L., Zahorjan, John, Vernon, Mary K.
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Gerezgiher, Yemane M.
• Application Number:
  US09/633,217
• Time in Patent Office: 1,660 Days
• Field of Search: 709/230, 709/231, 709/232, 709/233, 725/87, 725/91, 725/93, 725/95, 725/96, 725/97, 725/101
• US Class Current: 709/231
• CPC Class Codes: H04N 21/234381 by altering the temporal resolution, e.g. decreasing the frame rate by frame skipping
• CPC Class Codes: H04N 21/2393 involving handling client requests scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04N 21/2402 Monitoring of the downstream path of the transmission network, e.g. bandwidth available traffic monitoring in data switching networks H04L43/00; monitoring data switching networks utilization H04L43/0876
• 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/4331 Caching operations, e.g. of an advertisement for later insertion during playback
• CPC Class Codes: H04N 21/44016 involving splicing one content stream with another content stream, e.g. for substituting a video clip
• CPC Class Codes: H04N 21/47202 for requesting content on demand, e.g. video on demand
• CPC Class Codes: H04N 21/6405 Multicasting data broadcast and multicast in packet switching networks H04L12/18
• CPC Class Codes: H04N 21/6543 for forcing some client operations, e.g. recording remote booting in general G06F9/4416
• CPC Class Codes: H04N 7/173 with two-way working, e.g. subscriber sending a programme selection signal

Abstract

A method of efficiently transmitting streamed data of a program to multiple clients requesting the program at different times ranks the requests in a multilevel hierarchy, which describes merging of data streams servicing the requests. The multilevel hierarchy changes dynamically as new requests arrive or existing data streams are merged to reduce the bandwidth or other costs required to serve the requests. The hierarchy may be established by simple rules or by a modeling of the actual cost of possible hierarchies.

Claims

1. A method of transmitting streaming data, comprising the steps of:

(a) starting an original transmission of a program;

(b) after step (a), scheduling a requested transmission of the program in response to a client request;

(c) selecting a target transmission that is farther along in the program than the requested transmission as a merge target for the requested transmission;

(d) receiving at the client a composite of the requested transmission and data of the target transmission; and

(e) after step (d), merging the requested transmission and target transmission to provide a merged transmission; and

(f) after step (e), merging the merged transmission with the original transmission.

2. The method of claim 1 wherein the merge target simultaneously has a third transmission that is still farther along in the program as its merge target.

3. The method of claim 1 wherein the beginning of each transmission is asynchronous in response to an asynchronous request by a client.

4. The method of claim 1 wherein the beginning of each transmission is aperiodic in response to aperiodic requests by clients.

5. The method of claim 1 wherein the merge target is chosen to reduce transmission costs that are a function of total bandwidth of the transmission of the streaming data to clients.

6. The method of claim 5 wherein the transmission costs equal total economic cost of the transmission of the streaming data to clients.

7. The method of claim 5 wherein the determination of transmission costs is done by modeling transmission costs for different possible combinations of mergers of the transmissions.

8. The method of claim 5 wherein the determination of transmission costs is done according to predetermined rules anticipating transmission costs.

9. The method of claim 1 wherein each transmission is terminated at the earliest time that it has merged with the merge target.

10. The method of claim 1 wherein step (c) of selecting a merge target selects a target transmission that results in the earliest achievable merger for that client, given that no later clients merge with that client.

11. The method of claim 1 wherein step (c) of selecting a merge target selects a target transmission that is the least ahead of the transmission.

12. The method of claim 1 wherein the merging of the transmission and the target transmission in step (e) includes the steps of:

(i) the client recording the data of the target transmission, beginning when the merge target is selected;

(ii) ceasing the transmission of the requested transmission when the requested transmission reaches a first point in the program that was recorded at step (i).

13. The method of claim 12 wherein the transmission is at the program playback rate and wherein the recording rate is at least equal to the playback rate.

14. The method of claim 12 wherein the transmission is at the program playback rate and wherein the recording rate is at less than the playback rate.

15. The method of claim 14 wherein the recording rate is between 5% and 100% of the playback rate.

21. The method of claim 1, wherein step (d) further comprises concurrently receiving the requested transmission and the target transmission at the client.

22. A method as recited in claim 1, wherein the composite of requested stream is transmitted as a single stream.

23. The method of claim 1, wherein the requested transmission is not time distorted.

24. The method of claim 1, wherein the target transmission is not time distorted.

16. A method of transmitting a streaming data on-demand comprising the steps of:

(a) receiving at different times to requests for transmission of the streaming data from clients i;

(b) beginning i transmissions of the streaming data to the i clients;

(c) grouping the i transmissions into merge hierarchies defining merger of the transmissions of the streaming data to reduce the total transmission cost;

(d) receiving at a time t_i+1 subsequent to the times t_i a request for transmission of the streaming data from client i+1; and

(e) changing the grouping of the merge hierarchies in response to the receipt of the request from client i+1.

17. The method of claim 16 wherein the beginnings of the i transmissions are asynchronous with respect to each other.

18. The method of claim 16 wherein the transmission costs equal total bandwidth of the transmission of the streaming data to clients.

19. The method of claim 16 wherein the transmission costs equal total economic cost of the transmission of the streaming data to clients.

25. The method of claim 16, wherein the transmission of the streaming data is not time distorted.

20. A method of transmitting streaming data, on-demand, comprising the steps of:

(a) scheduling a requested transmission stream in response to a request of a client;

(b) selecting an earlier transmission stream as a merge target for the requested transmission stream so that the client receives both the requested transmission stream and the earlier transmission stream and so that the requested transmission stream could merge at a merger time with the earlier transmission stream; and

(c) subsequent to step (b), and prior to the merge time, changing the merge time.

26. The method of claim 20, wherein the requested transmission stream is not time distorted.

27. The method of claim 20, wherein the earlier transmission stream is not time distorted.