在點對點網路(peer-to-peer network)中從事即時的影像串流分享等應用，漸漸受到愈來愈多的重視。在此議題上面，一項重要的研究課題是，各個節點(peer)如何即時的決定向那些鄰居節點索取即將播出的影像資料，以令整體播出的影像品質能提高，此一問題主要是排程問題，在需求端與供給端如何配合，以達成資源的善用。由於大部分情況下，各個節點所能擁有鄰居的上傳頻寬不一，造成並不是每個節點都能順利的接收到所有的影像資料，用可調式視訊編碼(layer coding)將原始影片編碼後，接收端可依自己的頻寬狀況調整索取適當的影像品質。 目前提出的排程方法多基於影像各層的資料區塊大小是同樣(uniform)的假設之上，但事實上，各層資料區塊不同大小(non-uniform)才更符合現實的情形。
針對此問題，我們是第一個考量資料區塊大小不同的研究。而我們的排程演算法，主要的貢獻是針對各資料區塊的稀罕性(rarity)、時效性(time emergency)、以及區塊所屬層的狀況(layer property)，發展一套具有動態特性的算法給予權重，為各節點評定所需區塊的分數，進而讓分數較高的區塊有較多機會優先被傳送；最後，為了更貼近實際情況，我們提出一套分散式的演算法，以解決前述的問題。模擬的結果顯示我們的方法在異質性資料區塊的情形下能明顯達成更佳的效能，有效利用有限的頻寬，提升串流播放的品質。

During recent years, the Internet has witnessed a rapid growth of data-driven (or swarming based) peer-to-peer (P2P) media streaming. In these applications, an important issue is the data scheduling method which defines how each node requests the media streaming data from its neighbors. In most streaming systems, peers are likely to have heterogeneous uplink/downlink bandwidths and this leads to the fact that each peer may receive different streaming quality. Layered (or scalable) streaming in P2P networks is recently proposed to address the heterogeneity of peer network bandwidth problem. However, to the best of our knowledge, all existing works have assumed that different layers have uniform streaming rate; but, the nonuniform streaming rate is more practical for real world application. In this thesis, we present an on-demand streaming scheduling algorithm which is able to deal with nonuniform layer rate. We based on data-driven block scheduling concept that raw video content is encoded into several layers and each layer is further partitioned into blocks within a specific time duration. After that, we define a priority function which can adaptively adjust the priority for each desired block of each node according to the importance of a block, such as the block rarity, emergency caused by playback time approaching, and the layer property. We prove that maximizing the priority sum of each node under bandwidth constraints is a NP-complete problem, in addition we develop a heuristic global and distributed scheduling algorithm to improve the quality of received video. Experimental results show that our approach outperforms other existing schemes. Our method could improve the goodput by up to 19 percent and 27 percent as compare to Min Cost and Round Robin method, respectively.

[1] Z. Xinyan, L. Jiangchuan, L. Bo, and Y. S. P. Yum, \Coolstreaming/donet: a
data-driven overlay network for peer-to-peer live media streaming," in Proceed-
ings of the 24th Annual Joint Conference of the IEEE Computer and Commu-
nications Societies. INFOCOM 2005, vol. 3, pp. 2102{2111, 2005.
[2] V. Venkataraman, K. Yoshida, and P. Francis, \Chunkyspread: Heterogeneous
unstructured tree-based peer-to-peer multicast," in Proceedings of the 14th
IEEE International Conference on Network Protocols. ICNP 2006, pp. 2{11,
2006.
[3] V. Vishnumurthy and P. Francis, \On heterogeneous overlay construction and
random node selection in unstructured p2p networks," in Proceedings of the
25th IEEE International Conference on Computer Communications. INFO-
COM 2006, pp. 1{12, 2006.
[4] J. Liang and K. Nahrstedt, \Randpeer: Membership management for qos sen-
sitive peer-to-peer applications," in Proceedings of the 25th IEEE International
Conference on Computer Communications. INFOCOM 2006., pp. 1{10, 2006.
[5] P. Vinay, K. Kapil, T. Karthik, S. Vinay, and A. E. Mohr, \Chainsaw: Elim-
inating trees from overlay multicast," in Proceedings of the 4th International
Workshop on International workshop on Peer-To-Peer Systems. IPTPS 2005,
vol. 3640 LNCS, pp. 127{140, 2005.
[6] M. Zhang, J.-G. Luo, L. Zhao, and S.-Q. Yang, \A peer-to-peer network for live
media streaming using a push-pull approach," in Proceedings of the 13th Annual
ACM International Conference on Multimedia, pp. 287{290, ACM, 2005.
[7] N. Magharei and R. Rejaie, \Prime: Peer-to-peer receiver-driven mesh-based
streaming," in Proceedings of the 26th IEEE International Conference on Com-
puter Communications. INFOCOM 2007, pp. 1415{1423, 2007.
42
[8] R. Rejaie and A. Ortega, \Pals: Peer-to-peer adaptive layered streaming,"
in Proceedings of the 13th International Workshop on Network and Operating
Systems Support for Digital Audio and Video, pp. 153{161, ACM, 2003.
[9] X. Xin, S. Yuanchun, G. Yuan, and Z. Qian, \Layerp2p: A new data scheduling
approach for layered streaming in heterogeneous networks," in Proceedings of
the 28th IEEE International Conference on Computer Communications. INFO-
COM 2009, pp. 603{611, 2009.
[10] V. N. Padmanabhan, H. J. Wang, P. A. Chou, and K. Sripanidkulchai, \Dis-
tributing streaming media content using cooperative networking," in Proceed-
ings of the 12th International Workshop on Network and Operating Systems
Support for Digital Audio and Video, pp. 177{186, ACM, 2002.
[11] T. Duc A., H. Kien, and D. Tai, \A peer-to-peer architecture for media stream-
ing," IEEE Journal on Selected Areas in Communications, vol. 22, no. 1,
pp. 121{133, 2004.
[12] M. Hefeeda, A. Habib, B. Botev, D. Xu, and B. Bhargava, \Promise: Peer-
to-peer media streaming using collectcast," in Proceedings of the 11th ACM
International Conference on Multimedia, pp. 45{54, ACM, 2003.
[13] N. Magharei and R. Rejaie, \Understanding mesh-based peer-to-peer stream-
ing," in Proceedings of the 2006 International Workshop on Network and Op-
erating Systems Support for Digital Audio and Video, pp. 1{6, ACM, 2006.
[14] L. Zongpeng, L. Baochun, J. Dan, and L. Lap Chi, \On achieving optimal
throughput with network coding," in Proceeedings of the 24th Annual Joint
Conference of the IEEE Computer and Communications Societies. INFOCOM
2005, vol. 3, pp. 2184{2194, 2005.
[15] C. Huicheng, Z. Qian, J. Juncheng, and S. Xuemin, \E cient search and
scheduling in p2p-based media-on-demand streaming service," IEEE Journal
on Selected Areas in Communications, vol. 25, no. 1, pp. 119{130, 2007.
[16] Z. Jin, Y. Fan, Z. Qian, and Z. Zhensheng, \Mmc04-2: On improving the
throughput of media delivery applications in heterogeneous overlay network,"
43
in Proceedings of IEEE Global Telecommunications Conference. GLOBECOM
2006., pp. 1{6, 2006.
[17] C. Gkantsidis and P. R. Rodriguez, \Network coding for large scale content
distribution," in Proceedings of the 24th IEEE Annual Joint Conference on
Computer and Communications Societies. INFOCOM 2005, vol. 4, pp. 2235{
2245, 2005.
[18] Z. Meng, X. Yongqiang, Z. Qian, S. Lifeng, and Y. Shiqiang, \Optimizing
the throughput of data-driven peer-to-peer streaming," IEEE Transactions on
Parallel and Distributed Systems., vol. 20, no. 1, pp. 97{110, 2009.
[19] G. Kowalski and M. Hefeeda, \Empirical analysis of multi-sender segment trans-
mission algorithms in peer-to-peer streaming," in Proceedings of the 11th IEEE
International Symposium on Multimedia. ISM 2009., pp. 243{250, 2009.
[20] J. Li and C. K. Yeo, \Content and overlay-aware scheduling for peer-to-peer
streaming in
uctuating networks," ACM Journal on Network and Computer
Applications, vol. 32, no. 4, pp. 901{912, 2009.
[21] A. R. Bharambe, C. Herley, and V. N. Padmanabhan, \Analyzing and im-
proving a bittorrent networks performance mechanisms," in Proceedings of the
25th IEEE International Conference on Computer Communications. INFO-
COM 2006, pp. 1{12, 2006.
[22] L. Bracciale, F. L. Piccolo, D. Luzzi, and S. Salsano, \Opss: An overlay peer-to-
peer streaming simulator for large-scale networks," ACM SIGMETRICS Per-
formance Evaluation Review, vol. 35, no. 3, pp. 25{27, 2007.
4