Luận văn Truyền tin multicast đa luồng thờigian thực trên mạng ngang hàng có cấu trúc

ầ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