Cải tiến hiệu năng thuật toán chord dht trong điều kiện mạng có độ ổn định thấp - Phạm Thành Nam

Phạm Thành Nam và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 61 - 66 61 CẢI TIẾN HIỆU NĂNG THUẬT TOÁN CHORD DHT TRONG ĐIỀU KIỆN MẠNG CÓ ĐỘ ỔN ĐỊNH THẤP Phạm Thành Nam*, Mạc Thị Phƣợng, Nguyễn Thị Minh Huyền Trường Đại học Công Nghệ Thông tin và Truyền Thông - ĐH Thái Nguyên TÓM TẮT Trong các mạng Peer-to-Peer (P2P) có cấu trúc đƣợc tổ chức theo các bảng băm phân tán DHT thì vấn đề quan trọng là việc tìm kiếm dữ liệu chính xác và nhanh nhất. Ngày nay trong các môi trƣờng mạng tổ hợp gồm nhiều các thành phần tham gia vào mạng, việc quản lý các nút mạng này gặp nhiều khó khăn. Khi mạng ổn định thấp có nghĩa là thời gian gia nhập và rời đi khỏi mạng của các nút diễn ra trong thời gian ngắn dẫn tới cần phải tìm ra các cơ chế quản lý để đảm bảo duy trì hiệu năng tìm kiếm dữ liệu ổn định trong mạng. Trong bài báo này, chúng tôi đề xuất một thuật toán mới cho việc quản lý các nút gia nhập và rời đi khỏi mạng khi mạng Peer-to-Peer đƣợc tổ chức theo thuật toán Chord DHT trong mạng có độ ổn định thấp. Thuật toán của chúng tôi đề xuất tiến hành cập nhập tức thời bảng định tuyến của các nút mạng khi có sự gia nhập/rời đi mới của các nút. Các kết quả mô phỏng của thuật toán đã chỉ ra rằng thuật toán của chúng tôi cải tiến đáng kể hiệu năng mạng Chord trong điều kiện mạng có độ ổn định thấp. Từ khóa: P2P, DHT, DHT Chord, churn rate, DHT performance, lookup, Successor node, Predecessor node. GIỚI THIỆU* Giới thiệu chung về Chord DHT Các nghiên cứu về DHT đã đƣợc phát triển bởi các trƣờng đại học, đƣợc lấy ra từ cộng đồng mã nguồn mở và đƣợc triển khai ngoài thực tế. Các kiến thức về DHT hiện có chẳng hạn nhƣ là Chord[7], Kademlia[11], Tapestry[2], đó sẽ là các điểm bắt đầu cho các nghiên cứu phát triển kiến trúc bảng băm phân tán. Mỗi loại trong số chúng có vô số các thuộc tính mà có thể kết hợp trong nhiều cách khác nhau. Trong phạm vi nghiên cứu này chúng tôi tập trung vào nghiên cứu cải tiến thuật toán tổ chức bảng băm phân tán Chord DHT trong điều kiện mạng ổn định thấp (các nút gia nhập/rời đi khỏi mạng trong thời gian ngắn). Trong bài báo này chúng tôi đề xuất hai cơ chế để cải tiến hiệu năng tìm kiếm dữ liệu của thuật toán Chord DHT đƣợc giới thiệu trong [7]. Thuật toán [5] cải tiến quá trình gia nhập của các nút bằng cách đƣa ra một cơ chế thông báo cập nhập lại bảng định tuyến, tuy nhiên trong thuật toán này có các nhƣợc điểm đó là: * Email: ptnam@ictu.edu.vn Duy trì một thẻ bài làm cho tại một thời điểm nút mạng chỉ xử lý đƣợc một yêu cầu gia nhập mạng. Chƣa có cơ chế xử lý cho tiến trình rời đi của các nút trong mạng. Do đó chúng tôi đề xuất sử dụng 2 cơ chế mới: Cơ chế đầu tiên để điều chỉnh cho các nút mạng gia nhập mạng tiến hành cập nhập tức thời bảng định tuyến. Cơ chế thứ hai dành cho tiến trình rời đi khỏi mạng của các nút. Khi các nút rời mạng tiến hành thông báo tới các nút bên cạnh nó cập nhập lại bảng định tuyến. Chúng tôi tiến hành đánh giá hiệu năng thuật toán mới chúng tôi đề xuất bằng phƣơng pháp mô phỏng và đƣợc thực hiện trên công cụ mô phỏng OMNeT++. Đây là công cụ mô phỏng mạng P2P rất phổ biến hiện nay dành cho học tập và nghiên cứu. Các điểm yếu của Chord DHT trong điều kiện mạng có độ ổn định thấp Trong môi trƣờng mạng vô tuyến có độ ổn định thấp (churn rate cao) thì mạng Chord đã bộc lộ rõ các điểm yếu của mình. Trong các nghiên cứu [4], [5], [8], [12] trong điều kiện mạng P2P tổ chức theo Chord có độ ổn định Phạm Thành Nam và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 61 - 66 62 thấp thì mạng Chord bộc lộ các điểm yếu: không có sự cập nhập bảng định tuyến tức thời khi có sự thay đổi nút mạng, không có cơ chế sao chép các khóa, không có cơ chế lƣu trữ kết quả tìm kiếm. Một trong những lý do chính cho việc suy giảm hiệu năng mạng Chord khi có biến động về nút mạng đó chính là sự không chính xác của con trỏ các nút trong mạng. Chính các con trỏ này đƣợc sử dụng chủ yếu trong hoạt động tìm kiếm trong mạng. Khi một nút gia nhập vào mạng, mạng Chord không ngay lập tức kiểm tra các con trỏ successor và predecessor của tất cả các nút xung quanh nút mới gia nhập đó. Thay vào đó, Chord chỉ kiểm tra vài con trỏ và tin vào tiến trình ổn định mạng trƣớc để kiểm tra sự chuẩn xác của các con trỏ còn lại. Tƣơng tự, Chord sử dụng tiến trình ổn định mạng có tính chu kỳ để điều chỉnh lại các con trỏ không còn chuẩn xác khi các nút trong mạng bị hỏng. Khi mà có nút mới gia nhập vào mạng, dẫn đến một vài con trỏ tới nút lân cận không còn chính xác nữa trong khoảng thời gian chờ đến tiến trình gọi ổn định lại mạng và kết quả dẫn đến việc tìm kiếm không chính xác trong khoảng thời gian này do đó làm giảm hiệu năng của mạng. Tiến trình gia nhập mạng Chord đƣợc minh nhƣ sơ đồ hình 1. Giả sử rằng trên vòng Chord, nút q đang là successor của nút p và nút r muốn gia nhập mạng có ID nằm giữa ID của p và q (a). Nút r sẽ gửi bản tin join request đến một nút bootstrap mà nó biết trƣớc, nút này sẽ chuyển tiếp bản tin join request này tới nút q mà nó sẽ là successor của nút r. Nút q sẽ thiết lập con trỏ predecessor của nó vào nút r và gửi bản tin báo hiệu join response đến nút r. Trong khoảng thời gian nhập bản tin này, nút r cũng tiến hành thiết lập con trỏ successor của nó vào nút q (b). Trƣớc thời điểm gọi chu kỳ ổn định lại mạng tiếp theo tại nút p, con trỏ successor của nút p không còn chính xác (c). Điều này dẫn đến nút p sẽ trả về kết quả không chính xác khi nhận đƣợc một tìm kiếm cho nút r trong khoảng thời gian này. (a) Trước khi nút r gia nhập (b) Tiến trình gia nhập mạng của nút r (c) Sau tiến trình gia nhập Hình 1. Sự không chính xác của con trỏ các nút trong tiến trình gia nhập mạng. Các nghiên cứu liên quan Các cơ chế giải quyết vấn đề không chính xác của con trỏ các nút trong tiến trình gia nhập mạng đƣợc đƣa ra nhƣ là “automic ring maintenance” của Ali Ghodsi[1]. Cơ chế này sử dụng một thẻ lock để hạn chế việc đồng thời gia nhập mạng của các nút. Trong nghiên cứu của mình, nhóm tác giả Nguyen Chan Hung[5] đã đƣa ra một cơ chế đƣợc phát triển lên từ nghiên cứu của Ali Ghodsi gọi là MRLChord (Modify Ring Lock for Chord DHT). Hình 2 là một biểu đồ tuần tự mô tả cơ chế gia nhập đã đƣợc sửa đổi của một nút vào mạng theo cơ chế MRLChord. Hình 2. Biểu đồ tuần tự biểu diễn tiến trình gia nhập mạng của thuật toán MRLChord Phạm Thành Nam và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 61 - 66 63 Từ biểu đồ trên ta có thể thấy khi một nút r muốn gia nhập mạng, nó giữ thẻ bài và gửi bản tin báo hiệu xin gia nhập mạng đến một nút bootstrap. Yêu cầu gia nhập mạng này sau đó đƣợc chuyển tiếp tới nút q là successor của nút r(1). Nếu thẻ lock mà nút q đang giữ ở trạng thái free, nút q này sẽ thiết lập thẻ lock = taken điều này giúp cho nút q luôn ở trạng thái bận với các yêu cầu đến khác. Sau đó nó gửi bản tin join response về cho nút r(2). Khi nhận đƣợc bản tin join response, nút r thiết lập con trỏ successor của nó tới nút q và con trỏ predecessor tới nút p. Nút r sau đó gửi bản tin successor hint tới nút p để thông báo cho nút p biết về successor mới (3). Sau khi nút p nhận đƣợc bản tin này, nó thiết lập con trỏ successor của nó tới nút r và đồng thời cũng gửi bản tin successor acknowledge tới nút q (4). Nút q khi nhận đƣợc bản tin này sẽ thiết lập thẻ lock = free, sau đó trả về bản tin join done đến nút r (5). Cuối cùng nút r nhận bản tin join done và thiết lập thẻ lock = free. Để tránh tình huống deadlock, mỗi nút có một định thời lock timeout. Khi một nút thiết lập thẻ lock của nó sang trạng thái “taken”, nó cũng bắt đầu định thời. Nếu vƣợt quá thời gian định thời thì thẻ lock sẽ đƣợc thiết lập sang trạng thái “free”. Ở đây có sự kết hợp giữa cơ chế stabilization và lock timeout. Sự khác biệt so với thuật toán Ali Ghodsi[1] đó là quá trình stabilization trong mạng không chỉ chạy theo chu kỳ mà còn đƣợc lật theo sự kiện timeout. ĐỀ XUẤT THUẬT TOÁN MCHORD CẢI TIẾN HIỆU NĂNG MẠNG P2P CHORD Cơ chế sửa đổi cho tiến trình gia nhập mạng Dựa theo các nghiên cứu [1], [5] chúng tôi đề xuất một cơ chế giải quyết bài toán hiệu năng tìm kiếm dữ liệu của Chord DHT trong điều kiện mạng có độ ổn định thấp gọi là “Modified Chord - MChord”. Khác với nghiên cứu [5] ở đây các nút trong mạng Chord không cần phải duy trì thẻ bài lock, điều này cho phép các nút đƣợc tự do xử lý các yêu cầu gia nhập mạng đồng thời trao đổi các bản tin RPC tại mọi thời điểm mà không cần phải đợi đến khi thẻ bài lock = free nhƣ trên. Khi nút gia nhập mạng thì ngay lập tức nó sẽ thông báo cho nút successor và predecessor của nó cập nhập ngay các con trỏ của mình. Điều này giúp làm tăng thêm độ chính xác của quá trình tìm kiếm dữ liệu. Hình 3. Biểu đồ tuần tự biểu diễn tiến trình gia nhập mạng của một nút sử dụng thuật toán MChord Từ trên biểu đồ ta có thể thấy khác với hoạt động gia nhập mạng bình thƣờng khi một nút r muốn gia nhập mạng nó gửi bản tin báo hiệu xin gia nhập mạng đến một nút bootstrap. Yêu cầu gia nhập mạng này sau đó đƣợc chuyển tiếp tới nút q là successor của nút r(1). Khi mà q nhận đƣợc yêu cầu gia nhập mạng của nút r thì nó ngay lập tức sẽ cập nhập con trỏ predecessor của nó về nút r thay vì nút p cũ. Sau đó nó gửi bản tin join response về cho nút r(2). Khi nhận đƣợc bản tin join response, nút r thiết lập con trỏ successor của nó tới nút q và con trỏ predecessor của nó tới nút p. Nút r sau đó gửi bản tin successor hint tới nút p để thông báo cho nút p biết về successor mới (3). Sau khi nút p nhận đƣợc bản tin này, nó thiết lập ngay lập tức con trỏ successor của nó tới nút r thay vì nút q cũ. Nhƣ vậy tiến trình gia nhập mạng mới này khác với tiến trình cũ đó là không cần phải đợi đến chu kỳ ổn định mạng tiếp theo các nút mới tiến hành cập nhập lại các con trỏ của mình. Khi nhận đƣợc yêu cầu gia nhập mạng thì các nút lân cận nút gia nhập mạng sẽ ngay lập tức tiến hành cập nhập lại các con trỏ của mình. Do đó luôn đảm bảo sự chuẩn xác của các con trỏ trong mạng và làm tăng hiệu năng tìm kiếm dữ liệu trong mạng. Phạm Thành Nam và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 61 - 66 64 Thuật toán MChord của chúng tôi cho tiến trình gia nhập mạng có nhiều ƣu điểm hơn so với thuật toán MRLChord đó là sử dụng số lƣợng bản tin ít hơn nên sẽ giảm tải trọng trong mạng. Không sử dụng thẻ bài nên các nút có thể tự do trao đổi các bản tin RPC tại mọi thời điểm mà không cần phải đợi khi thẻ bài đƣợc giải phóng. Cơ chế sửa đổi cho tiến trình rời mạng Trong thực tế trong môi trƣờng mạng có churn rate cao nhƣ môi trƣờng các mạng vô tuyến không dây thì hiện tƣợng các nút rời mạng một cách ngẫu nhiên và không có thông báo là phổ biến. Khi đó con trỏ của các nút lân cận với nút vừa rời đi khỏi mạng sẽ không còn chính xác khi mà vẫn chƣa đến thời gian gọi tiến trình stabilization ổn định lại mạng. Nếu trong khoảng thời gian này có yêu cầu tìm kiếm tới các nút vừa rời đi sẽ dẫn tới kết quả trả về không chính xác. Để khắc phục hiện tƣợng này chúng tôi đƣa ra một cơ chế khi các nút rời khỏi mạng có thông báo để các nút lân cận nút rời đi này cập nhập lại chính xác con trỏ của chúng. Hình 4 minh họa cơ chế một nút r rời khỏi mạng có thông báo Hình 4. Minh họa tiến trình rời mạng có thông báo Biểu đồ tuần tự mô tả tiến trình rời mạng có thông báo đƣợc mô tả trong hình 5. Nút r nằm trên vòng Chord có ID nằm giữa ID nút p và q. Một nút r chuẩn bị rời mạng sẽ gửi cho nút successor q của nó bản tin new predecessor hint thông báo về predecessor mới của nó bây giờ là nút p(1). Tƣơng tự nó cũng gửi bản tin new successor hint cho predecessor p của nó để thông báo về successor mới của nó bây giờ là nút q(2). Nút p sau khi nhận đƣợc bản tin này sẽ gửi lại bản tin successor acknowledge tới nút q(3) để thông báo tiến trình cập nhập thành công. Hình 5. Biểu đồ tuần tự thể hiện quá trình rời đi có thông báo ĐÁNH GIÁ THUẬT TOÁN MCHORD Thiết lập các thông số mô phỏng Chúng tôi triển khai đánh giá thuật toán MChord bằng cách sử dụng công cụ mô phỏng OverSim[6]. Đây là công cụ mô phỏng mạng P2P đƣợc phát triển trên khung làm việc OMNeT++ framework[10], hiện nay đang trở nên phổ biến sử dụng trong học tập và nghiên cứu. Bảng 1. Kịch bản cài đặt các tham số mô phỏng Loại tham số Tên tham số Giá trị Tham số mô phỏng chung Node numbers 100, 500, 1000, 1500, 2000 (node) Churn rates 120, 180, 360, 540, 720 (s) Các tham số cơ bản mạng Chord Stabilize delay 10 (s) Fix fingers delay 20 (s) Successor list size 8 Chord Modified xacSuat_leaveN otify 0.5 aggressiveJoin Mode true Chúng tôi tiến hành mô phỏng thuật toán MChord trên cùng một bộ tham số so với thuật toán MRLChord[5] để so sánh đánh giá. Phạm Thành Nam và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 61 - 66 65 Để mô tả mạng có độ ổn định thấp chúng tôi thay đổi các tham số churn rates trong dải từ 120s – 720s. Bảng 1 chỉ ra kịch bản cài đặt các tham số mô phỏng. Hình 6. So sánh tỉ lệ tìm kiếm dữ liệu thành công giữa MRLChord vs MChord khi churn rate thay đổi Hình 7. So sánh tỉ lệ tìm kiếm thành công giữa thuật toán MRLChord vs MChord khi số node mạng thay đổi Phân tích kết quả Hình 6 so sánh kết quả tỉ lệ tìm kiếm thành công của thuật toán MRLChord và MChord trong các điều kiện churn rate khác nhau. Có thể thấy rằng mạng Chord modified đạt đƣợc tỉ lệ tìm kiếm dữ liệu thành công cao hơn so với mạng MRLChord trong tất cả các trƣờng hợp. Tuy nhiên khi mạng biến động lớn churn rate từ 120s đến 180s thì tỉ lệ tìm kiếm dữ liệu thành công trong mạng vẫn còn thấp mặc dù đƣợc cải thiện đáng kể so với thuật toán MRLChord. Hiệu năng mạng MChord chỉ tăng nhanh và đạt ổn định khi churn rate > 540s. Để đánh giá hiệu năng tìm kiếm dữ liệu của mạng MChord và MRLChord chúng tôi còn tiến hành điều chỉnh các kích thƣớc mạng từ 100 nodes tới 2000 nodes. Kết quả so sánh đƣợc mô tả nhƣ trong hình 7. Chúng ta có thể quan sát thấy rằng hiệu năng tìm kiếm dữ liệu của cả hai thuật toán đều giảm khi số lƣợng các nút mạng tăng lên. KẾT LUẬN Trong bài báo này chúng tôi đã đề xuất một thuật toán MChord mới giúp cải thiện hiệu năng tìm kiếm dữ liệu trong mạng Chord. Chúng tôi có đánh giá so sánh với các nghiên cứu trƣớc đó của Ali Ghodsi[1] và thuật toán MRLChord đƣợc giới thiệu trong [5]. Các kết quả mô phỏng bằng công cụ mô phỏng mạng OverSim đã chỉ ra rằng thuật toán của chúng tôi cải tiến đáng kể hiệu năng tìm kiếm dữ liệu của mạng Chord. Kết quả mô phỏng cũng chỉ ra rằng thuật toán của chúng tôi đề xuất luôn có tỉ lệ tìm kiếm dữ liệu thành công cao hơn so với thuật toán MRLChord. Tƣơng lai, nghiên cứu có thể tiến hành triển khai thuật toán của chúng tôi trên các cấu trúc mạng Peer-to-Peer khác nhƣ là Kademlia, TapeStry. Hoặc tiến hành các cơ chế khác để nâng cao hiệu năng tìm kiếm dữ liệu trong mạng nhƣ là thực hiện các cơ chế lƣu trữ kết quả tìm kiếm, thực hiện các phƣơng thức định tuyến dữ liệu chính xác nhanh gọn khác. TÀI LIỆU THAM KHẢO 1. Ali Ghodsi. (2006) “Distributed k-aray System: Algorithms for Distributed Hash Table”, PhD dissertation, KTH-Royal Insitude of Technology. 2. B. Zhao, J. Kubiatowicz, and A. Joseph, (2001) “Tapestry: An Infrastructure for Fault-Tolerant Wide-Area Location and Routing,” Computer. 3. Gurmeet Singh Manku. Dipsea (August 2004): A Modular Distributed Hash Table. Ph. D. Thesis (Stanford University). 4. Hung Nguyen Chan, Giang Ngo Hoang, Thang Le Quang, Tan Pek Yew, (12/2007) “Performance study of Chord, Kelips and Tapestry protocols on structured Peer-to-Peer Overlay Networks”, Special issues of Post & Telecommunications & Information Technology Journal, issue 2. 5. Hung Nguyen Chan, Giang Ngo Hoang, 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. Phạm Thành Nam và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 61 - 66 66 6. 7. Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan. (August 2001) “ Chord : A scalable Peer-to-peer Lookup Service for Internet Applications”, MIT Laboratory for Computer Science. 8. Jinyang Li, Jeremy Stribling, Thomer M. Gil, Robert Morris, and M. Frans Kaashoek, (2004) “Comparing the Performance of Distributed Hash Tables Under Churn”, LNCS 3279, pp. 87-89, Spinger-Verlag Berlin Heidelberg. 9. Moni Naor and Udi Wieder. (2003) Novel Architectures for P2P Applications: the Continuous- Discrete Approach. Proc. SPAA. 10. Omnet ++, 11. P. Maymounkov and D. Mazieres, (2002) “Kademlia: A Peer-to-Peer Information System Based on the XOR Metric,” Preceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS’02), vol. 258, p. 263. 12. Vũ Chiến Thắng, Phạm Việt Bình, Vũ Thành Vinh, Nguyễn Chấn Hùng, “Đánh giá hiệu năng của giao thức Chord trên mạng P2P trong điều kiện mạng có độ ổn định thấp”, Tạp chí Khoa học & Công nghệ Đại học Thái Nguyên) Tập 54, số 6(95, 2009, tr 95-99). 13. Xuemin Shen, Heather Yu, John Buford, Mursalin Akon, (2009) “Handbook of Peer-to- Peer Networking”, Spinger. SUMMARY IMPROVE THE PERFORMANCE OF CHORD DHT IN TERMS OF LOW NETWORK STABILLITY Pham Thanh Nam * , Mac Thi Phuong, Nguyen Thi Minh Huyen College of Information and Communication Technology – TNU Today, in the P2P network that consists of many different components, the main problem is that there are appropriate mechanisms to help manage the search for fast and accurate data possible. Complex network environments have low stability (node joining/leaving the network in short time) require management mechanisms to maintain search performance data stability in network. In this paper, we propose a new algorithm to manage process node joining and leaving the network from Peer-to-Peer networks are organized by Chord DHT algorithm at high churn rate. Our algorithm is proposed to conduct instant update of the routing table when the nodes join/ leave the network. Keywords: P2P, DHT, DHT Chord, Churn rate, DHT performance, latency, lookup, successor node, predecessor node Ngày nhận bài:25/01/2014; Ngày phản biện:10/02/2014; Ngày duyệt đăng: 26/02/2014 Phản biện khoa học: TS. Phùng Trung Nghĩa – Trường ĐH Công nghệ Thông tin & Truyền thông - ĐHTN * Email: ptnam@ictu.edu.vn