Luận án Nghiên cứu nâng cao hiệu năng hoạt động của mạng ngang hàng có cấu trúc

thời gian rời rạc. Mỗi bước hoạt động gồm ba kịch bản: nút tham gia và rời hệ thống, cập nhật bảng tìm đường, truy vấn dữ liệu và thực hiện cân bằng tải. Bằng cách sử dụng mô phỏng chúng tôi có thể theo dõi hiệu năng của hệ thống trong nhiều kịch bản khác nhau. Trong các thí nghiệm mô phỏng chúng tôi lựa chọn 10 thư mục và lưu trữ ở 10 nút ngẫu nhiên trong mạng gồm 4096 nút vật lý. Số nút được chọn để thử trong thuật toán Threshold là Log2(N), với N=4096. Nút vào và ra: Tại mỗi bước các nút ra/vào hệ thống theo phân bố xác suất Pareto [36]. Chúng tôi tạo ra một số phân bố xác suất để mô phỏng thời điểm ra/vào của các nút với thời gian sống trung bình của các nút trong mạng là 15 phút, 30 phút, 1 giờ, 2 giờ và 3 giờ. Mô phỏng thực hiện trong thời gian là 3 giờ. Chúng tôi ghi lại các thống kê trong nửa cuối của thời gian mô phỏng để tránh các kết quả mô phỏng không ổn định. Khả năng xử lý truy vấn của một nút là một số được sinh ngẫu nhiên có giá trị từ 1 đến 399,999. Khả năng xử lý truy vấn trung bình của một nút là khoảng 8000 truy vấn. Cập nhật bảng tìm đường: Mỗi nút mới tham gia vào hệ thống khởi tạo một bảng tìm đường rỗng. Các nút dựa theo cơ chế Chord để điền thông tin vào log(N) hàng của bảng tìm đường [21]. 57 Truy vấn dữ liệu: Các nút khởi tạo các câu truy vấn một cách ngẫu nhiên từ một tập khóa truy vấn. Khóa truy vấn được sinh ra theo theo phân bố Uniform hoặc phân bố Zipf phụ thuộc vào từng thí nghiệm cụ thể. Tập các khóa truy vấn được sinh theo phân bố xác suất Zipf có mức độ phổ biến khác nhau dựa trên một tham số gọi là thứ hạng. Xác suất để một khóa xuất hiện trong tập khóa truy vấn là 1 𝑟 với r là thứ hạng của khóa và là một số ngẫu nhiên giữa 1 và tổng số khóa truy vấn,  là một hằng số phản ảnh mức độ phổ biến của một khóa trong tập khóa,  càng lớn thì mức độ phổ biến của một khóa càng lớn và ngược lại. Mỗi nút sử dụng một finger (một hàng) thích hợp trong bảng tìm đường để chuyển câu truy vấn tới đích. Khi một nút chuyển tiếp câu truy vấn đến đích, hoặc thực hiện duy trì bảng tìm đường thì tải của nút đó tăng thêm một đơn vị. Nếu nút chuyển tiếp câu truy vấn có tải vượt quá khả năng xử lý của nó thì câu truy vấn đó được gọi là không thành công. Một câu truy vấn được gọi là thành công nếu nó đến được nút đích. Cân bằng tải: Định kỳ trong khoảng thời gian trung bình 30 giây, các nút kiểm tra ngưỡng tải và thực hiện cân bằng tải nếu tải của nút vượt quá ngưỡng cho phép. Chúng tôi đánh giá hiệu quả của phương pháp đề xuất thông qua các tham số mô tả trong các phần dưới đây. 2.4.2. Các kết quả mô phỏng 2.4.2.1. Ảnh hưởng của thời gian sống tới các thuật toán cân bằng tải. Thí nghiệm đầu tiên chúng tôi thực hiện để đánh giá khả năng thích ứng của các thuật toán cân bằng tải khi thời gian sống trung bình của một nút thay đổi. Các file theo dõi sự ra/vào của các nút trong mạng được tạo ra với thời gian sống trung bình của các nút là 15 phút, 30 phút, 1 giờ, 2 giờ và 4 giờ. 58 Mỗi lần chạy thí nghiệm, khả năng xử lý truy vấn của một nút trong mạng được giữ cố định, mỗi nút được khởi tạo trung bình 10 câu truy vấn trong một giây. Truy vấn được khởi tạo theo dạng Uniform và dạng Zipf với tham số =1.2. Kết quả của thí nghiệm được vẽ trong hình 2.10 cho thấy với số truy vấn trung bình đặt vào hệ thống 10 truy vấn/nút, thuật toán của chúng tôi có tỷ lệ thành công lớn hơn thuật toán Threshold khoảng 9% đối với truy vấn dạng Uniform và khoảng 14% đối với truy vấn dạng Zipf khi thời gian sống trung bình của các nút trong mạng thấp. Khi thời gian sống trung bình của các nút trong mạng thấp, các nút trong mạng vào ra của thường xuyên hơn, dẫn đến các nút trong mạng bị quá tải do phải chịu tải của nút hàng xóm rời mạng nhưng không tìm được nút nhẹ tải theo cơ chế tìm kiếm thông qua nút successor của Chord, do đó tỷ lệ tìm kiếm thành công một nút nhẹ tải giảm đi. Trong khi đó thuật toán đề xuất có cơ chế lưu trữ nút nhẹ tải ở thư mục cho nên việc tìm kiếm một nút nhẹ tải luôn được đảm bảo, chính cơ chế này giúp cho thuật toán cải tiến đạt được trạng thái cân bằng giữa các nút tốt hơn và hoạt động tốt hơn trong trường hợp này. Khi thời gian sống trung bình của các nút trong mạng lớn (4 giờ), mạng có độ ổn định cao, tỷ lệ truy vấn thành công của hai thuật toán tương đương nhau. 59 Hình 2.8. Thời gian sống trung bình của một nút thay đổi, các câu truy vấn thực hiện với phân bố Zipf và Uniform. 2.4.2.2. Ảnh hưởng số lượng câu truy vấn tới thuật toán cân bằng tải Thí nghiệm thứ hai thực hiện để đánh giá hiệu quả của các thuật toán khi số lượng câu truy vấn đặt vào hệ thống tăng lên. Trong đánh giá này chúng tôi giữ cố định khả năng xử lý truy vấn của các nút, thời gian sống trung bình của các nút trong mạng là 2 giờ, các câu truy vấn đặt vào hệ thống được phân bổ dưới dạng Uniform và dạng Zipf với  =1.2. Số lượng trung bình các câu truy vấn đặt vào một nút trong hệ thống tăng từ 0.01/giây truy vấn đến 100 truy vấn/giây. Kết quả thí nghiệm được vẽ trong hình 2.11 cho thấy thuật toán của chúng tôi có khả năng thích nghi tốt hơn thuật toán Threshold khoảng 6% đối với truy vấn dạng Uniform và khoảng 10% đối với truy vấn dạng Zipf. Khi số lượng câu truy vấn trung bình đặt vào mỗi nút thấp (0.01 truy vấn/giây, 0.1 truy vấn/giây), các nút trong mạng chưa bị quá tải do đó tỷ lệ thành công của cả hai thuật toán đều đạt rất cao (gần 100%). Khi số lượng các câu truy vấn trung bình đặt vào mỗi nút tăng cao (khoảng 100 truy vấn/giây), trong mạng tồn tại nhiều nút quả tải không có khả năng xử lý các câu truy vấn, do đó tỷ lệ 60 thành công của hai thuật toán đều thấp. Tuy nhiên, thuật toán chúng tôi đề xuất vẫn đạt tỷ lệ các câu truy vấn thành công cao hơn. Uniform: Số câu truy vấn đặt vào một nút Zipf: Số câu truy vấn đặt vào một nút Hình 2.9. Số câu truy vấn đặt vào một nút thay đổi, truy vấn được phân bố ở dạng Zipf và Uniform. 2.4.2.3. Ảnh hưởng câu truy vấn dạng Zipf tới thuật toán cân bằng tải Trong thí nghiệm tiếp theo chúng tôi đánh giá ảnh hưởng của câu truy vấn dạng Zipf tới các thuật toán cân bằng tải. Các tham số khả năng xử lý truy vấn của các nút trong mỗi lần chạy thí nghiệm được giữ không đổi, thời gian sống trung bình của một nút trong mạng là 2 giờ, số truy vấn trung bình đặt vào mỗi 61 nút là 10 truy vấn/giây. Khóa truy vấn phân bố cho các nút trong mạng theo dạng Zipf với tham số  thay đổi ( = 0.8, 1.2, 2.4 và 4.8). Kết quả thí nghiệm được vẽ trong hình 2.12 cho thấy thuật toán của chúng tôi có tỷ lệ thành công lớn hơn thuật toán Threshold khoảng 5%. Khi tham số  thấp ( = 0.8), các khóa có tính phổ biến tương đối đồng đều, tỷ lệ thành công của các thuật toán đạt tương đối cao. Khi tham số  cao ( = 4.8), trong mạng tồn tại nhiều khóa có tính phổ biến cao, câu truy vấn tập trung nhiều vào một số nút, các nút ở trong tình trạng quá tải, do đó tỷ lệ thành công của cả hai thuật toán tương đối thấp. Hình 2.10. Truy vấn đặt vào các nút ở dạng phân bố Zipf 2.4.2.4. Đánh giá chi phí của các thuật toán cân bằng tải Chi phí của các thuật toán cân bằng tải được đánh giá bằng số thông báo phát ra để tìm kiếm các nút nhẹ tải trong quá trình thực hiện cân bằng tải. Chi phí này được đánh giá thông qua các mô phỏng. Số thông báo này được đếm và ghi lại trong toàn bộ thời gian thực hiện mô phỏng, sau đó được tính trung bình trong một giây. Trong mô phỏng chúng tôi giữ cố định thời gian sống 62 của một nút là 30 phút, thay đổi số truy vấn đặt vào một nút lần lượt là 10, 20, 40, 60, 80, 100 truy vấn/giây. Khóa truy vấn đặt vào các nút được thực hiện dưới dạng Uniform và Zipf. Thời gian thực hiện thí nghiệm trong 1 giờ. Kết quả thí nghiệm được vẽ trong hình 2.13. Uniform: tốc độ gửi truy vấn thay đổi Zipf: tốc độ gửi truy vấn thay đổi Hình 2.11. Chi phí của các thuật toán cân bằng tải Kết quả thí nghiệm cho thấy: - Khi số lượng truy vấn đặt vào một nút ở tỷ lệ thấp, trong mạng tồn tại nhiều nút nhẹ tải và ít nút nặng tải. Với thuật toán đề xuất, số thông báo của nút nhẹ tải với thư mục nhiều, số thông báo truy vấn thư mục để tìm nút nhẹ 63 tải ít. Trong khi đó, với thuật toán Threshold số thông báo tìm kiếm nút nhẹ tải của thuật toán ít. Thuật toán đề xuất hoạt động không hiệu quả trong trường hợp này. - Khi số lượng truy vấn đặt vào một nút tăng dần, trong mạng tồn tại nhiều nút nặng tải và ít nút nhẹ tải, việc thực hiện cân bằng tải được thực hiện nhiều hơn. Với thuật toán đề xuất, số lượng thông báo của nút nhẹ tải cho thư mục giảm, số lượng thông báo truy vấn thư mục để tìm nút nhẹ tải tăng. Số lượng thông báo tìm kiếm nút nhẹ tải của thuật toán Threshold ban đầu tăng nhanh. Trong trường hợp này, thuật toán đề xuất hoạt động hiệu quả hơn thuật toán Threshold ban đầu rất nhiều. Khi số truy vấn đặt vào một nút đạt ngưỡng 100 truy vấn/giây, chi phí của thuật toán đề xuất chỉ bằng một nửa chi phí của thuật toán Threshold ban đầu. 2.5. Kết luận Chương 2 của luật án đã trình bày một số nghiên cứu liên quan về cân bằng tải trong mạng ngang hàng có cấu trúc và đề xuất một thuật toán để nâng cao khả năng cân bằng tải xử lý các câu truy vấn của các nút trong mạng, tăng tỷ lệ thành công của các câu truy vấn qua đó nâng cao hiệu năng hoạt động cho mạng ngàng có cấu trúc. Thuật toán cân bằng tải đề xuất có hai đóng góp chính: thứ nhất, thuật toán xem xét cả tải tìm kiếm các nút nhẹ tải trong quá trình thực hiện cân bằng tải. Thứ hai, thuật toán chỉ mất thời gian hằng số để tìm kiếm chính xác và nhanh chóng một nút nhẹ tải cho quá trình thực hiện cân bằng tải, do đó làm giảm số thông báo tìm kiếm nút nhẹ tải. Thuật toán đề xuất được đánh giá, so sánh với thuật toán Threshold nguyên thuỷ trên các tiêu chí tỷ lệ truy vấn thành công và chi phí tìm kiếm nút nhẹ tải. Trong các điều kiện thí nghiệm như nhau, thuật toán đề xuất có tỷ lệ 64 truy vấn thành công cao hơn so với thuật toán Threshold khoảng 12%. Đồng thời chi phí cho việc thực hiện cân bằng tải giảm xuống khi số lượng truy vấn đặt vào một nút tăng lên, có nghĩa là thuật toán đề xuất thích hợp cho hệ thống hoạt động ở ngưỡng tải nặng. Kết quả nghiên cứu và thuật toán chúng tôi đề xuất được công bố trong báo cáo khoa học tại hội thảo quốc gia về CNTT năm 2009 với tên gọi: “Nâng cao hiệu quả của thuật toán cân bằng tải theo ngưỡng trong mạng ngang hàng có cấu trúc”. 65 Chương 3. ĐIỀU KHIỂN TẮC NGHẼN TRONG MẠNG NGANG HÀNG CÓ CẤU TRÚC Các câu truy vấn trong mạng ngang hàng có cấu trúc được định tuyến qua nhiều nút khác nhau từ nút nguồn (nút phát câu truy vấn) đến nút đích (nút quản lý khóa truy vấn). Do tính không đồng nhất về khả năng định tuyến của các nút trong mạng cho nên xuất hiện tình trạng một số nút nhận được quá nhiều yêu cầu định tuyến truy vấn so với khả năng của nó. Điều này dẫn đến hiện tượng tắc nghẽn mạng tại một số nút, làm cho các câu truy vấn không đến được đích, gây ảnh hưởng đến hiệu năng hoạt động của hệ thống mạng. Để cải thiện hiệu năng hoạt động của mạng ngang hàng có cấu trúc, ngoài vấn đề cân bằng tải xử lý truy vấn đã giải quyết trong chương 2, cần phải giải quyết vấn đề tắc nghẽn tại các nút trong mạng khi thực hiện định tuyến truy vấn. Chương 3 trình bày về điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc và đề xuất thuật toán điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc. Thuật toán điều khiển tắc nghẽn góp phần nâng cao tỷ lệ thành công của các cấu truy vấn qua đó nâng cao hiệu năng hoạt động của mạng ngang hàng có cấu trúc. Nội dung của chương 3 gồm các vấn đề sau: - Các nghiên cứu liên quan về điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc. - Thuật toán điều khiển tắc nghẽn đề xuất. - Phân tích và đánh giá thuật toán. - Kết luận chương. 66 3.1. Đặt vấn đề Bảng băm phân tán (DHT) là kiến trúc hiệu quả để lưu trữ và tìm kiếm dữ liệu trong các mạng ngang hàng có cấu trúc. Thuật toán trong DHT xác định vị trí dữ liệu thông qua một định danh (ví dụ: khóa) trong không gian định danh. Mỗi nút chịu trách nhiệm quản lý một khoảng không gian liên tục các định danh. Thao tác cơ bản của DHT là tìm kiếm một định danh và trả lại địa chỉ (địa chỉ IP và địa chỉ cổng) của nút quản lý định danh đó. Mỗi nút trong hệ thống duy trì một bảng định tuyến để chuyển tiếp các truy vấn mà nó không quản lý. Các DHT, như P-Grid [45], Chord [21] hoặc Pastry [22] tạo các bảng định tuyến để chuyển tiếp gói tin đến nút đích. Trong những năm gần đây, DHT không chỉ được sử dụng cho các ứng dụng chia sẻ tệp tin mà còn được dùng trong xây dựng hệ thống truy vấn thông tin ngang hàng (P2P-IR - P2P Information Retrieval) [46]. Trong các hệ thống P2P-IR, DHT phải xử lý rất nhiều gói tin trong thời gian ngắn, làm tăng đáng kể tải hệ thống. Tối ưu hóa phương pháp định tuyến trong các mạng DHT là một yêu cầu quan trọng đối với các hệ thống P2P-IR. Hơn nữa, khi một nút nhận được một số truy vấn vượt quá khả năng định tuyến sẽ xảy ra sự cố tắc nghẽn trong mạng. Nếu không có cơ chế kiểm soát tắc nghẽn thích hợp, các câu truy vấn tiếp theo đến hoặc đi qua nút này sẽ không đến được đích. Do đó, làm giảm tỷ lệ thành công của các câu truy vấn và dẫn tới làm giảm hiệu năng hoạt động của hệ thống mạng ngang hàng có cấu trúc. Điều khiển tắc nghẽn trong DHT hoạt động ở lớp trên và độc lập với các cơ chế điều khiển tắc nghẽn của TCP. DHT thường sử dụng các thuật toán tham lam để định tuyến các gói tin trong mạng, trong đó một nút luôn lựa chọn nút láng giềng gần nhất để chuyển tiếp gói tin tới nút đích. Các mạng P2P là không đồng nhất, cho nên khả năng xử lý gói tin của các nút là không 67 giống nhau, độ ổn định của các nút không cao và các nút phải chia sẻ CPU và tài nguyên mạng cho các tiến trình khác đang chạy trong cùng thời điểm đó, v.v. Do đó, việc chọn các nút lân cận để chuyển tiếp các gói tin đến đích có thể không đáp ứng với sự thay đổi tải hệ thống trong mạng DHT. Các nghiên cứu điều khiển tắc nghẽn trong mạng P2P được thực hiện theo hai hướng: hạn chế tốc độ gửi truy vấn của các nút gửi hoặc thay đổi tuyến đường đi của thông điệp để tránh tắc nghẽn. Một số nghiên cứu tiêu biểu về điều khiển tắc nghẽn là CSCC [47] (Credit System Congestion Control), BPCC [47] (Back-Pressure Congestion Control) và CCLBR [48]. Các nghiên cứu này có đặc điểm chung là sử dụng bảng định tuyến cố định và kiểm soát tắc nghẽn bằng cách giảm tốc độ gửi gói tin hoặc sử dụng đường đi khác trong bảng định tuyến và không tính đến khả năng xử lý của các nút trong mạng. Do đó, chúng có thể làm giảm tốc độ truyền của mạng khi xảy ra tắc nghẽn. Chương này đề xuất một thuật toán điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc bằng cách thay đổi bảng định tuyến của một nút dựa trên trạng thái của các nút tiếp theo trong đường định tuyến. Khi một nút nhận được truy vấn, đầu tiên nó kiểm tra trạng thái tắc nghẽn của nó dựa trên khả năng định tuyến của nút và sau đó gửi thông tin phản hồi về trạng thái tắc nghẽn cho nút gửi nếu nó bị tắc nghẽn. Mỗi nút gửi sẽ theo dõi thông tin phản hồi tắc nghẽn được gửi từ các nút tắc nghẽn và thay thế nút tắc nghẽn bởi nút không tắc nghẽn trên đường đi của gói tin. Thuật toán đề xuất cho phép các nút nhanh chóng thích ứng với tuyến đường mới để tránh các phần còn lại của mạng bị quá tải. Do đó, phương pháp này có thể sử dụng hiệu quả băng thông mạng và tài nguyên của các nút không tắc nghẽn mà không ảnh hưởng đến hiệu năng định tuyến của toàn bộ mạng. 68 Thuật toán đề xuất có ba đóng góp chính. Thứ nhất, đề xuất phương pháp phát hiện tắc nghẽn dựa trên khả năng định tuyến của một nút trước khi một nút loại bỏ gói tin do tắc nghẽn xảy ra. Thứ hai, khi phát hiện một nút bị tắc nghẽn, nút định tuyến sẽ thay thế nút tắc nghẽn bằng nút không tắc nghẽn trong bảng định tuyến dựa trên các thông tin nhận được. Cuối cùng, phương pháp xử lý khi một nút hết tắc nghẽn đưa mạng trở lại trạng thái định tuyến ban đầu khi tỷ lệ truy vấn giảm và nút tắc nghẽn trở lại trạng thái không tắc nghẽn. Thuật toán đề xuất được đánh giá thông qua một số thí nghiệm mô phỏng hoạt động trên một hệ thống mạng gần với hệ thống mạng thực. Trong mô phỏng đánh giá thuật toán, khả năng định tuyến của các nút tham gia vào mạng là không giống nhau và thời điểm ra/vào của các nút được xác định theo phân bố xác suất Pareto. Kết quả mô phỏng cho thấy thuật toán điều khiển tắc nghẽn chúng tôi đề xuất đạt được tỷ lệ truy vấn thành công cao hơn so với thuật toán định tuyến trong giao thức Chord ban đầu khoản trên 40%. 3.2. Các nghiên cứu liên quan Các nghiên cứu liên quan đến điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc chủ yếu tập trung vào hai hướng: kiểm soát tốc độ và điều khiển bảng định tuyến. Trong hướng kiểm soát tốc độ, tốc độ gửi truy vấn bị giới hạn ở nút truy vấn khi một nút trong đường định tuyến bị quá tải. Các phương pháp tiêu biểu cho hướng này gồm: phương pháp CSCC [47], phương pháp BPCC [47] và phương pháp Marking [49]. Trong phương pháp CSCC, khi nút đích nhận được một gói tin, nó trả lời nút truy vấn bằng một gói tin ACK. Tại nút trung gian chuyển tiếp gói tin, một hàng đợi được duy trì để lưu trữ các truy vấn đến. Khi hàng đợi đạt đến ngưỡng, các truy vấn gửi đến tiếp theo sẽ bị loại bỏ mà không thông báo cho các nút gửi truy vấn. 69 Trong phương thức BPCC, mỗi nút duy trì một hàng đợi cho các truy vấn gửi đến. Khi nó nhận được một gói tin, nếu hàng đợi đạt đến giới hạn, nó sẽ gửi trạng thái hàng đợi của nó cho nút gửi. Nút gửi sẽ tự động điều chỉnh tốc độ gửi để tránh tắc nghẽn. Khi hàng đợi tại nút n đầy, nó sẽ tạm dừng đọc gói tin từ socket TCP của các kết nối đến thay vì từ chối gói tin. Sau đó, thuật toán điều khiển luồng trong TCP sẽ tự động làm chậm việc gửi truy vấn đến n. Trong phương pháp Marking, mỗi nút tổ chức một hàng đợi cho các truy vấn gửi đến và trả về trạng thái nghẽn bằng cách thêm một cờ h vào tiêu đề gói tin. Mục đích là để giữ các nút được chia sẻ tài nguyên với các nút khác đang bị nút cổ chai một cách công bằng mà không làm quá tải nút đang tắc nghẽn. Theo mặc định, cờ h bị tắt khi gói tin truy vấn được tạo. Cờ h tắt cho biết trạng thái mạng không tắc nghẽn và ngược lại. Mỗi nút thêm một giá trị x vào gói tin để biểu diễn tốc độ truy vấn hiện tại của nó. Mỗi nút lưu trữ số gói tin trung bình xavg, được tính toán trên các giá trị nhận được từ một số gói tin trước đó. Cờ h được kích hoạt hoặc vô hiệu hóa với xác suất q được xác định bằng cách xem xét tốc độ gói tin có đến nhanh hơn hay chậm hơn so với giá trị trung bình xavg và giá trị trung bình của kích thước hàng đợi. Khi cờ h được bật, nó sẽ không được tắt dọc theo đường đi đến đích cuối cùng. Nút đích sao chép giá trị của h vào gói ACK và trả nó về nút gửi truy vấn. Khi một nút nhận được một gói ACK với cờ h bị tắt, nghĩa là mạng không có tắc nghẽn, nó sẽ tăng tốc truy vấn. Nếu cờ h đang bật, nó sẽ giảm tốc độ truy vấn. Tốc độ truy vấn được tăng dần và giảm dần theo cấp số nhân. Do phương pháp Marking không loại bỏ các gói tin, có cơ chế đơn giản cho việc gửi trạng thái tắc nghẽn tới nút nguồn, cho nên thông lượng của phương pháp này tốt hơn và thời gian phản hồi truy vấn nhanh hơn so với hai phương thức CSCC và BPCC. 70 Theo hướng nghiên cứu định tuyến dựa trên trạng thái của mỗi nút trong bảng định tuyến, đường đi của gói tin được thay đổi để đi các nút ít tắc nghẽn hơn. Trong phương pháp Adaptive Routing [50], thay vì chọn nút gần nhất với khóa, nó chọn m nút gần khóa và theo dõi hiệu năng của các nút đó để xác định đường đi tốt nhất. Nút gửi truy vấn sử dụng cờ tắc nghẽn h để xác định khả năng sử dụng của mỗi tuyến đường định tuyến qua m nút gần khóa đã chọn. Từ giá trị h nhận được, mỗi nút tính toán xác suất (được gọi là op) quan sát h trên mỗi đường đi. Dựa trên giá trị xác suất này, mỗi nút sẽ di chuyển lưu lượng định tuyến thông qua các đường dẫn khác nhau để tăng thông lượng trên toàn mạng. Mỗi nút cập nhật giá trị op khi một truy vấn mới được thực hiện. Khi nút chuyển tiếp truy vấn đến các nút khác, các nút sẽ chia lưu lượng truy cập theo các hướng khác nhau dựa trên việc tính toán dung lượng của từng tuyến đường. Nhược điểm của phương pháp Adaptive Routing là khi muốn tăng số lượng đường định tuyến ta phải tăng kích thước của bảng định tuyến, điều này sẽ tiêu tốn tài nguyên của hệ thống. Ngoài ra, việc không sử dụng các phương thức định tuyến tham lam sẽ làm tăng số lượng gói tin được truyền qua mạng. Các cách tiếp cận khác bao gồm CCLBR [48], các phương pháp trong [49], [51] và [52]. CCLBR [48] đã đề xuất một phương pháp nhóm tài nguyên và một chiến lược định hướng lại (rewiring) để tự tổ chức và phân cụm các nút có tài nguyên giống nhau. Sau đó, một phương pháp học cộng tác (collaborative Q-learning) được đề xuất để cân bằng tải truy vấn giữa các nút trong nhóm để tránh các truy vấn được chuyển tiếp tới các nút bị tắc nghẽn trong mạng một cách thông minh. Nghiên cứu [49] có thể đạt được thông lượng mạng cao, nhưng mỗi nút phải chi phí tài nguyên của nó để quản lý sự gia tăng kích thước của bảng định tuyến. Nghiên cứu [51] đề xuất cơ chế định tuyến dựa trên DHT để cải thiện hiệu năng của lưới thông minh. Theo một 71 hướng khác, nghiên cứu [52] đề xuất một mô hình tối ưu hóa lưu lượng mạng P2P với khoảng cách tắc nghẽn và giới thiệu một sơ đồ tối ưu hóa dựa trên khoảng cách tắc nghẽn và bảng băm phân tán. Nghiên cứu [65] đề xuất cơ chế bảng định tuyến động (ERT - Elastic Routing Table) để tạo ra các đường định tuyến khác nhau đến đích tránh tắc nghẽn. Bảng định tuyến có cấu trúc không cố định như bảng định tuyến hiện tại, số lượng các hàng trong bảng định tuyến phụ thuộc vào các đường liên kết vào và ra của mỗi nút. Số hàng trong bảng định tuyến có thể được điều chỉnh một cách tự động dựa trên việc quan sát lưu lượng của một nút để định hướng luồng truy vấn đế các nút có khả năng xử lý tốt. Phương pháp MPPP [66] (Multi-Path with Probable Performance) phân bố tải định tuyến theo nhiều đường khác nhau đến đích để tận dụng khả năng nhàn rỗi của các nút và cải thiện mức độ tắc nghẽn trong mạng. Trong MPPP, mỗi đối tượng dữ liệu được gán nhiều định danh và đối tượng có thể được tìm kiếm bằng nhiều đường định tuyến khác nhau. Mỗi đường tìm kiếm được khởi tạo từ một khóa truy vấn (định danh) của đối tượng. Nghiên cứu [67] đề xuất mô hình tối ưu hóa lưu lượng P2P với khoảng cách tắc nghẽn cho phép các ứng dụng P2P sử dụng hợp lý băng thông mạng. Mô hình tối ưu hóa lưu lượng P2P bắt đầu từ mục tiêu của ISP (Internet Service Provider) và người dùng mạng P2P. Trạng thái tắc nghẽn của các đường liên kết được chuyển đổi sang giá trị khoảng cách truyền thông để đồng nhất việc tối ưu hóa. Có nhiều bộ điều khiển luồng và bộ thu thập thông tin phục được cài đặt trong mô hình tối ưu hóa lưu lượng P2P. Để tổng kết và đánh giá các thuật toán điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc đã đề xuất, chúng tôi xây dựng một bảng với một số 72 tiêu chí để so sánh một cách định tính chi phí cho các thuật toán. Các tiêu chí đánh giá của chúng tôi bao gồm: - Thông lượng: là lượng thông tin hữu ích được truyền đi trên mạng trong một đơn vị thời gian. Trong các thuật toán điều khiển tắc nghẽn theo hướng điều khiển tốc độ, khi có tắc nghẽn xảy ra gói tin tiếp theo sẽ bị xóa hoặc nút gửi hạn chế tốc độ gửi, do đó thông lượng sẽ bị giảm. Trong thuật toán thay đổi đường định tuyến, khi có tắc nghẽn xảy ra, gói tin tiếp theo sẽ được chuyển đi đến đích theo con đường khác mà không bị xóa bỏ hoặc hạn chế gửi. Do đó, nó không làm giảm thông lượng mạng. - Chi phí duy trì bảng định tuyến: là chi phí để quản lý, cập nhật bảng định tuyến. Trong thuật toán điều khiển tắc nghẽn theo hướng điều khiển tốc độ, mỗi nút duy trì cố định một đường định tuyến. Trong thuật toán thay đổi đường định tuyến, mỗi nút duy trì cố định m đường định tuyến. Do đó, chi phí duy trì bảng định tuyến của các thuật toán điều khiển tắc nghẽn theo hướng điều khiển tốc độ là thấp nhất và của thuật toán thay đổi đường định tuyến là tương đối cao. - Tận dụng nút không tắc nghẽn: Trong thuật toán điều khiển tắc nghẽn theo hướng điều khiển tốc độ, tuyến đường đi của gói tin là cố định, khi tắc nghẽn xảy ra nút gửi chỉ hạn chế tốc độ gửi hoặc nút nhận loại bỏ gói tin tiếp theo mà không chọn đường đi khác, mặc dù trong mạng còn rất nhiều nút có khả năng định tuyến. Trong phương pháp thay đổi đường định tuyến gói tin chỉ đi theo một số tuyến đường được cài đặt sẵn, do đó nó cũng không tận dụng được khả năng định tuyến của các nút trong mạng. Phần tiếp theo của chương này trình bày về thuật toán điều khiển tắc nghẽn