臺灣博碩士論文加值系統

在Peer-to-Peer視訊串流研究中，Peer傳輸速度高度攪動是備受矚目的議題。目前有幾個著名的Mesh-based(又稱Data-driven或Pull-based)P2P串流協定，其中一部份，它們的傳輸協定是由BitTorrent這個P2P檔案分享協定修改而來。由於BitTorrent高效能P2P檔案傳輸的啟發，在本論文的第一部份，我們研究在標準BitTorrent協定上覆疊串流傳輸機制。在此研究中，我們提出一個實際經驗的P2P視訊串流系統WuKong，研究系統中各元件的串流傳輸演算法。WuKong不只承襲了BitTorrent的優勢，更增加了可適性視訊編碼技術的支援。我們提出步進式下載演算法，用來在異質Peer中平衡視訊品質與頻寬使用。此外，我們使用一個開放源碼的BitTorrent函式庫來實作WuKong，在實際系統上證明所研究之串流機制在異質裝置與可適性視訊編碼(SVC)上具有高度穩定性。同時也利用Simulation驗證在大量Peer下，系統的容量與即時程度。

在第二部份的研究中，我們研究BitTorrent Tracker的備援機制。在BitTorrent協定中，Tracker被用來記錄所有種子檔的Peer資料，是極為重要的元件。但因通常只有單一主機執行，一旦功能失效即會造成整個P2P網路無法運作。在此研究中，我們設計了一個高可用度中介層，讓BitTorrent Tracker採用Active-Standby的方式進行備援。在此我們提出了高效率Peer Database備援演算法，有效的降低因備份大量peer資料庫而耗用了Active Tracker的效能。

在論文的第三部份，我們研究在視訊伺服器有限頻寬條件下，P2P視訊串流系統的服務容量計算。也就是在Peer互相上傳分享下，系統能容納最多的Peer數目計算。我們利用Root節點為視訊來源的Multicast delivery tree推衍證明，要找到最佳的Routing tree來達到最大系統容量的問題是NP-hard。在此，我們提出一般化單一路由與多重路由網路建立演算法。模擬結果證明，在多重路由條件下，因有效利用較低上傳頻寬的Peer，所以在相同的系統條件下可支持更多的peer。另外，我們提出分散式演算法，針對Peer在挑選父節點時以演算法計算公式，同時比較上傳頻寬與累計延遲，進而有效提昇系統服務容量。

Many researches on peer-to-peer video streaming have focused on dealing with highly dynamic, high-churn P2P environment. There have been tremendous efforts and innovations in mesh-based (also known as data-driven or pull-based) P2P streaming protocols and some of them were modified from a P2P file sharing protocol, called BitTorrent. Inspired by the high performance on peer-to-peer file sharing of the BitTorrent, we propose a scheme for overlaying streaming mechanisms on the native BitTorrent protocol. In the first part of dissertation, we focus on a practical P2P video streaming system-WuKong and investigate the stream delivery algorithms for each component. WuKong not only takes advantages of the BitTorrent but also combines the video scalability of layered video coding. An adaptive layer-downloading process is investigated to balance between the video quality and bandwidth utilization on heterogeneous peers. WuKong is implemented on using an open-sourced library of the BitTorrent protocol and coding schemes of the Windows Media Video(WMV) and the Scalable Video Coding(SVC). We measured and compared the end-user quality of WuKong on heterogeneous peers in this system. In addition, we evaluated the effectiveness of WuKong with randomly peers that are joining and leaving. The results show that WuKong not only provides high quality P2P video streaming services but also supports different scaling abilities over heterogeneous devices.

In the second part of the dissertation, we focus on investigate a high-availability BitTorrent tracker. Entering and leaving of random peers will result in great variance of data availability in P2P networks, especially when multimedia streams require high priority to the immediate playback data. All peers must be able to receive the complete video segment before that playback. Therefore, the provision of the tracker in the P2P networks is to accurately track the status of each peer and so to maintain high data availability being considered functionally. Our work deliberates the redundant mechanism of BitTorrent tracker and designs a BT-like redundant tracker mechanism that is configured to this purpose, and presents the relative performance measure. The result shows that the proposed redundant tracker does not increase overheads and is able to upgrade stability to the playback operations in P2P streaming networks.

The capacity of P2P streaming systems, \textit{i.e.}, how many peers can be concurrently serviced by the system, depends on system configurations including network bandwidth, overlay network formation, QoS constraints, membership management, peer selection, subscribing/publishing scheduling, coding schemes, etc. Due to the complexity, there are not too many systematic studies on system capacity. The third part of the dissertation answers this question of our system. Based on flow concepts, we compare the capacity of single-tree P2P streaming systems and multiple-tree P2P streaming systems. We prove that finding the routing tree to maximize system capacity, no matter for either single-tree systems or multiple-tree systems, is NP-hard. Two generic network formation heuristics, one for single-tree topology and the other for multiple-tree topology, are proposed. Simulation results show that since multiple-tree topology can efficiently utilize upload bandwidth, the multiple-tree systems have potential to service more clients. Moreover, we exposed the bandwidth and delay constraint on achieving maximum system capacity. The centralized and distributed network formation heuristics were proposed. We compared the performance of our centralized and distributed heuristics with the maximum uplink/minimum delay first scheme. Simulation results showed that our algorithm can achieve higher system capacity, since the algorithms considered on both uplink capability and delay constraints.

Contents
List of Figures xi
List of Tables xiii
1 Introduction and Related Works 1
2 A Practical P2P Video Streaming System Overlaid on BitTorrent 8
2.1 P2P Streaming Overlay Mechanisms . . . . . . . . . . . . . . . . . 8
2.1.1 Video Head-end . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.2 Super-seed . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.3 Client-engine . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Analytical Comparison . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 System Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.1 System Deployment and Conguration . . . . . . . . . . . . 22
2.3.2 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.3 Window Size Analysis . . . . . . . . . . . . . . . . . . . . . 26
3 High-availability BitTorrent tracker 31
3.1 BitTorrent Protocol and Tracker . . . . . . . . . . . . . . . . . . . . 31
3.2 High Availability Tracker . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.1 High Availability Middleware . . . . . . . . . . . . . . . . . 33
3.2.2 High Availability BT-tracker . . . . . . . . . . . . . . . . . . 35
3.3 Measurement Results and Analysis . . . . . . . . . . . . . . . . . . 39
4 Capacity Analysis of P2P Streaming Systems 42
4.1 Generic Model of P2P Streaming Systems . . . . . . . . . . . . . . 42
4.2 System Capacity Estimation . . . . . . . . . . . . . . . . . . . . . . 44
4.2.1 Upload Bandwidth Constraint . . . . . . . . . . . . . . . . . 45
4.2.2 Single-tree Routing . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.3 Multiple-tree Routing . . . . . . . . . . . . . . . . . . . . . . 47
4.2.4 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 Maximizing the P2P Streaming System Capacity Under Delay Con-
straint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3.1 Centralized Heuristics . . . . . . . . . . . . . . . . . . . . . 53
4.3.2 Distributed Heuristics . . . . . . . . . . . . . . . . . . . . . 55
4.3.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . 60
5 Conclusion 64
Bibliography 66

[1] BitTorrent, Inc., \BitTorrent," http://www.bittorrent.com/.
[2] Wiki, \Bittorrent Protocol Specication v1.0,"
http://wiki.theory.org/BitTorrentSpecication.
[3] Ipoque, Inc., \Internet Study 2008/2009,"
http://www.ipoque.com/resources/internet-studies/internet-study-
2008 2009, 2009.
[4] B. Cohen, \Incentives build robustness in bittorrent," in The 1st Workshop
on Economics of Peer-to-Peer Systems, 2003.
[5] D. Qiu and R. Srikant, \Modeling and performance analysis of BitTorrent-
like peer-to-peer networks," in Proceedings of the 2004 ACM SIGCOMM
Computer Communication Review (ACM SIGCOMM 2004), 30 August - 3
September 2004, pp. 367{378.
[6] S. Saroiu, K. P. Gummadi, and S. D. Gribble, \Measuring and analyzing the
characteristics of Napster and Gnutella hosts," Multimedia Systems, vol. 9,
no. 2, pp. 170{184, 1 August 2003.
[7] S. A. Baset and H. G. Schulzrinne, \An Analysis of the Skype Peer-to-Peer
Internet Telephony Protocol," in Proceedings of the 25th IEEE International
Conference on Computer Communications (INFOCOM 2006), April 2006,
pp. 1{11.
[8] C. Dana, D. Li, D. Harrison, and C.-N. Chuah, \BASS: BitTorrent Assisted
Streaming System for Video-on-Demand," in Proceedings of the IEEE 7th
Workshop on Multimedia Signal Processing, 30 October - 2 November 2005,
pp. 1{4.
[9] A. Vlavianos, M. Iliofotou, and M. Faloutsos, \BiToS: Enhancing BitTorrent
for Supporting Streaming Applications," in Proceedings of the 25th IEEE
International Conference on Computer Communications (INFOCOM 2006),
April 2006, pp. 1{6.
[10] P. Shah and J.-F. P^aris, \Peer-to-Peer Multimedia Streaming Using BitTor-
rent," in Proceedings of the IEEE International Performance, Computing,
and Communications Conference (IPCCC 2007), April 2007, pp. 340{347.
[11] X. Zhang, J. Liu, B. Li, and T.-S. P. Yum, \CoolStreaming/DONet: A data-
driven overlay network for peer-to-peer live media streaming," in Proceedings
of the 24th Annual Joint Conference of the IEEE Computer and Communi-
cations Societies (IEEE INFOCOM 2005), 13-17 March 2005, pp. 2102{2111.
[12] PPLive, Inc., \PPLive," http://www.pplive.com.
[13] X. Hei, C. Liang, J. Liang, Y. Liu, and K. W. Ross, \A measurement study of
a large-scale P2P IPTV system," IEEE Transactions on Multimedia, vol. 9,
no. 8, pp. 1672{1687, December 2007.
[14] T. Wiegand, G. Sullivan, J. Reichel, H. Schwarz, and M. Wien, Joint Draft
ITU-T Rec. H.264 | ISO/IEC 14496-10 / Amd.3 Scalable video coding.
Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, Doc. JVT-
X201, July 2007.
[15] H. Schwarz, D. Marpe, and T. Wiegand, \Overview of the Scalable Video
Coding Extension of the H.264/AVC Standard," IEEE Transactions on Cir-
cuits and Systems for Video Technology, vol. 17, no. 9, pp. 1103{1120, Septem-
ber 2007.
[16] V. N. Padmanabhan, H. J. Wang, and P. A. Chou, \Resilient peer-to-peer
streaming," in Proceedings of the 11th IEEE International Conference on
Network Protocols (ICNP 2003), 4-7 November 2003, pp. 16{27.
[17] P. Baccichet, T. Schierl, T. Wiegand, and B. Girod, \Low-delay peer-to-peer
streaming using scalable video coding," in Packet Video 2007, November 2007,
pp. 173{181.
[18] M. Mushtaq and T. Ahmed, \Smooth Video Delivery for SVC Based Media
Streaming Over P2P Networks," in Proceedings of the 5th IEEE Consumer
Communications and Networking Conference, 2008 (CCNC 2008), January
2008, pp. 447{451.
[19] PPStream, Inc., \PPStream," http://www.ppstream.com.
[20] CCANTS, Inc., \TVants," http://www.ccants.com/.
[21] J. Jannotti, D. K. Giord, K. L. Johnson, M. F. Kaashoek, and J. James
W. O'Toole, \Overcast: reliable multicasting with an overlay network," in
Proceedings of the 4th conference on Symposium on Operating System Design
& Implementation (OSDI'00), 22-25 October 2000, pp. 197{212.
[22] Y. Chu, S. Rao, S. Seshan, and H. Zhang, \Enabling conferencing applications
on the internet using an overlay muilticast architecture," ACM SIGCOMM
Computer Communication Review, vol. 31, no. 4, pp. 55{67, October 2001.
[23] S. Ratnasamy, M. Handley, R. M. Karp, and S. Shenker, \Application-level
multicast using content-addressable networks," in Proceedings of the 3rd In-
ternational COST264 Workshop on Networked Group Communication (NGC
2001), 7-9 November 2001, pp. 14{29.
[24] S. Banerjee, B. Bhattacharjee, and C. Kommareddy, \Scalable application
layer multicast," in Proceedings of the 2002 Conference on Applications, Tech-
nologies, Architectures, and Protocols for Computer Communications (ACM
SIGCOMM '02), 19-23 August 2002, pp. 205{217.
[25] M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and
A. Singh, \SplitStream: High-bandwidth content distribution in a cooperative
environment," in The 2nd International Workshop on Peer-to-Peer Systems
(IPTPS '03), 20-21 February 2003.
[26] A. Rowstron and P. Druschel, \Pastry: Scalable, decentralized object loca-
tion and routing for large-scale peer-to-peer systems," in Proceedings of the
IFIP/ACM International Conference on Distributed Systems Platforms (Mid-
dleware 2001), 12-16 November 2001, pp. 329{350.
[27] M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron, \Scribe: A large-
scale and decentralized application-level multicast infrastructure," IEEE
Journal on Selected Areas in Communication (IEEE JSAC), vol. 20, no. 8,
pp. 1489{1499, October 2002.
[28] M. Zhang, L. Zhao, Y. Tang, J.-G. Luo, and S.-Q. Yang, \Large-scale live me-
dia streaming over peer-to-peer networks through global Internet," in Proceed-
ings of the ACM Workshop on Advances in Peer-to-Peer Multimedia Stream-
ing (P2PMMS'05), 11 November 2005, pp. 21{28.
[29] N. Magharei and R. Rejaie, \Understanding mesh-based peer-to-peer stream-
ing," in Proceedings of the 2006 International Workshop on Network and
Operating Systems Support for Digital Audio and Video (NOSSDAV 2006),
22-23 May 2006, pp. 1{6.
[30] X. Yang and G. de Veciana, \Service capacity of peer to peer networks," in
Proceedings of the 23th Annual Joint Conference of the IEEE Computer and
Communications Societies (IEEE INFOCOM 2004), 7-11 March 2004, pp.
2242{2252.
[31] T. Small, B. Liang, and B. Li, \Scaling laws and tradeos in peer-to-peer
live media streaming," in Proceedings of the 14th Annual ACM International
Conference on Multimedia (ACM MM 2006), 23-27 July 2006.
[32] S. Tewari and L. Kleinrock, \Analytical model for BitTorrent-based live
video," in Proceedings of the 4th IEEE Consumer Communications and Net-
working Conference (CCNC 2007), 11-13 January 2007, pp. 976{980.
[33] X. Jin, S.-H. G. Chan, W.-C.Wong, and A. C. Begen, \A Distributed Protocol
to Serve Dynamic Groups for Peer-to-Peer Streaming," IEEE Transactions
on Parallel and Distributed Systems, vol. 21, no. 2, pp. 216{228, February
2010.
[34] J. W. Jiang, S. Zhang, M. Chen, and M. Chiang, \Minimizing streaming
delay in homogeneous peer-to-peer networks," in Proceedings of the IEEE
International Symposium on Information Theory Proceedings, 2010. (ISIT
2010), 13-18 June 2010, pp. 1783{1787.
[35] S. Liu, M. Chen, S. Sengupta, M. Chiang, J. Li, and P. A. Chou, \P2P Stream-
ing Capacity under Node Degree Bound," in Proceedings of the IEEE 30th
International Conference on Distributed Computing Systems, 2010. (ICDCS
2010), 21-25 June 2010, pp. 587{598.
[36] S. Sengupta, S. Liu, M. Chen, M. Chiang, J. Li, and P. A. Chou, \Peer-
to-Peer Streaming Capacity," IEEE Transactions on Information Theory,
vol. 57, no. 8, pp. 5072{5087, August 2011.
[37] D. Ren, Y.-T. H. Li, and S.-H. G. Chan, \On Reducing Mesh Delay for
Peer-to-Peer Live Streaming," in Proceedings of the 27th IEEE International
Conference on Computer Communications (INFOCOM 2008), 13-18 April
2008, pp. 1058{1066.
[38] ||, \Fast-Mesh: A Low-Delay High-Bandwidth Mesh for Peer-to-Peer Live
Streaming," IEEE Transactions on Multimedia, vol. 11, no. 8, pp. 1446{1456,
December 2009.
[39] G. Bianchi, N. B. Melazzi, L. Bracciale, F. L. Piccolo, and S. Salsano,
\Streamline: An Optimal Distribution Algorithm for Peer-to-Peer Real-Time
Streaming," IEEE Transactions on Parallel and Distributed Systems, vol. 21,
no. 6, pp. 857{871, June 2010.
[40] M. Chen, M. Chiang, P. Chou, J. Li, S. Liu, and S. Sengupta, \P2P Stream-
ing Capacity: Survey and Recent Results," in Proceedings of the 47th An-
nual Allerton Conference on Communication, Control, and Computing, 2009.
(Allerton 2009), 30 September-2 October 2009, pp. 378{387.
[41] K.-H. K. Chan, S.-H. G. Chan, and A. C. Begen, \Optimizing Substream
Scheduling for Peer-to-Peer Live Streaming," in Proceedings of the 7th
IEEE Consumer Communications and Networking Conference, 2010. (CCNC
2010), 9-12 January 2010, pp. 1{5.
[42] J. Reichel, H. Schwarz, and M. Wien, Joint Scalable Video Model 11 (JSVM
11). Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, Doc.
JVT-X202, July 2007.
[43] J.-Y. Kao, \An algorithm for svc bitstream allocation by a smart adaptor," in
Proceedings of the 9th International Conference on Signal Processing, 2008.
(ICSP 2008), October 2008, pp. 1243{1246.
[44] J.-Y. Kao and J.-S. Tu, \An Algorithm for Packing Bitstream of Scalable
Video Coding," in Proceedings of the Fifth International Conference on Intel-
ligent Information Hiding and Multimedia Signal Processing, 2009. (IIH-MSP
'09), September 2009, pp. 25{29.
[45] Mono Project, \Mono Torrent," http://monotorrent.com/.
[46] J. A. Pouwelse, P. Garbacki, D. Epema, and H. J. Sips, \The Bittorrent P2P
File-Sharing System: Measurements and Analysis," in Proceedings of the 4th
International Workshop on Peer-To-Peer Systems (IPTPS), 2005.
[47] G. Neglia, G. Reina, H. Zhang, D. Towsley, A. Venkataramani, and J. Dana-
her, \Availability in bittorrent systems," in Proceedings of the 26th IEEE
International Conference on Computer Communications. (IEEE INFOCOM
2007), May 2007, pp. 2216{2224.
[48] Service Availability Forum, Application Interface Specication. Service Avail-
ability Forum, SAI-AIS-B.01.01, November 2004.
[49] M. Reitenspiess, \Delivery of the sa forum application interface specication,"
in Proceedings of the Workshop on Dependable Embedded Systems (SRDS
2003), 5 October 2003.
[50] SourceForge.net, \BNBT," http://sourceforge.net/projects/bnbt/.
[51] OpenAIS, \OpenAIS," http://www.openais.org/.
[52] B.-Y. Choi, S. Moon, Z.-L. Zhang, K. Papagiannaki, and C. Diot, \Analysis of
point-to-point packet delay in an operational network," Computer Networks,
vol. 51, no. 13, pp. 3812{3827, September 2007.