Maximum factor selection policy for batching VOD requests

• US 5,631,694 A
• Filed: 02/01/1996
• Issued: 05/20/1997
• Est. Priority Date: 02/01/1996
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C., Yu, Philip S. L., Wolf, Joel L.
• Primary Examiner(s): Peng, John K.
• Assistant Examiner(s): GRANT, CHRISTOPHER C
• Application Number:
  US08/595,313
• Time in Patent Office: 474 Days
• Field of Search: 348/7, 348/12, 348/13, 348/6, 348/1, 348/10, 455/2, 455/4.2, 455/5.1, 455/6.1, 455/6.2
• US Class Current: 725/93
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

A VOD scheduler maintains a queue of pending performance for each video. Using the notion of queue selection factor, a batching policy is devised that schedules the video with the highest selection factor. Selection factors are obtained by applying discriminatory weighting factors to the adjusted queue lengths associated with each video where the weight decreases as the popularity of the respective video increases and the queue length is adjusted to take defection into account.

Claims

1. A method of scheduling a plurality of video requests, comprising the steps of:

a) placing each of said plurality of video requests into a respective corresponding queue;

b) determining a queue selection factor for each queue based on length of each queue and defections in each queue; and

c) scheduling one of said plurality of video requests based on said queue selection factor of each of said queues.

2. A method of scheduling a plurality of video requests according to claim 1, wherein said queue selection factor is based on video request frequency of each of said plurality of video requests.

3. A method of scheduling a plurality of video requests according to claim 1, wherein said queue selection factor is based on time since last scheduling in said respective corresponding queue.

4. A method of scheduling a plurality of video requests according to claim 2, wherein said one of said plurality of video requests is scheduled having a largest queue selection factor.

5. A method of scheduling a plurality of video requests according to claim 3, wherein said one of said plurality of video requests is scheduled having a largest queue selection factor.

6. A method of scheduling a plurality of video requests according to claim 2, wherein for queue i:

q_i =queue length

d_i =defections since last scheduling

f_i =relative request frequency.

and the queue selection factor is;

##EQU2##

7. A method of scheduling a plurality of video requests according to claim 3, wherein for queue i:

q_i =queue length

d_i =defections since last scheduling

δ

t_i =time since last scheduling

and the queue selection factor is;

space="preserve" listing-type="equation">(q.sub.i +d.sub.i)δ

t.sub.i.

8. A method of scheduling a plurality of video requests according to claim 2, wherein scheduling occurs when a request is made or when a communications channel becomes available to transmit a video signal corresponding to a respective one of said video requests.

9. A method of scheduling a plurality of video requests according to claim 3, wherein scheduling occurs when a request is made or when a communications channel becomes available to transmit a video signal corresponding to a respective one of said video requests.

10. Video apparatus for scheduling a plurality of video requests, comprising:

means for receiving a plurality of video requests and for maintaining a plurality of queues, each of said queues storing common ones of said requests

means for determining a queue selection factor for each queue based on length of each queue and defections in each queue; and

means for scheduling one of said plurality of video requests based on said queue selection factor of each of said queues.

11. Apparatus for scheduling a plurality of video requests according to claim 10 wherein said queue selection factor is based on video request frequency of each of said plurality of video requests.

12. Apparatus for scheduling a plurality of video requests according to claim 10 wherein said queue selection factor is based on time since last scheduling in said respective corresponding queue.

13. Apparatus for scheduling a plurality of video requests according to claim 11 wherein said one of said plurality of video requests is scheduled having a largest queue selection factor.

14. Apparatus for scheduling a plurality of video requests according to claim 11, wherein for queue i:

q_i =queue length

d_i =defections since last scheduling

f_i =relative request frequency

and the queue selection factor is;

##EQU3##

15. Apparatus for scheduling a plurality of video requests according to claim 12, wherein for queue i:

q_i =queue length

d_i =defections since last scheduling

δ

t_i =time since last scheduling

and the queue selection factor is;

space="preserve" listing-type="equation">(q.sub.i +d.sub.i)δ

t.sub.i.

16. Apparatus for scheduling a plurality of video requests according to claim 11, wherein scheduling occurs when a request is made or when a communications channel becomes available to transmit a video signal corresponding to a respective one of said video requests.

17. A method of scheduling a plurality of video requests according to claim 12, wherein scheduling occurs when a request is made or when a communications channel becomes available to transmit a video signal corresponding to a respective one of said video requests.