Evaluation of correlation between successful lookup ratio with network size and churn rate of chord in wireless communication environment - Vu Thanh Vinh

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên | 66 EVALUATION OF CORRELATION BETWEEN SUCCESSFUL LOOKUP RATIO WITH NETWORK SIZE AND CHURN RATE OF CHORD IN WIRELESS COMMUNICATION ENVIRONMENT Vu Thanh Vinh 1* , Nguyen Chan Hung 2 , Nguyen Tuan Anh 3 1The Faculty of Information Technology – TNU 2HaNoi University of Technology, 3ThaiNguyen University ABSTRACT One of the most critical problems of peer to peer (P2P) multimedia applications is the effect of churn to the efficiency of locating data items, which is a fundamental function of P2P networks. Especially, when P2P network extends to the mobile environment, churn effect may heavily affect the whole network and disrupt normal service. In this paper, we adapt a mechanism named atomic ring maintenance for Chord to mitigate the effect of churn. Simulation results show significant improvement in successful ratio of lookups for modified Chord protocol in high churn condition while latency of successful lookups is as good as that in basic Chord. Simultaneously, we also evaluate correlation between successful lookup ratio and network size and churn rate. Keywords: P2P, Peer to Peer, distributed hash tables, DHTs, Chord, DHT performance, latency, lookup, evaluation Chord INTRODUCTION 1 Peer to peer applications, such as P2PVoD, P2P streaming, P2P file sharing have been paid much attention from both industry and academia for the last few years thanks to the bandwidth efficiency of P2P network and the fast growth of broadband Internet. Nowadays, these applications not only operate on desktop/laptop computers but also on mobile and handheld devices. However, mobile nodes tend to join and leave network very frequently due to the intermittent of communication link and user behavior. As a result, the efficiency of locating a specific data on the P2P network (i.e. a piece of video chunk or a file) dramatically decreases under this condition [2]. While this phenomenon is not well aware in file sharing applications, it can severely impact P2PVoD and P2PStreaming applications, where timing has strong effect on video and audio quality. However, since structured P2P networks were originally designed for wired network, where nodes join and leave network at much slower rate, they need significant modifications to work in mobile environment. In this study, we adapted atomic ring maintenance mechanism for Chord protocol, a typical ring-based DHT, to reduce lookup Tel: 0982782966; Email: vtvinhtnu@gmail.com inconsistency under the effect of churn. We also successfully implemented a modified Chord protocol in Oversim simulator and evaluate its performance under high churn rate together with original Chord protocol. This paper is structured as follows: In section 2, we give a brief overview of related studies. Section 3 review Chord problems under churn, and illustrate the modified Chord protocol. Section 4 is given describing simulation setup and analyzing the results. Finally, section 5 concludes this paper with an outlook to future work. RELATED STUDIES Our work was inspired by the work of Ali Ghodsi [1] namely “Atomic ring maintenance”, which again derived from [6]. Differ from their approach, we only modified the join process and consider leave as a failure since this is the common case in mobile wireless environment. In addition, we adapt a hybrid stabilization mechanism whereproactive stabilization is activated when join activities happen and periodical stabilization still run in background. Moreover, Ali Ghodsi only proposed several algorithms and proved it using analytical method without fully evaluates their performance. S. Rhea et al [4] using emulation of 1000 DHT nodes to evaluate several DHT mechanisms under churn. They Vũ Thành Vinh và cs Tạp chí KHOA HỌC & CÔNG NGHỆ 72(10): 66 - 72 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên | 67 focused on three issues: reactive versus periodic recovery from neighbor failure, the calculation of timeouts on lookup messages, and proximity neighbor selection. By introducing a timeout mechanism based on virtual coordinates, they tried to improve the mean latency. However, most of these works assume a normal scenario of file-sharing applications, without regard to the characteristics of wireless environments. CHORD UNDER CHURN Churn effects on Chord One of the main reasons for the degradation of Chord performance under churn is the inconsistency of node pointers, which are used intensively in searching activities. When a node joins in network, Chord does not immediately correct successor and predecessor pointers of all relevant nodes. Instead, Chord only corrects some pointers and relies on periodical stabilization process to correct rest of pointers. Similarly, Chord uses periodical stabilization process to deal with pointer inconsistency caused by node failures. As a result, some pointers of relevant nodes are incorrect during the intervals between stabilization processes, which again decreases successful lookup ratio. The joining process in Chord is depicted in Fig.1. Assuming that in a Chord ring, node q is successor of node p and node r wants to join the network (a). Node r send join request to a bootstrap node, which forward it again to node q which is a successor of node r. Node q sets predecessor pointer to r and sends the signal join response to node r. Upon receive this signal, node r set its successor pointer to q (b). Before the next stabilization process is invoked at node p, successor pointer of node p is incorrect (c). Consequently, node p will return incorrect result upon receive a lookup for node r. a. Before joining process b. Joining process c. After joining process Figure 1. The problem of pointer inconsistency Chord protocol modifications The modified Chord tries to fix the problem of inconsistent pointers by forcing intermediate stabilization in joining/leaving activities to reduce inconsistency of pointers under failure. We consider node leave as a failure since mobile devices normally leave the network due to energy saving schemes or communication disruption. We adopt a mechanism called “atomic ring maintenance” proposed by [1]. This mechanism uses lock to eliminate concurrent joining. Figure 2 is a sequence diagram describes the modified joining mechanism of a node. Vũ Thành Vinh và cs Tạp chí KHOA HỌC & CÔNG NGHỆ 72(10): 66 - 72 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên | 68 Figure 2. Sequence diagram of the modified joining process As can be seen from the figure, when node r wants to join in network, it takes its lock and send join request signal to a boot strap node. Join request is then forwarded to node q which is a successor of node r (1). If lock of node q is free, it takes the lock and sets predecessor pointer to r and then sends join response to node r (2). Upon receives join response, node r sets its successor pointer to q and predecessor pointer to p. Node r then sends successor hint message to node p to notify node p of new successor (3). After node p receives this message, it sets its successor to node r and also send new successor acknowledge message to node q (4). Node q receive new successor acknowledge message and sets its lock to free, then returns the join done message to node r (5). Finally, node r receives join done message and sets its lock to the “free” state. To avoid deadlock situation, each node has a lock timeout. When a node sets its lock to the “taken” state, it also starts a timer. If the locking time exceeds the default timeout interval, lock is set back to the “free” state. We deal with failure using a combination of proactive stabilization mechanism and lock timeout. Different from algorithm of Ali Ghodsi [1], stabilization not only runs periodically but also is triggered by timeout event. Upon lock timeout, the stabilization process starts immediately at the successor of the new joining node. SIMULATION STUDY Simulation setup In order to verify the efficiency of modified Chord protocol, we implement the adapted atomic ring maintenance mechanism in C++ code of OverSim [12], a new simulator for P2P network developed on top of OMNET ++ framework [11], a popular graphical simulation environment. Two main parameters of Chord and modified Chord: successful lookup ratio and lookup latency are evaluated under the same simulation conditions. Various network sizes from 100 nodes to 2000 nodes are tested under various churn rates from 120s to 720s. Table 1 lists the simulation scenarios and the parameters of basic and modified Chord. Simulation scenarios and Chord parameters Type Parameters Values Simulation parameters Node numbers 100, 500, 1000, 1500, 2000 (node) Churn rates 120, 180, 360, 540, 720 (sec) Common Chord parameters Stabilize delay 10 sec Fix fingers delay 20 sec Successor list size 8 sec Modified Chord parameters Lock timeout 19 sec Results and comments Figure 3 compares successful lookup ratio of basic Chord with that of modified Chord in network of 100, 1000 and 2000 nodes while churn rates varying from 120 sec to 720 sec. Figure 4 compares them under churn rate of 180, 360 and 720s while network sizes vary from 100 nodes to 2000 nodes. From figure 3, we can see that modified Chord achieve successful lookup ratio much higher than that of basic Chord of same network size and under the same churn rate. For example, at churn rate of 200 sec, modified Chord of 100 nodes out-performs basic Chord by a factor of 2. This performance gain is due to the improvement in consistency of successor and predecessor pointers of nodes in modified Chord. 0 0.2 0.4 0.6 0.8 1 0 100 200 300 400 500 600 700 800 Churn rate S u c c e s s f u l l o o k u p r a t i o basic 100 modified 100 basic 1000 modified 1000 basic 2000 modified 2000 Vũ Thành Vinh và cs Tạp chí KHOA HỌC & CÔNG NGHỆ 72(10): 66 - 72 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên | 69 Figure 3. Successful lookup ratio of basic Chord and modified Chord operated in 100, 1000, 2000 node networks under various churn rates Figure 3 also shows that successful lookup ratio of both Chord and modified Chord dramatically decrease when churn rate increase. This ratio drops about more than six times when churn rate goes from 400s to 120s and closes to zero at churn rate higher than 120s. One important reason for this problem is network partitioning which is found when we observed OverSim GUI and real-time log. We found that Chord network tends to partition under high churn rate. The partitioning process happens if a group of nodes in Chord ring have no pointer to live nodes in other groups. We also observed that when churn rate increases, more and more partitions are created. Since nodes in a separated partition can not lookup nodes in other partitions, overall successful lookup ratio dramatically decreases. Figure 4. Successful lookup ratio of basic and modified Chord operated in various network sizes under churn rate of 180s, 360s and 720s Figure 4 shows successful lookup ratio of basic and modified Chord under churn rate of 180s, 360s and 720s as a function of network size. It can be observed that modified Chord can achieve better performance in all cases, up to twofold in a fairly large network of 2000 nodes under high churn rate of 360 sec. However, under extreme high churn rate of 180 sec, both basic and modified Chord show similar poor performance regardless of network size. The second observation from figure 4 is that the successful lookup ratio of both protocols quickly decreases while network size grows from 100 nodes to 500 nodes. This fact hints at the solution of clustering Chord ring into smaller ring for better churn tolerance. Figure 5. Latency of basic Chord and modified Chord operated in 100, 1000, 2000 node networks under various churn rates Figure 5 compares the parameter latency of successful lookup in basic and modified Chord networks of various sizes under various churn rates. As can be observed in these figures, modified Chord has very little effect on latency under every churn rate, (slight increases in some cases) in all network sizing from 100 to 2000 nodes. In order to obtain high fidelity results, we repeat simulations several times for each scenario and calculate the statistical parameter of results from all runs. Figure 6 graphs the Complementary Cumulative Distribution Function (CCDF) of successful lookup ratio of basic and modified Chord networks which consist of 100, 1000, 1500 and 2000 nodes under churn rate of 180s and 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 500 1000 1500 2000 Node Number S u c c e s s f u l l o o k u p r a t i o basic 180 modified 180 basic 360 modified 360 basic 720 modified 720 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0 200 400 600 800 Churn rate L a t e n c y basic 100 modified 100 basic 1000 modified 1000 basic 2000 modified 2000 Vũ Thành Vinh và cs Tạp chí KHOA HỌC & CÔNG NGHỆ 72(10): 66 - 72 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên | 70 360s. The graph shows probability of modified Chord to obtain certain successful lookup ratio is much higher than that of basic Chord to obtain the same ratio in all cases. Figure 6. CCDF of successful lookup ratio in basic and modified Chord networks of 100, 1000 and 2000 nodes under churn rate of 180s and 360s Figure 7 shows the strength and tendency of relationship between successful lookup ratio and churn rate. As can be seen from the figure, there is a strong positive correlation between successful lookup ratio and churn rates in both basic Chord and modified Chord for all network sizes ranging from 100-2000 nodes. Modified Chord shows weaker dependency on churn rate, which means it is more tolerant to churn. Figure 7. Correlation coefficients between successful lookup ratio and churn rates of modified and basic Chord versus network sizes Figure 8. Correlation coefficient between successful lookup ratio and node number of modified and basic Chord versus churn rates ranging from 120 to 720sec Figure 9. Correlation coefficients between successful lookup ratio and fix finger delay and that between successful lookup ratio and stabilize delay under various churn rates Figure 8 shows weaker negative correlation strength between successful lookup ratio and node number under various churn rates. In another word, Chord shows high scalability even under high churn rate. We investigate the dependency of successful lookup ratio on two important Chord parameters, fix finger delay and stabilize delay. Figure 9 shows the correlation strength between successful lookup ratio of both basic and modified Chord and these parameters. One can observe that fix finger delay has stronger effect on the performance of both basic and modified Chord than stabilize delay. CONCLUSION AND FUTURE WORK In this study, we propose a modified Chord protocol with locking mechanism and new stabilization strategy to ensure the correctness of node pointers under high churn rate. We also successfully implement the modified Successful lookup ratio vs. CCDF 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 0 0,2 0,4 0,6 0,8 1 Successful lookup ratio C C D F basic_1000_360 modified_1000_360 basic_2000_360 modified_2000_360 basic_100_180 modified_100_180 0.88 0.9 0.92 0.94 0.96 0.98 1 0 500 1000 1500 2000 Node numbers C o r r e l a t i o n C o e f f i c i e n t Ratio_churn_basic Ratio_churn_modified -1 -0.9 -0.8 -0.7 -0.6 -0.5 -0.4 0 100 200 300 400 500 600 700 800 Churn rates C o r r e la ti o n C o e ff ic ie n t Ratio_nodes_basic Ratio_nodes_modified -1 -0.9 -0.8 -0.7 -0.6 -0.5 -0.4 100 200 300 400 500 600 700 800 Churn rates C o r r e l a t i o n C o e f f i c i e n t FingerDelay_Ratio_Modified StabilizeDelay_Ratio_Modified FingerDelay_Ratio_Basic StabilizeDelay_Ratio_Basic Vũ Thành Vinh và cs Tạp chí KHOA HỌC & CÔNG NGHỆ 72(10): 66 - 72 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên | 71 Chord in OverSim simulator to verify the new protocol. The simulation results show significant improvement in successful lookup ratio of modified Chord over basic Chord under various conditions of churn rate and network size. However, our modification of the Chord protocol does not affect much on other aspects of Chord such as lookup latency. We also found the serious impact of churn on Chord topology, called ring-partitioning, which results in sharp performance degradation. Both basic and modified Chord has a churn rate limit around 120 sec where most of lookups fails. Another interesting result found is that smaller Chord network of a few hundreds nodes outperform larger network of more than about 500 nodes under churn. This fact leads to a possible solution of mitigating churn effect by clustering large Chord ring into multiple smaller rings connected through a second level overlay. We also discovered that churn rate affects Chord performance much more than network sizes and the parameter fix finger delay have greater effect on Chord than stabilization delay. In the next phase of our study, we will study the feasibility of this solution and develop mechanisms for modified Chord to deal with network partitioning under very high churn rate. To further improve Chord performance under churn, we are investigating a DHT proxy mechanism for caching lookup and correcting lookup results. REFERENCES [1]. Ali Ghodsi. “Distributed k-ary System: Algorithms for Distributed Hash Tables”, PhD dissertation, KTH-Royal Institute of Technology, 2006. [2]. Hung Nguyen Chan, Vinh Vu Thanh, etc “Performance improvement of Chord Distributed Hash Table under high churn rate”, International Conferences on Advanced Technologies for Communications ATC2009, Ha Noi, Vietnam. [3]. Vu Thanh Vinh, Hung Nguyen Chan, Pham Viet Binh, “Analysis and identification of Peer-to-Peer traffic in the WIDE backbone”, Proceedings of the 3rd International Conference on Ubiquitous Information Technologies and Appliction (ICUT -3), Ho Chi Minh, Vietnam, pp. 294-299, 2008. [4]. S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz, “Handling churn in a DHT,” in Proceedings of the 2004 USENIX Technical Conference, June 2004. [5]. Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, and Hari Balakrishnan. “Chord: A scalable Peer-To-Peer lookup service for internet applications”. In Proceedings of the 2001 ACM SIGCOMM Conference, pages 149–160, 2001. [6]. N. A. Lynch, D. Malkhi, and D. Ratajczak. “Atomic Data Access in Distributed Hash Tables”. In Proceedings of the First Interational Workshop on Peer-to-Peer Systems (IPTPS'02), Lecture Notes in Computer Science (LNCS), pages 295-305, London, UK, 2002. Springer-Verlag. [7]. B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz, “Tapestry: A resilient global-scale overlay for service deployment,” IEEE Journal on Selected Areas in Communications, vol. 22, no. 1, pp. 41–53, Jan. 2004. [8]. P. Maymounkov and D. Mazieres, "Kademlia: A Peer-to-Peer Information System based on the XOR Metric," presented at International Workshop on Peer-to-Peer Systems (IPTPS), 2002. [9]. M. F. Kaashoek and D. R. Karger. “Koorde: A Simple Degree-optimal Distributed Hash Table”. In Proceedings of the 2nd Interational Workshop on Peer-to-Peer Systems (IPTPS’03), volume 2735 of Lecture Notes in Computer Science (LNCS), pages 98–107, Berkeley, CA, USA, 2003. Springer-Verlag. [10]. G. S. Manku, M. Bawa, and P. Raghavan. “Symphony: Distributed Hashing in a Small World”. In Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS’03), Seattle, WA, USA, March 2003. USENIX. [11]. Omnet++, [12]. OverSim, Vũ Thành Vinh và cs Tạp chí KHOA HỌC & CÔNG NGHỆ 72(10): 66 - 72 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên | 72 TÓM TẮT ĐÁNH GIÁ SỰ TƯƠNG QUAN GIỮA TỶ LỆ TÌM KIẾM THÀNH CÔNG VỚI KÍCH THƯỚC VÀ ĐỘ ỔN ĐỊNH CỦA CHORD TRONG MÔI TRƯỜNG TRUYỀN THÔNG KHÔNG DÂY Vũ Thành Vinh1, Nguyễn Chấn Hùng2, Nguyễn Tuấn Anh 3 1Khoa Công nghệ Thông tin – ĐH Thái Nguyên 2Đại học Bách khoa Hà Nội 3Đại học Thái Nguyên Một trong những vấn đề quan trọng nhất của các ứng dụng ngang hàng (P2P) là độ ổn định của mạng ảnh hưởng tới hiệu quả tìm kiếm dữ liệu, là một chức năng cơ bản của các mạng P2P. Đặc biệt, khi mạng P2P làm việc trong môi trường di động, thì độ ổn định có thể ảnh hưởng lớn đến toàn bộ hệ thống và dịch vụ của mạng P2P. Trong bài báo này, chúng tôi đã sửa đổi thuật toán duy trì vòng nguyên tử cho giao thức Chord nhằm giảm thiểu ảnh hưởng của độ ổn định tới chất lượng dịch vụ của mạng P2P. Kết quả mô phỏng cho thấy sự cải thiện đáng kể tỷ lệ tìm kiếm thành công của giao thức Chord trong điều kiện mạng có độ ổn định thấp, trong khi đó độ trễ tìm kiếm thành công tốt như với Chord trước khi thay đổi. Đồng thời, chúng tôi cũng đưa ra những đánh giá về sự tương quan giữa tỷ lệ tìm kiếm thành công với kích thước và độ ổn định của mạng nhằm đưa ra mối liên hệ giữa các yếu tố đó với nhau. Từ khóa: Mạng ngang hàng, Bảng băm phân tán, thuật toán Chord, P2P, hiệu năng của Chord DHT, Chord, tìm kiếm, đánh giá Chord  Tel: 0982782966; Email: vtvinhtnu@gmail.com