Streaming while fetching broadband video objects using heterogeneous and dynamic optimized segmentation size

• US 7,324,555 B1
• Filed: 03/19/2004
• Issued: 01/29/2008
• Est. Priority Date: 03/20/2003
• Status: Active Grant

• Current Assignee: InfoValue Computing, Inc.
• Original Assignee: InfoValue Computing, Inc.
• Inventors: Chen, Monsong, Mukherjee, Bodhi, Duan, Dah-Weih
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): TRAN, PHUC H
• Application Number:
  US10/804,658
• Time in Patent Office: 1,411 Days
• Field of Search: 370/229, 370/235, 370/395.21, 370/395.41, 725/32, 725/145
• US Class Current: 370/468
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04N 21/2225 Local VOD servers
• CPC Class Codes: H04N 21/262 Content or additional data distribution scheduling, e.g. sending additional data at off-peak times, updating software modules, calculating the carousel transmission frequency, delaying a video stream transmission, generating play-lists scheduling strategies for dispatcher in multiprogramming arrangements G06F9/4881; arrangements for scheduling broadcast services or broadcast-related services H04H60/06; flow control in packet networks H04L47/10; establishing a time schedule or organising the servicing of application requests H04L67/62
• 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

An video data object distribution system for transfer of video data objects includes a network of digital data file servers. The network of digital data file servers communicate with a client system to transfer video data objects. A scheduling apparatus schedules the transfer of the video data objects. A client streaming device within the client begins transfer of a first segment such that the video data object is started streaming of prior to reception of a totality of the first segment. An ordered sequential transfer device orders and sequentially transfers segments of the video data object to the client system. The preemption device allows persistent video data object transfer of video data object without resending the video data objects. A hierarchical caching controller copies segments of any of the video data objects from a central distribution server to any of the network of data file servers.

Claims

1. A file distribution system for transfer of data objects comprising:

a network of digital data file servers in communication with at least one client system for the transfer of the data objects to the client system;

a scheduling apparatus for scheduling said transfer of the data objects from said digital data file servers to the client system, comprising;

a file segmenting device to variably and dynamically segment data objects within said digital data file servers dependent upon an available transfer bandwidth, a predicted request loading, and an actual request loading;

a client streaming device within said client to begin transfer of a first segment of said data object to said client system such that the client system begins processing of said data object prior to reception of a totality of said first segment;

an ordered sequential transfer device to order and sequentially transfer segments of the data object to the client system and to assign a bandwidth to said transfer to prevent simultaneous transfer of all segments of the data object so as to allow transfer of the data objects to multiple systems;

a preemption device to cease transfer of a first data object and allow transfer of a second data object that is more urgent than the first data object, whereby said preemption device allows persistent data object transfer of the first digital data object without resending said first digital data object; and

a hierarchical caching controller to copy segments of any of the data objects from a central distribution server to any of the network of data file servers, whereby the caching controller selects scheduling of transfers from the central distribution server to any of the network of data file servers or from on data file server within the network of data file servers.

2. The file distribution system of claim 1 wherein the transfer at which the network of data file servers has a greater transfer bandwidth than the bandwidth of the client system to accept and process the digital data objects.

3. The file distribution system of claim 1 wherein the preemption device executes the steps of:

assigning a priority to each of said data objects with in said data file servers;

upon request of a segment of a data object by said client, examining whether the transfer bandwidth is sufficient to transfer said requested data object;

if said bandwidth is not sufficient, determining if the priority of said requested data object supercedes that of any data object being transferred;

if said priority of said requested data object does not supercede that of any data object being transferred, scheduling transfer for said requested data object to a later time;

upon completion of the transfer of one of the data objects being transferred, transferring the requested data object;

if said priority of said request data object supercedes that of any data object being transferred, ceasing transfer of said data object being transferred having the priority that is superceded by the priority of the requested data object;

upon ceasing of said transfer of the data object, transferring the requested data object; and

upon completion of the transfer of the requested data object, restarting said data object that had ceased transfer.

4. The file distribution system of claim 1 wherein said scheduling apparatus schedules a request executing the steps of:

receiving a request for at least one portion of at least one data object;

segmenting by the file segmenting device said data object;

caching by said hierarchical caching controller said segments of said data objects within the digital data file servers;

determining within said digital data file servers, locations of said cached segments of said requested data object;

determining from those locations containing said cached segments those locations within the digital data file servers that are able to transfer said requested segments efficiently;

creating a schedule table describing a time at which said requested segments are to be dispatched; and

at said time, dispatching said segments to said client systems.

5. The file distribution system of claim 4 wherein said request for a segment is a pull request initiated by the client server to acquire said segment from the data file servers.

6. The file distribution system of claim 4 wherein said request for a segment is a push request initiated by a distributor to send said segment to said client server.

7. The file distribution system of claim 1 wherein the client streaming device controls the flow of packets within one segment being transferred to said client system by the steps of

receiving one of said packets;

determining if said packet is in correct order relative to previously received packets;

if said packet is not in the correct order, requesting a resend of the packet not received in order;

buffering said packet received but out of order;

receiving a next packet;

determining if said next packet is a missing packet not received in order;

if said next packet is said missing packet, storing said next packet and any packet received out of order in correct order; and

requesting sending of remaining packets of said segment.

8. The file distribution system of claim 7 wherein said segments of said data objects are transferred using user data gram protocol.

9. The file distribution system of claim 7 wherein said flow control is implemented as a flow control protocol comprising

a send one packet command requesting the data file server containing said segment to send a single packet of said segment;

a send packets continuously command requesting the data file server containing said segment to send packet continuously;

a send a set of packet command requesting the data file server containing said segment to send a certain number of packets of said segment;

a stop sending command requesting said data file server to cease sending said packets;

a resend packets command requesting said data file server to stop send current packets and send specified packets;

a file size command requesting said data file server to provide said client system with a file size of said segment; and

a setup communication command to establish communication parameters including packet size for a fixed packet size and algorithm parameters for a variable packet size.

10. The file distribution system of claim 1 wherein said data objects are digital video data objects and said segments are ordered to permit isochronous transfer of said digital video objects to said client systems.

11. A video object distribution system for transfer of video data objects comprising:

a network of digital data file servers in communication with at least one client system for the transfer of the video data objects to the client system;

a scheduling apparatus for scheduling said transfer of the video data objects from said digital data file servers to the client system, comprising;

a file segmenting device to variably and dynamically segment video data objects within said digital data file servers dependent upon an available transfer bandwidth, a predicted request loading, and an actual request loading;

a client streaming device within said client to begin transfer of a first segment of said video data object to said client system such that the client system begins streaming of said video data object prior to reception of a totality of said first segment;

an ordered sequential transfer device to order and sequentially transfer segments of the video data object to the client system and to assign a bandwidth to said transfer to prevent simultaneous transfer of all segments of the video data object so as to allow transfer of the video data objects to multiple systems;

a preemption device to cease transfer of a first video data object and allow transfer of a second video data object that is more urgent than the first video data object, whereby said preemption device allows persistent video data object transfer of the first digital video data object without resending said first digital video data object; and

a hierarchical caching controller to copy segments of any of the video data objects from a central distribution server to any of the network of data file servers, whereby the caching controller selects scheduling of transfers from the central distribution server to any of the network of data file servers or from on data file server within the network of data file servers.

12. The video object distribution system of claim 11 wherein the transfer at which the network of data file servers has a greater transfer bandwidth than the bandwidth of the client system to accept and stream the digital video data objects.

13. The video object distribution system of claim 11 wherein the preemption device executes the steps of:

assigning a priority to each of said video data objects with in said data file servers;

upon request of a segment of a video data object by said client, examining whether the transfer bandwidth is sufficient to transfer said requested video data object;

if said bandwidth is not sufficient, determining if the priority of said requested video data object supercedes that of any video data object being transferred;

if said priority of said requested video data object does not supercede that of any video data object being transferred, scheduling transfer for said requested video data object to a later time;

upon completion of the transfer of one of the video data objects being transferred, transferring the requested video data object;

if said priority of said request video data object supercedes that of any video data object being transferred, ceasing transfer of said video data object being transferred having the priority that is superceded by the priority of the requested video data object;

upon ceasing of said transfer of the video data object, transferring the requested video data object; and

upon completion of the transfer of the requested video data object, restarting said video data object that had ceased transfer.

14. The video object distribution system of claim 11 wherein said scheduling apparatus schedules a request executing the steps of:

receiving a request for at least one portion of at least one video data object;

segmenting by the file segmenting device said video data object;

caching by said hierarchical caching controller said segments of said video data objects within the digital data file servers;

determining within said digital data file servers, locations of said cached segments of said requested video data object;

determining from those locations containing said cached segments those locations within the digital data file servers that are able to transfer said requested segments efficiently;

creating a schedule table describing a time at which said requested segments are to be dispatched; and

at said time, dispatching said segments to said client systems.

15. The video object distribution system of claim 14 wherein said request for a segment is a pull request initiated by the client server to acquire said segment from the data file servers.

16. The video object distribution system of claim 14 wherein said request for a segment is a push request initiated by a distributor to send said segment to said client server.

17. The video object distribution system of claim 11 wherein the client streaming device controls the flow of packets within one segment being transferred to said client system by the steps of:

receiving one of said packets;

determining if said packet is in correct order relative to previously received packets;

if said packet is not in the correct order, requesting a resend of the packet not received in order;

buffering said packet received but out of order;

receiving a next packet;

determining if said next packet is a missing packet not received in order;

if said next packet is said missing packet, storing said next packet and any packet received out of order in correct order; and

requesting sending of remaining packets of said segment.

18. The video object distribution system of claim 17 wherein said segments of said video data objects are transferred using user data gram protocol.

19. The video object distribution system of claim 17 wherein said flow control is implemented as a flow control protocol comprising

a send one packet command requesting the data file server containing said segment to send a single packet of said segment;

a send packets continuously command requesting the data file server containing said segment to send packet continuously;

a send a set of packet command requesting the data file server containing said segment to send a certain number of packets of said segment;

a stop sending command requesting said data file server to cease sending said packets;

a resend packets command requesting said data file server to stop send current packets and send specified packets;

a file size command requesting said data file server to provide said client system with a file size of said segment; and

a setup communication command to establish communication parameters including packet size for a fixed packet size and algorithm parameters for a variable packet size.

20. The video object distribution system of claim 11 wherein said video data objects segments are ordered to permit isochronous transfer of said digital video objects to said client systems.