伴隨網際網路頻寬與多媒體技術之快速成長，隨選視訊服務已日益普及。鑑於典型之隨選視訊系統係藉由提供每一位用戶一條專屬之傳輸串流(stream)來達成，高頻寬需求即成為此類服務瓶頸之所在，廣播機制為解決此問題最有效率之方式。現今提出之廣播機制，大部分著眼於減少用戶等待時間或降低其儲存空間，惟影片之熱門程度會隨時間而有所變化，且用戶之頻寬能力亦有所不同，有鑑於此，本論文即在探討如何設計出一廣播協定，使內容供應商既可隨影片之熱門程度來調整播放該部影片所需之頻寬，同時亦可使異質用戶皆能完整且不受中斷地觀賞該部影片。
吾人首先提出一廣播機制，稱之為multi-base BroadCatch(以下簡稱MBC)。該機制不但可滿足使用不同網路頻寬連線之異質用戶，吾人並在其上建構出無縫隙頻寬切換協定，透過該協定，內容供應商即可依影片之熱門程度調整配置予它之頻寬。此外，使用MBC廣播機制進行頻寬切換時，內容供應商無須支付額外之成本。相較於先前提出之BroadCatch廣播機制 [60]，對頻寬能力較弱之用戶而言，MBC廣播機制大幅降低其等待時間及所需之儲存空間，與此同時，對頻寬能力強之用戶而言，其等待時間雖較BroadCatch為差，卻所差無幾。吾人最後提出一頻寬配置策略，使內容供應商能依據系統中所有影片之熱門程度來決定配置給每部影片之頻寬大小，從而妥善運用既有之頻寬資源。
吾人接著針對Fast廣播機制(以下簡稱FBR) [8] 之異質性進行全面之分析。先前雖已有學者在該機制上建構出無縫隙頻寬切換協定 [62,65]，卻無人探討其是否適用於異質用戶之隨選視訊服務環境。
本篇論文首先提出一遞迴公式，藉由該公式，可得出在不同時間要求服務之所有異質用戶，其最低之頻寬需求及最長等待時間。此外，吾人亦將FBR通式化，提出一稱之為GFBR-x之廣播機制，並分析比較其效能。相較於BroadCatch，對頻寬能力較弱之用戶而言，GFBR-2廣播機制大幅降低其等待時間及所需之儲存空間，與此同時，對頻寬能力強之用戶而言，其等待時間雖較BroadCatch為差，卻所差無幾。

With the accelerated growth of internet bandwidth and advances in multimedia
technology, video-on-demand (VOD) services are growing in popularity. To achieve
the VOD system, the simplest way is to assign a dedicated channel to each client and
allow the client having a complete control over the video session. However, such a
system places significant loads on server bandwidth resources due to the transmission
of sizable data. To relieve the stress of the high demand on bandwidth, solutions
based on broadcasting schemes are possible alternatives to the true VOD scheme.
Many broadcasting schemes proposed so far try to reduce either clients’ startup
latency or buffering space. However, due to the reason that the popularity of a video
usually changes with time and clients might employ heterogeneous terminals with
different communication capabilities, we focus on broadcasting schemes that not only
allow service provider to adjust bandwidth allocated to one single video according
to its popularity dynamically and seamlessly but also allow clients to choose among
a range of bandwidths to download a video at the cost of their startup latency.
In this dissertation, we first propose a heterogeneous broadcasting scheme and its
seamless channel transition protocols. The scheme, called the multiple-base Broad-
Catch scheme (MBC), is designed by modifying the BroadCatch scheme [61] to
allow an arbitrary number of base channels defined in BroadCatch. Compared with
the BroadCatch scheme, the MBC scheme has zero heterogeneous scalability when
channel transition is performed. With zero heterogeneous scalability, new clients can
benefit from newly added server channels without paying any extra cost. As compared
with BroadCatch, our results show that MBC greatly reduces startup laten-
I
cies for low-end clients while slightly sacrifices those for high-end clients. Maximum
buffering requirement is greatly reduced as well. Moreover, given a set of popular
videos, we present a channel allocation policy which allows the service provider to
be capable of determining the number of channels assigned to each video according
to the popularity of all videos so as to make the most benefit from the broadcasting
service.
Secondly, we provide a thorough analysis of the heterogeneous behavior of the
Fast broadcasting and receiving scheme (abbreviated as FBR scheme). Through a
derived analytical formula, we deduce client bandwidth requirement for any given
time slot, worst startup latencies for all heterogeneous clients, and average client
bandwidth requirement together with heterogeneous scalability. Moreover, we propose
a generalized FBR scheme called the GFBR-x scheme which is derived from the
FBR scheme by keeping the number of segments broadcast on the last x+1 channels
to be the same. Performances among the FBR, GFBR-2, and BroadCatch schemes
are also evaluated. First, as compared with the BroadCatch scheme, the GFBR-2
scheme not only reduces startup latencies by around 25% s 50% for most low-end
clients but also provides relatively acceptable startup latencies for some high-end
clients. Second, the FBR and GFBR schemes have a smaller heterogeneous

[1] K. C. Almeroth and M. H. Ammar, The use of multicast delivery to provide
a scalable and interactive video-on-demand service, IEEE Journal on Selected
Areas in Communications, vol. 14, no. 6, 1996, pp. 1110-1122.
[2] A. Dan, P. Shahabuddin, D. Sitaram, and D. Towsley, Channel allocation under
batching and VCR control in video-on-demand systems, Journal of Parallel
and Distributed Computing, vol. 30, no. 2, 1995, pp. 168-179.
[3] A. Dan, D. Sitaram, and P. Shahabuddin, Dynamic batching policies for an
on-demand video server, Multimedia Systems, vol. 4, no.3, 1996, pp. 112-121.
[4] S. W. Carter and D. D. E. Long, Improving video-on-demand server efficiency
through stream tapping, In Proc. of the Sixth International Conf. on Computer
communications and Networks (ICCCN ’97), Las Vegas, NV, USA, 1997, pp.
200-207.
[5] S. W. Carter and D. D. E. Long, Improving bandwidth efficiency on video-ondemand
servers, Computer Networks, vol. 31, no. 1-2, 1999, pp. 111-123.
[6] S. W. Carter, D. D. E. Long, and J. -F. Pˆaris, An efficient implementation
of interactive video-on-demand, In Proc. of the 8th International Symposium
99
on Modeling, Analysis and Simulation of Computer and Telecommunication
Systems, San Francisco, CA, 2000, pp. 172-179.
[7] K. A. Hua, Y. Cai, and S. Sheu, Patching: A multicast technique for true
video-on-demand services, Proc. 6th ACM Multimedia Conf., 1998, pp. 191-
200.
[8] L. S. Juhn and 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.
[9] J. F. Pˆaris, S. W. Carter, and D. D. Long, “A hybrid broadcasting protocol
for video on demand,” in SPIE Conf. Multimedia Computing and Networking,
1999, San Jose, CA, Jan. 1999, pp. 317-326.
[10] J. F. Pˆaris, “A simple low-bandwidth broadcasting protocol,” In International
Conference on Computer Communication and Network, 1999, pp. 118-123.
[11] J. F. Pˆaris, “A fixed-delay broadcasting protocol for video-on-demand,” Proc.
of the 10th International Conf. on Computer Communications and Networks
(ICCCN’01), Oct. 2001, pp. 418-423.
[12] J. F. Pˆaris, “A simple but efficient broadcasting protocol for video-ondemand,”
Proc. of the 24th International Performance of Computers and
Communication Conference (IPCCC 2005), Phoenix, AZ, April 2005, pp. 167-
174.
100
[13] Y. C. Tseng, M. H. Yang, and 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.
[14] Y. W. Chen, “An enhanced recursive frequency splitting broadcasting algorithm
for near video-on-demand services,” Information Processing Letters, vol.
92, pp. 299-302, 2004.
[15] L. S. Juhn and L. M. Tseng, “Harmonic broadcasting for video-on-demand
service,” IEEE Transactions on Broadcasting, vol. 43, no. 1, pp. 268-271, 1997.
[16] L. S. Juhn and L. M. Tseng, “Enhanced harmonic data broadcasting and
receiving scheme for popular video service,” IEEE Transactions on Consumer
Electronics, vol. 44, pp. 343-346, 1998.
[17] J. F. Pˆaris, S. W. Carter, and D.D. E. Long, “Efficient broadcasting protocols
for video on demand,” in Proceedings of the 6th International Symposium
on Modeling, Analysis and Simulation of Computer and Telecommunication
Systems, Montreal, Canada, July 1998, pp. 127-132.
[18] J. F. Pˆaris, S. W. Carter, and D.D. E. Long, “A low bandwidth broadcasting
protocol for video on demand,” Proc. Int’l Conf. on Computer Communications
and Networks, Oct. 1998, pp. 690-697.
[19] H. C. Yang, H. F. Yu, L. M. Tseng and Y. M. Chen, “Interleaving harmonic
broadcasting and receiving scheme with loss-anticipation delivery,” Proceedings
of IEEE Symposium on Computers and Communications, vol. 2, 28 June-
1 July 2004, pp. 600-605.
101
[20] L. S. Juhn and 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.
[21] S. Chand and H. Om, “Modified staircase data broadcasting scheme for popular
videos,” IEEE Transactions on Broadcasting, vol. 48, no. 4, pp. 274-280,
Dec. 2002.
[22] G. Zhiqi and Y. Songyu, “Conservative staircase data broadcasting protocol
for video on demand,” IEEE Transactions on Consumer Electronics, vol. 52,
no. 2, pp. 363-370, May 2003.
[23] H. C. Yang, H. F. Yu, L. M. Tseng and Y. M. Chen, “Interleaving staircase
broadcasting and receiving scheme with loss-anticipation delivery,” Proceedings
of International Conference on Internet Computing, Las Vegas, Nevada,
USA, June 2004.
[24] H. C. Yang, H. F. Yu, L. M. Tseng and Y. M. Chen, “An efficient staircaseharmonic
scheme for broadcasting popular videos,” 2005 IEEE Consumer
Communications and Networking Conference, 2005, pp. 122-127.
[25] S. Chand and H. Om, “Generalized conservative staircase data broadcasting
protocol for video-on-demand,” IEEE Transactions on Consumer Electronics,
vol. 49, no. 4, pp. 1173-1077, Nov. 2006.
[26] Y. W. Chen and C. Y. Hsieh, “An interleaving slotted-polyharmonic-staircase
broadcasting protocol for near video-on-demand services,” Computer Communications,
vol. 30, no. 4, pp. 807-817, 2007.
102
[27] Y. W. Chen and D. M. Huang, “Advanced generalized conservative staircase
method for broadcasting popular movies,” IEEE Transactions on Consumer
Electronics, vol. 54, no. 3, pp. 1029-1037, August 2008.
[28] H. F. Yu, H. C. Yang, and L. M. Tseng, “Reverse fast broadcasting (RFB) for
video-on-demand applications,” IEEE Transactions on Broadcasting, vol. 53,
no. 1, pp. 103-111, 2007.
[29] H. F. Yu, “Hybrid broadcasting with small buffer demand and waiting time
for video-on-demand applications,” IEEE Transactions on Broadcasting, vol.
54, no. 2, pp. 304-311, 2008.
[30] H. F. Yu, P. H. Ho, and H. C. Yang, “Generalized sequence-based and reverse
sequence-based models for broadcasting hot videos,” IEEE Transactions on
Multimedia, vol. 11, no. 1, pp. 152-165, 2009.
[31] T. Chiueh and C. Lu, “A periodic broadcasting approach to video-on-demand
service,” International Society for Optical Engineering, vol. 2615, pp. 162-169,
Oct 1995.
[32] K. A. Hua and S. Sheu, “Skyscraper broadcasting: a new broadcasting scheme
for metropolitan video-on-demand systems,” In ACM SIGCOMM’97, vol. 27,
pp. 89-100, 1997.
[33] K. A. Hua, Y. Cai and S. Sheu, “Exploiting client bandwidth for more efficient
video broadcast,” In Proc. 1998 International Conference Computer
Communications and Network, pp. 848-856, 1998.
103
[34] J. -F. Pˆaris and D. D. E. Long, “Limiting the receiving bandwidth of broadcasting
protocols for video-on-demand,” Proc. Euromedia 2000 Conference,
May 2000, pp. 107-111.
[35] A. Hu, “Video-on-demand broadcasting protocols: a comprehensive study,”
IEEE INFOCOM, 2001, pp. 508-517.
[36] L. Gao, J. Kurose and D. Towsley, “Efficient schemes for broadcasting popular
videos,” Multimedia Systems, vol. 8, pp. 284-294, 2002.
[37] E. Yan and T. Kameda, “Generalized fibonacci broadcasting: An efficient
VOD broadcasting scheme with user bandwidth limit,” Discrete Applied Mathematics,
vol. 154, pp.2418-2429, 2006.
[38] C. J. Wu, Y. W. Chen, J. H. Yan, and Y. L. Wang, “Seamless channel transition
for slotted generalized fibonacci broadcasting,” Multimedia Systems, vol.
13, no. 3, September 2007, pp. 223-233.
[39] H. F. Yu, Y. N. Chen, H. C. Yang, Z. Y. Yang and L. M. Tseng, “An efficient
scheme for broadcasting popular videos at low buffer demand,” Computer
Communications, vol. 31, no. 10, pp. 2270-2279, 2008.
[40] Y. W. Chen and J. Uemura, “An interleaving crescent broadcasting protocol
for near video-on-demand services,” Multimedia Tools and Applications,
vol.49, no.2, pp. 299-321, August 2010.
[41] Z. Fei, I. Kamel, S. Mukherjee, and M. H. Ammar, “Providing interactive functions
for staggered multicast near video-on-demand systems,” in Proceedings of
104
the IEEE International Conference on Multimedia Computing and Systems’99,
vol. 2, 1999, pp. 949-953.
[42] J. -F. Pˆaris, “An interactive broadcasting protocol for video-on-demand,” Proceedings
of the 20th IEEE International Performance, Computing, and Communications
Conference (IPCCC 2001), Phoenix, AZ, April 2001, pp. 347-353.
[43] J. B. Kwon and H. Y. Yeom, “Providing VCR functionality in staggered video
broadcasting,” IEEE Transactions on Consumer Electronics, vol. 48, no. 1,
pp. 41-48, 2002.
[44] J. B. Kwon and H. Y. Yeom, “VCR-oriented video broadcasting for near videoon-
demand services,” IEEE Transactions on Consumer Electronics, vol. 49,
no. 4, pp. 1106-1113, 2003.
[45] Z. Fei, M. H. Ammar, I. Kamel and S. Mukherjee, “An active buffer management
technique for providing interactive functions in broadcast video-ondemand
systems,” IEEE Transactions on Multimedia, vol. 7, no. 5, pp. 942-
950, 2005.
[46] W. T. Poon, K. T. Lo and J. Feng, “Provision of continuous VCR functions
in interactive broadcast vod systems,” IEEE Transactions On Broadcasting,
vol. 51, no. 4, pp. 460-472, 2005.
[47] Y. W. Chen and Y. T. Lee, “A broadcasting scheme with supporting VCR-like
forward function for near video-on-demand system,” Computer Communications,
vol. 29, no. 2, pp. 257-267, 2006.
105
[48] T. Yoshihisa, M. Tsukamoto, and S. Nishio, “A scheduling scheme for continuous
media data broadcasting with a single channel,” IEEE Transactions on
Broadcasting, vol. 52, no. 1, pp. 1-10, march 2006.
[49] T. Yoshihisa, M. Tsukamoto, and S. Nishio, “A scheduling protocol for continuous
media data broadcasting with large-scale data segmentation,” IEEE
Transactions on Broadcasting, vol. 53, no. 4, pp. 780-788, Dec. 2007.
[50] Y. W. Chen and C. Y. Hsieh, “SingBroad: A scheduling scheme for broadcasting
continuous multimedia data over a single channel,” Computer Networks,
vol. 53, no. 9, pp. 1546-1554, June 2009.
[51] B. S. Wu, C. C. Hsieha and Y. W. Chen, “A reverse-order scheduling scheme
for broadcasting continuous multimedia data over a single channel,” IEEE
Transactions on Broadcasting, accepted, 2011.
[52] D. L. Eager, and M. K. Vernon, “Dynamic skyscraper broadcast for video-ondemand,”
Proc. 4th Int. Workshop on Advances in Multimedia Information
Systems, vol. 1508, Sep. 1998, pp. 18-32.
[53] J. -F. Pˆaris, F. S.W. Carter, and D. D. E. Long, “A universal distribution
protocol for video-on-demand,” in Proc. Int. Conf. on Multimedia and Expo
2000, July 2000, pp. 657-664.
[54] P. K. Sahoo, and J. -P. Sheu, “An efficient channel allocation technique for
multiple videos-on-demand,” Multimedia Tools and Applications, vol. 20, no.
1, pp. 67-81, May 2003.
106
[55] L. -S. Juhn and L. -M. Tseng, “Adaptive fast data broadcasting scheme for
video-on-demand service,” IEEE Transactions on Broadcasting, vol. 44, no. 2,
pp. 182-185, June 1998.
[56] Q. Zhang and J.-F. Pˆaris, “A channel-based heuristic distribution protocol for
video-on-demand,” IEEE International Conference on Multimedia and Expo
2002, vol. 1, 2002, pp. 245-248.
[57] H. Kim and H. Y. Yeom, “Dynamic scheme transition adaptable to variable
video popularity in a digital broadcast network,” IEEE Transactions on Multimedia,
vol. 11, no. 3, pp. 486-493, April 2009.
[58] N. Carlsson, A. Mahanti, Z. Li and D. Eager, “Optimaized peridic broadcast
of nonlinear media,” IEEE Transactions on Multimedia, vol. 10, no. 5, pp.
871-884, August 2008.
[59] Y. Gotoh, T. Yoshihisa, M. Kanazawa, and Y. Takahashi, “A broadcasting
scheme for selective contents considering available bandwidth,” IEEE Transactions
on Broadcasting, vol. 55, no. 2, pp. 460-467, June 2009.
[60] M. A. Tantaoui, “Interactivity and user-heterogeneity in on demand broadcast
video,” Ph.D. dissertation, University of Central Florida, 2004.
[61] M. A. Tantaoui, K. A. Hua, and T. T. Do, “BroadCatch: a periodic broadcast
technique for heterogeneous video-on-demand,” IEEE Transctions on Broadcasting,
vol. 50, no. 3, pp. 289-301, 2004.
107
[62] C. T. Lin and J. W. Ding, “CAR: A low latency video-on-demand broadcasting
scheme for heterogeneous receivers,” IEEE Transactions on Broadcasting, vol.
52, no. 3, pp. 336-349, September 2006.
[63] Y. C. Tseng, M. H. Yang, C. M. Hsieh, W. H. Liao, and J. P. sheu, “Data
broadcasting and seamless channel transition for highly demanded videos,”
IEEE Transactions on Communications, vol. 49, no. 5., May 2001, pp. 863-
874.
[64] Y. C. Tseng, Y. C. Chueh, and J. P. Sheu, “Seamless channel transition for
the staircase video broadcasting scheme,” IEEE Transactions on Networking,
vol. 12, no. 3, June 2004, pp. 559-571.
[65] S. Chand and H. Om, “Seamless channel transition using Bespoke broadcasting
Scheme for video-on-demand service,” IEEE Transactions on Consumer
Electronics, vol. 51, no. 4, November 2005, pp. 1313-1318.
[66] W. D. Chien, Y. S. Yeh, and J. S.Wang, “Practical channel transition for near-
VOD services,” IEEE Transactions on Broadcasting, vol. 51, no. 3, September
2005, pp. 360-365.
[67] W. D. Chien, K. C. Yang, and J. S. Wang, “Seamless channel transition for
pyramid-based near-VOD services,” 2005 IEEE International Conference on
Multimedia and Expo. (ICME 2005), July 2005, pp. 161-164.
[68] Y. Guo, L. Gao, D. Towsley and S. Sen, “Smooth workload adaptive broadcast,”
IEEE Transactions on Multimedia, vol. 6, no. 2, April 2004, pp. 387-395.