Method and apparatus for managing a data carousel

• US 7,450,600 B2
• Filed: 04/21/2003
• Issued: 11/11/2008
• Est. Priority Date: 04/21/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Crinon, Regis J.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Hartmann, II, Kenneth R
• Application Number:
  US10/419,616
• Publication Number:
  US 20040208204A1
• Time in Patent Office: 2,031 Days
• Field of Search: 370/537, 370/466, 370/328, 370/473, 370/542, 370/432, 725/134, 725/109, 725/93, 725/135
• US Class Current: 370/412
• 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, wherein the determining comprises;

determining the 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;

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 method is performed in response to a plurality of requests to add a new data file to the data carousel.

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

11. 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.

12. 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.

13. 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.

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

15. 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.

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

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

18. 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.

19. A method as recited in claim 18 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.

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

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

22. 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;

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;

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.

23. A method as recited in claim 22 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.

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

25. One or more computer-readable media containing a computer program that is executable by a processor to perform the method recited in claim 22.

45. A method as recited in claim 22, wherein:

the data carousel comprises a single instance of the particular data file; and

the worst case latency between successive transmissions of the data file represents a time between a first transmission of the single instance of the particular file and a next transmission of the single instance of the particular file.

46. A method as recited in claim 22, wherein:

the data carousel comprises first and second instances of the particular data file; and

the worst case latency between successive transmissions of the data file represents a time between a transmission of the first instance of the particular file and a next transmission of the second instance of the particular file,

wherein the time between a transmission of the first instance of the particular file and a next transmission of the second instance of the particular file is greater than or equal to a time between a transmission of the second instance of the particular file and a next transmission of the first instance of the particular file.

26. 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.

27. A method as recited in claim 26 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.

28. A method as recited in claim 26 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.

29. A method as recited in claim 26 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.

30. One or more computer-readable media containing a computer program that is executable by a processor to perform the method recited in claim 26.

31. A method comprising:

identifying a darn carousel, wherein the data carousel comprises a plurality of positions arranged as a loop, wherein;

each of the plurality of positions is configured to maintain a data file, in its entirety; and

the data carousel repeatedly transmits data flies that are maintained in the plurality of positions, wherein an order of data file transmissions is determined based on an order of the positions within the loop;

determining a worst case latency between a transmission of an instance of a particular data file in the data carousel and a next transmission of an instance of the particular data file;

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.

32. 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;

identifying one of the plurality of new data files to store in the data carousel; and

modifying arrangement of the plurality of data files in the data carousel.

33. An apparatus as recited in claim 32 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.

34. An apparatus as recited in claim 32 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.

35. An apparatus as recited in claim 32 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.

36. An apparatus comprising:

a carousel generator configured to generate data files to be stored in 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;

manage the deletion of data files from the data carousel;

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; and

report calculated worst case latency associated with each module in the data carousel, wherein the carousel controller is configured to identify each of these latencies as either complying with or exceeding a reference latency threshold.

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

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

39. An apparatus as recited in claim 36 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.

40. 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 execute a method, the method comprising:

identifying a data carousel, wherein the data carousel comprising a plurality of positions arranged as a loop, wherein;

each of the plurality of positions is configured to maintain a data file, in its entirety; and

the data carousel repeatedly transmits data files that are maintained in the plurality of positions, wherein the order of data file transmissions is determined based on the order of the positions within the loop;

determining a maximum latency value associated with the data carousel;

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

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

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

41. One or more computer-readable media as recited in claim 40 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.

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

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

44. One or more computer-readable media as recited in claim 40 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.