Tóm tắt Luận án Nghiên cứu tổng quan về mạng P2P, (2) đề xuất các giải pháp cải thiện hiệu năng hệ thống mạng P2P và (3) kiểm chứng các giải pháp đã đề xuất

tiếp cận muc̣ tiêu của luận án. 1.1 Tổng quan về maṇg ngang hàng Mạng chồng phủ ngang hàng là mạng máy tính được xây dựng trên nền của một mạng khác. Các nút trong mạng ngang hàng được kết nối với nhau bằng liên kết logic, mỗi liên kết logic có thể bao gồm rất nhiều các liên kết vật lý của mạng nền tảng (Internet). Hình 1-1. Mô hiǹh maṇg chồng phủ ngang hàng Overlay IP -2- 1.1.1 Kiến trúc maṇg ngang hàng P2P Chia sẻ file, tin nhắn tức thời, luồng video, phân tán, tính toán, Application Layer ( Lớp ứng duṇg) Quản lý nút maṇg phủ, quản lý và tìm kiếm tài nguyên, Overlay Network Layer ( Lớp maṇg chồng phủ) TCP, UDP/IP Underlying Network Layer ( Lớp maṇg nền ) Hình 1-2. Kiến trúc phân lớp điển hiǹh maṇg ngang hàng P2P Dưạ trên cấu trúc và thuâṭ toán điṇh tuyến trong lớp maṇg chồng phủ, kiến trúc maṇg chồng phủ P2P đươc̣ chia thành mô hình tâp̣ trung, phân tán và lai ghép [48], [63]. Mô hình phân tán đươc̣ chia làm hai loaị không cấu trúc, có cấu trúc, phân cấp và không phân cấp. 1.1.2 Thách thức khi nghiên cứu maṇg ngang hàng P2P Bên cạnh các ưu điểm về khả năng mở rộng, khả năng chịu đựng lỗi, dễ dàng triển khai, chính cơ chế truyền thông ngang hàng và các yêu cầu cung cấp chất lươṇg dịch vụ, đã cho thấy một số thách thức mà maṇg P2P cần phải vươṭ qua về mặt hiệu năng: Tính động (Churn rate); Không đồng nhất hiệu năng giữa mạng chồng phủ ngang hàng và mạng nền (Topology Mismatch); Tính bảo mật; Đô ̣ tin câỵ ; Cân bằng tải. 1.2 Tham số hiêụ năng maṇg ngang hàng - Đô ̣dài đường tìm kiếm (Query path length ) - Tỷ lê ̣tìm kiếm thành công (Lookup Success Rate) - Đô ̣dài đường tìm kiếm trung bình (Mean Hop Count) - Trễ (Latency) -3- - Tỷ lê ̣trê ̃dãn cách trung biǹh (Average stretch) Tstretch là tỷ số giữa trễ trung bình tìm kiếm qua mạng chồng phủ P2P và trễ trung bình tìm kiếm qua mạng nền (IP). IPdelay overlaydelay T T   stretchT (1.3) - Băng thông tiêu tốn (bandwidth consumption) 1.3 Các hướng tiếp câṇ nghiên cứu cải thiêṇ hiêụ năng maṇg ngang hàng 1.3.1 Các công trình nghiên cứu trong nước Ở Việt Nam số lượng các kết quả nghiên cứu về các vấn đề liên quan đến hệ thống P2P phân cấp còn rất hạn chế. 1.3.2 Các công trình nghiên cứu trên thếgiới Để có thể triển khai các dic̣h vu ̣ trên quy mô lớn hầu hết nghiên cứu đều tâp̣ trung vào maṇg ngang hàng có cấu trúc. Qua khảo sát hướng nghiên cứu cải thiêṇ hiêụ năng của tác giả trước chủ yếu tập trung vào hai hướng chính: (i) Hướng nghiên cứu thứ nhất: Tối ưu cấu trúc maṇg chồng phủ: các tác giả trước đều tâp̣ trung giải quyết hai vấn đề: Mạng có có độ ổn định thấp và hiệu năng không đồng nhất giữa mạng nền và maṇg chồng phủ. Mô hiǹh phân cấp có hiêụ năng điṇh tuyến tốt hơn so với mô hình không phân cấp [37], [14], [25], [2], [35], [61]. Viêc̣ tính toán kích thước của nhóm trong maṇg phân cấp cũng ảnh hưởng tới đô ̣dài đường tìm kiếm [37]. (ii) Hướng nghiên cứu thứ hai: Cải thiêṇ điṇh tuyến DHTs: Điṇh tuyến bao gồm xây dưṇg cấu trúc bảng điṇh tuyến (Routing Structure) và kỹ thuật điṇh tuyến (Routing Scheme), đây là vấn đề then chốt ảnh hưởng tới hiêụ năng tổng thể maṇg P2P [75]. Hiêṇ nay với các cách -4- tiếp câṇ khác nhau nên DHTs có nhiều kỹ thuâṭ điṇh tuyến đươc̣ đề xuất như Kademlia, Chord, Pastry, Tapestry, CAN,...Tuy nhiên DHTs mới chỉ giải quyết đươc̣ vấn đề mở rôṇg quy mô và hiêụ quả tìm kiếm. Nhưng khi triển khai DHTs trong maṇg không đồng nhất và đô ̣ổn điṇh thấp thì DHTs có nhiều haṇ chế [43], [53], [63], [80], [36], [77], [27], [54]. 1.4 Hướng nghiên cứu của luận án 1.4.1 Nhận xét về công trình nghiên cứu của các tác giả khác Từ những khảo sát và phân tích các nghiên cứu về cải thiêṇ hiêụ năng maṇg ngang hàng đã được đề xuất trước đây, cho thấy các nghiên cứu mới chỉ quan tâm giải quyết được một trong hai vấn đề tính ổn định và tính không đồng nhất. Tuy nhiên cả hai vấn đề trên đều ảnh hưởng tới hiệu năng của hệ thống, để cải thiện hiệu năng của P2P cần phải cân bằng được hai yếu tố giảm chi phí để duy trì mạng và giảm trễ qua mạng chổng phủ. Xuất phát từ các khảo sát và phân tích ở trên luận án đề xuất cải thiện cấu trúc của mạng P2P và cải thiện thuật toán định tuyến, đưa trễ qua mạng IP vào xem xét trong quá trình tìm đường để cân bằng hai yếu tố phân tích ở trên. Trên cơ sở kết quả phân tích các hạn chế của các nghiên cứu liên quan, hướng nghiên cứu được đề xuất trong luận án này là: (1) Cải thiện hiệu năng thuâṭ toán định tuyến Chord trong quá trình tìm đường . (2) Đề xuất mô hình mạng Chord_SL phân cấp cải thiêṇ hiêụ năng định tuyến . (3) Đề xuất hàm giá bầu chọn siêu nút cải thiện hiệu năng trong mô hình phần cấp . -5- 1.5 Kết luận chương 1 Mô hiǹh P2P dưạ trên bảng băm phân tán DHT có khả năng mở rộng, khả năng chịu lỗi, dễ dàng triển khai, đươc̣ coi là giải pháp then chốt của maṇg ngang hàng thế hê ̣ thứ 3. Tuy nhiên DHTs mới chi ̉ giải quyết đươc̣ vấn đề quy mô và hiêụ quả tìm kiếm. Các khó khăn khi triển khai các thuâṭ toán DHTs trên maṇg P2P cũng đươc̣ phân tích trong chương môṭ. Muc̣ cuối của chương 1 đề câp̣ đến các tham số hiêụ năng của các DHTs và phân tích hướng nghiên cứu cải thiêṇ hiêụ năng của P2P. Kết quả nôị dung của chương môṭ đươc̣ thể hiêṇ trong bài báo khoa hoc̣ [V1]. CHƯƠNG 2: PHÂN TÍCH ĐÁNH GIÁ HIÊỤ NĂNG THUÂṬ TOÁN ĐIṆH TUYẾN DHTs Tóm tắt:Các thuâṭ toán điṇh tuyến DHTs đã đươc̣ các nghiên cứu chứng minh là có hiêụ năng tốt như: Cân bằng tải, tìm kiếm vị trí dữ liệu dễ dàng, khả năng chịu đưṇg lỗi, khả năng mở rộng. Chương hai phân tích hoaṭ đôṇg của ba thuâṭ toán điṇh tuyến DHTs: Kademlia, Tapestry và Chord. Việc mô phỏng được thực hiện bằng phần mềm mô phỏng OverSim. Kết quả của việc nghiên cứu đã chỉ ra những điểm mạnh và điểm yếu của các thuâṭ toán DHTs, là tiền đề cho việc cải thiện các thuâṭ toán điṇh tuyến DHTs trong nghiên cứu tiếp theo. 2.1 Bảng băm phân tán – DHT DHT sử duṇg hàm băm nhất quán SHA1 để cung cấp ánh xạ từ khóa/giá tri ̣ (key/value). Nhưng không giống như bảng băm thông thường, các giá trị trong một DHT được lưu trên các nút khác nhau trong mạng chứ không phải lưu trong một cấu trúc dữ liệu cục bộ. -6- Hình 2-1. Tim̀ kiếm và lưu trữ dữ liêụ trong DHT 2.2 Một số thuâṭ toán điṇh tuyến DHTs Ba thuâṭ toán điṇh tuyến DHTs được lựa chọn nghiên cứu: Kademlia, Tapestry và Chord. Cả ba thuâṭ toán điṇh tuyến này được thiết kế nhằm cải thiện hiệu năng tìm kiếm dữ liệu [74], [34], [47]. Tuy nhiên, những thuâṭ toán điṇh tuyến này lại sử dụng các cách tiếp cận khác nhau. Sở dĩ các thuâṭ toán điṇh tuyến DHTs này được luận án chọn để nghiên cứu bởi chúng có những đặc tính tiêu biểu để so sánh với các thuâṭ toán DHTs khác. 2.3 Phân tích, đánh giá hiêụ năng môṭ số thuâṭ toán điṇh tuyến DHTs 2.3.1 Lựa chọn công cụ mô phỏng mạng chồng phủ ngang hàng Qua nghiên cứu và phân tích và khảo sát, luận án đã chọn OverSim để thực hiện mô phỏng thử nghiệm cho các kịch bản trong luận án. 2.3.2 Mô phỏng đánh giá hiệu năng các thuâṭ toán định tuyến DHTs 2.3.2.1 Tham số hiệu năng Tham số hiêụ năng đươc̣ dùng để so sánh hiêụ năng của ba thuâṭ toán điṇh tuyến DHTs là: tỷ lê ̣ tìm kiếm thành công, tỷ lệ trễ dãn cách trung bình Tstretch và băng thông tiêu tốn, thời gian trễ, độ dài đường tìm kiếm (Hop count). -7- 2.3.2 Kết quả mô phỏng và thảo luâṇ Dựa trên kết quả mô phỏng, có thể thấy Tapestry hoạt động tốt khi số nút tăng, băng thông tiêu tốn tăng không đáng kể, tỷ lệ thành công được duy trì trên 99%, Tstretch hầu như không thay đổi. Đối với Kademlia, khi số nút tăng, tỷ lệ tìm kiếm thành công giảm xuống dưới 96%, Tstretch tăng, băng thông tiêu tốn giảm. Điều đó chỉ ra rằng, Kademlia hoạt động tốt với số nút ít hơn nhưng tiêu tốn băng thông nhiều hơn. Đối với Chord, khi số nút tăng, băng thông tiêu tốn tăng không đáng kể, tỷ lệ thành công được duy trì trên 96%. Tuy nhiên khi mạng có độ ổn định thấp có nghĩa là khi thời gian hoạt động trung bình của nút nhỏ thì tỷ lệ tìm kiếm thành công giảm đáng kể. Hơn nữa tỷ lệ trễ dãn cách trung bình giữa đường định tuyến lớp chồng phủ và đường định tuyến của lớp nền tảng quá lớn khoảng gấp ba lần. Điều này dẫn tới trễ tìm kiếm tăng và dẫn tới giảm chất lượng dịch vụ khi triển khai qua mạng P2P. Qua kết quả phân tích và mô phỏng để phù hợp với mục tiêu của luận án, thuật toán Chord sử dụng kỹ thuật tìm kiếm đệ quy đã được chọn vì các tham số hiệu năng của Chord khá ổn định khi triển khai trên mạng diện rộng, đặc biệt chi phí cho việc duy trì ổn định của mạng nhỏ hơn so với các thuật toán khác. Chord tìm kiếm đệ quy còn cải thiện 50% thời gian trễ trung bình so với Chord tìm kiếm lặp. Tuy nhiên Chord cũng còn một số vấn đề cần giải quyết như: đường định tuyến lớp chồng phủ quá xa so với đường định tuyến lớp nền tảng, hiệu năng thấp khi mạng không ổn định. 2.4 Kết luận chương 2 Chương hai phân tích hoaṭ đôṇg của ba thuâṭ toán DHTs, qua kết quả phân tićh lý thuyết và mô phỏng Chord phù hơp̣ với các ứng duṇg -8- quy mô lớn triển khai trên maṇg ngang hàng, với rất nhiều các đăc̣ tińh hấp dẫn như: Đơn giản, phân tán, tư ̣ tổ chức, khả dụng, mở rộng, cân bằng tải,Bên caṇh đó viêc̣ đánh giá hiệu năng của các thuâṭ toán định tuyến DHTs cũng đươc̣ thưc̣ hiêṇ qua phần mềm mô phỏng OverSim, qua kết quả mô phỏng cho thấy các tham số hiêụ năng của thuâṭ toán Chord duy trì ổn định khi maṇg có kích thước lớn và cấu trúc maṇg có “Churn rate” cao. Nội dung của chương là kết quả nghiên cứu được công bố taị [V2]. CHƯƠNG 3: CẢI THIÊṆ HIỆU NĂNG THUÂṬ TOÁN ĐIṆH TUYẾN CHORD Tóm tắt:Chord là môṭ thuâṭ toán điṇh tuyến DHT đươc̣ đánh giá đơn giản, dê ̃triển khai, hiêụ quả tìm kiếm phù hơp̣ với maṇg có kích thước lớn. Chương ba phân tích hoaṭ đôṇg của thuâṭ toán điṇh tuyến Chord, qua đó thấy đươc̣ ưu nhươc̣ điểm của thuâṭ toán; đồng thời phân tích các hướng nghiên cứu cải thiện Chord của các tác giả trước để đưa ra hướng nghiên cứu cải thiêṇ. Chord đaị diêṇ tiêu biểu cho thuâṭ toán điṇh tuyến DHT, đươc̣ phát triển từ lâu và rất thích hơp̣ để triển khai các dic̣h vu ̣trên diêṇ rôṇg. Nôị dung chương phân tích lý do choṇ thuâṭ toán Chord trong nghiên cứu; Các hướng cải thiêṇ thuâṭ toán Chord; Cải thiêṇ thuâṭ toán điṇh tuyến Chord và phân tích đánh giá mô phỏng so sánh với các nghiên cứu cải thiêṇ trước đây. -9- 3.1 Thuâṭ toán điṇh tuyến Chord Hình 3-1. Biểu diễn vòng Chord (M= 6) gồm 10 nút Thuâṭ toán Chord đã được IETF P2PSIP nhóm 79 lựa chọn như môṭ tiêu chuẩn của bô ̣giao thức P2PSIP [76], [77]. Như vậy, tất cả các ứng duṇg thoaị VoIP qua maṇg P2P choṇ Chord như môṭ giao thức nền tảng [2], [25], [54], [77], [75], v.v. Do đó, việc cải thiêṇ hiêụ năng thuâṭ toán điṇh tuyến Chord góp phần cải thiêṇ chất lươṇg dic̣h vu ̣thoaị qua maṇg ngang hàng (P2P VoIP). 3.2 Cải thiêṇ hiêụ năng thuâṭ toán Chord 3.2.1 Phân tích các điểm yếu của thuâṭ toán Chord Chord có rất nhiều ưu điểm, tuy nhiên khi triển khai trên maṇg có đô ̣ ổn điṇh thấp (các nút gia nhập/rời mạng liên tục trong thời gian ngắn) thì Chord đã bộc lộ những những vấn đề sau: 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; Chord thiếu các cơ chế nhớ đệm (Cache memory); Trễ định tuyến qua mạng chồng phủ lớn hơn rất nhiều so với trễ định tuyến qua lớp nền; dư thừa dữ liêụ trong bảng finger và không gian tìm kiếm chỉ giới haṇ trong môṭ nửa vòng tròn Chord. -10- 3.2.2 Hướng cải thiêṇ hiêụ năng của thuâṭ toán Chord Để cải thiêṇ hiêụ năng của Chord, chúng tôi đã đưa ra một phương pháp cải thiện thuật toán định tuyến Chord gốc qua việc làm bảng finger mở rộng phạm vi tìm kiếm mà không phải chiếm giữ thêm bất cứ không gian phụ nào. Hơn nữa, để cải thiện trễ và tỷ lệ trễ dãn cách trung bình , tham số điṇh tuyến kết hơp̣ cả khoảng cách định danh ID của Chord truyền thống và trê ̃ toàn tuyến RTT (Round Trip Time) qua lớp nền ( RTT được đo bằng lệnh ping). Chord cải thiêṇ trong luâṇ án đã cải thiêṇ so với các công trình nghiên cứu của các tác giả [60], [86], [11]. Cu ̣ thể bảng điṇh tuyến Chord luâṇ án đa ̃ mở rôṇg không gian định tuyến ra cả vòng tròn Chord, đô ̣dài trung bình đường định tuyến đaṭ đươc̣ giống như nghiên cứu [86], [11], giảm một nửa so với Chord truyền thống [60]. Thuâṭ toán Chord cải thiện đã giảm được 1 2 kích thước bảng định tuyến so với [86], [11]. Để thẩm định và kiểm tra thuâṭ toán Chord cải thiêṇ và đánh giá các đề xuất cải thiêṇ hiệu năng, luâṇ án sử dụng công cụ phân tích và mô phỏng OverSim [6]. Đây là công cụ mô phỏng mạng P2P được sử dụng phổ biến trong các nghiên cứu về P2P. Kết quả mô phỏng cho thấy rằng thuâṭ toán Chord cải thiện có hiệu năng tốt hơn so với các nghiên cứu trước đây. -11- 3.2.3 Cấu trúc mạng Chord cải thiêṇ trong luâṇ án Hình 3-5. Cấu trúc maṇg Chord cải thiêṇ Để giải quyết vấn đề “Topology mismatch” nghiên cứu trong luâṇ án cải tiến bảng định tuyến và cài đăṭ thêm 1 trường vào bảng định tuyến để lưu thời gian trễ qua mạng vật lý, ký hiệu là delay[i]. Để duy trì delay[i] là rất quan trọng, nó được dùng để giảm trễ tìm kiếm. Khi chạy thủ tục ổn điṇh stabilize(), bảng định tuyến của các nút liên quan sẽ được cập nhật và trường delay[i] cũng được cập nhật tại thời điểm này. Vì vậy hoạt động cập nhật delay[i] được cài đăṭ vào thuâṭ toán ổn điṇh stabilize(). Đồng thời việc loại bỏ thông tin dư thừa trong bảng finger được thực hiện mỗi khi cập nhật bảng finger (fix_fingers). Khi cập nhật bảng finger, trước tiên sẽ kiểm tra xem có mục nào dư thừa trong bảng finger không. Nếu có thông tin dư thừa sẽ thay đổi nội dung của con trỏ tại các thực thể trong bảng định tuyến đó bằng địa chỉ của các nút ở nửa còn lại của vòng Chord. Do đó không gian tìm kiếm sẽ mở rộng sang nửa vòng Chord còn lại. ID nút mới được tính theo tỷ số của A và B ( knA M  12 ) và B= (count +1). A cho biết khoảng cách giữa nút nguồn có định danh ID n và nút k có ID lớn nhất trong bảng điṇh tuyến. Và B phản ánh mức độ dư thừa con trỏ trong các mục của bảng finger. Biến đếm count cho biết số con trỏ dư thừa. -12- Bảng 3-4.So sánh hiêụ năng Chord cải thiêṇ Tham số hiêụ năng Chord gốc [60] Chord [86],[11] Chord cải thiêṇ [V3] Đô ̣dài đường tìm kiếm O(logN) O( 1 2 logN) N)log 2 1 O( 4 Kích thước bảng điṇh tuyến O(logN) O(logN2) O(logN) Số yêu cầu xử lý khi một nút gia nhập / rời mạng 2)(log NO 2)log2( NO 2)(log NO Chiến lược tim̀ kiếm của thuâṭ toán Chord cải thiêṇ: Quá triǹh tìm kiếm của thuâṭ toán Chord cải thiêṇ đươc̣ thưc̣ hiêṇ theo các bước như sau: Bước 1: Nút n yêu cầu tìm kiếm nguồn tài nguyên k nếu k nằm giữa n và Successor. Việc tìm kiếm kết thúc và n trả kết quả tìm kiếm về cho Successor. Nếu không chuyển đến bước 2. Bước 2: Dựa vào quy tắc a và b chọn chặng kế tiếp n'. Gửi truy vấn tìm kiếm đến nút n' và lặp lại bước 1. (a)Nếu ) 2 1 ,0(2mod)2( Nnk MM  MN 2 thì chọn nút n' min{delay[i]} (b) Nếu )1, 2 1 (2mod)2(  NNnk MM MN 2 thì choṇ chăṇg kế tiếp n'  )][(max nifingerdclockwise  3.2.4 Mô phỏng đánh giá hiêụ năng thuâṭ toán Chord cải thiêṇ Để kiểm tra đánh giá hiêụ năng thuâṭ toán Chord cải thiêṇ, luận án sử duṇg phần mềm mô phỏng OverSim. Các bước đánh giá nhằm so sánh giữa thuâṭ toán điṇh tuyến Chord gốc [60] với Chord cải thiêṇ. Các tham số hiệu năng được dùng để đánh giá: trễ tìm kiếm, Tstretch, độ -13- dài trung biǹh đường tìm kiếm (Hop count), băng thông tiêu tốn. Kích thước maṇg với số các nút 500 đến 10.000 nút. Kết quả mô phỏng cho thấy hiệu năng của Chord được cải thiện, tuy nhiên do phải tính toán trễ nên độ phức tạp tính toán và chi phí băng thông cho các lệnh ping cũng làm Chord cải tiến có băng thông tiêu tốn tăng so với các nghiên cứu trước. Hình 3-7. So sánh độ dài trung biǹh đường tìm kiếm Hình 3-6. So sánh thời gian trễ tìm kiếm trung bình và kích thước maṇg Hình 3-8. Tỷ lê ̣trê ̃dãn cách trung biǹh Tstretch và số nút Hình 3-9. Băng thông tiêu tốn và thời gian hoạt động trung bình của nút 3.4 Kết luâṇ chương 3 Nôị dung chương ba đưa ra một phương pháp cải thiêṇ hiêụ năng của Chord. Muc̣ tiêu của Chord cải thiêṇ tối ưu trê ̃tim̀ kiếm và đô ̣dài trung biǹh đường tìm kiếm qua maṇg chồng phủ ngang hàng. Chord cải thiêṇ đã cải tiến cấu trúc bảng finger và sửa đổi thuâṭ toán stabilize và fix_finger và cài đăṭ trong OverSim. Qua phân tićh và mô phỏng cho -14- thấy hiệu năng của thuâṭ toán Chord cải thiêṇ tốt hơn thuâṭ toán Chord gốc [60] và Chord của nghiên cứu [86], [11]. Cu ̣thể Chord cải thiêṇ đaṭ đươc̣ hiêụ năng tìm kiếm giống nghiên cứu [86], [11]. Kićh thước bảng điṇh tuyến bằng nghiên cứu [60] và giảm môṭ nửa so với nghiên cứu [86], [11]. Để giải quyết vấn đề “Topology mismatch”, luâṇ án đã đề xuất đưa trễ mạng nền vào xem xét. Trong quá trình định tuyến, thuâṭ toán Chord cải thiêṇ đã dung hòa được giữa khoảng cách ID lớp chồng phủ và trễ mạng nền IP. Hơn nữa, nó không chỉ có thể nhận được các nút tiếp theo gần đến đích, mà còn giải quyết vấn đề đồng nhất hiêụ năng giữa lớp ứng dụng với lớp nền . Kết quả nôị dung chương 3 đươc̣ thể hiêṇ trong bài báo khoa hoc̣ [V3]. CHƯƠNG IV: XÂY DƯṆG MAṆG CHORD_SL PHÂN CẤP CẢI THIÊṆ HIÊỤ NĂNG Tóm tắt : Cùng với sự phát triển nhanh chóng của số lượng người dùng Internet, việc cải thiêṇ hiêụ năng các dịch vụ triển khai trên nền Internet là rất cần thiết. Điển hình dịch vụ thoại IP truyền thống viêc̣ tìm kiếm người dùng dựa trên máy chủ trung tâm, vì vâỵ luôn phải đối mặt với nhiều vấn đề, ví dụ như: Tấn công từ chối dịch vụ, lỗi máy chủ trung tâm và nghẽn máy chủ,Gần đây, công nghệ maṇg P2P được sử dụng rộng rãi trong các ứng dụng chia sẻ file. Tuy nhiên, nó hỗ trợ khá chậm việc tìm kiếm và lựa chọn các file nguồn, không phù hợp cho hệ thống truyền thông thời gian thưc̣. Do đó, một maṇg Chord_SL phân cấp được đề xuất để đạt được yêu cầu tìm kiếm địa chỉ nhanh trong truyền thông thoại P2P. Maṇg Chord_SL được xây dựng dựa trên kiến trúc hai lớp và sử dụng thuật toán Chord cải thiện. Các kết quả phân tích chỉ ra rằng maṇg phân cấp -15- Chord_SL cải thiêṇ hiêụ năng hơn so với các mô hình dic̣h vu ̣triển khai trên maṇg Chord truyền thống và các cấu hình Chord phân cấp của nghiên cứu gần đây. 4.1 Giới thiệu chung Để cải thiện hiệu năng tìm kiếm và thích ứng với mạng không ổn định, các nút không đồng nhất, việc phát triển một maṇg Chord phân cấp P2P là cần thiết [99], [37], [14], [25], [2], [35]. Tuy nhiên các nghiên cứu đều triển khai trên mạng Chord truyền thống, độ phức tạp không gian lưu trữ của các siêu nút là O(𝑙𝑜𝑔2𝐾 + 𝑁/𝐾). Mô hiǹh maṇg phân cấp Chord_SL trong luận án được triển khai trên thuâṭ toán Chord cải thiện [V3]. Ngoài ra để giảm trễ, mô hình đã kết hợp với việc phân cấp dựa trên vị trí, kỹ thuật này đã cải thiện tỷ lê ̣trê ̃dãn cách qua maṇg P2P. 4.2 Mô hiǹh maṇg Chord_SL phân cấp cải thiện hiệu năng 4.2.1 Xây dựng mô hình Mô hình thiết kế dưạ trên 2 vòng tròn Chord cải thiêṇ, hê ̣thống quản lý N nút ký hiệu Chord_SL. Cấu trúc maṇg được chia làm hai lớp: Lớp liên miền (superlayer) quản lý K cụm nội miền và các lớp nội miền (local layer) có KN / . Các nút tham gia vào maṇg Chord của hai lớp và định tuyến theo nguyên tắc đã cải thiện trong nghiên cứu [V3]. -16- Hình 4-1. Mô hình maṇg phân cấp Chord_SL 4.2.2 Gán định danh cho các nút dựa vào địa chỉ IP Để giảm trễ, mô hình Chord_SL phân cấp định danh dựa trên tên miền của định danh ngoài. Một nút muốn lấy thông tin ở một miền khác, nó phải định tuyến truy vấn của mình tới SN trong cụm để từ đó có thể tìm được SN của miền đích. Định danh ID bao gồm 2 phần : tiền tố có chiều dài (D-d) bít và định danh hậu tố có độ dài d bít Hình 4-2. Gán định danh cho nút SN và nút ON [25] -17- 4.2.3 Xây dựng hàm giá bầu chọn siêu nút trong mạng Chord_SL 3 )( )( )( )( on(SN) on(p) .. t t SN p SN p B B P P G  (4.4) Trong đó 𝑡𝑜𝑛(𝑝), 𝑃(𝑝), 𝐵(𝑝) lần lươṭ là thời gian hoạt động trung bình của nút, khả năng xử lý CPU được tính bằng MIPS (Million Instruction Per Second), băng thông của nút của một nút p bất kỳ; 𝑡𝑜𝑛(𝑆𝑁), 𝑃(𝑆𝑁), 𝐵(𝑆𝑁) lần lươṭ là các giá tri ̣ yêu cầu tối thiểu của các tham số đối với môṭ nút SN, giá tri ̣ tham số đươc̣ choṇ tùy theo muc̣ tiêu của từng dic̣h vu ̣triển khai. 4.2.4 Chiến lược tìm kiếm trong mạng Chord_SL Bước 1: p chuyển tiếp truy vấn đến S (supernode) trong nhóm của mình. Do trong mô hình Chord_SL tất cả các nút nội miền đều chứa liên kết đến SN quản lý miền, nên viêc̣ kết nối đươc̣ hoàn thành trong môṭ bước nhảy, đô ̣dài đường tìm kiếm O(1). Bước 2: Sau khi tiếp nhận các truy vấn từ các nút nội miền, nút S (supernode) thực hiện tìm kiếm trong vòng Chord liên miền superlayer (C,E), miền đích là miền có ID tiền tố của SN gần với khóa nhất, độ dài đường tìm kiếm 𝑂(𝑙𝑜𝑔4𝐾). Ký hiêụ 𝐹𝑠𝑢𝑝(𝐶) là là điṇh danh của môṭ SN trong miền C, điṇh danh SN trong miền đích 𝐶𝑑𝑒𝑠𝑡 : 𝐶𝑑𝑒𝑠𝑡 = arg min 𝑑𝑐𝑙𝑜𝑐𝑘𝑤𝑖𝑠𝑒 (𝐹𝑠𝑢𝑝(𝐶), k ). Bước 3: Cuối cùng, bằng cách sử dụng tìm kiếm trong nội miền 𝐶𝑑𝑒𝑠𝑡, siêu nút có điṇh danh 𝐹𝑠𝑢𝑝(𝐶𝑑𝑒𝑠𝑡) chuyển truy vấn tìm kiếm tới nút chịu trách nhiệm với khóa k. 4.3 Phân tích, đánh giá hiêụ năng maṇg Chord_SL Để phân tích, đánh giá hiệu năng của maṇg chord_SL, luận án so -18- sánh mô hình đề xuất với các mô hình Chord không phân cấp Chord_flat , Chord phân cấp Chord_hiearchical. Các tham số hiệu năng được chọn để phân tích: Độ dài đường tìm kiếm, thời gian tìm kiếm trung bình, kích thước bảng định tuyến của nút và tổng chi phí duy trì định tuyến . Qua việc phân tích giải tích cho thấy Chord_SL phân cấp cải thiện hiệu năng hơn so với các mô hình phân cấp của nghiên cứu trước. Cụ thể được thể hiện qua kết quả dưới đây: Do mô hình phân cấp đề xuất trong luận án được triển khai trên thuật toán Chord cải thiện. Bảng định tuyến của các nút ON trong mạng Chord nội miền đều chứa con trỏ chỉ tới SN, vì vậy nút nội miền tìm kiếm SN có độ dài tìm kiếm )1(Ohns  . Độ dài đường tìm kiếm SN trong lớp liên miền là )(log 4KOhss  (theo bổ đề 3.1 ). Tỷ số giữa độ dài đường tìm kiếm nội miền qua mô hình Chord_SL và mô hình Chord không phân cấp: %50%100 )(log )(log 2 4 _  NO K N O h h flat SLChord -19- Nếu truyền thông nội miền thì độ dài đường tìm kiếm của mô hình Chord_SL cải thiện hơn so với mô hình Chord_flat : flatSLChord hh NO K N O   _ 24 )(log)(log  (4.11) Đối với các phiên tìm kiếm liên miền và K/N nhỏ (kích thước của nhóm nội miền nhỏ) thì mô hình Chord_SL cải thiện hơn so với các nghiên cứu trước: flatSLChord hhhNO OKOOKO K N OO   lhiearchica_2 244 )(log )1()(log)1()(log)(log)1(   (4.12) Mô hình Chord_SL và Chord_hiearchical đều chọn các nút có năng lực để làm siêu nút trong lớp liên miền, vì vậy ssT luôn nhỏ hơn ssT của mô hình mạng ngang hàng phẳng. Vì các nút cùng tên miền được sắp xếp trong cùng một lớp nội miền do siêu nút quản lý, nên nsT thường rất nhỏ. Do đó khi NK  thì thời gian tìm kiếm trung bình của Chord_SL được cải thiện đáng kể so với mô hình phẳng và mô hình phân cấp : flatSLChord ssnsss nsnsnsss TTT TNOTOTKO TOT K N OTOTKO    lhiearchica_ 22 44 )(log)1()(log )1()(log)1()(log    (4.13) Theo giải thuật đề xuất trong luận án phần 4.2.3, để lựa chọn được siêu nút phải tiêu tốn băng thông cho các bản tin trao đổi trong các trường hợp : a) Mỗi nút phát quảng bá các tham số của nó tới các nút hàng xóm; b) Các nút có năng lực thấp hơn ( băng thông, khả năng xử lý,) sẽ bầu chọn cho các nút có nă