System and method for fractional resource scheduling

• US 20030028656A1
• Filed: 07/11/2002
• Published: 02/06/2003
• Est. Priority Date: 07/31/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Forgent Networks (Asure Software)
• Inventors: Babka, James Joseph
• Granted Patent: US 7,328,264 B2
• Time in Patent Office: Days
• US Class Current: 709/229
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/52 by attributing bandwidth to queues
• CPC Class Codes: H04L 47/6265 past bandwidth allocation
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/826 Involving periods of time
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

The present invention discloses a system and method for reserving fractionally schedulable resources. The system includes a scheduling engine to receive reservation requests. The scheduling engine applies the reservation request to a resource usage table corresponding to a fractionally schedulable resource required by the reservation request. If the fractionally schedulable resource has adequate capacity to comply with the requested reservation, the scheduling engine will add the reservation request to a resource usage table.

Claims

1. A system for scheduling network resources comprising:

at least one fractionally schedulable resource associated with the scheduling engine and operable to perform multiple parallel tasks and having a maximum capacity;

a scheduling engine operable to receive resource scheduling requests and to maintain a resource usage table;

the resource usage table operable to maintain at least one usage record corresponding to the fractionally schedulable resource, the usage record having a start time, an end time, and a resource usage value;

the resource scheduling request having a start time, an end time, and a resource usage value;

the scheduling engine operable to compare the at least one usage record and the resource scheduling request and determine whether accepting the resource scheduling request will exceed the maximum capacity of the fractionally schedulable resource.

2. The system of claim 1 further comprising the scheduling engine operable to:

compare the start times and end times of the at least one usage record and the resource scheduling request; and

if the usage record start time is later that the start time of the resource scheduling request and the usage record end time is earlier than the end time of the resource scheduling request, increase the resource usage value of the usage record by the resource usage value of the resource scheduling request.

3. The system of claim 1 further comprising the scheduling engine operable to:

compare the start times and end times of the at least one usage record and the resource scheduling request; and

if the usage record start time is earlier than the start time of the resource scheduling request and the usage record end time is earlier than the end time of the resource scheduling request and later than the start time of the resource scheduling request, update the end time of the usage record to equal the start time of the resource scheduling request and create a new usage record having a start time equal to the start time of the resource scheduling request, an end time equal to the original end time of the usage record, and a usage value equal to the usage value of the usage record plus the usage value of the resource scheduling request.

4. The system of claim 1 further comprising the scheduling engine operable to:

compare the start times and end times of the at least one usage record and the resource scheduling request; and

if the usage record start time is later than the start time of the resource scheduling request and earlier than the end time of the resource scheduling request and the usage record end time is later than the end time of the resource scheduling request, update the usage record to have an end time equal to the end time of the resource schedule request and add the usage value of the resource scheduling request to the usage value of the usage record and create a new usage record having a start time equal to the end time of the resource scheduling request, an end time equal to the end time of the usage record and a usage value equal to the original usage value of the usage record.

5. The system of claim 1 further comprising the scheduling engine operable to:

compare the start times and end times of the at least one usage record and the resource scheduling request; and

if the usage record start time is earlier than the start time of the resource scheduling request and the usage record end time is later than the end time of the resource scheduling request;

update the end time of the usage record to the start time of the resource scheduling request;

create a first new usage record having a start time equal to the start time of the resource scheduling request, an end time equal to the end time of the resource schedule request and a usage value equal to the usage value of the usage record added to the usage value of the resource scheduling request; and

create a second new usage record having a start time equal to the end time of the resource scheduling request, an end time equal to the end time of the usage record and a usage value equal to the usage value of the usage record.

6. The system of claim 1 further comprising the scheduling engine operable to:

compare the start times and end times of the at least one usage record and the resource scheduling request; and

identify any time interval between the start time and end times of the resource scheduling request for which there is no corresponding usage record and create a new usage record for each interval having a start time and end time equal to each start and end time of each interval and having a usage value equal to the usage value of the resource scheduling request.

7. A system for scheduling network resources comprising:

a scheduling engine operable to receive resource scheduling requests;

at least one fractionally schedulable resource associated with the scheduling engine and operable to perform multiple parallel tasks; and

the fractionally schedulable resource operable to connect with a plurality of endpoint resources.

8. The system of claim 7 wherein the fractionally schedulable resource further comprises a Multipoint Control Unit having a maximum bandwidth.

9. The system of claim 7 wherein the fractionally schedulable resource further comprises a gateway having a maximum bandwidth.

10. The system of claim 7 wherein the fractionally schedulable resource further comprises a system having a plurality of connections.

11. The system of claim 7 wherein the fractionally schedulable resource further comprises a processor having a maximum processing power.

12. The system of claim 7 wherein the plurality of endpoint resources comprise endpoint resources within a video network.

13. The system of claim 7 wherein the scheduling engine further comprises a resource usage table corresponding to the fractionally schedulable resource.

14. The system of claim 13 further comprising the scheduling engine operable to selectively update the resource usage table.

15. The system of claim 13 wherein the resource usage table scheduling engine further comprises a listing of resource reservations.

16. The system of claim 7 further comprising:

a plurality of fractionally schedulable resources associated with the scheduling engine;

the scheduling engine operable to;

receive reservation requests for at least one of the plurality of fractionally schedulable resources;

determine the availability of the at least one requested fractionally schedulable resource; and

selectively grant the reservation request based upon the determined availability.

17. The system of claim 7 further comprising the scheduling engine operable to receive a reservation request comprising a start time, an end time, and a bandwidth requirement.

18. The system of claim 7 wherein the fractionally schedulable resource further comprises a ITU standard H.320 compliant network resource having a bandwidth.

19. The system of claim 7 further comprising the scheduling engine operable to determine the resource usage of a fractionally schedulable resource for a requested period.

20. The system of claim 7 further comprising the scheduling engine operable to receive resource scheduling requests from a network administrator.

21. The system of claim 7 further comprising the scheduling engine to receive resource scheduling requests from a reservation request application.

22. The systems of claim 7 further comprising a reservation request application operably coupled to the scheduling engine for submitting resource scheduling requests and accessible to a communications network.

23. A scheduling system for reserving fractionally schedulable resources comprising:

a scheduling engine operable to receive reservation requests for at least one associated fractionally schedulable resource;

a resource usage table for each fractionally schedulable resource associated with the scheduling engine, the resource usage table operatively connected to the scheduling engine;

a resource usage table further operable to list resource reservations, each resource reservation having a start time, an end time, and a bandwidth.

24. The scheduling system of claim 23 further comprising the scheduling engine operable to update the resource usage table according to a received reservation request and determine whether the requested resource has adequate capacity to comply with the received reservation request.

25. A method for scheduling fractionally schedulable resources comprising:

receiving a resource reservation request for a fractionally schedulable resource;

determining the availability of the fractionally schedulable resource; and

reserving the requested fractionally schedulable resource if adequate capacity is available.

26. The method of claim 25 further comprising:

updating an associated resource usage table based upon the resource reservation request;

determining whether resource usage exceeds a resource maximum;

granting the resource reservation request where resource usage does not exceed the resource maximum; and

rejecting the resource reservation request if resource usage exceeds the resource maximum.

27. The method of claim 25 wherein receiving the resource reservation request further comprises receiving a start time, an end time, and an associated attribute.

28. The method of claim 25 wherein receiving the resource reservation request further comprises receiving a reservation request from a reservation request application.

29. The method of claim 25 further comprising:

receiving a reservation cancellation request for a resource reservation from a reservation request application; and

canceling the resource reservation.

30. The method of claim 29 further comprising releasing the resource associated with the cancelled resource reservation.

31. The method of claim 25 wherein the fractionally schedulable resource comprises a component having a fractionally schedulable attribute.

32. The method of claim 31 wherein the fractionally schedulable attribute comprises a bandwidth.

33. The method of claim 31 wherein the fractionally schedulable attribute comprises a plurality of connections.

34. The method of claim 31 wherein the fractionally schedulable attribute comprises a processor having a maximum processor power associated therewith.