# Efficient Periodic Broadcasting for Mobile Networks at Small Client Receiving Bandwidth and Buffering Space

Authors: Hsiang-Fu Yu; Yao-Tien Wang; Jong-Yih Kuo; Chu-Yi Chien
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Periodic broadcasting is an effective approach for delivering popular videos. In general, this approach does not provide interactive (i.e., VCR) functions, and thus a client can tolerate playback latency from a video server. The concept behind the approach is partitioning a video into multiple segments, which are then broadcast across individual communication channels in terms of IP multicast. The method improves system throughput by allowing numerous clients to share the channels. For many broadcasting schemes, client receiving bandwidth must equal server broadcasting bandwidth. This limitation causes these schemes to be infeasible in mobile networks because increasing receiving bandwidth at all client sites is expensive, as well as difficult. To alleviate this problem, the fibonacci broadcasting (FiB) scheme allows a client with only two-channel bandwidth to receive video segments. In comparison with other similar schemes, FiB yields smallest waiting time. Extending FiB, this work proposes a new scheme (called FiB+) to achieve smaller client buffering space and the same waiting time under two-channel receiving bandwidth. Extensive analysis shows that FiB+ can yield 34.5% smaller client buffer size than that of FiB. Further simulation results also indicate that FiB+ requires lower client buffering space than several previous schemes.


---

## Body

## 1. Introduction

Video-on-demand (VOD) services have become popular due to advances in network and computer technology [1, 2]. A VOD system may easily run out of bandwidth since the growth in bandwidth can never keep up with the growth in the number of clients. To alleviate the problem, one way is to simply broadcast popular videos. According to the study in [3, 4], a few very popular videos constitute most client requests. Data broadcasting is thus suitable to transfer popular videos that may be interesting to many clients in a particular period of time. An efficient method for broadcasting a popular video is to divide it into segments, which are simultaneously and periodically transmitted across individual communication channels in terms of IP multicast [5]. Because video broadcasting does not provide VCR functions, a client is able to tolerate playback latency. To ensure continuous playback, clients must simultaneously download and save the video segments from these channels. The clients usually have to wait for the occurrence of the first segment before they can start playing the video. Since the clients cannot watch the video immediately, the broadcasting schemes provide near VOD services.The fast broadcasting (FB) scheme [6] improves segment partition and arrangement to yield shorter waiting time. To achieve near-minimum waiting time, the recursive frequency-splitting (RFS) scheme [7] broadcasts each segment at the frequency that can keep continuous video playback. A scalable binomial broadcasting scheme [8] transfers a variable-length video using constant bandwidth. To simplify the implementation of multiple channels, the PAS scheme [9] broadcasts video segments over a single channel. The reverse-order scheduling (ROS) scheme [10] transmits segments of the same group in reverse order over a single channel to save buffering space.With the fast growth of wireless networks, mobile video services become more and more popular. Broadcasting videos under rather restricted client resources is increasingly important. The following schemes address the savings on client buffer size and bandwidth. Modifying the FB scheme [6], the reverse fast broadcasting (RFB) scheme [11] buffers 25% of video size, just half of what is required by FB. By combining RFS and RFB, the hybrid broadcasting scheme (HyB) [12] achieves small client buffering space and waiting time. Different RFB-based hybrid schemes were proposed in [13, 14]. The skyscraper broadcasting (SkB) scheme [15] allows a client to download video data using only a bandwidth of two channels. The client-centric approach (CCA) [16] also permits a client downloading video data via a small number of channels, and CCA+ [17] further yields smaller waiting time than SkB. Like SkB and CCA+, the fibonacci broadcasting (FiB) scheme [18] supports a client with two-channel bandwidth but achieves the minimum waiting time. The authors in [19] proposed an FB-based scheme for heterogeneous clients. The studies in [20, 21] deploy a proxy in VoD systems to serve heterogeneous clients.The contributions of this study are summarized as follows.(1)
Extending FiB, this work proposes a promising scheme, called FiB+, to deliver near VOD services to clients with small receiving bandwidth and buffering space. In comparison with FiB, FiB+ still yields the minimum waiting time under two-channel receiving bandwidth; moreover, FiB+ can save about 34.5% of buffer size.(2)
The paper investigates the total client buffer requirements for FiB+ and explains why this scheme requires smaller buffering space than FiB. We further derive the maximum number of segments buffered by an FiB+ client mathematically. Extensive performance analysis has been conducted on FiB+ by comparing a number of past reported counterparts. The results indicate that FiB+ yields relatively lower client buffer requirements than most schemes.The remainder of this study is organized as follows. The FiB scheme is introduced in Section2. Section 3 presents FiB+. This section also verifies the on-time video delivery under two-channel client bandwidth. Section 4 evaluates the performance of FiB+. Brief conclusions are drawn in Section 5.


## 2. Review of FiB

Letk be the number of server channels throughout the paper. The FiB scheme [18] unequally divides a video of length L into k segments, denoted by S1,S2,…,Sk in sequence. The length of a segment Si is based on the following equation and equals Lni/∑p=1knp as follows:
(1)ni={1,i=12,i=2ni-1+ni-2,3≤i≤k.Assume that the data transmission rate of each channel equals the playback rateb. The server then periodically broadcasts segment Si on channel Ci, as illustrated in Figure 1. In the figure, segments downloaded and played by a client are gray. When a client wants to watch a video, the client first downloads segments S1 and S2 on the first two channels C1 and C2. Once finishing receiving the segment S1, the client continuously accepts segment S2 and newly downloads segment S3 on channel C3. The client repeats the process, which starts downloading segment Si on channel Ci once finishing receiving segment Si-2 from channel Ci-2, until all the segments are loaded. An FiB client thus requires a bandwidth of only two channels to download video segments.Figure 1
Illustration of segment downloading for the FiB scheme, wherek=6.


## 3. FiB+

Some of the frequently used terms and their definitions are listed in Table1. On the server side, the FiB+ scheme includes the following steps.(1)
The server equally divides a video intoN segments, denoted by S1,S2,…,SN in sequence, where N=∑p=1knp, where np is based on (1). The length of each segment thus equals L/N. From (1), we further yields
(2)mi=∑p=1inp=ni+2-2.See AppendixA for details. Thus, N=nk+2-2. The FiB+ scheme then assembles segments Sni+1-1 to Sni+2-2 (i.e., Smi-1+1 to Smi) into group Gi sequentially, as illustrated in Figure 2(a). The number of segments of group Gi thus equals ni. For instance, group G4 includes segments S7 to S11, and n4=5.(2)
ChannelCi, where 1≤i≤k-2, periodically broadcasts the segments of group Gi in sequence, as shown in Figure 2(b). That is, segments Sni+1-1 to Sni+2-2 are transferred one by one on channel Ci.(3)
The segments of groupsGk-1 and Gk are cyclically transmitted on channels Ck-1 and Ck in reverse order, respectively. Figure 2(b) shows that the scheme repeatedly broadcasts the segments of group Gk-1 in the order of Snk+1-2 to Snk-1 and the segments of group Gk in the order of Snk+2-2 to Snk+1-1.Table 1
List of terms used in the proposed scheme and their respective definitions.
Term
Definition
L
Video length
k
Number of broadcasting channels for each video on the server side
C
i
ith broadcasting channel, i=1,…,k
N
Number of segments of a video
S
i
ith video segment, i=1,…,N
n
i
Number of segments transferred on channelCi
m
i
Total segments transferred on channelsC1 through Ci, mi=∑p=1inp
b
Video playback rate assumed to equal the data transmission rate of each channel
T
0
Starting time to watch the first segment
Time unit
Basic unit on time axis, whose length equals the length of a segment (i.e.,L/N)Channel allocation for the FiB+ scheme.
(a)
(b)Figure3 demonstrates the segment broadcasting and downloading for FiB+, where the segments downloaded and played by a client are gray. Let T0 be the time that the client starts receiving video segments and be the origin (i.e., the first time unit) of the time axis. Due to k=6, FiB+ equally divides a video into 32 segments, which are then classified into six groups. The segments of groups G1 to G4 are broadcast sequentially on channels C1 to C4, respectively. In addition, FiB+ transmits segments of groups G5 and G6 on channels C5 and C6 in reverse order.Figure 3
Illustration of segment broadcasting and downloading for the FiB+ scheme, wherek=6 and N=32.A client is assumed to have enough buffers to store video segments downloaded. We further suppose that one time unit equals the length of a segment throughout this study. Playing a video on the client side includes the following steps.(1)
Download segments of groupGi on channel Ci during time units ni-1 to ni-1+ni-1=ni+1-1, where 1≤i≤k-2 and n0=1. For example, the client accepts segments from channel C4 during time units n4-1=3 to n4+1-1=7, as shown in Figure 3.(2)
The paper next presents how a client receives segments from channelsCk-1 and Ck. (In Figure 3, refer to channels C5 and C6.) Suppose that a client first sees a segment Sy on a channel Ci at time Tnow and sees the next segment Sy at time Tnext, where i=k-1 or i=k. (In Figure 3, i=6 and y=25.) The client is also assumed to play segments Sx and Sy at time Tnow and Tuse, respectively. Clearly, if Tnext≤Tuse, the client can delay downloading segment Sy at time Tnow, without interrupting the playback. Substituting Tuse=yth time unit, Tnow=xth time unit, and Tnext=Tnow+ni into Tnext≤Tuse, we obtain
(3)x+ni≤y.If the inequality is true, the client does not receive segmentSy at time Tnow, otherwise, performs the downloading immediately. For instance, when the client first sees segment S25 with only diagonal lines on channel C6 at the 7th time unit (i.e., Tnow) in Figure 3, (3) is true, 7+13≤25, and the client does not download the segment. Afterwards, the client sees next segment S25 with gray color and diagonal lines at the 20th time unit. The client must receive the segment because (3) does not hold, 20+13>25.(3)
The client plays the video in the order ofS1,S2,…,SN at time T0.(4)
The client stops loading data from networks when all the segments have been received.FiB+ and FiB differ in three areas.(i)
Equal-length segment partition versus variable-length segment partition. FiB+ divides a video into multiple equal-length segments, while FiB partitions a video into variable-length segments. For example, given k=6, FiB divides a video into six segments, whose lengths are L/32, 2L/32, 3L/32, 5L/32, 8L/32, and 13L/32. On the other hand, FiB+ partitions a video into 32 segments, whose lengths all equal L/32.(ii)
Multiple segments on each channel versus single segment. FiB+ cyclically broadcasts several segments on each channel except the first channel, and FiB transmits only one.(iii)
Segment transmission in reverse order. The FiB+ scheme broadcasts segments on the last two channels in reverse order. For example, the scheme transmits segments S19 to S12 on channel C5 and segments S32 to S20 on channel C6, as illustrated in Figure 3.


### 3.1. Analysis of Segment Playing and Downloading on a Single Channel

We next analyze the segment downloading on channelCi, where 1≤i≤k.For1≤i≤k-2, a client receives segments Sni+1-1 to Sni+2-2 from channel Ci during time units ni-1 to ni+1-1 and plays the segments during time units ni+1-1 to ni+2-2, as mentioned previously. Suppose that a client sees a segment Sj at the (ni+1-1)th time unit, where ni+1-1≤j≤ni+2-2. Figure 4(a) shows how a client downloads and plays segments, where the segments downloaded and played by the client are gray.Segment downloading on channelCi for FiB+.
(a)
(b)Fori=k-1 or k, a client downloads segments according to (3). We also assume that a client sees a segment Sj at the (ni+1-1)th time unit, where ni+1-1≤j≤ni+2-2. A complete segment-downloading diagram for channel Ci is based on (3), as indicated in Figure 4(b). The explanation is as follows.The client always downloads segmentSj since the inequality of (3) does not hold for x=ni+1-1 and y=j  (i.e., ni+1-1+ni=ni+2-1>j). In addition, because the segments of group Gi are transmitted once on channel Ci every ni time units and are played during time units ni+1-1 to ni+2-2, the client downloads a segment of group Gi either during time units ni+1-1 to ni+2-2 or during time units ni-1 to ni+1-2 (i.e., before the downloading of segment Sj).


#### 3.1.1. Segment Downloading within[ni+1-1,ni+2-2]

Figure4(b) shows that segments Sni+1-1 to Sj are broadcast on channel Ci in descending order during time units ni+1-1 to j, while a client plays these segments in turn. Let Sa be a segment broadcast on channel Ci during this period, and let Sb be the client-playback segment corresponding to Sa. Clearly, if a≥b, a client must download segment Sa to ensure continuous playing. Because the number of segments between Sj and Sa on channel Ci equals the number of segments between Sni+1-1 and Sb on the client playback, j-a=b-(ni+1-1) and a=j+ni+1-1-b. Substituting this equation to a≥b yields (j+ni+1-1)/2≥b. The maximum value of b is ⌊(j+ni+1-1)/2⌋, and the corresponding value of a equals j+ni+1-1-⌊(j+ni+1-1)/2⌋=⌈(j+ni+1-1)/2⌉. Figure 4(b) illustrates that the client downloads segments Sj to S⌈(j+ni+1-1)/2⌉ during time units ni+1-1 to ⌊(j+ni+1-1)/2⌋ and does not download any segment during time units ⌊(j+ni+1-1)/2⌋+1 to j. Similarly, this study obtains that a client receives segments Sni+2-2 to S⌈(j+ni+2-1)/2⌉ during time units j+1 to ⌊(j+ni+2-1)/2⌋ and does not download any segment during time units ⌊(j+ni+2-1)/2⌋+1 to ni+2-2.


#### 3.1.2. Segment Downloading within[ni-1,ni+1-2]

From (3), the client must download segments S⌈(j+ni+2-1)/2⌉-1 to Sj+1 during time units ⌊(j+ni+2-1)/2⌋+1-ni to ni+2-2-ni=ni+1-2 because the client does not download these segments during time units ⌊(j+ni+2-1)/2⌋+1 to ni+2-2, as shown in Figure 4(b). The figure further indicates that the client does not accept segments Sni+2-2 to S⌈(j+ni+2-1)/2⌉ during time units j+1-ni to ⌊(j+ni+2-1)/2⌋-ni since the client will perform their downloading during time units j+1 to ⌊(j+ni+2-1)/2⌋. Similarly, the client must receive segments S⌈(j+ni+1-1)/2⌉-1 to Sni+1-1 during time units ⌊(j+ni+1-1)/2⌋+1-ni to j-ni because the client does not download these segments during time units ⌊(j+ni+1-1)/2⌋+1 to j. Furthermore, since the client will download segments Sj-1 to S⌈(j+ni+1-1)/2⌉ during time units ni+1 to ⌊(j+ni+1-1)/2⌋, the client does not load any segment during time units ni+1-ni=ni-1 to ⌊(j+ni+1-1)/2⌋-ni, as illustrated in Figure 4(b).


### 3.2. Workable Verification

This section shows that FiB+ guarantees continuous playback and two-channel bandwidth demand on the client side.


#### 3.2.1. Continuous Playback

To keep on-time video delivery, the study in [7] indicates that a video server must broadcast a segment Sj on a channel Ci at least once in every j time units. For FiB+, a server transmits a segment Sj once every ni time units, where ni+1-1≤j≤ni+2-2. This paper thus needs to prove j≥ni. We then evaluate
(4)j-ni≥(ni+1-1)-ni,duetoni+1-1≤j=ni-1-1≥0.For FiB+, the segment broadcasting frequency is large enough to let clients receive video data in time.


#### 3.2.2. Two-Channel Bandwidth Demand

From the previous analysis in Figure4, we make a temporal-channel map of segment downloading for each channel, as indicated in Figure 5. In this figure, segments downloaded and played by a client are gray. This work divides client playback time t (in terms of time units) into multiple successive durations for ease of explanation.Figure 5
Segment downloading using client bandwidth2b.ForT0≤t≤nk-2-1, the client merely receives segments from channels C1 to Ck-2 because the client starts the segment downloading on channel Ck-1 at time unit nk-2, as shown in Figure 5. According to Step 1 of segment downloading on the client side, the client uses two-channel bandwidth to load segments in this period.Fornk-2≤t≤nk-1-1, the client receives segments only from channels Ck-2 and Ck-1 because the client finishes receiving segments from channel C1 to Ck-3 before time unit nk-2 and starts downloading segments on channel Ck at time unit nk-1, as indicated in Figure 5.Fornk-1≤t, the client simply receives the remaining segments from channels Ck-1 and Ck because the segment downloading on channel Ck-2 completes at time unit nk-1-1.Accordingly, an FiB+ client can download segments using two-channel bandwidth.


## 3.1. Analysis of Segment Playing and Downloading on a Single Channel

We next analyze the segment downloading on channelCi, where 1≤i≤k.For1≤i≤k-2, a client receives segments Sni+1-1 to Sni+2-2 from channel Ci during time units ni-1 to ni+1-1 and plays the segments during time units ni+1-1 to ni+2-2, as mentioned previously. Suppose that a client sees a segment Sj at the (ni+1-1)th time unit, where ni+1-1≤j≤ni+2-2. Figure 4(a) shows how a client downloads and plays segments, where the segments downloaded and played by the client are gray.Segment downloading on channelCi for FiB+.
(a)
(b)Fori=k-1 or k, a client downloads segments according to (3). We also assume that a client sees a segment Sj at the (ni+1-1)th time unit, where ni+1-1≤j≤ni+2-2. A complete segment-downloading diagram for channel Ci is based on (3), as indicated in Figure 4(b). The explanation is as follows.The client always downloads segmentSj since the inequality of (3) does not hold for x=ni+1-1 and y=j  (i.e., ni+1-1+ni=ni+2-1>j). In addition, because the segments of group Gi are transmitted once on channel Ci every ni time units and are played during time units ni+1-1 to ni+2-2, the client downloads a segment of group Gi either during time units ni+1-1 to ni+2-2 or during time units ni-1 to ni+1-2 (i.e., before the downloading of segment Sj).


### 3.1.1. Segment Downloading within[ni+1-1,ni+2-2]

Figure4(b) shows that segments Sni+1-1 to Sj are broadcast on channel Ci in descending order during time units ni+1-1 to j, while a client plays these segments in turn. Let Sa be a segment broadcast on channel Ci during this period, and let Sb be the client-playback segment corresponding to Sa. Clearly, if a≥b, a client must download segment Sa to ensure continuous playing. Because the number of segments between Sj and Sa on channel Ci equals the number of segments between Sni+1-1 and Sb on the client playback, j-a=b-(ni+1-1) and a=j+ni+1-1-b. Substituting this equation to a≥b yields (j+ni+1-1)/2≥b. The maximum value of b is ⌊(j+ni+1-1)/2⌋, and the corresponding value of a equals j+ni+1-1-⌊(j+ni+1-1)/2⌋=⌈(j+ni+1-1)/2⌉. Figure 4(b) illustrates that the client downloads segments Sj to S⌈(j+ni+1-1)/2⌉ during time units ni+1-1 to ⌊(j+ni+1-1)/2⌋ and does not download any segment during time units ⌊(j+ni+1-1)/2⌋+1 to j. Similarly, this study obtains that a client receives segments Sni+2-2 to S⌈(j+ni+2-1)/2⌉ during time units j+1 to ⌊(j+ni+2-1)/2⌋ and does not download any segment during time units ⌊(j+ni+2-1)/2⌋+1 to ni+2-2.


### 3.1.2. Segment Downloading within[ni-1,ni+1-2]

From (3), the client must download segments S⌈(j+ni+2-1)/2⌉-1 to Sj+1 during time units ⌊(j+ni+2-1)/2⌋+1-ni to ni+2-2-ni=ni+1-2 because the client does not download these segments during time units ⌊(j+ni+2-1)/2⌋+1 to ni+2-2, as shown in Figure 4(b). The figure further indicates that the client does not accept segments Sni+2-2 to S⌈(j+ni+2-1)/2⌉ during time units j+1-ni to ⌊(j+ni+2-1)/2⌋-ni since the client will perform their downloading during time units j+1 to ⌊(j+ni+2-1)/2⌋. Similarly, the client must receive segments S⌈(j+ni+1-1)/2⌉-1 to Sni+1-1 during time units ⌊(j+ni+1-1)/2⌋+1-ni to j-ni because the client does not download these segments during time units ⌊(j+ni+1-1)/2⌋+1 to j. Furthermore, since the client will download segments Sj-1 to S⌈(j+ni+1-1)/2⌉ during time units ni+1 to ⌊(j+ni+1-1)/2⌋, the client does not load any segment during time units ni+1-ni=ni-1 to ⌊(j+ni+1-1)/2⌋-ni, as illustrated in Figure 4(b).


## 3.1.1. Segment Downloading within[ni+1-1,ni+2-2]

Figure4(b) shows that segments Sni+1-1 to Sj are broadcast on channel Ci in descending order during time units ni+1-1 to j, while a client plays these segments in turn. Let Sa be a segment broadcast on channel Ci during this period, and let Sb be the client-playback segment corresponding to Sa. Clearly, if a≥b, a client must download segment Sa to ensure continuous playing. Because the number of segments between Sj and Sa on channel Ci equals the number of segments between Sni+1-1 and Sb on the client playback, j-a=b-(ni+1-1) and a=j+ni+1-1-b. Substituting this equation to a≥b yields (j+ni+1-1)/2≥b. The maximum value of b is ⌊(j+ni+1-1)/2⌋, and the corresponding value of a equals j+ni+1-1-⌊(j+ni+1-1)/2⌋=⌈(j+ni+1-1)/2⌉. Figure 4(b) illustrates that the client downloads segments Sj to S⌈(j+ni+1-1)/2⌉ during time units ni+1-1 to ⌊(j+ni+1-1)/2⌋ and does not download any segment during time units ⌊(j+ni+1-1)/2⌋+1 to j. Similarly, this study obtains that a client receives segments Sni+2-2 to S⌈(j+ni+2-1)/2⌉ during time units j+1 to ⌊(j+ni+2-1)/2⌋ and does not download any segment during time units ⌊(j+ni+2-1)/2⌋+1 to ni+2-2.


## 3.1.2. Segment Downloading within[ni-1,ni+1-2]

From (3), the client must download segments S⌈(j+ni+2-1)/2⌉-1 to Sj+1 during time units ⌊(j+ni+2-1)/2⌋+1-ni to ni+2-2-ni=ni+1-2 because the client does not download these segments during time units ⌊(j+ni+2-1)/2⌋+1 to ni+2-2, as shown in Figure 4(b). The figure further indicates that the client does not accept segments Sni+2-2 to S⌈(j+ni+2-1)/2⌉ during time units j+1-ni to ⌊(j+ni+2-1)/2⌋-ni since the client will perform their downloading during time units j+1 to ⌊(j+ni+2-1)/2⌋. Similarly, the client must receive segments S⌈(j+ni+1-1)/2⌉-1 to Sni+1-1 during time units ⌊(j+ni+1-1)/2⌋+1-ni to j-ni because the client does not download these segments during time units ⌊(j+ni+1-1)/2⌋+1 to j. Furthermore, since the client will download segments Sj-1 to S⌈(j+ni+1-1)/2⌉ during time units ni+1 to ⌊(j+ni+1-1)/2⌋, the client does not load any segment during time units ni+1-ni=ni-1 to ⌊(j+ni+1-1)/2⌋-ni, as illustrated in Figure 4(b).


## 3.2. Workable Verification

This section shows that FiB+ guarantees continuous playback and two-channel bandwidth demand on the client side.


### 3.2.1. Continuous Playback

To keep on-time video delivery, the study in [7] indicates that a video server must broadcast a segment Sj on a channel Ci at least once in every j time units. For FiB+, a server transmits a segment Sj once every ni time units, where ni+1-1≤j≤ni+2-2. This paper thus needs to prove j≥ni. We then evaluate
(4)j-ni≥(ni+1-1)-ni,duetoni+1-1≤j=ni-1-1≥0.For FiB+, the segment broadcasting frequency is large enough to let clients receive video data in time.


### 3.2.2. Two-Channel Bandwidth Demand

From the previous analysis in Figure4, we make a temporal-channel map of segment downloading for each channel, as indicated in Figure 5. In this figure, segments downloaded and played by a client are gray. This work divides client playback time t (in terms of time units) into multiple successive durations for ease of explanation.Figure 5
Segment downloading using client bandwidth2b.ForT0≤t≤nk-2-1, the client merely receives segments from channels C1 to Ck-2 because the client starts the segment downloading on channel Ck-1 at time unit nk-2, as shown in Figure 5. According to Step 1 of segment downloading on the client side, the client uses two-channel bandwidth to load segments in this period.Fornk-2≤t≤nk-1-1, the client receives segments only from channels Ck-2 and Ck-1 because the client finishes receiving segments from channel C1 to Ck-3 before time unit nk-2 and starts downloading segments on channel Ck at time unit nk-1, as indicated in Figure 5.Fornk-1≤t, the client simply receives the remaining segments from channels Ck-1 and Ck because the segment downloading on channel Ck-2 completes at time unit nk-1-1.Accordingly, an FiB+ client can download segments using two-channel bandwidth.


## 3.2.1. Continuous Playback

To keep on-time video delivery, the study in [7] indicates that a video server must broadcast a segment Sj on a channel Ci at least once in every j time units. For FiB+, a server transmits a segment Sj once every ni time units, where ni+1-1≤j≤ni+2-2. This paper thus needs to prove j≥ni. We then evaluate
(4)j-ni≥(ni+1-1)-ni,duetoni+1-1≤j=ni-1-1≥0.For FiB+, the segment broadcasting frequency is large enough to let clients receive video data in time.


## 3.2.2. Two-Channel Bandwidth Demand

From the previous analysis in Figure4, we make a temporal-channel map of segment downloading for each channel, as indicated in Figure 5. In this figure, segments downloaded and played by a client are gray. This work divides client playback time t (in terms of time units) into multiple successive durations for ease of explanation.Figure 5
Segment downloading using client bandwidth2b.ForT0≤t≤nk-2-1, the client merely receives segments from channels C1 to Ck-2 because the client starts the segment downloading on channel Ck-1 at time unit nk-2, as shown in Figure 5. According to Step 1 of segment downloading on the client side, the client uses two-channel bandwidth to load segments in this period.Fornk-2≤t≤nk-1-1, the client receives segments only from channels Ck-2 and Ck-1 because the client finishes receiving segments from channel C1 to Ck-3 before time unit nk-2 and starts downloading segments on channel Ck at time unit nk-1, as indicated in Figure 5.Fornk-1≤t, the client simply receives the remaining segments from channels Ck-1 and Ck because the segment downloading on channel Ck-2 completes at time unit nk-1-1.Accordingly, an FiB+ client can download segments using two-channel bandwidth.


## 4. Performance Analysis and Comparison

When a client just misses segmentS1 of a requested video, the maximum waiting time δ equals the access time of the segment from the first channel. Thus, δ=L/N=L/∑p=1knp, the same as that of FiB. According to the previous studies [15, 17], this work has calculated the values of N offered by these schemes at different numbers of channels, as listed in Table 2. The larger the value is, the smaller the waiting time is. The table reveals that FiB and FiB+ yield far bigger values than other schemes. Figure 6 shows maximum waiting time versus server channels. FiB and FiB+ thus achieve much smaller waiting time than SkB and CCA+ under two-channel client bandwidth. For example, when the server bandwidth equals 10 channels, FiB and FIB+ reduce the broadcast latency to less than 32 seconds. By contrast, SkB and CCA+ incur more than 51 and 48 seconds, respectively.Table 2
The values ofN offered by different schemes.
k
1
2
3
4
5
6
7
8
9
10
FiB/FiB+
1
3
6
11
19
32
53
87
142
231
SkB
1
3
5
10
15
27
39
64
89
141
CCA+2
1
3
5
10
15
27
39
64
89
149Figure 6
Maximum waiting time incurred on new clients at different numbers of channels (L=120 minutes).Before analyzing the entire buffer requirements, we first investigate the number of the buffered segments when a client performs segment downloading on a single channelCi.Lemma 1.
LetB(i,t) be the function of the number of the segments buffered by an FiB+ client on channel Ci at the tth time unit.(5a)For1≤i≤k-2,{B(i,t)=0,t<ni-1,B(i,t)=t-ni-1+1,ni-1≤t≤ni+1-2,B(i,t)=ni+2-2-t,ni+1-2<t≤ni+2-2,B(i,t)=0,ni+2-2<t.(5b)Fori=k-1ork,{B(i,t)=0,t<ni-1,B(i,t)≤⌊t-ni-1+22⌋,ni-1≤t≤ni+1-2,B(i,t)≤⌊ni2⌋,ni+1-2<t≤ni+2-2-⌈ni2⌉,B(i,t)≤ni+2-2-t,ni+2-2-⌈ni2⌉<t≤ni+2-2,B(i,t)=0,ni+2-2<t.Proof.
See AppendixB.Equation (5b) shows that a client buffers at most ⌊ni/2⌋ segments from channel Ci for i=k-1 or k. On the other hand, an FiB client needs to buffer ni-1 segments [18]. Such a difference leads to the result that FiB+ requires much smaller buffering space.Theorem 2.
LetB(t) be the maximum number of segments buffered by an FiB+ client. Then, B(t)≤⌈nk-1/4⌉+⌊nk/2⌋.Proof.
See AppendixC.Due tolimi→∞(ni+1/ni)≈((1+5)/2) [22] and N=nk+2-2, limk→∞((⌈nk-1/4⌉+⌊nk/2⌋)/N)≈0.25. This result indicates that an FiB+ client can buffer only 25% of video size, like RFB. We used the Perl language to implement a simulator, which could estimate the buffer requirements for FiB+. The results are listed in Table 3. The buffer size required by FiB+ is quite close to the bound when k≥6. Because FiB has to buffer nk-1 segments, we can derive the buffer reduction rate of FiB+ versus FiB as follows: limk→∞(1-(⌈nk-1/4⌉+⌊nk/2⌋)/(nk-1))≈0.345. FiB+ can reduce buffer requirements by 34.5%, when compared with FiB. Table 3 shows that with the growth of k, the reduction rate is close to the bound. For example, for k=10, an FiB client buffers 38.1% of video size. By contrast, an FiB+ client buffers only 25.1%. The reduction rate is 34.1%. According to the previous studies [15, 17], this work presents the buffer sizes required by different broadcasting schemes at different numbers of server channels, as indicated in Figure 7. For k>3, the FiB+ scheme outperforms all the schemes.Table 3
Comparison of buffering space in the percentage of video size usingk server channels.
k
1
2
3
4
5
6
7
8
9
10
FiB (%)
0
33.3
33.3
36.4
36.8
37.5
37.7
38
38
38.1
FiB+ (%)
0
33.3
33.3
27.3
26.3
25
24.5
25.3
25.4
25.1
Reduction rate (%)
0
0
0
25
28.6
33.3
35
33.3
33.3
34.1Figure 7
Comparison of required buffers.


## 5. Conclusions

With the advance of mobile computing technology, many clients access VOD services through their mobile devices. Delivering videos under rather restricted client resources is increasingly important. To fulfill this requirement, several schemes, such as SkB, FiB, and CCA+, are proposed to allow a client to watch a video using two-channel bandwidth. Extending FiB, this work devises FiB+, which exhibits the merits of small client waiting time and buffering space. The scheme still guarantees on-time video delivery under two-channel receiving bandwidth. According to the performance analysis, FiB+ yields the minimum waiting time and requires smaller client buffer size, when compared with most existing schemes.



---

*Source: 930316-2013-04-22.xml*