A Scheduling Method of Division-Based Broadcasting Considering Delivery Cycle

Abstract

Due to the recent popularization of multimedia broadcasting such as terrestrial digital TV broadcasting and one-segment broadcasting, the technology for broadcasting continuous media data such as audio and video has become important to users. Although broadcast delivery allows many clients to receive data with a certain bandwidth, clients have to wait between the request for data and the start of delivery. In order to reduce the waiting time, division-based broadcasting, in which the server divides data into several segments and delivers them on multiple channels, has been proposed. In addition, many scheduling methods set the timing of delivering each segment in division-based broadcasting. The Wrapped Harmonic Broadcasting (WHB) method, which is a conventional scheduling method, reduces the waiting time by setting a delivery schedule that shortens the delivery cycle of data using multiple channels. However, the WHB method increases the waiting time due to the long period during which segments are not scheduled on the channel. In this paper, we propose a scheduling method that considers the delivery cycle of video data in division-based broadcasting. Our method schedules more segments to be delivered than the conventional WHB method based on the available bandwidth and consumption rate. In our simulation evaluation assuming an actual network environment, waiting time with the proposed method is reduced by about 46.5$\%$ compared to the WHB method when the number of segments is 30, the playback rate is 5.0 Mbps, the available bandwidth is 15 Mbps, and the playing time is 180 s.

1 Introduction

Due to the recent popularization of online video streaming on the Internet, users are demanding environments in which they can watch multiple videos simultaneously  [1]. There are two types of delivery methods for video data: on-demand delivery and broadcast delivery. In on-demand delivery, the server allocates the bandwidth and delivers the video based on the client’s request. Therefore, as the number of clients requesting video at the same time increases, the available bandwidth of the server increases proportionally. On the other hand, in broadcasting, although the server can deliver the same video repeatedly to clients with a certain bandwidth, the clients must wait until the requested data are delivered.

In order to reduce waiting time, we proposed a division-based broadcasting that divides video data into multiple segments and delivers them using multiple channels. In division-based broadcasting, many scheduling methods have been proposed to reduce the waiting time for receiving data  [2, 3].

Conventional scheduling methods reduce waiting time by setting a delivery schedule that shortens the delivery cycle of data using multiple channels. However, these methods increases waiting time due to the long period when segments are not scheduled on the channel.

In this paper, we propose a scheduling method that considers the delivery cycle of video data in division-based broadcasting. Our method schedules more segments to be delivered than the conventional method based on the available bandwidth and consumption rate.

The remainder of this paper is organized as follows. In Sect. 2, we explain division-based broadcasting for multiple videos. We introduce related works in Sect. 3. We explain the conventional scheduling method considering the cycle in Sect. 4. We explain our proposed method in Sect. 5 and evaluate it in Sect. 6. Finally, we conclude our paper in Sect. 7.

2 Division-Based Broadcasting

IP networks have two main types of delivery systems: Video on Demand (VoD) and broadcasting. In broadcasting systems such as multicast and broadcast, the server delivers the same content data to many clients using a constant bandwidth. Although the server can reduce the network load and the required bandwidth, clients have to wait until their desired data are broadcast.

VoD systems are used for delivering many kinds of movies. Clients can watch movies from on-demand services such as Netflix  [4] and Amazon Prime Video  [5]. In VoD systems, the server requires adequate bandwidth and starts delivering data sequentially based on client requests. Although clients can get their desired data immediately, the server’s load increases as the number of clients increases.

In broadcasting systems, the server concurrently delivers data to many clients. In general broadcasting systems, since the server broadcasts data repetitively, clients must wait until their desired data are broadcast. Accordingly, various types of methods for broadcasting content data have been studied  [6,7,8,9]. In content data broadcasting, clients must play the data without interruption until their end. By dividing the data into several segments and scheduling them so that clients receive one segment before playing the next, many methods can reduce the waiting time.

In division-based broadcasting systems, since the waiting time is proportional to the data size of the preceding segment, we can reduce the waiting time by shortening the data size of the preceding segments. However, when the rate of the preceding segments is small, the client can not start the segment to be played next until it finishes playing the segment that it has already received. In this case, an interruption occurs while playing the data and the waiting time increases. Therefore, we need to consider the data size of the preceding segment. Several methods employ division-based broadcasting that reduces waiting time by dividing the data into several segments and frequently broadcasting precedent segments.

Fig. 1.

Broadcast schedule under FB method

In the conventional Fast Broadcasting (FB) method  [10], the broadcast bandwidth is divided into several channels. The broadcast schedule under the FB method is shown in Fig. 1. The bandwidth for each channel is equivalent to the consumption rate. In this case, the server uses three channels. In addition, the data are divided into three segments: $S_{1}$, $S_{2}$, and $S_{3}$. When the total playing time is seven min., the playing time of $S_{1}$ is calculated to be one min., $S_{2}$ is two min., and $S_{3}$ is four min. In Fig. 1, the server broadcasts $S_{i}$ ($i=1, 2, 3$) by broadcast channel $C_{i}$ repetitively as shown. Clients can store the broadcasted segments in their buffers while playing the data and play all segments after receiving them. When clients finish playing $S_{1}$, they have also finished receiving $S_{2}$ and can play $S_{2}$ continuously. In addition, when they have finished playing $S_{2}$, they have also finished receiving $S_{3}$ and can play $S_{3}$ continuously. Since clients can receive broadcasted segments midstream, the waiting time is the same as the time needed to receive only $S_{1}$ and the average waiting time is one min.

3 Related Works

In Optimized Periodic Broadcast (OPB)  [11], each bit of data is separated into two parts. The server uses several broadcast channels and distributes each segment on each channel. When clients finish receiving the precedent parts of the content, they begin receiving the remaining portions. Since clients can get the subsegment data in advance, waiting times can be reduced. However, the bandwidth increases as the amount of content increases.

In Heterogeneous Receiver-Oriented Broadcasting (HeRO) [12], the server divides the data into K segments. Let J be the data size for the first segment. The data sizes for the segments are $J,~2J,~2^{2}J, ...,~2^{K-1}J$. The server broadcasts them using K channels. However, since the data size of the $K^{th}$ channel becomes half of the data, clients may experience waiting times with interruptions.

The Generalized Fibonacci Broadcasting (GFB) method [13] creates a broadcast schedule using the Fibonacci sequence. When the data size ratios in the first and second segments are 1 and 2, the GFB method sets the ratio of the data size in the nth segment ($n \ge 3$) to $n-2 + n-1$ and makes schedules for clients with several types of available bandwidth. Clients with small available bandwidths can reduce their waiting time.

The Catch and Rest (CAR) method  [14] combines scheduling using the replicated channels in HeRO with scheduling that divides segments in the GFB method. Clients who have different bandwidth and buffer sizes use the CAR method. Clients with small buffer size and available bandwidth can reduce their waiting times by considering cases without receiving segments.

In Layered Internet Video Engineering (LIVE)  [15], clients feedback virtual congestion information to the server to support both bandwidth sharing and transient loss protection. LIVE can minimize the total distortion of all participating video streams and maximize their overall quality. Several researches studied reliable broadcasting in wireless networks with packet loss probability  [16, 17].

Other scheduling methods have investigated packet loss [18], the receiving performance of clients [19, 20], and the variable bit rate (VBR) [21, 22]. When a server delivers data to clients using bandwidth that is sufficiently larger than the consumption rate and plays it with buffering, they can reduce their waiting time. However, clients must have high performance memory and a processor. We need to evaluate a system in a situation where clients with various computer capabilities can simultaneously use division-based broadcasting with a scheduling method.

4 Conventional Scheduling Method Considering Delivery Cycle

The Wrapped Harmonic Broadcasting (WHB) method  [23], which is a conventional scheduling method, reduces the waiting time by setting a delivery schedule that shortens the delivery cycle using multiple channels. In this method, when the video data is divided into $S_{i}$ segments ($i = 1, 2, \cdots , n$), the ratio of data size in each segment is 1 : $\frac{1}{2}$ : $\cdots$ : $\frac{1}{n}$. The server determines the delivery cycle based on the data size of $S_{1}$ and schedules segments in the order of $S_{1}$, $S_{2}$, $\cdots$, and $S_{n}$. The available bandwidth of each channel is equal to the consumption rate. When the data size of the segment to be scheduled is less than $S_{i}$, the server sets up a new channel and schedules $S_{i}$.

An example of a WHB delivery schedule is shown in Fig. 2. The number of segments is 6, the playing time is 60 sec., and the consumption rate is 5.0 Mbps. First, the server divides the data size of $S_{1}$, $S_{2}$, $\cdots$, $S_{6}$ so that the ratio of the data size of $S_{1}$, $S_{2}$, $\cdots$, and $S_{6}$ is 1 : $\frac{1}{2}$ : $\cdots$ : $\frac{1}{6}$. Since the server has no space for scheduling $S_{2}$ to $C_{1}$, it sets a new channel $C_{2}$ and schedules $S_{2}$. Similarly, after scheduling $S_{3}$ to $C_{2}$, it schedules $S_{4}$ and $S_{5}$ to a new channel $C_{3}$ and $S_{6}$ to $C_{2}$, respectively. In this case, the necessary bandwidth is $5.0 \times 3 = 15$ Mbps. The waiting time is the same as the broadcast cycle of $S_{1}$ and is $60\times \frac{120}{294} \simeq 24.5$ s.

Fig. 2.

Example of WHB method

In the WHB method, the server does not schedule for 13.5 s in $C_{3}$. The proposed method can further reduce the broadcast cycle and waiting time by scheduling the segments during this time period.

5 Proposed Method

In this paper, we propose a scheduling method that considers the delivery cycle of video data in division-based broadcasting. The proposed method schedules more segments to be delivered than the conventional WHB method based on the available bandwidth and consumption rate.

5.1 Assumed Environment

The environment for division-based broadcasting assumed in this paper is as follows:

• The available bandwidth of each channel is equal to the consumption rate.

• The server can schedule multiple segments of video data on each channel.

• The server can broadcast video data from multiple channels simultaneously.

• The client can receive from all channels simultaneously.

• The client has an enough buffer to store video data.

5.2 Scheduling Procedure

The scheduling procedure of our proposed method is:

• 1. Based on the available bandwidth B and consumption rate r, the number of available channels m is calculated by

  $$\begin{aligned} m = \lfloor \frac{B}{r} \rfloor . \end{aligned}$$

• 2. The number of segments n in the video data $S_{i}$ is calculated using the following conditions:

  $$\begin{aligned} \sum ^{n}_{i=1}\frac{1}{i} \le m~~~and~~~ \sum ^{n+1}_{i=1}\frac{1}{i} > m. \end{aligned}$$

• 3. The server divides the data size of $S_{1}$, $S_{2}$, $\cdots$, $S_{n}$ so that the ratio of the data size of $S_{1}$, $S_{2}$, $\cdots$, $S_{n}$ is 1 : $\frac{1}{2}$ : $\cdots$ : $\frac{1}{n}$.

• 4. The server calculates the delivery cycle T of $S_{1}$ and schedules $S_{1}$ to $C_{1}$.

• 5. For scheduling of $S_{2}$, $\cdots$, and $S_{n}$, when the data size that can be scheduled by $C_{j}$ is less than $S_{i}$, the server creates new channel $C_{j+1}$ and schedules it.

• 6. The server repeats the steps until all segments are scheduled.

Fig. 3.

Example of broadcast schedule under proposed method

5.3 Implementation

Figure 3 shows an example of scheduling under the proposed method.

The available bandwidth is 15 Mbps, the consumption rate is 5.0 Mbps, and the playing time is 30 s. In step 1, the server calculates the number of channels as $m = \lfloor \frac{15}{5.0} \rfloor$ = 3. In step 2, the server calculates 10 as n, which is N with $\sum ^{n}_{i=1}\frac{1}{i} \le m$ and N with $\sum ^{n+1}_{i=1}\frac{1}{i} > m$. In step 3, the server divides the segment so that the ratio of the data size of $S_{1}$, $S_{2}$, $\cdots$, $S_{10}$ is 1 : $\frac{1}{2}$ : $\cdots$ : $\frac{1}{10}$. In step 4, the server calculates the delivery cycle $T = 20.5$ of $S_{1}$ and schedules $S_{1}$ to $C_{1}$. In step 5, for the scheduling of $S_{i}$ $(i = 2, \cdots , 10)$, the server schedules $S_{i}$ to $C_{3}$ if the data size that can be scheduled in $C_{2}$ is less than $S_{i}$. In Fig. 3, after scheduling $S_{2}$, $\cdots$, and $S_{5}$ to $C_{3}$, the server schedules $S_{6}$ to $C_{2}$ because the data size for scheduling in $C_{2}$ exceeds $S_{6}$. Finally, the server schedules $S_{7}$, $\cdots$, and $S_{10}$ to $C_{3}$.

In Fig. 3, the waiting time under the proposed method is 20.5 s and 24.5 s under the WHB method. Therefore, the waiting time with our proposed method is reduced by about 16.3$\%$ compared to the WHB method.

6 Evaluation

We evaluated the performance of the proposed method using computer simulations. In the evaluation, we compared the waiting time of the proposed method and the WHB method based on the change in the playing time of the video data.

Fig. 4.

Average waiting time and playing time

6.1 Waiting Time and Playing Time

We evaluate the waiting time as the playing time changes. The evaluation result is shown in Fig. 4. The horizontal axis is the playing time and the vertical axis is the waiting time. The number of segments is 30, the consumption rate is 5.0 Mbps, and the available bandwidth is 15 Mbps.

In Fig. 4, when the broadcast cycle increases by lengthening the playing time, the waiting time is lengthened. In addition, the waiting time under the proposed method is reduced compared to the WHB method. The proposed method reduces the broadcast cycle by scheduling more segments and shortens the waiting time.

Since the proposed method schedules many segments in the time period when the WHB method is not scheduled, we can reduce the number of channels. For example, when the playing time is 180 s, the waiting time under the proposed method is 13.0 s and that under the WHB method is 24.3 s. Therefore, we can reduce the waiting time under the proposed method by 46.5$\%$ compared with the WHB method.

7 Conclusion

In this paper, we proposed a scheduling method considering the delivery cycle of video data in division-based broadcasting. The proposed method schedules more segments to be delivered than the conventional WHB method based on the available bandwidth and consumption rate. In our simulation evaluation assuming an actual network environment, the waiting time of the proposed method was reduced by about 46.5$\%$ compared with the WHB method when the number of segments was 30, the playback rate was 5.0 Mbps, the available bandwidth was 15 Mbps, and the playing time was 180 s.

In the future, we will propose and evaluate a scheduling method that considers the division-based broadcasting of multiple videos.