Luận văn Điều khiển tắc nghẽn trên mạng ngang hàng có cấu trúc

I ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRẦN TRỌNG TẤN ĐIỀU KHIỂN TẮC NGHẼN TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC LUẬN VĂN THẠC SĨ HÀ NỘI - 2011 II ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRẦN TRỌNG TẤN ĐIỀU KHIỂN TẮC NGHẼN TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC Ngành: Công nghệ Thông tin Chuyên ngành: Truyền dữ liệu và mạng máy tính Mã số: 60 48 15 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Hoài Sơn HÀ NỘI - 2011 III Mục lục Mở đầu ..................................................................................................................... 1 Chương 1. Tổng quan .............................................................................................. 3 1.1. Mạng ngang hàng ......................................................................................... 3 1.1.1. Mức độ phân tán .................................................................................... 3 1.1.2. Cấu trúc mạng ........................................................................................ 5 1.2. Mạng ngang hàng có cấu trúc ....................................................................... 6 1.2.1. Đặc điểm của DHT ................................................................................ 7 1.2.2. Cấu trúc hệ thống ................................................................................... 7 1.3. Mạng Chord .................................................................................................. 9 1.3.1. Mô hình của Chord .............................................................................. 10 1.3.2. Tìm kiếm trong mạng Chord ............................................................... 11 1.3.3. Quá trình tham gia và ổn định mạng ................................................... 14 Chương 2. Vấn đề điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc ...... 16 2.1. Tắc nghẽn và tầm quan trọng của việc điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc ...................................................................................... 16 2.2. Phân tích quá trình sụp đổ do tắc nghẽn trong mạng ngang hàng có cấu trúc ............................................................................................................................ 17 2.2.1. Khái quát .............................................................................................. 17 2.2.2. Định nghĩa ............................................................................................ 17 2.2.3. Các mô hình ......................................................................................... 19 2.2.4. Tổng tải đến O ..................................................................................... 19 2.2.5. Ví dụ với một triệu nút ........................................................................ 22 2.2.6. Phân tích các trạng thái tiệm cận của A. .............................................. 22 2.2.7. Kết luận ................................................................................................ 25 Chương 3. Các nghiên cứu về điều khiển tắc nghẽn trên DHT ............................. 26 3.1. Phương pháp CSCC .................................................................................... 26 3.2. Phương pháp BPCC .................................................................................... 27 3.3. Phương pháp Marking ................................................................................ 28 3.4. Phương pháp định tuyến thích nghi ............................................................ 31 Chương 4. Điều khiển tắc nghẽn sử dụng phương pháp thay đổi bảng định tuyến ................................................................................................................................ 34 4.1. Đề xuất phương pháp .................................................................................. 34 4.2. Nội dung chi tiết ......................................................................................... 34 4.2.1. Phát hiện tắc nghẽn. ............................................................................. 34 4.2.2. Xử lý trong trường hợp có tắc nghẽn ................................................... 35 4.2.3. Xử lý khi hết tắc nghẽn ........................................................................ 36 4.3. Ví dụ minh họa ........................................................................................... 37 4.4. Nhận xét về phương pháp ........................................................................... 39 5. Mô phỏng và kết quả ......................................................................................... 41 5.1. Mô phỏng .................................................................................................... 41 5.1.1. Chương trình mô phỏng ....................................................................... 41 IV 5.1.2. Các thay đổi đã áp dụng ....................................................................... 44 5.2. Kết quả ........................................................................................................ 45 5.2.1. So sánh với mô hình Chord chuẩn ....................................................... 45 5.2.2. Đánh giá hiệu năng khi tiến hành tùy chỉnh các tham số và cải tiến phương pháp .................................................................................................. 47 6. Kết luận và hướng phát triển ............................................................................. 50 V Danh mục hình ảnh Hình 1: Mạng ngang hàng phân tán hoàn toàn ........................................................ 4 Hình 2: Mạng ngang hàng phân tán một phần ......................................................... 4 Hình 3: Mạng ngang hàng lai .................................................................................. 5 Hình 4: Bảng băm phân tán – DHT ......................................................................... 7 Hình 5: Mô hình vòng Chord với khóa có chiều dài 6 bit ..................................... 11 Hình 6: Quá trình tìm kiếm đơn giản trên Chord .................................................. 12 Hình 7: Bảng finger của nút 8 ................................................................................ 13 Hình 8: Giả mã của phương pháp tìm kiếm cải tiến .............................................. 13 Hình 9: Quá trình tìm kiếm khóa 54 trên nút 8 ..................................................... 14 Hình 10: (a) tải đến các nút tạo bởi P0, (b) Tải tới và rời khỏi nút ................... 18 Hình 11: Thông lượng đạt được so sánh với tốc độ truy vấn cho hệ thống DHT với một triệu nút trong hai trường hợp tắc nghẽn M1 và M2. Mạng DHT sụp đổ khi tải tới đạt đến giá trị xopt ......................................................................................... 22 Hình 12: Phương pháp CSCC ................................................................................ 26 Hình 13: Phương pháp BPCC ................................................................................ 28 Hình 14: Mạng DHT với 8 nút. ............................................................................. 31 Hình 15: Truy vấn thông thường trên mạng Chord (m=8). ................................... 37 Hình 16: Bảng định tuyến ban đầu của nút P8 ....................................................... 38 Hình 17: Bảng định tuyến của nút P8 khi xảy ra tình trạng tắc nghẽn trên nút P42. ................................................................................................................................ 38 Hình 18: Truy vấn được thay đổi đường đi khi áp dụng giải pháp chống tắc nghẽn ................................................................................................................................ 38 Hình 19: Mô hình mạng mô phỏng ........................................................................ 41 Hình 20: Mô hình lớp Node ................................................................................... 42 Hình 21: Biểu đồ số lượng gói tin bị loại bỏ khi áp dụng và không áp dụng việc điều khiển tắc nghẽn .............................................................................................. 45 Hình 22: Biểu đồ thể hiện số gói tin trung bình phải sử dụng với mỗi truy vấn thành công .............................................................................................................. 46 Hình 23: Ảnh hưởng của việc thay đổi giá trị xác định mức độ tắc nghẽn mềm của nút........................................................................................................................... 47 Hình 24: Ảnh hưởng của số lượng nút được khôi phục bảng định tuyến lên hiệu năng của hệ thống .................................................................................................. 48 Hình 25: Hiệu năng của hệ thống thay đổi khi cải tiến phương pháp điều khiển tắc nghẽn. ..................................................................................................................... 48 1 Mở đầu Ngày nay với mức độ phổ biến của máy tính cá nhân và mạng Internet, mạng ngang hàng với nhiều đặc tính phù hợp cho các hệ thống phân tán, ngày càng thu hút được nhiều chú ý của người sử dụng và giới nghiên cứu phát triển ứng dụng. Cùng với xu thế đó mô hình mạng ngang hàng có cấu trúc cũng dành được nhiều sự quan tâm và phát triển do đặc điểm là mạng ngang hàng thuần túy, không yêu cầu có sự tham gia của các máy chủ trung tâm. Đặc điểm này giúp mạng ngang hàng cấu trúc có khả năng mở rộng tốt hơn, loại bỏ các single- point-of-failure, tuy nhiên cũng tạo ra nhiều các vấn đề kỹ thuật cần phải giải quyết. Rất nhiều ứng dụng phức tạp đã được phát triển trên nền tảng mạng ngang hàng có cấu trúc như các hệ thống truy vấn dữ liệu, hay hệ thống quản trị cơ sở dữ liệu… Các ứng dụng phức tạp này với số lượng thông điệp được chuyển tải trong mạng là vô cùng lớn sẽ gây khó khăn cho việc duy trì hệ thống hoạt động một cách hiệu quả. Thêm nữa mạng ngang hàng nói chung và mạng ngang hàng có cấu trúc nói riêng thường xuyên xuất hiện việc một số tài nguyên được truy vấn nhiều lần trong một khoảng thời gian nhất định, do đó có thể gây tăng vọt số lượng truy vấn trên một số nút trên mạng. Khi trong mạng tồn tại nút có số lượng truy vấn tới cao hơn khả năng xử lý của nó sẽ gây ra tình trạng tắc nghẽn cục bộ trên nút. Nếu như không có những cơ chế điều khiển tắc nghẽn hợp lý sẽ dẫn đến việc tắc nghẽn lan rộng trên mạng và có thể gây sụp đổ mạng. Điều này có thể gây cản trở đến việc sử dụng mạng ngang hàng có cấu trúc trong các ứng dụng ở môi trường thực tế nơi các nút tham gia mạng có khả năng xử lý và đường truyền rất đa dạng. Do đó việc tạo ra một cơ chế điều khiển tắc nghẽn hiệu quả là nhu cầu thiết yếu với bất kỳ hệ thống mạng ngang hàng có cấu trúc nào. Luận văn này thông qua việc tìm hiểu về mạng ngang hàng có cấu trúc (cụ thể là mô hình mạng Chord) và phân tích quá trình sụp đổ do tắc nghẽn sẽ nêu bật tầm quan trọng của việc điều khiển tắc nghẽn. Khóa luận còn tìm hiểu các nghiên cứu có liên quan trước đây, phân tích ưu nhược điểm của chúng nhằm đề xuất một phương pháp điều khiển tắc nghẽn, bổ sung cho các phương pháp đã có. Phương pháp này sử dụng việc thay đổi bảng định tuyến của các nút trong mạng, nhằm chuyển hướng các thông điệp tránh khỏi những nút đang tắc nghẽn và đi qua những nút còn khả năng phục vụ. Đồng thời giảm thiểu số lượng thông tin và thông điệp phát sinh từ quá trình điều khiển tắc nghẽn này, 2 cũng như không tạo lên các thay đổi quá lớn trong việc tổ chức và định tuyến so với mô hình mạng ban đầu. Giải pháp đã được thử nghiệm trên chương trình mô phỏng mạng Chord. Kết quả thu được cho thấy, việc sử dụng giải pháp đã xử lý được vấn đề tắc nghẽn cục bộ qua đó nâng cao được thông lượng đạt được trên toàn hệ thống. Khóa luận có cấu trúc như sau:  Chương 1: Giới thiệu tổng quan về mạng ngang hàng, mạng ngang hàng có cấu trúc cụ thể là mô hình Chord.  Chương 2: Trình bày vấn đề điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc và tầm quan trọng của nó. Phân tích quá trình sụp đổ của mạng do tắc nghẽn.  Chương 3: Trình bày các nghiên cứu liên quan. Phân tích ưu nhược điểm của các phương pháp đã đưa ra.  Chương 4: Đề xuất và phân tích giải pháp điều khiển tắc nghẽn dựa trên việc thay đổi bảng định tuyến.  Chương 5: Xây dựng chương trình mô phỏng và các kết quả đã đạt được.  Chương 6: Kết luận và hướng phát triển nhằm giải quyết những tồn đọng và cải tiến giải pháp đã đưa ra. 3 Chương 1. Tổng quan 1.1. Mạng ngang hàng Mạng ngang hàng được định nghĩa như sau: một cấu trúc mạng phân tán, nếu như các thành phần tham gia chia sẻ tài nguyên của chúng (như khả năng tính toán của vi xử lý, dung lượng lưu trữ, đường truyền…). Các tài nguyên được chia sẻ này dùng để cung cấp các dịch vụ và nội dung. Chúng được truy cập một các trực tiếp bởi các nút khác, không thông qua các nút trung gian. Các thành phần tham gia trong mạng vừa đóng vai trò cung cấp tài nguyên và yêu cầu tài nguyên.[6] Ta có thể phân biệt mô hình mạng ngang hàng với mô hình khách chủ thông qua vai trò của các thành phần tham gia trong mạng. Mỗi thành phần trong mạng ngang hàng có thể được gọi là Servent được tạo nên từ hai phần: Serv trong từ server (máy chủ) và ent trong từ client (máy khách), nhằm thể hiện khả năng của một nút trong mạng ngang hàng có thể vừa đóng cả hai vai trò máy chủ và máy khách trong cùng một thời điểm. Điều này hoàn toàn khác biệt với môi hình khách chủ khi nút tham gia chỉ có thể đóng một trong hai vai trò, hoặc máy khách, hoặc máy chủ tại một thời điểm. Hoạt động của bất cứ hệ thống mạng ngang hàng nào cũng phụ thuộc vào mạng bao gồm các nút và kết nối giữa chúng. Mạng này được tạo ở tầng trên và độc lập với mạng vật lý phía dưới (thường là mạng IP), nên được gọi là “mạng phủ”. Mô hình, cấu trúc, mức độ tập trung của mạng phủ, và cách thức định tuyến, định vị trong mạng ảnh hưởng lớn đến hoạt động của hệ thống, do chúng sẽ quyết định tới khả năng tự bảo trì, tự ổn định mạng, chống lỗi, hiệu năng, khả năng mở rộng và mức độ bảo mật. Mạng phủ có thể phân biệt dựa vào mức độ phân tán và cấu trúc [1] 1.1.1. Mức độ phân tán Mặc dù thiết kế mong muốn của mạng phủ là hoàn toàn phân tán, tuy nhiên trong thực tế có thể không đúng như vậy. Dưới đây liệt kê các mô hình dựa trên mức độ phân tán của chúng Mô hình phân tán hoàn toàn: Tất cả các nút trong mạng thực hiện các vai trò như nhau. Vừa đóng vai trò là máy chủ, vừa là máy khách. Do đó không cần phải có bất kỳ thành phần nào đóng vai trò là trung tâm điều phối. 4 Hình 1: Mạng ngang hàng phân tán hoàn toàn Mô hình phân tán một phần: Về cơ bản mô hình này tương tự như mô hình phân tán hoàn toàn. Tuy nhiên có một số nút đóng vai trò quan trong hơn các nút khác, trở thành các điểm điều phối cho một số các nút khác. Các nút này được gọi là siêu nút (supernode) và chúng có thể đảm nhận các vai trò khác nhau tùy thuộc vào từng thiết kế. Hình 2: Mạng ngang hàng phân tán một phần Có một điểm quan trọng cần lưu ý là hệ thống sẽ không lệ thuộc vào một nút nào, dù nút đó có là supernode, do các nút này được gán động và nếu có lỗi sẽ được thay thế bằng nút khác. 5 Mô hình phân tán lai: Trong những hệ thống này, tồn tại một máy chủ trung tâm đóng vai trò duy trì thông tin về các nút và tài nguyên trên các nút. Hình 3: Mạng ngang hàng lai Mặc dù việc trao đổi tài nguyên có thể thực hiện trực tiếp giữa các nút, nhưng máy chủ trung tâm sẽ đóng vai trò tổng hợp và tìm kiếm tài nguyên trên nút. Về cơ bản mô hình này sẽ xuất hiện single point of failure chính là máy chủ trung tâm. Mô hình này sẽ khó mở rộng, và tạo các nguy hiểm tiềm tàng cho hệ thống khi máy chủ trung tâm có sự cố hoặc bị tấn công. 1.1.2. Cấu trúc mạng Cấu trúc ở đây mang nghĩa xác định rõ việc hình thành mạng phủ, cũng như việc nút và các tài nguyên được đưa vào mạng có theo một quy luật nhất định nào đó không. Nhờ đó ta phân loại ra như sau Không có cấu trúc: Vị trí của nội dung hoàn toàn không liên quan tới mô hình của mạng phủ. Trong mạng không có cấu trúc nội dung cần phải được định vị. Phương thức tìm kiếm rất đa dạng từ việc sử dụng các phương pháp bruteforce, đẩy truy vấn ra tất cả các nút cho tới khi có được kết quả, cho đến sử dụng các thuật toán phức tạp và tiết kiệm tài nguyên hơn truy vấn ngẫu nhiên (random walks) hay dùng bảng đinh tuyến. 6 Phương pháp tìm kiếm có liên hệ mật thiết và tác động sâu sắc tới tính ổn định, khả năng mở rộng và độ tin cậy của mạng. Mạng không cấu trúc thương được sử dụng trong môi trường mà các nút trong mạng luôn thay đổi. Có cấu trúc: Mạng không cấu trúc gặp nhiều khó khăn khi mở rộng, để giải quyết vấn đề này mạng có cấu trúc được đưa ra. Trong mạng có cấu trúc, mô hình của mạng phủ được kiểm soát chặt chẽ, các tài nguyên trong mạng được đặt ở các vị trí xác định. Hệ thống đảm nhận trách nhiệm ánh xạ giữa tài nguyên và vị trí của nút chứa tài nguyên đó, dưới dạng bảng định tuyến phân tán. Khi đó truy vấn có thể tới được nút chứa tài nguyên một cách hiệu quả. Mạng có cấu trúc cung cấp khả năng mở rộng cho việc tìm kiếm chính xác truy vấn (truy vấn với định danh chính xác). Nhược điểm của mạng có cấu trúc là việc duy trì mạng sẽ gặp khó khăn khi có quá nhiều nút ra vào mạng. 1.2. Mạng ngang hàng có cấu trúc Mạng không cấu trúc với sự phân bố tự do của nút và tài nguyên sẽ tồn tại nhược điểm về phương thức tìm kiếm gây tốn kém tài nguyên, đồng thời không đảm bảo sẽ luôn tìm được kết quả cho mỗi truy vấn. Vấn đề này càng trở nên khó giải quyết khi số lượng nút trong mạng tăng. Lý do đó khiến mạng không cấu trúc không được áp dụng trong các hệ thống yêu cầu khả năng mở rộng cao. Để khắc phục nhược điểm này ta sử dụng mạng có cấu trúc với kĩ thuật bảng băm phân tán (DHT). [9] Bảng băm phân tán là một hệ thống phân tán cung cấp chức năng tìm kiếm tương tự như bảng băm thông thường. Một cặp khóa và giá trị được lưu trong DHT và bất cứ nút nào tham gia vào hệ thống cũng có thể lấy được giá trị ứng với một khóa xác định. Việc duy trì bảng ánh xạ giữa khóa và các giá trị được lưu phân tán trên các nút, do đó việc thay đổi của một số nút tham gia vào hệ thống sẽ chỉ ảnh hưởng đến một số nhỏ các khóa liên quan. Điều này giúp cho DHT có thể dễ dàng mở rộng với số lượng lớn nút tham gia, và cung cấp khả năng duy trì hệ thống khi có nút tham gia, rời khỏi mạng, hay bị lỗi. 7 Hình 4: Bảng băm phân tán – DHT 1.2.1. Đặc điểm của DHT Các đặc điểm của DHT có thể tóm tắt như sau:  Phân tán: DHT là tập hợp các nút mà không cần bất kì một máy trung tâm nào.  Chống lỗi: hệ thống hoạt động được trong trường hợp các nút liên tục ra, vào, hoặc bị lỗi  Khả năng mở rộng: hệ thống hoạt động ổn định khi có số lượng lớn các nút tham gia. Để đạt được các đặc điểm mô tả ở trên kỹ thuật được sử dụng chủ yếu là mỗi nút phải có liên hệ, trao đổi với một số nút khác có trong mạng – thông thường là O(log n) với mạng có n nút tham gia. Do đó chỉ cần một số ít điều chỉnh khi có sự thay đổi về các nút tham gia mạng. Ngoài ra một hệ thống DHT cũng như bất kỳ hệ thống phân tán khác còn cần phải quan tâm đến các vấn đề như chống tấn công từ bên trong hay ngoài hệ thống, cân bằng tải, xác thực dữ liệu và hiệu năng của hệ thống 1.2.2. Cấu trúc hệ thống Cấu trúc của hệ thống DHT có thể gồm nhiều thành phần chính: Phần quan trọng nhất là không gian khóa ảo, ví dụ như chuỗi có độ dài 160 bit. Cách thức phân vùng của không gian khóa chia không gian khóa cho từng nút trong hệ thống. Một mạng phủ kết nối các nút với nhau, giúp các nút này tìm được nút đang giữ thông tin về một khóa trong không gian khóa. Với các thành phần như trên DHT có thể sử dụng phương thức sau để lưu trữ và lấy dữ liệu. Giả sử có không gian khóa gồm các khóa có độ dài 160 bit. Để lưu một filie với tên file và dữ liệu của nó trong DHT, thuật toán SHA-1 được sử dụng để tạo mã băm của tên file – là khóa k có độ dài 160 bit. Tiếp đó một thông 8 báo put(k,data) được gửi đến các nút trong mạng DHT. Thông điệp này được chuyển tiếp qua các nút qua mạng phủ cho đến khi tới được nút giữ trách nhiệm lưu giữ khóa k được quy định bởi cách phân bổ không gian khóa. Nút đó sẽ thực hiện lưu giữ khóa và dữ liệu. Các nút khác có thể lấy thông tin của file bằng cách thực hiện hàm băm trên tên file để lấy được khóa k, sau đó truy vấn bất kỳ nút nào trong mạng DHT để tìm kiếm dữ liệu ứng với khóa k bằng thông điệp get(k). Thông điệp này tương tự được truyền trên mạng phủ thông qua các nút cho đến khi tới nút lưu giữ thông tin về khóa k, nút này sẽ trả lại thông tin về dữ liệu ứng với khóa. Cách thức phân bổ không gian khóa và các thành phần của mạng phủ của một hệ thống DHT cơ bản sẽ được mô tả như ở dưới Phân bổ không gian khóa Phần lớn các hệ thống DHT sử dụng các phương pháp consistent hashing để ánh xạ khóa vào các nút. Kĩ thuật này cung cấp một hàm δ(k1,k2) để tính khoảng cách giữa hai khóa k1 và k2. Khoảng cách này không liên quan gì đến khoảng cách vật lý hay độ trễ của mạng. Mỗi nút được gán cho một khóa định danh ID. Một nút với ID là ix sẽ có trách nhiệm lưu trữ với tất cả các khóa km nếu như ix là định danh nút gần nhất với các khóa đó, tính toán bằng hàm δ(k1,k2). Phương pháp consistent hashing có một tính chất cần thiết cho DHT đó là khi có sự thêm bớt một nút trong mạng chi có những khóa thuộc nút đó mới cần chuyển sang các nút lân cận, trong khi không tác động gì đến các nút khác. Điểm này hoàn toàn khác biệt với phương pháp bảng băm thông thường, khi thay đổi một phần sẽ khiến cho gần như toàn bộ không gian khóa phải tính toán lại. Do việc chuyển đổi khóa từ nút này sang nút khác yêu cầu lượng băng thông trong việc chuyển đổi các dữ liệu, do đó để đáp ứng điều kiện mạng có nhiều biến động (nút ra vào với tần suất cao) thì việc có ít thay đổi lên cấu trúc mỗi khi có thay đổi là yêu cầu cấp thiết. Mạng phủ Mỗi nút duy trì một tập các đường dẫn đến các nút khác (các nút láng giềng) hay còn gọi là bảng định tuyến. Tập các đường dẫn này tạo lên mạng phủ. Một nút chọn các nút láng giềng dựa theo một cấu trúc nhất định gọi là topology của mạng. Tất cả các topology của DHT đều chứa các đặc điểm nhất định như: với khóa k bất kỳ, mỗi nút hoặc sẽ có là nút lưu trữ khóa k hoặc có đường dẫn tới nút có định danh gần với khóa k hơn, theo nghĩa về khoảng cách giữa các khóa đã nêu ở trên. Khi đó có thể dễ dàng chuyển tiếp truy vấn tới nút chịu trách nhiệm về 9 khóa sử dụng thuật toán tham lam: nút chỉ cần chuyển tiếp truy vấn đến một nút khác có định danh gần nhất với khóa cần tìm. Khi không còn nút nào gần với khóa tìm kiếm hơn thì chứng tỏ truy vấn đã tới nút chịu trách nhiệm về khóa đó. Phương thức định tuyến này còn được gọi là phương thức định tuyến dựa trên khóa. Ngoài việc đảm bảo định tuyến một cách chính xác, một topology cần phải đảm bảo hai yếu tố quan trọng là đảm bảo số lượng tối đa các nút phải đi qua để trả lời một truy vấn phải nhỏ để đảm bảo đáp ứng nhanh truy vấn và số lượng láng giềng của một nút (bậc của nút) phải nhỏ để đảm bảo không làm gây khó khăn trong việc duy trì hệ thống. Dĩ nhiên nếu muốn giảm số lượng nút phải đi qua thì sẽ phải tăng số lượng láng giềng trên mỗi nút. 1.3. Mạng Chord [7] Chord là một trong những giao thức phổ biến nhất được sử dụng trong bảng băm phân tán. Giao thức Chord hỗ trợ khả năng gán tương ứng một key cho trước với một nút mạng. Tùy thuộc vào ứng dụng sử dụng Chord, nút đó có thể đảm nhiệm nhiệm vụ lưu trữ dữ liệu được gán với khóa đó. Chord sử dụng phương pháp consistent hashing, gián tiếp thực hiện việc cân bằng tải giữa các nút do mỗi nút được gán với một số lượng key tương đương nhau. Việc tham gia và rời khỏi mạng sẽ chỉ khiến cho một số nhỏ các key chuyển từ nút này sang nút khác. Đặc điểm khiến Chord trở nên thông dụng chính là khả năng mở rộng mạng. Trong khi với các thuật toán trước đó một nút cần phải duy trì thông tin về nhiều nút khác trong mạng thì Chord chỉ cần một số lượng cố định. Chính điều này giúp cho Chord có thể hoạt động hiệu quả trong mạng có số lượng các nút lớn. Chord được đưa ra nhằm giải quyết các vấn đề thường gặp trong mạng ngang hàng:  Cân bằng tải: Chord đóng vai trò phân phối khóa đến từng nút với số lượng đồng đều, thông qua đó gián tiếp mang lại hiệu quả cân bằng tải.  Tính phân tán: Chord là hệ thống phân tán hoàn toàn: trong mạng không có nút nào đóng vai trò quan trọng hơn các nút khác. Điều này nâng cao tính ổn định và khiến Chord có thể đáp ứng các ứng dụng ngang hàng trong môi trường mạng không ổn định.  Khả năng mở rộng: Độ phức tạp của một truy vấn trong mạng Chord tăng lên ứng với log của số lượng các nút, do đó có thể đáp ứng cả với những hệ thống rất lớn. 10  Khả năng chịu lỗi: Chord có khả năng tự điều chỉnh các bảng định tuyến trên mỗi nút tương ứng với sự ra vào của các nút, cũng như khi có một nút đột ngột rời khỏi mạng. Chord đảm bảo trong bất kỳ môi trường mạng nào với mỗi một khóa bất kỳ đều có một nút tương ứng, chịu trách nhiệm về khóa đó. Điều này luôn đúng dù trạng thái của hệ thống liên tục thay đổi.  Khả năng đặt tên linh hoạt: Chord không có bất kỳ rằng buộc nào trên cấu trúc khóa mà nó tìm kiếm. Điều này cung cấp cho các ứng dụng sử dụng Chord khả năng tùy biến trong việc gán tên với các khóa của Chord. Giao thức Chord cung cấp khả năng tính toán phân tán một cách nhanh chóng nhằm ánh xạ một khóa với nút tương ứng. Chord gán các khóa vào các nút bằng cách sử dụng phương pháp consistent hashing, phương pháp này có một số khả năng cần thiết cho giao thức Chord. Với xác suất cao hàm băm sẽ phân bổ đều khóa đến các nút (các nút ban đầu nhận được cùng một số lượng khóa). Cũng với xác suất cao khi nút thứ N tham gia hay rời khỏi mạng chỉ một số lượng nhỏ (O(1/N)) các khóa phải chuyển tới vị trí khác. Điều này rõ ràng giúp cho mạng luôn giữ được một mức cân bằng tương đối. Chord nâng cao khả năng mở rộng của phương pháp consistent hashing bằng cách không yêu cầu một nút phải biết tất cả các nút còn lại trong mạng. Một nút chỉ cần biết một số thông tin định tuyến giới hạn về một số nút khác. Bởi vì thông tin này là phân tán do đó một nút tiến hành hàm băm bằng cách liên hệ với các nút khác. Trong mạng gồm N nút, mỗi nút chỉ cần duy trì thông tin về O(log N) các nút khác, và mỗi một truy vấn chỉ yêu cầu O(log N) thông điệp. Phương pháp consistent hashing gán mỗi nút và khóa với một chuỗi định danh gồm m bit sử dụng SHA-1 làm thuật toán băm cơ sở. Số m phải chọn đủ lớn sao cho khả năng hai nút hoặc khóa có chung định danh là không đáng kể. 1.3.1. Mô hình của Chord Các nút trong mạng Chord tạo lên một mạng logic dạng vòng tròn có các vị trí nút từ 0 đến 2m-1. Khóa k được gán cho nút đầu tiên có định danh bằng hoặc lớn hơn định danh của k. Nút đó được gọi là nút successor của khóa k hay successor(k). Trong vòng định danh của Chord successor của một khóa chính là nút gần nhất theo chiều kim đồng hồ tính từ khóa k. 11 Hình 5: Mô hình vòng Chord với khóa có chiều dài 6 bit Trong hình 5 là vòng Chord với m=6. Vòng Chord có chứa 10 nút và 5 khóa. Successor của định danh 10 là nút 14 do đó key 10 sẽ được đặt ở nút 14. Tương tự khóa 24 và 30 sẽ được đặt ở nút 32, khóa 38 tại nút 38 và khóa 54 tại nút 56. Kĩ thuật consistent hashing được thiết kế để việc các nút tham gia hay rời khỏi mạng sẽ tạo ra ít ảnh hưởng nhất. Để duy trì bảng mapping khi một nút n tham gia vào mạng, một số khóa trước đây được đặt tại successcor của n sẽ chuyển sang cho nút n. Trong ví dụ trên, nếu có một nút với định danh 26 tham gia vào mạng, nó sẽ nhận được khóa 24 chuyển từ nút 32. Successor của một nút là nút tiếp sau nút đó trên vòng Chord, predecessor là nút liền trước trên vòng Chord. 1.3.2. Tìm kiếm trong mạng Chord Tìm kiếm đơn giản: Đây là thuật toán tìm kiếm đơn giản nhất trong Chord. Thuật toán này chỉ yêu cầu các nút biết được successor của mình. Truy vấn cho một định danh được chuyển xung quanh vòng Chord qua các nút successor cho đến khi gặp nút có chứa khóa với định danh cần tìm. 12 Hình 6: Quá trình tìm kiếm đơn giản trên Chord Trong hình 6 là ví dụ khi nút 8 thực hiện truy vấn cho khóa có định danh 54. Nút 8 gọi hàm find_successor cho khóa 54, kết quả trả về là nút 56 – successor của khóa 54 này. Truy vấn được chuyển lần lượt qua tất cả các nút trên vòng nằm giữa nút 8 và 56. Mở rộng khả năng tìm kiếm: Thuật toán tìm kiếm ở trên sử dụng một số lượng thông báo tương ứng tuyến tính với số nút có trong mạng. Để tăng tốc độ quá trình tìm kiếm Chord sử dụng thêm một số thông tin định tuyến. Tương tự như trên, ví dụ định danh của mỗi nút và khóa có độ dài m bit. Mỗi nút n duy trì một bảng định tuyến chứa m mục, được gọi là bảng finger. Mục thứ i trong bảng của nút n chứa định danh của nút s sao cho s là nút đầu tiên trên vòng tiếp sau khóa n+2 i-1 s=successor(n+2 i-1 ), với 1 ≤ i ≤ m (lấy số dư với modun 2m). Ta gọi s là finger thứ i của nút n. Finger đầu tiên của một nút cũng chính là successor của nút đó. 13 Hình 7: Bảng finger của nút 8 Hình 8 thể hiện bảng finger của nút . Finger đầu tiên được trỏ đến nút 14 dó 14 là nút liền sau (8+20) mod 26 = 9. Tương tự finger cuối cùng của nút 8 trỏ đến nút 42 do 42 là nút liền sau (8+25) mod 26 = 40. Có thể dễ nhận xét thấy với các thiết lập như vậy: một nút chỉ lưu thông tin về một số giới hạn các nút có trong mạng, một nút cũng chỉ biết đến một số nút nằm gần với nó. Một nút cũng không lưu trữ đủ thông tin để có thể ngay lập tức tìm được successor của một khóa k. Hình 8: Giả mã của phương pháp tìm kiếm cải tiến Hình 8 thể hiện đoạn giả mã ứng với việc thực hiện tìm kiếm successor của key id có sử dụng bảng finger. Nếu id nằm giữa n và successor của nó, find_successor sẽ trả lại successor của nó. Nếu không n tìm kiếm trong bảng 14 finger cho nút n‟ – có định danh ngay sau id cần tìm kiếm và thực hiện hàm find_successor trên nút n‟. Hình 9: Quá trình tìm kiếm khóa 54 trên nút 8 Như hình 9 ở trên nút 8 tìm kiếm successor của khóa 54. Qua bảng finger của nút 8 ta thấy nút 42 là nút gần khóa cần tìm kiếm nhất, nên nút 8 sẽ thông qua nút 42, tương tự query sẽ chuyển qua nút 51 và đến đích là nút 56. Có thể chứng minh được định lý có nội dung như sau: Với xác suất cao số nút cần thông qua để tìm kiếm successor trong một mạng N nút là O(log N) [7] 1.3.3. Quá trình tham gia và ổn định mạng Trên thực tế, mạng Chord cần phải giải quyết các vấn đề như việc một nút mới tham gia vào mạng, rời khỏi mạng và đột ngột rời khỏi mạng. Để tham gia vào mạng một nút n thực hiện truy vấn tìm kiếm cho chính id của nó thông qua một số nút ban đầu đã tham gia vào mạng và tự đưa nó vào vòng Chord, ở vị trí nằm giữa successor s và predecessor của s thông qua quá trình ổn định mạng. Bảng finger của n được khởi tạo bằng cách sao chép bảng finger của của s hoặc để s lần lượt tìm kiếm các finger cho n. Các nút cần thay đổi bảng finger khi có sự tham gia của n sẽ lần lượt thực hiện việc này thông qua quá trình ổn định mạng chạy định kỳ. Cuối cùng các khóa đang được giữ bởi s, có id nhỏ hơn hoặc bằng n sẽ được chuyển qua n. 15 Khi một nút tự nguyện dời khỏi mạng, tất các khóa (các item liên quan đến khóa) được chuyển cho successor, sau đó thông báo cho successor và predecessor. Bảng finger trên các nút khác sẽ dần dần được điều chỉnh thông qua quá trình ổn định mạng định kỳ. Chống lỗi và tạo bản sao: Khi một nút đột ngột rời khỏi mạng sẽ gây ra các hậu quả như sau: Đầu tiên việc này có thể gây mất các khóa (các item liên quan đến khóa). Thứ hai: một bộ phận các nút sẽ không truy vấn được một số khóa nhất định. Chord giải quyết vấn đề này bằng cách lưu trên mỗi nút một danh sách các nút nằm sau nó trong vòng Chord. Nếu một nút đột ngột không liên lạc được với successor thì nó sẽ sử dụng các nút liền sau trong danh sách. Tiếp nữa các khóa (các item liên quan tới khóa) sẽ được sao chép trên các nút có trong danh sách đó. Do đó một khóa (item liên quan đến khóa) sẽ chỉ bị mất khi có log2(N)+1 các nút trong danh sách phải đồng thời rời khỏi mạng. 16 Chương 2. Vấn đề điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc 2.1. Tắc nghẽn và tầm quan trọng của việc điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc Mạng ngang hàng có cấu trúc được xây dựng với mục đích đáp ứng được nhu cầu mở rộng về số lượng node, khóa cũng như khả năng đáp ứng của toàn mạng. Đối với một hệ thống chia sẻ file đơn giản khi mỗi node chỉ phải đáp ứng số lượng nhỏ query và chỉ phải index một số giới hạn các tập tin, hệ thống có thể hoạt động tốt với thiết kế ban đầu. Tuy nhiên trong thời gian gần đây, mạng ngang hàng có cấu trúc được phát triển để có thể phục vụ cho các ứng dụng có độ phức tạp cao, ví dụ như hệ thống truy vấn thông tin (P2P Information Retrieval – P2P-IR) [8] hay hệ thống quản trị cơ sở dữ liệu (P2P Database Management Systems - P2P-DBMS) [2]. Các ứng dụng ở lớp trên này tạo lượng truy vấn lớn hơn rất nhiều, ví dụ: với một hệ thống chia sẻ file đơn giản các nút chỉ phải đánh index và tạo một số lượng khóa nhỏ lấy từ tên của các file, với một hệ thống truy vấn sử dụng kĩ thuật tìm kiếm full-text số lượng khóa phải index và đưa vào mạng là vài nghìn với một văn bản. Trong DHT, cụ thể ở đây là mạng Chord một nút đảm nhận hai chức năng chính là trả lời truy vấn và chuyển tiếp truy vấn đến nút khác, do đó khi một nút có vấn đề cũng có thể gây ảnh hưởng tới nhiều nút khác trong mạng. Thông thường các nút trong mạng có cấu hình phần cứng và băng thông mạng rất đa dạng, do đó khả năng đáp ứng truy vấn của từng nút cũng hoàn toàn khác nhau. Ngoài ra với mạng ngang hàng thường xảy ra tình trạng một số lượng tài nguyên được truy vấn với tần suất cao, chỉ trong một khoảng thời gian nhất định. Những đặc điểm trên khiến cho mạng ngang hàng có cấu trúc dễ xảy ra tình trạng tắc nghẽn và có thể gây ảnh hưởng rộng trên toàn mạng. Tắc nghẽn trong DHT thường bắt đầu khi một nút nhận được số truy vấn vượt quá khả năng xử lý của nó, nếu không có cơ chế thích hợp các truy vấn sau đến hoặc đi qua nút đó sẽ tạo ra tắc nghẽn trên mạng, có thể gây sụp đổ toàn mạng. Việc điều khiển tắc nghẽn giúp một hệ thống DHT có khả năng xử lý lượng lớn truy vấn nhằm đáp ứng cho các ứng dụng phức tạp ở lớp trên. Việc xử lý tắc nghẽn trên DHT nằm ở tầng trên và độc lập với các cơ chế điều khiển tắc nghẽn ở các tầng bên dưới, như TCP. 17 2.2. Phân tích quá trình sụp đổ do tắc nghẽn trong mạng ngang hàng có cấu trúc [8] Trong mục này chúng ta sẽ phân tích quá trình sụp đổ của một mạng DHT khi có tắc nghẽn xảy ra và không có cơ chế điều khiển tắc nghẽn nào được sử dụng. Nhằm đơn giản hóa, ta xét mạng DHT trong trường hợp đặc biệt khi các nút có cùng khả năng đáp ứng truy vấn. Giả sử các nút tham gia vào mạng thực hiện các truy vấn với tốc độ chỉ phụ thuộc vào khả năng của từng nút (ví dụ như tốc độ của bộ vi xử lý hay đường truyền của nút đó). Các truy vấn đến từ các nút khác nhau sẽ phải “cạnh tranh” tài nguyên trên nút đích. Nếu như lượng truy vấn đến vượt quá khả năng xử lý của một nút thì nút đó sẽ phải loại bỏ một số truy vấn. 2.2.1. Khái quát Mục đích của việc phân tích này là nghiên cứu về thông lượng đạt được – A trong mạng DHT khi mỗi nút tạo ra lượng truy vấn với tốc độ x. Mỗi truy vấn có xác suất được thực hiện thành công là p. p=1 nếu như nút không bị quá tải, ngược lại 0<p<1. Một nút được xác định tắc nghẽn hay không dựa vào lượng truy vấn tới và tài nguyên trên máy (có thể là tốc độ vi xử lý hoặc băng thông). Do đó ta phải tính toán tổng tải O mà tài nguyên thấp nhất (bottleneck) trên nút phải xử lý và so sánh với khả năng của nút đã được cho trước: c, qua đó ta có thể tính p và thông lượng đạt được A là một hàm của x. p là đại lượng không thứ nguyên, còn x,O và A có đơn vị là số truy vấn/giây. 2.2.2. Định nghĩa Thông lượng đến: Mỗi nút khởi tạo các truy vấn, được chuyển qua các nút trong mạng. Để tính tổng tải đến O trước hết ta định nghĩa thông lượng đến od h là thông lượng đến với đích là d trước khi qua h nút. Như đã giả thiết ở trên, các nut có cùng khả năng đáp ứng truy vấn, và các nút cùng khởi tạo một số lượng truy vấn. Do đó, thông lượng đến độc lập với nguồn sinh truy vấn. Để đơn giản ta xét một mạng Chord nhỏ, tuy nhiên kết quả sẽ vẫn đúng cho bất kì mạng DHT log n nào. 18 Hình 10: (a) tải đến các nút tạo bởi P0, (b) Tải tới và rời khỏi nút Hình 10a thể hiện thông lượng đến các nút khác được sinh bởi nút P0. Mỗi nút có log2n = l (ở đây n=8 và l=3) mục trong bảng định tuyến, mỗi mục trỏ đến một nút với khoảng cách 2i với i=0…(l-1). Mỗi nút thực hiện việc định tuyến bằng cách gửi truy vấn đến nút gần khóa được tìm kiếm nhất. P0 tạo các truy vấn đến 7 nút còn lại trong mạng. Một trong số truy vấn được chuyển qua nút khác.Ví dụ o7 1 là thông lượng đến tại P0 với đích đến là P7 trước khi đi qua nút đầu tiên (P0 – P4). Thông lượng đạt được: Mỗi nút có khả năng đáp ứng c để xử lý thông lượng đến. c phụ thuộc vào tốc độ vi xử lý và đường truyền của nút. Nếu như tổng thông lượng đến không vượt quá khả năng xử lý của nút, tất cả truy vấn đều được xử lý. Ngược lại sẽ có một số truy vấn bị hủy. Ta định nghĩa thông lượng đạt được như sau: ad h là thông lượng đạt được với đích là d sau khi qua h nút. Ví dụ: a7 1 ≤ o7 1 là thông lượng với đích là nút 7 sau khi qua nút đầu tiên, ứng với thông lượng tới nút 4. Xác suất xử lý: thông lượng đã xử lý được định nghĩa bởi công thức: p= min (1, c/O) (1) ở đó c là khả năng xử lý của nút và O là tổng tải đến. Khi một nút không quá tải O≤c tất cả thông lượng tới đều được xử lý, khi đó p=1, ngược lại p <1. Giả sử nếu thông lượng đến lớn gấp 2 lần khả năng xử lý của nút thì khi đó xác suất xử lý là 0.5. 19 Nếu truy vấn đến nút đích đi qua một số các nút, tại các nút tiếp theo thông lượng đến được tính theo công thức: (2) 2.2.3. Các mô hình Mỗi nút phải xử lý các truy vấn đến và đi hình 10b: truy vấn đến bao gồm tổng thông lượng tới Ofinal, được xử lý bởi ứng dụng phía trên và thông lượng truyền qua Orel là các truy vấn được chuyển đến các nút khác. Ta xet hai trường hợp tắc nghẽn: Trường hợp 1: Đường truyền lên (uplink) là bottleneck: Trên thực tế rất nhiều máy tính cá nhân có đường truyền bất đối xứng với tốc độ download lớn hơn tốc độ upload. Vì thế băng thông của uplink quyết định đến khả năng xử lý của nút. Tuy nhiên chúng ta cũng phải chú ý tới đại lượng α được sinh ra bới các gói tin ack phục vụ cho việc tải thông tin xuống trên đường downlink. Do đó tổng tải đến nút là: Trường hợp 2: Khả năng xử lý của nút là bottleneck: Nếu một nút có đủ băng thông cho cả đường uplink và downlink thì khi đó bottleneck của nút là tốc độ của vi xử lý. Ta có: 2.2.4. Tổng tải đến O Chúng ta tính toán OM1 và OM2 cho mô hình mạng DHT trên, để có thể tính được khả năng xử lý p với c cho trước sử dụng công thức 1. Chúng ta xét trường hợp các nút đồng thời tạo ra các truy vấn ngẫu nhiên với tốc độ x. x ở đấy chứa cả các truy vấn mà nút khởi tạo có thể tự trả lời, tức không cần đi qua nút nào.Trước hết ta xét trường hợp ứng với mạng gồm 8 nút, sau đó sẽ xét tới trường hợp tổng quan. Với mạng gồm 8 nút: Trong trường hợp này số truy vấn không phải qua bất kỳ nút nào là x/8, và 7/8 . x truy vấn cần đi qua các nút trong mạng để đến được đích. Khi đó tải đến nút đầu tiên sẽ là: 20 ∀ d, 0 < d ≤ 7, od 1 = 1/8 · x (3) Ta sẽ tính tổng thông lượng O đến mỗi nút sinh bởi P0. Sử dụng công thức 2 và 3 ta có: Thông lượng tạo bởi ứng dụng đến tất cả các đích trong mạng DHT trước khi qua nút đầu tiên: Thông lượng đạt được tại tất cả các đích sau khi đi qua nút cuối cùng, được xử lý bởi ứng dụng và không chuyển tiếp nữa được tính bởi công thức: Thông lượng chuyển tiếp được chuyển qua các nút lân cận được tính bởi công thức: Thông lượng đến và đi có thể được tính như sau: Với trường hợp có n nút: với bất kỳ mạng DHT log n nào với n=2l trong đó mỗi nút có l=log2n liên kết đến các nút khác trong mạng. Tổng tải trên mỗi nút với đích đến là d ở nút đầu tiên là: ∀ d, 0 < d < n, od 1 = x/n = x/2 l Chúng ta có các tổng tải tương ứng là: 21 Thông lượng cuối hay còn gọi là thông lượng đạt được A thể hiện tổng tất cả các truy vấn được định tuyến thành công. Trong mạng DHT log n qua cách thức chọn lựa các mục định tuyến ta có thể tính toán số lượng các nút có thể đến sau khi đi qua một số nút nhất định bằng tam giác Pascal. Với l nút trong bảng định tuyến sau h lần đi qua các nút khác sẽ có thể tới: nút đích. Trên mỗi nút mà truy vấn đi qua, mỗi truy vấn sẽ được xử lý với xác suất là p. Do đó ta có: Ở đây ta chỉ xét các truy vấn được chuyển qua nút khác, các truy vấn được trả lời ngay trên host đó coi như không tốn tài nguyên, do đó h≥1. Thông lượng chuyển tiếp được tính bằng cách lấy tổng thông lượng đi ra trừ đi thông lượng mới được tạo Tổng thông lượng có thể được tính bằng tam giác Pascal. Tuy nhiên chúng ta xét tới tất cả các nút chứ không riêng ở nút đích. Do đó ta có: Sử dụng công thức 8 với l=3 ta sẽ có lại đúng công thức 4 đã xét ở phần trước. 22 2.2.5. Ví dụ với một triệu nút Ta lấy ví dụ trường hợp l=20, ứng với n=220 tức khoảng 1 triệu nút. Giả sử khả năng xử lý trên mỗi nút là c=120 truy vấn/giây. Ta xét hai trường hợp: M1 là trường hợp đường truyền lên của nút là bottleneck, M2 là trường hợp tốc độ vi xử lý của nút là bottleneck. Ta chọn α=5% cho trường hợp M1 ứng với thông lượng mà các gói tin ACK của TCP. Với các công thức 1, 5 và 8 ta có thể tính toán được xác suất xử lý p với 2l nút với c và x cho trước. Với p và công thức 6 ta có thể tính được Ofinal tức là thông lượng đạt được của mạng DHT. Hình dưới thể hiện thông lượng đạt được A. Thông lượng đạt được cao nhất đạt được khi x đạt giá trị tối ưu: x=11.4 trong trường hợp M1 và x=10,9 trong trường hợp M2. Khi tổng tải đến vượt quá giá trị x tối ưu, thông lượng đạt được sẽ giảm một cách nhanh chóng. Đó là hiện tượng sụp đổ do tắc nghẽn. Hình 11: Thông lượng đạt được so sánh với tốc độ truy vấn cho hệ thống DHT với một triệu nút trong hai trường hợp tắc nghẽn M1 và M2. Mạng DHT sụp đổ khi tải tới đạt đến giá trị xopt 2.2.6. Phân tích các trạng thái tiệm cận của A. Ta xét A trong trường hợp mạng DHT chạy với khả năng tối đa: p → 1 và trường hợp mạng DHT bị quá tải ở mức cao: p → 0 23 Sử dụng công thức )1/()1( 1 0 ppp h h j j    1)1( 1         lhl h pp h l 12 1         ll h h l để đơn giản các công thức từ 5 đến 8 ta có: Ta sẽ tính toán sự thay đổi của thông lượng đạt được A khi p→1 và khi p→0. Với trường hợp M1 ta có: 24 Ứng với p→1 tức là mạng được sử dụng hết khả năng tuy nhiên vẫn chưa quá tải có: Với O≥c mạng được sử dụng hết hoặc chưa sử dụng hết ứng với p ≤1 và O=c/p. Chúng ta có thể tính toán O khi p→1 Với trường hợp M2 tương tự ta có: Ứng với p→0 tức là đang xảy ra tình trạng tắc nghẽn ở mức độ cao. Sử dụng công thức 1/1 – p = 1+p+p 2 +. . ., với | p | < 1 ta có thể khai triển c/x=pO/x thành: a0p 0 + a1p 1 + a2p 2 + . . . và p thành: b0 + b1x -1 + b2x -2 + . . . Do đó ta có:    ... 2 12 21)1( )1(2 2 2      pappp p p x c l l ll l  25 ... 12 2 2 2 1     xbx c p l l Thay p vào công thức 9 và sử dụng công thức:   ...1... 210 1 210 0                            lpp l p l p l p k l p k l k l Do đó với trường hợp 1 và 2 khi p→0 ta có: 2.2.7. Kết luận Với hai trường hợp M1 khi đường uplink là bottleneck, và M2 khi tốc độ xử lý là bottleneck, mạng DHT có thể rơi vào trạng thái sụp đổ do tắc nghẽn nếu như các nút trong mạng tăng tốc độ truy vấn mà không tính toán đến khả năng chịu tải của mạng. Trong thực tế với mô hình mạng phức tạp, khả năng chịu tải của các nút là hoàn toàn khác nhau, thời gian truy vấn không theo quy luật, tình trạng mạng sụp đổ do tắc nghẽn sẽ xảy ra dễ dàng và nhanh chóng hơn. 26 Chương 3. Các nghiên cứu về điều khiển tắc nghẽn trên DHT Các nghiên cứu liên quan về vấn đề điều khiển tắc nghẽn của mạng DHT tập trung chủ yếu vào hai hướng giải quyết:  Điều khiển tốc độ truy vấn: giới hạn tốc độ gửi ở nút truy vấn hoặc tốc độ xử lý ở nút đích khi nút đích có hiện tượng quá tải. Gồm các phương pháp: Credit System Congestion Control (CSCC), Back-Pressure Congestion Control (BPCC), và phương pháp đánh dấu (Marking)  Thay đổi bảng định tuyến nhằm chuyển truy vấn đang đi qua nút quá tải sang nút không quá tải. Ý tưởng chung của các phương pháp này là việc không sử dụng thuật toán định tuyến tham lam (như trong Chord, nút được chuyển tiếp gói tin đến là nút trong bảng định tuyến có định danh gần với khóa nhất), mà dựa vào tình trạng từng nút để thay đổi đường đi của gói tin qua các nút ít tắc nghẽn hơn. Các phương pháp này đều có những ưu nhược điểm riêng sẽ được phân tích dưới đây. 3.1. Phương pháp CSCC[4] Ta có thể coi mô hình của mạng DHT (cụ thể là Chord) được phân tầng như hình dưới Hình 12: Phương pháp CSCC 27 Layer 1 đảm nhận việc truyền thông tin giữa 2 nút, layer 2 – overlay routing đảm nhận việc chuyển tiếp gói tin lên trên hoặc qua các nút khác tùy thuộc vào điểm đến của gói tin, layer 3 là tầng ứng dụng nằm trên mạng DHT. CSCC hoạt động phía trên của layer 2 – overlay routing và dưới layer 3. Tại nút đích mỗi khi nhận được gói tin đến CSCC sẽ trả lại gói tin ACK trực tiếp cho nút ban đầu gửi truy vấn bằng giao thức UDP. Tại nút nhận, CSCC duy trì trong bộ nhớ đệm của nó một hàng đợi cho các truy vấn đến. Khi hàng đợi đạt tới mức giới hạn của nút, các truy vấn đến sau sẽ bị loại bỏ mà không có thông báo gì cho nút gửi. Trên mỗi nút lưu một giá trị credit thể hiện số lượng truy vấn đã gửi đi mà chưa nhận được gói tin ACK trả về. Sử dụng thuật toán tương tự như thuật toán tính toán kích thước cửa sổ TCP cho giá trị credit, ta so sánh giá trị credit này với một giá trị threshold. Nếu credit nhỏ hơn threshold ta tiếp tục tăng nhanh giá trị credit, nếu credit đến ngưỡng threshold, ta sẽ tăng chậm hơn với mỗi gói ACK nhận được. Nếu như có gói tin bị mất (quá thời gian timeout mà chưa có gói ACK trả về) giá trị threshold sẽ được giảm xuống. Sau khi nhận biết một gói tin bị mất, nút gửi sẽ gửi lại gói tin đó. Có thể thấy phương thức hoạt động của CSCC gần tương tự như CC của TCP. Tuy nhiên nhược điểm của CSCC là sử dụng trên mạng DHT với quá trình kết nối tương đối phức tạp, chuyển tiếp giữa nhiều nút, không giống như TCP có kết nối 2 điểm trong thời gian dài và tương đối ổn định. Điều này gây khó khăn cho việc xác định các giá trị cần thiết như thời gian timeout. Thêm nữa, một gói tin có thể nhận được nhiều lần do đó mỗi nút cần phải tốn tài nguyên lưu giữ danh sách các gói nhận được ứng với mỗi nút gửi. CSCC thực hiện việc drop gói tin do đó thông lượng đạt được sẽ giảm. 3.2. Phương pháp BPCC[4] Tương tự như phương pháp CSCC mỗi nút đều lưu một hàng đợi cho các truy vấn đến. Tuy nhiên ở phương pháp này thay vì loại bỏ gói tin, nút đích gửi trạng thái hàng đợi của nó cho nút gửi. Khi đó nút gửi sẽ tự điều chỉnh lại tốc độ gửi để tránh tắc nghẽn xảy ra. BPCC sử dụng TCP ở layer 1. 28 Hình 13: Phương pháp BPCC Khi hàng đợi tại nút P đầy, thay vì loại bỏ gói tin, nút sẽ tạm ngưng việc đọc gói tin từ socket TCP của các kết nối đến. Khi đó thuật toán điều khiển lưu lượng sẵn có của TCP sẽ tự động làm chậm lại việc các nút gửi truy vấn đến nút P. Nguy cơ hình thành deadlock: Nguyên nhân của việc hình thành deadlock là khi một nút gửi đợi nút nhận xử lý các gói tin trong hàng đợi, trong khi nút nhận cũng đang phải đợi một nút khác. Deadlock xảy ra khi các nút đợi nhau tạo thành vòng kín, dễ thấy trong trường hợp mạng có dạng vòng như Chord. Có thể thấy khác biệt lớn nhất của BPCC là việc phương thức này không drop gói tin, do đó tăng thông lượng đạt được trên toàn hệ thống. Tuy nhiên phương pháp này có thể sinh ra deadlock và việc phát hiện, xử lý deadlock này là rất khó khăn, đặc biệt là trong môi trường mạng ngang hàng với sự tham gia của nhiều nút tự do, không thể kiểm soát. Ngoài ra việc chờ đợi trên các nút gây tăng thời gian đáp ứng của các truy vấn. 3.3. Phương pháp Marking[3] Hai phương pháp CSCC và BPCC ở trên có chung một nhược điểm là chỉ thực hiện việc chống tắc nghẽn tức là khi tắc nghẽn đã xảy ra trên mạng. Phương pháp Marking có gắng giải quyết vấn đề này. Để phân tích phương pháp này ta xét lần lượt từng thành phần tham gia vào việc điều khiển tắc nghẽn trong phương pháp này: Layer 3 BPCC Layer 2 Layer 1 - TCP Layer 3 BPCC Layer 2 Layer 1 - TCP Destination Queue state Source 29 Hàng đợi: Trên mỗi nút duy trì một hàng đợi chứa các truy vấn tới. Ta sử dụng các hàng đợi này để phản hồi tình trạng tắc nghẽn thông qua việc thêm một cờ h vào trong header. Mục đích là giữ cho các nút được chia sẻ tài nguyên đang bị bottleneck một cách công bằng mà không làm quá tải nút đang tắc nghẽn. Cờ h có kích thước 1 bit, mặc định được tắt trong gói tin truy vấn tại nguồn. Cờ h tắt thể hiện tình trạng mạng không tắc nghẽn, h bật thể hiện tình trạng tắc nghẽn. Mỗi nút đặt giá trị x thể hiện tốc độ truy vấn hiện tại của nó vào trong header của gói tin. Ngoài ra mỗi nút lưu số lượng trung bình xavg các gói tin, được tính toán thông qua giá trị x nhận được từ một số gói tin đến trước đó. Cờ h được bật với xác suất q được xác định thông qua việc xét xem gói tin đến có tốc độ nhanh hay chậm hơn giá trị trung bình xavg và giá trị trung bình kích thước của hàng đợi, cụ thể như sau: s: là số lượng gói tin trong hàng đợi δ: giá trị làm mềm, ví dụ bằng 0.9 s : số lượng trung bình các gói tin trong hàng đợi t: giá trị ngưỡng tối đa sẽ gửi phản hồi γ: giá trị đảm bảo độ công bằng s = (1 − δ) · s + δ · s q=min                   1, )(  avgx x stt s (10) Công thức 10 bao gồm 2 phần: phần thứ nhất dùng cho việc điều khiển tắc nghẽn, giá trị số gói tin trung bình s càng gần đến ngưỡng t sẽ làm tăng xác suất q dẫn tới việc khả năng cờ h được bật tăng. Nếu s ≥t, q=1 thì cờ h sẽ được bật với xác suất bằng 1. Giá trị ngưỡng t được đặt nhỏ hơn khả năng tối đa mà hàng đợi có thể lưu trữ, để đảm bảo khả năng phục vụ kể cả trong trường hợp có lượng lớn gói tin trong một thời điểm ngắn. Ngoài ra còn có thêm giá trị δ trong việc tính toán giá trị s để tránh việc bật cờ h trong trường hợp tốc độ truy vấn thay đổi đột biến trong thời gian ngắn. Phần thứ hai được dùng cho mục đích đảm bảo công bằng: khi tốc độ truy vấn x của một nút nguồn nhỏ hơn tốc độ trung bình xavg của truy vấn đến mà nút đích nhận được thì q giảm. Ngược lại 30 nếu x > xavg thì q tăng, thể hiện việc nút nguồn sẽ bị giới hạn tốc độ nếu như chiếm phần lớn tài nguyên của nút đích. Giá trị γ xác định xem mức độ quan trọng của việc chia sẻ công bằng. Nếu γ = 0 sẽ bỏ qua việc đảm bảo công bằng. γ càng lớn thì độ lệch giữa x và xavg sẽ ảnh hưởng càng nhiều đến xác suất p. Một khi cờ h được bật nó sẽ không bị tắt trên suốt quãng đường truyền tới đích cuối cùng. Nút đích sao chép giá trị của h vào gói tin overlay-acknowledgement được gửi trả lại cho nút nguồn kèm với trả lời cho truy vấn. Nút nguồn: Một nút sẽ nhận được gói tin trả lời truy vấn với overlay-ack có cờ h. Nếu h tắt, tức là không có tắc nghẽn, nút tăng tốc độ truy vấn của nó như sau: x c xx : c+ là một hằng số dương nhỏ thể hiện mức độ một nút kiểm tra lượng băng thông còn có thể sử dụng khi nhận được thông báo không tắc nghẽn. Với cờ h được bật nút giảm tốc độ truy vấn của nó như sau:  cxx : với 0 < c- < 1 là hằng số, thể hiện mức độ một nút giảm tốc độ truy vấn khi có tắc nghẽn xuất hiện. Qua hai công thức trên có thể thấy ta tăng tốc độ truy vấn theo cấp số cộng và giảm theo cấp số nhân của một nút tương tự như trong TCP. Giá trị c+ và c- được chọn dựa vào RTT và khả năng phục vụ của mạng. Lựa chọn giá trị RTT: Mỗi nút lưu một giá trị RTT ước lượng cho các truy vấn: với mỗi truy vấn RTT được tính dựa trên thời gian gửi và thời gian nhận được phản hồi. Giá trị RTT được sử dụng cho toàn mạng nghĩa là không phụ thuộc vào đích đến của truy vấn. Do thông thường mỗi truy vấn đến một nút khác nhau trong mạng do đó giá trị RTT có sự thay đổi rất lớn. Nếu như sau thời gian RTT mà nút không nhận được trả lời cho truy vấn, một nút giảm tốc độ gửi truy vấn và gửi lại truy vấn. Do không phải loại bỏ gói tin cũng như cơ chế gọn nhẹ trong việc gửi phản hồi tình trạng tắc nghẽn cho nút nguồn nên phương pháp Marking có kết quả về 31 thông lượng đạt được cũng như thời gian trả lời truy vấn tốt hơn nhiều so với hai phương pháp CSCC và BPCC đã trình bày ở phần trước. 3.4. Phương pháp định tuyến thích nghi[5] Các phương pháp trình bày ở trên đều có chung nhược điểm là nếu trong mạng có tồn tại các nút có khả năng đáp ứng thấp hơn hẳn các nút khác sẽ gây giảm thông lượng đạt được trên toàn mạng. Để giải quyết vấn đề này, phương pháp định tuyến thích nghi được đề xuất. Đây cũng là phương pháp gần nhất với giải pháp được nêu ra trong tài liệu này. Trong phương pháp này, thay vì chọn nút gần với khóa cần tìm nhất, ta chọn ra k nút gần với khóa và theo dõi hiệu năng của các nút đó. Khi gửi đi một truy vấn nút nguồn kiểm tra gói tin trả lời chứa cờ báo hiệu tắc nghẽn h trong header để xác định khả năng sử dụng của mỗi đường định tuyến qua k nút trên. Để đơn giản ta xét trường hợp k=2, nghĩa là một nút có hai đường định tuyến qua hai nút lân cận. Giả sử ta có mạng DHT như sau: Hình 14: Mạng DHT với 8 nút. Bảng dưới thể hiện các đường định tuyến mà P0 có thể sử dụng khi chuyển tiếp gói tin. 32 Ví dụ với dòng thứ 3, với đích là nút P3 lựa chọn đầu tiên của P0 là chuyển qua nút P2 sử dụng đường dẫn l0-2 và lựa chọn thứ hai là qua P1 sử dụng đường dẫn l0-1. Nếu như nút đích lưu khóa cần tìm thì sẽ không có lựa chọn thứ hai (N/A). Nếu hai nút có cùng khoảng cách đến khóa cần tìm ta chọn nút bên trái làm lựa chọn đầu tiên. Định tuyến thích nghi: Mỗi nút ghi nhận giá trị của cờ h trong gói trả về trên cả hai đường định tuyến. Với mỗi cặp đường định tuyến mỗi nút duy trì k (ở đây k=2) giá trị xác suất đã quan sát được (op) của giá trị cờ h trong gói trả về như bảng dưới: Các giá trị xác suất này là thông tin duy nhất mà mỗi nút cần phải duy trì cho việc định tuyến chống tắc nghẽn. Mỗi nút sẽ chỉ phải lưu thêm O(log(n)) thông tin thêm do đó mạng vẫn sẽ giữ được khả năng mở rộng cao. Thay đổi lưu lượng: Để đạt được mục đích tăng thông lượng đạt được trên toàn mạng ta thực hiện việc chuyển lưu lượng chuyển qua các nút. Mỗi nút có thể sử dụng k đường định tuyến để chuyển tiếp gói tin (ở đây k=2). Như ở bảng trên mỗi nút lưu xác suất op1 và op2, giữa vào các xác suất này một nút sẽ chuyển lượng f1 lưu lượng qua đường định tuyến thứ nhất và f2 lưu lượng qua đường thứ hai (f1+f2=1). Một nút cập nhật giá trị f1 và f2 bằng cách sử dụng công thức: δ = (op1 – op2 ) · φ f1 = f1 − δ, f2 = f2 + δ fmin ≤ fi, fj ≤ 1 – fmin trong đó δ là lưu lượng chuyển từ đường định tuyến thứ nhất sang đường định tuyến thứ hai. Giá trị φ là một hằng số xác định tốc độ chuyển lưu lượng từ đường định tuyến này sang đường khác. Nếu δ có giá trị âm lưu lượng sẽ được chuyển ngược lại. Các giá trị f được có cận dưới được xác định bởi giá trị fmin như công thức ở trên nhằm đảm bảo luôn luôn nhận được phản hồi về khả năng của mỗi đường định tuyến. 33 Với trường hợp k>2 đầu tiên chúng ta tính toán giá trị opmean là giá trị trung bình của tất cả các opi. Sau đó chúng ta sẽ tăng giảm fi dựa vào việc so sánh các giá trị opi và opmean. Một nút cập nhật các giá trị op mỗi khi có truy vấn mới. Khi một nút chuyển tiếp các truy vấn từ các nút khác, nó sẽ chia lưu lượng theo các hướng dựa vào các tính toán về khả năng của từng đường định tuyến. Do đó trên mỗi nút truy vấn sẽ được định tuyến theo đường tối ưu, qua đó sẽ tăng thông lượng đạt được trên toàn mạng. Nhược điểm của phương pháp này là khi muốn tăng số lượng các đường định tuyến, ta phải tăng kích thước bảng định tuyến. Sẽ là rất tốn kém tài nguyên nếu như mỗi nút phải duy trì bảng theo dõi trạng thái của nhiều nút khác. Đồng thời việc bỏ phương pháp định tuyến tham lam sẽ làm tăng số lượng gói tin truyền trên mạng. 34 Chương 4. Điều khiển tắc nghẽn sử dụng phương pháp thay đổi bảng định tuyến 4.1. Đề xuất phương pháp Như các phân tích ở chương trước về các cơ chế điều khiển tắc nghẽn đã có, ta thấy còn một số nhược điểm cần khắc phục. Khóa luận này nhằm đưa ra một phương pháp điều khiển tắc nghẽn sử dụng việc thay đổi bảng định tuyến với mục đích chính là: điều khiển tắc nghẽn, giảm thiểu tối đa sự gia tăng số lượng nút phải đi qua với mỗi truy vấn so với phương pháp định tuyến tham lam đã có, đồng thời không làm ảnh hưởng quá nhiều đến mô hình hoạt động của mạng Chord, tránh phát sinh lãng phí tài nguyên cho việc duy trì thêm nhiều thông tin và các gói tin phụ phục vụ cho việc thay đổi định tuyến này. Để thực hiện các yêu cầu trên ta sẽ tìm cách tác động đến bảng định tuyến trên từng nút để khi có nút tắc nghẽn trên bảng định tuyến, nút đó sẽ được thay thế bằng nút lân cận. Để tối thiểu số lượng nút phải đi qua với mỗi truy vấn ta sẽ ưu tiến thay thế nút tắc nghẹn bằng nút lân cận nằm ngoài khoảng giữa nút truy vấn và nút đang bị tắc nghẽn. Để đơn giản khi ta chuyển định tuyến đến nút lân cận nếu như nút đó cũng gặp tình trạng tắc nghẽn thì ta tiếp tục chuyển đến nút lân cận tiếp theo. Ta chỉ giữ trong mỗi mục của bảng định tuyến hai giá trị của nút đích đó là nút đích ban đầu và nút đích được chuyển định tuyến tới tại thời điểm hiện tại. 4.2. Nội dung chi tiết Ta đi vào nội dung chi tiết của phương pháp đã được khái quát ở trên. Để đảm bảo việc điều khiển tắc nghẽn ta xét lần lượt các bước gặp phải khi cần giải quyết bài toán tắc nghẽn trên một hệ thống. 4.2.1. Phát hiện tắc nghẽn. Trên mỗi nút ta tính toán tốc độ xử lý gói tin tối đa mà nút đó có thể xử lý được, ta có thể tính toán giá trị đó thông qua tốc độ xử lý và đường truyền của máy. Việc tính toán này không nằm trong nội dung của khóa luận này. Ta quy định trên mỗi nút sẽ tồn tại hai giá trị giới hạn gọi là hardLimitRate và softLimitRate, lần lượt ứng với tốc độ xử lý tối đa của máy trên một đơn vị thời gian: limitRate và x*limitRate (với x là hằng số 0<x<1). Khi tốc độ gói tin tới nút chạm tới mức softLimitRate ta coi như máy đó bước vào giai đoạn “tắc nghẽn mềm” và sẽ tiến 35 hành các phương thức chống tắc nghẽn với nút đó. Khi tốc độ gói tin tới mức hardLimitRate thì lúc đó máy bị tắc nghẽn hoàn toàn. Việc tính toán giá trị của hằng số x sẽ ảnh hưởng đến độ “nhạy” của việc phát hiện tắc nghẽn, nếu x quá nhỏ các nút sẽ dễ dàng bị coi là tắc nghẽn dù vẫn còn khả năng phục vụ, nếu x quá lớn sẽ khiến cho việc xử lý tắc nghẽn trên nút diễn ra quá muộn dẫn tới trường hợp nút bị tắc nghẽn hoàn toàn kéo theo số lượng gói tin bị loại bỏ sẽ tăng. 4.2.2. Xử lý trong trường hợp có tắc nghẽn Khi phát hiện “tắc nghẽn mềm” trên nút, nếu nút nhận được một truy vấn tới thì hệ thống sẽ tiến hành các động thái sau:  Nút nhận đang bị tắc nghẽn sẽ gửi gói tin đến nút vừa gửi truy vấn đến nó thông báo mình bị tắc nghẽn. Nút nhận lưu lại danh sách các nút nó đã gửi thông báo tắc nghẽn đến.  Nút gửi truy vấn (có thể là nút vừa chuyển tiếp truy vấn) đến nút tắc nghẽn tiến hành thay đổi bảng định tuyến của nó: chuyển nút tắc nghẽn thành các nút lân cận không bị tắc nghẽn.  Truy vấn đến nút đang bị “tắc nghẽn mềm” vẫn tiếp tục được xử lý như bình thường Để tiến hành thay đổi bảng định tuyến đồng thời giữ lại giá trị nút đích ban đầu ta thay đổi bảng định tuyến (bảng finger) bằng cách thêm một cột lưu giữ giá trị định tuyến ban đầu. Khi đó bảng finger có dạng ví dụ như sau: Finger Active Route Origin Route 1 (Pi + 1) Pa Pa 2 (Pi + 2) Pb Pb 3 (Pi + 4) Pc Pc … … … M (Pi + 2 m ) Px Px Giả sử khi nút Pb bị tắc nghẽn ta sẽ thay đổi bảng finger thành: 36 Finger Active Route Origin Route 1 (Pi + 1) Pa Pa 2 (Pi + 2) Pt Pb 3 (Pi + 4) Pc Pc … … … M (Pi + 2 m ) Px Px Với Pt là successor của Pa. Việc chọn lựa nút thay thế là nút “xa hơn” nút nguồn so với nút ban đầu nhằm mục đích giảm thiểu số lượng nút mà gói tin phải chuyển qua. Nếu có một truy vấn tới Pi mà theo bảng finger gốc truy vấn đó sẽ chuyển qua nút Pb, thì trong thời điểm này truy vấn đó sẽ được chuyển tới:  Pt nếu khóa của truy vấn không nằm trong khoảng của Pb và Pt  Pb nếu khóa của truy vấn nằm trong khoảng Pb và Pt Trong trường hợp gói tin đến khi nút đang bị tắc nghẽn hoàn toàn (tốc độ gói tin đến vượt quá hardLimitRate) thì gói tin đó sẽ bị loại bỏ. 4.2.3. Xử lý khi hết tắc nghẽn Các nút trong hệ thống thực hiện việc kiểm tra định kỳ số lượng truy vấn tới để so sánh với các giới hạn đã có. Khi một nút đang từ trạng thái tắc nghẽn chuyển về trạng thái không tắc nghẽn (có lượng truy vấn tới trong một đơn vị thời gian nhỏ hơn softLimitRate), hệ thống sẽ tiến hành các bước sau:  Nút vừa ra khỏi trạng thái tắc nghẽn sẽ gửi thông báo về tình trạng của mình cho một số nút trong danh sách các nút nó đã gửi thông báo tắc nghẽn mà nó đã lưu lại như mô tả ở bước trên.  Nút nhận được thông báo hết tắc nghẽn sẽ thay đổi các mục có liên quan về nút vừa gửi thông báo trong bảng định tuyến về trạng thái như ban đầu. 37 Ví dụ như trường hợp trên khi nhận được thông báo hết tắc nghẽn từ Pb, thì Pi sẽ chuyển Pt lại thành Pi trong bảng định tuyến của nó. Số lượng nút sẽ nhận được thông báo khi nút đích hết tắc nghẽn cũng cần được quan tâm ở đây. Ta chỉ chọn ra một số lượng nhất định trong số các nút trong danh sách nút đã nhận được thông báo tắc nghẽn. Số lượng nút nhận được thông báo hết tắc nghẽn sẽ gián tiếp ảnh hưởng đến mức độ khôi phục lại tải sau tắc nghẽn của một nút, nếu ta đặt giá trị này quá thấp sẽ làm cho nút chậm trở lại trạng thái phục vụ bình thường, nếu như quá cao sẽ dễ làm cho nút bị tắc nghẽn trở lại. 4.3. Ví dụ minh họa Ta xét một mạng Chord đơn giản với không gian khóa 8 bit để minh họa cho giải pháp vừa đưa ra: Hình 15: Truy vấn thông thường trên mạng Chord (m=8). Ta thực hiện việc truy vấn khóa 54 trên nút P8. Hình 13 mô tả quá trình truy vấn thông thường theo đúng như thuật toán ban đầu của Chord. Khi đó bảng finger trên nút P8 có dạng: 38 Hình 16: Bảng định tuyến ban đầu của nút P8 Giả sử ta phát hiện tắc nghẽn tại nút P42, khi đó nút này sẽ thông báo cho nút nguồn thực hiện truy vấn (nút P8) về tình trạng của mình. Với giải pháp đã nêu ta thực hiện việc thay đổi bảng finger trên nút P8 như sau: Hình 17: Bảng định tuyến của nút P8 khi xảy ra tình trạng tắc nghẽn trên nút P42. Trên nút P8 tất cả các mục định tuyến có nút đích là P42 sẽ được thay đổi thành successor của P42 là P48. Khi đó nếu tiếp tục phát sinh truy vấn từ nút P8 mà truy vấn đó theo như bảng finger ban đầu sẽ phải đi qua nút P42 sẽ được thay đổi để đi qua nút P48. Hình 18: Truy vấn được thay đổi đường đi khi áp dụng giải pháp chống tắc nghẽn 39 Như hình trên truy vấn thay vì đi qua nút P42 đang tắc nghẽn sẽ được điều chỉnh đi qua nút P48. Số lượng nút mà truy vấn phải đi qua vẫn là 3 bằng với số lượng cần thiết trong trường hợp ban đầu. Giả sử nút P48 cũng xảy ra tình trạng tắc nghẽn, trên bảng định tuyến nút P8 nút P48 sẽ được thay thế bằng nút P51. Vẫn trên nút P8 giả sử ta cần truy vấn khóa 49. Do 49 thuộc khoảng [42,51) nên truy vấn sẽ phải đi qua nút P42 và được thực hiện như bình thường. Trong quá trình hoạt động giả sử một số nút có bảng định tuyến đi qua nút P42 đều phải thay đổi để qua nút khác thì khi nút P42 hết tắc nghẽn các nút đã thay đổi bảng định tuyến sẽ được lần lượt phục hồi về trạng thái ban đầu. 4.4. Nhận xét về phương pháp Ta có thể rút ra một số nhận xét về phương pháp đã nêu ở trên:  Ưu điểm: Có thể thấy đây là một phương pháp đơn giản nhằm điều khiển tắc nghẽn trong mạng Chord. Việc thay đổi định tuyến sẽ giúp tránh khỏi nút tắc nghẽn qua đó tăng khả năng thực hiện truy vấn thành công. Việc thay đổi chỉ tác động một số nhỏ các nút (nút tắc nghẽn và nút nguồn) do đó số lượng gói tin và thông tin phụ cần để thực hiện quá trình thay đổi và phục hồi là không lớn. Hơn nữa việc chọn lựa nút thay thế nút tắc nghẽn như đã trình bày ở trên không làm tăng số lượng nút mà mỗi một truy vấn phải đi qua.  Nhược điểm: Do cơ chế thay đổi nút định tuyến rất đơn giản nên chỉ có thể giới hạn các nút thay thế có định danh nằm trong vùng định danh lân cận với nút tắc nghẽn, mà không xét đến yếu tố là khả năng đáp ứng của nút vào việc quyết định lựa chọn nút thay thế. Ngoài ra việc chuyển đổi có thể tiếp tục nếu như nút đích mới cũng bị tắc nghẽn nên có thể gây đến tình trạng số lượng gói tin thông báo tăng rất cao trong trường hợp toàn bộ các nút trên mạng đều rơi vào trạng thái tắc nghẽn khi không có một cơ chế giới hạn số lần chuyển đổi bảng định tuyến. Hơn thế nữa có thể dễ nhận thấy việc thay đổi đường định tuyến của gói tin không thể giải quyết triệt để tắc nghẽn nếu như các nút trong mạng tiếp tục đẩy tốc độ truy vấn lên quá cao so với khả năng đáp ứng của mạng. Dù còn tồn tại một số nhược điểm tuy nhiên phương pháp đã nêu có thể giải quyết được vấn đề tắc nghẽn ở mức độ nhẹ đặc biệt là các trường hợp tắc nghẽn cục bộ, qua đó tăng khả năng đáp ứng của toàn mạng. Mặt khác phương pháp 40 này hoàn toàn có thể kết hợp với các phương pháp điều khiển tắc nghẽn sử dụng phương pháp điều chỉnh lưu lượng đã có nhằm loại bỏ khả năng sụp đổ của mạng khi xảy ra tắc nghẽn ở mức độ cao. 41 5. Mô phỏng và kết quả 5.1. Mô phỏng Để kiểm chứng khả năng hoạt động chính xác cũng như những lợi ích đạt được, ta sử dụng một hệ thống mô phỏng mạng Chord và tiến hành cài đặt giải pháp đã đề xuất. 5.1.1. Chương trình mô phỏng Tổng quan cấu trúc mạng mô phỏng: Do mô hình mạng trên thực tế là rất phức tạp và khó có khả năng thể hiện hoàn thiện trên một chương trình mô phỏng do đó ta chỉ xét đến tính chất đặc trưng có ảnh hưởng lớn tới một hệ thống mạng ngang hàng đó là độ trễ giữa các nút trong mạng. Mô hình mạng mô phỏng bao gồm:  Nhiều miền (area) chứa một số nút nhất định, các miền độc lập với nhau  Mỗi miền có một nút biên, nút biên này nối với các nút khác theo mô hình hình sao.  Các miền được nối với nhau thông qua liên kết giữa hai nút biên của miền. Liên kết này được đặt ngẫu nhiên một giá trị độ trễ gọi là độ trễ liên miền.  Liên kết giữa các nút trong miền và nút biên cũng được lấy ngẫu nhiên một giá trị độ trễ gọi là độ trễ nội miền. Độ trễ nội miền sẽ nhỏ hơn nhiều so với độ trễ liên miền. Hình 19: Mô hình mạng mô phỏng 42 Với mô hình trên ta có thể tính toán được độ trễ giữa hai nút trong mạng bằng cách cộng giá trị độ trễ nội miền và liên miền của hai nút đó (nếu hai nút cùng miền thì độ trễ liên miền bằng 0). Có thể thấy với cách xác định độ trễ như vậy thì giá trị độ trễ ở đây là cố định, trong khi với mạng thực tế độ trễ là một giá trị biến đổi liên tục, ngoài ra mạng thực tế còn phức tạp hơn nhiều với cấu trúc đa tầng, tuy nhiên mô hình này cũng đã đủ đáp ứng mục đích mô phỏng độ trễ đa dạng giữa các nút có trong mạng. Cấu trúc chương trình: Chương trình bao gồm các lớp quan trọng sau:  Lớp Areas: gồm các đối tượng chứa thông tin về các miền có trong mạng mô phỏng, chứa các hàm truy xuất thông tin về miền, các hàm tính toán độ trễ liên miền.  Lớp Node: chứa thông tin về các nút có trong mạng. Một nút có các giá trị quan trọng như: tên, định danh, định danh miền chứa nó, độ trễ nội miền. Mỗi nút khi đưa vào mạng sẽ lưu thêm thông tin về các định danh của các nút successor, predecessor và bảng định tuyến. Bảng định tuyến (bảng finger) chứa thông tin về các finger của nút – là các đối tượng thuộc lớp FingerEntry. Lớp Node ngoài các phương thức để thiết lập và truy xuất các thông tin kể trên còn một số phương thức quan trọng sau: o fixFingerTable: thực hiện quá trình ổn định mạng bằng cách kiểm tra và chỉnh sửa lại tất cả các finger của nút. o findSuccessor: đảm nhận việc tìm kiếm nút successor của một khóa cho trước. Phương thức trả lại giá trị là định danh của chính nút đó Hình 20: Mô hình lớp Node 43 nếu nó là successor của khóa, hoặc sẽ chuyển tiếp truy vấn cho một nút gần nhất sau khóa trong bảng định tuyến bằng cách tiếp tục gọi đệ quy phương thức findSuccessor trên nút đó.  Lớp FingerEntry gồm các đối tượng là các mục trong bảng định tuyến của mỗi nút. Mỗi nút chứa fingerTable là tập hợp các đối tượng FingerEntry tạo nên bảng định tuyến của nút đó.  Lớp Network: Là lớp chứa toàn bộ thông tin về mạng mô phỏng. Sau khi khởi tạo các đối tượng miền và nút được thêm vào đối tượng network để xây dựng mô hình mạng. Đối tượng này tiếp tục thực hiện tất cả các quá trình phân bố tài nguyên vào các nút, sinh ra các truy vấn và thực hiện các truy vấn này. Các phương thức quan trọng là: o nodeBirth, nodeDeath o fixFingerTables o getNodeDistance  Lớp InputGenerator: Là lớp đảm nhận việc sinh các dữ liệu cần thiết cho mạng hoạt động gồm thông tin về mạng, nút, vị trí của nút.  Lớp ResourceGen: Là lớp đảm nhận việc sinh tài nguyên và các truy vấn theo phân phối Zipf.  Lớp DoSchedule: Đảm nhận nhiệm vụ lên lịch và thực thi lần các thao tác của chương trình mô phỏng. Quá trình thực thi: Quá trình thực thi chương trình sẽ được phân ra làm nhiều bước và thực hiện tuần tự: đầu tiên là việc sinh ra các dữ liệu về mạng, tiếp đến là dữ liệu về tài nguyên và các truy vấn. Sau khi hoàn tất việc sinh các dữ liệu cần thiết, chương trình sẽ tiếp tục thực hiện các truy vấn, sau quá trình truy vấn các thông tin về mạng và kết quả thu được sẽ được tổng hợp và xuất ra file hoặc màn hình. Quá trình sinh dữ liệu: Ban đầu một đối tượng Network được khởi tạo. Tiếp đó các thông tin về các đối tượng miền và nút được tạo ra từ các hằng số như số lượng miền, số lượng nút… Thời gian, thứ tự thực hiện truy vấn cũng như khả năng chịu tải của nút sẽ được sinh ngẫu nhiên bằng quá trình Poisson. Các thông số này được lưu lại thành file. Sau đó các đối tượng Areas và Node được sinh ra từ các file thông số đó. Sau khi tất cả các nút được sinh bằng cách gọi phương thức nodeBirth, bảng định tuyến của tất cả các nút được tính toán dựa vào phương thức fixFingerTables. Tiếp đến lớp ResourceGen được sử dụng để tạo số lượng các tài nguyên, cũng như danh sách truy vấn tương ứng. 44 Quá trình thực thi: Chương trình khởi tạo đối tượng thuộc lớp DoSchedule ứng với các thông số đã khởi tạo trước đó. Các thao tác thực hiện được đọc từ file schedule, bắt đầu bằng việc gán các tài nguyên vào từng nút, tiếp đến thực hiện các truy vấn từ file danh sách đã tạo ra trước đó. Quá trình thực hiện truy vấn theo đúng thiết kế của Chord thông qua hàm findSuccessor của lớp Node. 5.1.2. Các thay đổi đã áp dụng Để cài đặt phương pháp điều khiển tắc nghẽn đã nêu, ta tiến hành một số thay đổi trên chương trình:  Cấu trúc chương trình: với lớp FingerEntry ta thêm biến lưu trữ thông tin về nút đích ban đầu.  Quá trình sinh dữ liệu: ngoài các dữ liệu ban đầu, ta sinh thêm một số dữ liệu như: giới hạn khả năng đáp ứng của các nút, thời gian thực hiện các truy vấn, thứ tự các nút thực hiện các truy vấn.  Quá trình thực thi: thay đổi chủ yếu được thực hiện trên lớp Node bao gồm các phương thức nhằm thực hiện: o Phát hiện tắc nghẽn: trên mỗi nút duy trì một vector có kích thước bằng giới hạn khả năng đáp ứng của nút, chứa thời gian các truy vấn tới nút. Dựa vào vector này ta tính toán được tại thời điểm có một truy vấn tới nút đang trong tình trạng không tắc nghẽn, tắc nghẽn mềm hay tắc nghẽn hoàn toàn. o Xử lý tắc nghẽn: Ta tạo ra phương thức tìm kiếm Successor cho một khóa mới. Nếu nút đang nhận truy vấn không bị tắc nghẽn việc thực hiện tương tự như phương thức findSuccessor ban đầu. Nếu nút xảy ra tắc nghẽn “mềm” sẽ tiến hành đặt lại fingerTable trên nút gửi truy vấn: chuyển tất cả các mục có đích là nút tắc nghẽn thành nút lân cận. Đồng thời lưu định danh nút gửi truy vấn vào danh sách các nút đã tiến hành thay đổi định tuyến: nodeChangedRoute. Với mỗi truy vấn sau đó nếu khóa cần tìm thuộc khoảng nút đích ban đầu và nút đích đã thay đổi ta thực hiện hàm tìm kiếm successor trên nút đích ban đầu, ngược lại ta thực hiện trên nút đích mới. Nếu nút tắc nghẽn hoàn toàn truy vấn sẽ bị hủy bỏ và ghi lại để tiện thực hiện việc nhận xét sau này. o Xử lý khi nút hết tắc nghẽn: Khi một nút hết tắc nghẽn, sẽ thay đổi lại bảng fingerTable của một số nút thuộc danh sách nodeChangedRoute. Số lượng nút thay đổi lại fingerTable được 45 tính bằng kích thước danh sách nodeChangedRoute nhân với một hằng số quy định trước. 5.2. Kết quả 5.2.1. So sánh với mô hình Chord chuẩn Để xác định hiệu quả của phương pháp đã đưa ra chúng ta tiến hành so sánh với mô hình Chord truyền thống. Với cùng một số bộ dữ liệu ta sẽ chạy lần lượt hai chương trình, trong đó một là chương trình truyền thống, hai là chương trình có áp dụng việc điều khiển tắc nghẽn. Việc đánh giá sẽ dựa trên số lượng gói tin bị loại bỏ và số gói tin trung bình phát sinh thêm với mỗi một truy vấn thành công trong toàn quá trình thực thi. Mạng được xây dựng với một số thông số cơ bản như sau: số lượng node: 1000, độ dài khóa là 16 bit, số lượng query 10000, giá trị lambda để sinh ngẫu nhiên khả năng chịu tải của các nút trong mạng là 10. Ta lần lượt thay đổi tốc độ truy vấn của các nút trên mạng và quan sát sự thay đổi về số lượng truy vấn bị loại và số gói tin phát sinh. Kết quả thu được được trình bày ở biểu đồ dưới. Cột x thể hiện tốc độ truy vấn tính bằng số truy vấn gửi đi mỗi ms, cột y thể hiện phần trăm số query bị loại bỏ do được gửi đến nút bị tắc nghẽn hoàn toàn. Đường đứt thể hiện trường hợp Chord truyền thống, đường liền thể hiện trường hợp sử dụng phương pháp điều khiển tắc nghẽn. Hình 21: Biểu đồ số lượng gói tin bị loại bỏ khi áp dụng và không áp dụng việc điều khiển tắc nghẽn Thông qua biểu đồ trên ta có thể thấy phương pháp điều khiển tắc nghẽn đưa ra có khả năng làm giảm số lượng truy vấn bị loại bỏ qua đó tăng khả năng phục vụ 46 của toàn hệ thống. Tuy nhiên cũng có thể thấy rõ ràng rằng phương pháp đưa ra không có khả năng ngăn chặn việc mạng sụp đổ khi chịu tải quá cao do không có phương pháp điều khiển tắc nghẽn đi kèm. Tiếp đến ta xét tới số lượng trung bình gói tin mà một truy vấn thành công sử dụng nhằm đánh giá mức độ ảnh hưởng của việc sử dụng phương pháp điều khiển tắc nghẽn đã nêu. Hình 22: Biểu đồ thể hiện số gói tin trung bình phải sử dụng với mỗi truy vấn thành công Ở biểu đồ trên cột x ứng với tốc độ truy vấn, cột y thể hiện số gói tin trung bình trên mỗi truy vấn thành công. Ta tính toán giá trị một cách tương đối bằng cách chia tổng số gói tin sử dụng cho số truy vấn thành công. Qua biểu đồ có thể thấy khi tốc độ truy vấn tăng, tương ứng với mức độ tắc nghẽn tăng, số lượng các gói tin điều khiển và gói tin phát sinh thêm khi thay đổi đường định tuyến sẽ tăng. Tuy nhiên mức độ tăng có thể thấy là không quá lớn, chủ yếu là do các gói tin điều khiển. Qua đó có thể thấy mức độ ảnh hưởng khi sử dụng phương pháp là không quá lớn so với phương pháp định tuyến tham lam của Chord truyền thống. 47 5.2.2. Đánh giá hiệu năng khi tiến hành tùy chỉnh các tham số và cải tiến phương pháp Đầu tiên ta xét tới tham số xác định khi nào xảy ra hiện tượng tắc nghẽn “mềm” tính bằng số phần trăm mức chịu tải của từng nút. Hình 23: Ảnh hưởng của việc thay đổi giá trị xác định mức độ tắc nghẽn mềm của nút Ở biểu đồ trục x thể hiện giá trị xác định tắc nghẽn đã để cập bên trên, cột kẻ chéo thể hiện số truy vấn bị loại bỏ do tắc nghẽn, cột đặc thể hiện số gói tin trung bình trên một truy vấn thành công. Hai cột cuối tương ứng với việc không sử dụng việc điều khiển tắc nghẽn. Có thể thấy nếu ta thay đổi giá trị xác định tắc nghẽn lên quá cao sẽ khiến cho nút phản ứng chậm khi bị tắc nghẽn dẫn tới số lượng gói tin bị loại bỏ cao, nếu đặt giá trị này quá thấp làm nút phản ứng quá sớm với việc tắc nghẽn, làm tăng đột biến số lượng gói tin, đặc biệt là gói tin điều khiển, khiến cho tải trên các nút ngày càng cao và sẽ làm cho tình trạng tắc nghẽn trầm trọng hơn. Giá trị phù hợp nhất nằm trong khoảng từ 50% đến 70%. Khi đó ta giảm thiểu được số lượng truy vấn bị loại bỏ mà không làm số lượng gói tin phát sinh thêm tăng cao. Một tham số quan trọng khác đã được nhắc đến ở phần trước là số lượng các nút sẽ được phục hồi lại bảng định tuyến khi nút đích hết tắc nghẽn. Ta tiến hành thay đổi tham số này và quan sát kết quả thu được 48 Hình 24: Ảnh hưởng của số lượng nút được khôi phục bảng định tuyến lên hiệu năng của hệ thống Qua biểu đồ trên có thể thấy số lượng gói tin bị loại bỏ do tắc nghẽn giảm khi ta tiến hành phục hồi chậm trên các nút hết tắc nghẽn. Tuy nhiên cũng phải xét đến ảnh hưởng khi một nút phục hồi quá chậm mà ở đây chương trình mô phỏng chưa thể hiện được. Ta tiếp tục xét đến một hình thức cải tiến của phương pháp đã đưa ra. Trên một nút ta duy trì thêm một giá trị xác định tắc nghẽn thứ hai nhỏ hơn giá trị xác định mức độ tắc nghẽn “mềm” đã có. Khi một nút có lượng truy vấn đến vượt qua giá trị tắc nghẽn thứ hai, nút đó sẽ thực hiện việc gửi yêu cầu thay đổi bảng định tuyến đến các nút ở “xa”, khi nút đạt đến mức tắc nghẽn “mềm” nó sẽ gửi yêu cầu thay đổi bảng định tuyến đến tất cả các nút. Việc xác định một nút xa hay gần được dựa trên ID của các nút đó. Dưới đây là một số kết quả thu được khi áp dụng phương pháp này Hình 25: Hiệu năng của hệ thống thay đổi khi cải tiến phương pháp điều khiển tắc nghẽn. 49 Hai cột đầu tiên mô tả phương pháp ban đầu với mức tắc nghẽn mềm được đặt là 75% khả năng của nút. Hai cột tiếp theo mô tả phương pháp cải tiến với giá trị tắc nghẽn mềm được đặt là 75%, giá trị tắc nghẽn thứ hai được đặt là 50%. Hai cột cuối mô tả phương pháp ban đầu với mức tắc nghẽn mềm được đặt là 50%. Qua biểu đồ có thể thấy khi sử dụng phương pháp cải tiến sẽ cho kết quả tốt hơn thể hiện bằng việc có số lượng truy vấn bị loại bỏ nhỏ nhất, đồng thời không sử dụng thêm quá nhiều các gói tin điều khiển như trường hợp sử dụng phương pháp ban đầu với mức tắc nghẽn mềm là 50%. 50 6. Kết luận và hướng phát triển Luận văn đã đề xuất một phương thức điều khiển tắc nghẽn dựa vào việc điều chỉnh định tuyến trong mạng ngang hàng có cấu trúc. Tuy còn dừng ở mức đơn giản tuy nhiên thông qua thực nghiệm trên chương trình mô phỏng đã chứng tỏ khả năng giải quyết tắc nghẽn cục bộ, qua đó tăng thông lượng đạt được trên mạng. Phương pháp đưa ra vẫn còn một số vấn đề cần phát triển thêm như việc tính toán các thông số phù hợp để đem lại hiệu quả cao nhất. Ngoài ra có thể kết hợp phương pháp đã nêu với một phương pháp điều khiển tắc nghẽn dựa trên điều khiển lưu lượng nhằm giải quyết triệt để vấn đề tắc nghẽn khi mạng chịu tải cao, tránh bị sụp đổ do tắc nghẽn mà vẫn đảm bảo được khả năng phục vụ của toàn mạng. 51 Reference 1. Stephanos Androutsellis-Theotokis and Diomidis Spinellis. “A survey of peer-to-peer content distribution technologies”. ACM Computing Surveys, 36(4):335–371, December 2004. 2. R. Huebsch, B. N. Chun, J. M. Hellerstein, B. T. Loo, P. Maniatis, T. Roscoe, S. Shenker, I. Stoica, and A. R. Yumerefendi. “The architecture of pier: an internet-scale query processor”. In CIDR, pages 28–43, 2005. 3. F. Klemm, Jean-Yves Le Boudec, Dejan Kosti´c, and Karl Aberer, “Handling Very Large Numbers Of Messages In Distributed Hash Tables”, Proceeding COMSNETS'09 Proceedings of the First international conference on COMmunication Systems And NETworks, 2009. 4. F. Klemm, J.-Y. Le Boudec, and K. Aberer. “Congestion control for distributed hash tables”, In The 5th IEEE International Symposium on Network Computing and Applications (IEEE NCA06), 2006. 5. F. Klemm, J.-Y. Le Boudec, D. Kostic, and K. Aberer. “Improving the throughput of distributed hash tables using congestion-aware routing”. In International Workshop on Peer-to-Peer Systems (IPTPS), 2007. Ecole Polytechnique F´ed´erale de Lausanne (EPFL), Lausanne, Switzerland 6. Rüdiger Schollmeier, “A Definition of Peer-to-Peer Networking for the Classification of Peer-to-Peer Architectures and Applications”, Proceedings of the First International Conference on Peer-to-Peer Computing, IEEE (2002). 7. Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan. Chord: “A scalable peer-to-peer lookup service for internet applications”. In Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols For Computer Communications (San Diego, California, United States). SIGCOMM „01. ACM, New York, NY, 149-160. 2001. 8. C. Tang and S. Dwarkadas. “Hybrid global-local indexing for efficient peer-to-peer information retrieval”. In NSDI, pages 211–224, 2004. 9.