Video distribution system using disk load balancing by file copying

• US 6,925,499 B1
• Filed: 12/19/2001
• Issued: 08/02/2005
• Est. Priority Date: 12/19/2001
• Status: Active Grant

• Current Assignee: InfoValue Computing, Inc.
• Original Assignee: InfoValue Computing, Inc.
• Inventors: Mukherjee, Bodhi, Duan, Dah-Weih, Pappu, Aparna, Chen, Monsong
• Primary Examiner(s): Burgess, Glenton B.
• Assistant Examiner(s): BARQADLE, YASIN M
• Application Number:
  US10/025,242
• Time in Patent Office: 1,322 Days
• Field of Search: 709212-219, 709224-226, 709231-232
• US Class Current: 709/226
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04N 21/2225 Local VOD servers
• CPC Class Codes: H04N 21/23103 using load balancing strategies, e.g. by placing or distributing content on different disks, different memories or different servers storage management G06F3/0604; allocation of resources considering the load in multiprogramming arrangements G06F9/505; techniques for rebalancing the load in a distributed system G06F9/5083; access to distributed or replicated servers, e.g. load balancing, in data networks H04L67/1001
• CPC Class Codes: H04N 21/2405 Monitoring of the internal components or processes of the server, e.g. server load allocation of resources in multiprogramming arrangements G06F9/50; performance measurement of computer activity G06F11/34
• 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 apparatus for dynamically balancing the loading of data storage facilities is described. A listing is acquired of locations and loading of all segments of a requested data object including all copies of the segments of the requested data object. Those storage devices containing copies of each segment of the data object having a least loading is selected. If the loading of the storage devices is greater than the maximum loading for the storage devices, the segment is designated to be copied. The presence of all segments of the requested data object is determined. If there are missing segments of the requested data object, each of those missing segments is assigned a file identification and file location, such that those missing segments are assigned to data storage devices having the least loading. The missing segments are retrieved from a back-up storage device.

Claims

1. A method for balancing a loading of storage devices attached to multiple computing systems comprising the steps of:

acquiring a listing of locations of all segments of a requested data object including all copies of said segments of the requested data object;

evaluating the loading of the storage devices attached to the multiple computing systems containing all copies of all segments of a requested data object;

selecting storage devices containing copies of each segment of the data object having a least loading, which is less than a maximum loading for said storage devices;

if the loading of the storage devices is greater than the maximum loading for said storage devices, copying any segment resident on said storage device having loading greater than said maximum loading to an alternate storage device;

selecting said alternate storage device; and

transferring those segments of said requested data object to a requesting computer system.

2. The method of claim 1 further comprising the steps of:

determining the presence of all segments of the requested data object;

if there are missing segments of the requested data object, assigning each of those missing segments a file identification and file location, such that those missing segments are assigned to data storage devices having the least loading; and

retrieving those missing segments from a back-up storage device.

3. The method of claim 1 wherein selecting the storage devices containing copies of the segments of the requested data object and having the least loading comprises the steps of:

a) setting a current segment indicator to indicate which of the segments of the data object is to be transferred next;

b) setting a current storage device indicator to specify a primary location of the segment to be transferred next;

c) if the transfer of said segment causes the loading of the storage device containing said segment to be exceeded, incrementing the current storage device indicator to a next location of the segment to be transferred; and

d) repeatedly executing step c) until said loading is not exceeded.

4. The method of claim 1 wherein transferring of the segments of the data object comprises the actions of reading said segments from the data storage device, writing said segments to the data storage device, and copying said segments from a said data storage device to an alternate data storage device, whereby said loading of the data storage device is allocated between the reading, writing, and copying of the segments to prevent interference with said reading of the segments.

5. The method of claim 1 wherein the requested data object is a video data file to be streamed isochronously to the requesting computer system.

6. A data object service system in communication with a plurality of computing systems to provide at least one data object of plurality of data object to at least one of the plurality of computing system, comprising:

a plurality of data object storage devices in communication with each other and with any of the plurality of computing systems; and

a load balancing apparatus in communication with the plurality of data object storage devices to balance a loading of said data object storage devices during transfer of said data objects,

whereby said load balancing apparatus comprises;

a load evaluator to assess the loading of the data object storage devices containing segments of said data objects,

a storage device selector to create a selection list to indicate selection of those data object storage devices containing copies of each segment of the requested data object having the least loading, and

a copying initiator to initiate a copying of a segment of the data object to an alternate storage device having low loading if all storage devices containing said segment have a loading greater than a maximum loading.

7. The system of claim 6 wherein the load balancing apparatus generates a listing of all copies of all segments of the requested data objects.

8. The system of claim 6 wherein a data storage device having a copied segment of the requested data object is selected to transfer said data object to a requesting computing system.

9. The system of claim 6 wherein the load balancing apparatus comprises:

a presence determining device to determine the presence of all segments of the requested data object; and

a segment retrieving device which, if there are missing segments of the requested data object, said segment retrieving device assigns each of those missing segments a file identification and file location, such that those missing segments are assigned to data storage devices having the least loading, and then said segment retrieving device retrieves those missing segments from a back-up storage device.

10. The system of claim 6 wherein the load balancing apparatus further comprises:

a segment indicator that is set to indicate which of the segments of the data object to be transferred next; and

a current storage device indicator to specify initially a primary location of the segment identified by the segment indicatory;

wherein the load balancing apparatus executes the steps of;

a) determining if the loading of the data storage device indicated by the current storage device indicator exceeds the maximum loading with transfer of the segment indicated by the segment indicator,

b) if said loading exceeds the maximum loading, setting the current storage device indicator to a next location of the segment indicated by the segment indicator, and

c) repeatedly executing steps a) and b) until said loading is not exceeded.

11. The system of claim 6 wherein transferring of the segments of the data object comprises the actions of reading said segments from the data storage device, writing said segments to the data storage device, and copying said segments from a said data storage device to an alternate data storage device, whereby said loading of the data storage device is allocated between the reading, writing, and copying of the segments to prevent interference with said reading of the segments.

12. The system of claim 6 wherein the requested data object is a video data file to be streamed isochronously to the requesting computer system.

13. An apparatus for balancing a loading of storage devices attached to multiple computing systems comprising:

means for acquiring a listing of locations of all segments of a requested data object including all copies of said segments of the requested data object;

means for evaluating the loading of the storage devices attached to the multiple computing systems containing all copies of all segments of a requested data object;

means for selecting storage devices containing copies of each segment of the data object having a least loading, which is less than a maximum loading for said storage devices;

means for copying any segment resident on said storage device having loading greater than said maximum loading to an alternate storage device, if the loading of the storage devices is greater than the maximum loading for said storage devices;

means for selecting said alternate storage device; and

means for transferring those segments of said requested data object to a requesting computer system.

14. The apparatus of claim 13 further comprising:

means for determining the presence of all segments of the requested data object;

means for assigning each of those missing segments a file identification and file location, such that those missing segments are assigned to data storage devices having the least loading, if there are missing segments of the requested data object; and

means for retrieving those missing segments from a back-up storage device.

15. The apparatus of claim 13 wherein the means for selecting the storage devices containing copies of the segments of the requested data object and having the least loading comprises:

a) means for setting a current segment indicator to indicate which of the segments of the data object is to be transferred next;

b) means for setting a current storage device indicator to specify a primary location of the segment to be transferred next; and

c) means for repeatedly incrementing the current storage device indicator to a next location of the segment to be transferred, if the transfer of said segment causes the loading of the storage device containing said segment to be exceeded until said loading is not exceeded.

16. The apparatus of claim 13 wherein transferring of the segments of the data object comprises

means for reading said segments from the data storage device;

means for writing said segments to the data storage device; and

means for copying said segments from a said data storage device to an alternate data storage device;

wherein said loading of the data storage device is allocated between the reading, writing, and copying of the segments to prevent interference with said reading of the segments.

17. The apparatus of claim 13 wherein the requested data object is a video data file to be streamed isochronously to the requesting computer system.

18. A medium for retaining a computer program which, when executed on a computing system, balances a loading of storage devices attached to multiple computing systems, said program executing the steps of:

acquiring a listing of locations of all segments of a requested data object including all copies of said segments of the requested data object;

evaluating the loading of the storage devices attached to the multiple computing systems containing all copies of all segments of a requested data object;

selecting storage devices containing copies of each segment of the data object having a least loading, which is less than a maximum loading for said storage devices;

if the loading of the storage devices is greater than the maximum loading for said storage devices, copying any segment resident on said storage device having loading greater than said maximum loading to an alternate storage device;

selecting said alternate storage device; and

transferring those segments of said requested data object to a requesting computer system.

19. The medium of claim 18 further comprising the steps of:

determining the presence of all segments of the requested data object;

if there are missing segments of the requested data object, assigning each of those missing segments a file identification and file location, such that those missing segments are assigned to data storage devices having the least loading; and

retrieving those missing segments from a back-up storage device.

20. The medium of claim 18 wherein selecting the storage devices containing copies of the segments of the requested data object and having the least loading comprises the steps of:

setting a current segment indicator to indicate which of the segments of the data object is to be transferred next;

setting a current storage device indicator to specify a primary location of the segment to be transferred next;

if the transfer of said segment causes the loading of the storage device containing said segment to be exceeded, incrementing the current storage device indicator to a next location of the segment to be transferred; and

repeatedly executing step c) until said loading is not exceeded.

21. The medium of claim 18 wherein transferring the segments of the data object comprises the actions of reading said segments from the data storage device, writing said segments to the data storage device, and copying said segments from a said data storage device to an alternate data storage device, said loading of the data storage device being allocated between the reading, writing, and copying of the segments to prevent interference with said reading of the segments.

22. The medium of claim 18 wherein the requested data object is a video data file to be streamed isochronously to the requesting computer system.

23. A method for balancing a loading of storage devices containing video data objects attached to multiple computing systems comprising the steps of:

acquiring a listing of locations of all segments of a requested video data object including all copies of said segments of the requested video data object;

evaluating the loading of the storage devices attached to the multiple computing systems containing all copies of all segments of a requested video data object;

selecting storage devices containing copies of each segment of the video data object having a least loading, which is less than a maximum loading for said storage devices;

if the loading of the storage devices is greater than the maximum loading for said storage devices, copying any segment resident on said storage device having loading greater than said maximum loading to an alternate storage device;

selecting said alternate storage device; and

transferring those segments of said requested video data object to a requesting computer system.

24. The method of claim 23 further comprising the steps of:

determining the presence of all segments of the requested video data object;

if there are missing segments of the requested video data object, assigning each of those missing segments a file identification and file location, such that those missing segments are assigned to data storage devices having the least loading; and

retrieving those missing segments from a back-up storage device.

25. The method of claim 23 wherein selecting the storage devices containing copies of the segments of the requested video data object and having the least loading comprises the steps of:

setting a current segment indicator to indicate which of the segments of the video data object is to be transferred next;

setting a current storage device indicator to specify a primary location of the segment to be transferred next;

if the transfer of said segment causes the loading of the storage device containing said segment to be exceeded, incrementing the current storage device indicator to a next location of the segment to be transferred; and

repeatedly executing step c) until said loading is not exceeded.

26. The method of claim 23 wherein transferring of the segments of the video data object comprises the actions of reading said segments from the data storage device, writing said segments to the data storage device, and copying said segments from a said data storage device to an alternate data storage device, said loading of the data storage device being allocated between the reading, writing, and copying of the segments to prevent interference with said reading of the segments.

27. The method of claim 23 wherein the requested video data object is streamed isochronously to the requesting computer system.

28. A video data object service system in communication with a plurality of computing systems to provide at least one video data object of plurality of video data object to at least one of the plurality of computing system, comprising:

a plurality of video data object storage devices in communication with each other and with any of the plurality of computing systems; and

a load balancing apparatus in communication with the plurality of video data object storage devices to balance a loading of said video data object storage devices during transfer of said video data objects,

said load balancing apparatus comprising;

a load evaluator to assess the loading of the video data object storage devices containing segments of said video data objects,

a storage device selector to create a selection list to indicate selection of those video data object storage devices containing copies of each segment of the requested video data object having the least loading, and

a copying initiator to initiate a copying of a segment of the video data object to an alternate storage device having low loading if all storage devices containing said segment have a loading greater than a maximum loading.

29. The system of claim 28 wherein the load balancing apparatus generates a listing of all copies of all segments of the requested video data objects.

30. The system of claim 28 wherein a data storage device having a copied segment of the requested video data object is selected to transfer said video data object to a requesting computing system.

31. The system of claim 28 wherein the load balancing apparatus comprises:

a presence determining device to determine the presence of all segments of the requested video data object; and

a segment retrieving device which, if there are missing segments of the requested video data object, said segment retrieving device assigns each of those missing segments a file identification and file location, such that those missing segments are assigned to data storage devices having the least loading, and then said segment retrieving device retrieves those missing segments from a back-up storage device.

32. The system of claim 28 wherein the load balancing apparatus further comprises:

a segment indicator that is set to indicate which of the segments of the video data object to be transferred next; and

a current storage device indicator to specify initially a primary location of the segment identified by the segment indicatory;

said load balancing apparatus executing the steps of;

determining if the loading of the data storage device indicated by the current storage device indicator exceeds the maximum loading with transfer of the segment indicated by the segment indicator,

if said loading exceeds the maximum loading, setting the current storage device indicator to a next location of the segment indicated by the segment indicator, and

repeatedly executing steps a) and b) until said loading is not exceeded.

33. The system of claim 28 wherein transfer of the segments of the video data object comprises the actions of reading said segments from the data storage device, writing said segments to the data storage device, and copying said segments from a said data storage device to an alternate data storage device, said loading of the data storage device being allocated between the reading, writing, and copying of the segments to prevent interference with said reading of the segments.

34. The system of claim 28 wherein the requested video data object is streamed isochronously to the requesting computer system.