JP2001231025A - Video title delivery scheduling method and device - Google Patents

Abstract

(57) [Summary] [PROBLEMS] In a video-on-demand system using a large-capacity downlink of a bandwidth sharing type, it is possible to allow each user to view a title requested by the user at a guaranteed time for each user. In addition, delivery scheduling with improved overall waiting time characteristics is executed. An initial setting waiting time setting unit that sets an initial setting waiting time according to the popularity of a title, and a reference arrangement position calculating unit that calculates a reference arrangement position of a title that is not waiting for delivery based on the initial setting waiting time. If there is a vacancy at the reference placement position in the arranged delivery state, the title is assigned to that title.If there is no vacancy at the reference placement position and there is a vacancy at the position in the forward direction, the assigned other title is Position, and if there is no space at both the reference position and the forward position, an empty delivery position is searched backward to set the position of the title.
A changing unit 16 is provided.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a video-on-demand system for directly delivering a digital moving image title stored in a video server to an image receiving device at a user's home in response to a request from a user via a bandwidth sharing type network. In particular, the present invention relates to a delivery scheduling method in a video-on-demand system, and more particularly to a title delivery scheduling method and apparatus that can determine a time when delivery of a digital moving image title is completed and viewing is possible when a user requests viewing.

[0002]

2. Description of the Related Art Conventionally, in order to enjoy watching video content such as a movie at home, it has conventionally been necessary to use a program broadcast by a broadcasting station or go to a rental video store to rent a video having a desired title. . In program broadcasting, program and movie titles are broadcasted in accordance with a program edited by a broadcasting station, so that each user cannot request a title to view. If you use rental videos, you can watch your favorite titles. However, it is troublesome to go to a rental video store before and after viewing, and there is a possibility that all the titles you want to watch are on loan.

[0003] Therefore, by delivering moving image data via a communication network in response to a user's request (Voice), VoD (Video on Demand) enables viewing of a favorite title while staying at home. : Vide
o On Demand) services have been considered. Vo
In the D system, digitized moving image data is used. However, since the amount of information is enormous (N-standard, which is a standard used for television broadcasting in Japan and North America).
If the moving image data in the TSC format is directly digitized, the moving image data is compressed to about 5 Mbps using a high efficiency coding technique (MPEG (motion picture expert group 2) is generally used). To deliver. Nevertheless, in the case of a movie with a duration of 100 minutes, the data size is about 30 Gbits. That is, since the VoD system is required to directly transfer data files of several tens of Gbits to each home, it is necessary to provide two of (1) a low-cost delivery system and (2) a large-capacity access line. , VoD system.

At this stage, available access lines include an analog telephone line (using a modem) and an ISDN (integrated services digital network).
twork), CATV (cable television) (using cable modem), ADSL (asymmetric digital subsc
riber line) and communication satellites. However, these systems are not realistic, except for CATV and communication satellites, because the time required to deliver a moving image title of several tens of Gbits is several tens to one hundred hours.

[0005] Both the CATV and the communication satellite share the band with a large number of users. At this time, if the title requested by each user is delivered to each user every time the request is made, the delivery cost increases, and it is possible to construct a price competitive system for rental videos. It will be difficult. Therefore, by providing a time lag between the title request and the actual delivery, a batching technique that supports all users who have requested the same title in one delivery is indispensable.

[0006] When using the batching technique, it is necessary to consider that a certain amount of waiting time is required from when a user requests (requests) a title until the user can actually view the title. What is important here is that when the user requests the title, the time at which the title can be viewed is determined and notified to the user.

Several methods have been proposed as digital title delivery scheduling methods, but the following three are typical.

[FIFO (First-in-first-out; First-in Fir
st Out) method] This is the simplest method of delivering in the order requested, and the waiting time is determined when the request is accepted, so that the maximum waiting time can be guaranteed to the user. The difference from the general first-in first-out method is that a new request is not queued for a title already queued because another user has requested the same title. This is due to the characteristic of the bandwidth sharing type network that the delivery can be completed with only one delivery to all the users who are waiting for the request for the same title.

[MQL (Maximum Queue Length) Method] When selecting the next title to be delivered, the title with the largest number of waiting users is selected and delivered. Empirically, it is known that this is a technique for maximizing the throughput. However, in this method, the title to be delivered is determined when a vacant channel occurs, so that the waiting time of the user is not determined at the stage when the user requests the title.

[LWF (Lowest Wait First) Method] When a title to be delivered next is selected, the sum of the waiting times (the sum of the waiting times of the individual users up to the present for all the waiting users) is calculated. Select and deliver the largest title. Empirically, it is known that this is a technique for minimizing the average waiting time. However, with this method,
Since the title to be delivered is determined when an empty channel occurs, the waiting time of the user is not determined at the stage when the user requests the title.

After all, among the above three methods, the FIF
The O method is the only method that determines the viewable time,
In the FO method, all titles are treated the same,
There is room for improving the average waiting time. That is, it is generally known that the ratio of the number of users who desire to view individual titles is not uniform over all titles but has a biased distribution. For example,
Zipf distribution where the value of parameter θ is 0.271

[0012]

(Equation 1)

## EQU1 ## Therefore, by setting delivery scheduling so that less popular titles are delivered at later times, an improvement in the average waiting time guaranteed for the user can be expected. Furthermore, this makes it possible to provide a particularly popular topic work to the user with a short waiting time.

[0014]

SUMMARY OF THE INVENTION An object of the present invention is a video title delivery scheduling method in a video-on-demand system via a large-capacity bandwidth sharing network, which satisfies the following requirements (main points). It is another object of the present invention to provide a moving picture title delivery scheduling device that performs scheduling based on this scheduling method.

(1) To enable a user to view a title requested by a user at a guaranteed time for each user. In the present invention, since the burst delivery is assumed that the entire title has arrived at the user side before the start of viewing, this means that the delivery of the entire title has been completed at an arbitrary time up to the guaranteed time. Means that.

(2) As long as the delivery is completed by the guaranteed time, the delivery of the title can be performed at an arbitrary time. Under this condition, the multiplicity of the user in one delivery is determined. Increase throughput. To that end, it is desirable to delay the delivery time as much as possible.

(3) Improve the average waiting time from when a viewing request is made to when the viewing becomes possible. For this purpose, it is desirable to reflect the difference in the popularity of each title in the scheduling.

[0018]

A moving picture title delivery scheduling method according to the present invention is directed to a video-on-demand system for directly delivering digital moving picture titles stored in a video server to a receiver at a user's home via a shared bandwidth network. A video title delivery scheduling method that can be used to determine the time at which delivery is completed and can be viewed at the time of a viewing request, and an initial setting waiting time according to the popularity of each title in order to reduce the average guaranteed waiting time. When a user requests title viewing,
Determines whether the requested title has already been requested by another user and is waiting for delivery, and if it is a new request that is not waiting for delivery, the title requested based on the initial setting waiting time Is calculated, and if there is a vacancy in the calculated reference arrangement position, the reference arrangement position is set as the delivery position of the requested title. If there is no vacancy in the reference arrangement position, the delivery position of the requested title is determined in various ways as described later.

The video title delivery scheduling device of the present invention is used in a video-on-demand system for directly delivering a digital video title stored in a video server to a receiver at a user's home via a shared bandwidth network, and the delivery is completed. A video title delivery scheduling device that can determine the time at which the user can view the video at the time of the viewing request, a means for providing an initial setting waiting time according to the degree of popularity of the title, Means for determining whether or not the title has already been requested by another user and is in a delivery waiting state; and, if the requested title is a newly requested title, based on the initial setting waiting time. Means for calculating the reference arrangement position, and the arrangement of the requested title based on the reference arrangement position. It has a position setting / changing means for determining the position.

[0020]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, a preferred embodiment of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing a configuration of a moving picture title delivery scheduling device according to an embodiment of the present invention. This video title delivery scheduling device 10
Is used in the video-on-demand system, and performs delivery scheduling when delivering the moving image title stored in the video server 20 to the user 30 in response to the request of the user 30. The scheduling is executed according to the video title delivery scheduling method. Here, a large number of users 30 share a large-capacity downlink (band-sharing large-capacity line 32) such as satellite communication or CATV. Then, prior to the start of viewing on the user 30 side,
The entire title (from the beginning to the end of the title) of which the user has made a viewing request among the digital video titles stored in the video server 30 is transferred from the video server 20 to each user by using the bandwidth sharing large capacity line 32. Delivery is made directly to the image receiving device at home.

In order to receive a viewing request from the user 30, each user 30 and the moving picture title delivery scheduling device 10 are connected by a narrow band line 31 such as an analog telephone line. In the moving picture title delivery scheduling device 10, the time at which the requested title can be viewed is determined at the time when the user 30 makes a viewing request. Also, when the moving image title delivery scheduling device 10 notifies the user 30 that the delivery has been completed), the narrow band line 31 is used.

Video title delivery scheduling device 1
0 is a request receiving unit 11 that receives a viewing request from the user 30 and transmits a response to the viewing request to the user 30, and a title requested by the user has already been requested by another user and is in a delivery waiting state. A delivery waiting determination unit 12 that determines whether or not the title is waiting, an initialization waiting time setting unit 13 that sets an initialization waiting time according to the popularity of the title for each title in order to reduce the average guaranteed waiting time, The initial setting waiting time storage unit 14 for holding the set initial setting waiting time and the result of the judgment by the delivery waiting judging unit 12 are stored in the initial setting waiting time storing unit 14 when the request is for a new title. A reference arrangement position calculation unit 15 for calculating a reference arrangement position of the title based on the data of the initialized waiting time thus set, and a reference arrangement position based on the calculated reference arrangement position. Can the arrangement position setting / changing unit 16 to set the position of the title (delivery position), position stored to store the location of each title of the delivery waiting portion 17
And

The delivery waiting judgment unit 12 is provided with the arrangement position storage unit 1
By referring to the data of the arrangement position of each title stored in 7, it is determined whether the title requested by the user 30 for viewing has been requested by another user and is already waiting for delivery. As a result of the determination, if the request is a new request, the reference arrangement position calculating unit 15
Is calculated, but if the request is an existing request, the delivery waiting determination unit 12 determines
Is transferred to the request receiving unit 11 with respect to the time at which the user can view the title requested by the user. Similarly, when the arrangement position setting / change unit 16 sets the arrangement position (delivery position) of the title requested by the user,
The information about the time at which the title can be viewed is transferred to the request receiving unit 11. When the request receiving unit 11 receives, from the delivery waiting determination unit 12 or the arrangement position setting / change unit 16, information on the time at which the title requested by the user can be viewed, the request receiving unit 11 sets the time at which the viewing is possible at the viewing request. Is notified to the user 30 who issued the.

Next, a specific example of the processing in the arrangement position setting / change unit 16 will be described. As will be described later, the processing in the arrangement position setting / change unit 16, that is, the method of setting the arrangement position may be other than that described here.

When the reference arrangement position of the title is calculated by the reference arrangement position calculation unit 15 based on the user's viewing request for a title, the arrangement position setting / change unit 16 is stored in the arrangement position storage unit 17. With reference to the arrangement position of each title waiting for distribution, it is first determined whether or not the reference arrangement position is already filled with another title in a state where each title awaiting distribution is arranged. If the reference arrangement position is empty, it is determined as the arrangement position of the title, and the arrangement position storage unit 1
7 is set to that effect, and the process ends. On the other hand, if the reference arrangement position is not empty in the arrangement state stored in the arrangement position storage unit 17, it is determined whether or not there is an empty space in the arrangement state in the forward direction (a direction earlier in time). If it is determined that there is such a vacancy, another title already assigned is moved to the previous position, and the arrangement position of the title is set to its reference arrangement position. On the other hand, if there is no vacancy in the forward direction, a vacant delivery position is searched in the backward direction, and the arrangement position of the title is set. When the setting of the arrangement position of the title requested by the user in this manner is completed, the arrangement position setting / change unit 16 receives the information on the arrangement position of the title, that is, the information on the time when the title can be viewed. It is sent to the unit 11.

The video server 20 will be described. The video server 20 stores the titles stored in the title storage unit 21 that stores various moving image titles in digital form in the digital format and the arrangement information stored in the arrangement position storage unit 17 of the moving image title delivery scheduling device 10. And a distribution unit 22 for delivering the data to each user 30 via the shared bandwidth large capacity line 32. As described later, the initial setting waiting time is set by the initial setting waiting time setting unit 13 for each title stored in the title storage unit 21.

Hereinafter, the moving picture title delivery scheduling method according to the present invention will be described in more detail.
For the description here, the following assumptions are made.

(I) Assume that M movie titles are prepared in a video server, and the order of popularity is known. This premise is considered to be appropriate by utilizing the popularity of the movie at the movie theater when it was released and the results of prior research. Each movie title is labeled 1, 2,..., M in descending order of popularity. However, the selection probability that the user selects the title changes according to the combination of titles and the time zone / day of the week, and it is generally difficult to specify the selection probability.

(Ii) All titles have the same time length, and the time T required to deliver each title is considered as a time slot, and the following consideration is advanced in discrete time using this time slot as a unit. Further, it is assumed that K channels in a band sharing type network (specifically, CATV, communication satellite, etc.) can be used, and the time slots of each channel are synchronized. That is, it is assumed that a maximum of K titles are delivered for each T.

Initial setting waiting time When the user desires to view the title m (1 ≦ m ≦ M), if another user has already requested the same title and is waiting for delivery, a new setting is made as described above. No scheduling is required. If not, the title m is included in the delivery schedule. At this time, an initial setting waiting time ω _m according to the degree of popularity of the title is set for each title m in order to treat a popular title more preferentially than a lower title.

FIG. 2 shows titles 10, 7, 6, 7, 4,
An example of delivery scheduling in a case where requests for No. 1 occur in this order will be described. However, in the figure, the number of channels K is 1, and one title can be delivered in each time slot. Since the request other than the request for the fourth title 7 is a request for an unscheduled title, a new delivery is scheduled. However, in the conventional FIFO method, as shown in FIG. The title 7 is scheduled to be delivered in the order in which the requests are generated. On the other hand, in the scheduling method according to the present embodiment, as shown in FIG. 2B, the title is placed at the reference arrangement position of the time width W _m obtained from the initial setting waiting time ω _m set for each title. Of delivery slots are scheduled. Here, W _m is a discrete variable in units of time slots, and when the requested arrival time to title m is T _A and the next time slot start time is T _B ,

[0033]

(Equation 2)

Is calculated as follows. As shown in FIG.
After omega _m from the time the request is generated (A point) to the title m in order to enable viewing in (D point) it is required to have delivered the title m is completed at the latest time point C. Delivery scheduling position counted from the next time slot start time (B point) corresponds to W _m.

For a user who has newly requested the content m, scheduling is performed at such a position of W _m , and the time point C is notified to the user as a guaranteed viewable time. Since the delivery of the content m may be completed by the time point C, it may be delivered in an arbitrary time slot from the time point B to the time point C. However, the delivery is performed in a slot as late as possible from the above-mentioned main point (2). Is desirable, W _m
At the initial position. Already K to the position of the W _m
If titles are scheduled,
It is necessary to perform processing such as shifting the already arranged title, which will be described in the next bar. In the following, to consider how to set up the initial setup latency ω _m.

Since the popularity ranking of the M titles has been determined by the above assumption (i), it is desirable to set ω _m based on this ranking. In other words, it is expected that the average guaranteed waiting time will be reduced by setting ω _m to be smaller for titles that are more popular. Here, the title numbers are assigned in the order of popularity, which means that ω ₁ <ω ₂ <... <ω _M is set. There are countless setting methods that satisfy this, but in practice it is desirable to represent with as few parameters as possible. Also, the minimum value ω ₁ and the maximum value ω _{M of} ω _m
It is effective to allow the network operator to freely set the two.

Therefore, the following three formulas (p ₁ and p ₂ are used as parameters) are considered as setting equations that can easily determine ω _m .

(I) Linear: ω _m = p ₁ + p ₂ · m, (ii) Exponential form: ω _m = p ₁ · p ₂ ^m , (iii) Reciprocal form of Zipf function: ω _m = p ₁ · m ^p2 . Given ω ₁ and ω _M for each, the parameters p ₁ and p ₂
Is uniquely determined as follows.

(I) Linear:

[0040]

(Equation 3)

(Ii) Exponential form:

[0042]

(Equation 4)

(Iii) Reciprocal form of Zipf function:

[0044]

(Equation 5)

In the pre- delivery scheduling subsection, it has been described that for a request for a new title m (there is no other waiting user), an attempt is made to place the request in the time slot position W _m based on the initial setting waiting time ω _m . If the number of titles arranged at this time slot time is less than the number of channels K, scheduling can be performed at that position without any problem. However, when K titles have already been arranged, one of the following three methods is used.

[0046] (1) merely to place the title n the position of the W _m. To do so, it is necessary to move one of the other titles already placed, but in order to keep the viewable time guaranteed for the user who made the reservation,
It should be noted that late travel is not allowed, only early travel is allowed. If the next time slots W all until time slots of the K position of the _m title is located, the title m since there is no space to move is lost calls.

[0047] (2) Find the time slots with available from the position of W _m in the direction of the earlier time, to place the empty position is closest to W _m. If there is no free space, the call will be lost.

[0048] (3) Find the time slots with available from the position of W _m in the direction of the slow time, placing the empty position is closest to W _m. Since a vacancy is always found, there is no possibility of a call loss.

When the method (3) is used among the above three methods, it is expected that the scheduling position will be extended at a later time.
Both channel utilization may deteriorate. The remaining methods (1) and (2) are considered to be effective methods, respectively. However, the method of (1) that satisfies the purpose of providing an initial setting waiting time for each title, which was the original purpose, is considered. Hereinafter, it is used. However, if a call is lost due to full blockage, the method of (3)
Avoid call blocking. This is because it is considered that it is desirable for the user to be notified of the viewable time even if the waiting time is slightly longer than the desired title is lost.

When the above method (1) is used, one of the K titles already arranged is moved to the previous (cannot be moved backward) time slot. Become. When K titles are already arranged in the immediately preceding time slot, one of them is moved to the immediately preceding time slot. This operation is completed a finite number of times since there is always a free time slot unless it is completely closed. Here, it is necessary to determine which one of the K titles is to be moved, but it is assumed that the title arranged at the earliest time is selected.

FIG. 4 shows an example of scheduling when requests for titles 6 and 3 occur consecutively (the number of channels is three). In order to simplify the notation, the title arranged at a larger channel number (upper in the figure) is a title arranged at an older time among the titles arranged at the same time slot. And Although Figure 4 requests titles 6 when the arrangement state as shown in (a) is to occur, in this example the delivery position W ₆ calculated from the initial setup latency omega ₆ is a 5. In the third time slot from the next time slot to the next time slot, two titles are arranged, so there is still one free space. Therefore, by the method (1), the title 6 is arranged at the position of W ₆ , and the title 15 arranged at the oldest time among the already arranged titles 15, 12, and 9 is assigned to the immediately preceding time slot. Move. Similarly, the title 5 arranged at the oldest time in the immediately preceding slot is moved to the immediately preceding time slot. Since only two titles 19 and 8 are arranged here, the moving operation ends here. As a result, the arrangement state is as shown in FIG.

Next, although a request for title 3 has been issued, since the time slot from the next time slot to the time slot three ahead (W ₃ = 3) is completely closed, the method (1) cannot be used. Therefore, the arrangement position of the title 3 is searched by the method (3). A search time slots with available direction after the time slot position of the W _3, it can be seen that the sixth working time slot has a free only title 16 is arranged. As a result, as shown in FIG. 4C, title 3 is arranged in this time slot. The maximum number of titles in the waiting state is M. If a scheduling table having a capacity of M is prepared, a position where the title can be arranged is always found, so that there is no call loss.

Finally, the title delivery scheduling algorithm when the user u requests viewing of the title m at the time r (within the time slot n) will be summarized.

(I) First, it is checked whether or not the title m has already been requested and scheduled by another user. If scheduled, the delivery scheduled slot _nm is notified to the user u as the viewable time, and the process ends. If not, go to (ii).

(Ii) The reference arrangement position W _m of the title is

[0056]

(Equation 6)

This is calculated from: Here, T is the time length of the time slot, and t _n is the start time of the time slot n.

(Iii) Next time slot n + 1 to n + W
_It is checked whether at least one of the _m time slots has the number of arranged titles less than K. If there is at least one vacancy, the process proceeds to (iv) with r = n + W _m and s = m. If there is no empty space, r = n + W _m +1 is set, and the process proceeds to (vi).

(Iv) If the number of titles arranged in the time slot r is less than K, the title s is arranged in one of the available channels in the time slot r, and the processing ends. When K titles are arranged, the process proceeds to (v).

(V) The title arranged at the oldest time is extracted from the K titles arranged in the time slot r, and the title s is arranged in the empty space. Then, the extracted title is newly set to s. The process proceeds to (iv) with r = r-1.

(Vi) When the number of titles arranged in the time slot r is K, (vi) is repeated with r = r + 1. If less than K, proceed to (vii).

(Vii) Arrange the title m in the time slot r and finish.

[0063]

[Simulation Result] Next, a simulation result performed for the above-described embodiment of the present invention will be described.

Simulation conditions The reference set value of the number of channels K is 32, and the delivery time T of each title is 1200 seconds (the time required to deliver a title having a required bandwidth of 5 Mbps and a length of 120 minutes on a 30 Mbps line). I do. Suppose that the user requests viewing according to the Poisson process, and the requested generation rate λ from the entire user group is determined by the system load ρ

[0065]

(Equation 7)

Is determined. Here, ρ is given as a steady state and its reference set value is given as 20.0. As described above, since all users who have requested the same title can provide the title in one delivery (batch effect), the operation is stable even when the load ρ exceeds 1.0. It is assumed that the user who has requested viewing selects a title with a probability according to the Zipf distribution of parameter 0.271. The number of titles M that can be selected is that the average number of titles provided by the rental video store is 4676 (Yoshiaki Tanaka, Sotaro Kato, “VOD service price and traffic volume prediction,” IEICE Technical Report, SSE95- 123), desirably several hundreds to several thousand. Therefore, the reference set value of M is set to 2000. In the present invention, the initial setting waiting time ω _m
Is set by the three methods described in the section of “Initial setting waiting time” above. At this time, two necessary values, that is, reference setting values of ω ₁ and ω _M are given at 3600 seconds (1 hour) and 129600 seconds (36 hours), respectively. At this time, ω is set by the three setting methods described in the section “Initial setting waiting time”.
_The result of setting _m is shown in FIG. In FIG. 5, the horizontal axis is
The index number m of the video title, that is, the title number of each title labeled 1, 2,... In descending order of popularity. Table 1 summarizes reference setting values of various parameters.

[0067]

[Table 1]

Basic Characteristics for Each Title Here, by examining the basic characteristics for each title, it is confirmed that the method of the present invention achieves differentiation according to the popularity of the title through the initialization waiting time. A simulation was performed under the conditions shown in Table 1.

FIG. 6 shows an average notification (guarantee) for each title.
It is a graph which shows waiting time. Since the title viewing request arrives at a constant rate, a value that is half of the set waiting time at the time of new scheduling is the average value of the guaranteed waiting time notified from the network when the user requests viewing. ω _m to Zi
When set in the inverse form of the pf function, the average notification latency, since it has become roughly half the value of omega _m shown in FIG. 5, that is can be placed in a position of approximately omega _m when a new scheduling I understand. In contrast, the other two setting methods (linear and exponential), which is considerably greater than half the value of _m average notification delay of popular titles (title number is small) is omega. this is,
In the case of the linear type and the exponential type, since ω _m increases at a slow speed due to the increase of the title number, it is a cause that the title is arranged in the reference position at the position where the titles are completely packed.
As a result, relatively popular titles (1 in the linear case)
At the time of the reference arrangement of 850, exponential type, 1−1650), the backward search (the method of (3) in the above “delivery scheduling”) is often used due to the full blockage, and the initial setting waiting time ω The arrangement at the position of _m becomes difficult.

Although it is important to reduce the overall average guaranteed waiting time, it is also important to reduce the guaranteed waiting time of particularly popular titles. Therefore, as a method of setting the initial setting waiting time, the Zipf function is used. Is desirable.

Performance Comparison with FIFO Method Here, in order to confirm that the method according to the present invention has the effectiveness over the conventional FIFO method, the average notification waiting time of all titles and the best 10 titles of popular titles were compared. Compare the two characteristics with respect to the average notification waiting time.
The initialization latency in the method according to the invention is Zipf
It was set using the reciprocal form of the function. Based on the setting values shown in Table 1, the title number M, the number of channels K, system load [rho, the characteristics in the case of changing the respective maximum initial setup latency omega _M, shown in FIGS. 7 to 14.

Since all users who watch the same title are batched, the waiting time greatly depends on the number M of titles. This is because as the number of titles increases, the title requests of the users are dispersed, and the number of users bundled by batching decreases. Therefore, as shown in FIG. 7 and FIG. 8, as the number of titles increases, the possibility of performing full search at the time of new scheduling and performing a backward search increases, and the result of the method of the present invention becomes smaller than the result of arrangement by the conventional FIFO method. As a result, the average characteristic difference between the two disappears. Conversely, in an area where the number of titles is small, the characteristics are improved by the FIFO method in which the number of broadcast users is increased and the substantial load is reduced. And the average characteristic shown in FIG. 7 shows that the FIFO method has better results. However, for popular titles, as shown in FIG.
The method of the present invention is still better. In other areas, the method of the present invention shows better properties both for average properties for all titles and properties for popular titles.

The characteristics with respect to the number of channels K (FIGS. 9 and 1)
Regarding 0), the same can be said for the characteristics with respect to the number of titles. That is, when the number of channels is small, the substantial load increases, so that the difference between the two methods cannot be seen. Conversely, when the number of channels is sufficiently large, the FIFO method shows better characteristics in terms of average characteristics, and the method of the present invention shows better characteristics in respect of popular titles. In other areas, it can be seen that the method of the present invention is overall superior.

When the system load ρ is low, as shown in FIG. It can be seen that in the method of the present invention, the average notification waiting time deteriorates because the channel utilization efficiency decreases. Nevertheless, as shown in FIG. 12, for popular titles, the method of the present invention is all better in the load area.

As the maximum initial setting waiting time ω _M is increased, the total blocking state is reduced and the waiting time of the popular title is improved. As a result, as shown in FIG. 13, the overall average waiting time can be improved. Understand. However, when ω _M is further increased, the waiting time for the unpopular title increases, and the channel utilization rate decreases. On the other hand, as for the characteristics of popular titles, as shown in FIG. 14, an increase in ω _M leads to an improvement in characteristics, but it can be seen that the effect eventually disappears.

[0076]

As described above, according to the present invention, an initial setting waiting time is provided according to the degree of popularity of each title, and when a user requests a new title to be viewed, the request is made based on the initial setting waiting time. When calculating the reference placement position of the title, and setting the reference placement position as the delivery position of the requested title when there is a space in the calculated reference placement position, when scheduling the delivery of the video title, It is possible to improve the overall throughput and improve the overall waiting time characteristics, while enabling each user to view the title requested by that user at the time guaranteed for each user. effective.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating a configuration of a video title delivery scheduling device according to an embodiment of the present invention.

FIG. 2A is a diagram illustrating delivery scheduling according to a conventional FIFO method, and FIG. 2B is a diagram illustrating delivery scheduling based on the present invention.

3 is a diagram for explaining a reference position W _m.

4A is a diagram showing a scheduling state when a title 6 is requested, and FIG. 4B is a diagram showing a scheduling state when a title 3 is requested;
(c) is a diagram showing a scheduling state after accepting title 6 and title 3 requests.

FIG. 5 is a graph showing a distribution of an initial setting waiting time for each title.

FIG. 6 is a graph showing an average notification (guaranteed) waiting time for each title.

FIG. 7 is a graph showing a change in average notification waiting time according to the number of titles.

FIG. 8 is a graph showing a change in average notification waiting time of the top 10 popular titles according to the number of titles.

FIG. 9 is a graph showing a change in an average notification waiting time according to the number of channels.

FIG. 10 is a graph showing a change in average notification waiting time of the top 10 popular titles according to the number of channels.

FIG. 11 is a graph showing a change in average notification waiting time according to a system load;

FIG. 12 is a graph showing changes in the average notification waiting time of the top 10 popular titles according to the system load.

FIG. 13 is a graph showing a change in an average notification waiting time according to a maximum initial setting waiting time.

FIG. 14: Top 1 popularity according to maximum initial setting waiting time
It is a graph which shows the change of the average notification waiting time of 0 titles.

[Explanation of symbols]

 Reference Signs List 10 Video title delivery scheduling device 11 Request receiving unit 12 Delivery waiting judgment unit 13 Initial setting waiting time setting unit 14 Initial setting waiting time storage unit 15 Reference arrangement position calculating unit 16 Arrangement position setting / change unit 17 Arrangement position storage unit 20 Video server 21 Title storage unit 22 Distribution unit 30 User 31 Narrow band line 32 Bandwidth sharing type large capacity line

Claims (12)

[Claims] 1. A video-on-demand system for directly distributing digital video titles stored in a video server to a user's home receiving device via a shared bandwidth network, at which time delivery is completed and viewing is possible. Is a video title delivery scheduling method that can determine when a viewing request is made, wherein an initial setting waiting time is provided according to the popularity of each title, and when a title viewing request is made from a user, the requested title is already requested by another user. To determine whether or not the request is waiting for delivery, and if the request is not a new request for delivery, calculate the reference arrangement position of the requested title based on the initial setting waiting time. If there is a vacancy in the reference placement position, the reference placement position is set as the delivery position of the requested title. Set, the video title delivery scheduling method. 2. If there is no vacancy in the calculated reference arrangement position, it is searched whether there is an empty delivery position from the reference arrangement position in the forward direction. The delivery position of a title which is behind the empty delivery position and is already waiting for delivery is moved to the empty delivery position, whereby the reference arrangement position is determined as the delivery position of the requested title. 2. The video title delivery scheduling method according to 1. 3. A position to be a delivery position of each title is defined as a time slot. If there is no vacancy in the reference arrangement position, one of the reference arrangement positions starts from a time slot next to the current time slot. It is determined whether there is one or more empty spaces until the previous time slot, and if there is an empty space, the title assigned to the oldest time among the titles already assigned to the reference arrangement position is determined. The title is moved to the previous time slot, the title requested by the user is assigned to the empty space, and thereafter, the movement of the title is repeated in the forward direction until all the titles are accommodated, so that there is no empty space. 2. The moving picture title delivery scheduling method according to claim 1, wherein in that case, the title requested by the user is regarded as a call loss. 4. A position to be a delivery position of each title is defined as a time slot. If there is no vacancy in the reference arrangement position, one of the reference arrangement positions starts from the time slot next to the current time slot. It is determined whether there is one or more empty spaces until the previous time slot, and if there is an empty space, the title assigned to the oldest time among the titles already assigned to the reference arrangement position is determined. The title is moved to the previous time slot, the title requested by the user is assigned to the empty space, and thereafter, the movement of the title is repeated in the forward direction until all the titles are accommodated, so that there is no empty space. In this case, a search is made for an empty slot in the backward direction of the reference arrangement position, and the title requested by the user is assigned to an empty slot closest to the reference arrangement position. The moving picture title delivery scheduling method according to claim 1. 5. If there is no vacancy in the calculated reference arrangement position, it is searched for an empty delivery position from the reference arrangement position in the forward direction. The moving picture title delivery scheduling method according to claim 1, wherein the delivery position is determined as a delivery position of the requested title, and if there is no available delivery position, the requested title is regarded as a call loss. 6. When there is no vacancy in the calculated reference arrangement position, it is searched whether there is an empty delivery position from the reference arrangement position in the forward direction. The delivery position is determined as the delivery position of the requested title, and if there is no available delivery position, the available delivery position is searched for in the backward direction of the reference arrangement position, and the available delivery position closest to the reference arrangement position is found. 2. The moving picture title delivery scheduling method according to claim 1, wherein a title requested by the user is assigned. 7. An initial setting waiting time for each title is set based on the premise that the popularity ranking of titles is known, so that a title having a higher popularity has a shorter initial setting waiting time. 7. The moving picture title delivery scheduling method according to any one of 6. 8. The default wait time for all titles is uniquely determined by providing an initial wait time for the most popular title and an initial wait time for the least popular title. Video title delivery scheduling method. 9. The moving picture title delivery scheduling method according to claim 8, wherein one of linear, exponential, and reciprocal forms is used as a specific function form of the initial setting waiting time determined for each title. 10. The method according to claim 1, wherein the preset waiting time of the continuous time amount is converted into a reference arrangement position of a discrete time amount required for scheduling based on the viewing request generation time and the next slot start time. 8. The moving picture title delivery scheduling method according to any one of 8. 11. A video-on-demand system for directly distributing digital video titles stored in a video server to an image receiving device at a user's home via a shared bandwidth network, at which time delivery is completed and viewing is possible. Means for providing an initial setting waiting time in accordance with the degree of popularity of a title, and a request for a title already requested by another user at the time of a title viewing request from a user. Means for determining whether the requested title is in a delivery waiting state, and means for calculating a reference arrangement position based on the initial setting waiting time when the requested title is a newly requested title. Setting / changing an arrangement position for determining a delivery position of the requested title based on the reference arrangement position; Video title delivery scheduling device including a stage, a. 12. An arrangement position setting / changing means, when the reference arrangement position is already occupied by another title, judges whether or not there is a space in the forward direction from the reference arrangement position, and there is a space. The method according to claim 11, further comprising: moving another title already allocated to the empty position in the forward direction when it is determined to be empty; and searching for an empty delivery position in the backward direction when it is determined that there is no empty space. Video title delivery scheduling device.