System and method for scheduling data delivery using flow and stretch algorithms

• US 6,502,062 B1
• Filed: 06/21/1999
• Issued: 12/31/2002
• Est. Priority Date: 06/21/1999
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Muthukrishnan, Shanmugavelayut, Acharya, Swarup, Sundaram, Ganapathy
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): Tsai, Carol S W
• Application Number:
  US09/337,865
• Time in Patent Office: 1,289 Days
• Field of Search: 702/119, 702/122, 702/125, 702/176-178, 702/179, 702/182-185, 702/186, 702/187, 702/188, 702/FOR.103, 702/FOR.104, 702/FOR.134, 702/FOR.135, 702/FOR.139, 702/FOR.170, 702/FOR.171, 709/231, 709/223, 709/224, 709/225
• US Class Current: 702/186
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 9/505 considering the load

Abstract

In accordance with one embodiment, a method for scheduling the servicing of job requests in a point-to-point communication system having a central server providing job requests to a plurality of local channel servers. In a first step, the method receives a new job request at a central server. A performance of each local channel server is measured, and the job request is dispatched to one of the local channel servers for servicing thereby dependent upon the performance of each of the local channel servers. In one embodiment, the job request is dispatched to the local channel servers having the lowest current average flow time. In another embodiment, the job request is dispatched to the local channel server having the lowest current maximum stretch value, wherein a stretch value is a ratio equal to an amount of time required to service a job request while also serving other uncompleted job requests, divided by an amount of time required to service said job request if no other job requests were required to be serviced.

Claims

1. A method for scheduling the servicing of job requests in a point-to-point communication system having a central server providing job requests to a plurality of local channel servers, the method comprising the steps of:

for each new job request, receiving said job request at said central server;

measuring a flow time for each job request serviced by each of said local channel servers, and

storing said flow times for each job request serviced by said local channel servers,

measuring an average flow time for all job requests serviced by each of said local channel servers; and

dispatching said job request to one of said local channel servers for servicing based on at least said measured average flow time.

2. The method according to claim 1, wherein said dispatching step further comprises dispatching said job request to one of said local channel servers having the lowest average flow time.

5. The method according to claim 1, wherein said method further comprises the steps of:

after said dispatching step, storing said job request in a queue corresponding to said local channel server; and

determining an adaptive schedule for servicing said job requests in said queue.

6. The method according to claim 1, wherein said flow is equal to the difference between an arrival time of said job request and a completion time of said job request.

18. The method of claim 1, wherein said plurality of job requests further comprises a set having n number of job requests, wherein n is an integer.

19. The method of claim 18, wherein said integer n has a value that is equal to a total number of job requests processed by said server system.

20. The method of claim 18, wherein said integer n has a value that is less than a total number of job requests processed by said server system.

3. A method for scheduling the servicing of job requests in a point-to-point communication system having a central server providing job requests to a plurality of local channel servers, the method comprising the steps of:

for each new job request, receiving said job request at said central server;

determining a stretch value for job requests serviced by said local channel server, wherein a stretch value is a ratio equal to an amount of time required to service a job request while also serving other uncompleted job requests, divided by an amount of time required to service said job request if no other job requests were required to be serviced, and

dispatching said job request to one of said local channel servers based on at least a lowest stretch value of each of said channels.

4. The method according to claim 3, wherein said step of determining a stretch value further comprises measuring a maximum stretch value for job requests serviced by said local channel server.

7. The method according to claim 3, wherein said method further comprises the steps of:

after said dispatching step, storing said job request in a queue corresponding to said local channel server; and

determining an adaptive schedule for servicing said job requests in said queue.

8. The method according to claim 7, wherein said step of determining an adaptive schedule further comprises the steps of:

for each of said job requests in said queue, calculating a deadline, D_i, given by D_i=S×

P_i+A_i, wherein P_i is a processing time corresponding to said job request, A_i is an arrival time corresponding to said job request, and S is a stretch value; and

determining a schedule for processing said job requests so that each said job request is serviced within its corresponding deadline.

9. The method of claim 8, wherein said processing time comprises a value corresponding to the size of each said job request divided by a channel bandwidth.

10. The method of claim 8, further comprising the step of proposing said stretch value.

11. The method of claim 10, further comprising the step of calculating said deadlines for each of said job requests as a function of said proposed stretch value.

12. The method of claim 11, wherein said scheduling step further comprises scheduling said job requests, at said proposed stretch value, according to an “

earliest deadline first”

arrangement.

13. The method of claim 12, wherein said stretch value is a feasible stretch value if, when processed in an order dictated by said “

earliest deadline first”

arrangement, a completion time of each and every said job request is prior to said corresponding deadline for each said job request at said feasible stretch value.

14. The method of claim 13, further comprising the steps of:

iteratively adjusting said stretch value until said stretch value is a feasible stretch value; and

after finding said feasible stretch value, processing said job requests in an order dictated by said “

earliest deadline first”

arrangement, said “

earliest deadline first”

arrangement corresponding to said stretch values determined in the latest iteration.

15. The method of claim 14, wherein said adjusting step further comprises adjusting said proposed stretch value by doubling said proposed stretch value.

16. The method of claim 15, wherein said feasible stretch value further comprises an optimal feasible stretch value, said method further comprising the step of adjusting said proposed stretch value until a feasible stretch value is found, said optimal feasible stretch value corresponding to the smallest feasible stretch value that permits said each and every job request to have a completion time prior to said deadline of said job request at said optimal feasible stretch value.

17. The method of claim 16, wherein said adjusting step further comprises performing a binary search for said optimal feasible stretch value after said controller determines that said feasible stretch value falls between said proposed stretch value and double said proposed stretch value.

21. In a point-to-point communication system, a system for scheduling the servicing of job requests comprising:

a plurality of local channel servers, each local channel server having a queue buffer for storing incoming job requests;

a central server coupled to each one of said local channel servers and configured to receive a new job request and to dispatch said new job request to one of said local channel servers for servicing said central server configured to store flow times for each job request serviced by said local channel servers; and

said system is configured to measure an average flow time for all job requests serviced by said local channel server, so as to dispatch said job requests to said local channel servers based on at least said measured average flow time.

22. The system according to claim 21, wherein said central server is configured to dispatch said job request to said local channel server having the lowest average flow time.

23. The system according to claim 21, wherein said flow time is equal to the difference between an arrival time of said job requests and a completion time of said job request.

24. In a point-to-point communication system, a system for scheduling the servicing of job requests comprising:

a plurality of local channel servers, each local channel server having a queue buffer for storing incoming job requests;

a central server coupled to each one of said local channel servers and configured to receive a new job request and to dispatch said new job request to one of said local channel servers for servicing, said central server configured to store stretch values for each job request received by said local channel server, wherein a stretch value is a ratio equal to an amount of time required to service a job request while also serving other uncompleted job requests, divided by an amount of time required to service said job request if no other job requests were required to be serviced,

said system is configured to dispatch a job request to a local channel server based on at least the lowest stretch value.

25. The system according to claim 24, wherein said system is configured to measure a maximum stretch value for job requests serviced by said local channel server.

26. The system according to claim 25, wherein said central server is configured to dispatch said job request to said local channel server having the lowest maximum stretch value.