Method and system for scheduling the transfer of data sequences utilizing an anti-clustering scheduling algorithm

Claim 2

In a system having a resource for servicing requests of a plurality of consumers to utilize the resource and a schedule having entries for allocation to the consumer requests, an entry being available when the entry is not allocated to a consumer request, the schedule having a clustering indicator for the available entries indicating a clusteriness of the schedule when an available entry is allocated to a consumer request, a method for scheduling a consumer request comprising the steps of: determining the clustering indicator for the available entries in the schedule; selecting the clustering indicator indicating a lowest clusteriness of the schedule; and allocating the consumer request to the available entry with the selected clustering indicator.

Claim 3

The method of claim 1 wherein the system is a video-on-demand system, wherein the resource is a storage device containing video image sequences, and wherein the consumer requests are for requesting video image sequences contained on the storage device.

Claim 4

The method of claim 1 wherein the system is a video-on-demand system, wherein the resource is a storage device containing video image sequences, and wherein the consumer requests are for storing video image sequences onto the storage device.

Claim 5

The method of claim 1 wherein the step of determining the clustering indicator includes the steps of: for each available entry, allocating the available entry to the consumer request; calculating the clustering indicator after allocating the available entry; and deallocating the available entry from the consumer request after calculating the clustering indicator.

Claim 6

The method of claim 4 wherein entries in the schedule are organized in sequence, wherein the schedule contains unavailable entries allocated to consumer requests, wherein the schedule has a group of sequentially contiguous unavailable entries and a group of sequentially contiguous available entries, wherein the step of calculating the clustering indicator includes the steps of: examining the entries in the schedule; determining the groups of sequentially contiguous unavailable entries and the groups of sequentially contiguous available entries in response to examining the entries; and calculating the clustering indicator in response to determining the groups of sequentially contiguous unavailable entries and the groups of sequentially contiguous available entries.

Claim 7

The method of claim 4 wherein entries in the schedule are organized in sequence, wherein the schedule contains unavailable entries allocated to consumer requests, wherein the schedule has a group of contiguous unavailable entries and a group of contiguous available entries, wherein each group of contiguous available entries and contiguous unavailable entries is contiguous in sequence and has an associated counter, wherein the step of determining the clustering indicator includes the steps of: for each group of contiguous unavailable entries and contiguous available entries, for each entry in the group, adjusting the counter associated with the group; and calculating the clustering indicator by combining the counters.

Claim 8

In a system having a resource for servicing requests of a plurality of consumers to utilize the resource and a schedule having sequential entries for allocation to the consumer requests, an entry being available when the entry is not allocated to a consumer request, each entry having a slip indicator identifying an amount of time that a request allocated to the entry waits until being serviced, wherein the system has an acceptable time that the consumer requests can wait until being serviced, the schedule having a clustering indicator indicating a clusteriness of at least a portion of the schedule, a method for scheduling a consumer request comprising the steps of: for each available entry in the schedule having a slip indicator within the acceptable time, determining the clustering indicator for the schedule if the request were allocated to the available entry; storing the clustering indicator with a reference to the available entry; selecting the stored clustering indicator indicating a lowest clusteriness of the schedule; and allocating the consumer request to the available entry referred to by the selected stored clustering indicator.

Claim 9

In a system having a resource for servicing requests of a plurality of consumers to utilize the resource and a schedule having sequential entries for allocation to the consumer requests, an entry being available when the entry is not allocated to a consumer request, each entry having a slip indicator identifying an amount of time that a request allocated to the entry waits until being serviced, wherein the system has an acceptable time that the consumer requests can wait until being serviced, the schedule having a clustering indicator indicating a clusteriness of at least a portion of the schedule, a method for scheduling a consumer request comprising the steps of: for each available entry in the schedule having a slip indicator within the acceptable time, determining the clustering indicator for the schedule if the request were allocated to the available entry; storing the clustering indicator with a reference to the available entry; selecting the stored clustering indicator indicating a lowest clusteriness of the schedule; and allocating the consumer request to the available entry referred to by the selected stored clustering indicator.

Claim 10

The method of claim 7 wherein the step of selecting the stored clustering indicator includes the steps of: determining if there are available entries in the schedule having a slip indicator within the acceptable time; and when it is determined that there are available entries in the schedule having a slip indicator within the acceptable time, selecting the stored clustering indicator indicating a least clusteriness of the schedule, and wherein the step of allocating the consumer request includes the steps of: when it is determined that there are available entries in the schedule having a slip indicator within the acceptable time, allocating the consumer request to the available entry referred to by the selected stored clustering indicator; and when it is determined that there are no available entries in the schedule having a slip indicator within the acceptable time, allocating the consumer request to an available entry with a least slip indicator.

Claim 11

The method of claim 7 wherein the system is a video-on-demand system, wherein the resource is a storage device containing video image sequences, and wherein the consumer requests are for requesting video image sequences contained on the storage device.

Claim 12

The method of claim 7 wherein the system is a video-on-demand system, wherein the resource is a storage device containing video image sequences, and wherein the consumer requests are for storing video image sequences onto the storage device.

Claim 13

The method of claim 7 wherein the schedule contains unavailable entries allocated to consumer requests, wherein the schedule has a group of sequentially contiguous unavailable entries and a group of sequentially contiguous available entries, wherein the step of determining the clustering indicator includes the steps of: examining the entries in the schedule; determining the groups of sequentially contiguous unavailable entries and the groups of sequentially contiguous available entries in response to examining the entries; and calculating the clustering indicator in response to determining the groups of sequentially contiguous unavailable entries and the groups of sequentially contiguous available entries.

Claim 14

The method of claim 7 wherein the schedule contains unavailable entries allocated to consumer requests, wherein the schedule has a group of sequentially contiguous unavailable entries and a group of sequentially contiguous available entries, wherein each group of sequentially contiguous available entries and sequentially contiguous unavailable entries has an associated counter, wherein the step of determining the clustering indicator includes the steps of: for each group of sequentially contiguous unavailable entries and sequentially contiguous available entries, for each entry in the group, adjusting the counter associated with the group; and calculating the clustering indicator by combining the counters.

Claim 15

In a system having a resource for servicing requests of a plurality of consumers to utilize the resource and a schedule having entries for storing the consumer requests, an entry being available when the entry does not contain a consumer request, the schedule having a clustering indicator indicating a clusteriness of the schedule, the available entries having an associated value identifying a change in the clustering indicator of the schedule when a consumer request is stored in the available entry, a method for scheduling a consumer request comprising the steps of: examining the associated values of the available entries in the schedule; selecting an available entry with a smallest associated value identifying a least change in the clustering indicator; and storing the consumer request in the selected entry.

Claim 16

In a system having a resource for servicing requests of a plurality of consumers to utilize the resource and a schedule having entries for storing the consumer requests, an entry being available when the entry does not contain a consumer request, the schedule having a clustering indicator indicating a clusteriness of the schedule, the available entries having an associated value identifying a change in the clustering indicator of the schedule when a consumer request is stored in the available entry, a method for scheduling a consumer request comprising the steps of: examining the associated values of the available entries in the schedule; selecting an available entry with a smallest associated value identifying a least change in the clustering indicator; and storing the consumer request in the selected entry.

Claim 17

The method of claim 13 wherein the system is a video-on-demand system, wherein the resource is a storage device containing video image sequences, and wherein the consumer requests are for requesting video image sequences contained on the storage device.

Claim 18

The method of claim 13 wherein the system is a video-on-demand system, wherein the resource is a storage device containing video image sequences, and wherein the consumer requests are for storing video image sequences onto the storage device.

Claim 19

The method of claim 13 wherein the entries in the schedule are organized sequentially, wherein the schedule contains unavailable entries, wherein an unavailable entry stores a consumer request, wherein the schedule contains groups of sequentially contiguous unavailable entries and groups of sequentially contiguous available entries, wherein the associated values of the available entries comprise a plurality of values, wherein the step of examining the associated values includes the step of: examining a first of the values that indicates a number of entries in a group of sequentially contiguous available entries that precedes the available entry; examining a second of the values after examining the first value wherein the second value indicates a number of entries in a group of sequentially contiguous unavailable entries that precedes the available entry; examining a third of the values after examining the second value wherein the third value indicates a number of entries in a group of sequentially contiguous available entries that follows the available entry; examining a fourth of the values after examining the third value wherein the fourth value indicates a number of entries in a group of sequentially contiguous unavailable entries that follows the available entry; and combining the first value, the second value, the third value and the fourth value.

Claim 20

The method of claim 13, further including the steps of: examining the schedule after storing the consumer request in the selected entry to determine available entries that precede the selected entry; examining the schedule to determine available entries that follow to the selected entry; and updating the associated values of the available entries that precede the selected and the following available entries to reflect the storing of the consumer request in the selected entry.

Claim 21

A scheduling mechanism comprising: a resource for servicing requests of consumers; a list having a plurality of entries for maintaining the requests of the consumers and having a clustering indicator indicating the clusteriness of the list; a selecting component for selecting an entry of the list to maintain a request to least affect the clustering indicator; and an allocating component for receiving a request from a consumer, for invoking the selecting component to select an entry and for allocating the consumer request to the selected entry.

Claim 22

A scheduling mechanism comprising: a resource for servicing requests of consumers; a list having a plurality of entries for maintaining the requests of the consumers and having a clustering indicator indicating the clusteriness of the list; a selecting component for selecting an entry of the list to maintain a request to least affect the clustering indicator; and an allocating component for receiving a request from a consumer, for invoking the selecting component to select an entry and for allocating the consumer request to the selected entry.

Claim 23

The scheduling mechanism of claim 18 wherein the scheduling mechanism is part of a video-on-demand system.

Claim 24

In a system for scheduling consumer requests, the system having a resource for servicing requests of a plurality of consumers to utilize the resource and a schedule having entries for allocation to the consumer requests, an entry being available when the entry is not allocated to a consumer request, the available entries having a clustering indicator indicating a clusteriness of at least a portion of the schedule when an available entry is allocated to a consumer request and having a slip value for indicating an amount of time that a consumer request waits for servicing when allocated to the available entry, the system having a predefined value indicating an acceptable slip value, the system comprising: means for receiving a consumer request for servicing by the resource; means, responsive to receiving the consumer request, for measuring the clustering indicator for the available entries; means, responsive to measuring the clustering indicator, for measuring the slip value for the available entries; and means, responsive to measuring the slip value, for allocating the consumer request to an available entry with a slip value less than the predefined value and with a least clustering indicator.

Claim 25

In a system for scheduling consumer requests, the system having a resource for servicing requests of a plurality of consumers to utilize the resource and a schedule having entries for allocation to the consumer requests, an entry being available when the entry is not allocated to a consumer request, the available entries having a clustering indicator indicating a clusteriness of at least a portion of the schedule when an available entry is allocated to a consumer request and having a slip value for indicating an amount of time that a consumer request waits for servicing when allocated to the available entry, the system having a predefined value indicating an acceptable slip value, the system comprising: means for receiving a consumer request for servicing by the resource; means, responsive to receiving the consumer request, for measuring the clustering indicator for the available entries; means, responsive to measuring the clustering indicator, for measuring the slip value for the available entries; and means, responsive to measuring the slip value, for allocating the consumer request to an available entry with a slip value less than the predefined value and with a least clustering indicator.

Claim 26

In a video-on-demand system having a storage device for servicing requests of a plurality of subscribers to receive video image sequences stored on the storage device and a schedule having bandwidth units for allocation to the subscriber requests, a bandwidth unit being available when the bandwidth unit is not allocated to a subscriber request, the schedule having a clustering indicator indicating a clusteriness of at least a portion of the schedule, the available bandwidth units having a slip value for indicating an amount of time that a subscriber request waits for servicing when allocated to the available bandwidth unit, the video-on-demand system having a predefined value indicating an acceptable slip value, a method for allocating a bandwidth unit to the subscriber request comprising the steps of: for each bandwidth unit in the schedule, examining the bandwidth unit; determining whether the examined bandwidth unit is available after examining the bandwidth unit; when the bandwidth unit is available, allocating the bandwidth unit to the subscriber request; measuring the clustering indicator of the schedule after allocating the bandwidth unit; deallocating the bandwidth unit from the subscriber request after measuring the clustering indicator; measuring the slip value of the bandwidth unit after deallocating the bandwidth unit; determining whether the slip value is less than the predefined value after measuring the slip value; when the slip value is less than the predefined value, determining whether the bandwidth unit has a least clustering value; when the bandwidth unit has a least clustering value, selecting the bandwidth unit; and allocating the selected bandwidth unit to the subscriber request.

Claim 27

In a video-on-demand system having a storage device for servicing requests of a plurality of subscribers to receive video image sequences stored on the storage device and a schedule having bandwidth units for allocation to the subscriber requests, a bandwidth unit being available when the bandwidth unit is not allocated to a subscriber request, the schedule having a clustering indicator indicating a clusteriness of at least a portion of the schedule, the available bandwidth units having a slip value for indicating an amount of time that a subscriber request waits for servicing when allocated to the available bandwidth unit, the video-on-demand system having a predefined value indicating an acceptable slip value, a method for allocating a bandwidth unit to the subscriber request comprising the steps of: for each bandwidth unit in the schedule, examining the bandwidth unit; determining whether the examined bandwidth unit is available after examining the bandwidth unit; when the bandwidth unit is available, allocating the bandwidth unit to the subscriber request; measuring the clustering indicator of the schedule after allocating the bandwidth unit; deallocating the bandwidth unit from the subscriber request after measuring the clustering indicator; measuring the slip value of the bandwidth unit after deallocating the bandwidth unit; determining whether the slip value is less than the predefined value after measuring the slip value; when the slip value is less than the predefined value, determining whether the bandwidth unit has a least clustering value; when the bandwidth unit has a least clustering value, selecting the bandwidth unit; and allocating the selected bandwidth unit to the subscriber request.

Claim 28

The method of claim 21 wherein the step of allocating the selected bandwidth unit includes the steps of: determining if a bandwidth unit is selected; when it is determined that a bandwidth unit is selected, allocating the selected bandwidth unit to the subscriber request; when it is determined that a bandwidth unit is not selected, determining an available bandwidth unit with a least slip value; and allocating the determined bandwidth unit to the subscriber request.

Claim 29

In a video-on-demand system having a storage device for servicing requests of a plurality of subscribers to receive video image sequences stored on the storage device and a schedule having bandwidth units for allocation to the subscriber requests, a bandwidth unit being available when the bandwidth unit is not allocated to a subscriber request, the schedule having a clustering indicator indicating a clusteriness of at least a portion of the schedule, the available bandwidth units having a slip value for indicating an amount of time that a subscriber request waits for servicing when allocated to the available bandwidth unit, the video-on-demand system having a predefined value indicating an acceptable slip value, a method for allocating a bandwidth unit to the subscriber request comprising the steps of: identifying the bandwidth units with a slip value less than the predefined value; for the identified bandwidth units in the schedule, examining the bandwidth unit; determining whether the examined bandwidth unit is available after examining the bandwidth unit; when the bandwidth unit is available, allocating the bandwidth unit to the subscriber request; measuring the clustering indicator of the schedule after allocating the bandwidth unit; deallocating the bandwidth unit from the subscriber request after measuring the clustering indicator; determining whether the bandwidth unit has a least clustering value after deallocating the bandwidth unit; when the bandwidth unit has a least clustering value, selecting the bandwidth unit; and allocating the selected bandwidth unit to the subscriber request.

Claim 30

In a video-on-demand system having a storage device for servicing requests of a plurality of subscribers to receive video image sequences stored on the storage device and a schedule having bandwidth units for allocation to the subscriber requests, a bandwidth unit being available when the bandwidth unit is not allocated to a subscriber request, the schedule having a clustering indicator indicating a clusteriness of at least a portion of the schedule, the available bandwidth units having a slip value for indicating an amount of time that a subscriber request waits for servicing when allocated to the available bandwidth unit, the video-on-demand system having a predefined value indicating an acceptable slip value, a method for allocating a bandwidth unit to the subscriber request comprising the steps of: identifying the bandwidth units with a slip value less than the predefined value; for the identified bandwidth units in the schedule, examining the bandwidth unit; determining whether the examined bandwidth unit is available after examining the bandwidth unit; when the bandwidth unit is available, allocating the bandwidth unit to the subscriber request; measuring the clustering indicator of the schedule after allocating the bandwidth unit; deallocating the bandwidth unit from the subscriber request after measuring the clustering indicator; determining whether the bandwidth unit has a least clustering value after deallocating the bandwidth unit; when the bandwidth unit has a least clustering value, selecting the bandwidth unit; and allocating the selected bandwidth unit to the subscriber request.

Claim 31

The method of claim 23 wherein the step of allocating the selected bandwidth unit includes the steps of: determining if a bandwidth unit is selected; when it is determined that a bandwidth unit is selected, allocating the selected bandwidth unit to the subscriber request; when it is determined that a bandwidth unit is not selected, determining an available bandwidth unit with a least slip value; and allocating the determined bandwidth unit to the subscriber request.

Claim 32

In a video-on-demand system having a storage device for servicing requests of a plurality of subscribers to receive video image sequences stored on the storage device and a schedule having bandwidth units organized in a sequence for allocation to the subscriber requests, a bandwidth unit being available when the bandwidth unit is not allocated to a subscriber request, the schedule having groups of sequentially contiguous available bandwidth units and having a clustering indicator indicating a clusteriness of at least a portion of the schedule, the groups of sequentially contiguous available bandwidth units having a slip value for indicating an amount of time that a subscriber request waits for servicing when allocated to an available bandwidth unit within the group, each group of sequentially contiguous available bandwidth units having a center bandwidth unit being a bandwidth unit closest to the center of the group of available bandwidth units, the video-on-demand system having a predefined value indicating an acceptable slip value, a method for allocating a bandwidth unit to the subscriber request comprising the steps of: determining the groups of sequentially contiguous available bandwidth units with a slip value less than the predefined value; identifying the center bandwidth unit for each determined group of sequentially contiguous available bandwidth units; for the identified bandwidth units in the schedule, measure the delta clustering value; determining whether the bandwidth unit has a least delta clustering value; when the bandwidth unit has a least delta clustering value, selecting the bandwidth unit; and allocating the selected bandwidth unit to the subscriber request.

Claim 33

In a video-on-demand system having a storage device for servicing requests of a plurality of subscribers to receive video image sequences stored on the storage device and a schedule having bandwidth units organized in a sequence for allocation to the subscriber requests, a bandwidth unit being available when the bandwidth unit is not allocated to a subscriber request, the schedule having groups of sequentially contiguous available bandwidth units and having a clustering indicator indicating a clusteriness of at least a portion of the schedule, the groups of sequentially contiguous available bandwidth units having a slip value for indicating an amount of time that a subscriber request waits for servicing when allocated to an available bandwidth unit within the group, each group of sequentially contiguous available bandwidth units having a center bandwidth unit being a bandwidth unit closest to the center of the group of available bandwidth units, the video-on-demand system having a predefined value indicating an acceptable slip value, a method for allocating a bandwidth unit to the subscriber request comprising the steps of: determining the groups of sequentially contiguous available bandwidth units with a slip value less than the predefined value; identifying the center bandwidth unit for each determined group of sequentially contiguous available bandwidth units; for the identified bandwidth units in the schedule, measure the delta clustering value; determining whether the bandwidth unit has a least delta clustering value; when the bandwidth unit has a least delta clustering value, selecting the bandwidth unit; and allocating the selected bandwidth unit to the subscriber request.

Claim 34

The method of claim 25 wherein the step of allocating the selected bandwidth unit includes the steps of: determining if a bandwidth unit is selected; when it is determined that a bandwidth unit is selected, allocating the selected bandwidth unit to the subscriber request; when it is determined that a bandwidth unit is not selected, determining an available bandwidth unit with a least slip value; and allocating the determined bandwidth unit to the subscriber request.

Claim 35

A video demand system comprising: a plurality of storage devices for storing video image sequences; a receiver component for receiving consumer requests for the video image sequences on the storage devices; and a scheduling component further comprising: a schedule having a plurality of entries for maintaining the requests of the consumers and having a clustering indicator indicating a clusteriness of the schedule; a selecting component for selecting an entry in the schedule to maintain a request to least affect the clustering indicator; and an allocating component for receiving a consumer request from the receiver component, for invoking the selecting component to select an entry and for allocating the consumer request to the selected entry.

Claim 36

A video demand system comprising: a plurality of storage devices for storing video image sequences; a receiver component for receiving consumer requests for the video image sequences on the storage devices; and a scheduling component further comprising: a schedule having a plurality of entries for maintaining the requests of the consumers and having a clustering indicator indicating a clusteriness of the schedule; a selecting component for selecting an entry in the schedule to maintain a request to least affect the clustering indicator; and an allocating component for receiving a consumer request from the receiver component, for invoking the selecting component to select an entry and for allocating the consumer request to the selected entry.