Interactive video distribution systems – User-requested video program system – Video-on-demand
Reexamination Certificate
1998-10-16
2003-05-27
Faile, Andrew (Department: 2611)
Interactive video distribution systems
User-requested video program system
Video-on-demand
C725S091000, C725S093000, C725S097000, C725S098000, C725S114000, C709S241000
Reexamination Certificate
active
06571391
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to broadcasting systems, and more particularly to the scheduling of job requests to be serviced in an on-demand broadcast system.
BACKGROUND OF THE INVENTION
The demand for broadcast technology has increased with the growth of wireless communication services. Broadcast technology is particularly well suited for disseminating a single item of data to a large number of users.
One type of broadcast system for disseminating information is the push-based system, in which a broadcast server delivers data using a periodic broadcast program based on pre-compiled access profiles and typically without any active user intervention. A broadcast application which transmits or pushes a continuous stream of data relating to stock prices, sports scores or weather forecasts is an example of a push-based system. Push-based systems, however, may not be suitable for dynamic workloads, because the preferences of actual users for a particular data item may differ significantly from the pre-compiled access profiles. In other words, poor performance may result because the scheduling of the data to be disseminated does not account for existing user preferences.
Another type of broadcast system currently being utilized to disseminate data, and the type to which the present invention is directed, is referred to as a pull-based, or “on-demand” broadcast system. In the on-demand broadcast setting, the server broadcasts information in response to explicit client requests to all users, including those who did not request the information. One example (of many) of an on-demand broadcast system that information. One example (of many) of an on-demand broadcast system that currently exists is one in which users request internet data over phone lines and the broadcast server delivers the data via satellite. Another example is a system which broadcasts news, sports and entertainment updates via a wireless interface and provides live audio or video capability in response to a user's request.
When explicit client requests are made for the same data items, a broadcast system is used to advantage by satisfying all of the pending job requests for that data item with a single broadcast of the data item. In this manner, a broadcast system is unlike a point-to-point or unicast system, which require that each client's request for data be individually satisfied, even if more than one client makes a job request for the same data item.
FIG. 1
illustrates a typical on-demand broadcast system. Devices
30
a
,
30
b
and
30
d
make requests for data which are delivered to broadcast server
10
by any uplink method. Specifically, device
30
a
makes a job request for data item a, device
30
b
makes a job request for data item b, and device
30
d
makes a job request for data item d. Broadcast server
10
receives the job requests and broadcasts the requested data via downlink
34
so as to satisfy the job requests. Many job requests may be made for the same data item. Therefore, server
10
may transmit the requested data item once to all of the requesting users at the same time.
Various arrangements for scheduling the broadcast of different data items which have been requested by users have been proposed. One scheduling arrangement, referred to as the “Longest Wait First” method (hereinafter “LWF method”) examines the total waiting time for all of the pending job requests for specific data items. For example, there may be several job requests to the server for the same data item, each request having arrived at a point in time prior to the present. Furthermore, there may be additional requests to the server for another data item. For each job request, the server calculates the time that has elapsed since the job request arrived until the present. The server then sums all of the elapsed times for job requests for a particular data item. The data item which has the largest summed total of waiting times is serviced first, the data item which has the next largest summed total is serviced second, etc. Another scheduling arrangement which has been proposed is the “Shortest Service Time First” method (hereinafter “SSTF method”), in which the data item which can be transmitted in the least amount of time is serviced first.
Another scheduling method is proposed by D. Aksoy and M. Franklin in “Scheduling for Large Scale On-Demand Data Broadcast”, March 1998. Generally, this scheduling method utilizes the frequency with which different data items are requested, so as to minimize overall average response time for data items. This method, however, can only be used for homogenous data items. The homogeneity of data items refers to the size of the data item, i.e.—data items are homogenous when they are identically sized. Thus, the scheduling method proposed in this prior art reference does not address heterogeneous data items.
Although the above-referenced scheduling methods for on-demand broadcast systems have attempted to address performance issues, there is an ever increasing need for improved scheduling methods that provide satisfactory performance in terms of worst case response time and overall average response time.
Therefore, there exists a need for a system and method for optimally scheduling the transmission of heterogeneous data items in an on-demand broadcast system.
SUMMARY OF THE INVENTION
In accordance with one embodiment of the invention, a method for scheduling responses in an on-demand broadcast system is disclosed. The method comprises the steps of receiving at a broadcast server a plurality of job requests for a plurality of data items, and determining an adaptive schedule for broadcasting the data items. In a departure from prior art scheduling methods for on-demand broadcast systems wherein a response to a job request is transmitted entirely before a following response is transmitted, the schedule in accordance with the present invention is adaptively determined such that the broadcast of a first data item may be interrupted upon receipt of a new job request, so as to broadcast a second data item in accordance with a new schedule, and such that the schedule eliminates job requests for a data item that are pending while the broadcast server broadcasts the requested data item.
In accordance with another embodiment of the invention, an on-demand broadcast server computes a feasible stretch value for use in scheduling heterogeneous job requests to be serviced. A stretch value provides an indication of the delay experienced by each job request to complete, when the server processes many job requests concurrently. In one embodiment, for a set of job requests to be serviced in an off-line setting (to be explained later), a processing time is calculated for each job request based on the size of the job and the bandwidth of the broadcast system. Thereafter, a stretch value is proposed and the broadcast server computes a deadline for each job to be the arrival time of the job request plus the product of the processing time and the proposed stretch value. Thereafter, each job request is scheduled, based on an “earliest deadline first” arrangement, wherein the job request that has the earliest deadline is scheduled first, the job request having the next earliest deadline is scheduled second, etc.
The proposed stretch value is deemed feasible if each pending job request can be completed, if performed in the order determined by the earliest deadline first methodology, prior to its deadline. If the proposed stretch value is deemed not feasible, it is adjusted iteratively until a feasible stretch value is found. Once the feasible stretch value is found, the job requests are serviced in the order dictated by the EDF schedule as found in the latest iteration. Once the broadcast of a job request has been completed, all of the pending job requests for the same data item, which arrived prior to the start of the broadcast, are necessarily simultaneously satisfied and can be eliminated from the pending job requests. According to one embodiment, the feasible stretch value is fu
Acharya Swarup
Muthukrishnan Shanmugavelayut
Bui Kieu-Oanh
Faile Andrew
Lucent Technologies - Inc.
Sofer & Haroun LLP
LandOfFree
System and method for scheduling on-demand broadcasts for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for scheduling on-demand broadcasts for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for scheduling on-demand broadcasts for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3070014