Tóm tắt Luận án tiến sĩ Kỹ thuật: Nghiên cứu cải thiện hiệu năng định tuyến mạng ngang hàng P2P

Chia sẻ: Trần Văn Yan | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

30
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu chính mà luận án hướng tới là nghiên cứu tìm kiếm các giải pháp cải thiện hiệu năng hệ thống mạng ngang hàng. Để đạt được mục tiêu chính này, ii luận án đã nghiên cứu xây dựng cấu trúc mạng theo cấu trúc phân cấp và cải thiện hiệu năng thuật toán định tuyến trong hệ thống này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án tiến sĩ Kỹ thuật: Nghiên cứu cải thiện hiệu năng định tuyến mạng ngang hàng P2P

BỘ THÔNG TIN VÀ TRUYỀN THÔNG HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG VŨ THỊ THÚY HÀ NGHIÊN CỨU CẢI THIỆN HIỆU NĂNG ĐINH ̣ TUYẾN MẠNG NGANG HÀ NG P2P MÃ SỐ: 62.52.02.08 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT Hà Nội - 2017
Công trình hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: 1. PGS.TS. Lê Hữu Lập 2. PGS.TS. Lê Nhật Thăng Phản biện 1: ……………………………………………… Phản biện 2: ……………………………………………… Phản biện 3: ……………………………………………… Luận án được bảo vệ trước hội đồng chấm luận án cấp Học viện tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Vào hồi: giờ, ngày……..tháng…….năm 2017 Có thể tìm hiểu luận án tại: 1. Thư viện Quốc Gia Việt Nam 2. Thư viện Học viện Công nghệ Bưu chính Viễn thông
i MỞ ĐẦU Mạng ngang hàng P2P là một mạng hỗn hợp, được ta ̣o lâ ̣p trên diê ̣n rô ̣ng bao gồm cả những người dùng mạng Internet và các mạng máy tính chuyên nghiệp. Các mạng chồng phủ, dưới dạng các mạng P2P, đang trở nên rất phổ biến trong những năm gần đây, do các tính năng làm cho chúng phù hợp với việc phát triển hay triển khai các dịch vụ mới như truyền thông đa hướng, chia sẻ dữ liệu phạm vi rộng và phân phối nội dung như Kazaa, Napster, Bittorrent, Skype, Sopcast. Kiế n trúc của ma ̣ng viễn thông ngày nay đang chuyể n thành hướng dich ̣ vu ̣ thay vì xu hướng ma ̣ng trước đây, nhằm cho phép mở ha ̣ tầ ng viễn thông cho các nhà phát triể n ứng du ̣ng để ta ̣o ra các dich ̣ vu ̣ mới theo mô hin ̀ h của ma ̣ng Internet. Mạng ngang hàng với các ưu điểm như: Khả năng mở rộng, khả năng chịu đựng lỗi, dễ dàng triển khai,...Tuy nhiên chính cơ chế truyền thông ngang hàng và các yêu cầu cung cấp chất lươ ̣ng dịch vụ đã cho thấy một số thách thức mà ma ̣ng P2P cần phải giải quyế t. Các tính chất đă ̣c thù của ma ̣ng ngang hàng chiń h là nguyên nhân làm ảnh hưởng tới hiê ̣u năng của ma ̣ng như: Tiêu tố n băng thông cho quá trình duy trì cấ u hình ma ̣ng, tỷ số trễ dãn cách trung bình Tstretch tăng (tỷ số giữa đường đinh ̣ tuyế n lớp ma ̣ng chồ ng phủ và đường đinh ̣ tuyế n lớp nề n), tỷ lệ tổn thất gói tin cao. Mục tiêu chính mà luận án hướng tới là nghiên cứu tìm kiếm các giải pháp cải thiện hiệu năng hệ thống mạng ngang hàng. Để đạt được mục tiêu chính này,
ii luận án đã nghiên cứu xây dựng cấu trúc mạng theo cấu trúc phân cấp và cải thiện hiệu năng thuật toán định tuyến trong hệ thống này. Phạm vi nghiên cứu giới hạn với các hệ thống mạng ngang hàng có cấu trúc Chord-DHT. Tham số hiệu năng của hệ thống được đánh giá, khảo sát trong luận án là: Băng thông tiêu tốn, trễ (latency), tỷ lệ trễ dãn cách trung bình, tỷ lệ tổn thất gói tin, đô ̣ dài đường tim ̀ kiế m, kích thước bảng đinh ̣ tuyế n, tỷ lệ tìm kiếm thành công, chi phí bầu chọn siêu nút. Để đạt được mục tiêu nghiên cứu nêu trên, các nhiệm vụ nghiên cứu trong quá trình thực hiện luận án được xác định bao gồm: (1) 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. Phương pháp nghiên cứu được sử dụng trong luận án là nghiên cứu lý thuyết dựa trên mô hình giải tích với các công cụ toán học kết hợp với mô phỏng. Luận án bố cục thành bốn chương như sau: Chương 1: Tổ ng quan về ma ̣ng ngang hàng (P2P) Chương 2 : Đánh giá hiệu năng thuâ ̣t toán định tuyến DHTs Chương 3 : Cải thiê ̣n hiê ̣u năng thuâ ̣t toán đinh ̣ tuyế n Chord Chương 4 : Xây dựng ma ̣ng ngang hàng Chord_SL phân cấ p cải thiê ̣n hiê ̣u năng Kết luận và định hướng nghiên cứu tiếp theo. Hà nội, tháng 2 năm 2017
-1- CHƯƠNG 1: TỔNG QUAN VỀ MẠNG P2P Tóm tắt: Chương một tập trung nghiên cứu các đặc tính kỹ thuật của mạng ngang hàng cùng với các ứng dụng điển hình, các vấn đề ảnh hưởng tới hiê ̣u năng mạng ngang hàng; tiếp cận giải quyết vấn đề cải thiê ̣n hiê ̣u năng mạng ngang hàng và các điểm mấu chốt của thuật toán định tuyến dựa trên bảng băm phân tán và tìm kiế m tố i ưu. Đặc biệt, các giải pháp cải thiện hiệu năng thuật toán đi ̣nh tuyế n DHTs của các nghiên cứu trong nước và trên thế giới cũng được phân tích nhằm sáng tỏ cách thức tiếp cận mục tiêu của luận án. 1.1 Tổng quan về ma ̣ng ngang hà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). Overlay IP ̀ h ma ̣ng chồ ng phủ ngang hàng Hình 1-1. Mô hin
-2- 1.1.1 Kiến trúc ma ̣ng ngang hàng P2P Chia sẻ file, tin nhắ n tức thời, luồ ng Application Layer video, phân tán, tính toán,… ( Lớp ứng du ̣ng) Quản lý nút ma ̣ng phủ, quản lý Overlay Network Layer và tìm kiế m tài nguyên,… ( Lớp ma ̣ng chồ ng phủ) TCP, UDP/IP Underlying Network Layer ( Lớp ma ̣ng nề n ) Hình 1-2. Kiế n trúc phân lớp điể n hin ̀ h ma ̣ng ngang hàng P2P Dựa trên cấ u trúc và thuâ ̣t toán đinh ̣ tuyế n trong lớp ma ̣ng chồ ng phủ, kiế n trúc ma ̣ng chồ ng phủ P2P đươ ̣c chia thành mô hiǹ h tâ ̣p trung, phân tán và lai ghép [48], [63]. Mô hình phân tán đươ ̣c chia làm hai loa ̣i không cấu trúc, có cấ u trú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 ̣ng ngang hà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 hàng và các yêu cầu cung cấp chất lươ ̣ng dịch vụ, đã cho thấy một số thách thức mà ma ̣ng P2P cần phải vươ ̣t 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â ̣y ; Cân bằng tải. 1.2 Tham số hiêụ năng ma ̣ng ngang hàng - Đô ̣ dài đường tìm kiế m (Query path length ) - Tỷ lê ̣ tim ̀ kiế m thành công (Lookup Success Rate) - Đô ̣ dài đường tim ̀ kiế m trung bình (Mean Hop Count) - Trễ (Latency)
-3- - Tỷ lê ̣ trễ dãn cách trung biǹ h (Average stretch) Tstretch là tỷ số giữa trễ trung bình tìm kiếm qua mạng chồ ng phủ P2P và trễ trung bình tìm kiếm qua mạng nề n (IP). Tdelay overlay Tstretch  (1.3) Tdelay IP - Băng thông tiêu tố n (bandwidth consumption) 1.3 Các hướng tiế p câ ̣n nghiên cứu cải thiêṇ hiêụ năng ma ̣ng ngang hà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 Để có thể triể n khai các dich ̣ vu ̣ trên quy mô lớn hầu hết nghiên cứu đề u tâ ̣p trung vào ma ̣ng ngang hàng có cấu trúc. Qua khảo sát hướng nghiên cứu cải thiê ̣n hiê ̣u năng của tác giả trước chủ yếu tập trung vào hai hướng chính: (i) Hướng nghiên cứu thứ nhấ t: Tố i ưu cấ u trúc ma ̣ng chồ ng phủ: các tác giả trước đề u tâ ̣p trung giả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 ̣ng chồ ng phủ. Mô hiǹ h phân cấ p có hiê ̣u năng đinh ̣ tuyế n tố t hơn so với mô hiǹ h không phân cấ p [37], [14], [25], [2], [35], [61]. Viê ̣c tính toán kić h thước của nhóm trong ma ̣ng phân cấ p cũng ảnh hưởng tới đô ̣ dài đường tìm kiế m [37]. (ii) Hướng nghiên cứu thứ hai: Cải thiêṇ đinh ̣ tuyế n DHTs: Đinh ̣ tuyế n bao gồ m xây dựng cấ u trúc bảng đinh ̣ tuyế n (Routing Structure) và kỹ thuật đinh ̣ tuyế n (Routing Scheme), đây là vấ n đề then chố t ảnh hưởng tới hiê ̣u năng tổ ng thể ma ̣ng P2P [75]. Hiê ̣n nay với các cách
-4- tiế p câ ̣n khác nhau nên DHTs có nhiề u kỹ thuâ ̣t đinh ̣ tuyế n đươ ̣c đề xuấ t như Kademlia, Chord, Pastry, Tapestry, CAN,...Tuy nhiên DHTs mới chỉ giải quyế t đươ ̣c vấ n đề mở rô ̣ng quy mô và hiê ̣u quả tim ̀ kiế m. Nhưng khi triể n khai DHTs trong ma ̣ng không đồ ng nhấ t và đô ̣ ổ n đinh ̣ thấ p thì DHTs có nhiề u ha ̣n chế [43], [53], [63], [80], [36], [77], [27], [54]. 1.4 Hướng nghiên cứu của luận án 1.4.1 Nhận xét về công trình nghiên cứu của các tác giả khác Từ những khảo sát và phân tích các nghiên cứu về cải thiê ̣n hiê ̣u năng ma ̣ng ngang hà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â ̣t toá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 cải thiê ̣n hiê ̣u 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ô hiǹ h P2P dựa trên bảng băm phân tán DHT có khả năng mở rộng, khả năng chịu lỗi, dễ dàng triển khai, đươ ̣c coi là giải pháp then chố t của ma ̣ng ngang hàng thế hê ̣ thứ 3. Tuy nhiên DHTs mới chỉ giải quyế t đươ ̣c vấ n đề quy mô và hiê ̣u quả tim ̀ kiế m. Các khó khăn khi triể n khai các thuâ ̣t toán DHTs trên ma ̣ng P2P cũng đươ ̣c phân tić h trong chương mô ̣t. Mu ̣c cuố i của chương 1 đề câ ̣p đế n các tham số hiê ̣u năng của các DHTs và phân tić h hướng nghiên cứu cải thiê ̣n hiê ̣u năng của P2P. Kế t quả nô ̣i dung của chương mô ̣t đươ ̣c thể hiê ̣n trong bài báo khoa ho ̣c [V1]. CHƯƠNG 2: PHÂN TÍ CH ĐÁNH GIÁ HIỆU NĂNG THUẬT TOÁN ĐINḤ TUYẾN DHTs Tóm tắt:Các thuật toán đi ̣nh tuyế n DHTs đã được các nghiên cứu chứng minh là có hiê ̣u năng tố t như: Cân bằng tải, tìm kiế m vị trí dữ liệu dễ dàng, khả năng chịu đựng lỗi, khả năng mở rộng. Chương hai phân tích hoạt động của ba thuật toán đi ̣nh 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ật toán DHTs, là tiền đề cho việc cải thiện các thuật toán đi ̣nh tuyế n DHTs trong nghiên cứu tiế p theo. 2.1 Bảng băm phân tán – DHT DHT sử du ̣ng hàm băm nhấ t quán SHA1 để cung cấp ánh xạ từ khóa/giá 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- ̀ kiế m và lưu trữ dữ liêụ trong DHT Hình 2-1. Tim 2.2 Một số thuâ ̣t toán đinh ̣ tuyế n DHTs Ba thuâ ̣t toán đinh ̣ tuyế n DHTs được lựa chọn nghiên cứu: Kademlia, Tapestry và Chord. Cả ba thuâ ̣t toán đinh ̣ 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â ̣t toán đinh ̣ 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â ̣t toán đinh ̣ 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â ̣t toán DHTs khác. 2.3 Phân tích, đánh giá hiêụ năng mô ̣t số thuâ ̣t toán đinh ̣ 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 đánh giá hiệu năng các thuâ ̣t toán định tuyến DHTs 2.3.2.1 Tham số hiệu năng Tham số hiê ̣u năng đươ ̣c dùng để so sánh hiê ̣u năng của ba thuâ ̣t toán đinh ̣ tuyế n DHTs là: tỷ lê ̣ tìm kiế m thành công, tỷ lệ trễ dãn cách trung bình Tstretch và 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 quả mô phỏng và thảo luâ ̣n Dựa trên kết quả mô phỏng, có thể thấy Tapestry hoạt động tốt khi số nú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ố nú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ố nút ít hơn nhưng tiêu tốn băng thông nhiề u hơn. Đối với Chord, khi số nú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 nú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 tić h hoa ̣t đô ̣ng của ba thuâ ̣t toán DHTs, qua kế t quả phân tić h lý thuyết và mô phỏng Chord phù hơ ̣p với các ứng du ̣ng
-8- quy mô lớn triể n khai trên ma ̣ng ngang hàng, với rấ t nhiề u các đă ̣c tiń h hấ p dẫn như: Đơn giản, phân tán, tự tổ chức, khả dụng, mở rộng, cân bằ ng tải,…Bên ca ̣nh đó viê ̣c đánh giá hiệu năng của các thuâ ̣t toán định tuyến DHTs cũng đươ ̣c thực hiê ̣n qua phầ n mề m mô phỏng OverSim, qua kế t quả mô phỏng cho thấ y các tham số hiê ̣u năng của thuâ ̣t toán Chord duy trì ổn định khi ma ̣ng có kích thước lớn và cấ u trúc ma ̣ng có “Churn rate” cao. Nội dung của chương là kết quả nghiên cứu được công bố ta ̣i [V2]. CHƯƠNG 3: CẢI THIỆN HIỆU NĂNG THUẬT TOÁN ĐINH ̣ TUYẾN CHORD Tóm tắt:Chord là một thuật toán đi ̣nh tuyế n DHT được đánh giá đơn giản, dễ triển khai, hiê ̣u quả tìm kiế m phù hợp với mạng có kích thước lớn. Chương ba phân tích hoạt động của thuật toán đi ̣nh tuyế n Chord, qua đó thấ y được ưu nhược điể m của thuật toán; đồ ng thời phân tích các hướng nghiên cứu cải thiện Chord của các tác giả trước để đưa ra hướng nghiên cứu cải thiê ̣n. Chord đại diê ̣n tiêu biểu cho thuật toán đi ̣nh tuyế n DHT, được phát triể n từ lâu và rấ t thích hợp để triể n khai các di ̣ch vụ trên diê ̣n rộng. Nội dung chương phân tích lý do chọn thuật toán Chord trong nghiên cứu; Các hướng cải thiê ̣n thuật toán Chord; Cải thiê ̣n thuật toán đi ̣nh tuyế n Chord và phân tích đánh giá mô phỏng so sánh với các nghiên cứu cải thiê ̣n trước đây.
-9- 3.1 Thuâ ̣t toán đinh ̣ tuyế n Chord Hình 3-1. Biểu diễn vòng Chord (M= 6) gồm 10 nút Thuâ ̣t toán Chord đã được IETF P2PSIP nhóm 79 lựa chọn như mô ̣t tiêu chuẩn của bô ̣ giao thức P2PSIP [76], [77]. Như vậy, tấ t cả các ứng du ̣ng thoa ̣i VoIP qua ma ̣ng P2P cho ̣n Chord như mô ̣t giao thức nề n tảng [2], [25], [54], [77], [75], v.v. Do đó, việc cải thiê ̣n hiê ̣u năng thuâ ̣t toán đinh ̣ tuyế n Chord góp phầ n cải thiê ̣n chấ t lươ ̣ng dich ̣ vu ̣ thoa ̣i qua ma ̣ng ngang hàng (P2P VoIP). 3.2 Cải thiêṇ hiêụ năng thuâ ̣t toán Chord 3.2.1 Phân tích các điể m yế u của thuâ ̣t toán Chord Chord có rấ t nhiề u ưu điể m, tuy nhiên khi triể n khai trên ma ̣ng có đô ̣ ổ n đinh ̣ thấ p (cá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ê ̣u trong bảng finger và không gian tim ̀ kiế m chỉ giới ha ̣n trong mô ̣t nửa vòng tròn Chord.
-10- 3.2.2 Hướng cải thiêṇ hiêụ năng của thuâ ̣t toán Chord Để cải thiê ̣n hiê ̣u năng của Chord, chúng tôi đã đư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ố đinh ̣ tuyế n kế t hơ ̣p cả khoảng cá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 cải thiê ̣n trong luâ ̣n án đã cải thiê ̣n so với các công trình nghiên cứu của các tác giả [60], [86], [11]. Cu ̣ thể bảng đinh ̣ tuyế n Chord luâ ̣n án đã mở rô ̣ng không gian định tuyến ra cả vòng tròn Chord, đô ̣ dài trung bình đường định tuyến đa ̣t đươ ̣c giố ng như nghiên cứu [86], [11], giảm một nửa so với Chord 1 truyền thống [60]. Thuâ ̣t toán Chord cải thiện đã giảm được 2 kích thước bảng định tuyến so với [86], [11]. Để thẩ m định và kiểm tra thuâ ̣t toán Chord cải thiê ̣n và đánh giá các đề xuất cải thiê ̣n hiệu năng, luâ ̣n á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 các nghiên cứu về P2P. Kết quả mô phỏng cho thấy rằng thuâ ̣t toán Chord cải thiện có hiệu năng tốt hơn so với các nghiên cứu trước đây.
-11- 3.2.3 Cấu trúc mạng Chord cải thiêṇ trong luâ ̣n án Hình 3-5. Cấ u trúc ma ̣ng Chord cải thiêṇ Để giải quyế t vấ n đề “Topology mismatch” nghiên cứu trong luâ ̣n án cải tiến bảng định tuyến và cài đă ̣t 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 đinh ̣ 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 cài đă ̣t vào thuâ ̣t toán ổ n đinh ̣ 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 ( A  2 M  1  n  k ) 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 có ID lớn nhất trong bảng đinh ̣ 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 sánh hiêụ năng Chord cải thiêṇ Tham số hiê ̣u năng Chord gố c Chord [86],[11] Chord cải thiê ̣n [60] [V3] Đô ̣ dài đường tìm kiế m O(logN) 1 O( logN) 1 2 O( log 4 N) 2 Kích thước bảng đinh ̣ tuyế n O(logN) O(logN2) O(logN) Số yêu cầu xử lý khi một O(log N ) 2 O(2 log N ) 2 O(log N ) 2 nút gia nhập / rời mạng Chiến lược tim ̀ kiế m của thuâ ̣t toán Chord cải thiên: ̣ Quá triǹ h tìm kiế m của thuâ ̣t toán Chord cải thiê ̣n đươ ̣c thực hiê ̣n theo cá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. 1 (a)Nếu (k  n  2 M ) mod 2 M  (0, N ) N  2 M thì chọn nút n' min{delay[i]} 2 1 (b) Nếu (k  n  2 M ) mod 2 M  ( N , N  1) N  2 M thì cho ̣n chă ̣ng kế tiế p n' 2 max  d clockwise ( finger[i ]  n) 3.2.4 Mô phỏng đánh giá hiêụ năng thuâ ̣t toán Chord cải thiêṇ Để kiể m tra đánh giá hiê ̣u năng thuâ ̣t toán Chord cải thiê ̣n, luận án sử du ̣ng phầ n mề m mô phỏng OverSim. Các bước đánh giá nhằ m so sánh giữa thuâ ̣t toán đinh ̣ tuyế n Chord gố c [60] với Chord cải thiê ̣n. Các tham số hiệu năng được dùng để đánh giá: trễ tìm kiếm, Tstretch, độ
-13- dài trung bình đường tìm kiếm (Hop count), băng thông tiêu tốn. Kích thước ma ̣ng với số các nút 500 đến 10.000 nú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 sánh độ dài trung bin ̀ h đường tìm Hình 3-6. So sánh thời gian trễ tìm kiế m kiếm trung bình và kích thước ma ̣ng Hình 3-8. Tỷ lê ̣ trễ dãn cách trung bin ̀ h Tstretch Hình 3-9. Băng thông tiêu tốn và thời và số nút gian hoạt động trung bình của nút 3.4 Kế t luâ ̣n chương 3 Nô ̣i dung chương ba đưa ra một phương pháp cải thiê ̣n hiê ̣u năng của Chord. Mu ̣c tiêu của Chord cải thiê ̣n tố i ưu trễ tim ̀ kiế m và đô ̣ dài trung biǹ h đường tim ̀ kiế m qua ma ̣ng chồ ng phủ ngang hàng. Chord cải thiê ̣n đã cải tiến cấu trúc bảng finger và sửa đổ i thuâ ̣t toán stabilize và fix_finger và cài đă ̣t trong OverSim. Qua phân tić h và mô phỏng cho
-14- thấ y hiệu năng của thuâ ̣t toán Chord cải thiê ̣n tốt hơn thuâ ̣t toán Chord gốc [60] và Chord của nghiên cứu [86], [11]. Cu ̣ thể Chord cải thiê ̣n đa ̣t đươ ̣c hiê ̣u năng tim ̀ kiế m giố ng nghiên cứu [86], [11]. Kić h thước bảng đinh ̣ tuyế n bằ ng nghiên cứu [60] và giảm mô ̣t nửa so với nghiên cứu [86], [11]. Để giải quyế t vấ n đề “Topology mismatch”, luâ ̣n án đã đề xuất đưa trễ mạng nền vào xem xét. Trong quá trình định tuyến, thuâ ̣t toán Chord cải thiê ̣n đã dung hòa được giữa khoảng cách ID lớp chồ ng phủ 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ê ̣u năng giữa lớp ứng dụng với lớp nề n . Kế t quả nô ̣i dung chương 3 đươ ̣c thể hiê ̣n trong bài báo khoa ho ̣c [V3]. CHƯƠNG IV: XÂY DỰNG MẠNG CHORD_SL PHÂN CẤP CẢI THIỆN HIỆU 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 cải thiê ̣n hiê ̣u năng các dịch vụ triển khai trên nền Internet là rất cầ n thiế t. Điển hình dịch vụ thoại IP truyền thống viê ̣c tìm kiế m người dùng dựa trên máy chủ trung tâm, vì vậy 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̣ng 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̣ng Chord_SL phân cấ p được đề xuất để đạt được yêu cầ u tìm kiế m địa chỉ nhanh trong truyền thông thoại P2P. Mạng 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̣ng phân cấ p
-15- Chord_SL cải thiê ̣n hiê ̣u năng hơn so với các mô hình di ̣ch vụ triển khai trên mạng Chord truyề n thố ng và các cấ u hì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 ̣ng Chord phân cấp P2P là cần thiết [99], [37], [14], [25], [2], [35]. Tuy nhiên cá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ô hiǹ h ma ̣ng phân cấ p Chord_SL trong luận án được triển khai trên thuâ ̣t toá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 tỷ lê ̣ trễ dãn cách qua ma ̣ng P2P. ̀ h ma ̣ng Chord_SL phân cấ p cải thiện hiệu năng 4.2 Mô hin 4.2.1 Xây dựng mô hình Mô hình thiết kế dựa trên 2 vòng tròn Chord cải thiê ̣n, hê ̣ thố ng quản lý N nút ký hiệu Chord_SL. Cấ u trúc ma ̣ng đượ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ó N / K . Các nút tham gia vào ma ̣ng Chord củ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 ̣ng 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. Gán định danh cho nút SN và nút ON [25]