Khóa luận Truyền tin multicast đa luồng thời gian thực trên mạng ngang hàng có cấu trúc

1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Văn Minh TRUYỀN TIN MULTICAST ĐA LUỒNG THỜI GIAN THỰC TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Văn Minh TRUYỀN TIN MULTICAST ĐA LUỒNG THỜI GIAN THỰC TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC KHOÁ 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: TS. Nguyễn Hoài Sơn HÀ NỘI - 2010 LỜI CẢM ƠN Em xin chân thành cảm ơn các thầy cô trường Đại học Công Nghệ - Đại học Quốc Gia Hà Nội đã tận tình giảng dạy và giúp đỡ em trong suốt 4 năm vừa qua để em có đủ kiến thức để hoàn thành khóa luận này. Đặc biệt em xin gửi lời cảm ơn sâu sắc đến thầy Nguyễn Hoài Sơn. Thầy đã hướng dẫn và định hình cho em cách tiếp cận nghiên cứu khoa học. Đồng thời trong suốt quá trình làm luận văn luôn phải đối mặt với các vấn đề khó khăn cần giải quyết thầy đã luôn theo sát để em tránh khỏi sai lầm giúp em từng bước hoàn thành khóa luận này. Em cũng xin gửi lời cảm ơn đến các anh chị và các bạn trong nhóm nghiên cứu của thầy Nguyễn Hoài Sơn đặc biệt là cô Bùi Thị Lan Hương đã nhiệt tình hỗ trợ về mặt ý tưởng và kinh nghiệm để em có thể hoàn thành khóa luận này thật tốt. Con xin gửi tới bố mẹ và những người thân trong gia đình lòng biết ơn sâu sắc đã luôn động viên , giúp đỡ cho con vượt qua giai đoạn khó khăn này. Hà Nội, tháng 5 năm 2010 Sinh viên Nguyễn Văn Minh Tóm tắt Trong thời gian gần đây sư ̣phát triển maṇh me ̃của ha ̣tầng Internet đa ̃cho ra đời những ứng duṇg mới thay đổi hoàn toàn cách tương tác của con người với nhau trên toàn thế giới. Kết nối với baṇ bè thông qua maṇg Internet trở nên đơn giản hơn bao giờ hết nhờ những ứng duṇg nh ư Chat , Voice Call , Video Conference..Hay như cách thức xem truyền hình IP TV, xem video theo yêu cầu thông qua maṇg Internet với chất lươṇg cao cũng cho thấy sư ̣ thú vị hơn việc xem tivi truyền thống . Mô ̣ phần trong những ứng duṇg này được xây dựng dựa trên nền tả ng truyền tin multicast thời gian thưc̣ đươc̣ đề câp̣ đến trong khóa luâṇ. Truyền tin multicast thời gian thưc̣ trên maṇg ngang hàng là môṭ nhánh trong truyền tin multicast thời gian thưc̣ trên maṇg Internet . Khác với các mô hình Client - Server truyền thống , mô hình maṇg ngang hàng có những đăc̣ trưng riêng biêṭ . Với mô hình maṇg ngang hàng người thiết kế có thể tâṇ duṇg băng thông và khả năng lưu trữ của các máy tham gia maṇg thay vì tâp̣ trung tải vào một số máy chính như các server trong mô hình Client-Server. Điểm maṇh này của mô hình mạng ngang hàng đã làm cho các nghiên cứu về truyền tin multicast cũng như video str eaming trên maṇg ngang hàng ngày càng nhiều khi mà các nghiên cứu trên mô hình client -server đa ̃gần như không thể tối ưu hơn nữa. Khóa luận tôi trình bày nhằm đưa ra một giải pháp xây dựng cây multicast đa luồng thời gian thực trên mạng ngang hàng có cấu trúc với mong muốn đáp ứ ng đươc̣ các yêu cầu đăc trưư g như đảm bảo đô ̣trê ̃taị các node tham gia maṇg không quá lớn và độ trễ giữa các luồng nhận được tại mỗi node chênh lệch nhau nhỏ . Thiết kế được đưa ra trong khóa luận dựa trên giao thức DHT và mô hình mạng Chord , kết quả mô phỏng và đánh giá bước đầu đã cho kết quả tốt. Tuy nhiên cần nhiều nghiên cứu cải tiến hơn nữa nhằm đạt hiệu quả cao nhất. Mục lục Mở đầu ............................................................................................................................. 2 Chương 1. Truyền tin multicast thời gian thực ............................................................... 3 1.1. Tổng quan về truyền tin multicast thời gian thực ................................................. 3 1.1.1. IP Multicast ..................................................................................................... 4 1.1.2. Multicast tầng ứng dụng ................................................................................. 6 1.1.3. Các mô hình truyền tin multicast tầng ứng dụng ............................................ 8 1.2. Truyền tin multicast thời gian thực ..................................................................... 11 Chương 2. Truyền tin multicast đa luồng thời gian thực .............................................. 13 2.1. Tổng quan về truyền tin multicast đa luồng ........................................................ 13 2.2. Splitstream ........................................................................................................... 14 Chương 3. Xây dựng cây multicast đa luồng thời gian thực trên mạng ngang hàng có cấu trúc .......................................................................................................................... 25 3.1. Vấn đề cần giải quyết .......................................................................................... 25 3.2. Ý tưởng................................................................................................................ 25 3.3. Thiết kế giải pháp ................................................................................................ 27 3.3.1. Xây dựng cây multicast ................................................................................ 29 3.3.2. Duy trì cây multicast khi có node rời khỏi mạng ......................................... 32 Chương 4. Mô phỏng và đánh giá ................................................................................. 33 4.1. Chương trình mô phỏng ...................................................................................... 33 4.1.1. Kiến trúc mạng mô phỏng ............................................................................ 33 4.1.2. Các tham số trong mạng mô phỏng .............................................................. 34 4.2. Kết quả và đánh giá ............................................................................................. 36 4.2.1. Hiệu quả độ chênh lệch số hop nhận được các luồng tại các node .............. 36 4.2.2. Hiệu quả độ cân bằng tải trên toàn hệ thống ................................................ 38 Chương 5. Kết luận ........................................................................................................ 40 5.1. Kết luận ............................................................................................................... 40 5.2. Hướng phát triển tiếp theo của đề tài .................................................................. 40 1 Danh mục hình ảnh Hình 1. Một số mô hình truyền tin ...........................................................................................................3 Hình 2. Mô hình IP Multicast ....................................................................................................................4 Hình 3. Bộ định tuyến trong truyền tin multicast tầng mạng ..................................................................6 Hình 4. Truyền thông multicast tầng mạng và tầng ứng dụng ................................................................7 Hình 5. Giao thức Narada.........................................................................................................................9 Hình 6. Mạng phủ 7 node (a) và cây multicast xây tương ứng (b) ....................................................... 10 Hình 7. Truyền tin mulicast đa luồng .................................................................................................... 13 Hình 8. Bảng định tuyến của node 10233102 trong Pastry .................................................................. 15 Hình 9. Node 10233102 gửi thông điệp m đến node 33321220 ........................................................... 16 Hình 10. Quá trình 1 node join vào group ............................................................................................. 19 Hình 11. Truyền tin multicast trong group Scribe ................................................................................. 20 Hình 12. Quá trình tự sửa cây multicast ............................................................................................... 21 Hình 13. Splitstream F luồng ................................................................................................................. 22 Hình 14. Xác định node cha khi băng thông đi ra vượt quá giới hạn .................................................... 23 Hình 15. Phân chia vùng gần vùng xa cho các node con ....................................................................... 26 Hình 16. Bảng Finger Table trong Chord ............................................................................................... 28 Hình 17.Lưu giữ key trong mạng Chord ................................................................................................ 29 Hình 18.Tìm các node con gần và node con xa .................................................................................... 30 Hình 19. Node nhận được các luồng ..................................................................................................... 31 Hình 20. Sửa cây multicast khi có node rời khỏi mạng ......................................................................... 32 Hình 21. Mô hình mạng thực tế ............................................................................................................ 33 Hình 22. Chênh lệch hop lớn nhất giữa các luồng với 1014 node ......................................................... 37 Hình 23. Chênh lệch hop lớn nhất giữa các luồng với 2072 node ......................................................... 38 Hình 24. Hiệu quả cân bằng tải với 1014 node ..................................................................................... 38 Hình 25. Hiệu quả cân bằng tải với 2072 node .................................................................................... 39 2 Mở đầu Trong thời gian gần đây ha ̣tầng Internet phát triển với tốc đô ̣chóng măṭ . Tốc đô ̣ truyền tải trên maṇg cao đa ̃làm xuất hiêṇ nhiều ứng duṇg mới sử duṇg truyền tin multicast thời gian thưc̣ như IP TV , video conference.. Chúng đang làm thay đổi cách giao tiếp của con người , thu hep̣ moị khoảng cách vâṭ lí , mang đến cho chúng ta những trải nghiêṃ mới mẻ về cuôc̣ sống . Truyền tin multicast có 2 loại chính là IP multicast và multicast trên tầng ứng dụng. IP Multicast có thể xem là phương pháp multicast chính thống , hiêụ quả nhất . Tuy nhiên khi triển khai trên maṇg Internet thì IP Multicast găp̣ những trở ngaị rất lớn : đó là chi phí cho viêc̣ thay thế router trên toàn maṇg Inter net (do các router trước đây không có khả năng multicast ) và chi phí cho việc duy trì các cây multicast đó trên hê ̣thống Internet rôṇg lớn. Xu hướng truyền tin multicast vì thế chuyển sang truyền tin multicast trên tầng ứng duṇg. Tuy nhiên khi triển khai trên truyền tin multicast trên tầng ứng duṇg cũng găp̣ không ít vấn đề . Thay vì nhân bản các gói tin taị các router như IP Multicast , cơ chế Multicast trên tầng ứng duṇg laị nhân bản các gói tin trên các má y đầu cuối . Do đó viêc̣ tối ưu cây multicast nhằm taọ sư ̣cân bằng tải tương đối trên toàn maṇg cũng là môṭ vấn đề . Môṭ vấn đề nữa phải tính đến là đô ̣trễ . Các gói tin liên tục phải luân chuyển qua nhiều vi ̣ trí đầu cuối nên đô ̣trê ̃se ̃tăng cao . Viêc̣ xây dưṇg đươc̣ môṭ cây multicast phù hơp̣ để giảm thiểu đô ̣trê ̃cũng là môṭ vấn đề quan troṇg . Hiêṇ nay đa ̃có những nghiên cứu xây dưṇg cây multicast đa luồng trên maṇg ngang hàng có cấu trúc như Sp litstream. Splitstream đươc̣ xây dưṇg dưạ trên nền tảng Pastry, Scribe thêm vào đó môṭ số giải pháp để haṇ chế tình traṇg quá tải taị môṭ số node tham gia maṇg. Nghiên cứu này đã có kết quả tương đối tốt. Giải pháp của khóa luận đưa ra dựa trên ý tưởng và các ưu điểm của mô hình mạng có cấu trúc Chord được sửa đổi để phù hợp với việc xây dựng cây truyền tin multicast đa luồng. Tóm tắt nội dụng trình bày trong các chương: Chương 1: Truyền tin multicast thời gian thực Chương 2: Truyền tin multicast đa luồng thời gian thực Chương 3: Xây dựng cây multicast đa luồng thời gian thực trên mạng ngang hàng có cấu trúc Chương 4: Mô phỏng và đánh giá Chương 5: Kết luận và hướng phát triển 3 Chƣơng 1.Truyền tin multicast thời gian thực 1.1.Tổng quan về truyền tin multicast thời gian thực Trong điều kiện internet phát triển rất nhanh như hiện nay việc truyền tin trên mạng đã trở nên ngày càng quan trọng và phổ biến. Mục đích cuối cùng của việc truyền tin là gửi thông tin từ máy này đến máy khác nên để đơn giản và trực quan người ta đã mô hình hóa việc truyền tin giữa các máy thành truyền tin giữa các node. Sau đây là 1 số mô hình truyền tin thường gặp : Hình 1. Một số mô hình truyền tin Chương này của khóa luận sẽ làm rõ chi tiết việc truyền tin multicast. Truyền tin multicast được định nghĩa là việc 1 máy truyền tin đến 1 nhóm máy có lựa chọn. Quá trình được mô hình hóa thành các node như trên hình 1: gói tin được nhân bản thành nhiều gói tin khác và gửi đi theo các cạnh của cây multicast . Ta có thể thấy truyền tin multcast tỏ ra rất hiệu quả trên mạng Internet. So sánh với phương pháp truyền tin broadcast (gửi không có lựa chọn) ta thấy : môṭ node se ̃ gửi gói tin đến tất cả các node khác mà nó biết , trong khi những node thưc̣ sư ̣cần dữ liêụ không phải là tất cả các node ấy . Điều này thưc̣ sư ̣làm lañg phí băng thông của mạng. Chính nhờ các đặc tính riêng hiệu quả như vậy mà truyền tin multicast đang trở thành hướng phát triển truyền tin chính so với các phương pháp truyền tin khác. Truyền tin multicast hiện nay được phân loại thành 2 nhánh chính là : IP Multicast 4 (Multicast tầng mạng ) và Multicast trên tầng ứng dụng sẽ được giới thiệu ở mục tiếp theo. 1.1.1.IP Multicast Định nghĩa cơ bản nhất của IP Multicast : 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.. Hình 2. Mô hình IP Multicast Hình 2 trình bày chi tiết về mô hình IP Multicast và cách thức hoạt động của nó. Node gửi là máy Sender với mục tiêu là gửi được gói tin đến cho 2 máy Receiver. Sender sẽ gửi gói tin IP với địa chỉ multicast (cái này sẽ được giải thích chi tiết ở đoạn sau) đến Switch/Router. Switch/Router nhận được gói tin và phân tích địa chỉ multicast trên gói tin IP đó. Sau đó Switch/Router nhân bản gói tin thành n gói tin gửi đi cho n máy có địa chỉ IP Multicast trên (trong hình minh họa là 2 máy có cùng địa chỉ IP Multicast đó). Deering được xem như là người đầu tiên đề xuất giải pháp IP multicast. Năm 1990 IP Multicast ra đời , nó là sự phát triển từ mô hình dịch vụ IP unicast để nhằm nâng cao giao tiếp đa điểm. Mô hình dịch vụ multicast cung cấp hai lợi ích chính: (1) hiệu quả sử dụng băng thông và (2) việc địa chỉ nhóm gián tiếp cho phép redezvous tầng mạng. Đề xuất này của Deering đã mở ra một lĩnh vực mới cho các ứng dụng của IP Multicast. 5 Để truyền multicast thì cần dựa trên khái niệm một nhóm. Nhóm chứa tất cả các máy cùng mong muốn nhận được một dữ liệu. Nhóm này không có giới hạn về vật lý và địa lý, nó có thể nằm ở bất cứ đâu trên mạng Internet. Thực ra ban đầu IP Multicast được phát triển trong các trường đại học và các phòng nghiên cứu nhằm phục vụ chủ yếu cho video streaming với tốc độ cao nhất. Việc quản lý và phân nhóm trong khu vực mạng LAN như vậy sẽ không quá phức tạp. Tuy nhiên khi áp dụng vào mạng Internet thì nó cần 1 định nghĩa nhóm tốt hơn. Và IGMP( IGMP - Internet Group Management Protocal) đã ra đời. Các máy trên mạng Internet muốn nhận dữ liệu thì cần phải gia nhập giao thức quản lý nhóm mạng IGMP. 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. Mỗi một máy cần có địa chỉ multicast là địa chỉ mà mỗi máy tham gia vào nhóm và mong muốn nhận được dữ liệu. IANA ( IANA - Internet Assigned Numbers Authority) sẽ kiểm soát việc gán địa chỉ IP Multicast. IANA gán không gian địa chỉ lớp D được dùng cho IP Multicast. Như vậy tất cả địa chỉ Multicast nằm trong dải: 224.0.0.0 – 239.255.255.255. Ngoài ra, để có thể thực hiện multicast, bộ định tuyến (tiếng Anh: Router) trong mô hình này phải có chức năng multicast(đây là một trong những vướng mắc lớn nhất khiến IP Multicast khó có thể phát triển mạnh). 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 Error! Reference source not found.. 6 Hình 3. Bộ định tuyến trong truyền tin multicast tầng mạng 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, 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 IP Multicast đang sử dụng hiện nay để triển khai trên hệ thống mạng Internet đang thực sự găp̣ các vấn đề khó khăn :  Khi triển khai trên hê ̣thống lớn như Internet các router phải lưu giữ rất nhiều trạng thái của các nhóm . Đây thưc̣ sư ̣là môṭ vấn đề lớn khi số nhóm tăng lên cao.  Tạo và duy trì một cây multicast mấ t rất nhiều tài nguyên và thời gian .  Khi có quá nhiều kết nối hoặc một node 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 xử lí thâṭ tốt. Vấn đề lớn nhất của viêc̣ triển khai IP Multicast là chi phí để thay thế lại hạ tầng mạng đã được xây dựng là cực kỳ lớn. Chính vì vậy mà xu hướng chuyển giao sang truyền thông multicast tầng ứng dụng. 1.1.2.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 cộng với rất nhiều khó khăn ở trên, xu hướng multicast ngày càng mở rộng sang multicast tầng ứng dụng. 7 Multicast tầng ứng dụng không thay đổi và phá vỡ hệ thống mạng. Thay vào đó, nó chỉ thực hiện chức năng truyền multicast trên các máy cuối ở tầng ứng dụng. Từ tầng ứng dụng sẽ truyền xuống các tầng mạng và tầng giao vận. Ở các tầng thấp hơn, cơ chế hoàn toàn không thay đổi. Hình 4. 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) 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 nguyên thuỷ (IP multicast) 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. Có hai thông số đo đạc tính chất của việc truyền multicast trên tầng phủ: stress và stretch. Stress được xác định theo từng kết nối và đếm số gói tin được gửi đi bởi một giao thức ở tầng mạng dưới. Stretch được đo bởi mỗi máy và là tỷ lệ của chiều dài từ nguồn đến thành viên ở một mạng phủ theo đường dẫn unicast. Nhìn chung, các giao thức tầng mạng có thể được đánh giá theo ba hướng:  Chất lượng của đường truyền dữ liệu: là chất lượng của cây được đo bởi một số thông số stress, stretch và cấp độ node.  Độ mạnh yếu của tầng phủ: Mỗi máy thường không ổn định như router, các node có thể rời mạng tạm thời hoặc vĩnh viễn làm ảnh hưởng đến các node nhận phía dưới. Độ mạnh yếu của các giao thức tầng ứng dụng được đo bởi việc đo đạc sự mất mát dữ liệu truyền khi các thành viên bị lỗi và thời gian mà nó cần để giao thức có thể khôi phục lại để truyền cho các thành viên khác.  Quá tải : để sử dụng hiệu quả tài nguyên mạng, quá tải điều khiển ở mỗi thành viên nên nhỏ. Đó là một thông số giá thành quan trọng để đo đạc tính mở rộng của thành viên. 8 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 ứng dụng vẫn có khả năng giảm tải nhiều cho đường truyền và nguồn tin multicast. 1.1.3.Các mô hình truyền tin multicast tầng ứng dụng Đề có thể truyền tin multicast được thì trước tiên cần có một cấu trúc topology của mạng phủ. Trong topology của tầng mạng phủ - tầng mạng ứng dụng, các máy tính liên kết với nhau. Mỗi máy tính gọi là một node mạng liên kết ảo với các node khác. Việc xem máy tính là 1 node ảo được sử dụng rất nhiều trong cấu trúc của các mạng ngang hàng như Chord , Pastry do tính chất phân tán và không xác định được về phương diện địa lý của các máy thật. Dựa vào topology đó, các node tương ứng với các node trên cây multicast (node lá hoặc node con), liên kết ảo sẽ tạo nên cơ chế truyền tin từ node lá sang các node con. Có hai cách thức truyền thông multicast: multicast trên mạng có cấu trúc (tree- first) và multicast trên mạng không có cấu trúc (mesh-first). Sau đây ta sẽ nghiên cứu phân tích và lựa chọn một hướng truyền thông phù hợp cho video streaming. Multicast theo hướng mesh-first Trong cách tiếp cận mesh-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. Giao thức Narada là một trong những giao thức multicast tầng ứng dụng đầu tiên và theo hướng mesh-first. Nó chỉ định một máy đặc biệt là Rendezvous Point (RP) được sử dụng để theo dõi sự gia nhập của một thành viên mới. Tất cả các giao thức multicast tầng mạng cũng sử dụng một hoặc một số các thực thể tương tự như RP trong Narada để tạo cơ chế gia nhập. Xây dựng mesh: khi một node mới muốn gia nhập nhóm multicast, nó sẽ có danh sách thành viên đã gia nhập vào mesh do RP cung cấp. Sau đó thành viên mới sẽ lựa chọn ngẫu nhiên một số các thành viên và gia nhập vào mesh và coi như là láng giềng của những thành viên đó. Quy trình gia nhập thành công khi mà ít nhất một thành viên trong danh sách đồng ý để thành viên mới là láng giềng mesh. Khi gia nhập vào mesh, thành viên mới bắt đầu định kỳ trao đổi thông điệp với các lang giềng mesh của nó. Bất cứ khi nào một node gia nhập hoặc một thành viên rời 9 nhóm, nhóm này sẽ thay đổi thông tin của tất cả thành viên. Do đó, mỗi thành viên trong nhóm giữ trạng thái của tất cả các thành viên trong nhóm. Thông tin này thường xuyên được cập nhật. Việc lưu trữ các thông tin trạng thái của tất cả thành viên trong nhóm ở mỗi thành viên dẫn tới quá tải kiểm soát lớn, quá tải kiểm soát lên tới (O(N2)) với N là kích thước của nhóm. Do đó, giao thức Narada hiệu quả chỉ khi kích thước nhóm Multicast là nhỏ. Hình 5. Giao thức Narada Khi cả thành viên D và E cùng lỗi, mesh phân chia thành 2 phần. Do đó, các thành viên A, B và C sẽ ngừng nhận được thông tin trạng thái từ F, G và H; và ngược lại. Mỗi thành viên có thể khảo sát các thành viên từ khi nó ngừng nhận được thông điệp trạng thái để tạo ra một kết nối mới và sửa các phần. Chý ý rằng, việc sửa không yêu cầu sự hỗ trợ của RP và do đó vẫn có thể thực hiện được ngay cả khi RP bị lỗi. Đường truyền dữ liệu: các thành viên của một nhóm thực hiện một giao thức định tuyến để tính ra các đường đi unicast trong mesh. Sự chọn lọc của mesh: các đường truyền dữ liệu trong Narada là các cây nhịp của mesh. Do đó, chất lượng của đường truyền dữ liệu phụ thuộc vào chất lượng của các kết nối là một phần của mesh. Khi một thành viên mới tham gia, hoặc khôi phục từ các phần, một tập ngẫu nhiên các cạnh sẽ được thêm vào mesh. Do đó, sự chọn lọc định kỳ cần phải được thực hiện với các cạnh để cải tiến chất lượng của các đường truyền dữ liệu. Việc thêm cạnh (J,G) là có ích bởi vì một số lượng lớn các node unicast 10 có thể được thay bằng một cạnh mới. Cạnh (A, C) được xoá đi. Quyết định để thêm hoặc bỏ đi một cạnh của mess được thực hiện giữa cạnh của 2 điểm cuối. Ư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ủ. Với nhược điểm này thì không phù hợp với truyền video streaming do các gói tin có độ trễ khác nhau, gói tin gửi trước có thể đến sau, gói tin gửi sau đến trước. Việc không cân bằng độ trễ sẽ làm ảnh hưởng đến việc trình diễn dữ liệu. Multicast theo hướng tree-first Trong cách tiếp cận 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 chịu tải quá cao. Hình 6. Mạng phủ 7 node (a) và cây multicast xây tương ứng (b) Scribe là hệ thống multicast tầng ứng dụng mở rộng được xây dựng trên Pastry. Để tạo nhóm multicast, Scribe tạo ra một khoá Pastry tự động được biết như Id của một nhóm. Cây multicast tương ứng với một nhóm được thực hiện bằng một tập hợp các bộ định tuyến Pastry từ một node thành viên đến nhóm gốc của Id. Bằng việc truyền lùi lại trên đường dẫn, các gói tin multicast từ gốc tới mỗi thành viên. SplitStream là hướng phát triển sau của Scribe mà tập trung vào việc phân bổ truyền thông. Ngoài Scribe là hệ thống multicast tầng ứng dụng xây dựng trên Pastry, ta cũng có thể xây dựng multicast trên các mạng ngang hàng có cấu trúc DHT khác như CAN, CHORD… 11 Mạng ngang hàng có cấu trúc thuộc nhánh các mạng ngang hàng phân tán trong các mô hình mạng ngang hà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ả. Phát triển trên mạng ngang hàng có cấu trúc sẽ tận dụng ưu điểm là khả năng dễ mở rộng do cấu trúc liên kết rõ ràng; việc tìm kiếm thông tin nhanh hơn. 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. Đây là một lợi thế rất quan trọng khi áp dụng mạng ngang hàng có cấu trúc để triển khai truyền tin multicast, do truyền tin multicast yêu cầu khả năng định tuyến của mạng phủ để xây dựng nên cây multicast. Ngoài ra, 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. 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. 1.2.Truyền tin multicast thời gian thực Một nhánh trong truyền tin multicast là truyền tin multicast thời gian thực. Phương pháp truyền tin này thường được áp dụng trong các ứng dụng video streaming trực tiếp có thể xem là thế mạnh thực sự của mạng ngang hàng so với mô hình mạng client – server truyền thống. Ví dụ cụ thể nhất là khi chúng ta muốn xem một trận đá bóng rất được mong đợi giữa Real Maldrid – Barcelona. Một thống kê cho biết có đến gần 1 tỷ người theo dõi trận cầu này trên toàn thế giới và chắc chắn là tại thời điểm đó không có 1 server nào có thể đủ mạnh để phát sóng trực tiếp trận đấu lên mạng Internet. Thế nhưng với 1 ứng dụng của video streaming thời gian thực trên mạng ngang hàng (như Sopcast , TVU Player) bạn lại có thể theo dõi trận đấu này với chất 12 lượng có thể chấp nhận được. Đó chính là ưu điểm vượt trội của mô hình mạng ngang hàng và hiện nay vẫn đang được phát triển để ngày càng tối ưu hóa. Khóa luận này cũng là một đề xuất về truyền tin multicast đa luồng thời gian thực dựa trên giao thức Chord nhằm ứng dụng cho video streaming thời gian thực. Trong truyền tin multicast thời gian thực có 2 đặc tính riêng quan trọng nhất cần phải đáp ứng để đạt được chất lượng có thể chấp nhận được :  Inbound bandwith tại mỗi máy là đủ lớn để decode được thành video với chất lượng chấp nhận được . Với các kỹ thuật decode bây giờ thì các máy với mức download lớn hơn 240Kbits/s là có thể xem được video.  Độ trễ tại các máy là không quá lớn để đảm bảo tính thời gian thực . Tính chất này thường rất quan trọng trong các ứng dụng video streaming 2 chiều như video call … tuy nhiên trong các ứng dụng 1 chiều như các ứng dụng xem TV trên Internet đặc tính này lại có thể không quá quan trọng 13 Chƣơng 2.Truyền tin multicast đa luồng thời gian thực Trong chương một, chúng ta đã hiểu được khái niệm và cách thức truyền tin multicast cũng như truyền tin multicast thời gian thực. Một trong những đặc tính quan trọng của hệ thống multicast là 1 máy khi tham gia vào hệ thống multicast có thể vừa là node gửi dữ liệu lại vừa là node nhận dữ liệu. Từ tính chất này người ta đã phát triển truyền tin multicast từ đơn luồng thành đa luồng với những ưu điểm , hiệu quả ứng dụng rất đáng ghi nhận trên mạng ngang hàng. 2.1. Tổng quan về truyền tin multicast đa luồng Hình 7. Truyền tin mulicast đa luồng Về cơ bản truyền tin multicast đa luồng được xây dụng trên cây multicast với mở rộng : các node thay vì chỉ gửi và nhận 1 gói dữ liệu thì bây giờ lại nhận và gửi nhiều dữ liệu hơn. Xét ví dụ ở Hình 7. Bây giờ giả sử ta chỉ quan tâm đến stripe 1(luồng 1) : đây chính là truyền tin multicast đơn luồng. Quá trình truyền tin như sau : node source (nguồn) gửi dữ liệu đến node con 2. Node 2 gửi dữ liệu cho node 3 , 4. Các node 3 , 4 gửi dữ liệu cho các node lá 5 , 6 ,7 ,8. Như vậy ta có thể thấy các node trong 2 , 3 , 4 đều phải gửi dữ liệu đi cho 2 node khác trong lúc đó chỉ nhận về 1 luồng dữ liệu. Trong khi đó các node lá 5 , 6 , 7 , 8 chỉ nhận dữ liệu mà không phải gửi. Việc truyền tin multicast như thế này trên mạng ngang hàng đã vi phạm tiêu chí quan trọng nhất trong mạng ngang hàng : tính công bằng. Trên mạng ngang hàng các node gửi đi nhiều dữ liệu thì cũng phải được nhận lượng dữ liệu xứng đáng với mức đóng góp của node 14 đó trong hệ thống mạng. Điều kiện này là cơ sở để mạng ngang hàng phát triến mạnh trên hệ thống Internet. Trên đây chỉ là trường hợp cây multicast đơn luồng nhị phân , còn trên thực tế mô hình cây multicast chắc chắn sẽ phức tạp hơn nhiều. Theo như nghiên cứu về cây multicast đơn luồng với fanout = 16 (mỗi node gửi dữ liệu cho 16 node con khác) thì có đến 90% là node lá và chỉ có 10% là node trong. 10% đó phải gánh toàn bộ băng thông mạng. Mục đích lớn nhất cuả truyền tin multicast đa luồng là giải quyết được vấn đề vừa đặt ra : làm sao đạt được tính công bằng cho các node tham gia hệ thống multicast. Xét ví dụ ở Hình 7. Bây giờ ta quan tâm đến cả 2 luồng stripe 1 , 2. Sau khi xét quá trình truyền tin của cả 2 luồng ta có thể thấy tất cả các node trong cây đều nhận 2 2 luồng dữ liệu và gửi đi 2 luồng dữ liệu. Nếu stripe 1 và stripe 2 là tương đương nhau thì quả thực hệ thống này đã đạt được sự công bằng mong muốn. Ví dụ ở Hình 7 có thể xem là hình mẫu đơn giản nhất cho cây multicast đa luồng. Việc phát triển và ứng dụng trong hệ thống mạng ngang hàng với độ phức tạp lớn hơn nhiều đã gặp 1 số vấn đề :  Số luồng mong muốn là lớn để đảm bảo mỗi luồng dữ liệu khi truyền đi trên mạng đủ nhỏ để tránh tắc nghẽn. Việc tăng số luồng đồng nghĩa với cách xây dựng việc gửi và nhân các luồng tại mỗi node trong cây multicast cũng sẽ phức tạp hơn để đảm bảo vẫn giữ được tính công bằng  Tính không ổn định của mạng. Đây chính là đặc trưng thực tế của hệ thống mạng ngang hàng. Các node trong cây multicast sẽ vào ra liên tục và để cây multicast vẫn đảm bảo truyền tin được đến tất cả các node thì cần phải có cơ chế thay đổi lại cây multicast cho phù hợp. Gần đây đã có một số nghiên cứu liên quan đến xây dựng cây multicast đa luồng trên mạng ngang hàng có cấu trúc sử dụng giao thức DHT(Bảng băm phân tán - Distributed Hash Table). Mục 2.2 sẽ trình bày về những giải pháp này 2.2.Splitstream Splitstream là giải pháp xây dựng cây multicast đa luồng dựa trên nền tảng Pastry , Scribe. Để hiểu được Splitstream ta sẽ tìm hiểu rõ về cấu trúc Pastry và Scribe ngay sau đây. 15 Pastry Là một giao thức phân phối dữ liệu và định tuyến ở tầng ứng dụng trong các ứng dụng mạng ngang hàng có cấu trúc. Đúng như định nghĩa của nó Pastry có hai nhiệm vụ chính là phân phối dữ liệu trong một mạng ngang hàng và tìm kiếm dữ liệu trong mạng dựa vào khóa tìm kiếm. Hệ thống Pastry là một hệ thống phân tán có khả năng tự cấu hình và có tính ổn định cao, khả năng chống chịu lỗi tốt, đồng thời nó cũng có khả năng mở rộng và ứng dụng cho những dịch vụ lớn. Pastry cũng sử dụng giao thức DHT để lấy định danh các node tham gia vào hệ thống mạng. Với dải địa chỉ lớn thì giao thức DHT quả thực rất phù hợp với hệ thống mạng ngang hàng , không ngoại trừ đối với Pastry. Tuy nhiên điều thú vị của Pastry nằm ở bảng định tuyến sẽ được mô tả dưới đây. Hình 8. Bảng định tuyến của node 10233102 trong Pastry Node và dữ liệu trong mạng Pastry được định danh bởi một giá trị 128 bit (nodeId, ObjId). Mỗi dữ liệu lưu trữ trong mạng được băm bởi một hàm băm từ đó thu được một giá trị gọi là khóa và dữ liệu này được lưu trữ tại node quản lý dãy các khóa có chứa giá trị khóa này (giá trị khóa thu được khi băm dữ liệu). Mỗi node trong mạng sẽ lưu trữ một bảng định tuyến (routing table) một tập các hàng xóm (neighborhood set) và một tập namespace. Pastry dùng các dữ liệu này để quản lý và duy trì sự ổn định của mạng đồng thời phục vụ cho việc tìm kiếm dữ liệu. 16 Ở Hình 8 là bảng định tuyến của nodeId 10233102. Dựa vào bảng định tuyến này node 10233102 có thể gửi dữ liệu đến cho node khác. Ví dụ node 10233102 muốn gửi thông điệp m đến cho node 33321220. Đầu tiên nó sẽ tìm trong các node hàng xóm trong bảng định tuyến , nếu có sẽ gửi đến luôn. Nếu không tìm thấy nó sẽ tìm trong Routing table và so sánh các ký tự ban đầu của node cần gửi đến (33321220) với các cột trong Routing table. Cụ thể là node 33321220 có ký tự đầu là 3 : nó sẽ tìm trong Routing table tại hàng 1 cột 3 tìm được node 31203203. Do ngay từ ký tự đầu của node cần gửi đã khác node gửi nên quá trình tìm kiếm dừng lại. Node 10233102 sẽ gửi đến node 31203203 với yêu cầu sẽ gửi thông điệp m đến node 33321220. Quá trình này tiếp tục xảy ra cho đến khi đến được node cần gửi. Hình 9. Node 10233102 gửi thông điệp m đến node 33321220 Các node định kỳ gửi các gói tin keep-alive cho các node hàng xóm của nó và nếu như một node nào đó không nhận được gói keep-alive của một node hàng xóm trong tập hàng xóm của nó trong một thời gian nhất định thì nó sẽ xem như node hàng xóm đã rời khỏi mạng và tự động update thông tin. Scribe Scribe là cơ sở hạ tầng cho việc truyền multicast ở tầng ứng dụng dựa trên giao thức Pastry. Cũng chính vì thế nó thừa hưởng được những đặc tính của một giao thức mạng ngang hàng có cấu trúc và đồng thời mang những đặc điểm này vào trong việc 17 truyền thông điệp multicast ở tầng ứng dụng. Giống như Pastry, Scribe là mô hình phân quyền hoàn toàn nó có khả năng xây dựng, duy trình mạng, phát tán thông báo một cách có tổ chức và tin cậy đồng thời có tính tương thích cao với số lượng nhóm, số thành viên trong nhóm lớn cũng như khi có nhiều tài nguyên trên mạng. Scribe sẽ xây dựng một cây multicast bằng cách gọi thủ tục join giao thức Pastry mỗi khi một nút có yêu cầu đăng nhập vào nhóm truyền multicast. Và nhờ khả năng tự cấu hình của Pastry mà vấn đề quản lý nút, nút lỗi cũng như ra vào của nút trở nên dễ dàng. Đồng thời Scribe sử dụng giao thức Pastry để phát tán thông báo multicast. Scribe tổ chức theo nhóm, tức là hợp những node có cùng nhu cầu nhận dữ liệu multicast vào một nhóm, và về mặt logic thì các node trong nhóm sẽ có quan hệ với nhau theo hình cây(sẽ giải thích kỹ ở phần sau). Bất kỳ một node nào trong mạng cũng có thể thực hiện được 3 thao tác: một là tạo ra 1 group, hai là join vào một group đã có từ trước (trở thành một node trong cây multicast) và ba là truyền multicast tới tất cả các node có trong group (nguồn multicast). Scribe là một mô hình cung cấp một cách cố gắng tối đa trong việc truyền multicast nó có thể quản lý và duy trì được nhiều group cùng một lúc, các group có số lượng thành viên lớn cũng như có nhiều tài nguyên trong mạng. Chi tiết giải thuật: Mô hình: Mô hình để thực thi Scribe là một mạng Pastry trong đó các máy có cài đặt chương trình ứng dụng của Scrible. Chương trình ứng dụng này sẽ cung cấp cho các máy này hai phương thức là forward (được gọi khi một thông điệp định tuyến qua một node) và deliver (được gọi khi thông điệp đến một node mà có nodeId gần với key nhất hoặc nội dung thông điệp chính là địa chỉ của node đó). Các thông điệp trong Scribe có 4 kiểu là : JOIN (xin tham gia vào một group), CREATE (tạo một group mới), LEAVE (rời khỏi group), MULTICAST (truyền thông điệp multicast). Quản lý nhóm: – Mỗi nhóm truyền multicast có một định danh groupId duy nhất  Scirbe node (tức là node trong mạng có cài chương trình ứng dụng Scrible) có id gần với id của group (groupId) nhất được gọi là “điểm gặp” và nó cũng chính là gốc của cây multicast tương ứng với groupId này luôn. – Tạo Nhóm: Một node Scribe nào đó muốn khởi tạo một group thì các bước thực hiện sẽ là : 18  B1: node Scribe dùng Pastry định tuyến thông điệp route(CREATE,groupId).  B2: giao thức Pastry sẽ gửi thông điệp này tới điểm cuối là một node có nodeId gần với groupId nhất. Và node này sẽ được xem như là gốc của group mới tạo ra.  B3: Hệ thống sẽ kiểm tra độ an toàn, các thông tin về chứng thực nếu không có vấn đề gì thì sẽ thêm group mới vào danh sách các group đã biết trong mạng. Trong việc tạo nhóm bước quan trọng nhất chính là bước kiểm tra độ an toàn và chứng thực thông tin, vì điều này có ảnh hưởng rất lớn tới sự an toàn của toàn mạng nói chung chứ không chỉ riêng sự an toàn của group multicast. Quản lý thành viên : Một group về phương diện logic là một cây multicast có gốc là “điểm gặp", mỗi khi có một node mới được join vào group thì nó sẽ trở thành một thành viên của group cũng như trở thành một thành phần của cây multicast, vì thế phải có cơ chế hợp lý để tổ chức, quản lý các thành viên của group. Nếu một node Scribe là một phần của group thì về phương diện cây multicast thì nó là một forwarder. Mỗi một forwarder duy trì một bảng gọi là children table mà mỗi entry của bảng này sẽ gồm có 2 trường: địa chỉ ip của một node “con” nào đó của nó (ip addr), và nodeId tương ứng của node con đó. Join group: Khi một node muốn join vào một group nào đó nó sẽ thực hiện các bước sau:  Gửi thông điệp JOIN với groupId của group cần join làm key: route (JOIN,groupId).  Giao thức Pastry sẽ định tuyến nó tới “điểm gặp” - Nếu node trung gian trong quá trình truyền thông điệp là một forwarder (một thành phần của group đang định join vào) thì đơn giản chỉ là thêm node cần join vào làm một con của node forwarder này. - Nếu node trung gian không phải là một forwarder của group cần join vào thì thực hiện các bước:  Tạo một children table cho node trung gian và thêm thông tin của node cần join vào bảng này.  Gửi thông điệp JOIN của node trung gian tới điểm gặp (lúc này thay cho việc thực hiện join node ban đầu ta đi join node trung gian vào group). Và cứ thực hiện đệ quy như thế này ta sẽ có được một danh sách các node mới join vào group thay vì chỉ một node ban đầu. 19 Để dễ hiểu ta xét ví dụ sau : một group có điểm gặp là node A có nodeId = 1100 (như hình vẽ ở dưới) Hình 10. Quá trình 1 node join vào group Node B có nodeId là 0111 muốn join vào group có A là gốc. nó sẽ gửi gói tin route(JOIN,x) với x là groupId của group này, giao thức Pastry sẽ định tuyến gói tin tới node D có nodeId là 1001. Nhưng node D không phải là một thành phần của group này cho nên D sẽ tạo ra một children table của nó và thêm vào đó entry (122.145.1.23;0111). Tiếp đó D sẽ gửi gói tin yêu cầu join vào group có gốc là A: route(JOIN,x). Tiếp tục giao thức Pastry lại định tuyến nó tới node E và E cũng không phải là thành viên của group này vì thế E cũng sẽ tự tạo ra một childeren table của nó và thêm vào entry (172.16.2.13;1001) Và sau đó E gửi gói tin route(JOIN,x). Gói tin này tiếp tục được định tuyến và tới được A vì A là một thành của group cho nên ở đây A sẽ thêm entry (10.10.1.123;1101) vào children table của nó. Kết quả là ta sẽ có thêm 3 thành phần mới của group là B ,D, E. Tiếp theo node C có nodeId là 0100 muốn join vào group này. Để bắt đầu nó cũng sẽ gửi gói tin yêu cầu route(JOIN,x) gói tin này được định tuyến tới node D và vì bây giờ D đã là một thành phần của group này nên đơn giản D sẽ thêm vào children table của nó một entry mới (123.134.12.12;0100). Leave group: Khi một node nào đó muốn rời khỏi group nó sẽ ghi một cách cục bộ rằng nó đã rời khỏi group (tức là chỉ một mình nó biết nó đã rời khỏi mạng). Sau đó nếu bảng children table của node này là rỗng tức là nó không có con trong cây multicast thì nó sẽ gửi thông điệp LEAVE tới cha của nó trong cây multicast. Thông điệp này sẽ được đệ quy trong cây multicast cho tới khi nó tới một node mà node có con đã rời khỏi group. Còn nếu bảng children table của node muốn rời mạng không rỗng thì nó làm 20 như trong trường hợp nó không có con nào cả. Sau đó các con của nó sẽ xem như nó bị lỗi và thực thi theo cơ chế sửa lỗi (sẽ trình bày ở dưới). Với cách join và leave group như thế này và với đặc tính phân phối ngẫu nhiên của Pastry cây multicast sẽ được xây dựng một cách đồng đều theo nghĩa là không một node nào trong cây multicast ngay cả node gốc chịu quá nhiều kiết nối tới các node khác. Việc này giúp cho Scribe có khả năng mở rộng về kích thước cũng như về khả năng, tức là cả khi tăng số lượng node trong group hay là tăng các gói mulicast gửi đến mạng thì Scribe vẫn có thể đảm đương được. Truyền multicast tới mạng : Khi một node nào đó muốn truyền multicast tới các điểm trong một group nào đó nó sẽ gửi thông điệp multicast tới điểm gặp (route(MULTICAST,rootId)). Sau khi điểm gặp nhận được thông điệp này nó sẽ gửi trả lại node kia Ip của nó (rootIP), sau đó node này sẽ truyền thông tin muốn gửi tới điểm gặp. Điểm gặp sẽ sẽ copy gói tin multicast này gửi cho các con của nó trong cây multicast (nếu có), các điểm con này khi nhận được dữ liệu cũng lại tiếp tục copy dữ liệu đó và gửi tới các con của nó trong cây (nếu có). Cứ lặp đi lặp lại như vậy và chỉ dừng lại việc này khi dữ liệu tới các node là node lá của cây. Hình 11. Truyền tin multicast trong group Scribe Giả sử như hình vẽ ở trên Sender là node cần gửi dữ liệu cho cây multicast có gốc là 1100. Nó sẽ gửi gói tin route(MULTICAST,1100), node 1100 nhận được gói tin và trả lại cho sender địa chỉ ip của nó từ lúc này sender giao tiếp với node gốc này thông qua ip (bây giờ là quan hệ trong giao thức tcp/ip chứ không liên quan gì đến pastry hay p2p gì cả). Sender gửi dữ liệu cho node gốc 1100 node này sẽ tạo một bản sao dữ liệu và gửi cho con của nó là 1101. Node 1101 nhận được dữ liệu từ root, nó cũng sẽ tạo một bản sao và gửi cho 1001 là con của nó. Node 1001 lại tiếp tục copy dữ liệu và gửi cho 0111 và 0100 là thành viên trong bảng children table của nó. Khi các 21 node 0100 và 0111 nhận được giữ liệu thì vì nó là lá của cây multicast nên nó không làm gì nữa. Trong vấn đề truyền dữ liệu multicast này có một điểm thú vị là khi sender muốn gửi dữ liệu multicast tới group nó lại phải xin và nhận IP của node gốc rồi để sau đó giao tiếp với node này dựa vào IP mà không sử dụng luôn giao thức Pastry để gửi dữ liệu. Đơn giản là việc định tuyến cũng như gửi tin thông qua Pastry là một việc rất tốn thời gian và tài nguyên mạng, mà bình thường một sender không chỉ gửi một gói tin multicast tới mạng, mà nó sẽ gửi một số hoặc nhiều gói, do đó việc sender lưu IP của node root và gửi gói tin trực tiếp sẽ tiết kiệm được thời gian cũng như tài nguyên của mạng. Tuy nhiên nếu node gốc bị lỗi hoặc bị rời khỏi mạng thì sender phải tìm lại IP của node root mới và tiếp tục việc truyền thông tin Sửa cây multicast Vì Scribe làm việc trong môi trường mạng mang, do đó muốn duy trì được sử ổn định của group, phải có những cơ chế hợp lý để giải quyết các vấn đề thường gặp phải trong mạng ngang hàng. Phần này sẽ đi sâu vào việc làm sao để sửa chữa một cây multicast khi một node bị rời khỏi mạng. Trong Scribe node cha sẽ định kỳ gửi các gói tin hearbeat tới node con của nó nhằm thông báo sự tồn tại của mình trong cây. Nếu node con không nhận được gói tin heartbeat do cha nó gửi tới trong một thời gian nào đó, nó sẽ xem như node cha của nó bị lỗi. Và nó sẽ tự động tìm một node cha khác thay thế, bằng cách gửi thông điệp JOIN với key là groupId của group hiện tại (quá trình này giống với quá trình join vào group). Hình 12. Quá trình tự sửa cây multicast 22 Giả dụ như hình vẽ trên ban đầu ta có cây multicast với gốc là node 1100 trong cây node 1001 có cha là node 1101. Khi node 1001 không nhận được heartbeat của 1101 trong một khoảng thời gian nào đó nó sẽ xem như 1101 bị lỗi và nó sẽ tự động gửi gói tin route(JOIN,groupId). Tiếp theo giống như trong quá trình jon group. Cây multicast sẽ được xây dựng lại và bây giờ thì node 1001 nhận một node mới là 1111 là cha mới của nó (như hình vẽ). Trong trường hợp node gốc bị lỗi. Thì các con của nó cũng sẽ chạy giải thuật như trên khi đó giải thuật Pastry sẽ tự chọn ra một node gốc mới có nodeId gần nhất (tính theo hiện thời) với groupId và group sẽ lại được duy trì như bình thường. Vì khả năng chống lỗi cao như thế này, Scribe luôn có tính sẵn sàng cao và chống chịu lỗi tốt, cho dù có nhiều node lỗi cùng một lúc thì sau một thời gian ngắn cây multicast lại được xây dựng lại và ổn định như trước. Splitstream Splistream có thể xem như là việc chọn lựa các cây Scrbie để tạo nên cây multicast đa luồng. Việc chọn lựa các cây Scribe sẽ dễ dàng tạo nên cây multcast đa luồng với tính chất : 1 node là node trong của 1 luồng sẽ là node lá trong các luồng còn lại Hình 13. Splitstream F luồng Việc xây dựng các luồng là khá đơn giản. Như ở trên hình 3 với không gian Pastry được đánh địa chỉ các node gồm F ký tự. Splitstream sẽ chọn ra các luồng có tên là 0x , 1x , … Fx để các node sau khi gia nhập vào cây multicast đa luồng có thể đảm bảo. Node có id bắt đầu là 0x sẽ là node trong của cây multicast stripeId 0x và là node lá của tất cả các luồng còn lại. Tương tự Node có id bắt đầu là 1x se là node trong của cây multicast stripeId 1x và là lá của tất cả các luồng còn lại… 23 Tuy nhiên Splitstream sẽ gặp vấn đề tại các máy( peer ) tham gia mà nếu chỉ đơn thuần lựa chọn các cây Scribe để truyền các luồng vào thì là chưa đủ đáp ứng tính chất multicast :  Không giới hạn dc băng thông đi ra của 1 peer do nhu cầu join của các peer khác: khi 1 peer đã bị vượt quá băng thông giới hạn đi ra thì các peer khác vẫn muốn gia nhập vào luồng của peer này. Nếu vẫn duy trì cơ chế như cây Scribe thì sẽ có 1 số peer thật sự không nhận được dữ liệu từ 1 vài luồng do node cha của nó không gửi dữ liệu thực sự đến cho nó Splistream sử dụng cơ chế mới để giải quyết vấn đề tại các node mà băng thông đi ra đã bị vượt quá giới hạn. Cơ chế này bao gồm các bước :  B1. Xác định node cha: Hình 14. Xác định node cha khi băng thông đi ra vượt quá giới hạn Trong ví dụ trên node với id 080* đã bị limit outdegree ( băng thông đi qua vượt quá giới hạn ) thì nhận được yêu cầu join vào của node với id 001* ở luồng 0800. Node 080* sẽ xem xét lại tất cả các node con của nó để loại đi 1 node con. Hình 14.(1)-(2) là trường hợp có node con 9* nhận node 080* làm cha trong luồng 1800 khác với luồng 0800. Node 080* sẽ nhận node 001* làm con và loại bỏ node 9*. Sau đó node 085* lại yêu cầu join vào node 080* .Hình 14.(3)-(4) là trường hợp các node con đều nhận 080* là cha trong luồng 0800 , xét đến id của các node con. Node 001* la node có id với số ký tự tính từ trái 24 sang phải khác với luồng 0800 nhất. Node 001* sẽ trở thành node orphan và node 085* được nhận làm node con.  B2. Nếu sau Bước 1 vẫn có node orphan (tức là node chưa tìm được node cha) sẽ tiến hành bước này. Node orphan sẽ gửi unicast đến SCG (Spare Capacity Group) để tìm được node cha. SCG là tập hợp tất cả các node mà băng thông đi ra chưa vượt quá giới hạn . Với cơ chế truyền unicast , node orphan sẽ gửi thông điệp tìm node có luồng mà băng thông đi ra chưa vượt quá giới hạn để nhận nó làm node cha. Ƣu điểm : xây dưṇg cây multicast đa luồng khá đơn giản dưạ vào kết cấu có sẵn của Pastry và Scribe . Khi maṇg ổn điṇh và việc phân chia định danh là khá đều thì các node trong hê ̣thống chiụ tải tương đương nhau . Thêm vào đó là các cơ chế tìm node cha nhằm đảm bảo các node trong maṇg không bi ̣ quá tải . Nhƣơc̣ điểm : không đảm bảo đươc̣ đô ̣chênh lêc̣h đô ̣trê ̃các luồng nhâṇ đươc̣ taị các node là nhỏ do việc tạo cây Scribe mang tính ngẫu nhiên dựa chủ yếu vào kết cấu bên dưới của Pastry. 25 Chƣơng 3.Xây dựng cây multicast đa luồng thời gian thực trên mạng ngang hàng có cấu trúc Sau khi đã nghiên cứu các giải pháp hiện nay về truyền tin multicast đa luồng với các ưu nhược điểm riêng khi ứng dụng sang truyền tin multicast đa luồng thời gian thực thì ở chương ba này sẽ là giải pháp mà tôi đưa ra trong khóa luận. Giải pháp này đã hướng đến mục tiêu là truyền tin multicast đa luồng thời gian thực ngay từ đầu nên nó sẽ có những ưu điểm riêng. Tuy nhiên bên cạnh đó cũng có những nhược điểm nhất định. Phần đánh giá về chương trình mô phỏng sẽ được trình bày ở chương bốn. Giải pháp này được xây dựng dựa trên giao thức DHT tham khảo bảng định tuyến của Chord.. 3.1.Vấn đề cần giải quyết Mục tiêu lớn nhất khi xây dựng cây multicast đa luồng thời gian thực trong mạng ngang hàng có cấu trúc là:  Xây dựng cây multicast đa luồng  Duy trì cây mulitcast khi mạng thay đổi  Cân bằng băng thông đi ra tại các node trong mạng : hạn chế các node không gửi dữ liệu cho node nào , các node phải gửi nhiều hơn số luồng giới hạn là không quá lớn  Độ trễ của một node khi nhận được tất cả các luồng là nhỏ  Chênh lệch độ trễ tại một node giữa luồng nhận được sớm nhất và nhận được muộn nhất là nhỏ (đây chính là mục tiêu quan trọng nhất của thiết kế) Trong khuôn khổ khóa luận giới hạn nên giải pháp của tôi đưa ra mới chỉ là bước đầu , chưa được tối ưu hóa để có thể đáp ứng tất cả các vấn đề cần giải quyết. Quá trình chạy chương trình mô phỏng tuy chưa được tốt như mong muốn nhưng đã cho thấy kết quả khả quan và cho thấy khả năng phát triển của giải pháp này. 3.2.Ý tƣởng Ý tưởng đưa ra được dựa trên thiết kế chính của Chord với các ưu điểm: 26  Đảm bảo rằng khi 1 node muốn gửi dữ liệu đến 1 điểm nào đó trên vòng tròn định danh thì chắc chắn sẽ có 1 node thực sự đảm nhiệm việc quản lý vị trí đó (đây chính là việc tìm Successor trọng mô hình Chord)  Việc xây dựng bảng Finger Table một cách thông minh để đảm bảo 1 node muốn tìm 1 node khác bất kỳ trên vòng tròn định danh thì chỉ phải mất tối đa log2n bước. Các ưu điểm trên của Chord sẽ được áp dụng vào thiết kế bảng Finger Table tại các node trong mạng. Vấn đề chính là cách xây dựng và phân chia luồng để giải quyết các vấn đề đặt ra trong vòng tròn định danh với 2 ý tưởng cơ bản :  Mỗi node sẽ kiếm soát vùng gần và vùng xa. Sau đó phân chia các vùng gần vùng xa ấy cho các node con tùy thuộc vào số con mà nó có. Việc xây dựng đệ quy như thế sẽ chia nhỏ dần các vùng và đảm bảo tất cả các node có mặt trong mạng đều nhận được dữ liệu. Sau khi đã xác định được các node con thì các node đó sẽ được lưu vào bảng Finger Table để lần truyền dữ liệu tiếp theo diễn ra nhanh chóng  Các node gốc gửi đi các luồng sẽ đảm nhiệm các vùng gần và vùng xa đan xen nhau nhằm đảm bảo tính hiệu quả của quá trình xây dựng cây multicast Hình 15. Phân chia vùng gần vùng xa cho các node con Hình 15 thể hiện ý tưởng cơ bản của việc phân chia các vùng gần và vùng xa. 27 Trong ví dụ có 4 node gốc sẽ gửi đi 4 luồng. Node Source 1 đảm nhiệm vùng gần (source 1 , source 2) : tức là nó sẽ là node gốc trong luồng 1 và các node nằm trong vùng định danh từ source 1 đến source 2 sẽ là các node con và cháu. Đồng thời Node Source 1 đảm nhiệm vùng xa (source 2 , source 1). Source 1 sẽ gửi đến 1 node trong vùng xa từ source 2 đến source 1. Lần lượt các node con cháu của source 1 cũng sẽ gửi đến 1 node trong vùng xa từ source 2 đến source 1 bằng việc làm nhỏ dần các vùng xa. Trong ví dụ source 1 sẽ gửi dữ liệu đến cho 3 node con vùng gần và 1 node con vùng xa. 3 node con vùng gần này sẽ đảm nhiệm các vùng gần và vùng xa nhỏ dần. Tương tự với các node source 2, 3 , 4. 3.3.Thiết kế giải pháp Bây giờ ta sẽ đi vào chi tiết giải pháp gồm 2 phần chính là xây dựng cây multicast và duy trì nó trong trường hợp các node rời mạng. Quá trình join và leave của các node trong mạng giống hệt như thiết kế trong mạng Chord. Quá trình tạo mới bảng Finger Table chỉ diễn ra khi xây dựng cây multicast. Ta sẽ tìm hiểu qua về việc xây dựng bảng Finger Table của các node và cách tìm kiếm successor trong Chord Chord được mô tả dưới dạng một vòng tròn và có không gian định danh cỡ N, với N là số bit định danh của không gian. Mạng Chord sẽ có thế chứa tối đa 2 mũ N Chord nút. Một Chord nút (hay một nút - một máy tính trong mạng Chord) có một định danh id, và các id trong mạng Chord sắp xếp thành vòng tròn và tăng theo chiều kim đồng hồ. Chord sử dụng một hàm băm để sinh định danh cho nút và tài liệu, đầu ra của hàm băm là một giá trị N bit. Để đảm bảo xác suất định danh trùng nhau là thấp, N phải đủ lớn. Với Chord, N thường là 160 bit. Một nút trỏ tới nút tiếp theo là nút có id lớn hơn, được gọi là Successor(id), và một nút nữa có id nhỏ hơn, được gọi là Predecessor(id). Các nút liên kết với nhau dựa vào Succcessor và Predecessor của nó. 28 Hình 16. Bảng Finger Table trong Chord Mỗi nút sẽ lưu một bảng định tuyến gọi là Finger Table (Hình 16). Thay vì phải tìm kiếm tuyến tính, bảng định tuyến cho phép một nút định tuyến tới các nút ở xa. Mỗi dòng trong bảng Finger Table sẽ lưu thông tin về 1 nút ở xa, gọi là 1 liên kết (entry). Entry thứ i sẽ lưu nút là successor của khóa có định danh cách định danh nút đang xét 2i theo chiều tiến của vòng Chord. Vì vậy, không gian định danh có bao nhiêu bit thì Finger Table có bấy nhiêu entry. Chord ánh xạ các khóa vào các nút, thường sẽ là một cặp key và value. Một value có thể là 1 address, 1 văn bản, hoặc 1 mục dữ liệu. Chord có thể thực hiện chức năng này bằng cách lưu các cặp key/value ở các nút mà key được ánh xạ (Hình 17). Một nút sẽ chịu trách nhiệm lưu giữ một khóa k nếu nút đó là nút có định danh id nhỏ nhất và lớn hơn k. Một nút khi lưu giữ khóa k cũng sẽ được gọi là Successor(k). Khi một nút cần tìm kiếm một khóa có định danh id, nút đó sẽ tìm nút chịu trách nhiệm lưu giữ id đó. Nếu nút ở xa so với vị trí của nút lưu giữ id, nút có thể nhờ vào thông tin trong bảng Finger Table để định tuyến đến các nút xa hơn, từ đó dần dần biết được nút chịu trách lưu giữ id. Một ví dụ được chỉ trong hình 17, giả sử nút 3 muốn tìm successor của ID (hoặc còn có thể coi là khóa) 1. ID 1 thuộc khoảng [7, 3), tức là 3.finger[3].interval. nút 3 kiểm tra entry thứ 3 trong bảng định tuyến của nó, là 0. Bởi vì 0 trước 1, nút 3 sẽ hỏi nút 0 để tìm successor của 1. Quay trờ lại, nút 0 sẽ suy ra từ bảng định tuyển rằng successor của 1 chính là nút 1, và trả về nút 1 cho nút 3. 29 Hình 17.Lưu giữ key trong mạng Chord 3.3.1.Xây dựng cây multicast Quá trình này bắt đầu từ 1 node gốc. Giả sử muốn xây dựng cây multicast k luồng. Đầu tiên các luồng sẽ được lựa chọn đưa vào k node gốc. Từ đây các node gốc này sẽ gửi dữ liệu đi khắp các node trong mạng. Trong Hình 18 là ví dụ với cây multicast 5 luồng. Node 1 sẽ là node gốc để truyền dữ liệu của luống 1 đến các node trong mạng. Node 1 này sẽ đảm nhiệm vùng gần từ idNode1 đến 5 21 NidNode  và vùng xa từ 5 21 NidNode  cho đến idNode1. Với N là số bit của không gian định danh. Việc đặt vùng gần và vùng xa cho node gốc đã đảm bảo chiếm hết vùng không gian định danh có thể để chắc chắn các node trong mạng đều nhận được dữ liệu Đầu tiên node 1 sẽ tìm successor của vị trí 5 21 NidNode  . Nếu successor của vị trí này không nằm ngoài khoảng vùng xa thì nó sẽ là node con vùng xa của node 1. Trên hình ta tìm được node 15. Node 1 sẽ chia vùng không gian của nó thành k - 1 = 4 vùng bằng nhau và xác định id tại các điểm đó. Sau đó node 1 tiến hành tìm successor của chính nó và successor tại các vị trí id mình đã chia 4 ở trên (trên hình vẽ là các vị trí đánh dấu x). Do thiết kế của mạng Chord nên có thể trong quá trình tìm kiếm không tìm được đủ 4 30 node con ở vùng gần. Node 1 sẽ tùy vào số node con mà gán vùng xa và vùng gần cho các node con tiếp theo. Trong hình ta tìm được 4 node con vùng gần là node 11 , 12 , 13 , 14. Bây giờ các node con sẽ lần lượt được giao nhiệm vụ quản lý các vùng gần và xa như sau. Node 11 sẽ kiểm soát vùng gần từ idNode11 đến vị trí X thứ 1 , Node 12 sẽ kiểm soát vùng gần từ idNode12 đến vị trí X thứ 2 , Node 13 sẽ kiểm soát vùng gần từ idNode13 đến vị trí X thứ 3 và Node14 sẽ kiểm soát vùng gần từ idNode14 đến 5 21 NidNode  . Hình 18.Tìm các node con gần và node con xa Vùng xa từ idNode15 đến idNode1 cũng được chia ra 4 phần và đặt cho các node con. Node 11 kiểm soát vùng xa idNode15 đến vị trí X thứ 4 , Node 12 kiểm soát vùng xa từ vị trí X thứ 4 đến vị trí X thứ 5 , Node 13 kiểm soát vùng xa từ vị trí X thứ 5 đến vị trí X thứ 6 , Node 14 kiểm soát vùng xa từ vị trí X thứ 6 đến idNode1. Như vậy node 1 đã xác định được các node con và giao nhiệm vụ cho các node con đó. Sau quá trình này các node con sẽ được lưu vào bảng Finger Table vào 4 dòng thêm vào : Successor( 5 21 NidNode  )= idNode15; Successor(idNode1) = idNode11; 31 Successor(X1) = idNode12; Successor(X2) = idNode13; Successor(X3) = idNode14; Các node 11 , 12 , 13 , 14 tiếp tục tìm các node con trong vùng gần và vùng xa của nó tương tự như thế. Quá trình này sẽ dừng lại khi 1 node không có node con gần nữa mà nó vẫn còn 1 vùng xa kiểm soát. Node này sẽ gửi unicast đến từng node trong vùng này bằng cách tìm Successor lần lượt của các node. Việc gửi unicast đến từng node có thể là quá lớn nên sẽ có 1 phương pháp nữa là các node không có node con gần sẽ gửi đến cho 5 node xa trong vùng xa và giao nhiệm vụ cho node cuối cùng tiếp tục gửi đi cho 5 node xa tiếp theo cho đến khi hết vùng xa. Cách xây dựng này sẽ không kiểm soát được tính cân bằng của cây multicast. Trong trường hợp tốt nhất là các node được phân bố đồng đều trên vùng không gian định danh id thì cây multicast xây dựng này sẽ rất tốt. Các node đồng cấp trên các luồng cây multicast khác nhau sẽ có chênh lệch độ trễ giữa các luồng là rất thấp (chỉ khoảng 1-3 bước). Hình 19. Node nhận được các luồng Hình 19 cho ta cái nhìn trực quan về một Node K khi nhận được các luồng. Trong luồng của chính nó (tức là nó là node trong ) sẽ mất 1 bước để K nhận được dữ liệu. Trong luồng thứ 2, 3, 4 (các luồng mà nó là node lá) sẽ mất 2 bước để K nhận được dữ liệu do việc phân chia vùng đồng đều như trên. Giao thức DHT và quá trình 32 random có thể phần nào đảm bào được tính đồng đều khi phân chia dịnh danh trên vòng tròn định danh. 3.3.2.Duy trì cây multicast khi có node rời khỏi mạng Khi 1 node rời khỏi mạng thì các node con cháu của nó sẽ không tiếp tục nhận được dữ liệu và các node con cháu đó sẽ cần phải có node cha mới. Hình 20. Sửa cây multicast khi có node rời khỏi mạng Hình 20 là ví dụ Node 4 rời khỏi mạng. Các node con trực tiếp của nó sẽ tìm node cha mới. Node 0 trong quá trình cập nhật bảng định tuyến biết được node 4 là node con của nó đã rời khỏi mạng. Các node con của node 4 sẽ gửi yêu cầu tìm node cha mới đến node 0 (idNode0 đã được lưu vào bảng định tuyến của các node này). Node 0 sẽ gửi thông điệp tìm node cha mới của các node con này đến node lá của 1 nhánh node con nào đó của nó. Ở đây node cha mới tìm được là Node M. Quá trình tìm kiếm mất logkn bước với n là số các node con của node 1. Node M sẽ cập nhật các node con mới của nó vào bảng định tuyến. Các node cháu trong vùng nét đứt sẽ không có ảnh hưởng gì vì với việc thiết kế truyền tin multicast mỗi node chỉ cần biết các node con trực tiếp của nó. Việc tìm node lá trong 1 nhánh node con sẽ đảm bảo node lá không phải tải băng thông đi ra quá lớn.Tuy nhiên việc tìm node lá sẽ cần mất logkn bước cũng là 1 yếu điểm của việc duy trì cây multicast này. 33 Chƣơng 4.Mô phỏng và đánh giá Việc mô phỏng và đánh giá là bước rất quan trọng để xem xét tính khả thi của giải pháp đặt ra. Nếu mô phỏng cho kết quả tốt thì giải thuật đưa ra có thể khả thi để ứng dụng vào thực tế. Xây dụng mạng mô phỏng giống với thực tế là rất khó do tính phức tạp trong hệ thống mạng ngang hàng có cấu trúc. Trong khóa luận trước của anh Đặng Ngọc Bền đã xây dựng lên 1 mô hình mạng khá tốt , đáp ứng phần nào tính phức tạp trên lý thuyết nên tôi đã sử dụng cấu trúc mạng của anh nhằm phát triển cho khóa luận của mình. Sau đây là chi tiết về chương trình mô phỏng 4.1. Chƣơng trình mô phỏng Chương trình mô phỏng gồm hai phần chính là dữ liệu và thực thi. Phần dữ liệu bao gồm các loại dữ liệu và phần mã nguồn chương trình tạo ra chúng. Thực thi chính là phần mô tả hoạt động của mạng ngang hàng dựa trên giao thức DHT và quá trình truyền tin multicast đa luồng trong mạng. Ngoài ra còn phải kể đến kiến trúc mạng mô phỏng cho tầng dưới – tầng liên kết vật lý. 4.1.1.Kiến trúc mạng mô phỏng Để có thể thực hiện được quá trình mô phỏng, trước tiên chúng ta cần có một mô hình mạng tầng liên kết vật lý với thời gian trễ giữa các nút trên mạng. Topo của mạng mô phỏng rất quan trọng vì nó quyết định việc thử nghiệm, kết quả và đánh giá hiệu năng của những cải tiến. Hình 21. Mô hình mạng thực tế 34 Mô hình mạng mô phỏng được xây dựng sau đây phần nào sẽ thể hiện được tính phức tạp và không ổn định trên Internet của độ trễ giữa các nút (gây ra do khoảng cách vật lý , môi trường đường truyền). Cụ thể như sau : - Các node tham gia vào mạng sẽ nằm được xét nằm trong một miền nhất định. Mỗi một miền sẽ có 1 node switch được xem là node trung tâm và các node khác sẽ liên lạc với các node bên ngoài miền thông qua switch này. - Từ đó việc xác định độ trễ giữa 2 node bất kỳ trong mạng được tính bằng độ trễ nội miền của node 1 + độ trễ nội miền của node 2 + độ trễ liên miền 1 và 2. Trong đó độ trễ nội miền của 1 node được tính bằng độ trễ từ node đó đến node switch của miền , độ trễ liên miền được cố định từ đầu và được xem là độ trễ giữa 2 switch của 2 miền đó. - Độ trễ liên miền được cố định từ đầu , độ trễ nội miền của 1 node sẽ được thay đổi trong quá trình sinh mới dữ liệu nhằm phần nào thể hiện tính không ổn định của độ trễ trên Internet. 4.1.2.Các tham số trong mạng mô phỏng Các đối tượng tham gia mô hình mạng :  Area: Đối tượng này lưu trữ tên miền , các thao tác với tệp dữ liệu miền , quan trọng nhất là xác định độ trễ liên miền  NodeLocation Xác định một node nằm trong vùng nào.  FingerEntry Thể hiện một liên kết (entry) trong bảng định tuyến. Thuộc tính idSuccessor với ý nghĩa là định danh successor của khóa mục tiêu tại entry đang xét. Khi định tuyến chúng ta quan tâm đến thuộc tính này. Các finger entry thiết kế trong giải pháp này mới chỉ dùng lại của Chord , chưa thêm vào trong quá trình truyền tin multicast như mong muốn. Do quá trình truyền tin multicast sẽ được thực hiện khi đã ổn định mạng nên việc thêm vị trí các node con vào bảng định tuyến là không cần thiết nên sẽ không được thể hiện trong chương trình mô phỏng này.  Node Lưu trữ các dữ liệu và các đối tượng con của một node bao gồm : định danh của node , successor, predecessor , bảng định tuyến , mảng vùng gần , vùng xa (sẽ được 35 đặt đệ quy từ các node cha cho các node con) , thời gian trễ nhận được của các luồng (đây là thông tin để xác định tính hiệu quả của giải pháp về độ trễ) , outbound bandwith – băng thông đi ra (thông tin xác định số luồng ra mà 1 node phải gửi). Các phương thức quan trọng: nextNode(): tìm node tiếp theo dựa vào bảng định tuyến , setFarRegion , setNearRegion , setDelayTime , setOutBandwith : là những hàm đặt xác định khoảng xa , gần , độ trễ , băng thông đi ra tại mỗi node.  Network Đây là đối tượng chính, cơ bản nhất trong chương trình mô phỏng. Đối tượng lưu trữ thông tin tạo lên một topo mạng mô phỏng, thể hiện quá trình churn (join, leave của node khi tham gia vào mạng), multicastMsg (truyền tin multicast k luồng khi mạng đã ổn định). Các phương thức cơ bản : - birth(), death(): Thực hiên khi có một nút tham gia hay rời khỏi mạng. - fixFingerTables(): Cập nhật bảng định tuyến của tất cả các nút trong mạng. Hàm thực hiện sau khi có một loạt quá trình vào ra của các nút làm cho bảng định tuyến trở lên lỗi thời. - findSuccessor(): Tìm successor của một nút. - findChildNode(): Tìm các node con của 1 node và thực hiện các thao tác gán vùng cho các node con đó . - sendMsg() : Truyền tin multicast đến 1 node. - multicastMsg() : Là hàm quan trọng nhất. Hàm này sẽ truyền tin multicast đến các node gốc và từ đây đệ quy đến tất cả các node con trong mạng  InputGenerator Đối tượng chứa các phương thức để tạo ra các tệp dữ liệu như đã mô tả phần trên. Dữ liệu để cho chương trình có thể vận hành gồm bốn tệp, tương đương có bốn phương thức tạo tệp riêng. Các dữ liệu miền, dữ liệu nút và truy vấn được sinh theo phân bố đều một cách ngẫu nhiên với các giá trị giới hạn là các tham số mô tả trong lời gọi phương thức. Riêng dữ liệu về độ bất ổn (churn) được sinh theo luật phân bố Pareto. Đây là luật phân bố khá phổ biển và đúng đắn trong nhiều lĩnh vực.  Distribution Đây là đối tượng cho phép sinh các giá trị theo luật phân bố Pareto như đã nêu. Sau 36 khi khởi tạo bằng các hằng số đặc trưng cho loại phân bố này, đối tượng cho phép sinh một giá trị theo luật bằng phương thức next().  Thƣ viện hash Một thư viện nhỏ chứa hàm băm sha-1. Thư viện là mã nguồn mở với hai hàm băm tiêu biểu là sha và md5. Riêng sha, thư viện cung cấp nhiều hơn một hàm, do yêu cầu số lượng bit của kết quả (160, 256, 512,…). Do nhu cầu sử dụng là nhỏ nên chương trinhg mô phỏng chỉ thêm hàm băm sha với số lượng bit của kết quả là 160. Thư viện sử dụng khá dễ dàng với API là các phương thức mô tả đơn giản.  Các hàm toán học Khá nhiều hàm liên quan đến toán học và những con số. Những hàm này rất cần thiết, phục vụ hầu hết các quá trình tính toán trong chương trình. Đáng kể là hàm băm hash(). Đầu vào của hàm là tên của một nút, đầu ra là một định danh 32 bit. Chương trình mô phỏng chỉ sử dụng không gian định danh 32 bit vì nhu cầu chỉ cần như vậy. 32 bit này được trích từ những bit đầu tiên của giá trị băm có được từ thư viện hashlib++ [12] với 160 bit độ dài. 4.2.Kết quả và đánh giá Đây là phần trình bày kết quả và đánh giá sau khi thực thi chương trình mô phỏng. Quá trình sẽ so sánh kết quả đạt được khi thực hiện với lần lượt 1037 , 2098 node tham gia và chia ra 4 , 8 , 16 luồng. 4.2.1.Hiệu quả độ chênh lệch số hop nhận đƣợc các luồng tại các node Chương trình thử nghiệm với 2048 node tham gia vào 16 miền. Sau quá trình vào ra mạng ổn định với 1014 node. Đồ thị biểu diễn độ chênh lệch của 1014 node này khi chia ra 4 , 8 , 16 luồng. 37 Hình 22. Chênh lệch hop lớn nhất giữa các luồng với 1014 node Trục tung là số hop chênh lệch lớn nhất nhận được các luồng tại các node trong khoảng từ 0 đến 6. Theo kết quả mô phỏng nhận được : dù chia ra 4 , 8 , 16 luồng thì chênh lệch hop lớn nhất giữa các luồng nhận được tại các node đều rất nhỏ và chủ yếu tập trung ở 1 , 2 , 3 hop , các node khác nhận được chênh lệch cao hơn từ 4 đến 6 là rất ít. Việc tăng các luồng lên làm cho số node chênh lêc̣h 2 hop giữa các luồng nhâṇ đươc̣ tăng lên. Tuy nhiên viêc̣ tăng luồng laị làm giảm các node nhâṇ đươc̣ các luồng chênh lêc̣h lớn (4 , 5 , 6). Các kết quả nhận được đã cho thấy hiệu quả cao và phù hợp với lý thuyết đề ra. Có thể thấy việc phân bố các node trên vòng tròn định danh là khá đồng đều nên chênh lệch giữa các luồng nhận được là bé (do các node đồng cấp giữa các luồng cây multicast khác nhau có xác suất gửi trực tiếp cho nhau khá cao). Chương trình thử nghiệm với 4096 node tham gia 32 miền. Sau khi các node vào ra thì mạng ổn định với 2072 node. 38 Hình 23. Chênh lệch hop lớn nhất giữa các luồng với 2072 node Thử nghiệm với 2072 node vâñ thể hiêṇ tính hiệu quả của giải thuật . Khi chia thành nhiều luồng hơn thì chênh lệch các hop lại càng tâp̣ trung ở mức 2. Nghĩa là các node trên maṇg có xu hướng nhâṇ đươc̣ các luồng chênh lêc̣h nhau 2 hop khi ta tăng số luồng lên. Kết quả mô phỏng nhâṇ đươc̣ đa ̃cho thấy hiêụ quả khá tốt về viêc̣ làm giảm chênh lêc̣h hop giữa các luồng nhằm đảm bảo chất lươṇg truyền tin multicast đề ra. 4.2.2.Hiệu quả độ cân bằng tải trên toàn hệ thống Thử nghiệm với 2048 node tham gia 16 miền. Mạng ổn định có 1014 node. Hình 24. Hiệu quả cân bằng tải với 1014 node 39 Kết quả trên chỉ ra số luồng trung bình 1 node phải gửi đi taị 1 thời điểm. Có thể thấy hầu hết các node đều đóng góp vào hê ̣thống toà n maṇg. Giải pháp đưa ra không hướng tới tính đồng đều về cân bằng tải mà chỉ hướng tới haṇ chế chênh lêc̣h hop nhâṇ đươc̣ giữa các luồng nên không có nhiều nhâṇ xét về đồ thi ̣ này . Thử nghiệm với 4096 node tham gia 32 miền. Mạng ổn định có 2072 node. Hình 25. Hiệu quả cân bằng tải với 2072 node Kết quả thu được tương tự như với 1014 node. Với 2072 node , các node trong mạng hầu như đều có đóng góp. 40 Chƣơng 5.Kết luận 5.1.Kết luận Khóa luận đã đưa ra cái nhìn tổng quan về truyền tin multicast trên mạng ngang hàng có cấu trúc và tiềm năng phát triển các ứng dụng này trong thời gian tới . Với viêc̣ đánh giá Splitsream và dưạ vào kiến thức cơ bản của mô hình maṇg ngang hàn g cũng như truyền tin multicast khóa luâṇ đa ̃chỉ ra đươc̣ những vấn đề cần đươc̣ giải quyết như chênh lêc̣h thời gian trê ̃giữa các luồng nhâṇ đươc̣ , đô ̣trê ̃trên toàn maṇg nhằm nâng cao hiêụ suất của truyền tin multicast đa luồng thời gian thưc̣. Dưạ vào các yêu cầu đăṭ ra đó , khóa luận đã đề ra một giải pháp mới về việc xây dưṇg môṭ mô hình truyền tin multcast đ a luồng thời gian thưc̣ dưạ trên giao thức DHT . Bàng định tuyến của thiết kế này dựa vào ý tưởng của Chord đã tỏ ra có hiệu quả đối với môi trường không ổn điṇh như của maṇg ngang hàng có cấu trúc . Ý tưởng chủ đạo của giải pháp là các node xác định được các node con của nó trong mỗi môṭ luồng multicast và ghi vào bảng định tuyến. Cách thiết kế phân vùng quản lý nhằm tìm ra các node con môṭ cách hiêụ quả dưạ trên vòng tròn điṇh danh đa ̃đưa tới môṭ xác suất cao các node con đồng cấp ở các luồng multicast khác nhau sẽ có xu hướng truyền dữ liêụ cho nhau. Khóa luận cũng trình bày chương trình mô phỏng để đánh giá giải pháp đưa ra và đa ̃cho thấy kết quả khá tốt khi cho thấy phần lớn các node trên toàn maṇg có đô ̣chênh lêc̣h hop giữa các luồng nhâṇ đươc̣ là nhỏ (1 – 3 hop). Thử nghiêṃ với 2032 node ứng với 16 miền , sau khi maṇg ổn điṇh có 1014 node và 4096 node ứng với 32 miền , sau khi maṇg ổn điṇh có 2072 node. 5.2.Hƣớng phát triển tiếp theo của đề tài Kết quả mô phỏng đa ̃cho thấy tiềm năng của giải pháp đưa ra , tuy nhiên đấy chỉ là một mạng mô phỏng không thể hiện được rõ sự phức tạp như môi trường Internet thưc̣ tế. Vì thế hướng phát triền tiếp theo của đề tài phải nhằm đến tối ưu hó a giải pháp trên Internet với các điṇh hướng như sau:  Tối ưu hóa giao thức DHT nhằm phân vùng các điṇh danh trên vòng tròn môṭ cách đồng đều . Viêc̣ phân vùng này càng tốt thì tính hiêụ quả của giải pháp càng đươc̣ tăng lên. 41  Cải tiến việc phân vùng sao cho hiệu quả . Với ý tưởng phân vùng là chính thì trong chương trình mô phỏng đa ̃sử duṇg viêc̣ phân vùng dưạ vào viêc̣ chia đều các khoảng (tức là các node cùng cấp trong cùng cây multicast se ̃có cá c vùng kiểm soát nhằm xác định node con đều nhau ). Viêc̣ phân vùng này nếu găp̣ trường hơp̣ các node phân bố không đồng đều sẽ làm cây multicast có độ cao lớn hơn mong đơị. Vì thế có thể hướng tới một cách phân vùng không đều nhằm đưa đến hiêụ quả cao hơn.  Viêc̣ câp̣ nhâṭ laị bảng điṇh tuyến để xây dưṇg laị cây multicast khi có node vào ra chịu độ trễ khá lớn logkn . Cách sửa cây multicast do vậy cần phải được tối ưu hơn . 42 Tài liệu tham khảo Tiếng Việt [1] Đặng Ngọc Bền – Tối ưu hóa topology cho maṇg ngang hàng có cấu trúc Chord . June 2009 Tiếng Anh [2] Antony Rowstron et. el. “Pastry : scalable , distributed object location and routing for large-scale peer-to-peer system” [3] Dapeng Wu et. el., “Streaming Video over the Internet: Approaches and Directions”, IEEE Trans. Circuit and Systems, 2001 [4] Ion Stoica et. el. “Chord : A scalable peer-to-peer lookup service for internet applications. SIGCOMM‟01. ACM, New York. 2001. [5] Miguel Castro et. el. “Scribe : A large-scale and decentralized application-level multicast infrastructure” [6] Miguel Castro et.el., “SplitStream: High-Bandwidth Multicast in Cooperative environments”, SOSP‟03 [7] Suman Banerjee et. el “A comparative Study of Application Layer Multicast Protocol [8] Zhengye et.el. , “Using Layered Video to Provide Incentives in P2P Live Streaming”, IPTV-2007 43 Phụ lục A A.1. Định dạng dữ liệu Thông tin miền - Dòng đầu tiên chứa một số nguyên n là số lượng miền. - n*(n+1)/2 dòng tiếp theo, mỗi dòng có cú pháp là a b l. Trong đó, a và b là định danh miền, l là thời gian trễ liên miền giữa hai miền a và b. 32 0 1 171 0 2 161 Thông tin nút - Dòng đầu số nguyên N là số lượng nút tối đa. - N dòng sau, mỗi dòng có cấu trúc a s. Trong đó, a là chỉ số nút, s là định danh miền mà nút đó thuộc về. 4096 0 18 1 30 Thông tin sự vào ra (churn) Gồm nhiều dòng, mỗi dòng có cấu trúc t c a l. Trong đó, t là nhãn thời gian, thời điểm xảy ra sự kiện; c là loại sự kiện, „b‟ là nút tham gia, „d‟ là nút rời đi khỏi mạng, giá trị „q‟ khi quá trình churn kết thúc; a là chỉ số của nút; l là thời gian trễ nội vùng của nút đó. 00000 b 996 7 00000 b 998 25 00001 b 1003 1