Method for improving bandwidth efficiency

• US 6,965,730 B2
• Filed: 05/10/2001
• Issued: 11/15/2005
• Est. Priority Date: 05/12/2000
• Status: Expired due to Term

• Current Assignee: TiVo Solutions Inc. (Adeia Inc.)
• Original Assignee: TiVo Inc. (Adeia Inc.)
• Inventors: Zenchelsky, Dan, Chamberlin, David, Platt, David C., Vannier, Eric
• Primary Examiner(s): Chevalier, Robert
• Application Number:
  US10/275,927
• Publication Number:
  US 20040223722A1
• Time in Patent Office: 1,650 Days
• Field of Search: 386/125, 386/124, 386/126, 386/129, 386/105, 386/106, 386/109, 386/111, 386/112, 386/45, 386/40, 386/46, 386/68, 386/70, 386/69, 386/81, 386/82, 386/1, 386/6, 386/27, 386/33
• US Class Current: 386/293
• CPC Class Codes: H04N 5/76 Television signal recording
• CPC Class Codes: H04N 5/781 on disks or drums
• CPC Class Codes: H04N 9/8042 involving data reduction

Abstract

A method for dynamically managing a digital recording system'"'"'s bandwidth requirements, provides prioritized accesses to the recording system'"'"'s hard drive according to a pre-defined policy which gives the first priority to the data streams being written to the disk, the second priority to the data streams being read from the disk, and the third priority to other accesses to the disk. The recording system'"'"'s bandwidth efficiency may also be improved by optimizing allocation of the disk'"'"'s storage space which is partitioned into lower bandwidth portions and higher bandwidth portions, where lower bandwidth data streams are stored in lower bandwidth portions and higher bandwidth data streams are stored in higher bandwidth portions.

Claims

1. A method for dynamically managing bandwidth requirements for a digital recording system which stores data streams in a storage device, comprising:

detecting a situation prior to said digital recording system exceeding said storage device'"'"'s available bandwidth;

prioritizing accesses to said storage device according to a policy to avoid losing data from a data stream that is being written to or being read from said storage device; and

wherein said step of detecting a situation comprises the sub-steps of;

determining, by a media data management module, whether said digital recording system is close to failing to meet a time deadline for writing a data stream to said storage device or reading a data stream from said storage device; and

wherein if said digital recording system is close to failing to meet a time deadline for writing a data stream to said storage device or reading a data stream from said storage device, then reporting this fact to a policy module which implements said policy;

wherein said media data management module measures said time deadline for each buffer of data transferred to or from said storage device.

2. The method of claim 1, further comprising the sub-step of:

sending an urgent error alert to said policy module if a time deadline is missed.

3. A method for dynamically managing bandwidth requirements for a digital recording system which stores data streams in a storage device, comprising:

detecting a situation prior to said digital recording system exceeding said storage device'"'"'s available bandwidth;

prioritizing accesses to said storage device according to a policy to avoid losing data from a data stream that is being written to or being read from said storage device; and

wherein said step of detecting a situation comprises the sub-steps of;

determining, by a disk driver, whether said digital recording system is close to failing to meet deadline requirements on all on-going data streams'"'"' input-output requests; and

wherein if said digital recording system is close to failing to meet deadline requirements on all on-going data streams'"'"' input-output requests, then reporting this fact to said policy module which implements said policy.

4. The method of claim 3, wherein said disk driver measures its total available time for all on-going data streams'"'"' input-output requests over a specific time period;

and

wherein if said total available time exceeds a programmable threshold for more than said specific time period, then said driver determines that said digital recording system is coming close to failing to satisfy deadline requirements on all on-going data streams'"'"' input-output requests.

5. The method of claim 3, wherein said disk driver is a kernel'"'"'s disk driver.

6. A method for dynamically managing bandwidth requirements for a digital recording system which stores data streams in a storage device, comprising:

detecting a situation prior to said digital recording system exceeding said storage device'"'"'s available bandwidth;

prioritizing accesses to said storage device according to a policy to avoid losing data from a data stream that is being written to or being read from said storage device; and

wherein said step of prioritizing comprises a sub-step of;

deferring, pausing, or terminating one or more accesses to said storage device in a priority order of;

accesses other than data streams that are being written or read;

data streams that are being read from said storage device; and

data streams that are being written to said storage device.

7. The method of claim 6, further comprising the sub-step of:

when said digital recording system'"'"'s bandwidth requirements are mitigated, resuming said deferred, paused, or terminated accesses in a priority order of;

data streams that were being written to said storage device before they were deferred, paused, or terminated;

data streams that were being read from said storage device before they were deferred, paused, or terminated; and

accesses other than data streams that were being written or read before they were deferred, paused or terminated.

8. The method of claim 7, said data streams that were being written to said storage device before they were deferred, paused, or terminated are resumed in a nearest deadline first order.

9. The method of claim 7, wherein said data streams that were being read from said storage device before they were deferred, paused, or terminated are resumed in a nearest deadline first order.

10. A method for improving bandwidth efficiency of a digital recording system which stores data streams in a storage device, said method comprising the steps of:

partitioning said storage device'"'"'s space into a set of portions, some of which are used for storing lower bandwidth data streams and some of which are used for storing higher bandwidth data streams;

indicating whether a data stream is known to be of low bandwidth;

requesting low-bandwidth allocation when a data stream known to be of low bandwidth is being recorded; and

monitoring an actual average or peak bandwidth required by said data stream being recorded;

wherein each portion is associated with a set of data structures which are stored on said storage device and are loaded into memory when a media file system is initialized.

11. The method of claim 10, wherein the step of indicating whether a data stream is known to be of low bandwidth is performed by a parameter which is included in a space-allocation API of said media file system.

12. The method of claim 10, further comprising the step of:

flagging, by a flag, a given disk region as a lower bandwidth portion or a higher bandwidth portion.

13. The method of claim 12, wherein said flag is incorporated into a data structure associated with each specific portion of said storage device.

14. The method of claim 12, wherein said flag is a one-bit flag which shows that a specific area is in a lower bandwidth portion of said storage device.

15. The method of claim 10, further comprising the step of:

allocating space preferentially from any available low-bandwidth portion if said data stream is of low bandwidth.

16. The method of claim 15, wherein space is allocated outwards from the inner diameter of said storage device.

17. The method of claim 10, further comprising the step of:

allocating space preferentially from any available high-bandwidth portion if said data stream is not of low bandwidth.

18. The method of claim 17, wherein space is allocated inwards from the outer diameter of said storage device.

19. The method of claim 10, wherein said step of monitoring an actual or peak bandwidth is performed in terms of actual-arrival rate from an input medium or a network.

20. The method of claim 10, wherein said step of monitoring an actual or peak bandwidth is performed by tracking timestamps which are embedded in said data stream.

21. The method of claim 10, further comprising the steps of:

checking a recorded unknown bandwidth data stream in a higher bandwidth portion to determine whether its peak or average bandwidth is lower than a pre-defined value; and

migrating said data stream to a lower bandwidth portion if said recorded unknown bandwidth data stream'"'"'s peak or average bandwidth is lower than a pre-defined value.

22. The method of claim 21, wherein said step of migrating comprises the sub-steps of:

creating a new file in said low-bandwidth portion for said data stream;

playing contents of said data stream and recording said contents into said new file; and

deleting the original file for said data stream once said contents are recorded into said new file.

23. The method of claim 21, wherein said step of migrating is performed in the background with no time deadlines on read and write requests.

24. The method of claim 10, further comprising the step of:

caching average or peak bandwidth information for each recording in a database.

25. An apparatus for dynamically managing bandwidth requirements for a digital recording system which stores data streams in a storage device, comprising:

a module for detecting a situation prior to said digital recording system exceeding said storage device'"'"'s available bandwidth;

a module for prioritizing accesses to said storage device according to a policy to avoid losing data from a data stream that is being written to or being read from said storage device; and

wherein said module of detecting a situation comprises;

a media data management module that determines whether said digital recording system is close to failing to meet a time deadline for writing a data stream to said storage device or reading a data stream from said storage device; and

wherein if said digital recording system is close to failing to meet a time deadline for writing a data stream to said storage device or reading a data stream from said storage device then reporting this fact to a policy module which implements said policy;

wherein said media data management module measures said time deadline for each buffer of data transferred to or from said storage device.

26. The apparatus of claim 25, further comprising:

a module for sending an urgent error alert to said policy module if a time deadline is missed.

27. An apparatus for dynamically managing bandwidth requirements for a digital recording system which stores data streams in a storage device, comprising:

a module for detecting a situation prior to said digital recording system exceeding said storage device'"'"'s available bandwidth;

a module for prioritizing accesses to said storage device according to a policy to avoid losing data from a data stream that is being written to or being read from said storage device; and

wherein said detecting module comprises;

a disk driver that determines whether said digital recording system is close to failing to meet deadline requirements on all on-going data streams'"'"' input-output requests; and

wherein if said digital recording system is close to failing to meet deadline requirements on all on-going data streams'"'"' input-output requests then reporting this fact to said policy module which implements said policy.

28. The apparatus of claim 27, wherein said disk driver measures its total available time for all on-going data streams'"'"' input-output requests over a specific time period;

and

wherein if said total available time exceeds a programmable threshold for more than said specific time period, then said driver determines that said digital recording system is coming close to failing to satisfy deadline requirements on all on-going data streams'"'"' input-output requests.

29. The apparatus of claim 27, wherein said disk driver is a kernel'"'"'s disk driver.

30. A apparatus for dynamically managing bandwidth requirements for a digital recording system which stores data streams in a storage device, comprising:

a module for detecting a situation prior to said digital recording system exceeding said storage device'"'"'s available bandwidth;

a module for prioritizing accesses to said storage device according to a policy to avoid losing data from a data stream that is being written to or being read from said storage device; and

wherein said prioritizing module comprises;

a module for deferring, pausing, or terminating one or more accesses to said storage device in a priority order of;

accesses other than data streams that are being written or read;

data streams that are being read from said storage device; and

data streams that are being written to said storage device.

31. The apparatus of claim 30, further comprising:

a module for when said digital recording system'"'"'s bandwidth requirements are mitigated, resuming said deferred, paused, or terminated accesses in a priority order of;

data streams that were being written to said storage device before they were deferred, paused, or terminated;

data streams that were being read from said storage device before they were deferred, paused, or terminated; and

accesses other than data streams that were being written or read before they were deferred, paused or terminated.

32. The apparatus of claim 31, said data streams that were being written to said storage device before they were deferred, paused, or terminated are resumed in a nearest deadline first order.

33. The apparatus of claim 31, wherein said data streams that were being read from said storage device before they were deferred, paused, or terminated are resumed in a nearest deadline first order.

34. An apparatus for improving bandwidth efficiency of a digital recording system which stores data streams in a storage device, said apparatus comprising the steps of:

a module for partitioning said storage device'"'"'s space into a set of portions, some of which are used for storing lower bandwidth data streams and some of which are used for storing higher bandwidth data streams;

a module for indicating whether a data stream is known to be of low bandwidth;

a module for requesting low-bandwidth allocation when a data stream known to be of low bandwidth is being recorded; and

a module for monitoring an actual average or peak bandwidth required by said data stream being recorded;

wherein each portion is associated with a set of data structures which are stored on said storage device and are loaded into memory when a media file system is initialized.

35. The apparatus of claim 34, wherein the step of indicating whether a data stream is known to be of low bandwidth is performed by a parameter which is included in a space-allocation API of said media file system.

36. The apparatus of claim 34, further comprising:

a module for flagging, by a flag, a given disk region as a lower bandwidth portion or a higher bandwidth portion.

37. The apparatus of claim 36, wherein said flag is incorporated into a data structure associated with each specific portion of said storage device.

38. The apparatus of claim 36, wherein said flag is a one-bit flag which shows that a specific area is in a lower bandwidth portion of said storage device.

39. The apparatus of claim 34, further comprising:

a module for allocating space preferentially from any available low-bandwidth portion if said data stream is of low bandwidth.

40. The apparatus of claim 39, wherein space is allocated outwards from the inner diameter of said storage device.

41. The apparatus of claim 34, further comprising:

a module for allocating space preferentially from any available high-bandwidth portion if said data stream is not of low bandwidth.

42. The apparatus of claim 41, wherein space is allocated inwards from the outer diameter of said storage device.

43. The apparatus of claim 34, wherein said monitoring module is performed in terms of actual-arrival rate from an input medium or a network.

44. The apparatus of claim 34, wherein said monitoring module is performed by tracking timestamps which are embedded in said data stream.

45. The apparatus of claim 34, further comprising:

a module for checking a recorded unknown bandwidth data stream in a higher bandwidth portion to determine whether its peak or average bandwidth is lower than a pre-defined value; and

a module for migrating said data stream to a lower bandwidth portion if said recorded unknown bandwidth data stream'"'"'s peak or average bandwidth is lower than a pre-defined value.

46. The apparatus of claim 45, wherein said migrating module comprises:

a module for creating a new file in said low-bandwidth portion for said data stream;

a module for playing contents of said data stream and recording said contents into said new file; and

a module for deleting the original file for said data stream once said contents are recorded into said new file.

47. The apparatus of claim 45, wherein said migrating module is performed in the background with no time deadlines on read and write requests.

48. The apparatus of claim 34, further comprising:

a module for caching average or peak bandwidth information for each recording in a database.