논문 10-35-08-11 한국통신학회논문지 '10-08 Vol. 35 No. 8 Unchoked Peer 개수에따른 BitTorrent 성능분석 정회원정태중 *, 한진영 *, 김현철 *, 권태경 *, 종신회원최양희 * An Analysis on BitTorrent Performance Based on the Number of Unchoked Peers Taejoong Chung*, Jinyoung Han*, Hyunchul Kim*, Taekyoung Ted Kwon* Yanghee Choi* Lifelong Member Regular Members, 요 약 최근파일공유를위해널리사용되는 BitTorrent의강점은 BitTorrent의핵심메커니즘인 peer 선택기법에기인한다. Peer 선택기법은해당호스트가업로드할 peer를선택하는것인데, 이때자신에게각 peer가업로드한비율을비교해서가장많이업로드한 peer들에게업로드를하게된다. 그런데 BitTorrent에서는업로드할 peer의개수 ( 즉, unchoked peer 개수 ) 를 4개로고정하고있다. 하지만 peer들의개수나다운로드속도, 업로드속도와같은공유집단 ( 즉, swarm) 의특성은계속변하기때문에 unchoked peer 개수를고정하는것은효율적이지않다. 본논문에서는 BitTorrent에서 unchoked peer 개수가고정된 4개가아니라변할때전체시스템성능에어떠한영향이끼치는지분석한다. 분석을위해본논문에서는서울대학교캠퍼스망에테스트베드를설치하였고, 실제로널리사용되는오픈소스 BitTorrent 클라이언트를수정해서사용하였다. 테스트베드에서의다양한실험을통해 BitTorrent의성능이 unchoke 개수에따라달라지게되는것을보였고, 이에따라 swarm의상황을고려해서 unchoke개수를적절하게조절하는메커니즘이필요하다는것을보였다. Key Words : BitTorrent, Swarming System, Choking Algorithm, Number of Unchoked Peer ABSTRACT A strength of BitTorrent, which is widely used for file sharing today, is due to its peer selection mechanism which is designed to encourage peers to contribute data. In the peer selection phase in BitTorrent, peers to upload the file in a swarm are selected by determining which peers upload the most to themselves. However, the number of peers to upload (i.e., number of unchoked peers) is fixed to four in its peer selection mechanism of BitTorrent, which yields inefficiency because the situation of the swarm may vary frequently (e.g., number of peers in the swarm, download rates, and upload rates). In this paper, we analyze the swarming system performance when the number of unchoked in BitTorrents is not static, but dynamic. For empirical investigation, we established a testbed in Seoul National Universty by modifying an open-source BitTorrent client, which is popular. Through our experiments, we show that an adaptive mechanism to adjust the number of unchoked peers considering the situation of the swarm is needed to improve the performance of BitTorrent. This work was supported by NAP of Korea Research Council of Fundamental Science and Technology, and the project K-10-L05-C03-S05 of Korea Institute of Science and Technology Information(KISTI). * 서울대학교멀티미디어및이동통신연구실 (tijayoo@gmail.com) 논문번호 :KICS2010-06-264, 접수일자 :2010 년 6 월 11 일, 최종논문접수일자 : 2010 년 8 월 5 일 1197
한국통신학회논문지 '10-08 Vol. 35 No. 8 Ⅰ. 서론 최근 BitTorrent [1] 는파일을공유하기위한 peerto-peer ( 이하 P2P) 소프트웨어로많이사용되고있다. IPoque에서 2009년에발간한보고서에따르면현재인터넷트래픽의약 27-55% 를 BitTorrent가차지하고있다 [2]. 이렇게 BitTorrent가널리사용되는이유는 BitTorrent가기존의다른 P2P에서해결하지못한문제점들을해결하였기때문이다. 첫째, BitTorrent에서는인기도가높은파일에대한요구가몰리는 flash crowd 상황에서도효과적으로파일이전송된다. 둘째, 기존의 P2P에서는파일을공유하는공유집단 ( 이하 swarm) 에기여하지않고받기만하는 free-rider 문제 [3] 가심각한데, BitTorrent 에서는이문제가효과적으로방지된다 [4]-[6]. 이러한 BitTorrent의장점들은 choking algorithm 이라고도불리우는 BitTorrent의핵심메커니즘인 peer 1) 선택기법에기인한다. 본기법은각각의 peer 에게인센티브를제공함으로써파일을공유하도록촉진하는 built-in 인센티브메커니즘으로, 본기법의효율성은많은연구에서증명되었다 [4]-[7]. 그런데 BitTorrent에서기본적으로호스트가여러 peer로부터다운로드를할수있지만, 자신이업로드할 peer의개수 ( 즉, unchoked peer 2) 개수 ) 는 4개로고정하고있다. 하지만 BitTorrent의공유집단 ( 즉, swarm) 의상황은계속변하기때문에 unchoked peer 개수를 4개로고정하는것은효율적이지않다. 예를들어서 swarm에참여하는 peer 의개수나데이터의완전한사본을가지고업로드만해주는 peer ( 이하 seed) 의개수, 데이터를다운로드하고자하는 peer ( 이하 leecher) 의개수, 그리고 swarm내에서다운로드및업로드하는속도등은계속해서변하게된다. 이때, 해당호스트가다운로드를받기위해서는 ( 즉, 다른 peer가해당호스트에게업로드를해주기위해서는 ) 다른 peer 로부터 tit-for-tat 전략에의해선택을받아야한다. 따라서다른 peer로부터선택을효과적으로받기위해서는해당호스트가 swarm의상황에따라소수의 peer에게많은양의대역폭으로업로드를하는것이유리할수도있고, 많은 peer에게적은양 1) 본논문에서는 peer는파일을함께공유하는호스트중에서자신과연결이되어있는호스트를지칭한다. 2) 호스트가 peer에게전송하지않을때해당 peer는 choke 되었다라고하며, 반대로호스트가 peer에게전송하고자할때해당 peer는 unchoke 되었다고한다. 의대역폭으로업로드를하는것이유리할수도있다. 하지만현재의 BitTorrent의 peer 선택기법은 unchoked peer 개수를고정해서이러한 swarm의상황을반영하지못하고있다. 본논문에서는, BitTorrent에서 unchoked peer 개수가고정된 4개가아니라변할때, 전체시스템성능에어떠한영향이끼치는지분석한다. 분석을위해본논문에서는서울대학교캠퍼스망에테스트베드를설치하였고, 실제로널리사용되는오픈소스 BitTorrent 클라이언트를수정해서실험하였다. 실험결과를바탕으로 unchoked peer의개수를 swarm의상황에따라적응적으로결정하는기법의필요성을제시하였다. 본논문의구성은다음과같다. 2장에서는 BitTorrent의동작과정을설명하고, 3장에서는실험을위한테스트베드및실험설정에대해설명한다. 4장에서는다양한시나리오에서 unchoke할 peer 개수변화에따른성능측정을하고마지막으로 5장에서결론을맺는다. Ⅱ. BitTorrent 배경지식 BitTorrent가실제로널리사용됨에따라 BitTorrent 의 throughput, fairness 그리고 incentive 문제에관해많은연구가진행되었다 [5]-[8]. 본장에서는 BitTorrent 프로토콜에관한용어설명과더불어핵심알고리즘인 peer 선택기법을설명하도록한다. 2.1 BitTorrent 용어정리 BitTorrent에관한많은연구가진행되었으나용어들은표준화되어있지않다. 따라서명확성을위해서본논문에서사용할대표적인 BitTorrent 용어들을정리하였다. 2.1.1 Torrent / Swarm BitTorrent 프로토콜을사용하여같은파일을받고자하는 peer들의집합. 보통 torrent와 swarm이교환적으로사용된다. 2.1.2 Metainfo File (.torrent) Torrent file ( 즉,.torrent ) 이라고도불리우며 piece의개수나파일을 download하기위한모든정보가들어있다. 각각의 piece를검증하기위해 piece 의 SHA-1 hash값이들어있으며, tracker의 IP 주소와 port number가들어있다. 1198
논문 / Unchoked Peer 개수에따른 BitTorrent 성능분석 2.1.3 Tracker BitTorrent System중에서유일한 centralized 요소로실제적인파일의전송에는관여하지않으나파일을공유하는 peer들의위치정보를가지고있으며, 그들의통계또한수집한다. 호스트가접속하면해당토런트를공유하는 peer 리스트를제공한다. 2.1.4 Piece and Blocks 파일은여러개의 piece로나뉘어져있으며각각의 piece는 block으로또나누어져있다. 실제적인전송단위는 block이며 peer가완전한 piece을소유하고있지않으면공유할수가없다. 2.1.5 Leecher and Seed 파일의 piece를다운로드하고있는상태일경우 ( 즉, 모든 piece를소유하고있지않을때 ) leecher 라고하며, 파일의다운로드가끝나고완전한사본을소유하고있을때 ( 즉, 모든 piece를소유하고있을때 ) seed라고한다. 한 peer는위두가지상태중하나의상태에만있을수있다. 2.2 BitTorrent 동작과정본장에서는 BitTorrent 프로토콜을이용해서파일을공유하는세부동작과정을설명한다. 그림 1 은 BitTorrent의주요동작과정을묘사한것이다. 파일배포자는파일의정보를담은 metainfo file ( 즉.torrent 파일 ) 을생성한다. 생성된.torrent 파일은 tracker와사람들이다운로드받을수있도록 TPB [9] 나 Mininova [10] 와같은잘알려진웹사이트에등록한다. 이파일에관심을갖고있는호스트는해당웹사이트로부터.torrent 파일을받는다 ( 그림 1의 A). 해당호스트는.torrent 파일에포함되어있는 tracker의주소로그림 1의 B와같이접속을한다. 이때, tracker는자신이관리하고있는해당파일을공유하는 peer들중에서일부의 peer를선택하여그들의주소가담긴리스트를호스트에게알려준다 ( 그림 1의 C). 이때, 보통 50개의 peer정보를호스트에게알려준다. 호스트는 tracker로부터획득한 peer들의주소를바탕으로연결을시도하고연결된 peer에한해서자신이원하는파일의각기다른 piece를요청하게된다 ( 그림 1의 D). 2.1.6 Rarest-First Algorithm 어떠한 piece를요구할지를결정하는선택기법이다. 각각의 peer는자신과연결된 peer가어떠한 piece를소유하고있는지에대한리스트를가지고있고, 이리스트를바탕으로가장개수가적은 piece를선택하고요청하게된다. 이때, 각 peer가소유한정보를바탕으로선택하기때문에 local rarest-first algorithm이라고도한다. 2.1.7 Peer 선택기법 (Choking Algorithm) 본기법은 choking algorithm이라고도불리는기법으로, 자신이업로드할 peer를선택하는것으로 BitTorrent에서는 tit-for-tat 전략에의해 peer를선택하게된다. tit-for-tat 전략이란자신에게각 peer 가업로드한비율을비교해서가장많이업로드한 4개의 peer를선택하는전략이다. 주기적으로호스트는자신에게 upload해준 peer들의 upload rate를계산하여 unchoke할 peer와 choke할 peer를선택하게된다. 만약이러한기법이 Bitorrent에존재하지않으면자신이가지고있는 piece를다른 peer에게전송해줄이유가없게되고, 다른 peer에게자신이가지고있는 piece를업로드하지않은채자신이받고자하는파일만받고바로나가버리는 free-rider 문제가심화된다 [3]. 그림 1. BitTorrent 동작과정모식도 Ⅲ. 테스트베드설정본논문에서 unchoked peer 개수의효과를검증하기위해그림 2와같이서울대학교캠퍼스망에테스트베드를설치하였다. 본테스트베드는총 9개의호스트로구성되어있고, 이중에서 8대는파일을다운로드받고자하고 leecher이고, 나머지 1대는공유할파일을미리갖고있는 seed 이다. 또한실 1199
한국통신학회논문지 '10-08 Vol. 35 No. 8 그림 2. 테스트베드모식도 표 1. 실험환경설정 항목파일의크기 Seed의개수 Seed의업로드 Peer 개수 Leecher의개수대역폭 값 298Mb 1 개 2 개 8 개 100Mbps 험을위해테스트베드에하나의독립된 tracker도설치하여독립적인실험을수행할수있도록하였다. 각호스트에서동작할 BitTorrent 클라이언트는현재많이사용되고있는오픈소스기반의 Azureus [11] 이다. 각호스트의상태를매시간마다측정및기록하고, unchoked peer의개수를변화시키기위해서 Azureus 클라이언트의소스를고쳐서사용하였다. 실험을위한자세한환경설정은표 1에나타나있다. Ⅳ. 성능평가및분석 본장에서는 unchoked peer가 swarm의상황에따라 BitTorrent 성능에어떤영향을끼치는지분석하기위해다양한상황을가정하고실험하였다. Swarming system에서성능을가장쉽고정확하게알수있는방법은 swarm에참여하는각각의 peer들의다운로드속도를모두측정하여비교분석하는것이다. swarm에참여하는 peer들의평균적인다운로드속도가상승된다면그것은바로 swarm의성능향상을의미한다. 따라서본실험에서는 swarm 의성능을판단하기위한기준으로다운로드속도를측정하고분석하였다. 4.1 Swarm내모든 peer의 unchoked peer 개수가동일할때첫번째실험은 swarm내에모든 peer가동일한 unchoked peer개수를가지고파일을공유할때효율 그림 3. 8 개호스트의 unchoked peer 개수가각각 2 개, 4 개, 6 개, 8 개일때의 Average Download Rate 적인 unchoked peer 개수를알아보기위한것이다. 그림 3에서 swarm내의모든 peer들의 unchoked peer 개수가각각 2, 4, 6, 8개일때시간에따른각 peer의다운로드속도를각각나타내고있고, 표 2에서이에따른평균파일다운로드종료시간을나타내고있는데, unchoked peer 개수가 8개일때, 2개일때와 4개일때보다각각 34%, 21% 종료시간이단축되었다. 즉 unchoked peer 개수가늘어남에따라전체 swarm에서의 peer간의업로드의수와양이늘어나되고, 이에따라 swarm 전체적으로다운로드속도가빨라지게된것이다. 하지만자신을제외한전체 leecher개수만큼 unchoked peer 개수가늘어갈수록효과는줄어들었다. 그러므로전체 swarm측면에서는대역폭이충분할때, unchoke 개수가늘어날수록 swarm 의전체적인성능이향상됨을알수있다. 4.2 Swarm내 peer의 unchoked peer 개수가다를때다음실험은한 swarm내에동일하지않은 unchoked peer 개수를지닌호스트들이파일을공유할때의성능차이를알아보기위한것이다. 각각의호스트들은서로다른상황에서파일을공유하고있고 ( 예 : 높은대역폭사용 vs. 낮은대역폭사용 ), 또한각자 swarm에업로드로공헌하려는정도가모두다르다. 따라서 4.1장의결과처럼모든호스트들이많은 unchoked peer 개수를사용하는것은전체 swarm 성능에도움이되지만일부호스트들은많은 unchoked peer 개수를사용하려하지않을수있다. 따라서본실험에서는이와같은상황을가정해서 unchoked peer 개수가 2개인 4개의호스트와 unchoked peer 개수가 5개인 4개의호스트가존재 1200
논문 / Unchoked Peer 개수에따른 BitTorrent 성능분석 할때시간에따른다운로드속도를측정하였고, 또한자유도를높여서두호스트씩짝을지어서 unchoked peer 개수가 2개, 4개, 6개, 8개일때의실험을진행하였다. 4.2.1 Unchoked peer 개수가 2개일때와 5개일때의다운로드속도비교그림 4는 unchoked peer 개수가 2개인호스트들과 unchoked peer 개수가 5개인호스트들의평균다운로드속도를나타낸다. 그림 4에서보여주듯이 unchoked peer 개수가 2개인호스트들이보다빠른다운로드속도를보여주었고, 표 3에서볼수있듯이약 30초정도빠른파일다운로드종료시간을나타내었다. 즉한 swarm내에다른수의 unchoked peer 개수를지닌호스트들이참여하고있을때적은개수의 unchoked peer 개수를사용하는호스트들이더큰이득을봄을알수가있다. 이것은같은양의대역폭을더적은수의 peer에게할당한 unchoked peer 개수를 2개로설정한호스트들이각 peer에게할당한업로드대역폭의양이 unchoked peer 개수 5개호스트들보다크기때문에상대적으로다른 peer로부터선택될확률이크기때문이다. 즉, 이와같은경우에는많은 peer에게적은양으로업로드하는것 ( 즉, 많은 unchoked peer 개수를설정하는것 ) 보다, 적은 peer에게많은양으로업 로드하는것 ( 즉, 적은 unchoked peer 개수를설정하는것 ) 이개개의호스트에게는더유리하다. 물론 4.1장에서보듯이개개의호스트가이러한선택을한다면전체 swarm 성능에는오히려좋지않을수있다. 4.2.2 Unchoked peer 개수가 2개, 3개, 4개, 5일때의비교마지막으로좀더다양한 unchoked peer 개수를가진호스트들이파일공유를할때의효율적인 unchoked peer 개수를알아보기위해 2대씩호스트를묶은 4그룹의 unchoked peer 개수를각각 2, 3, 4, 5씩설정하고실험을하였다. 그림 5에서보여주듯이 unchoked peer 개수가상대적으로작은호스트들이 unchoked peer 개수가큰호스트들보다빠른다운로드속도를나타내었고그에따라표4에나와있듯이다운로드종료시간도단축됨을볼수있었다. 이것은그림 4의실험과유사한결과로써한 swarm내에각기다른 unchoked peer 개수를지닌호스트가존재할때, unchoked peer 개수를적게설정할수록호스트의성능에유리함을보여준다. 그림 5. 2 개호스트씩무리를지은 4 개의그룹이각각 2 개 3 개 4 개 5 개의 unchoke 개수를가질때 Average Download Rate 그림 4. Unchoked peer 개수가 2 개인호스트 4 개와 5 개인호스트 4 개의 Average Download Rate 표 4. Unchoke 개수에따른다운로드종료시간 표 3. Unchoked peer 개수에따른 peer 들의평균다운로드종료시간 Unchoked peer 개수 평균파일다운로드종료시간 Unchoked peer 개수 평균파일다운로드종료시간 2 개 211 초 3 개 219 초 2 개 201 초 5 개 228 초 4 개 220 초 5 개 225 초 1201
한국통신학회논문지 '10-08 Vol. 35 No. 8 Ⅴ. 결론및향후과제본논문에서는 swarm 의상황에따라 unchoked peer 개수의변화가 BitTorrent 성능에영향을주는것을보여주었다. 전체적인 swarm의성능을고려하자면 unchoked peer 개수가많을수록전체 peer 들의다운로드속도와종료시간에서의이득을볼수있었다. 하지만각기다른 unchoked peer 개수를지닌호스트들이한 swarm에참가할경우적은 unchoked peer 개수를지닌 peer가큰 unchoked peer 개수를지닌 peer보다성능향상에서의이득을보았다. 따라서많이변하는 swarm의상황에따라전체적인 swarm의성능과각호스트의성능을동시에최대화할수있는 unchoked peer 개수선택기법이필요하다. 본연구팀에서는 swarm의상황에따라서 unchoked peer 개수를조정하는적응적 unchoked peer 개수선택기법을후속연구로진행하고있다. 참고문헌 [7] D. Qiu and R. Srikant. Modeling and performance analysis of bittorrent-like peer-topeer networks. In ACM SIGCOMM, 2004. [8] A. Sherman, J. Nieh, and C. Stein. Fairtorrent: bringing fairness to peer-to-peer systems. In ACM CoNEXT, 2009. [9] The pirate bay. http://thepiratebay.org [10] Mininova. http://www.mininova.org [11] Azureus - now called vuze - open source bittorrent client. http://azureus.sourceforge.net/. 정태중 (Taejoong Chung) 정회원 2009년 8월 POSTECH 컴퓨터공학과학사 2009년 8월 ~ 현재서울대학교전기컴퓨터공학부석사과정 < 관심분야 > Peer-to-Peer, Contents Distribution [1] B. Cohen. Incentives build robustness in bittorrent. In 1st Workshop on Economics of peer-to-peer Systems, 2003. [2] Ipoque The impact of p2p file sharing, voice over ip, instanct messaging, one click hosting and media streaming on the internet. http:// www.ipoque.com/resources/internet-studies/inte rnet-study-2008 2009 [3] Michael Sirivianos, Jong Han Park, Rex Chen, Xiaowei Yang Free-riding in BitTorrent Networks with the Large View Exploit In IPTPS 2007. [4] M. Piatek, T. Isdal, T. Anderson, A. Krishnamurthy, and A. Venkataramani. Do incentives build robustness in bittorrent In USENIX NSDI, 2007. [5] Arnaud Legout, G. Urvoy-Keller and P.Michiardi Rarest First and Choke Algorithms Are Enough In IMC 2006 [6] A. Legout, N. Liogkas, E. Kohler, and L. Zhang. Clustering and sharing incentives in bittorrent systems. In ACM SIGMETRICS, 2007. 한진영 (Jinyoung Han) 정회원 2007년 8월 KAIST( 한국과학기술원 ) 전산학과학사 2007년 9월 ~ 현재서울대학교전기컴퓨터공학부박사과정 < 관심분야 > Peer-to-Peer, 유비쿼터스컴퓨팅김현철 (Hyunchul Kim) 정회원 1995년 2월 KAIST( 한국과학기술원 ) 전산학과학사 1997년 8월 KAIST( 한국과학기술원 ) 석사 2005년 2월 KAIST( 한국과학기술원 ) 박사 2008년 3월 ~ 현재서울대학교전기컴퓨터공학부 BK 조교수 < 관심분야 > Internet Traffic Measurement, Contents Oriented Networking, Network Security 1202
논문 / Unchoked Peer 개수에따른 BitTorrent 성능분석 권태경 (Ted Taekyoung Kwon) 정회원 1993년 2월서울대학교컴퓨터공학과학사 1995년 2월서울대학교컴퓨터공학과석사 2000년 2월서울대학교컴퓨터공학과박사 2002년 3월 ~ 현재서울대학교전기컴퓨터공학부교수 < 관심분야 > 센서네트워크, 유비쿼터스컴퓨팅 최양희 (Yanghee Choi) 종신회원 1975년 2월서울대학교전자공학과학사 1977년 2월한국과학기술원전자공학과석사 1984년 2월프랑스 ENST 전자학박사 1991년 3월 ~ 현재서울대학교전기컴퓨터공학부교수 < 관심분야 > 미래인터넷, 멀티미디어통신 1203