A Seamless Broadcasting Scheme with Live Video Support

Abstract

Broadcasting schemes, such as the fast broadcasting and harmonic broadcasting schemes, significantly reduce the bandwidth requirement of video-on-demand services. In the real world, some history events are very hot. For example, every year in March, thousands of people connect to Internet to watch the live show of Oscar Night. Such actions easily cause the networks contested. However, the schemes mentioned previously cannot alleviate the problem because they do not support live broadcasting. In this paper, we analyze the requirements for transferring live videos. Based on the requirements, a time skewing approach is proposed to enable the broadcasting schemes to support live broadcasting. However, the improved schemes require extra bandwidth for live broadcasting once the length of live shows exceeds the default. Accordingly, we proposed a scalable binomial broadcasting scheme to transfer live videos using constant bandwidth by increasing clients' waiting time. When the scheme finds that the length of a video exceeds the default, it doubles the length of to-be-played segments and then its required bandwidth is constant.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Zeng-Yuan Yang 1 and Yi-Ming Chen 2 and Li-Ming Tseng 1

Recommended by Hsiang-Fu Yu

1, Department of Computer Science and Information Engineering, National Central University, Jhongli 32001, Taiwan
2, Department of Information Management, National Central University, Jhongli 32001, Taiwan

Received 30 January 2012; Accepted 9 February 2012

1. Introduction

With the growth of broadband networks, the video-on-demand (VOD) [1] becomes realistic. Many studies start investigating VOD. One of important areas is to explore how to distribute the top ten or twenty so-called hot videos more efficiently. Broadcasting is one of the promising solutions. It transfers each video according to a fixed schedule and consumes constant bandwidth regardless of the presence or absence of requests for the video. That is, the system's bandwidth requirement is independent of the number of users watching a given video. A basic broadcasting scheme is the batch scheme [2], which postpones the users' requests for a certain amount of time and serves these requests in batch so that its bandwidth consumption is reduced. However, the batch scheme still requires quite large bandwidth for a hot video. For example, given a video of 120 minutes, if the maximum clients' waiting time equals 10 minutes, the required bandwidth is 12 b , where b is the video playout rate.

Many broadcasting schemes were proposed to further reduce the bandwidth requirement by using a set-top box (STB) at the client end. The schemes include the fast broadcasting (FB) [3, 4], pagoda broadcasting (PB) [5], new pagoda broadcasting (NPB) [5], recursive-frequency splitting (RFS) [6], staircase broadcasting (SB) [7], and harmonic broadcasting (HB) [8, 9] schemes, which divide a video into multiple segments and distribute them through several independent data channels. As well, these schemes require the STB to receive the segments from the channels when users start watching the video. The schemes substantially reduce the bandwidth requirements for hot videos. For example, if a video server allocates 4 video channels to transmit a 120-minute video by FB, then its maximum waiting time is merely 8 minutes. The FB scheme, in comparison with the batch scheme, reduces the bandwidth requirements and waiting time remarkably.

In the real world, some history events are very hot. For example, every year in March, many people connect to Internet to watch the live show of Oscar Night. Such actions easily cause the networks congested. However, the schemes, such as PB, NPB, SB, RFS, and HB, cannot broadcast live programs to alleviate the congestion. In order to overcome this obstacle, we analyzed the requirements for live broadcasting and proposed an approach, called time skewing, to enabling these schemes to distribute live shows. However, the improved schemes require extra bandwidth for live broadcasting once the length of live shows exceeds the default. Accordingly, a scalable binomial broadcasting scheme was proposed to demonstrate how to transfer live videos at the constant bandwidth regardless of video length.

The remainder of the paper is as follows. Section 2 analyzes the requirements of live broadcasting. This section also introduces the time skewing and the scalable binomial broadcasting scheme. An analysis and comparison is presented in Section 3. Finally, we make a brief conclusion in Section 4.

2. The Live Broadcasting Schemes

2.1. Background

This work briefly introduces the FB and HB first. Suppose that there is a video with length L (e.g., 120 minutes). The consumption rate of the video is b (e.g., 10 Mbps). The size of the video is S=L*b (e.g., 9 Gbytes). Suppose that the desired viewer's waiting time is less than l=L/N , where N is a positive integer. Both schemes involve the following steps.

(1) The video is equally divided into N segments. Suppose that _Si is the i th segment of the video. The concatenation (...) of all the segments, in the order of increasing segment numbers, constitutes the whole video, S=_S1 *_S2 *...*_SN .

(2) On the server side, the FB and HB schemes involve the following steps, respectively.

(a) For FB, there exists an integer k such that ^∑i=0k-12i <N...4;^∑i=0k2i . The server then periodically transfers segments _S²ⁱ to _{S²ⁱ⁺¹ -1} on channel _Ci , where 0...4;i...4;k , as shown in Figure 1. Hence, the total bandwidth allocated for the video is B=(k+1)*b .

(b) For HB, the server further equally divides segment _Si into i subsegments {_S1,i ,_S2,i ,...,_Si,i } . The subsegments of segment _Si are then broadcast on channel _Ci , where 1...4;i...4;N , as indicated in Figure 2. The bandwidth of _Ci thus equals b/i . The total bandwidth for the video equals B=^∑i=1N b/i=_HN *b , where _HN =^∑n=1N 1/n is the harmonic number of N .

(3) At the client end, suppose that there are enough buffer spaces to store data segments of a video. The steps to watch a video include the following.

(a) The client downloads the first data segment at the first occurrence on the first channel and then downloads other related data segments from other channels concurrently.

(b) Once finishing the downloading of the first segment, the client starts to play the video with its normal speed in the order of _S1 *_S2 *...*_SN .

(c) The client stops loading from channels when all data segments are received.

Figure 1: The FB scheme ( N=15 and k=3 ).

[figure omitted; refer to PDF]

Figure 2: The HB scheme ( N=4 ).

[figure omitted; refer to PDF]

2.2. The Requirements of Live Broadcasting

The section describes three important requirements for live broadcasting.

(R1) The data transfer rate of a channel must be less or equal to media production rate . In the case of live broadcasting, the new media are produced at constant speed such that the broadcasting schemes transferring data on a channel at a higher rate than media production rate are unable to support live broadcasting.

(R2) The broadcasting schemes cannot transmit the rearward and unavailable video segments in advance.

(R3) A live broadcasting scheme has to tolerate the varying length of live videos. In the real world, live shows often end either early or late, rarely on time. Most current broadcasting schemes [3-9] assume that the length of a video is known and fixed. In the case of early ending, such schemes simply free the allocated channels or repeat the last or blank video segments. Hence, the viewer watching the video is not affected. However, in the case of late ending, the schemes require additional bandwidth to handle the situation of program elongation. If the bandwidth is not available, the live broadcasting will be interrupted.

Being subject to the aforementioned requirements, we examine whether several proposed broadcasting schemes support live-program broadcasting. First, the pyramid broadcasting [10] scheme violates the requirement R1 because it uses multifold bandwidth channels to distribute video segments. Second, HB and SB conflict with the requirement R2 because they attempt to broadcast the nonexistent rearward video segments. Third, all of the mentioned broadcasting schemes cannot satisfy the requirement R3. They need to allocate additional channels to transfer the over length of a live video. Hence, they cannot distribute live videos using constant bandwidth. Accordingly, we proposed the time skewing to enable the schemes to satisfy the requirement R2. Furthermore, a scalable binomial broadcasting, based on FB, was proposed to demonstrate how to fulfill the requirement R3.

2.3. Time Skewing

Suppose that a broadcasting scheme schedules a subsegment _Si,j of segment _Sj onto channel _Ck in a constant cycle time _Tk . That is, subsegment _Si,j will appear once on channel _Ck every time _Tk . This work also assumes that in the beginning of broadcasting the video, segment _Sj is not available yet. Hence, the video server must put off the transmission of segment _Sj until the segment is available. Once receiving segment _Sj from a video source, such as a video camera, the video server transfers the deferred subsegment _Si,j via channel _Ck as it does for prerecorded videos. We call this postponement as time skewing. Figure 3 shows the differences between a regular broadcasting scheme on _Ck and a broadcasting scheme with the time skewing.

Figure 3: An illustration of time skewing.

[figure omitted; refer to PDF]

The time skewing is a general approach. If a broadcasting scheme cannot be rescheduled to fit time skewing, then it cannot support live broadcasting. In the paper, we merely demonstrate how HB takes the advantage of the approach to support live broadcasting. This is because HB was proved to require the minimum bandwidth under the same average waiting time in [9].

Live Harmonic Broadcasting

Suppose that the default length of a live video is L and the maximum user's waiting time is L/5 . According to HB, the video is equally divided into five segments, and the j th segment is further divided into j subsegments. With the time skewing, we put off the transmission of the posterior video segments until they are available. Figure 4 displays the scenario.

The channel _CL broadcasts the live video sequentially. Meanwhile, the other channels, that is, _C1 to _C5 , distribute the recorded segments of live program with time skewing. Whenever the entire live video is recorded, it is distributed over the HB scheme.

Figure 4: Live harmonic broadcasting scheme.

[figure omitted; refer to PDF]

2.4. The Scalable Binomial Broadcasting

The time skewing successfully allows the previous broadcasting schemes [3-9] to distribute live videos; however, it does not address the over-length problem. For example, in Figure 4, if the live program's length is longer than L , we must allocate an additional channel _C6 to transmit the excess part of the video. If the bandwidth is unavailable, the system has to stop video distribution. To overcome this obstacle, we develop a scalable binomial broadcasting that broadcasts a live video using constant bandwidth, regardless of its length.

The idea comes from the binomial relationship of FB [3]. The FB scheme reveals the binomial relationship between two conjunctive channels (Figure 5(a)). For channel _Ct+1 , the length of basic cycle unit ( ^{S2t[variant prime]} +^{S3t[variant prime]} ) is twice larger than that ( ^{St[variant prime]} ) of channel _Ct+0 . The binomial relationship is independent of the length of each video segment. Therefore, the server can broadcast a video of double length on the same number of channels by doubling the length of basic cycle unit (Figure 5(b)). Namely, by increasing the length of the cyclic unit on demand, the over-length part of a live video can be broadcast via preallocated channels.

The binomial relations on the fast broadcasting scheme.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

The work then presents how to seamlessly lively broadcast an over-length video at a constant bandwidth.

(1) Schedule the allocated channels by regular FB.

(2) When the last timeslot of a basic cycle unit on the highest numbered channel ( ^{S7t[variant prime]} on _Ct+2 in Figure 6(a)) is allocated and no addition channel is available for the live video, the elongation process of the basic cycle unit starts. The process doubles the length of basic cycle unit of each channel ( 2*^{St[variant prime]} on channel _Ct+0 ,4*^{St[variant prime]} on channel _Ct+1 , and 8*^{St[variant prime]} on channel _Ct+2 ). As well, the starting segment ^{St+i[variant prime]} =^{Sw[variant prime]} of basic cycle unit on each channel _Ct+i is derived based on the following formula: [figure omitted; refer to PDF] where k is the times which the elongation process is applied to. (As shown in Figure 6(b), the starting segments of channel _Ct , _Ct+1 , and _Ct+2 are ^{S1t[variant prime]} , ^{S3t[variant prime]} , and ^{S7t[variant prime]} , resp.).

(3) If the starting segment ^{Sw[variant prime]} has been broadcasted via this channel, the VOD server scans backward one by one till to the first occurrence of ^{Sw[variant prime]} and mark it as a new run of broadcasting cycle.

(4) If a new data cycle has been broadcasted completely and the live video is not over yet, then the video server jumps back to Step 2 and begins a new elongation process (Figure 6(c)). Otherwise, the video server cyclically broadcasts the double length of basic cycle unit as usual.

The scalable binomial broadcasting scheme.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

(c) [figure omitted; refer to PDF]

By the scalable binomial broadcasting, a video server can distribute live videos using a constant number of channels. The cost of the scheme is that the latecomers' waiting time and buffer requirements grow in the power of two.

3. Analysis and Comparison

This section presents the requirements of network bandwidth, buffer size, and I/O load on client sides with respect to each live broadcasting scheme. The assumptions include the following. Let L be the video length. (1) The media playback rate is b . (2) The length of a segment is l . (3) The number of video segments is N . The media size of the live video is blN bytes. The over-length portion is M . (4) A playing time slot denotes n .

3.1. Bandwidth Requirements

When the length of the live video is longer than L , the broadcasting scheme must allocate extra channels to distribute the over-length portion, as mentioned in Section 2.3. The bandwidth requirements of each broadcasting scheme are listed as follows.

(i) Live Harmonic Broadcasting (LHB). Its bandwidth requirements include a channel for live broadcast _CL and multiple channels _Cn for clients (Figure 4). Since the bandwidth of each channel is a harmonic series [8], the bandwidth requirement ( _βh ) is [figure omitted; refer to PDF] Equation (2) represents the bandwidth requirement when the live video is not over: [figure omitted; refer to PDF] The equation represents the bandwidth requirement when the live video is over, and the channel _CL is released.

(ii) Live Staircase Broadcasting (LSB). In comparison with the regular staircase broadcasting [7], this scheme requires an additional channel C_L for live broadcasting. Hence, the bandwidth requirement ( _βs ) is [figure omitted; refer to PDF] where c=[left floor]lo_g2 n[right floor] , m=n-^2c , and 1...6;n...6;N+M : [figure omitted; refer to PDF] where c=[left floor]lo_g2 (N+M+1)[right floor] , m=N+M-^2c , and N+M<n .

(iii): Live Fast Broadcasting (LFB. Its bandwidth requirement _βf can be obtained from [3]; it is [figure omitted; refer to PDF] [figure omitted; refer to PDF]

(iv) Scalable Binomial Broadcasting . Since the scalable binomial broadcasting scheme transfers a live video at a constant number of channels, its bandwidth requirement _βb is [figure omitted; refer to PDF]

Figure 7 depicts the bandwidth requirements of each broadcasting scheme. In [9], we proved that the optimal broadcasting scheme is harmonic scheme. However, in the study, we find that when the length of the live video is less than 16l, LFB becomes the optimal live broadcasting scheme, as shown in Figure 7. This is because LHB requires an additional channel, the live channel CL, to broadcast the live program. Furthermore, when the length exceeds 16l, LHB can be proved to be the optimal scheme by following the same deduction process revealed in [9]. Finally, Figure 7 displays that the scalable binomial broadcasting works with constant number of channels at the cost of doubling the maximum waiting time.

Figure 7: The required bandwidth versus the length of live videos.

[figure omitted; refer to PDF]

3.2. The Minimum Disk Transfer Rate Requirement

In the broadcasting schemes, the video segments are written to clients' disk as they need to be buffered. When clients need to consume the segments, they need to read them from disk. The disk transfer rate (Φ) is the sum of the read transfer rate ( _rread ) and write transfer rate ( _rwrite ). In order to ensure smooth playback, the minimum read transfer rate is the playback rate B . As well, the minimum write transfer rate must be large enough to save the need-to-be-buffered segments in time. It depends on which time slot a client receives video segments at. The following discusses the required disk transfer rate of each broadcasting schemes.

(i) LHB . From (2) and (3), we can find that the bandwidth requirement is maximum when n=N+M . The bandwidth requirement β at the time slot is β=(1+^∑x=1N+M-1 1/x)×B , and the server distributes maximum data at the time slot. In order to save video segments completely, the minimum write transfer rate at clients ( _{rmin _write} ) must equal the bandwidth requirement. Accordingly, the minimum disk transfer rate (Φmin) is the sum of _{rmin _read} and _{rmin _write} . That is, [figure omitted; refer to PDF]

(ii) LSB . Like the LHB, when n=N+M , the bandwidth requirement is maximum. Thus, [figure omitted; refer to PDF] where c=[left floor]lo_g2 (N+M)[right floor] , and m=N+M-^2c .

(iii): LFB . From (6), we can derive the maximum bandwidth requirement when n=N+M . Thus, [figure omitted; refer to PDF]

(iv) Scalable Binomial Broadcasting . Owing to the constant bandwidth requirement, the disk transfer rate is also constant and equal to [figure omitted; refer to PDF] Figure 8 shows the maximum I/O load Φ of each broadcasting scheme.

Figure 8: The maximum I/O load on clients versus the length of live videos.

[figure omitted; refer to PDF]

3.3. Maximum Client Buffer Requirements

Based on the previous discussion, we find that the client's video incoming rate ( _rlive +_rfilling ) is greater than video playback rate ( _rplayback ). The unconsumed video segments will be saved on the client's auxiliary storage. Because media playback rate is equal to the live broadcasting rate ( _rplayback =_rlive =B ), the rate to fill the missing segments mainly contributes to the buffer accumulation, as indicated in Figure 9.

Figure 9: A media rate diagram of a client on LHB.

[figure omitted; refer to PDF]

Suppose that the filling process of missing segments ends at Tf and the live video ends at Te . Thus the integration ∫TaTfrfilling dt is the size of missing video segments. If Tf is before Te , as shown in Figure 9, the maximum buffer requirement ( Z ) is equal to the size of missing video segments Z=∫TaTfrfilling dt . In order to satisfy the continuous playback constraint, the time to fill the missing segments must be shorter than the time to play the missing segments. Therefore, if a client arrives in the first half of the live broadcasting, the buffered video size is always equal to the size of missing video segments. On the contrary, if a client arrives after the midpoint of a live show, the maximum buffer requirement varies with the adopted live broadcasting schemes. Suppose that the length of a live video is 1024l. Figure 10 illustrates the relationship between the buffer requirements and the client's arrival time.

Figure 10: The relation between the buffer requirement and the client's arrival time.

[figure omitted; refer to PDF]

Suppose that a client arrives at the n th time slot and the live video length is N . For the live broadcasting schemes, their maximum buffer ( Z ) requirements are listed as follows.

(i) LHB. Its maximum buffer requirement is [figure omitted; refer to PDF] where ^ζi =_rlive,i +^[varphi]i -_rplayback,i . The ^[varphi]i is the sum of the (i-n )th column of filling rate matrix in (6) when i...4;n+n ; others ^[varphi]i =0 . (The _rlive,i =0 , when i>N ; others _rlive,i =_rplayback,i =B .)

(ii) LSB . Its maximum buffer requirement is [figure omitted; refer to PDF] where ^ζi =_rlive,i +^[varphi]i -_rplayback,i . The ^[varphi]i is the sum of the (i-n )th column of filling rate matrix in (9) when i...4;n+n ; others ^[varphi]i =0 . (The _rlive,i =0 , when i>N ; others _rlive,i =_rplayback,i =B .)

(iii): LFB . Its maximum buffer requirement can be obtained from [3] [figure omitted; refer to PDF] where c is the number of channels, and c=(1+[left floor]lo_g2 N[right floor]) .

(iv) Scalable Binomial Broadcasting. Its maximum buffer requirement is identical to that of live fast broadcasting: [figure omitted; refer to PDF] where C is a constant number of the preallocated channels.

According to (13) to (16), Figure 11 illustrates the maximum buffer requirements of the previous live broadcasting in the percentage of the video length.

Figure 11: The maximum buffer requirements of each live broadcasting scheme.

[figure omitted; refer to PDF]

4. Conclusions

Live program distribution is an important service on Internet. However, most current broadcasting schemes, such as PB, NPB, SB, and HB, cannot support live broadcasting. In this paper, we analyze the requirements for broadcasting live programs. In addition, the time skewing approach is proposed to allow traditional the VOD broadcasting schemes to distribute live programs. We also develop the scalable binomial broadcasting to distribute a live program with varying length in constant bandwidth consumption, however, at the cost of longer waiting time. The analyses and comparisons indicate that the scalable binomial broadcasting provides a reasonable performance than other live broadcasting schemes with respect to bandwidth requirements, I/O capacity, and receiver's buffer size.

References

[1] T. D. Little, D. Venkatesh, "Prospects for interactive video-on-demand," IEEE Multimedia , vol. 1, no. 3, pp. 14-24, 1994.

[2] T. C. Chiueh, C. H. Lu, "Periodic broadcasting approach to video-on-demand service," in Integration Issues in Large Commercial Media Delivery Systems, vol. 2615, of Proceedings of SPIE, pp. 162-169, October 1995.

[3] L. S. Juhn, L. M. Tseng, "Fast data broadcasting and receiving scheme for popular video service," IEEE Transactions on Broadcasting , vol. 44, no. 1, pp. 100-105, 1998.

[4] L. S. Juhn, L. M. Tseng, "Adaptive fast data broadcasting scheme for video-on-demand service," IEEE Transactions on Broadcasting , vol. 44, no. 2, pp. 182-185, 1998.

[5] J.- F. Paris, S. W. Carter, D. E. Long, "A hybrid broadcasting protocol for video-on-demand," in Proceedings of the Multimedia Computing and Networking Conference, pp. 317-326, San Jose, Calif, USA, January 1999.

[6] Y. C. Tseng, M. H. Yang, C. H. Chang, "A recursive frequency-splitting scheme for broadcasting hot videos in VOD service," IEEE Transactions on Communications , vol. 50, no. 8, pp. 1348-1355, 2002.

[7] L. S. Juhn, L. M. Tseng, "Staircase data broadcasting and receiving scheme for hot video service," IEEE Transactions on Consumer Electronics , vol. 43, no. 4, pp. 1110-1117, 1997.

[8] L. S. Juhn, L. M. Tseng, "Harmonic broadcasting for video-on-demand service," IEEE Transactions on Broadcasting , vol. 43, no. 3, pp. 268-271, 1997.

[9] Z. Y. Yang, L. S. Juhn, L. M. Tseng, "On optimal broadcasting scheme for popular video service," IEEE Transactions on Broadcasting , vol. 45, no. 3, pp. 318-324, 1998.

[10] S. Viswanathan, T. Imielinski, "Metropolitan area video-on-demand service using pyramid broadcasting," Multimedia Systems , vol. 4, no. 4, pp. 197-208, 1996.