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