Method and apparatus for managing a data carousel

• US 20040208204A1
• Filed: 04/21/2003
• Published: 10/21/2004
• Est. Priority Date: 04/21/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Crinon, Regis J.
• Granted Patent: US 7,450,600 B2
• Time in Patent Office: Days
• US Class Current: 370/537
• CPC Class Codes: H04N 21/643 Communication protocols network streaming protocols, e.g. real-time transport protocol [RTP] or real-time control protocol [RTCP], H04L65/65

Abstract

A data carousel contains multiple data files. A procedure determines a worst case latency between successive transmissions of a data file in the data carousel. The worst case latency is compared with a threshold latency value. The composition of the data carousel is modified if the worst case latency exceeds the threshold latency value.

Claims

1. A method comprising:

determining a worst case latency between successive transmissions of a data file in a data carousel;

comparing the worst case latency with a threshold latency value; and

modifying composition of the data carousel if the worst case latency exceeds the threshold latency value.

2. A method as recited in claim 1 wherein modifying composition of the data carousel includes deleting all instances of the data file from the data carousel.

3. A method as recited in claim 1 wherein modifying composition of the data carousel includes:

determining a specific data file to delete from the data carousel; and

deleting the specific data file from the data carousel.

4. A method as recited in claim 1 wherein modifying composition of the data carousel includes adding another instance of an existing data file to the data carousel.

5. A method as recited in claim 1 wherein modifying composition of the data carousel includes adding multiple instances of a new data file to the data carousel.

6. A method as recited in claim 1 wherein modifying composition of the data carousel includes:

determining a specific data file to insert into the data carousel; and

inserting the specific data file into the data carousel.

7. A method as recited in claim 1 wherein modifying composition of the data carousel includes:

deleting a first data file from the data carousel; and

inserting a second data file into the data carousel.

8. A method as recited in claim 1 wherein modifying composition of the data carousel includes changing a frequency of an existing data file in the data carousel.

9. A method as recited in claim 1 wherein the worst case latency is determined by:

determining a number of other data files that will be transmitted between successive transmissions of the data file; and

determining the time needed to transmit each of the other data files.

10. A method as recited in claim 1 wherein the method is performed in response to a plurality of requests to add a new data file to the data carousel.

11. A method as recited in claim 1 wherein modifying composition of the data carousel includes deleting lowest priority data files in the data carousel.

12. A method as recited in claim 1 wherein modifying composition of the data carousel includes deleting data files that have been contained in the data carousel for a longest period of time.

13. A method as recited in claim 1 wherein modifying composition of the data carousel includes deleting data files in the data carousel having a largest size.

14. A method as recited in claim 1 wherein the threshold latency value is calculated by summing:

a time for a user request to reach the head end;

a time for the head end to insert a requested file into the data carousel; and

a time for a receiver to acquire the requested file.

15. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 1.

16. A method comprising:

receiving a request to add a new data file to a data carousel;

identifying a plurality of existing data files in the data carousel;

for each of the plurality of existing data files, identifying a worst case latency between successive transmissions of the existing data file in the data carousel;

determining a data file having the largest worst case latency; and

deleting all instances of the data file having the largest worst case latency from the data carousel.

17. A method as recited in claim 16 further comprising adding the new data file to the data carousel.

18. A method as recited in claim 16 further comprising adding multiple 1 instances of the new data file to the data carousel.

19. A method comprising:

receiving a request to add a new data file to a data carousel;

identifying a plurality of existing data files in the data carousel;

for each of the plurality of existing data files, identifying a smallest latency between successive transmissions of the existing data file in the data carousel; and

deleting at least one instance of the data file having the smallest latency from the data carousel.

20. A method as recited in claim 19 wherein deleting at least one instance of the data file having the smallest case latency includes:

deleting an instance of the data file having the smallest latency; and

adjusting the positions of the remaining data files having the smallest case latency.

21. A method as recited in claim 19 further comprising adding the new data file to the data carousel.

22. A method as recited in claim 19 further comprising adding multiple instances of the new data file to the data carousel.

23. A method comprising:

determining a number of data files accommodated by a data carousel;

identifying a maximum latency value permitted between successive transmissions of a particular data file in the data carousel;

identifying a request frequency associated with various data files; and

inserting data files into the data carousel based on the identified request frequency and the maximum latency value permitted between successive transmissions of a particular data file in the data carousel.

24. A method as recited in claim 23 further comprising positioning the inserted data files such that a worst case latency between successive transmissions of a particular data file is less than the maximum latency value.

25. A method as recited in claim 23 wherein inserting data files into the data carousel includes inserting multiple instances of certain data files into the data carousel.

26. A method as recited in claim 23 further comprising:

monitoring the worst case latency between successive transmissions of a data file in a data carousel; and

modifying composition of the data carousel if the worst case latency exceeds a threshold value.

27. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 23.

28. A method comprising:

determining a number of data files that can be stored in a data carousel;

determining a number of bits associated with each data file in the data carousel;

determining a data transmission rate associated with the data carousel;

determining a maximum allowed latency associated with the data carousel;

determining a ratio of frequencies of pairs of data files in the data carousel; and

calculating a worst case latency between successive transmissions of a particular data file.

29. A method as recited in claim 28 further comprising deleting all instances of a specific data file from the data carousel if the worst case latency associated with the specific data file exceeds the maximum allowed latency associated with the data carousel.

30. A method as recited in claim 28 wherein calculating a worst case latency between successive transmissions of a particular data file utilizes the number of bits associated with each data file, the data transmission rate, and the ratio of frequencies of pairs of data files.

31. A method as recited in claim 28 further comprising:

recalculating a worst case latency between successive transmissions of the particular data file if a new data file is added to the data carousel; and

adding the new data file to the data carousel if addition of the new data file does not cause the recalculated worst case latency to exceed the maximum allowed latency associated with the data carousel.

32. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 28.

33. A method comprising:

determining a worst case latency between successive transmissions of a data file in a data carousel;

comparing the worst case latency with a threshold latency value; and

requesting an increase in a data delivery rate associated with the data carousel if the worst case latency exceeds the threshold latency value.

34. An apparatus comprising:

means for storing a plurality of data files in a data carousel;

means for generating a plurality of new data files to be stored in the data carousel; and

means for controlling the data carousel, the means for controlling the data carousel identifying one of the plurality of data files to be deleted from the data carousel, the means for controlling the data carousel further identifying one of the plurality of new data files to store in the data carousel.

35. An apparatus as recited in claim 34 wherein the means for controlling the data carousel identifies one of the plurality of data files to be deleted from the data carousel in response to a request to add a data file to the data carousel.

36. An apparatus as recited in claim 34 wherein the means for controlling the data carousel identifies one of the plurality of new data files to store in the data carousel in response to a request to add data to the data carousel.

37. An apparatus as recited in claim 34 wherein the means for controlling the data carousel modifies arrangement of the plurality of data files in the data carousel.

38. An apparatus as recited in claim 34 wherein the means for controlling the data carousel modifies arrangement of the plurality of data files such that a worst case latency between successive transmissions of any data file is less than a threshold latency value.

39. An apparatus comprising:

a carousel generator configured to generate data files to be stored a data carousel; and

a carousel controller coupled to the carousel generator and configured to manage the insertion of data files into the data carousel and to manage the deletion of data files from the data carousel, the carousel controller further configured to determine a maximum latency between successive transmissions of multiple instances of a data file in the data carousel, wherein the carousel controller prevents insertion in a transport stream of data files having a maximum latency between successive transmissions that exceed a threshold.

40. An apparatus as recited in claim 39 wherein the threshold is associated with a particular quality of service level.

41. An apparatus as recited in claim 39 wherein the carousel controller prevents insertion in a transport stream of data files having a maximum latency between successive transmissions that exceed a threshold.

42. An apparatus as recited in claim 39 wherein the carousel controller is further configured to receive a request for a particular data file, and wherein the carousel controller deletes at least one data file from the data carousel and inserts the requested data file into the data carousel.

43. An apparatus as recited in claim 39 wherein the carousel controller is further configured to report calculated worst case latency associated with each data module in the data carousel and wherein the carousel controller is configured to identify each of these latencies as either complying with or exceeding a reference latency threshold.

44. One or more computer-readable media having stored thereon a computer program that, when executed by one or more processors, causes the one or more processors to:

determine a maximum latency value associated with a data carousel;

determine a worst case latency between successive transmissions of an existing data file in a data carousel;

comparing the worst case latency to the maximum latency value; and

delete the existing data file if the worst case latency exceeds the maximum latency value.

45. One or more computer-readable media as recited in claim 44 wherein the computer program further causes the one or more processors to maintain the existing data file in the data carousel if the worst case latency does not exceed the maximum latency value.

46. One or more computer-readable media as recited in claim 44 wherein all instances of the existing data file are deleted from the data carousel if the worst case latency exceeds the maximum latency value.

47. One or more computer-readable media as recited in claim 44 wherein the maximum latency value is associated with a particular quality of service.

48. One or more computer-readable media as recited in claim 44 wherein the computer program further causes the one or more processors to insert a new data file into the data carousel in response to a request for the new data file.