( ) ( ) ( ) ( ) ( )

NAIST-IS-MT0851074 ALM 2012 3 2

( ) ( ) ( ) ( ) ( )

ALM P2P P2P ALM,,,,, NAIST-IS- MT0851074, 2012 3 2. i

Proposal of How to Build Autonomy Type ALM for Simultaneous Viewing Multi Videos Takahiro Nakagawa Abstract In recent years, an opportunity and the time when people view to image contents are increasing with spread and improvement in high-speed Internet. Research which is going to view to two or more images simultaneously is done. Although viewing to one image was assumed, but viewing to two or more images simultaneously was not assumed. Therefore, if it is going to view two or more images simultaneously, gap will arise to the reproduction timing of each image. Moreover, when it is going to view to two or more images by high definition as much as possible, the bandwidth of a server will be tight, if all images tend to be summarized to one server and it is going to transmit. So, in this research, the P2P streaming system which gave the synchronous information based on a time stamp to the streaming packet from the server of two or more points, and the mechanism which synchronizes and reproduces each image is proposed by arranging by each reproduction client side. Thereby, when reproducing simultaneously combining the image from two or more points, it becomes possible to suppress gap of the arising reproduction timing. Keywords: ALM, streaming, synchronization between videos, tree construction, delay Master s Thesis, Department of Information Systems, Graduate School of Information Science, Nara Institute of Science and Technology, NAIST-IS-MT0851074, March 2, 2012. ii

1 1 2 5 2.1.......................... 5 2.2............................ 7 2.3.............................. 8 3 9 3.1. ALM.................................. 9 3.1.1................ 9 3.1.2................... 15 3.1.3........................ 16 3.2.............................. 17 3.3. ALM.................... 17 3.4............................ 18 4 ALM 19 4.1................................. 20 4.2................................. 21 4.3................................... 22 4.3.1.................... 24 4.3.2.................... 24 4.3.3......................... 25 4.3.4......................... 28 4.3.5......................... 30 iii

4.4................................... 33 4.4.1..................... 33 4.4.2.......................... 36 4.4.3....................... 38 5 40 5.1................................. 40 5.1.1........................ 40 5.1.2..................... 41 5.1.3....................... 43 5.2........................ 45 5.2.1........................ 45 5.2.2.................... 48 5.2.3... 51 5.2.4.......... 54 5.3.............................. 55 6 57 6.1.................................. 57 6.2............................ 57 iv

1.1....................... 2 3.1 ALM.................. 10 3.2.................. 11 3.3 ALM.................... 15 4.1................... 19 4.2...... 23 4.3....................... 25 4.4.................. 26 4.5....................... 27 4.6........................... 28 4.7........................... 29 4.8........................ 31 4.9...................... 32 4.10......................... 33 4.11......................... 34 4.12.............................. 36 4.13........................... 38 4.14.................... 39 5.1 1............................ 41 5.2 2............................ 42 5.3....................... 43 5.4.................... 44 v

5.5......................... 45 5.6....................... 46 5.7................................ 46 5.8.............. 49 5.9................. 50 5.10............... 51 5.11........... 52 5.12............. 53 5.13............................ 54 5.14........ 55 vi

1.1........... 1 4.1...................... 20 4.2................................ 21 4.3......................... 24 5.1...................... 44 5.2.... 47 5.3.... 47 5.4............................ 48 vii

1 Cisco 2010 2015 [1] 1.1 2010 4672PB 48% 1.1 (PB/ ) 2010 2011 2012 2013 2014 2015 CAGR 2010 2015 4,968 6,017 7,277 8,867 11,040 13,797 23% 4,672 8,079 12,146 17,583 24,357 33,620 48% Web E 2,393 3,113 4,146 5,325 6,769 8,592 29% 308 442 659 905 1,251 1,736 41% 49 68 95 133 187 290 43% Voice over IP VoIP 138 147 153 157 160 168 4% 1

1.1 (CGM (Wiki )) 1.1 [2] [3] ALM(Application Layer Multicast) 2

P2P ALM ALM ALM ALM ALM ALM ( ) 3

ALM 2 3 4 5 4

2 2.1. Web CPU 5

Contents Delivery Network(CDN) CDN CPU DNS CDN akamai IP IP L2 CPU IP ISP IP ISP ISP Application Layer Multicast(ALM) ALM P2P CPU 6

2.2. ( ) [4] MU(MediaUnit) MU ( ) 7

2.3. BB [6] 1 100 10 100 1 ALM 8

3 3.1 ALM 3.2 3.3 ALM 3.4 3.1. ALM ALM ALM OLM(Over Lay Multicast) P2P P2P ALM ALM 3.1.1 ALM ALLM 9

3.1 3.1 ALM ALM ALM 3.2 ShareCast[7] 10

3.2 ALMI[8] session controler 11

[9] ALM 1000 1000 1000 1000 PeerCast[10] PeerCast 12

PeerCast ALM [11] PeerCast 30ms [12] [13] [14] ( ) DOS 13

[15] [16] ( ) Narada[17] IP DVMRP Distance Vector Multicast Routing Protocol [19] 14

Scribe[20] Pastry ALM Pastry 3.1.2 [22] DONet: Data-driven Overlay Network ALM 3.3 3.3 ALM mcache 15

mcache mcache 3.1.3 OceanGrid[23] 16

3.2. [24] ALM [5] 80ms [-500ms, +750ms] 3.3. ALM ALM ALM ALM ALM 17

[30] ALM NTP 3.4. ALM ALM ALM 18

4 ALM 4.1 A A B 4.1 19

4.1. BB [6] ALM 4.1 4.1 1 1 100 ALM(BB ) 10 1000 50 1000 20 BB 8 1 20

4.2 4.2 1 10 LAN 100Mbps 384kbps 800kbps 4 4.2. 10 4 [5] 80ms 80ms 1 21

360kbps 1Mbps 100Mbps 4.3. ALM 22

N 4.2 4.2 N 0 N T T DoS ALM 23

ALM ( ) ( ) ( ) 4.3.1 4.3 StreamID IP PictID 4.3 ID IP (IP ) 4.3.2 24

NTP 4.3 4.3 4.3.3 NTP IP 25

IP IP 4.4 4.4 NTP NTP 26

NTP 4.5 4.5 27

4.3.4 [5] (RTT) 4.6 4.6 ( ) 1 1 28

Source to End Delay 4.7 4.7 29

4.3.5 P2P N A B ( T) 100 N R ( 0 ) IP R T 100 R 4.8 30

4.8 R T 100 T 4.9 N T 100 N N A:( 120ms - 110ms ) 2 = 20ms 20ms B:( 120ms - 150ms ) 2 =-60ms 60ms 31

C:( 120ms - 110ms ) 2 = 20ms 20ms D:( 120ms - 160ms ) 2 =-80ms 80ms 4.9 2 1 4.10 TCP A( ) ( ) 32

4.10 4.4. 4.4.1 4.11 33

4.11 1 public r e f class node 2 { 3 public : 4 S t r i n g ˆ streamid ; // ID 4.1 5 S t r i n g ˆ ipadress ; // I P 6 S t r i n g ˆ port ; // 7 S t r i n g ˆ p i c t I d ; // ID 8 S t r i n g ˆchildNum ; // 9 S t r i n g ˆ delay ; // 10 S t r i n g ˆ d e s c r i p t i o n ; // 11 12 } ; 4 4.2 1 i f ( TextArr1 [0] > Equals ( r e g i s t ) ) { // 2 34

3 } else i f ( TextArr1 [0] > Equals ( get ) ) { // 4 5 } else i f ( TextArr1 [0] > Equals ( d e l e t e ) ) { // 6 7 } else i f ( TextArr1 [0] > Equals ( update ) ) { // 8 9 } 35

4.4.2 4.12 4.12 ALM 4.3 1 i f ( TextArr1 [0] > Equals ( c h i l d r e n ) ) { // 2 3 } else i f ( TextArr1 [0] > Equals ( connect ) ) { 4 // 36

5 6 i f ( Int32 : : Parse ( TextArr1 [4])>=cnum){ 7 // 8 9 } else {// 10 11 } 12 } else i f ( TextArr1 [0] > Equals ( broad ) ) { 13 // 14 15 } children connect broad 2 1 public r e f class StateObject 2 { 3 Socket ˆ worksocket ; // 4.4 4 S t r i n g ˆ i p p o r t ; // I P 5 int c l i e n t p o r t ; // 6 7 int streamid, timeidx ; // ID 8 int children num ; // 9 int mydelay ; // 10 11 array<byte> ˆ send ; // 12 array<int> ˆ t r a n s t i m e ; // 13 14 Queue ˆ s e n d b u f f e r q u e u e ; // 15 16 StateObject ( void ){ // 17 ( ) 18 } 19 20 void send round ( void ){ 21 // 22 ( ) 37

23 } 24 25 } send round 4.4.3 4.13 4.13 4.14 38

1 // 2 for ( int i =0; i <4; i ++){ 3 //50 4.5 4 while ( b u f f e r q u e u e [ i ] >Count >50){ b u f f e r q u e u e [ i ] >Dequeue ( ) ; } 5 // 6 while ( b u f f e r q u e u e [ i ] >Count >10 + d e l a y f r a m e [ i ] ) { 7 // 8 FrameSet ˆ f s e t = s a f e c a s t<frameset ˆ>( b u f f e r q u e u e [ i ] >Dequeue ( ) ) ; 9 // 10 BeginInvoke ( gcnew p i c t D e l e g a t e ( this, &Form1 : : p i c t ), f s e t, i ) ; 11 } 12 } 4.14 39

5 5.1. 5.1.1 [31] PC ALM 1 1 5.1 1 10 (+ 10 ) Send 40

5.1 1 2 5.2 WIDE PC PC eo 100M ping RTT 9ms 2 4 6 8 10 5.1.2 1 1 5.3 5.4 41

5.2 2 5.3 30 70 120 80.18ms 2 2 5.5 5.6 2 ALM 10 PC 42

5.3 2 ALM 2 7 10 1023 5.1.3 RTT 9ms RTT 5.1 10ms 100ms 300ms ALM 1 2 1 100ms 43

5.4 5.1 RTT yahoo.com NAIST google.com NAIST yahoo.co.jp NAIST yahoo.com eonet google.com eonet yahoo.co.jp eonet www.inei.gob.pe NAIST WIDE eonet 128ms 60ms 10ms 47ms 60ms 13ms 277ms 9ms 44

5.5 200ms ALM 200ms 2 ALM 5.2. 5.2.1 5.7 45

5.6 5.7 100ms GEM[32] 2 NTP 3 46

NTP 2 NTP NTP 15 NTP 2 5.3 4 8 5.2 1 5.2 CPU Core 2 Duo 1.20GHz 3GB RAM NIC Marvell Yukon 88E8055 Gigabit Ethernet OS Windows XP Professional SP2 5.3 CPU Celeron M 1.40GHz 1.3GB RAM NIC Broadcom 10/100 Ethernet OS Windows XP Professional SP3 1 30 1 53 47

7 424 45 5.4 5.4 Motion JPEG 10fps JPEG (20 ) 1 4KB 4KB 10fps 8bit=320kbps 2 3 40 T 1 20 50 100 200 3 5.2.2 5.8 T T 2 48

5.8 T 5.9 T T 1 4500ms T 50 2100ms T 100 200 T 100 2000ms 128 2 7 1 2 14 49

5.9 2000ms 4000ms 4000ms 1 5.10 45 2 350 NTP 50

5.10 5.2.3 T 50 5.11 51

5.11 10fps 320kbps 30fps 1Mbps 5Mbps 10Mbps 10Mbps 14000ms 52

5.12 5.12 30fps 1 17ms 53

5.2.4 100ms 5.13 0ms 200ms 5.13 5.14 100ms -30 54

5.14 5.3. 2 7 2000ms 1 14 55

2 4000ms 1 3 10fps 50ms 80ms PC PC 4 56

6 6.1. RTT ALM 6.2. ALM 57

58

4 59

[1] Cisco Visual Networking Index 2010 2015 http://www.cisco.com/web/jp/solution/isp/ipngn/literature/white paper c11-481360.html [2] http://nicofarre.jp/ [3] LIVE http://www.ntt.com/release/2000news/0009/0904.html [4].. Vol. 84, No. 3, pp. 177-183, 2001 [5] R. Steinmetz. Human perception of jitter and media synchonaization. IEEE Journal of Selected Areas in Communications, Vol. 14, No. 1, pp. 61-72, 1996. [6]. P2P. R&D. 2008. [7],. P2P ShareCast.. NS, Vol. 108 No. 392, pp. 33-37, 2009. [8] D. Pendarakis, S. Shi, D. Verma, and M. Waldvogel. ALMI: An Application Level Multicast Infrastructure. Proceedings of the 3rd Usenix Symposium on Internet Technologies & Systems, March, 2001. 60

[9],.., Vol. 2004, No. 7, pp. 285-288, 2004. [10] H. Deshpande, M. Bawa, Garcia H. Molina. Streaming Live Media over Peers. Technical Report. Stanford InfoLab, 2002. [11],,,. PeerCast PeerStream.. NS,, Vol. 105, No. 562, pp. 5-8, 2005. [12],. PeerCast.. NS,, Vol. 108, No. 258, pp. 7-12, 2008. [13],,. ALM.. NS,, Vol. 105, No. 627, pp. 81-84, 2006. [14],.. 2009, Vol. 2, pp. 260, 2009. [15],,,. M.. NS, Vol. 106, No. 492, pp. 35-40, 2007. [16],. ALM.. NS, Vol. 109, No. 326, pp. 85-88, 2009. [17] Y. Chu, S. Rao, H. Zhang. A Case for End System Multicast. Proceedings of ACM SIGMETRICS, Santa Clara, CA, Jun. 2000. 61

[18],,,,... Vol. 2006, No. 96, pp. 55-60, 2006. [19],,,,,... IN, Vol. 105, No. 279, pp.137-142, 2005. [20] 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 Communications, Vol. 20, No. 8, pp. 1489-1499, 2002. [21],. P2P.., Vol.2009, No.3, pp.1-7, 2009. [22] 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. IEEE International Conference on Computer Communications, Vol. 3, pp. 2102-2111, 2005. [23] Ocean Grid http://www.utagoe.com/en/service/pdf/20060731-oceangridintroduce.pdf [24],,... IN, Vol. 107, No. 222, pp. 125-130, 2007. [25],,,,,. 62

.. Vol. 46, No. 2, pp. 525-535, 2005. [26]... 2006. [27],,... IN,. Vol. 107, No.222, pp. 125-130, 2007. [28],,,... NS,, Vol. 105 No.127, pp. 13-16, 2005. [29],,,,,..., Vol. 2002, No. 32, pp. 43-48, 2002. [30]. ALM.. 2011. [31] HP http://tanma.homelinux.com/ [32] Anue Network Emulators http://www.anuesystems.com/test-and-measurement/products/networkemulators 63