Method for stream merging

• US 20020023166A1
• Filed: 04/10/2001
• Published: 02/21/2002
• Est. Priority Date: 04/11/2000
• Status: Abandoned Application

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Ladner, Richard, Bar-Noy, Amotz
• Application Number:
  US09/829,566
• Publication Number:
  US 20020023166A1
• Time in Patent Office: Days
• US Class Current: 709/231
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/611 for multicast or broadcast systems for broadcast or conference H04L12/18; arrangements for broadcast or distribution combined with broadcast H04H20/00; arrangements for broadcast applications with a direct linkage to broadcast information or to broadcast space-time H04H60/00; selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS], H04W4/06
• CPC Class Codes: H04L 65/764 at the destination reformatting of additional data in video clients H04N21/4355
• 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/44004 involving video buffer management, e.g. video decoder buffer or video display buffer
• 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 7/17336 Handling of requests in head-ends

Abstract

The present invention is directed to a system and method for stream merging which improves upon the prior art by utilizing optimized merging patterns.

Claims

1. A method of streaming media to a client comprising:

receiving a request from a client for a media stream;

computing a receiving procedure for the client;

transmitting the receiving procedure to the client;

initiating a first multicast stream such that the client can utilize the receiving procedure to receive a first portion of the media stream from the first multicast stream and a second portion of the media stream from a second multicast stream.

2. The invention of claim 1 wherein the client can further utilize the receiving procedure to receive a third portion of the media stream from a third multicast stream.

3. The invention of claim 1 wherein the receiving procedure is computed after a step of computing a merge tree incorporating the request from the client.

4. The invention of claim 3 wherein the merge tree is a Fibonacci merge tree.

5. A method of streaming media to a plurality of clients comprising:

receiving reservation requests for a media stream from a plurality of clients;

constructing a merge tree based on the reservation requests;

scheduling a plurality of multicast transmissions of the media stream based on the merge tree.

6. The invention of claim 5 wherein the merge tree is constructed to minimize the cost of the merge tree.

7. The invention of claim 6 wherein the merge tree is a Fibonacci merge tree.

8. The invention of claim 5 wherein the merge tree is constructed to minimize the cost of a forest of merge trees further comprising the merge tree.

9. A method of streaming media to a plurality of clients comprising:

constructing a merge tree based on anticipated requests for a media stream;

scheduling a plurality of multicast transmissions of the media stream based on the merge tree.

10. The invention of claim 9 wherein the anticipated requests for the media stream are scheduled to arrive at every time unit.

11. The invention of claim 10 wherein the merge tree is a Fibonacci merge tree.

12. The invention of claim 9 wherein the merge tree is a static merge tree with a fixed number of nodes.

14. The invention of claim 13 wherein the second merge tree is constructed to minimize an incremental merge cost.

15. The invention of claim 13 wherein the second merge tree is constructed such that the request is represented as a node of a parent node in the first merge tree closest to the node.

16. The invention of claim 13 wherein the second merge tree is an infinite merge tree.

17. The invention of claim 16 wherein the infinite merge tree is an infinite Fibonacci merge tree.

13. A method of streaming media to a client comprising:

receiving a request from a client for a media stream;

taking a first merge tree further comprising a right frontier and constructing a second merge tree which incorporates the request into the right frontier of the first merge tree; and

scheduling a plurality of multicast transmissions of the media stream, including a multicast transmission to the client, based on the second merge tree.

18. A machine-readable medium comprising executable program instructions for performing a method on a computer comprising the steps of:

transmitting a request for a media stream to a server;

obtaining a receiving procedure from the server;

in accordance with instructions in the receiving procedure, receiving and buffering a first portion of the media stream from a first multicast channel while receiving and buffering a second portion of the media stream from a second multicast channel.