Method and apparatus for scheduling broadcast information

• US 7,036,138 B1
• Filed: 11/08/2000
• Issued: 04/25/2006
• Est. Priority Date: 11/08/2000
• Status: Expired due to Term

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: Digeo Incorporated (CommScope Holding Company, Inc.)
• Inventors: Tash, Jonathan K.
• Primary Examiner(s): TRAN, HAI V
• Application Number:
  US09/709,004
• Time in Patent Office: 1,994 Days
• Field of Search: 725/39, 725/46, 725 52- 54, 725/109, 725/136, 725/139, 725/9, 725 28- 29, 725/32, 725/97, 707/3, 707/10, 709/203, 709/205, 709217-220
• US Class Current: 725/46
• CPC Class Codes: H04H 60/06 Arrangements for scheduling broadcast services or broadcast-related services
• CPC Class Codes: H04N 21/218 Source of audio or video content , e.g. local disk arrays details of retrieval in video databases G06F16/739
• CPC Class Codes: H04N 21/235 Processing of additional data, e.g. scrambling of additional data or processing content descriptors
• CPC Class Codes: H04N 21/2353 specifically adapted to content descriptors, e.g. coding, compressing or processing of metadata
• CPC Class Codes: H04N 21/26208 the scheduling operation being performed under constraints
• CPC Class Codes: H04N 21/26258 for generating a list of items to be played back in a given order, e.g. playlist, or scheduling item distribution according to such list retrieval of multimedia data based on playlists G06F16/40
• CPC Class Codes: H04N 21/26603 for automatically generating descriptors from content, e.g. when it is not made available by its provider, using content analysis techniques
• CPC Class Codes: H04N 21/2665 Gathering content from different sources, e.g. Internet and satellite
• CPC Class Codes: H04N 21/435 Processing of additional data, e.g. decrypting of additional data, reconstructing software from modules extracted from the transport stream
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

Methods and apparatus are disclosed for efficiently scheduling incoming information objects so that timely objects from a variety of content classes are scheduled for broadcast. The incoming information objects are preferably received from one or more information sources, and are tagged with attributes that associate each object with one or more classes of information (e.g., sports, news, etc.), and provide a gauge of the timeliness or ‘age’ of the object. The tags can be used to select and broadcast objects from a variety of classes, and to identify the most timely objects at any give time.

Claims

1. A method for delivering objects to one or more receiver units, comprising:

receiving a number of incoming objects, each object corresponding to one or more classes;

maintaining objects from a variety of classes in an object schedule, wherein each object has a utility factor, and the value of the utility factor is dependent, at least to some degree, on the position of the object in the object schedule; and

delivering selected objects from the object schedule to the one or more receiver units based on the position of the object in the object schedule,

wherein each class has a utility factor that is calculated by combining, via a sub-linear function, the utility factors of those scheduled objects that correspond to the class, and wherein the sub-linear function includes a square-root function.

2. A method according to claim 1, wherein objects from a variety of classes are maintained by determining which of the incoming objects are to be added to the object schedule and which of the cached objects in the object schedule are be evicted, such that objects from a variety of classes are maintained in the object schedule.

3. A method according to claim 1, wherein the object schedule has an overall schedule utility factor, the overall schedule utility factor is calculated by combining via a schedule function the utility factors for each of the classes.

4. A method according to claim 3, wherein the schedule function is a summing function.

5. A method according to claim 3, wherein objects from a variety of classes are maintained in the object schedule by:

receiving a new object;

scheduling the new object in an initial position within the object schedule; and

reordering the scheduled objects so that the overall schedule utility factor is increased.

6. A method according to claim 1, wherein each object in the object schedule has an estimated time for delivery based on the position of the object in the schedule.

7. A method according to claim 6, wherein each object in the schedule has an importance factor.

8. A method according to claim 7, wherein the utility factor for each object is dependent on the estimated time for delivery and the importance factor.

9. A method according to claim 8, wherein the value of the utility factor Utility_obj for each object is related to the importance factor of the object times a function f(AGE), where f(AGE) is a predetermined function that decreases with an AGE of the object, the AGE of the object being related to the estimated time for delivery.

10. A method according to claim 9, wherein the value of the utility factor Utility_obj for each object Is related to the importance factor of the object times a freshness function R(AGE), where R(AGE) is a predetermined function that decreases with an AGE of the object, the AGE of the object being related to the estimated time for delivery.

11. A method according to claim 1, wherein each object in the schedule is a member of one or more classes, and the utility factor for each object is dependent on a ClassVarietyScore of each of the member classes.

12. A method according to claim 11, wherein the ClassVarietyScore for each class is a measure of the number of member objects of the class that were previously broadcast and/or are scheduled to be broadcast.

13. A method according to claim 12, wherein the contribution of each object to the ClassVarietyScore decreases with time.

14. A method according to claim 13, wherein each class has a class importance factor.

15. A method according to claim 14, wherein the utility factor Utility_obj for each object is the sum over all member classes, the class importance factor of each member class times a function g(ClassVarietyScore), where g(ClassVarietyScore) is a predetermined function that decreases with the ClassVarietyScore of the class.

35. A method according to claim 4, further comprising returning to the calculating step to calculate a new score, S_i, for each object using the relation S_i=R_i*(T_c−

T_l).

16. A method for scheduling objects for delivery to one or more receiver units, the method comprising:

receiving one or more incoming objects, each having a utility factor;

scheduling the objects for delivery in an initial scheduling order, the value of the utility factor for each of the objects being dependent, at least to some degree, on the position of the object in the schedule;

calculating an overall schedule utility factor for the schedule by combining the utility factors of each of the scheduled objects using a predefined function;

reordering the scheduled objects so that the overall schedule utility factor is increased, wherein reordering the scheduled objects includes;

moving a selected object up one position in the schedule;

calculating an updated overall schedule utility factor;

determining if the updated overall schedule utility factor is greater than the previous overall schedule utility factor; and

retaining the new position of the selected object if the updated overall schedule utility factor is greater than the previous overall schedule utility factor; and

delivering one or more of the objects from the top of the schedule.

17. A method according to claim 16, further comprising:

repeating the moving, calculating, determining, and retaining steps until the updated overall schedule utility factor is not greater than the previous overall schedule utility factor; and

returning the selected object to its previous position when the updated overall schedule utility factor is not greater than the previous overall schedule utility factor.

18. A method according to claim 16, wherein reordering the scheduled objects includes:

moving a selected object to a random position in the schedule;

calculating an updated overall schedule utility factor;

determining if the updated overall schedule utility factor is greater than the previous overall schedule utility factor, and

retaining the new position of the selected object if the updated overall schedule utility factor is greater than the previous overall schedule utility factor.

19. A method according to claim 18, further comprising:

repeating the moving, calculating, determining, and retaining steps until the updated overall schedule utility factor is not greater than the previous overall schedule utility factor; and

returning the selected object to its previous position when the updated overall schedule utility factor is not greater than the previous overall schedule utility factor.

20. A method according to claim 18, further comprising:

selecting another object and moving the selected object to a random position in the schedule;

repeating the moving, calculating, determining, and retaining steps until the updated overall schedule utility factor is not greater than the previous overall schedule utility factor; and

returning the selected object to its previous position when the updated overall schedule utility factor is not greater than the previous overall schedule utility factor.

21. A method according to claim 16, wherein the utility factor of an object is higher than another similarly situated object if the object is more timely.

22. A method according to claim 16, wherein the utility factor of an object increases the overall schedule utility factor more than another similarly situated object if the object provides more variety to the object schedule.

23. A method according to claim 16, wherein each object in the schedule has an estimated time for delivery based on the position of the object in the schedule, and the value of the utility factor for the object is dependent on the estimated time for delivery.

24. A method according to claim 23, wherein the estimated time for delivery of each object is calculated by:

estimating a current channel bandwidth for delivery of the scheduled objects; and

calculate an estimated time for delivery for each object using the size of each scheduled object and the estimated channel bandwidth.

25. A method according to claim 24, wherein each object in the schedule is a member of one or more classes, and the value of the utility factor for each class is dependent on a measure of the objects assigned to the class.

26. A method according to claim 25, wherein the measure of the objects is the number of objects assigned to the class.

27. A method according to claim 25, wherein the measure of the objects is the number of object bytes assigned to the class.

28. A method according to claim 25, wherein the measure of the objects is the sum of the object utility factors assigned to the class.

29. An information delivery system, comprising

a receiver for receiving a stream of incoming objects, each object corresponding to one or more classes;

object schedule for storing a set of the incoming objects, wherein each object has a utility factor, and the value of the utility factor is dependent, at least to some degree, on a position of the object in the object schedule;

object scheduler for determining which of the incoming objects to add to the object schedule and which of the cached objects to evict from the object schedule, such that objects from a variety of classes are maintained in the object store; and

delivery means for delivering selected cached objects from the object schedule to one or more receiver units based on the position of the object in the object schedule,

wherein each class has a utility factor that is calculated by combining, via a sub-linear function, the utility factors of those scheduled objects that correspond to the class, and wherein the sub-linear function includes a square-root function.

30. An information delivery system according to claim 29, wherein the object schedule has an overall schedule utility factor, the overall schedule utility factor is calculated by combining, via a schedule function, the utility factors for each of the classes.

31. An information delivery system according to claim 30, wherein the schedule function is a summing function.

32. A system for scheduling objects for delivery to one or more receiver units, comprising:

a receiver for receiving one or more objects, each object having a utility factor;

an object scheduler for scheduling the objects for delivery in an initial scheduling order, the value of the utility factor for each of the objects being dependent, at least to some degree, on the position of the object in the schedule;

the object scheduler calculating an overall schedule utility factor for the schedule by combining the utility factors of each of the scheduled objects using a predetermined function;

the object scheduler reordering the scheduled objects so that the overall schedule utility factor is increased, wherein reordering the scheduled objects includes;

moving a selected object up one position in the schedule;

calculating an updated overall schedule utility factor;

determining if the updated overall schedule utility factor is greater than the previous overall schedule utility factor; and

retaining the new position of the selected object if the updated overall schedule utility factor is greater than the previous overall schedule utility factor; and

delivery means for delivering one or more of the objects from the top of the schedule to the one or more receiver units.

33. A method for transmitting one or more objects (O₁, . . . O_N) to one or more receiver units, wherein each object O_i has one or more packets (P₁, . . . P_K) and a packet transfer rate R_i, the method comprising:

initializing a transmit time (T₁, . . . T_N) for each object to zero;

calculating a score, S_i, for each object using the relation S_i=R_i*(T_c−

T_i), where T_c is the current time;

transmitting one or more packets from the object with the highest score, S_i; and

setting the transmit time T_i for the object with the highest score to the current time T_c.

34. A method according to claim 33, further comprising:

determining if the last transmitted packet was the last packet of the object with the highest score; and

removing the object with the highest score if the last transmitted packet was the last packet of the object with the highest score.

36. A method for transmitting one or more objects to one or more receiver units, wherein each object has one or more data packets, comprising:

providing a next transmit time variable for each object;

initializing the next transmit time variable for each object to a predetermined value;

selecting the object with the lowest next transmit time variable;

transmitting one or more packets from the selected object; and

incrementing the next transmit time variable for the selected object by an incremental value;

repeating the selecting, transmitting and incrementing steps;

wherein the incremental value is dependent on the transfer rate for the selected object, and wherein the incremental value is l/(the transfer rate) for the selected object.

37. A method according to claim 36, further comprising:

determining if the last transmitted packet was the last packet of the selected object; and

removing the selected object if the last transmitted packet was the last packet of the selected object.

38. A method for delivering objects to one or more receiver units, comprising:

receiving a number of incoming objects, each object corresponding to one or more classes;

maintaining objects from a variety of classes in an object schedule, wherein each object has a utility factor, and the value of the utility factor is dependent, at least to some degree, on the position of the object in the object schedule; and

delivering selected objects from the object schedule to the one or more receiver units based on the position of the object in the object schedule,

wherein each object in the object schedule has an estimated time for delivery based on the position of the object in the schedule, wherein each object in the schedule has an importance factor, wherein the utility factor for each object is dependent on the estimated time for delivery and the importance factor, and wherein the value of the utility factor Utility_obj for each object is related to the importance factor of the object times a function f(AGE), where f(AGE) is a predetermined function that decreases with an AGE of the object, the AGE of the object being related to the estimated time for delivery.

39. A method according to claim 38, wherein the value of the utility factor Utility_obj for each object is related to the importance factor of the object times a freshness function R(AGE), where R(AGE) is a predetermined function that decreases with an AGE of the object, the AGE of the object being related to the estimated time for delivery.

40. A method for delivering objects to one or more receiver units, comprising:

receiving a number of incoming objects, each object corresponding to one or more classes;

maintaining objects from a variety of classes in an object schedule, wherein each object has a utility factor, and the value of the utility factor is dependent, at least to some degree, on the position of the object in the object schedule; and

delivering selected objects from the object schedule to the one or more receiver units based on the position of the object in the object schedule,

wherein each object in the schedule is a member of one or more classes, and the utility factor for each object is dependent on a ClassVarietyScore of each of the member classes, the ClassVarietyScore for each class is a measure of the number of member objects of the class that were previously broadcast and/or are scheduled to be broadcast, wherein the contribution of each object to the ClassVarietyScore decreases with time, wherein each class has a class importance factor, and wherein the utility factor Utility_obj for each object is the sum over all member classes, the class importance factor of each member class times a function g(ClassVarietyScore), where g(ClassVarietyScore) is a predetermined function that decreases with the ClassVarietyScore of the class.