Khóa luận Giải pháp khắc phục lỗi trong truyền thông multicast dựa trên nền mạng ngang hàng chord

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Duy Thăng GIẢI PHÁP KHẮC PHỤC LỖI TRONG TRUYỀN THÔNG MULTICAST DỰA TRÊN NỀN MẠNG NGANG HÀNG CHORD KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: Tiến sỹ Nguyễn Hoài Sơn HÀ NỘI - 2009 Lời cảm ơn Trước tiên, em muốn gửi lời cảm ơn sâu sắc nhất đến thầy giáo, tiến sĩ Nguyễn Hoài Sơn, người đã tận tình hướng dẫn em trong suốt quá trình nghiên cứu khóa luận tốt nghiệp. Em xin gửi lời cảm ơn chân thành và sâu sắc đến tất cả những thầy cô giáo của trường đại học Công nghệ, những kiến thức quý báu mà em nhận được từ thầy cô trong suốt bốn năm ngồi trên ghế nhà trường sẽ là hành trang tốt nhất giúp em vững bước trong sự nghiệp của bản thân. Tôi cũng xin gửi lời cảm ơn đến các anh chị K46, K48, K49, cùng tất cả bạn bè K50 của tôi, những người đã đồng hành cùng tôi trong suốt bốn năm học. Cuối cùng, xin gửi những lời tri ân đến bố mẹ và gia đình, những người thân yêu nhất của tôi. Sinh viên Phạm Duy Thăng Khóa luận tốt nghiệp 2 Phạm Duy Thăng Tóm tắt Hiện nay, nhu cầu truyền thông qua mạng internet ngày càng lớn, trong đó có các nhu cầu về truyền dữ liệu đa phương tiện như hình ảnh, âm thanh, phục vụ các mục đích truyền hình, hội nghị trực tuyến. Do đây là những dữ liệu có kích thước lớn, để giải quyết vấn đề băng thông, nên áp dụng mô hình truyền tin multicast. Tuy nhiên, hạ tầng mạng hiện nay chưa đủ để có thể triển khai các giao thức truyền multicast trên tầng mạng, bởi vậy đã có nhiều ý tưởng và thử nghiệm về truyền tin multicast trên tầng ứng dụng được đưa ra. Trong đó, giải pháp sử dụng mạng ngang hàng có cấu trúc để truyền tin multicast tỏ ra là một giải pháp ưu việt. Mạng ngang hàng Chord là một trong những mạng ngang hàng có cấu trúc có nhiều ưu điểm như tính ổn định, phân cấp, khả năng mở rộng, khả năng định tuyến, rất phù hợp cho mục đích truyền thông multicast. Tuy nhiên cấu trúc của mạng ngang hàng Chord cũng có một số điểm không phù hợp, dẫn đến vấn đề phục hồi cấu trúc cây multicast khi một node trong cây bị lỗi trong quá trình truyền tin multicast. Mục đích của khóa luận là đưa ra giao thức chống lỗi mới, bổ sung vào các giao thức đồng bộ sẵn có của mạng ngang hàng Chord, để tối ưu hóa việc chống lỗi trong truyền thông multicast. Nói cách khác là làm thế nào để giảm đến tối thiểu thời gian cần để khôi phục cấu trúc của cây multicast mỗi khi xảy ra lỗi ở các node tham gia, từ đó nâng cao hiệu năng và chất lượng của quá trình truyền thông multicast. Giao thức khắc phục lỗi sẽ được cài đặt vào ứng dụng truyền video sử dụng multicast trên nền mạng ngang hàng giao thức Chord. Khóa luận tốt nghiệp 3 Phạm Duy Thăng Mục lục Mục lục ............................................................................................................................................ 3  Danh mục hình vẽ ............................................................................................................................ 5  Mở đầu ............................................................................................................................................ 6  Chương 1 – Tổng quan về truyền tin multicast .......................................................................... 8  1.1.  Khái niệm về truyền tin multicast ....................................................................................... 8  1.2.  Truyền tin multicast tầng mạng (IP multicasting) ............................................................... 9  1.3. Truyền tin multicast tầng ứng dụng.................................................................................... 11  1.4.  Các mô hình truyền tin multicast tầng ứng dụng............................................................... 12  Chương 2 – Truyền tin multicast trên nền mạng ngang hàng có cấu trúc Chord ................ 14  2.1.  Khái niệm mạng ngang hàng............................................................................................. 14  2.1.1. Ưu điểm của mạng ngang hàng ................................................................................... 15  2.1.2. Mạng ngang hàng không có cấu trúc và mạng ngang hàng có cấu trúc ..................... 16  2.2.  Giao thức Chord ................................................................................................................ 22  2.2.1. Bảng băm phân tán ...................................................................................................... 22  2.2.2. Băm đồng nhất............................................................................................................. 23  2.2.3. Định tuyến thông báo .................................................................................................. 24  2.2.4. Khắc phục lỗi trong giao thức Chord .......................................................................... 26  2.3.  Truyền tin multicast trên nền mạng ngang hàng có cấu trúc Chord.................................. 29  Chương 3 – Khắc phục lỗi trong truyền thông multicast trên nền mạng ngang hàng giao thức Chord...................................................................................................................... 32  3.1.  Vấn đề lỗi và vai trò của việc khắc phục lỗi trong truyền thông multicast trên nền mạng Chord ................................................................................................................................. 32  3.2.  Giải pháp đề xuất............................................................................................................... 34  3.3.  Ba pha của giao thức khắc phục lỗi ................................................................................... 35  Khóa luận tốt nghiệp 4 Phạm Duy Thăng 3.3.1. Thông báo thông tin cây multicast .............................................................................. 35  3.3.2. Phát hiện lỗi và thông báo lỗi ...................................................................................... 37  3.3.3. Khắc phục lỗi............................................................................................................... 37  3.4.  Các vấn đề khác................................................................................................................. 38  Chương 4 – Kết quả thực nghiệm và đánh giá ......................................................................... 40  4.1.  Ứng dụng truyền video theo phương thức multicast dựa trên nền mạng ngang hàng Chord ........................................................................................................................................... 40  4.2.  Triển khai giao thức khắc phục lỗi ba pha cho ứng dụng truyền video multicast............. 43  4.3.  Mô hình thực nghiệm ........................................................................................................ 44  4.4.  Các kết quả thực nghiệm ................................................................................................... 45  Chương 5 – Kết quả và hướng phát triển ................................................................................. 46  5.1.  Đánh giá kết quả ................................................................................................................ 46  5.2.  Vấn đề còn tồn tại và hướng phát triển tiếp theo............................................................... 46  Tài liệu tham khảo ......................................................................................................................... 48  Khóa luận tốt nghiệp 5 Phạm Duy Thăng Danh mục hình vẽ Hình 1. Các phương thức truyền tin khác nhau broadcast, multicast và unicast............................. 8  Hình 2. Vai trò của các bộ định tuyến trong truyền tin multicast tầng mạng................................ 10  Hình 3. Truyền thông multicast tầng mạng và tầng ứng dụng ...................................................... 12  Hình 4. Mạng phủ 7 node (a) và cây multicast xây dựng trên mạng phủ (b) ................................ 13  Hình 5. Mô hình mạng ngang hàng ............................................................................................... 14  Hình 6. Một mạng ngang hàng không cấu trúc sử dụng một máy tính server .............................. 16  Hình 7. Mô hình chia sẻ file của Napster ...................................................................................... 17  Hình 8. Tìm kiếm dữ liệu chia sẻ trong Gnutella .......................................................................... 18  Hình 9. Mạng ngang hàng có cấu trúc thuộc nhánh các hệ thống phân tán trong các mô hình mạng ngang hàng............................................................................................................................. 1  Hình 10. Mạng ngang hàng có cấu trúc Chord dạng vòng tròn .................................................... 21  Hình 11. Vòng tròn Chord với 3 node và lưu trữ 4 khóa .............................................................. 24  Hình 12. Mạng Chord với các bảng finger .................................................................................... 25  Hình 13. Đoạn giả mã của các hàm trong quá trình đồng bộ ........................................................ 27  Hình 14. Sơ đồ một mạng Chord với 9 node tham gia.................................................................. 28  Hình 15. Truyền thông multicast trên mạng Chord....................................................................... 30  Hình 16. Sơ đồ một cây multicast ................................................................................................... 1  Hình 17. Giải pháp chống lỗi cho truyền tin multicast trên nền mạng Chord............................... 36  Hình 18. Kiến trúc chương trình phía máy chủ ............................................................................. 40  Hình 19. Kiến trúc chương trình phía máy khách ......................................................................... 41  Hình 20.Triển khai giao thức khắc phục lỗi ba pha....................................................................... 43  Khóa luận tốt nghiệp 6 Phạm Duy Thăng Mở đầu Hiện nay, khi mạng internet đang phát triển với tốc độ vũ bão, nhu cầu truyền thông dựa trên mạng internet ngày càng lớn. Một trong số những nhu cầu đó là truyền thông multicast, phục vụ cho việc truyền dữ liệu đa phương tiện như truyền hình trực tuyến, hội nghị trực tuyến,… Từ những năm 1990 đã có những nghiên cứu về việc bổ sung phần giao thức truyền multicast vào giao thức IP [14], và đã có những kết quả nhất định. Tuy nhiên, việc triển khai multicast trên giao thức IP gặp nhiều khó khăn do phải thay đổi hạ tầng mạng lớp ba. Trong những năm gần đây, công nghệ mạng ngang hàng đang trở thành mối quan tâm trong nhiều nghiên cứu về lĩnh vực internet, hứa hẹn giải pháp mới cho truyền thông multicast. So với các mô hình mạng khác, mô hình mạng ngang hàng có nhiều điểm lợi thế như sự phân tán, phân cấp, khả năng mở rộng, hiệu suất cao,… Các nghiên cứu mới hơn tập trung vào mạng ngang hàng có cấu trúc, ổn định hơn và tìm kiếm thông tin trong mạng hiệu quả hơn so với mạng ngang hàng không có cấu trúc. Một trong những giao thức mạng ngang hàng có cấu trúc mang nhiều ưu điểm phù hợp với truyền thông multicast như khả năng định tuyến tốt, hoạt động ổn định,… là giao thức Chord. Do đó, mạng ngang hàng sử dụng giao thức Chord sẽ là giải pháp hiệu quả để phục vụ truyền thông multicast trong khi chưa giải quyết được vấn đề truyền thông multicast ở tầng mạng. Tuy nhiên, giao thức Chord cũng có nhiều điểm không phù hợp cho việc truyền multicast như cấu trúc không ổn định, chống lỗi bằng các hàm chạy định kỳ, mỗi node nắm tương đối ít thông tin về các node khác, dẫn đến việc thiếu thông tin về cấu trúc cây multicast khi truyền multicast. Do đó, khi triển khai multicast trên mạng Chord, độ trễ cần thiết để khôi phục cấu trúc cây multicast khi một node lỗi cao. Khóa luận sẽ đề xuất một giải pháp chống lỗi, khắc phục được các nhược điểm của giao thức Chord khi áp dụng cho mục đích truyền thông multicast. Giải pháp sẽ chống lỗi sẽ được xây dựng theo hình thức phản ứng, có nghĩa là sẽ được kích hoạt ngay khi có lỗi xảy ra. Giải pháp chống lỗi cung cấp thêm thông tin về cây multicast cho mỗi node tham gia, đồng thời cung cấp cho các node khả năng phát hiện lỗi ở node cha trong cây Khóa luận tốt nghiệp 7 Phạm Duy Thăng multicast, từ đó gửi các thông báo lỗi cần thiết nhằm mục đích xây dựng cây multicast mới trong thời gian ngắn nhất. Khóa luận cũng sẽ cung cấp các kết quả thực nghiệm khi áp dụng giải pháp chống lỗi mới vào một ứng dụng truyền video theo hình thức truyền multicast dựa trên nền mạng ngang hàng giao thức Chord. Các kết quả này sẽ chứng minh tính hiệu quả của giái pháp. Dưới đây là tóm tắt khóa luận gồm 5 chương như sau: Chương 1: Giới thiệu tổng quan về mạng ngang hàng nói chung và phân tích các ưu điểm của mạng ngang hàng. Chương này cũng phân loại và so sánh giữa mạng ngang hàng không có cấu trúc và mạng ngang hàng có cấu trúc. Phần cuối của chương sẽ được giành để giới thiệu những khái niệm cơ bản của giao thức mạng ngang hàng Chord. Chương 2: Giới thiệu tổng quan về truyền thông multicast. Đầu tiên là những vấn đề cơ bản của multicast như cách thức truyền tin, so sánh với cách thức truyền tin unicast truyền thống. Tiếp đó, tôi sẽ trình bày về multicast trong tầng ứng dụng, so sánh với multicast ở tầng mạng. Cuối chương trình bày về truyền thông multicast trong mạng ngang hàng có cấu trúc. Chương 3: Trình bày cụ thể về vấn đề khắc phục lỗi trong truyền thông multicast trên nền mạng ngang hàng Chord, bao gồm những giao thức khắc phục lỗi cơ bản của mạng ngang hàng Chord, và những giao thức mới được đề ra để cải thiện hiệu năng truyền thông multicast trên nền mạng Chord. Chương 4: Trình bày kết quả thực nghiệm và đánh giá kết quả đó, so sánh với giao thức Chord truyền thống. Chương 5: Kết luận, nêu các vấn đề còn tồn tại và đề ra hướng phát triển tiếp theo. Khóa luận tốt nghiệp 8 Phạm Duy Thăng Chương 1 – Tổng quan về truyền tin multicast Truyền thông multicast là cách hữu hiệu để truyền dữ liệu đến một nhóm máy tính trên mạng Internet hoặc mạng nội bộ. Thay vì phải gửi thông tin tới từng máy đơn lẻ, thông tin sẽ được gửi cho cả nhóm multicast theo một sơ đồ gọi là cây multicast. 1.1. Khái niệm về truyền tin multicast Khi phân loại các phương pháp truyền tin trên mạng máy tính dựa vào số lượng máy nhận, ta có ba cách truyền tin như sau: Unicast: là hình thức truyền tin cơ bản của các giao thức mạng máy tính. Trong hình thức truyền tin này, một máy gửi tin đi tới chỉ một máy nhận xác định trước. Phương thức truyền tin này được sử dụng cho hầu hết các giao thức mạng máy tính từ tầng cho tới tầng ứng dụng như IP, TCP, UDP, HTTP, FTP,… Nhược điểm của phương pháp này là tốn băng thông trong trường hợp một nguồn gửi nhiều gói tin giống nhau tới nhiều máy nhận khác nhau. Broadcast: là hình thức truyền tin từ một điểm tới toàn mạng. Máy gửi gửi gói tin đi, và tất cả các máy khác trong mạng đều nhận được. Hình thức này thường được sử dụng khi một máy thiếu các thông tin về các máy khác trong mạng. Các ví dụ điển hình áp dụng hình thức truyền tin broadcast là giao thức phân giải địa chỉ ARP (tiếng Anh: Address Resolution Protocol) hoặc giao thức cấu hình động máy chủ DHCP (tiếng Anh: Dynamic Host Configuration Protocol). Hình 1. Các phương thức truyền tin khác nhau broadcast, multicast và unicast Multicast: là hình thức nằm giữa hai hình thức đã nêu. Trong hình thức truyền tin này, máy gửi gửi gói tin đi, và một số máy nhất định đã đăng ký trước sẽ được nhận gói Khóa luận tốt nghiệp 9 Phạm Duy Thăng tin đó. Nếu so sánh unicast với cuộc nói chuyện giữa hai người khi sử dụng một chương trình nhắn tin tức thi, thì multicast sẽ giống như cuộc hội nghị (tiếng Anh: conference) giữa nhiều người. Hình 1 minh họa cho các phương thức truyền tin unicast, broadcast và multicast. Có thể thấy multicast là phương pháp hữu hiệu khi một máy muốn gửi cùng một dữ liệu tới nhiều máy khác trong mạng. Trong trường hợp này, rõ ràng sử dụng multicast sẽ tiết kiệm băng thông trên đường truyền cũng như tài nguyên của máy gửi hơn so với sử dụng hình thức unicast. Khi sử dụng multicast, một cây multicast sẽ hình thành. Node gốc của cây là máy gửi tin, còn các node lá của cây là các máy nhận tin. Nhờ vào quá trình định tuyến, sẽ chỉ có một gói tin được gửi trên mỗi cạnh của cây, và nó sẽ được nhân bản tại các node dọc theo thân cây multicast. Các node trên thân cây có thể là bộ định tuyến (tiếng Anh: router) hoặc các máy đầu cuối, phụ thuộc vào các giao thức truyền multicast khác nhau. Tiếp theo đây, chúng ta sẽ lần lượt tìm hiểu về truyền tin multicast tầng mạng và truyền tin multicast tầng ứng dụng. 1.2. Truyền tin multicast tầng mạng (IP multicasting) Cuối những năm 80, Steve Deering làm việc trên một dự án trong đó có nhu cầu gửi một thông điệp từ một máy tính đến một nhóm các máy tính thông qua các giao thức lớp 3 (hay còn gọi là tầng mạng, tiếng Anh: network layer). Sau khi nghiên cứu vài giao thức định tuyến, Deering kết luận rằng chức năng của các giao thức định tuyến có thể mở rộng để hỗ trợ cơ chế multicast lớp 3. Định nghĩa cơ bản nhất của IP multicast là: IP multicast là cơ chế gửi một thông điệp từ một nguồn duy nhất đến một nhóm chọn lựa các địa chỉ đích thông qua một hạ tầng mạng lớp 3 trong một dòng dữ liệu. Hiện nay, IP multicast là một chuẩn mở của IETF (Internet Engineering Task Force), dùng để truyền dữ liệu tới nhiều máy nhận. Thành viên trong nhóm multicast có thể thay đổi. Người dùng có thể quyết định tham gia hoặc rời bỏ nhóm bất cứ lúc nào, và có thể là thành viên của nhiều nhóm multicast cùng lúc. Vai trò của máy tham gia trong quá trình truyền multicast cũng có thể khác nhau: cùng một máy có thể là nguồn gửi trong cây multicast này, nhưng lại là máy nhận trong cây multicast khác. Khóa luận tốt nghiệp 10 Phạm Duy Thăng Bộ định tuyến trong mô hình này phải có chức năng multicast. Khi nguồn multicast truyền thông điệp multicast, bộ định tuyến cục bộ sẽ gửi thông điệp đó đến các bộ định tuyến khác được kết nối với mạng có các thành viên của nhóm multicast. Như vậy, trong cây multicast của mô hình truyền tin multicast tầng mạng, các bộ định tuyến đóng vai trò là các node trong thân cây, có nhiệm vụ chuyển tiếp các gói tin multicast tới các máy nhận, là các node lá của cây multicast. Vai trò của bộ định tuyến được minh họa như trong hình 2. Hình 2. Vai trò của các bộ định tuyến trong truyền tin multicast tầng mạng IP multicast sử dụng cách đánh địa chỉ lớp D, là dạng đặc biệt của địa chỉ IP dành cho multicast. Tất cả các máy kết nối vào Internet phải có địa chỉ IP thuộc lớp A, lớp B, hoặc lớp C. Một máy có thể có một hoặc nhiều địa chỉ multicast lớp D tùy thuộc vào số nhóm multicast mà nó tham gia. Địa chỉ lớp D có độ dài là 32bit. 4 bit đầu tiên được dùng để xác định nó thuộc lớp D, 28 bit còn lại được dùng để xác định nhóm multicast. Một địa chỉ lớp D có thể so sánh với một kênh trên tivi. Khi bạn truy cập một địa chỉ lớp D, bạn sẽ nhận được tất cả thông tin được truyền multicast đến địa chỉ đó. Truyền tin multicast tầng mạng phát huy mạnh mẽ các ưu điểm của truyền thông multicast nói chung. Do các bộ định tuyến đóng vai trò các node trên thân cây multicast, Khóa luận tốt nghiệp 11 Phạm Duy Thăng các cạnh của cây cũng chính là các đường truyền vật lý, các gói tin multicast được nhân bản tại các bộ định tuyến làm cho số gói tin lưu thông trên đường truyền giảm tới mức tối thiểu. Do đó, hiệu suất truyền tin của mạng đạt mức tối đa. Với kiến trúc multicast tầng mạng đang sử dụng hiện nay, các phương thức xử lý đáp ứng các ràng buộc về chất lượng dịch vụ (tiếng Anh: Quality of service) vẫn là vấn đề phức tạp và chưa mang lại hiệu quả cao vì: • Khả năng thích ứng với sự tăng trưởng về số lượng trạng thái chuyển tiếp multicast tại các bộ định tuyến không tốt: các bộ định tuyến cần lưu giữ trạng thái theo nhóm. • Định tuyến phức tạp, mỗi cây chỉ kết hợp được với một nhóm đơn. Việc tạo và duy trì một cây multicast cho mỗi nhóm làm mất nhiều thời gian và tài nguyên, đặc biệt khi tính đến các ràng buộc về chất lượng dịch vụ. • Khi có quá nhiều kết nối hoặc một nút mạng không hoạt động sẽ gây ra rớt mạng và phải sửa chữa lại nhiều phần của cây. • Việc cân bằng tải và định tuyến lại cây chưa được đề cập thấu đáo. Hơn nữa, cho dù bộ định tuyến khắc phục được các vấn đề trên, thì chi phí để thay thế lại hạ tầng mạng lớp 3 đã được xây dựng là cực kỳ lớn. 1.3. Truyền tin multicast tầng ứng dụng Do nhu cầu sử dụng truyền thông multicast đang ngày càng lớn, trong khi giao thức IP multicast ở tầng mạng chưa đủ để đáp ứng, người ta đã đề ra các giao thức truyền thông multicast tầng ứng dụng. Khái niệm truyền tin multicast tầng ứng dụng được đưa ra để nói về lớp các giao thức multicast trong đó quá trình định tuyến được thực hiện ở tầng ứng dụng, sử dụng các giao thức khác đã có ở tầng mạng và tầng giao vận. Do đó, các giao thức truyền thông multicast tầng ứng dụng không yêu cầu phải thay đổi kiến trúc mạng đã đó. Thay vào đó, các giao thức này thực hiện các chức năng chuyển tiếp các thông điệp multicast tại các máy đầu cuối. Khóa luận tốt nghiệp 12 Phạm Duy Thăng Hình 3. Truyền thông multicast tầng mạng và tầng ứng dụng (Hình vuông là các router, hình tròn là các máy đầu cuối) Hình 10 thể hiện ý tưởng của truyền thông multicast tầng ứng dụng. Khi truyền multicast ở tầng ứng dụng, các gói tin không được nhân bản tại các bộ định tuyến giống như mô hình multicast truyền thống mà việc nhân bản gói tin sẽ được thực hiện tại các máy đầu cuối. Về mặt logic, các máy đầu cuối tạo nên một mạng phủ và giao thức truyền thông multicast phải xây dựng và duy trì việc truyền multicast trên mạng phủ này. Do truyền thông multicast tầng ứng dụng phải gửi các gói tin giống nhau trên cùng một kết nối, hiệu suất của mô hình này không thể tối ưu được bằng truyền thông multicast trên tầng mạng. Tuy nhiên, truyền tin multicast tầng multicast vẫn có khả năng giảm tải nhiều cho đường truyền và nguồn tin multicast. 1.4. Các mô hình truyền tin multicast tầng ứng dụng Dựa vào việc truyền tin multicast có yêu cầu mạng phủ trước hay không, người ta phân loại các giao thức truyền tin multicast tầng ứng dụng thành hai loại: mesh-first và tree-first. Trong mô hình truyền tin kiểu tree-first, các node khi tham gia vào cây multicast sẽ tự tìm cho mình một node cha từ các node thành viên trước đó của cây. Việc chọn node cha thường được thực hiện dựa trên một số tiêu chí như cân bằng băng thông giữa các node hoặc đảm bảo độ sâu của cây cân bằng giữa các nhánh. Ưu điểm của mô hình này là các node có thể chọn node cha, do đó có thể tránh được tình trạng một node nào đó phải Khóa luận tốt nghiệp 13 Phạm Duy Thăng chịu tải quá cao. Tuy nhiên nhược điểm của mô hình này là khi một node nào đó bị lỗi, việc khôi phục lại cây multicast để đảm bảo luồng dữ liệu cho các node con là tương đối khó khăn do mỗi node biết rất ít thông tin về các node khác trong mạng. Hình 4. Mạng phủ 7 node (a) và cây multicast xây dựng trên mạng phủ (b) Trong mô hình truyền tin kiểu tree-first, các node trước khi tham gia vào cây phải là thành viên của một mạng phủ nào đó, và giữa chúng đã tồn tại các liên kết với nhau dạng lưới. Sau đó, cây multicast sẽ được xây dựng dựa trên các liên kết của mạng phủ này. Ưu điểm của mô hình này là khả năng chịu lỗi cao do mỗi node tồn tại nhiều liên kết với các node khác trong mạng. Tuy nhiên nhược điểm của mô hình này là rất khó để thực hiện cân bằng tải và cân bằng độ trễ giữa các node do phụ thuộc vào kiến trúc mạng phủ. Khóa luận tốt nghiệp 14 Phạm Duy Thăng Chương 2 – Truyền tin multicast trên nền mạng ngang hàng có cấu trúc Chord 2.1. Khái niệm mạng ngang hàng Hiện nay, trong một số lĩnh vực mà giới hạn tài nguyên phần cứng không đủ để đáp ứng nhu cầu thực tế của người sử dụng, mô hình máy chủ - máy khách truyền thống đã tỏ rõ những nhược điểm của nó. Giải pháp đã và đang được nghiên cứu nhiều năm nay đó là thay thế mô hình máy chủ - máy khách bằng việc sử dụng mạng ngang hàng. Mạng ngang hàng (tiếng Anh: peer-to-peer network), còn gọi là mạng đồng đẳng, là một mạng máy tính trong đó hoạt động của mạng chủ yếu dựa vào khả năng tính toán và băng thông của các máy tham gia chứ không tập trung vào một số nhỏ các máy chủ trung tâm như các mạng thông thường [4]. Hình 5 minh họa cấu trúc của một mạng ngang hàng nhỏ. Hình 5. Mô hình mạng ngang hàng Mạng ngang hàng thường được sử dụng để kết nối các máy thông qua một lượng kết nối dạng ad hoc. Mạng ngang hàng có nhiều ứng dụng. Ứng dụng thường xuyên gặp nhất là chia sẻ tệp tin, tất cả các dạng như âm thanh, hình ảnh, dữ liệu,... hoặc để truyền dữ liệu thời gian thực như điện thoại VoIP. Khóa luận tốt nghiệp 15 Phạm Duy Thăng Một mạng ngang hàng đúng nghĩa không có khái niệm máy chủ và máy khách, nói cách khác, tất cả các máy tham gia đều bình đẳng và được gọi là peer, là một nút mạng đóng vai trò đồng thời là máy khách và máy chủ đối với các máy khác trong mạng. Một số mạng hay kênh như Napster, IRC (thuộc thế hệ thứ nhất) sử dụng mô hình máy chủ-máy khách cho một số tác vụ và mô hình ngang hàng cho những tác vụ khác. Ngược lại, các mạng như Gnutella hay Freenet (thế hệ thứ 2) sử dụng mô hình ngang hàng cho tất cả các tác vụ, nên các mạng này thường được xem như là mạng ngang hàng đúng nghĩa (thực ra Gnutella vẫn sử dụng một số máy chủ để giúp các máy trong mạng tìm kiếm địa chỉ IP của nhau). Vậy sử dụng mạng ngang hàng mang lại những lợi thế gì? Chúng ta sẽ xét đến các ưu điểm của mạng ngang hàng trong phần kế tiếp. 2.1.1. Ưu điểm của mạng ngang hàng  Một mục đích quan trọng của mạng đồng đằng là trong mạng tất cả các máy tham gia đều đóng góp tài nguyên, bao gồm băng thông, lưu trữ, và khả năng tính toán. Do đó khi càng có nhiều máy tham gia mạng thì khả năng tổng thể của hệ thống mạng càng lớn. Đây là các ưu điểm rất phù hợp để sử dụng cho mục đích truyền tin multicast. Ngược lại, trong cấu trúc máy chủ-máy khách, nếu số lượng máy chủ là cố định, thì khi số lượng máy khách tăng lên khả năng chuyển dữ liệu cho mỗi máy khách sẽ giảm xuống. Tính chất phân tán của mạng ngang hàng cũng giúp cho mạng hoạt động tốt khi một số máy gặp sự cố. Đối với cấu trúc tập trung, chỉ cần máy chủ gặp sự cố thì cả hệ thống sẽ ngưng trệ. Còn đối với mạng ngang hàng các máy tính có thể tham gia và rời khỏi mạng bất kì lúc nào mà mạng vẫn hoạt động bình thường, các máy tính còn lại vẫn có thể trao đổi thông tin và chia sẻ tài nguyên với nhau. Trong mạng ngang hàng dữ liệu trên các máy tính được đem ra chia sẻ nên một máy tính có thể thực hiện vai trò giống server để chia sẻ cho các máy tính khác. Các máy tính sau khi được chia sẻ dữ liệu cũng có thể tham gia chia sẻ cho các máy tính khác. Như vậy sẽ tăng số bản sao dữ liệu và giúp cho việc chia sẻ dữ liệu nhanh chóng. Khóa luận tốt nghiệp 16 Phạm Duy Thăng Đối với mạng Napster, thuật ngữ ngang hàng nói lên tính chất quan trọng của giao thức giao tiếp ngang hàng, còn thực ra thành công của Napster phải nhờ vào sự liên kết chặt chẽ giữa các máy tham gia với máy chủ trung tâm lưu trữ danh sách nội dung tệp trên các máy tham gia. Nhờ vậy việc tìm kiếm trở nên nhanh và hiệu quả hơn, tuy nhiên, đây cũng chính là điểm yếu dẫn đến các rắc rối pháp lý mà kết cục là sự sụp đổ của Napster. 2.1.2. Mạng ngang hàng không có  cấu trúc và mạng ngang hàng có cấu trúc  Mạng phủ ngang hàng bao gồm tất cả các nút mạng đại diện cho các máy tham gia và các liên kết giữa các nút mạng này. Một liên kết tồn tại giữa hai nút mạng khi một nút mạng biết vị trí của nút mạng kia. Dựa vào cấu trúc liên kết giữa các nút mạng trong mạng phủ ta có thể phân loại mạng ngang hàng thành 2 loại: có cấu trúc hay không cấu trúc. Mạng ngang hàng không cấu trúc Hình 6. Một mạng ngang hàng không cấu trúc sử dụng một máy tính server Hình 6 minh họa một mạng ngang hàng không có cấu trúc. Một mạng ngang hàng được gọi là mạng ngang hàng không cấu trúc khi các liên kết giữa các nút mạng trong mạng phủ được thiết lập ngẫu nhiên (tức là không theo qui luật nào). Những mạng như Khóa luận tốt nghiệp 17 Phạm Duy Thăng thế này dễ dàng được xây dựng vì một máy mới khi muốn tham gia mạng có thể lấy các liên kết có sẵn của một máy khác đang ở trong mạng và sau đó dần dần tự bản thân nó sẽ thêm vào các liên kết mới của riêng mình. Khi một máy muốn tìm một dữ liệu trong mạng ngang hàng không cấu trúc, yêu cầu tìm kiếm sẽ được truyền trên cả mạng để tìm ra càng nhiều máy chia sẻ càng tốt. Hình 7. Mô hình chia sẻ file của Napster Napster (hình 7) là mạng ngang hàng không cấu trúc đầu tiên thu hút được đông đảo người sử dụng trên mạng. Đây là sự kết hợp của một mạng ngang hàng peer to peer và một số máy chủ trung tâm để duy trì kết nối hệ thống và danh sách dữ liệu được chia sẻ trong mạng. Ngoài việc là một mạng peer to peer, Napster cũng giống như một mạng với các máy chủ. Chính các máy chủ này làm cho việc tìm kiếm dữ liệu và chia sẻ giữa các máy tính trong mạng tốt hơn, tạo nên mô hình mạng peer to peer đầu tiên cuốn hút Khóa luận tốt nghiệp 18 Phạm Duy Thăng được số lượng lớn người dùng với các dịch vụ chia sẻ file dữ liệu, file nhạc trên mạng Internet. Napster gồm 2 thành phần, thứ nhất là máy chủ trung tâm và thứ hai là các ứng dụng trên các máy tính kết nối với nhau. Một máy tính tham gia vào mạng sẽ kết nối với máy chủ trung tâm và đưa danh sách file chia sẻ trong máy tính lên máy chủ này. Những máy tính khi tìm kiếm dữ liệu sẽ tìm kiếm thông tin về từ khóa trên máy chủ trung tâm để biết máy tính nào hiện đang giữ file chia sẻ đó. Để tìm kiếm một file, một truy vấn sẽ được gửi đi tới máy chủ trung tâm cùng với từ khóa tìm kiếm. Máy chủ trung tâm sẽ tìm trong danh sách các file chia sẻ được đưa lên bởi các máy tính và trả về địa chỉ IP của máy tính lưu giữ file chia sẻ này. Sau đó sẽ là kết nối trực tiếp giữa máy tính yêu cầu và máy tính giữ file chia sẻ, dữ liệu được truyền giữa hai máy tính giống như trong một mạng ngang hàng. Hình 8. Tìm kiếm dữ liệu chia sẻ trong Gnutella Khóa luận tốt nghiệp 19 Phạm Duy Thăng Bên cạnh Napster, một mô hình mạng ngang hàng không cấu trúc khác cũng rất nổi tiếng là Gnutella. Gnutella là một mạng ngang hàng thuần và chủ yếu dựa trên mạng ngang hàng không có cấu trúc. Một phiên bản thương mại của Gnutella là Limewire. Các máy tính trong Gnutella được mô tả như là những “servent”, những thành viên trong mạng và được chia sẻ file trong mạng. Các máy tính khác có thể lấy được những file chia sẻ này. Việc tìm kiếm file trên mạng mô tả trong hình 8, khi một máy tính A tìm kiếm file X, nó sẽ gửi một truy vấn broadcast tới tất cả các máy tính nó biết, được coi là hàng xóm của nó. Truy vấn sau đó sẽ được chuyển dần qua các bước và tới được máy tính có chứa file X. Gnutella có mã nguồn mở và có giao thức mô tả rõ ràng trên mạng Internet, bất cứ ai quan tâm cũng có thế tìm hiểu và phát triển để tạo ra một mạng ngang hàng của riêng mình với các tính năng muốn có. Mạng ngang hàng có cấu trúc Hệ thống mạng ngang hàng không cấu trúc thể hiện nhược điểm: không có gì đảm bảo tìm kiếm sẽ thành công. Đối với tìm kiếm các dữ liệu phổ biến được chia sẻ trên nhiều máy, tỉ lệ thành công là khá cao, ngược lại, nếu dữ liệu chỉ được chia sẻ trên một vài máy thì xác suất tìm thấy là khá nhỏ. Tính chất này là hiển nhiên vì trong mạng ngang hàng không cấu trúc, không có bất kì mối tương quan nào giữa một máy và dữ liệu nó quản lý trong mạng, do đó yêu cầu tìm kiếm được chuyển một cách ngẫu nhiên đến một số máy trong mạng. Số lượng máy trong mạng càng lớn thì khả năng tìm thấy thông tin càng nhỏ. Một nhược điểm khác của hệ thống này là do không có định hướng, một yêu cầu tìm kiếm thường được chuyển cho một số lượng lớn máy trong mạng làm tiêu tốn một lượng lớn băng thông của mạng, dẫn đến hiệu quả tìm kiếm chung của mạng thấp. Khóa luận tốt nghiệp 20 Phạm Duy Thăng Mạng ngang hàng có cấu trúc khắc phục nhược điểm của mạng không cấu trúc bằng cách sử dụng hệ thống DHT (Bảng Băm Phân Tán, tiếng anh: Distributed Hash Table). Hệ thống này định nghĩa liên kết giữa các nút mạng trong mạng phủ theo một thuật toán cụ thể, đồng thời xác định chặt chẽ mỗi nút mạng sẽ chịu trách nhiệm đối với một phần dữ liệu chia sẻ trong mạng. Với cấu trúc này, khi một máy cần tìm một dữ liệu, nó chỉ cần áp dụng một giao thức chung để xác định nút mạng nào chịu trách nhiệm cho dữ liệu đó và sau đó liên lạc trực tiếp đến nút mạng đó để lấy kết quả. Hình 10 minh họa cho mạng ngang hàng có cấu trúc Chord. Các node liên kết với nhau theo một vòng tròn, và các thông điệp được gửi đi dựa vào đó. System P2P Decentraliz Centralized Unstructured Structured Hybrid CAN CHORD Gnutella KaZaA Hình 9. Mạng ngang hàng có cấu trúc thuộc nhánh các hệ thống phân tán trong các mô hình mạng ngang hàng Khóa luận tốt nghiệp 21 Phạm Duy Thăng Hình 10. Mạng ngang hàng có cấu trúc Chord dạng vòng tròn Trong mạng ngang hàng có cấu trúc, tài nguyên được phân bố một cách hợp lý để không có một máy tính nào lưu giữ quá nhiều dữ liệu dẫn đến quá tải thông tin định tuyến. Do mạng là có cấu trúc nên các thông điệp chuyển đi giữa các máy tính để duy trì mạng ngang hàng được giảm xuống mức tối thiểu. Băng thông của mạng được dành nhiều hơn cho việc chia sẻ tài nguyên. Việc tìm kiếm thông tin trong mạng ngang hàng có cấu trúc cũng nhanh hơn trong mạng không cấu trúc. Nếu như mạng không có cấu trúc các máy tính gửi thông điệp broadcast để tìm kiếm thông tin thì trong mạng có cấu trúc một máy tính chỉ cần gửi thông điệp tìm kiếm qua một số máy tính. Giao thức tìm kiếm chung trong mạng sẽ đảm bảo thông tin được tìm kiếm chính xác. Một số mạng ngang hàng có cấu trúc nổi tiếng bao gồm Chord, CAN, Kademlia, Pastry và Tapestry. Trong đó Chord và CAN được mô tả chi tiết, đã được mô phỏng và cho kết quả qua các bài báo. Phần tiếp theo sẽ trình bày chi tiết về giao thức mạng ngang hàng Chord. Khóa luận tốt nghiệp 22 Phạm Duy Thăng 2.2. Giao thức Chord Chord [9] là một trong những giao thức mạng ngang hàng có cấu trúc dùng bảng băm phân tán. Chord hiện đang được phát triển tại MIT. 2.2.1. Bảng băm phân tán  Bảng băm phân tán (Distributed hash tables) là một giải thuật cung cấp dịch vụ tìm kiếm tương tự cấu trúc dữ liệu bảng băm: Một cặp {khóa, giá trị} được lưu trữ vào trong bảng băm phân tán, và bất kỳ node tham gia nào cũng có thể đưa ra một khóa và dễ dàng truy vấn lấy giá trị tương ứng. Trách nhiệm duy trì ánh xạ từ không gian khóa vào giá trị được phân tán ra các node, nên khi thay đổi số node tham gia không ảnh hưởng đáng kể đến hoạt động của hệ thống. Điều này cho phép bảng băm phân tán có thể mở rộng ra một số lượng rất lớn các node tham gia mà vẫn quản lý được sự ra vào liên tục của các node, cũng như sự gián đoạn của một số node. Mỗi bảng băm phân tán đều cần có một không gian địa chỉ. Mỗi khóa sẽ lấy một giá trị từ không gian này. Kích thước không gian địa chỉ thường gặp nhất là 2160 (mỗi khóa là một số nhị phân 160 bit). Các node và dữ liệu sẽ được ánh xạ vào cùng một không gian địa chỉ sử dụng hàm băm SHA-1. Với mỗi node, hàm băm sẽ băm địa chỉ IP của node đó để thu được một khóa 160 bit, gọi là định danh node (node identifier hay nodeID). Định danh node được sử dụng để xác định vị trí của node trong bảng băm. Như vậy mỗi node sẽ có một địa chỉ duy nhất, và do không gian khóa là rất lớn nên cũng có thể xem là mỗi địa chỉ tương ứng với một node duy nhất. Đối với dữ liệu, mỗi file dữ liệu cũng được gắn với một định danh. Định danh của dữ liệu được băm từ tên file dữ liệu hoặc băm từ nội dung của file, là giá trị duy nhất trong không gian địa chỉ. Mỗi node sẽ quản lý một khoảng giá trị nhất định trong không gian địa chỉ. Dữ liệu được lưu ở node và được quản lý thông qua định danh. Khi một node muốn tìm kiếm một dữ liệu trong bảng băm phân tán, nó sẽ gửi truy vấn lần lượt qua các node khác. Nội dung truy vấn chính là định danh của dữ liệu. Khi một node lưu trữ dữ liệu có định danh trên nhận được truy vấn thì nó sẽ trả về dữ liệu yêu cầu. Như vậy, việc tìm kiếm dữ liệu trong bảng băm phân tán sẽ luôn thực hiện được. Tuy nhiên vấn đề đặt ra là khi số lượng node tham gia lớn thì việc tìm kiếm sẽ diễn ra như Khóa luận tốt nghiệp 23 Phạm Duy Thăng thế nào để đảm bảo tính hiệu quả về mặt thời gian và tính ổn định khi liên tục có các node gia nhập và rời khỏi bảng băm. 2.2.2. Băm đồng nhất  Hàm băm đồng nhất sử dụng SHA-1 để gán cho mỗi node và khóa một định danh (tiếng Anh: identifier) m-bit. Định danh của node là kết quả của hàm băm với đầu vào là địa chỉ IP của node trong khi định danh của khóa sinh ra từ việc băm khóa đó. Sau đây ta sẽ sử dụng thuật ngữ “khóa” cho cả khóa và ánh xạ của nó qua hàm băm, nghĩa của nó sẽ phụ thuộc vào ngữ cảnh sử dụng. Tất cả các định danh được xếp theo thứ tự vào vòng tròn định danh mô-đun 2m. Khóa k sẽ được gắn cho node đầu tiên có định danh bằng hoặc lớn hơn (định danh của) k trong không gian định danh. Node này được gọi là node kế tiếp (successor node) của k, ký hiệu là successor (k). Nếu các định danh được xếp vào vòng tròn các số từ 0 đến 2m – 1 thì successor (k) chính là node đầu tiên theo chiều kim đồng hồ tính từ k. Vòng tròn này gọi là vòng Chord (Chord ring). Hình 11 là vòng Chord với m = 3. Không gian khóa gồm có 8 số (từ 0 đến 7). Vòng Chord có tất cả 3 node tham gia, quản lý 4 khóa. Node kế tiếp của định danh 5 là node 0, do đó khóa 5 được lưu ở node 0. Tương tự với các khóa khác. Khóa luận tốt nghiệp 24 Phạm Duy Thăng Hình 11. Vòng tròn Chord với 3 node và lưu trữ 4 khóa 2.2.3. Định tuyến thông báo  Chúng ta có thể tìm kiếm đích đến cho các thông báo theo mô hình tìm kiếm tuyến tính: Mỗi thông điệp tìm kiếm sẽ được gửi lần lượt qua các node trên vòng tròn Chord cho đến khi tìm được dữ liệu cần tìm. Tuy nhiên, tìm kiếm tuyến tính yêu cầu một số lượng thông điệp tăng tuyến tính theo số lượng node. Và rõ ràng điều này làm giảm hiệu suất tìm kiếm của hệ thống khi số lượng node tăng. Để tăng tốc quá trình tìm kiếm, mạng Chord duy trì thêm thông tin định tuyến. Mỗi node n trong vòng Chord duy trì thêm một bảng định tuyến gồm m hàng (m là số bit để biểu diễn không gian khóa), gọi là bảng finger. Hàng thứ i trong bảng finger của node n xác định node đầu tiên s theo sau node n bởi ít nhất 2i-1 trong vòng tròn định danh, nghĩa là: s = successor (n + 2i-1). Node s này được gọi là finger thứ i của node n, và được ký hiệu là n.finger (i). Finger đầu tiên của node n chính là node kế tiếp của node n trong vòng Chord, tức là successor (n). Hình 12 minh họa việc bổ sung các bảng finger vào một mạng Chord trong trường hợp m = 3. Khóa luận tốt nghiệp 25 Phạm Duy Thăng Hình 12. Mạng Chord với các bảng finger Mô hình này có hai đặc điểm quan trọng. Thứ nhất, mỗi node chỉ lưu giữ thông tin về một số nhỏ các node khác, và có nhiều thông tin về các node ở gần hơn các node ở xa. Thứ hai, bảng finger của một node thường không chứa đủ thông tin để có thể ngay lập tức xác định được successor của một khóa k bất kỳ. Trong mô hình tìm kiếm mở rộng, khi một node n muốn xác định successor của khóa k, quá trình tìm kiếm sẽ được thực hiện như sau: - Node n tự kiểm tra khóa k, nếu nó thấy khóa k nằm trong khoảng không gian định danh từ n tới successor (n), thì việc tìm kiếm trả về successor (n). - Nếu khóa k nằm ngoài đoạn [n, successor (n)], n sẽ tìm trong bảng finger của mình một node n’ có định danh lớn nhất ngay trước k, sau đó chuyển tiếp truy vấn tìm kiếm cho n’. Quá trình trên được thực hiện liên tiếp cho tới khi xác định được successor (k). Bài báo đã chứng minh được rằng với mô hình tìm kiếm mở rộng, số node cần liên lạc để có thể tìm thấy một successor trong một mạng N-node là O(log N). Như vậy, so với mô hình tìm kiếm tuyến tính, mô hình tìm kiếm mở rộng tuy không cải thiện tính đúng Khóa luận tốt nghiệp 26 Phạm Duy Thăng đắn của các phép tìm kiếm nhưng rõ ràng mô hình tìm kiếm mở rộng tối ưu hơn rất nhiều về mặt thời gian. Nếu sử dụng mô hình tìm kiếm mở rộng, chúng ta có thể thấy được khả năng mở rộng của mạng Chord. 2.2.4. Khắc phục lỗi trong giao thức Chord  Trên thực tế hoạt động của mạng ngang hàng, có thể có các node mới tham gia vào mạng ngang hàng. Các node đang tham gia, nếu không còn nhu cầu nữa có thể rời khỏi mạng bất cứ lúc nào. Hơn nữa, các node tham gia mạng ngang hàng là các thực thể trên mạng máy tính, do đó có thể xảy ra lỗi tại các node này do nhiều nguyên nhân, khiến việc truyền tin bị gián đoạn. Kích thước mạng ngang hàng càng lớn thì số node tham gia mới, rời khỏi mạng hoặc xảy ra lỗi càng lớn. Giao thức Chord đã xử lý khá tốt các trường hợp trên, đảm bảo được tính ổn định của toàn mạng. Node mới tham gia và quá trình đồng bộ Để đảm bảo sự hoạt động ổn định của toàn bộ mạng khi có node mới tham gia vào mạng, hoặc khi có node rời khỏi mạng, Chord đã sử dụng một giao thức đồng bộ hoạt động định kỳ để cập nhật lại bảng finger và con trỏ successor của các node. Đoạn giả mã của các hàm tham gia và đồng bộ được thể hiện trên hình 13. Trước hết, chúng ta định nghĩa khái niệm node đứng trước (predecessor) của node n: nếu n là node kế tiếp của node p thì p là node đứng trước của node n, ký hiệu p = predecessor(n). Khi một node n là node đầu tiên tham gia mạng Chord, nó sẽ gọi hàm create() để khởi tạo vòng Chord mới. Nếu node n tham gia vào một mạng có sẵn, nó sẽ liên lạc với một node n’ trong mạng, sau đó yêu cầu n’ tìm giá trị successor(n). Khóa luận tốt nghiệp 27 Phạm Duy Thăng Hình 13. Đoạn giả mã của các hàm trong quá trình đồng bộ Định kỳ, node n phải gọi hàm stablilize() để thực hiện việc ổn định hóa. Hàm này có nhiệm vụ kiểm tra nếu tồn tại một node n’ nằm giữa n và successor(n) thì gán lại con trỏ successor của n là n’. Sau đó, n yêu cầu n’ kiểm tra và cập nhật n là predecessor của n’ thông qua hàm notify(). Khóa luận tốt nghiệp 28 Phạm Duy Thăng Định kỳ, node n cũng phải gọi hàm fix_fingers() để cập nhật lại bảng finger của mình. Cuối cùng, n sẽ gọi hàm check_predecessor() một cách định kỳ để kiển tra xem node đứng trước nó có bị gián đoạn hay không. Nếu có, n tự thiết lập lại con trỏ predecessor của nó thành con trỏ NULL. Như vậy, giao thức đồng bộ như trên đã giải quyết được các vấn đề node tham gia, node rời mạng, đảm bảo được sự hoạt động ổn định của toàn bộ mạng Chord. Node lỗi và danh sách successor Tính đúng đắn của giao thức Chord phụ thuộc vào điều kiện là mỗi node đều biết successor của nó. Tuy nhiên, điều kiện này có thể bị vi phạm nếu như có lỗi xảy ra ở các node. Hình 14. Sơ đồ một mạng Chord với 9 node tham gia Khóa luận tốt nghiệp 29 Phạm Duy Thăng Ví dụ, trên hình 14, nếu như các node 14, 21 và 32 xảy ra lỗi cùng một lúc và bị gián đoạn, node 8 không có khả năng nhận biết được rằng node 38 hiện là successor của nó, bởi vì không có bản ghi nào trong bảng finger của nó trỏ đến node 38. Như vậy, node 8 sẽ nhận sai successor, điều này ảnh hưởng trực tiếp đến tính đúng đắn của toàn bộ mạng Chord. Để tăng cường sự an toàn cho toàn bộ mạng Chord, giao thức Chord quy định thêm rằng mỗi node trong mạng phải duy trì một danh sách successor gồm r node, chứa r successor đầu tiên của node đó. Nếu successor trực tiếp (node kế tiếp) của một node không hoạt động, node đó có thể thay thế successor bởi bản ghi tiếp theo trong danh sách successor. Nếu xảy ra lỗi cùng lúc tại tất cả r successor thì mạng Chord có thể bị sụp đổ, tuy nhiên điều này rất khó có thể xảy ra nếu giá trị r được lựa chọn hợp lý. Như vậy, để duy trì danh sách successor, chúng ta cần sửa đổi lại hàm stablilize(). Node n sẽ đồng bộ danh sách successor của nó với node p là successor trực tiếp của n bằng cách copy toàn bộ danh sách successor của p, rồi loại đi bản ghi cuối cùng và thêm p vào đầu danh sách. Nếu node n nhận thấy successor trực tiếp của nó lỗi, n sẽ chọn ra node đầu tiên còn hoạt động tốt trong danh sách làm successor mới của mình, rồi lại đồng bộ danh sách successor với node này. Bài báo [9] cũng tính toán và chứng minh rằng với r = Ω(logN) thì hoạt động của mạng Chord trở nên tối ưu. 2.3. Truyền tin multicast trên nền mạng ngang hàng có cấu trúc Chord Chúng ta đã có những khái niệm cơ bản về giao thức mạng ngang hàng Chord và truyền thông multicast tầng ứng dụng. Chúng ta có thể thấy được rằng Chord là giao thức mạng ngang hàng ở tầng ứng dụng, có khả năng quản lý một số lượng lớn các node tham gia, có khả năng hoạt động được trong môi trường lỗi cao, tần suất vào/ra của các node lớn. Hơn nữa, bảng finger giúp cho giao thức Chord có được khả năng định tuyến rất tốt, với số bước để thực hiện việc định tuyến đạt mức tối thiểu. Do đó, có thể sử dụng mạng ngang hàng giao thức Chord làm mạng phủ để triển khai truyền thông multicast tầng ứng dụng. Khóa luận tốt nghiệp 30 Phạm Duy Thăng Hình 15. Truyền thông multicast trên mạng Chord Hình 15 minh họa quá trình truyền thông multicast dựa trên nền mạng ngang hàng sử dụng giao thức Chord. Trong truyền thông multicast, việc truyền tin sẽ thực hiện theo sơ đồ dạng cây, node nguồn sẽ truyền luồng dữ liệu cho một số node con. Đến lượt mình, mỗi node con lại truyền luồn dữ liệu đó cho một số node khác. Quá trình này được thực hiện liên tục cho tới khi tất cả các node tham gia vào nhóm multicast đều đã nhận được luồng dữ liệu. Khi đó, sơ đồ truyền dữ liệu qua các node được gọi là cây multicast. Dựa vào bảng finger của giao thức Chord, quá trình xây dựng cây multicast và truyền dữ liệu sẽ được thực hiện như sau: • Các node con của node nguồn chính là các bản ghi trong bảng finger của nó. Node nguồn chỉ trực tiếp truyền dữ liệu cho các node này, gọi là các node con cấp một. Khóa luận tốt nghiệp 31 Phạm Duy Thăng • Cùng với quá trình truyền dữ liệu, node nguồn sẽ phân công khoảng multicast cho mỗi node con cấp một. Khoảng multicast này là khoảng định danh bắt đầu từ node con đó tới ngay trước node con kế tiếp. Node con cấp một sẽ phải đảm bảo luồng dữ liệu multicast phải được phát đến tất cả các node có định danh nằm trong khoảng định danh mà mình phụ trách. • Đến lượt mình, các node con cấp một trực tiếp truyền dữ liệu multicast cho các bản ghi trong bảng finger của nó và có định danh nằm trong quản multicast mà nó quản lý. Chúng ta gọi các node này là node con cấp hai. • Mỗi node con cấp hai lại được giao quản lý một khoảng multicast nhỏ hơn, bắt đầu từ nó đến trước node con kế tiếp. • Quá trình này được thực hiện đến khi tất cả các node đều đã nhận được luồng multicast. Như vậy, chúng ta có thể thấy rằng nếu thực hiện multicast theo phương thức này, tất cả các node trong mạng Chord đều sẽ chắc chắn nhận được dữ liệu. Việc định tuyến hoàn toàn dựa vào bảng finger của giao thức Chord, do đó rất nhanh chóng, hiệu quả và dễ cài đặt. Nhược điểm của phương pháp này là cây multicast được xây dựng là cây lệch trái. Các node ở cuối vòng tròn Chord thường có độ sâu lớn hơn nhiều so với các node ở đầu vòng tròn. Do đó, độ trễ tương đối của dữ liệu nhận được giữa các node là không đều nhau. Tuy nhiên, nếu hàm băm được xây dựng tốt thì có thể làm giảm đáng kể sự chênh lệch trên. * * * Trong chương này, chúng ta đã có những khái niệm cơ bản nhất về truyền thông multicast và truyền thông multicast trên mạng ngang hàng Chord. Trong chương tiếp theo, tôi sẽ trình bày các vấn đề lỗi ảnh hưởng lớn đến sự ổn định và hiệu năng của quá trình truyền thông multicast trên nền mạng ngang hàng giao thức Chord. Tôi cũng sẽ đề ra giải pháp để khắc phục các vấn đề đó. Khóa luận tốt nghiệp 32 Phạm Duy Thăng Chương 3 – Khắc phục lỗi trong truyền thông multicast trên nền mạng ngang hàng giao thức Chord Phần đầu của chương này nêu những hạn chế khi sử dụng giao thức mạng ngang hàng Chord để triển khai truyền tin multicast và vấn đề lỗi trong truyền thông multicast dựa trên mạng Chord. Phần tiếp theo đề ra giao thức khắc phục lỗi ba pha, nhằm giải quyết vấn đề lỗi đã nêu, từ đó nâng cao độ ổn định và hiệu năng của toàn bộ quá trình truyền thông multicast. 3.1. Vấn đề lỗi và vai trò của việc khắc phục lỗi trong truyền thông multicast trên nền mạng Chord Với giao thức đồng bộ và danh sách successor được trình bày trong phần trước, chúng ta có thể thấy rằng mạng Chord có thể hoạt động ổn định trong môi trường có nhiều node mới tham gia cũng như rời mạng, đồng thời khả năng chịu lỗi của mạng Chord cũng tương đối cao. Như vậy, ta có thể thấy khi áp dụng mạng ngang hàng Chord để thực hiện truyền thông multicast sẽ có nhiều lợi thế. Tuy nhiên, giao thức Chord chưa có phương pháp nào để giải quyết vấn đề chính khi truyền thông multicast. Trong quá trình truyền thông multicast theo sơ đồ cây, một cây multicast được xây dựng. Theo đó, mỗi node sẽ chỉ truyền luồng dữ liệu cho một số node con nhất định, và các node con này lại truyền luồng dữ liệu con đó cho các node khác. Mỗi node N (trừ các node lá) sẽ là nguồn của một cây multicast con, và chịu trách nhiệm đảm bảo luồng dữ liệu phải được truyền đến tất cả các node trong cây con đó. Tuy nhiên, nếu node N bị lỗi, cần phải có một cơ chế để thay thế node N, đảm bảo quá trình nhận dữ liệu của toàn bộ các node thuộc cây con N (các node P, Q trên hình 16). Khóa luận tốt nghiệp 33 Phạm Duy Thăng Trong các bài báo về multicast [6, 7, 8, 9, 10, 11], đã có các phương pháp khắc phục được đưa ra, nhằm tìm node cha mới cho các node con của node bị lỗi. Tuy nhiên, các phương pháp đó không phù hợp với mô hình truyền thông multicast dựa trên mạng ngang hàng Chord. Thứ nhất, cây multicast xây dựng dựa trên nền tảng mạng Chord là cây multicast có cấu trúc động. Do mạng ngang hàng Chord liên tục có các node mới tham gia vào mạng và các node rời khỏi mạng, bảng finger và danh sách successor của các node trong mạng liên tục thay đổi. Chỉ một node vào hoặc ra khỏi mạng đã có thể làm ảnh hưởng đến bảng finger của rất nhiều node. Do đó, cấu trúc của cây multicast xây dựng trên mạng Chord liên tục bị xáo trộn. Vai trò của các node trong cây thường xuyên thay đổi. Do đó nếu một node lưu thông tin của node khác nhằm thực hiện việc thay thế cho node cha bị lỗi, thì thông tin đó sẽ rất nhanh chóng bị lỗi thời. Thứ hai, do đặc thù của giao thức Chord, mỗi node nắm được rất ít thông tin về cấu trúc của toàn bộ cây multicast. Do quá trình truyền dữ liệu được định tuyến dựa vào bảng finger, mỗi node chỉ biết được các node con của nó trong cây multicast. Các node không I F N M P Q Hình 16. Sơ đồ một cây multicast Khóa luận tốt nghiệp 34 Phạm Duy Thăng thể biết được node nào thực sự là node cha của nó do cấu trúc cây multicast liên tục thay đổi. Chord cũng chưa cung cấp phương thức nào để một node lưu thông tin node cha hiện thời của nó. Trong các nghiên cứu về multicast tầng ứng dụng trước đây, một phương pháp thường được đề ra để giải quyết node cha lỗi là các node con tìm một node cùng cấp với node cha để thay thế khi node cha xảy ra lỗi. Tuy nhiên trong mạng Chord, việc tìm một node như vậy gần như là không thể do chính node cha cũng không có thông tin nào về các node cùng cấp với mình trong cây multicast. Ngoài ra, việc sử dụng mạng Chord để phục vụ truyền thông multicast còn có một điểm hạn chế khác. Các phương thức đồng bộ và khắc phục lỗi của giao thức Chord đều là các hàm hoạt động định kỳ. Như vậy có nghĩa là nếu có lỗi xảy ra tại một node, lỗi chỉ có thể được phát hiện ra bởi node successor và node predecessor của node lỗi thông qua các hàm kiểm tra định kỳ. Tiếp đó, các node khác cũng sẽ dần nhận được thông tin về node lỗi sau khi hàm fix_finger(), cũng là một hàm được gọi định kỳ, thực hiện xong. Ta có thể thấy độ trễ để một lỗi được khôi phục sẽ là rất lớn, và điều này là khó chấp nhận đối với các ứng dụng truyền multicast. 3.2. Giải pháp đề xuất Để có thể đưa ra được giao thức khắc phục lỗi hiệu quả cho truyền multicast trên nền mạng Chord, chúng ta cần tập trung giải quyết các vấn đề đã nêu ở phần trước. Giao thức đưa ra phải khắc phục được vấn đề độ trễ của các phương thức đồng bộ định kỳ trong mạng Chord. Để làm được điều đó, giao thức đưa ra phải đảm bảo tính phản ứng, có nghĩa là các hàm giải quyết vấn đề phải được gọi sớm nhất có thể sau khi có lỗi xảy ra. Như vậy có nghĩa là phải có cơ chế phát hiện lỗi tốt hơn. Ta có thể thấy rằng trong quá trình truyền multicast, luồn dữ liệu được truyền liên tục từ node cha sang node con. Do đó, nếu xảy ra lỗi ở node cha, node con có thể nhận biết được do luồng dữ liệu bị gián đoạn. Từ đó, có thể thấy rằng vai trò phát hiện lỗi nên thuộc về các node con. Nói cách khác, mỗi node sẽ có trách nhiệm giám sát node cha của mình, nếu luồng dữ liệu bị gián đoạn thì sẽ thực hiện kiểm tra tình trạng của node cha. Giao thức đưa ra cũng cần phải cung cấp cho mỗi node thêm thông tin về các node khác trong mạng. Khóa luận tốt nghiệp 35 Phạm Duy Thăng Mặt khác, ta thấy rằng tại mỗi node N, dữ liệu mà nó nhận được do node cha cung cấp. Khoảng multicast mà N chịu trách nhiệm cũng do node cha của N phân phối, và là một phần của khoảng multicast của node cha. Do đó nếu node N lỗi thì node cha của phải có trách nhiệm với khoảng multicast của N. Tóm lại, để có thể khắc phục các vấn đề lỗi xảy ra ở một node N, cần phải có sự tham gia cả node cha và các node con của node N. Các node con của N sẽ được cung cấp thông tin về node cha của N. Nếu các node con nhận thấy rằng có lỗi xảy ra ở node N, chúng sẽ thông báo cho node cha của N. Đến lượt mình, node cha của N sẽ tìm một node khác thay thế cho N, chịu trách nhiệm cho khoảng multicast của N. Chúng ta sẽ gọi đây là giao thức khắc phục lỗi ba pha. 3.3. Ba pha của giao thức khắc phục lỗi Từ ý tưởng trên, tôi đề ra giao thức khắc phục lỗi gồm ba pha như sau: • Pha thứ nhất: Thông báo thông tin cây multicast • Pha thứ hai: Phát hiện lỗi và thông báo lỗi • Pha thứ ba: Khắc phục lỗi Sau đây chúng ta sẽ đi vào chi tiết nội dung của các pha của giao thức. Quy ước: Trong cây multicast, khi một node F truyền dữ liệu cho node N thì node F được gọi là node cha của node N. Nếu node G là node cha của node F thì G được gọi là node ông của node N. 3.3.1. Thông báo thông tin cây multicast  Trong pha này, mỗi node F có trách nhiệm thông báo cho các node con về node cha của F. Ví dụ trong hình 17, node F có trách nhiệm phải thông báo cho các node con N, M và P thông tin về node F. Các node N, M và P sẽ lưu thông tin đó lại. Chi tiết giao thức như sau: • Mỗi node có một thuộc tính father, dùng để lưu thông tin node cha, và thuộc tính grandfather, dùng để lưu thông tin node ông. Khóa luận tốt nghiệp 36 Phạm Duy Thăng • Mỗi khi node F nhận được luồng multicast mới, nó thay đổi thuộc tính father, đồng thời gửi thông điệp cho các node con, yêu cầu các node con thay đổi thuộc tính grandfather. • Mỗi khi node F thay đổi một bản ghi trong bảng finger, nó cũng gửi yêu cầu node con mới (được trỏ bởi bản ghi mới thay đổi) cập nhật lại thuộc tính grandfather thành node cha của node F. • Mỗi node khi nhận được thông tin về node ông của mình thì lưu thông tin này vào thuộc tính granfather. Như vậy, nhờ pha thông báo thông tin cây multicast, mỗi node sẽ có thêm thông tin về cấu trúc của cây. Hình 17. Giải pháp chống lỗi cho truyền tin multicast trên nền mạng Chord Khóa luận tốt nghiệp 37 Phạm Duy Thăng 3.3.2. Phát hiện lỗi và thông báo lỗi  Pha này nhằm xây dựng tính phản ứng cho giao thức khắc phục lỗi. Phương pháp phát hiện lỗi được xây dựng dựa trên tính chất của quá trình truyền thông multicast: luồng dữ liệu thường được truyền liên tục. Do đó, nếu luồng dữ liệu bị gián đoạn, node nhận dữ liệu có thể nghi ngờ rằng có lỗi xảy ra tại node cha của nó. Trong pha này, mỗi node có trách nhiệm phát hiện sớm nhất lỗi xảy ra (nếu có) ở node cha. Lỗi được phát hiện sẽ được thông báo cho node ông của nó, là node có trách nhiệm xử lý lỗi. Chi tiết giao thức như sau: • Trong quá trình truyền thông multicast, nếu sau một khoảng thời gian delta, node con N không nhận được dữ liệu từ node cha F, N sẽ thực hiện việc gửi thông điệp kiểm tra tới F để xác định xem có phải node F gặp lỗi hay không. Khoảng thời gian delta trên phụ thuộc vào mục đích sử dụng của hệ thống multicast (luồng dữ liệu là liên tục hay gián đoạn và mức độ gián đoạn). • Nếu như không có lỗi xảy ra tại node F, node này khi nhận được thông điệp kiểm tra sẽ gửi thông điệp trả lời, nhằm mục đích thông báo cho node con rằng F vẫn còn hoạt động. • Nếu sau một khoảng thời gian chờ đợi, node N không nhận được thông điệp trả lời, nó sẽ kết luận là node cha F gặp lỗi. Trong trường hợp này, N sẽ gửi một thông điệp thông báo lỗi cho node ông của N (node cha của node F). Nội dung thông điệp thông báo lỗi có chứa thông tin về node F. Ví dụ như trên hình 16, trong quá trình node F truyền dữ liệu cho node N, nếu N nhận thấy có lỗi ở node F, node N sẽ thông báo lỗi này cho node ông của nó là node G. 3.3.3. Khắc phục lỗi  Nếu một node G nhận được thông báo lỗi chứa thông tin node F, nó sẽ kiểm tra xem F có phải là một node con của nó hay không. Nói cách khác, G sẽ kiểm tra bảng finger của nó, xem F có phải là một bản ghi trong bảng finger hay không. Nếu đúng, G sẽ tiến hành việc cập nhật đột xuất bản ghi đó bằng cách gọi hàm fix_finger(). Nếu không phải, G sẽ bỏ qua thông điệp. Khóa luận tốt nghiệp 38 Phạm Duy Thăng Như vậy, nếu node F lỗi, có thể sẽ có nhiều hơn một thông điệp thông báo lỗi từ các node con của F gửi cho G. Tuy nhiên, chỉ có thông báo đầu tiên được xử lý, vì khi các thông điệp sau đến, lỗi đã được xử lý rồi. Việc cập nhật lại bảng finger như trên sẽ đảm bảo được việc truyền multicast trong khoảng multicast mà F phụ trách. Khoảng multicast này sẽ được bàn giao lại cho node F’ được trỏ bởi bản ghi mới, node này sẽ là node thay thế cho node F lỗi. Node F’ sẽ dựa vào bảng finger của mình để thực hiện việc truyền multicast cho khoảng đó (cấu trúc cây multicast có thể thay đổi do bảng finger của F’ khác bảng finger của F). Như vậy, chúng ta có thể thấy rằng giao thức khắc phục lỗi ba pha đã giải quyết được các vấn đề đã nêu trong mục 3.1. Giao thức khắc phục lỗi được thiết kế theo hình thức phản ứng, nhằm giải quyết sớm nhất lỗi xuất hiện, đảm bảo sự ổn định cho quá trình truyền thông multicast. Giao thức khắc phục lỗi cũng không làm ảnh hưởng nhiều đến bằng thông chung của toàn mạng do số lượng gói tin kiểm soát ít. Giao thức khắc phục lỗi ba pha dễ cài đặt, do không thay đổi nhiều đến giao thức Chord cũng như giao thức truyền multicast trên nền mạng ngang hàng Chord. 3.4. Các vấn đề khác Giao thức khắc phục lỗi ba pha đã nêu đã giải quyết thành công các vấn đề đã nêu ở mục 3.1. Tuy nhiên, giao thức này lại mở ra một vấn đề mới. Ý tưởng của giải pháp đưa ra là sử dụng các node con của một node N để phát hiện lỗi xảy ra ở node N, rồi thông báo cho node cha của N để xử lý. Giải pháp đưa ra đã thực hiện tốt ý tưởng. Tuy nhiên, trong giải pháp chưa đưa ra được hướng giải quyết cho trường hợp có lỗi xảy ra ở cả node N và node cha của nó. Vấn đề này có thể giải quyết theo phương thức sau: • Nếu node N sau khi thông báo lỗi cho node ông thì lập tức liên lạc với finger xa nhất còn hoạt động trong bảng finger của mình, đăng ký làm node con tạm thời của finger đó. • Nếu mỗi node khi nhận được một yêu cầu làm node con tạm thời từ một node khác, thì thêm node yêu cầu vào danh sách node con tạm thời. Trong quá trình truyền tin multicast, sau khi truyền tin cho các node con trong bảng Khóa luận tốt nghiệp 39 Phạm Duy Thăng finger xong thì tiến hành truyền tin cho các node con trong danh sách node con tạm thời. • Nếu sau khi node N đăng ký làm node con tạm thời của một node F’, node N lại nhận được một luồng multicast khác từ node F’’ khác F’, N gửi thông điệp thông báo cho N’ ngừng gửi luồng multicast, đồng thời thay đổi thuộc tính father thành F’’ Khóa luận tốt nghiệp 40 Phạm Duy Thăng Chương 4 – Kết quả thực nghiệm và đánh giá Trong chương này, giao thức khắc phục lỗi ba pha đã đề ra sẽ được áp dụng vào một ứng dụng cụ thể: ứng dụng truyền video sử dụng multicast trên nền mạng ngang hàng giao thức Chord. Chúng ta sẽ xem xét xem tỷ lệ thành công của giải pháp chống lỗi là bao nhiêu. Đồng thời, chúng ta cũng sẽ có những kết quả đánh giá hiệu năng của giải pháp chống lỗi dựa trên việc đo đạc các thông số liên quan đến độ trễ và số gói tin điều khiển. 4.1. Ứng dụng truyền video theo phương thức multicast dựa trên nền mạng ngang hàng Chord Ứng dụng truyền video được sử dụng trong khóa luận là ứng dụng truyền multicast theo phương thức multicast dựa trên nền mạng ngang hàng Chord. Ứng dụng gồm hai phần: phần máy chủ giành cho nguồn phát video và phần máy khách giành cho các node nhận. Tất cả các node nguồn và node nhận đều là các node tham gia vào một mạng ngang hàng Chord. Trên mỗi node, cổng truyền và nhận gói tin điều khiển của giao thức Chord và cổng truyền/nhận gói tin video multicast là các cổng khác nhau. Việc truyền các gói tin điều khiển của giao thức Chord được thực hiện trên nền giao thức giao vận UDP có bổ sung các cơ chế truyền tin tin cậy, trong khi việc truyền các gói tin video multicast sử dụng giao thức UDP đơn thuần, không có cơ chế truyền tin tin cậy. Hình 18. Kiến trúc chương trình phía máy chủ Khóa luận tốt nghiệp 41 Phạm Duy Thăng Hình 19. Kiến trúc chương trình phía máy khách Việc triển khai truyền video multicast sử dụng bảng finger của các node để định tuyến, tuy nhiên quá trình truyền hoàn toàn tách biệt với giao thức Chord. Hình 18 và hình 19 thể hiện sự liên quan giữa chức năng truyền video multicast (xây dựng trong các lớp WebcamServer và WebcamClient) và giao thức Chord. Trong phần xây dựng giao thức Chord, lớp Node chứa các thuộc tính và phương thức của giao thức Chord, trong khi lớp MessageHandler có chức năng liên kết lớp Node với giao thức UDP tầng giao vận, đồng thời bổ sung cơ chế tin cậy cho giao thức UDP. Ứng dụng phần giành cho máy chủ (nguồn phát video) có hai hàm chính: hàm captureImage() được sử dụng để lấy hình ảnh video từ camera, và hàm SendBroadcastImage() được sử dụng để gửi hình ảnh đã lấy cho các node tham gia cây multicast. Ở ứng dụng máy chủ, chức năng định tuyến sử dụng bảng finger phục vụ cho quá trình truyền multicast được tích hợp vào trong hàm SendBroadcastImage(), gửi hình ảnh đã nhận được tới tất cả các node có trong bảng finger, cũng như thông báo cho mỗi node biết khoảng multicast mà nó chịu trách nhiệm. Ứng dụng phần giành cho máy khách (các node nhận video) gồm ba luồng chạy độc lập: • Receive(): Nhận các gói tin hình ảnh đến và xếp vào một hàng đợi. Khóa luận tốt nghiệp 42 Phạm Duy Thăng • ProcessPacket(): Xử lý các gói tin trong hàng đợi gói tin để xếp vào hàng đợi hình ảnh và thực hiện việc gọi hàm FowardPacket() để chuyển tiếp gói tin cho các node khác trong cây multicast. • Show(): Biểu diễn các hình ảnh đã được xử lý ra màn hình của máy khách. Ở ứng dụng phía máy khách, chức năng định tuyến multicast sử dụng bảng finger được tích hợp vào trong hàm ForwardPacket(), gửi các gói tin hình ảnh đến cho các node thuộc bảng finger và nằm trong khoảng multicast mà nó quản lý, đồng thời gửi khoảng multicast của các node con cho các node này. Khóa luận tốt nghiệp 43 Phạm Duy Thăng 4.2. Triển khai giao thức khắc phục lỗi ba pha cho ứng dụng truyền video multicast Hình 20.Triển khai giao thức khắc phục lỗi ba pha Để triển khai giao thức khắc phục lỗi ba pha, chúng ta thực hiện lần lượt từng pha theo thứ tự. Tất cả các công đoạn triển khai được minh họa trên hình 20. Pha thứ nhất, pha thông báo thông tin cây multicast, được triển khai ở lớp Node của giao thức Chord. Lớp Node sẽ được bổ sung hai thuộc tính là Father lưu thông tin node cha và Grandfather lưu thông tin node ông. Chức năng thông báo thông tin node ông được thực hiện bởi hàm requestUpdateGrandfather(), được gọi từ trong thân Khóa luận tốt nghiệp 44 Phạm Duy Thăng hàm WebcamClient.Receive() mỗi khi node nhận được một luồng video từ một node cha mới. Mỗi khi node con nhận được thông điệp thông báo thông tin node ông, nó tiến hành cập nhật thuộc tính Grandfather. Pha thứ hai là pha phát hiện lỗi và thông báo lỗi. Chức năng phát hiện lỗi được cài đặt trong hàm WebcamClient.Receive(). Chức năng phát hiện lỗi được thực hiện nhờ một đồng hồ. Nếu đồng hồ nhận thấy sau một khoảng thời gian delta mà vẫn không có gói tin multicast truyền đến, nó sẽ gọi phương thức thông báo lỗi requestUpdateEntry(). Phương thức này được cài đặt trong lớp node. Khi phương thức này được gọi, node sẽ gửi một gói tin tới node ông yêu cầu cập nhật lại finger trỏ tới node cha. Pha thứ ba là pha xử lý lỗi, được cài đặt trong lớp Node. Mỗi khi nhận được gói tin thông báo lỗi, phương thức OnRequestUpdateEntry() sẽ được gọi để cập nhật lại entry tương ứng với node được thông báo (nếu có). Giá trị delta phụ thuộc vào độ liên tục của dữ liệu truyền đi (số gói tin trong mỗi giây), sẽ được lựa chọn sau khi có đo đạc cụ thể. 4.3. Mô hình thực nghiệm Việc chạy thử chương trình và đo đạc được thực hiện trên môi trường mạng LAN. Số node tham gia là 6 - 9 node, trong đó có 1 node đóng vai trò nguồn phát video(chạy chương trình phía máy chủ) và các node còn lại đóng vai trò các node nhận video (chạy chương trình máy khách). Việc truyền video được thực hiện trong suốt quá trình thực nghiệm. Trong suốt quá trình này, việc gửi và nhận các gói tin điều khiển của giao thức Chord và các gói tin multicast đều được ghi lại trong các tệp ghi log. Để xác định tính hiệu quả của giao thức khắc phục lỗi, sau khi quá trình truyền multicast đã ổn định, lần lượt cho các node tham gia rời mạng, và theo dõi luồng multicast truyền đến tất cả node con của các node rời mạng. Từ đó đưa ra các kết luận về tỷ lệ thành công của giao thức và độ trễ để cây multicast được khôi phục. Khóa luận tốt nghiệp 45 Phạm Duy Thăng 4.4. Các kết quả thực nghiệm Trước tiên, ta tiến hành đo đạc số gói tin multicast được truyền từ nguồn tới một node trong mỗi giây. Ta tiến hành theo dõi trên một node con của nguồn, trong hai khoảng thời gian khác nhau là 5 giây và 10 giây. Số lần thực hiện đo đạc là 3 lần Kêt quả đo đạc được thể hiện trong bảng sau: Số gói tin nhận Khoảng thời gian (miligiây) Lần đo 1 Lần đo 2 Lần đo 3 Trung bình 5000 149 147 145 147 10000 297 251 298 282 Result (gói/giây) 28.8 Khoảng cách 2 gói 34.72 Như vậy khi truyền trong mạng LAN, chúng ta có thể chọn giá trị delta là 347 miligiây, tương ứng với việc chúng ta chịu mất mát (hoặc trễ) tối đa 10 gói tin liên tục. Chúng ta sẽ sử dụng giá trị này để cài đặt giao thức khắc phục lỗi. Tiếp theo, chúng ta tiến hành đo độ trễ trung bình của quá trình khôi phục. Việc đo đạc sẽ tiến hành với ứng dụng truyền video multicast trước và sau khi bổ sung giao thức khắc phục lỗi. Áp dụng giao thức 6 node 9 node Trung bình Trước (ms) 11220 12003 1542 9876 13786 2546 11235 11543 9218.88 Sau (ms) 1245 2354 2322 1564 2454 4328 2835 4102 2650.5 Như vậy, chúng ta có thể thấy được rằng sau khi áp dụng giao thức khắc phục lỗi ba pha, độ trễ (đơn vị: miligiây) của quá trình khôi phục đã giảm rất nhiều. Điều này có nghĩa là các node con sẽ mất ít thời gian chờ đợi hơn khi node cha bị lỗi, hay nói cách khác, hiệu suất của giao thức đã được cải thiện rõ rệt. Khóa luận tốt nghiệp 46 Phạm Duy Thăng Chương 5 – Kết quả và hướng phát triển Thay cho lời kết luận, tôi xin trình bày đánh giá công việc thực hiện được và đưa ra các định hướng cho các công việc sẽ xây dựng tiếp theo. 5.1. Đánh giá kết quả Khóa luận trình bày về giải pháp khắc phục lỗi cho quá trình truyền thông multicast trên nền mạng ngang hàng giao thức Chord. Tôi đã trình bày các vấn đề lỗi xảy ra trong truyền thông multicast trên nền mạng Chord, cũng như đã đưa ra giao thức để giải quyết các vấn đề đó. Giao thức đưa ra đã khắc phục được những điểm chưa phù hợp khi áp dụng mô hình mạng ngang hàng giao thức Chord cho mục đích truyền thông multicast, đồng thời vẫn giữ được những ưu điểm của mô hình. Kết quả thực nghiệm cũng đã đưa ra những đánh giá bước đầu về tính khả thi và tính hiệu quả của giải pháp khắc phục lỗi. Như vậy, khi khắc phục được các vấn đề lỗi còn tồn tại, ta đã nâng cao tính ứng dụng của mô hình truyền thông multicast dựa trên nền mạng ngang hàng Chord. Nhờ vào việc phân tán tài nguyên của toàn mạng lên các node tham gia, đồng thời vẫn đảm bảo được độ tin cậy, mô hình này hiện có thể áp dụng được vào cho các mục đích phân phát dữ liệu đa phương tiện trên mạng internet như truyền hình trực tuyến, hội nghị trực tuyến,… 5.2. Vấn đề còn tồn tại và hướng phát triển tiếp theo Tuy đã góp phần giải quyết được những điểm chưa phù hợp khi áp dụng mô hình mạng ngang hàng Chord cho mục đích truyền thông multicast, nhưng do thời gian thực hiện nghiên cứu có hạn, giao thức đưa ra trong khóa luận này vẫn còn những tồn tại chưa giải quyết được. Thứ nhất, ý tưởng của giải pháp đưa ra là sử dụng các node con của một node N để phát hiện lỗi xảy ra ở node N, rồi thông báo cho node cha của N để xử lý. Giải pháp đưa ra đã thực hiện tốt ý tưởng. Tuy nhiên, với vấn đề lỗi xảy ra ở cả node N và node cha của nó, giao thức xử lý chưa được cài đặt thành công. Khóa luận tốt nghiệp 47 Phạm Duy Thăng Thứ hai, giao thức cũng chưa đưa ra được giải pháp để giải quyết cho tình huống có hai node cùng gửi luồng dữ liệu multicast đến một node N. Do quá trình thực hiện việc đồng bộ bảng finger và danh sách successor trong mạng Chord được thực hiện định kỳ nên có thể xảy ra trường hợp bảng finger được đồng bộ chậm. Do đó hoàn toàn có thể xảy ra trường hợp có một node nhận được hai luồng multicast, nghĩa là node đó có hai node cha. Trong trường hợp này giao thức khắc phục lỗi sẽ hoạt động sai. Do giao thức còn một số tồn tại chưa giải quyết được, nên trong thời gian tới, để hoàn thiện giải pháp cần tập trung giải quyết các vấn đề đó. Tôi cũng sẽ kết hợp với một số nghiên cứu khác để thực hiện việc triển khai giao thức vào một ứng dụng thực tế như truyền hình ảnh trong hội nghị trực tuyến. Khóa luận tốt nghiệp 48 Phạm Duy Thăng Tài liệu tham khảo Tiếng Việt [1] Hoàng Ngọc Khánh. Xây dựng giao thức mạng ngang hàng có cấu trúc Chord. Khóa luận tốt nghiệp Đại học Công nghệ, 2008. [2] Nguyễn Hữu Tú. Triển khai multicast trên mạng ngang hàng có cấu trúc Chord. Khóa luận tốt nghiệp Đại học Công nghệ, 2008. [3] Giới thiệu về multicast. [4] Mạng đồng đẳng, C4%91%E1%BA%B3ng Tiếng Anh [5] M. Amad, A. Meddahi. A Scalable Approach for Application Layer Multicast in P2P Networks. PerCom 2008. [6] Miguel Castro, Peter Druschel,… Scribe: A large-scale and decentralized application-level multicast infrastructure, 2002. [7] Jung-Rung Han. Failure Recovery with Priority Progress Multicast. B.Sc., The University of British Columbia, 2003. Khóa luận tốt nghiệp 49 Phạm Duy Thăng [8] Gifford Jannotti, et al. Overcast: Reliable multicasting with an overlay network, 2000. [9] Ion Stoica, Robert Morris,… Chord: a scalable peer-to-peer lookup protocol for internet applications, 2003. [10] Guang Tan; Stephen. A. Jarvis. Improving the Fault Resilience of Overlay Multicast for Media Streaming, 2007 [11] Guang Tan; Stephen. A. Jarvis. Stochastic Analysis and Improvement of the Reliability of DHT-Based Multicast. INFOCOM 2007. [12] Multicast. [13] Peer-to-peer computer network, [14] RFC791 – Internet Protocol