# Single-Channel Data Broadcasting under Small Waiting Latency

Authors: Hsiang-Fu Yu
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Due to the advancement of network technology, video-on-demand (VoD) services are growing in popularity. However, individual stream allocation for client requests easily causes a VoD system overload; when its network and disk bandwidth cannot match client growth. This study thus presents a fundamentally different approach by focusing solely on a class of applications identified as latency tolerant applications. Because video broadcasting does not provide interactive (i.e., VCR) functions, a client is able to tolerate playback latency from a video server. One efficient broadcasting method is periodic broadcasting, which divides a video into smaller segments and broadcasts these segments periodically on multiple channels. However, numerous practical systems, such as digital video broadcasting-handheld (DVB-H), do not allow clients to download video data from multiple channels because clients usually only have one tuner. To resolve this problem in multiple-channel broadcasting, this study proposes a novel single-channel broadcasting scheme, which leverages segment-broadcasting capability further for more efficient video delivery. The comparison results show that, with the same settings of broadcasting bandwidth, the proposed scheme outperforms the alternative broadcasting scheme, the hopping insertion scheme, SingBroad, PAS, and the reverse-order scheduling scheme for the maximal waiting time.


---

## Body

## 1. Introduction

Due to the advancement of network technology, video-on-demand (VoD) services are growing in popularity. Clients can watch their desired videos at anytime without waiting or visiting a video rental store. Because of the online access provided by VoD services, several studies have predicted the success of VoD [1, 2]. VoD is inherently a personalized service because of its characteristic one-to-one interaction. Therefore, a VoD system typically allocates a dedicated stream for each incoming video request [3]. However, individual stream allocation easily causes a VoD system overload when its network and disk bandwidth cannot match client growth. This study thus presents a fundamentally different approach by focusing solely on a class of applications identified as latency tolerant applications. The key feature of latency tolerant applications is that they are unconcerned with latency between video servers and clients. Broadcast video streaming is perhaps the most important example of this class of applications [4]. Because video broadcasting does not provide interactive (i.e., VCR) functions, a client is able to tolerate playback latency from a video server. One efficient broadcasting method is periodic broadcasting, which divides a video into smaller segments and broadcasts them periodically on a set of communication channels. This method enhances bandwidth usage by allowing various clients to share the same channel bandwidths. Because periodic broadcasting typically requires a client to wait for the beginning of the first segment before starting playback, this scheme cannot support real-time VoD services.The fast broadcasting (FB) [5] scheme divides a video into a geometrical series of 1,2,4,…,2k-1, where k is the number of broadcasting channels. An implementation of the FB scheme on IP multicasting was reported in [6]. To achieve minimal latency, the harmonic broadcasting (HB) scheme [7] partitions a video into multiple segments, and each segment Si is divided into i subsegments. The subsegments of the same segment are then broadcast on the same channel. The recursive frequency-splitting (RFS) scheme [8] achieves a near-minimal waiting time by periodically broadcasting each segment at a frequency that can guarantee continuous video playback. In modifying the FB scheme, the reverse fast broadcasting (RFB) scheme [9] buffers 25% of video length, merely half of what is required by the FB scheme. By combining RFB and RFS, the hybrid broadcasting scheme (HyB) [10] requires the same client buffering space as that of RFB; however, it achieves smaller waiting time. The study in [11] integrates the fixed-delay pagoda broadcasting scheme [12] and RFB to reduce client waiting time and buffer demand. A generalized reverse sequence-based model [13] was proposed to clarify why broadcasting segments in reverse order can reduce buffer requirements. A scalable binomial broadcasting scheme [14] transfers live videos using constant bandwidth, regardless of video length.The mentioned schemes transfer video segments on multiple channels simultaneously and periodically, and a client typically must receive segments from these channels concurrently. To perform multiple-channel segment broadcasting, a server must multiplex video segments into multiple channels and synchronize these segments across these channels. Segment multiplexing and synchronization are difficult, because packet transmissions are varied with network traffic. In addition, numerous practical systems, such as digital video broadcasting-handheld (DVB-H) and integrated services digital broadcasting-handheld (ISDBH), do not permit a client to download video data from multiple channels, because the client typically has only one tuner [15, 16]. To solve these problems caused by multiple-channel broadcasting, many studies were proposed to broadcast segments over a single channel, such as the alternative broadcasting (AB) scheme [15], the hopping insertion (HI) scheme [16], SingBroad [17], PAS [18], and the reverse-order scheduling (ROS) scheme [19]. The basic concept behind these schemes is to partition a video into equal-sized segments, which are classified into several groups and transferred over a single channel according to a predefined arrangement.This study proposes a single-channel broadcasting scheme to yield short waiting time. Letkb be the bandwidth of a single channel, where k is a positive integer and b is the playback rate of a video. The proposed scheme partitions the single channel as an infinite set of time slots. Each time slot is further composed of smaller subslots. A video of length L is equally divided into 2k-1 segments, which are then arranged to k groups, denoted by G0,G1,…,Gk-1. A segment of group Gi is split into 2i equal subsegments, which are then placed to individual subslots. The mathematical analysis shows that the maximal client waiting time of the scheme is (k+1)L/k(2k-1). This study also verifies the workability of the scheme and compares it with several current approaches. The comparison results show that, with the same settings of broadcasting bandwidth, the proposed scheme outperforms AB, HI, SingBroad, PAS, and ROS for the maximal waiting time. Extensive simulations also indicate that the proposed scheme requires smaller client buffering space than AB and SingBroad for k>4.The remainder of this study is organized as follows. Section2 reviews AB, HI, SingBroad, PAS, and ROS. Section 3 introduces the proposed scheme and verifies its accuracy. Section 4 shows the evaluations of the performance of the scheme, and Section 5 makes a brief conclusion.


## 2. Related Work

This section introduces AB [15], HI [16], SingBroad [17], PAS [18], and ROS [19]. Table 1 defines the terms used in this study. As mentioned previously, this study divides a single channel into an infinite set of time slots.Table 1
List of terms used in this study and their respective definitions.
Term
Definition
L
Video length
b
Video playback rate
k
b
Bandwidth of a single channel, wherek is a positive integer
N
Number of segments
S
i
ith video segment
d
Segment length ofSi
S
i
,
j
jth subsegment of Si
t
a
Client arrival time
T
i
ith time slot, i≥0
w
Maximal waiting time for playbackThe AB scheme [15] splits a video into N segments. This scheme proposes two modes for determining the value of N. One is the mechanism-dominant (MD) mode, and the other is the waiting time-dominant (WD) mode. In the MD mode, N=⌊(k+3)/2⌋, and clients start playing video data when they receive segment S1. The AB scheme with WD obtains N=⌈(k+3)/2⌉. In this mode, the starting time of video playback is determined by whether each segment can be played continuously, rather than the downloading of segment S1. For both modes, the AB scheme broadcasts segment S1 on the single channel at time slot Ti if imod2=0. The rest of segments are broadcast sequentially and periodically on the remaining time slots. Figure 1 shows an example to demonstrate the segment downloading and playing for AB, where k=4. The segments downloaded and played by a client are gray. The AB scheme with MD divides a video into three segments, as shown in Figure 1(a). A client starts to play video data at the beginning of segment S1. In addition, the AB scheme with WD partitions the same video into four segments, as presented in Figure 1(b). Note that if the client started playing segment S1 on time slot T2, segment S2 would not be played continuously. Therefore, the client begins to play video data on time slot T3 to guaranteecontinuous playback.Segment partition and arrangement for AB.
(a)
(b)The HI scheme [16] divides a video into N even segments, where N is an arbitrary positive integer. This scheme then classifies the segments into ⌈N/Q⌉ groups, where Q=⌈N/exp(0.57(k-1))⌉. Group Gj contains segments SjQ+1 to S(j+1)Q, where 0≤j≤⌈N/Q⌉-2. The last group includes the remaining segments. Initially, HI puts the segments of group G0 together in order. The segments of the remaining groups are then inserted into the segments of G0 in a hopping way to obtain the final broadcasting schedule [16].SingBroad [17] partitions a video into 2k-1-1 segments that are arranged into k-1 groups. Group Gj contains segments S2j to S2j+1-1, where 0≤j≤k-2. Segment S2j+i of group Gj is broadcast on time slot Tj+i(k-1)+2j(k-1)y, where 0≤i≤2j-1 and y is zero or a positive integer. For example, for k=4, SingBroad divides a video into seven segments, which are then arranged to three groups. Group G2 contains segments S4 to S7. Segment S5 is broadcast on time slot T5+12y (e.g., time slots T5, T17, T29, and so on), where j=2 and i=1. When a video request arrives, the client must wait for the beginning of the nearest segment S1 to start video downloading and playing.Like the SingBroad scheme, the PAS scheme [18] splits a video into 2k-1-1 segments and classifies these segments into k-1 groups. Group Gj contains segments S2j to S2j+1-1, where 0≤j≤k-2. Unlike SingBroad, PAS further divides each segment of Gj into 2j even subsegments. Each time slot Ti is split into 2imod(k-1) subslots that are used to place subsegments. For instance, for k=4, PAS partitions a video into segments S1 to S7, which are arranged to three groups. Segment S5 of G2 is divided into four subsegments S5,1, S5,2, S5,3, and S5,4 that are broadcast across various subslots. A client must wait for the nearest segment S1 to begin video downloading and playing.The ROS scheme [19] divides a video into 3×2k-2 segments that are classified into k groups. Groups G0 and G1 contain {S1} and {S2,S3}, respectively. The remaining group Gj includes segments S3×2j-2+1 to S3×2j-1 where 2≤j≤k-1. Let y be zero or a positive integer. Segment  of G0 is broadcast on time slot Tky. This scheme then puts segments S3 and S2 of G1 on time slots T1+2ky and Tk+1+2ky, respectively. The ROS scheme transmits segment S3×2j-1-x of the remaining group Gj on time slot Tj+xk+3×2j-2×ky, where 2≤j≤k-1 and 0≤x≤3×2j-2-1. For example, segment S6 of group G2 is broadcast on time slot T2+3ky because j=2 and x=0. For k=4, ROS puts segment S6 on time slots T2, T14, T26, and others. When a client wants to watch a video, the client must wait for the beginning of the nearest segment S1 to start downloading. In addition, segments S2 and S3 must be received in order. For the segments of the remaining groups, the client downloads them according to the following process. Suppose that Sp is the segment that a client is currently playing, and segment Si of Gj is the segment that appears on the channel and is not received by the client. If p+3×2j-2<i, the client does not download segment Si. Otherwise, the client receives it. When downloading segment S1 is complete, the client starts video playback.


## 3. Proposed Scheme

According to the mentioned schemes [15–19], the number of video segments mainly determines client waiting time. Therefore, the key to minimizing the waiting time is to partition a video into as many segments as possible, under the condition that ensures continuous playback. To maximize the segment number, the proposed scheme broadcasts video data over a single channel according to the following step.:(1)
Divide a video into2k-1 (i.e., N=2k-1) equal-length segments, denoted by S1, S2, … , S2k-1 in sequence. The length of each segment, d, thus equals L/(2k-1). For example, in Figure 2, a server allocates a single channel with a bandwidth of 3b to broadcast a video of length L. The video is equally divided into 23-1 segments, denoted by S1, S2, … , S7. The length of each segment equals L/7.(2)
Classify these segments intok groups, denoted by G0,G2,…,Gk-1. Assemble segments S2j to S2j+1-1 into group Gj sequentially. Figure 2 shows that the segments are then classified into three groups G0={S1}, G1={S2,S3}, and G2={S4,S5,S6,S7}. Each segment Si of group Gj is further partitioned into 2j subsegments, denoted by Si,1,Si,2,…,Si,2j. As shown in Figure 2, segment S5 of group G2 is split into four subsegments S5,1, S5,2, S5,3, and S5,4.(3)
Partition a single channel as an infinite set of time slots, denoted byT0, T1, T2, and so on. Each time slot is used to deliver segment data at a bandwidth of kb, and the length of each time slot equals
(1)L(kN)=dk.(4)
A time slotTi is further divided into 2j subslots, denoted by Ti,1,Ti,2,…,Ti,2j, if imodk=j. The length of a subslot of time slot Ti thus equals d/(2jk). For example, Figure 2 shows that the length of each time slot equals d/3 because k=3. Time slot T2 is further partitioned into four subslots T2,1, T2,2, T2,3, and T2,4 because 2mod3=2.(5)
Put the segment data of each group on each time slot in sequence. For example, the segment data of groupsG0, G1, and G2 are sequentially broadcast on time slots T0, T1, T2, and so on, as indicated in Figure 2. In general, the segment data of group Gj are put on time slot Tj+ky, because there are k groups, where y is zero or a positive integer. Furthermore, the scheme sequentially broadcasts the subsegments of the segments of group Gj on the subslots of time slot Tj+ky. For example, Figure 2 shows that the subsegments of segments S4 to S7 of group G2 are sequentially put on the subslots of T2, T5, T8, T11, and others. Note that only a subsegment of a segment of the same group is put on a subslot of a time slot. Because the segment data of group Gj are broadcast once every k time slots and each segment consists of 2j subsegments, each subsegment is transmitted once every 2jk time slots. Therefore, the scheme broadcasts subsegment Si,x of group Gj on subslot
(2)Tj+(x-1)k+2jky,i-2j+1,wherey∈int and y≥0.For example, Figure2 shows that the proposed scheme puts subsegment S5,3 of group G2 on subslot T8+12y,2 (e.g., T8,2, T20,2, and T32,2) because k=3, j=2, i=5, and x=3.Figure 2
Segment partition and arrangement for the proposed scheme.This study next presents how to download video segments on the client side. A client is assumed to have a sufficient buffer to store downloaded segments. Suppose that a client can download and play the same segment concurrently, because the downloading bandwidth is equal to or larger than the playback rate. This study also assumes that a client desires to watch a video at timeta. Let Tu,v be the subslot that is nearest to time ta. The segment downloading and playing are as the following.(1)
The client must wait for subslotTu,v before receiving subsegments. Once the subslot is up, the client starts downloading the subsegment from this subslot.(2)
After this downloading is complete, the client continues to receive the remaining subsegments from the following subslots. If a subsegment has been downloaded, the client simply skips it.(3)
When all the subsegments are received, the client stops the segment downloading.(4)
The client assembles the received subsegments to form complete segments and starts playing them at the beginning of subslotTu+k,v.Figure3 shows an example for demonstrating how to download and play video segments, where the subsegments downloaded and played by a client are gray. Because subslot T1,2 is closest to the client arrival time ta, the client starts downloading subsegment S3,1 on subslot T1,2. The client then continues to receive subsegments from subslots T2,1 to T5,4. Because subsegment S1,1 has been downloaded on subslot T3,1, the client does not receive it again on subslot T6,1. Similarly, the client does not download subsegments S3,1, S1,1, S2,2, and S3,2 on subslots T7,2, T9,1, T10,1, and T10,2, respectively. When the client finishes receiving all the subsegments at the end of subslot T11,4, the client stops downloading subsegments. The client assembles the received subsegments to form complete segments and plays them at the start of subslot T4,2, as shown in Figure 3.Figure 3
Segment downloading and playing for the proposed scheme.


### 3.1. Workable Verification

Suppose that segmentSi is in group Gj, where 2j≤i≤2j+1-1. The mentioned broadcasting process transfers a subsegment of segment Si once every k time slots. Because the number of subsegments of segment Si equals 2j, the broadcasting process can transmit all the subsegments of segment Si once every 2jk time slots. According to the downloading process, a client starts segment downloading at the beginning of subslot Tu,v. Therefore, the client can receive all the subsegments of Si at the beginning of subslot Tu+2jk,v. In addition, the client begins segment playback at the beginning of subslot Tu+k,v. Because the playback length of a segment equals k time slots according to (1), the start time to play segment Si is the beginning of subslot Tu+k+ik,v. To guarantee continuous playback for the client, the end time of downloading segment Si must be earlier than the start time of its playback. That is, the beginning of subslot Tu+k+ik,v must be later than the beginning of subslot Tu+2jk,v. This study evaluates
(3)(u+k+ik)-(u+2jk)=(i+1-2j)k>0,dueto2j≤i.The end time of downloading segmentSi is earlier than the start time of its playback. Therefore, the proposed scheme ensures continuous video playback on the client side.


## 3.1. Workable Verification

Suppose that segmentSi is in group Gj, where 2j≤i≤2j+1-1. The mentioned broadcasting process transfers a subsegment of segment Si once every k time slots. Because the number of subsegments of segment Si equals 2j, the broadcasting process can transmit all the subsegments of segment Si once every 2jk time slots. According to the downloading process, a client starts segment downloading at the beginning of subslot Tu,v. Therefore, the client can receive all the subsegments of Si at the beginning of subslot Tu+2jk,v. In addition, the client begins segment playback at the beginning of subslot Tu+k,v. Because the playback length of a segment equals k time slots according to (1), the start time to play segment Si is the beginning of subslot Tu+k+ik,v. To guarantee continuous playback for the client, the end time of downloading segment Si must be earlier than the start time of its playback. That is, the beginning of subslot Tu+k+ik,v must be later than the beginning of subslot Tu+2jk,v. This study evaluates
(3)(u+k+ik)-(u+2jk)=(i+1-2j)k>0,dueto2j≤i.The end time of downloading segmentSi is earlier than the start time of its playback. Therefore, the proposed scheme ensures continuous video playback on the client side.


## 4. Performance Analysis and Comparison

This study primarily selected client waiting time and buffer demand as the performance criteria. The proposed scheme was compared with AB, HI, SingBroad, PAS, and ROS. According to the downloading process, when a client exactly arrives at the beginning of a subslot, the waiting time equalsk timeslots (i.e., d) because of (1). If the client just misses the startup of a subsegment on the channel, the client must additionally wait for the length of the subsegment. Because subsegment S1,1 is the longest subsegment, the maximal waiting time w equals k+1 time slots. That is,
(4)w=(k+1)dk=(k+1)Lk(2k-1).Table2 summarizes the maximal waiting time incurred by AB [15], HI [16], SingBroad [17], PAS [18], ROS [19], and the proposed scheme. The results show that the number of segments mainly determines the maximal waiting times for all the schemes. The increase of the server bandwidth (i.e., the value of k) enlarges the number of segments and thus reduces the waiting time.Table 2
Maximal waiting time for different schemes in terms of video lengthL.
Scheme
AB-MD
AB-WD
HI
SingBroad
PAS
ROS
Proposed
Maximal waiting time
2
L
⌊
(
k
+
3
)
/
2
⌋
k
2
L
⌈
(
k
+
3
)
/
2
⌉
k
(
Q
×
H
(
⌊
N
/
Q
⌋
)
+
(
(
N
-
Q
⌊
N
/
Q
⌋
)
/
(
⌊
N
/
Q
⌋
+
1
)
)
)
L
k
N, whereQ=⌈Nexp(0.57(k-1))⌉  H(i)=∑j=1i1j
(
k
-
1
)
L
(
2
k
-
1
-
1
)
k
(
k
-
1
)
L
(
2
k
-
1
-
1
)
k
(
k
+
1
)
L
3
×
2
k
-
2
k
(
k
+
1
)
L
(
2
k
-
1
)
kTo clarify the performance advantages of the proposed scheme, this study calculated the maximal waiting times of AB, HI, SingBroad, PAS, ROS, and the proposed scheme at various values ofk, where the value of N for HI equals 10000. Figure 4 shows the performance results. As the server bandwidth increases, the waiting times under all the schemes are sharply reduced. In addition, the proposed scheme yields the shortest waiting time. For example, when the server bandwidth equals 7b (i.e., k=7), the scheme reduces the broadcast latency to less than 0.009L. In contrast, AB-MD, AB-WD, HI, SingBroad, PAS, and ROS yield 0.057, 0.057, 0.019, 0.014, 0.014, and 0.012L, respectively. The proposed scheme reduces the waiting times by 84%, 84%, 53%, 36%, 36%, and 25%. Assume that the video length L is 120 min. Figure 5 shows the maximal waiting time for all the schemes in seconds. For k=6, the waiting times of AB-MD, AB-WD, HI, SingBroad, PAS, ROS, and the proposed scheme are 600, 480, 240, 194, 194, 175, and 133 s, respectively. In this case, the waiting times for the proposed scheme are 78%, 72%, 45%, 31%, 31%, and 24% smaller than those of AB-MD, AB-WD, HI, SingBroad, PAS, and ROS, respectively.Figure 4
Maximal waiting time (in terms ofL) incurred on new clients at different broadcasting bandwidth.Figure 5
Maximal waiting time yielded by different schemes, whereL=120 min.With low cost and large capacity of storage disks, client buffer demand is no longer a substantial concern. However, for completeness, this work studies the required buffer size under AB-MD, AB-WD, SingBroad, PAS, ROS, and the proposed scheme (the comparison does not include HI, because its buffer requirements are not provided in [16]). Because this study did not derive a close formula for the required buffering space of the proposed scheme, a simulator in Perl [20] was developed to exhaustively search all possibilities to determine the maximum buffering space required at various broadcasting bandwidths. Figure 6 shows the client buffer requirements regarding video length L, where the server bandwidth is varied from 3b to 12b. The proposed scheme initially requires the largest buffering space. However, as the server bandwidth increases, the client buffer requirements drop and approach 50% of video size. Therefore, the proposed scheme yields smaller buffer requirements than AB and SingBroad.Figure 6
Maximum buffer requirements for AB-MD, AB-WD, SingBroad, PAS, ROS, and the proposed scheme.


## 5. Conclusion

A VoD system typically allocates a dedicated stream for each incoming video request; however, individual stream allocation easily causes the system overloaded. This study thus presents a fundamentally different approach by focusing solely on a class of applications identified as latency tolerant applications. Because video broadcasting does not provide interactive functions, a client is able to tolerate playback latency. One efficient broadcasting method is periodic broadcasting, which divides a video into smaller segments and broadcasts them periodically on multiple channels. However, the implementation of multiple-channel broadcasting is difficult and complicated. Therefore, this study proposes a novel single-channel broadcasting scheme for more efficient video delivery. The correctness of the scheme is verified mathematically. The performance comparisons show that, with the same settings of broadcasting bandwidth, the proposed scheme yields the shortest waiting time when compared with AB, HI, SingBroad, PAS, and ROS.



---

*Source: 629350-2013-04-11.xml*