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

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.
Nội dung trích xuất từ tài liệu:
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ấpPhạm Thành Nam và ĐtgTạp chí KHOA HỌC & CÔNG NGHỆ116 (02): 61 - 66CẢI TIẾN HIỆU NĂNG THUẬT TOÁN CHORD DHTTRONG ĐIỀU KIỆN MẠNG CÓ ĐỘ ỔN ĐỊNH THẤPPhạm Thành Nam*, Mạc Thị Phượng, Nguyễn Thị Minh HuyềnTrường Đại học Công Nghệ Thông tin và Truyền Thông - ĐH Thái NguyênTÓM TẮTTrong 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ôitrườ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àygặ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ủacá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ácnú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ỉ rarằ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 DHTCác nghiên cứu về DHT đã được phát triểnbở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àithực tế. Các kiến thức về DHT hiện có chẳnghạn như là Chord[7], Kademlia[11],Tapestry[2], đó sẽ là các điểm bắt đầu cho cácnghiên cứu phát triển kiến trúc bảng bămphâ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ềucách khác nhau. Trong phạm vi nghiên cứunày chúng tôi tập trung vào nghiên cứu cảitiến thuật toán tổ chức bảng băm phân tánChord DHT trong điều kiện mạng ổn địnhthấp (các nút gia nhập/rời đi khỏi mạng trongthờ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ủathuậ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ậpcủ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, tuynhiên trong thuật toán này có các nhược điểmđó là:*Email: ptnam@ictu.edu.vnDuy trì một thẻ bài làm cho tại một thời điểmnút mạng chỉ xử lý được một yêu cầu gianhập mạng.Chưa có cơ chế xử lý cho tiến trình rời đi củacá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útmạng gia nhập mạng tiến hành cập nhập tứcthời bảng định tuyến.Cơ chế thứ hai dành cho tiến trình rời đi khỏimạng của các nút. Khi các nút rời mạng tiếnhành thông báo tới các nút bên cạnh nó cậpnhập lại bảng định tuyến.Chúng tôi tiến hành đánh giá hiệu năng thuậttoán mới chúng tôi đề xuất bằng phương phápmô phỏng và được thực hiện trên công cụ môphỏng OMNeT++. Đây là công cụ mô phỏngmạng P2P rất phổ biến hiện nay dành cho họctập và nghiên cứu.Các điểm yếu của Chord DHT trong điềukiện mạng có độ ổn định thấpTrong 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ácnghiên cứu [4], [5], [8], [12] trong điều kiệnmạng P2P tổ chức theo Chord có độ ổn định61Phạm Thành Nam và ĐtgTạp chí KHOA HỌC & CÔNG NGHỆ116 (02): 61 - 66thấ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ứcthờ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ưutrữ kết quả tìm kiếm.Một trong những lý do chính cho việc suygiảm hiệu năng mạng Chord khi có biến độngvề nút mạng đó chính là sự không chính xáccủa con trỏ các nút trong mạng. Chính cáccon 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 gianhập vào mạng, mạng Chord không ngay lậptức kiểm tra các con trỏ successor vàpredecessor của tất cả các nút xung quanh nútmớ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ủacác con trỏ còn lại. Tương tự, Chord sử dụngtiến trình ổn định mạng có tính chu kỳ để điềuchỉnh lại các con trỏ không còn chuẩn xác khicác nút trong mạng bị hỏng. Khi mà có nútmới gia nhập vào mạng, dẫn đến một vài contrỏ tới nút lân cận không còn chính xác nữatrong 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ìmkiếm không chính xác trong khoảng thời giannà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 minhnhư sơ đồ hình 1. Giả sử rằng trên vòngChord, 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 IDcủa p và q (a). Nút r sẽ gửi bản tin joinrequest đến một nút bootstrap mà nó biếttrước, nút này ...