Đề tài Xây dựng ứng dụng luồng video streaming qua mạng ngang hàng

cha chỉ đơn giản là cung cấp các gói tin yêu cầu của mỗi con trong trình tự quy định và theo tỷ giá được xác định bởi các cơ chế kiểm soát tắc nghẽn. Mỗi phân đoạn của các nội dung được gửi đến các peer cá nhân tham gia trong hai giai đoạn: giai đoạn khuếch tán và tràn ngập giai đoạn. Trong giai đoạn khuếch tán, mỗi peer nhận được bất kỳ của một phân đoạn mới từ nút cha của nó ở mức cao hơn. Vì vậy, các mảnh của một phân đoạn mới được tạo ra đang dần dần kéo theo các đồng nghiệp ở các cấp độ khác nhau. Trong giai đoạn lụt, mỗi peer nhận được thấp hơn. Các cha được gọi là tràn ngập các nút cha. Mỗi phần của bất kỳ phân đoạn mới được lan tỏa thông qua một khuếch tán đặc biệt cây con trong giai đoạn khuếch tán của phân khúc đó. Sau đó, các phần có sẵn được trao đổi giữa các đồng nghiệp trong cây tổng, khuếch tán khác nhau thông qua các lưới tràn ngập trong giai đoạn tràn ngập của phân khúc này. Các ứng dụng của hai giai đoạn khác nhau cho phân phối nội dung dẫn đến hiệu quả sử dụng nguồn lực sẵn có để chứa khả năng mở rộng và cũng giảm thiểu nội dung nút cổ chai. Những bất lợi của PRIME là nếu nội dung nút cổ chai xảy ra, các nút phải chờ đợi lâu để tìm ra đơn vị dữ liệu cần thiết của họ sau khi một vài giai đoạn lụt, khi dữ liệu có sẵn trong khu vực của mình. Do đó, không có sự đảm bảo cho một mức độ hợp l của luồng trực tuyến chất lượng. Hơn nữa, các thuật toán không xem xét hành vi của các hệ thống P2P trong sự hiện diện của một thùng đựng. Đồ án tốt nghiệp đại học Chương II: Hệ thống luồng video qua mạng ngang hàng P2P Lê Ngọc Anh – D09VT2 45 Hình 2.20 Hai lớp lƣới/ cây che phủ trong mạng lai 2.4.1.8 HyPO HyPo là một lớp phủ lai P2P cho truyền thông đa phương tiện trực truyến. Tối ưu hóa các lớp phủ bằng cách tổ chức peer với các phạm vi có băng thông tương tự trong bất kì khu vực địa lý nào trong một lớp phủ lưới và tạo thành một lớp phủ cây bằng cách chọn các peer được ổn định. Hình 2.20 minh họa một lưới / cây che phủ hai lớp trong HyPO. Tùy thuộc vào cơ chế tối ưu hóa cây, trong đó các peer có một băng thông lớn sẽ được ở gần với nút nguồn trong các lớp phủ cây, và phân bố đều trong các cây với các nhánh với một chiều sâu tương tự. Do đó, việc tối ưu hóa cây làm giảm độ sâu trung bình của cây, do đó nâng cao khả năng mở rộng. Lưới trong HyPO không phải là một kết nối bổ trợ từ các peer trong lưới, thành viên luôn luôn cung cấp dữ liệu cho lưới cho đến khi nó trở thành một thành viên cây. Tuy nhiên, tất cả các thủ tục của HyPO rất ít dựa trên một máy chủ theo dõi, một khoảng thời gian liên tục có thể xảy ra nếu máy chủ bị lỗi. Hơn nữa, HyPO không đề cập đến cách làm sao dữ liệu được phân bố trong lớp phủ lưới của nó. 2.4.1.9 mTreebone mTreebone là một thiết kế cây lưới phối hợp thúc đẩy cả lưới và cấu trúc cây. Ý tưởng chính của mTreebone là xác định một nhóm các nút ổn định để xây dựng một cây dựa trên xương sống, các nút này được gọi là treebone với hầu hết các dữ liệu bị đẩy trên xương sống này. Các nút bền vững cùng với những nút khác, được tổ chức thành một lớp phủ lưới bổ trợ, tạo điều kiện cho treebone để phù hợp động lực của một nút và khai thác hoàn toàn băng thông giữa các nút lớp phủ. Các nút không ổn định khác được gắn vào xương sống như vùng bên ngoài. Hình 2.21 cho thấy một mô hình mTreebone. Trong sơ đồ này, kết nối lưới được gọi chỉ khi có một nút riêng biệt bị ảnh hưởng bởi sự ra đi của nút cha hay nút cha thất bại. Việc duy trì treebone và tối ưu hóa chỉ xảy ra tại các nút treebone và không có thêm chi phí cho các peer vùng ngoài xương sống. Thông thường, chất lượng truyền là tốt nhất cho các nút treebone do sự ổn định tốt của các con đường cung cấp dữ liệu của nó từ nguồn. Thách thức chính là chúng ta cần phải xác định tập hợp các nút lớp phủ ổn định và vị trí của nút tại các địa điểm thích hợp trong cây. Một yêu cầu như vậy có thể gây xung đột với băng thông và chậm trễ trong xây dựng cây. Một phát sinh khác khi xem xét về sự ổn Đồ án tốt nghiệp đại học Chương II: Hệ thống luồng video qua mạng ngang hàng P2P Lê Ngọc Anh – D09VT2 46 định của mTreebone là phụ thuộc vào các nút treebone, đó là các nút sẽ ở lại trong treebone trong khoảng thời gian bao lâu. Mặt khác, CliqueStream là một lớp phủ lai tương tự như mTreebone khai thác các thuốc tính của một nhóm lớp phủ P2P (hình 2.22). ClipueStream tìm ra một hay nhiều nút bền vững có băng thông cao nhất trong mỗi nhóm và giao cho các nút đó vai trò chuyển tiếp nội dung đặc biệt. Để duy trì hiệu quả truyền tải, một cây phân phối nội dung được xây dựng trên các nút bền vững sử dụng cấu trúc trong nền định tuyến cơ bản và nội dung sẽ được đẩy qua chúng. Các nút ít ổn định trong một nhóm sau đó tham gia vào việc phổ biến nội dung và kéo nội dung tạo ra một lưới xung quanh các nút bền vững. Hình 2.21 Khung mTreebone (a) một lớp phủ lai (b) xử lý trạng thái nút Hình 2.22 Cấu trúc trực tuyến trong CiqueStream Lai kéo – đẩy P2P treaming lớp phủ nổi lên như một giải pháp thay thế cho các phương pháp truyền thống như là cây và lưới. Kể từ khi thiết kế hệ thống lai làm đơn giản hóa việc xây dựng lớp phủ và các quy trình bảo dưỡng và đồng thời vẫn giữ được hiệu quả của mạng và đạt được kiểm soát tốt các nút quá tải. 2.5 Video theo yêu cầu trên P2P VoD (Video on Demand) hiện có đặt ra một số vấn đề như tính khả thi của giao thức multicast, máy chủ hỏng và chi phí triển khai bảo đưỡng các thiết bị định tuyến Đồ án tốt nghiệp đại học Chương II: Hệ thống luồng video qua mạng ngang hàng P2P Lê Ngọc Anh – D09VT2 47 lớp phủ cao. Tuy nhiên, video streaming dựa trên P2P cung cấp một kiến trúc thay thế cho các dịch vụ video theo yêu cầu. Trong một hệ thống VoD P2P, tất cả các peer là host có kết nối Internet, trong đó peer lưu trữ và các luồng video do khách hàng đề nghị. Chi phí của các peer truy cập Internet sẽ được chịu bởi khách hàng chứ không phải bởi các nhà cung cấp dịch vụ VoD. Bởi vì có một nguồn cung cấp phong phú của các peer cung cấp nguồn tài nguyên chưa được sử dụng như băng thông và lưu trữ, dựa trên kiến trúc P2P nên có chi phí ít hơn so với các giải pháp truyền thống client- server và giải pháp CDN. Áp dụng kỹ thuật luồng trực tuyến P2P vào luồng VoD không phải là một công việc dễ vì nhiều l do. Như hệ thống luồng trực truyến P2P, hệ thống P2P - VoD cũng cung cấp nội dung bằng luồng. Tuy nhiên, các peer có thể xem các gói khác nhau của một đoạn video cùng một lúc, do đó làm yếu đi khả năng giúp đỡ lẫn nhau. Hệ thống VoD có khả năng cho phép người dùng bắt đầu xem một đoạn video sau khi chờ đợi một thời gian, trong khi vẫn tiếp tục tải video về. Mặc dù, trễ end-to-end của luồng trực truyến ngắn nhưng vẫn gây khó khăn cho người sử dụng. Do đó, một cây ngắn bắt nguồn tại máy chủ video và kéo dài trên peer không phải là điều mong muốn trong truyền tải VoD. Người sử dụng sẽ có thể xem video tại một thời gian tùy , không giống như trong truyền hình trực tiếp họ cần phải đồng bộ hóa thời gian xem. Người sử dụng cũng sẽ có thể thực hiện các hoạt động kiểm soát như tua lại, lùi về phía trước ..vv trên video. Ví dụ, một peer có thể chặn xem một luồng VoD khi đó QoS của hệ thống giảm, nhưng các peer khác có thể không làm điều tương tự cho một luồng vì nó không có tùy chọn xem lại. Nếu QoS của các luồng video giảm, sẽ có nhiều các peer rời hệ. Điều này cho thấy tầm quan trọng của một giao thức phục hồi trong một hệ thống luồng VoD. Các giao thức kết nối lại các peer bị bỏ rơi, do đó không có mất mát nội dung và không trễ lâu. Một yêu cầu quan trọng của một dịch vụ VoD là khả năng mở rộng. Một hệ thống VoD cho phép một peer mới tham gia hệ thống nhanh. Thời gian tham gia ngắn, yêu cầu tham gia của các peer đến hệ thống ở các thời điểm khác nhau. Dự kiến hệ thống phải truyền tải các video cho tất cả các peer mà không làm cho máy chủ trở thành một nút cổ chai. Hệ thống VOD P2P thường yêu cầu người dùng đóng góp dung lượng lưu trữ vì các hệ thống này cần kích thước bộ đệm rất lớn để đáp ứng các yêu cầu đa dạng từ các peer khác nhau. Không gian lưu trữ này thường là 1 GB trong PPLive. Có hiệu lực sau khi người dùng cài đặt PPLive và chạy hệ thống lần đầu tiên, người dùng có thể nhìn thấy một loại file chưa biết 1 GB tồn tại trong bộ nhớ máy. Như hệ thống video streaming, hệ thống VoD P2P thường được phân loại dựa trên cây và hệ thống dựa trên lưới. 2.5.1 Hệ thống VoD dựa trên dạng cây Nhiều người dùng sử dụng mạng che phủ dạng cây được đồng bộ và nhận nội dung theo thứ tự các máy chủ sẽ gửi đi. Vấn đề chính trong hệ thống VoD dựa trên Đồ án tốt nghiệp đại học Chương II: Hệ thống luồng video qua mạng ngang hàng P2P Lê Ngọc Anh – D09VT2 48 cây là việc thiết kế cây và các thủ tục cho người dùng tham gia vào hệ thống. P2Cast và P2VoD là những ví dụ của hệ thống VoD dựa trên cây. P2Cast là một mô hình vá lỗi (patching) ban đầu cho hệ thống VoD. chương trình đề xuất để hỗ trợ sử dụng dịch vụ VoD có nguồn gốc IP multicast. P2Cast giải quyết hai vấn đề kỹ thuật quan trọng như xây dựng một lớp phủ thích hợp cho các tuyến và cung cấp một luồng tin liên tục phát lại khi một khách hàng ra khỏi hệ thống. Số lượng khách hàng đến một ngưỡng nhất định tạo thành một phiên. Đối với mỗi phiên máy chủ cùng với các khách hàng P2Cast tạo thành một cây đa luồng ở lớp ứng dụng trên mạng unicast. Các khách hàng trong P2Cast có thể chuyển tiếp các luồng video cho các khách hàng. Mỗi khách hàng tích cực góp phần băng thông và không gian lưu trữ cho hệ thống đồng thời tận dụng các nguồn tài nguyên tại các khách hàng khác. Toàn bộ video được truyền trực tiếp trên cây đa luồng ở lớp ứng dụng, để nó có thể được chia s giữa các khách hàng. Đối với khách hàng tham gia muộn hơn các khách hàng đầu tiên trong phiên giao dịch và do đó bỏ lỡ một đoạn ban đầu của video, đoạn thiếu này có thể được lấy từ máy chủ hoặc máy khách hàng khác có lưu trữ đoạn ban đầu. P2Cast có thể phục vụ nhiều khách hàng so với dịch vụ unicast client-server truyền thống. Các chương trình phục hồi trong P2Cast cho phép các đồng nghiệp nhận dữ liệu từ máy chủ trực tiếp khi các nút cha tách ra. Tuy nhiên, điều này làm tăng khối lượng công việc của máy chủ. P2VoD là một mô hình video theo yêu cầu dạng cây mà nó cố gắng để giải quyết các vấn đề của việc kết nối nhanh, cung cấp nhanh chóng và phục hồi thất bại cục bộ, xử l hiệu quả các yêu cầu không đồng bộ của khách hàng và cung cấp chi phí quản l nhỏ so với P2Cast. Mỗi khách hàng trong P2VoD có một bộ đệm FIFO kích thước thay đổi để lưu trữ các nội dung gần đây nhất của luồng video nhận được. Tồn tại những khách hàng trong P2VoD có thể chuyển tiếp các luồng video tới một khách hàng mới miễn là họ đủ băng thông đầu ra và vẫn giữ khối đầu tiên của tập tin video trong bộ đệm. Mô hình bộ nhớ đệm cho phép một nhóm các khách hàng, đến với hệ thống tại thời điểm khác nhau, để lưu trữ các nội dung video giống nhau trong tiền tố của các bộ đệm của nó. Nhóm như vậy hình thành một phiên. Khi một thành viên của một phiên rời hệ thống, bất kỳ thành viên còn lại của phiên có thể cung cấp video mà không có biến động tới các peer con bị bỏ rơi của các thành viên rời đi với điều kiện băng thông đầu ra quy định là đủ. Trong P2VoD, một kết nối luồng được giả định là tốc độ bit không đổi, bằng với tốc độ phát lại của video. Quá trình phục hồi trong VoD là phức tạp hơn. Ngoài ra, P2VoD không xem xét các băng thông không đồng nhất của các peer. Bộ nhớ đệm và chuyển tiếp là một cách tiếp cận dựa trên cây, là nơi mà một khách hàng VoD thường dựa trên nội dung được lưu trong bộ đệm của các peer cha của nó. Trong mô hình này, các bộ định tuyến không thực hiện chức năng multicast. Do đó, các host cuối chịu trách nhiệm cho việc lưu trữ và phân bố của luồng tin đa phương tiện. Các host cuối có thể là các máy khách hàng hoặc các proxy của nó và các hệ Đồ án tốt nghiệp đại học Chương II: Hệ thống luồng video qua mạng ngang hàng P2P Lê Ngọc Anh – D09VT2 49 thống này duy trì các đối tượng truyền thông trong bộ nhớ cục bộ tạm thời của họ. Nếu một khách hàng yêu cầu các đối tượng truyền thồng về sau, máy chủ gốc có thể chuyển tiếp các yêu cầu tới các host cuối. Ostream tận dụng khả năng đệm của host cuối bằng cách sử dụng bộ nhớ cache và phương pháp lưu trữ và chuyển tiếp. Mô hình sử dụng một thuật toán cây mở rộng cho các peer để xây dựng một lớp phủ cho truyền thông trực tuyến. ostream làm giảm sự thiểu sự thiếu hiệu quả của topo như trễ liên kết và kéo dài được giới thiệu bằng cách sử dụng multicast lớp ứng dụng. Hình 2.23 Cấu trúc DirectStream Một khung làm việc được gọi là DirectStream cho phép khách hàng tận dụng những lợi ích của khoảng thời gian bộ nhớ đệm và dịch vụ video theo yêu cầu với sự hỗ trợ hoạt động VCR . DirectStream bao gồm một máy chủ chỉ dẫn, máy chủ nội dung và khách hàng. Máy chủ chỉ dẫn hoạt động như một điểm trung tâm hành chính. Nó duy trì một cơ sở dữ liệu theo dõi của tất cả các máy chủ và khách hàng tham gia trong DirectStream và giúp khách hàng mới xác định các dịch vụ cần thiết. Các máy chủ nội dung cung cấp các chức năng tương tự như trong mô hình client – server truyền thống lưu trữ nội dung trong kho lưu trữ của nó và phục vụ yêu cầu của khách hàng, miễn là đủ băng thông có sẵn. Do đó khách hàng trong DirectStream có chức năng như nút P2P. Một peer lưu trữ một cửa sổ chuyển động của một nội dung được nhận được mới nhất và phục vụ những peer đến muộn bằng cách liên tục chuyển tiếp các nội dung được lưu trữ. Một tập hợp các khách hàng hoạt động trong một lớp phủ P2P streaming được thành lập được gọi là một nhóm. Các nhóm trong DirectStream phát triển theo thời gian và mỗi khách hàng trong một nhóm chia s luồng giống nhau. Quá trình tìm kiếm dịch vụ cho một yêu cầu mới bao gồm bốn bước như được chỉ ra trong hình 2.23. Đầu tiên các khách hàng mới sẽ gửi một yêu cầu đến máy chủ chỉ dẫn để yêu cầu video bắt đầu từ vị trí. Các máy chủ chỉ dẫn sau đó nhìn vào cơ sở dữ liệu của mình và trả về một danh sách các nút ứng cử viên, bao gồm cả máy chủ dữ liệu và khách hàng có nội dung để phục vụ yêu cầu này. Khách hàng mới xác định từ các nút để lấy các luồng sử dụng cho thuật toán lựa chọn cha QoS. Sử dụng thuật toán Đồ án tốt nghiệp đại học Chương II: Hệ thống luồng video qua mạng ngang hàng P2P Lê Ngọc Anh – D09VT2 50 này, một khách hàng lựa chọn một nút cha có đủ băng thông. Các khách hàng mới liên hệ với nút ứng viên được chọn và yêu cầu chuyển tiếp luồng. Sau khi kết nối được thiết lập, khách hàng mới gửi tín hiệu trở lại máy chủ chỉ dẫn và đăng ký chính nó vào cơ sở dữ liệu. DirectStream giảm đáng kể khối lượng công việc đặt ra trên máy chủ. Một lợi thế là quy mô của nó cũng như sự phổ biến của video tăng ngay cả khi khách hàng tham gia không hợp tác chia sẽ. DirectStream có hai nhược điểm, quản l tập trung đưa ra một điểm đơn của sự thất bại. Khi nhiều nhóm cao cấp khác nhau thất bại, một peer có thể nhanh thiếu bộ đệm của nó. Trong hệ thống VoD dựa trên cây, các peer trên lớp trên luôn luôn đóng một vai trò quan trọng trong mạng che phủ toàn bộ. Sự ra đi của nó sẽ dẫn đến sự biến động lớp mạng thấp hơn. Hơn nữa, mỗi peer chỉ có một nhà cung cấp dữ liệu, điều đó sẽ gây ra không hiệu quả sử dụng băng thông có sẵn trong một mạng không đồng nhất và mạng cómôi trường năng động. Đồng thời, trong bộ nhớ cache và dựa trên hệ thống chuyển tiếp, nếu cha nhảy đến một điểm nào đó trong đoạn video, nó bắt đầu nhận dữ liệu và không quan tâm tới nút con và những nút cần phải tìm kiếm cha mới. 2.5.2 Hệ thống VoD dựa trên lƣới Trong hệ thống VoD dựa trên lưới, không có cấu trúc liên kết cụ thể được tạo ra. Các peer trong mạng kết nối với một số peer cha để nhận các gói tin video. Hệ thống VoD dựa trên lưới có giao thức ở trên lớp phủ, dễ dàng để thiết kế và linh hoạt hơn cho tốc độ các khối nội dung và do đó nó được phổ biến hơn. Hiện P2P dựa trên hệ thống lưới đã được chứng minh là rất tốt cho phân phối nội dung video quy mô lớn với ít tài nguyên máy chủ. Tuy nhiên, trong hệ thống VoD khó khăn trong thực tế là người dùng muốn nhận được các khối tuần tự để xem video trong khi tải về. Ngoài ra, trong dịch vụ VoD người sử dụng có thể quan tâm tới các phần khác nhau của đoạn video và có thể cạnh tranh tài nguyên của người dùng khác. Qua đó, thách thức chính của hệ thống là đảm bảo rằng người dùng có thể bắt đầu xem video tại bất kỳ thời điểm nào, với thời gian chờ nhỏ và tốc độ phát lại cao. BitTorrent (BT) là một trong những kỹ thuật dựa trên lưới để phân phối khối lượng lớn các nội dung trên Internet. Nó là một giao thức chia s tập tin mở rộng mà còn kết hợp với cơ chế truyền dữ liệu tràn lụt. Có một số hạn chế của kỹ thuật BT ban đầu trong việc cung cấp video streaming. Trong BT, các tập tin được phân đoạn trên khoảng trống (space). Mặc dù cơ chế lựa chọn đoạn mặc định của BitTorrent là rất hiệu quả trong việc giảm thiểu xác suất cho các đoạn miếng hiếm và cung cấp các đoạn hiếm cho các peer, nó không thất vọng trong thời gian lưu lượng tắc nghẽn. L do là với thời gian dữ liệu nhạy cảm thì mỗi đoạn sẽ phải nhận trong một khoảng thời gian nhất định. Yếu tố này không được xem xét trong cơ chế lựa chọn đoạn ban đầu của BT và do vậy nó không thể cung cấp dịch vụ phân phối nhạy cảm thời gian, bởi vì các đoạn được yêu cầu dựa trên sự hiếm có và không theo thời hạn của nó. Do đó, cơ Đồ án tốt nghiệp đại học Chương II: Hệ thống luồng video qua mạng ngang hàng P2P Lê Ngọc Anh – D09VT2 51 chế lựa chọn đoạn hiện tại cần sửa đổi để hỗ trợ dịch vụ thời gian nhạy cảm như VoD. BASS và BiToS là các ví dụ của BitTorrent dựa trên hệ thống P2P VoD dạng lưới. Hình 2.24 BASS: (a) Tổng quan hệ thống, (b)Mẫu khách hàng BitTorrent hỗ trợ hệ thống streaming (BASS) mở rộng hệ thống BitTorrent hiện tại để cung cấp một dịch vụ gần Video-on-Demand. Bởi vì BASS sử dụng sự hỗ trợ của BT cho các luồng, nó sử dụng các dịch vụ của một máy chủ bên ngoài mà có thể lưu được toàn bộ video của các nhà sản xuấ và đảm bảo rằng người sử dụng có thể phát lại video mà không gặp sự thay đổi chất lượng. Sự thay đổi duy nhất của BitTorrent cho thấy là nó không nên tải về bất cứ dữ liệu nào trước thời điểm playback. Nó được phép sử dụng đoạn hiếm nhất đầu tiên và chính sách ăn miếng trả miếng (tit – for - tat). Trong chính đoạn hiếm đầu tiên, khách hàng yêu cầu một phần dựa trên số lượng bản sao nó thấy có sẵn và chọn một cái là phổ biến nhất. Từ máy chủ truyền thông, BASS tải các phần trong trật tự, bỏ qua các phần mà đã được tải bởi BitTorrent, hoặc đang trong quá trình được tải về và dự kiến sẽ hoàn thành trước thời hạn phát. Tổng quan về hệ thống của BASS được đưa ra trong hình 2.24. Dù BASS làm giảm tải tại các máy chủ, thiết kế của hệ thống vẫn là máy chủ theo định hướng và do đó các yêu cầu băng thông tại các máy chủ tăng tuyến tính với số lượng người dụng. Hình 2.25 Phƣơng ph p tiếp cận BiToS Đồ án tốt nghiệp đại học Chương II: Hệ thống luồng video qua mạng ngang hàng P2P Lê Ngọc Anh – D09VT2 52 Hệ thống BiToS cũng dựa trên BitTorrent. Ý tưởng chính là để phân chia các khối đang thiếu thành hai tập hợp: “tập hợp ưu tiên cao” và “tập hợp còn lại” và yêu cầu với các khối xác suất cao hơn từ tập hợp ưu tiên cao hơn (hình 2.25). Tập hợp ưu tiên cao hơn, có chứa tất cả các phần khá gần để được tái tạo. Vì vậy, peer mong muốn tải về những phần sớm hơn. Trái ngược với tập hợp còn lại, trong đó có chứa các phần mà sẽ không cần đến trong tương lai gần. Sau khi người dùng bắt đầu, bộ đệm của người dùng yêu cầu những phần cần thiết từ các phần đệm các peer nhận. Trong BiToS, trọng tâm chính được đưa ra cho việc lập lịch cẩn thận của các khối video. Các phần mà bỏ lỡ thời hạn phát lại của nó được giảm xuống đơn giản. Do vậy, điều này có thể dẫn đến suy giảm chất lượng phát lại video. Ngoài ra do tính chất bất đối xứng của các kết nối Internet và không đồng nhất của các peer, hệ thống không thể đảm bảo rằng các đoạn video được yêu cầu luôn luôn có sẵn để phát lại đúng thời gian yêu cầu. 2.6 Kết luận chƣơng II Chương 2 đã trình bày khái quát về khái niệm mạng ngang hàng P2P, ưu nhược điểm của mạng ngang hàng. Bên cạnh đó còn đề cập đến việc phân loại mạng ngang hàng. Qua đó thấy mạng ngang hàng rất ổn định và dễ mở rộng; tận dụng tối đa tài nguyên đóng góp của các nút tham gia mạng; mạng ngang hàng dễ cài đặt; chi phí thiết bị thấp, triển khai một hệ thống mạng khá dễ dàng. Nội dung chính chương 2 trình bày các hệ thống P2P streaming, có thể phân chia thành hệ thống P2P live Streaming và P2P VoD. Tùy theo cách tiếp cận, hệ thống P2P live streaming có thể được chia thành dạng cây hoặc dạng lưới. Hệ thống P2P VoD cũng có thể chia thành dạng cây và dạng lưới. Tuy nhiên, hệ thống P2P streaming cũng bộc lộ nhiều nhược điểm cần phải xem xét, trong đó quan trọng nhất là trễ luồng video. Đồ án tốt nghiệp đại học Chương III: Ứng dụng luồng video streaming qua mạng Pastry Lê Ngọc Anh – D09VT2 53 CHƢƠNG III: ỨNG DỤNG LUỒNG VIDEO STREAMING QUA MẠNG PASTRY 3.1 Giới thiệu về Pastry Gần đây các ứng dụng Internet trong mạng ngang hàng đã được phổ biến một cách rộng rãi thông qua các ứng dụng chia sẽ file như Napster, Gnutella và FreeNet. Trong khi khá nhiều sự chú đều tập trung vào các vấn đề bản quyền được đưa ra bởi các ứng dụng cụ thể thì các hệ thống P2P lại đưa nhiều khía cạnh về vấn đề kỹ thuật như kiểm soát phân cấp, tự tổ chức và khả năng mở rộng. Các hệ thống P2P được mô tả như một hệ thống phân phối, trong đó tất cả các nút đều có nhiệm vụ và năng lực giống nhau, đồng thời tất cả các thông tin truyền thông là đối xứng. Hiện nay có khá nhiều dự án nhằm xây dựng các ứng dụng P2P. Một trog những vấn đề quan trọng trong việc xây dựng này là nhằm cung cấp các thuật toán hiệu quả cho vị trí đối tượng và quá trình định tuyến trong mạng. Pastry là một trong những giải pháp được đưa ra. Pastry có khả năng chống chịu lỗi, khả năng mở rộng và đáng tin cậy. Hơn nữa, Pastry còn có đặc tính định tuyến cục bộ khá tốt. Pastry được thiết kế như một chất nền chung cho việc xây dựng một loạt các ứng dụng mạng ngang hàng trên Internet như chia s file toàn cầu, lưu trữ file, truyền thông nhóm và các hệ thống đặt tên. Một số ứng dụng được xây dựng trên đinh của Pastry cho đến nay bao gồm một tiện ích lưu trữ liên tục chung, được gọi là PAST và một hệ thống có khả năng mở rộng, đó là Scribe. Còn lại các ứng dụng khác đang được phát triển. Pastry cung cấp các khả năng sau đây: đầu tiên mỗi nút trong mạng pastry sẽ có một định danh duy nhất (NodeId) trong một không gian định danh 128 bit vòng tròn. Khi có một thông điệp và một khóa 128 bit dạng số, một nút pastry sẽ hiệu quả trong việc định tuyến thông điệp đó tới một nút với nodeid có số gần nhất với khóa, trong số tất cả các nút pastry hiện đang sống. Số lượng chuyển tiếp các bước trong mạng bao phủ pastry là O(logN), trong khi kích thước của bảng định tuyến được duy trì trong mỗi nút Pastry chỉ là O(logN) (trong đó N là số nút Pastry sống trong mạng bao phủ). Tại mỗi nút Pastry dọc theo đường định tuyến mà một tin nhấn có, ứng dụng sẽ được thông báo và có thể thực hiện các tính toán ứng dụng cụ thể có liên quan đến tin nhắn. Thứ hai, môi nút Pastry sẽ tiến hành theo dõi L hàng xóm trực tiếp của nó trong không gian nodeid (được gọi là tập lá) và thông báo cho các ứng dụng của các nút mới đến, nút ra và nút phục hồi trong tập lá. Thứ ba, pastry đưa vào tài khoản cục bộ trong Internet cơ bản, nó tìm cách giảm thiểu khoảng cách truyền đi thông điệp, theo một hệ mét xấp xỉ vô hướng giống như độ trễ lệnh ping. Pastry hoàn toàn là phi tập trung, có khả năng mở rộng và tự tổ chức. Bởi vậy nó sẽ tự động thích nghi với sự ra đi, đến và sự thất bại của các nút. ứng dụng P2P xây dựng trên pastry có thể sử dụng khả năng của mình bằng nhiều cách, bao gồm: Đồ án tốt nghiệp đại học Chương III: Ứng dụng luồng video streaming qua mạng Pastry Lê Ngọc Anh – D09VT2 54  Ánh xạ đối tượng ứng dụng tới các nút Pastry: Các đối tượng ứng dụng cụ thể được phân công thành các định danh ngẫu nhiên đồng đều, duy nhất ( các ObjId) và được ánh xạ tới k (k ≥ 1), các nút với nodeId có số gần nhất với objId. Đại lượng k phản ánh mức độ mong muốn nhân rộng các ứng dụng cho các đối tượng.  Cách chèn them các đối tượng: Các đối tượng ứng dụng cụ thể có thể được them vào bằng cách đinh tuyến một thong điệp Pastry sử dụng ObjId như là khóa (key).  Quá trình truy cập các đối tượng: Các đối tượng ứng dụng cụ thể có thể được tra cứu, liên lạc hoặc thu hồi bằng cách định tuyến một thông điệp Pastry có sử dụng ObjId như là khóa. Theo định nghĩa, thong điệp này được đảm bảo đến một nút có khả năng duy trì một bản sao của đối tượng được yêu cầu, trừ khi tất cả k nút với các nodeId gần nhất với ObjId đều thất bại  Tính đa dạng: Việc phân công các nodeId là ngẫu nhiên và không thể bị hỏng bởi một sự tấn công nào đó. Như vậy, với xác suất cao, các nút với các nodeId liền kề có tính đa dạng cả về vị trí địa l , thẩm quyền, quyền sở hữu và việc đính kèm các tập tin trong mạng…Điều này giảm thiểu xác suất thất bại đồng thời của tất cả k nút trong việc duy trì một bản sao đối tượng.  Khả năng cân bằng tải: Cả nodeId và ObjId đều được phân bố ngẫu nhiên và đồng đều trong không gian định danh Pastry 128bit. Kết quả này tạo nên một sự cân bằng tốt đầu tiên nhằm lưu trữ các yêu cầu và truy vấn tải trọng giữa các nút Pastry cũng như trong mạng Internet cơ bản.  Hiệu quả và khả năng mở rộng việc phổ biến thông tin: Các ứng dụng có thể thực hiện multicast một cách hiệu quả bằng cách sử dụng chuyển tiếp đường dẫn ngược dọc theo cây được hình thành bởi các định tuyến từ các client tới nút có nodeId gần với ObjId nhất. Tính chất cục bộ của mạng Pastry đảm bảo rằng các kết quả multicast trên cây là khá hiệu quả, tức là dữ liệu có hiệu quả trong việc cung cấp và sử dụng nguồn tài nguyên Internet cơ bản. Pastry là một giao thức phân phối dữ liệu và định tuyến ở lớp ứng dụng trong các ứng dụng mạng ngang hang có cấu trúc. Đúng như định nghĩa của nó, Pastry có 2 nhiệm vụ chính là phân phối dữ liệu trong một mạng ngang hang 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 sử dụng giao thức DHT để lấy định danh các nút 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 hang, 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. Đồ án tốt nghiệp đại học Chương III: Ứng dụng luồng video streaming qua mạng Pastry Lê Ngọc Anh – D09VT2 55 Hình 3.1 Bảng định tuyến của nút 10233102 trong Pastry Nút và dữ liệu trong mạng Pastry được định danh bởi một giá trị 128bit (nodeId và 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 nút quả 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 nút 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. Ở hình 3.1 là bảng định tuyến của nodeId 10233102. Dựa vào bảng định tuyến này, nút 10233102 có thể gửi dữ liệu đến cho nút khác. Ví dụ 10233102 muốn gửi thông điệp m tới cho nút 33321220. Đầu tiên nó sẽ tìm trong các nút 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 nút cần gửi đến 33321220 với các cột trong Routing Table. Cụ thể là nút 33321220 có ký tự đầu là 3: nó sẽ tìm trong Routing Table tại hàng 1 cột 3 và tìm được nút 31203203. Do ngay từ ký tự đầu của nút cần gửi đã khác nút gửi nên quá trình tìm kiếm dừng lại. Nút 1023312 sẽ gửi đến nút 31203203 với yêu cầu sẽ gửi thông điệp m đến nút 33321220. Quá trình này tiếp tục xảy ra cho đến khi đến được nút cần gửi. Đồ án tốt nghiệp đại học Chương III: Ứng dụng luồng video streaming qua mạng Pastry Lê Ngọc Anh – D09VT2 56 Hình 3.2 Nút 10233102 gửi thông điệp m đến nút 33321220 Các nút định kỳ gửi các gói tin keep-alive cho các nút bằng hàng xóm của nó và nếu như một nút nào đó không nhận được gói keep-alive của một nút bằ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ư nút hàng xóm đã rời khỏi mạng và tự động update thông tin. 3.2 Qu tr nh truyền tin multicast trong nhóm Scribe Scribe là cơ sở hạ tầng cho việc truyền tin multicast ở lớp ứng dụng dựa trên giao thức Pastry. Cũng chính vì thế mà 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 truyền thông điệp multicast ở lớp ứng dụng. Giống như Pastry, Scribe là mô hình phân quyền hoàn toàn và nó có khả năng xây dựng, duy trì 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 tin 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 nút có cùng nhu cầu nhận dữ liệu multicast vào một nhóm. Về mặt logic thì các nút 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 nút 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 nhóm (group), hai là join vào một Đồ án tốt nghiệp đại học Chương III: Ứng dụng luồng video streaming qua mạng Pastry Lê Ngọc Anh – D09VT2 57 nhóm đã có từ trước (trở thành 1 nút trong cây multicast) và ba là truyền tin multicast tới tất cả các nút có trong nhóm. Scribe là một mô hình cung cấp một cách „nỗ lực tối đa” trong việc truyền tin multicast, nó có thể quản l và duy trì được nhiều nhóm cùng một lúc, các nhóm có số lượng thành viên lớn cũng như có nhiều tài nguyên trong mạng. 3.2.1 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 Scribe. 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 nút) và deliver (được gọi khi thông điệp đến một nút 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 nút đó). Các thông điệp trong Scribe có 4 kiểu là: JOIN (xin tham gia vào một nhóm), CREATE (tạo một nhóm mới), LEAVE (rời khỏi nhóm), 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. Scribe node (tức là nút trong mạng có cài chương trình ứng dụng Scribe) có Id gần với Id của nhóm (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 nút Scribe nào đó muốn khởi tạo một nhóm thì các bước thực hiện sẽ là:  B1: Nút Scribe dùng Pastry định tuyến thông điệp router (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 nút có nodeId gần với groupId nhất. Và nút này sẽ được xem như là gốc của nhóm 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 nhóm mới vào danh sách nhóm đã 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 nhóm multicast. - Quản lý thành viên: Một nhóm 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 nút mới được join vào nhóm thì nó sẽ trở thành một thành viên của nhóm 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 nhóm. Nếu một nút Scribe là một phần của nhóm 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 mục của bảng này sẽ gồm 2 trường : địa chỉ IP của một nút con nào đó của nó (IP Adds) và nodeId tương ứng của nút con đó. Đồ án tốt nghiệp đại học Chương III: Ứng dụng luồng video streaming qua mạng Pastry Lê Ngọc Anh – D09VT2 58 3.2.2 Qu tr nh gia nhập nhóm (join group): Khi một nút muốn join vào một nhóm 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 nhóm cần tham gia làm key: route (JOIN, groupId).  Giao thức Pastry sẽ định tuyến nó tới “điểm gặp”. - Nếu nút trung gian trong quá trình truyền thông điệp là một forwarder (một thành phần của nhóm đang định tham gia vào) thì đơn giản chỉ là thêm nút cần tham gia vào làm một nút con của nút forwarder này. - Nếu nút trung gian không phải là một forwarder của nhóm cần tham gia vào thì thực hiện các bước: + Tạo một children table cho nút trung gian và thêm thông tin của nút cần tham gia vào bảng này. + Gửi thông điệp JOIN của nút trung gian tới “điểm gặp” ( lúc này thay cho việc thực hiện tham gia nút ban đầu, ta đi tham gia nút trung gian vào nhóm). Và cứ thực hiện đệ quy như thế này ta sẽ có được một danh sách các nút mới tham gia vào nhóm thay vì chỉ một nút như ban đầu. Để dễ hiểu, ta xét ví dụ sau: Một nhóm có “điểm gặp” là A có nodeId = 1100 (như ở hình vẽ dưới). Hình 3.3 Quá trình 1 nút gia nhập vào nhóm Nút B có nodeId là 0111 muốn tham gia vào nhóm có A là gốc, nó sẽ gửi gói tin route (JOIN,x) với x là groupId của nhóm này, giao thức Pastry sẽ định tuyến gói tin tới nút D có nodeId là 1001. Nhưng nút D không phải là một thành phần của nhóm này cho nên D sẽ tạo ra một children table của nó và thêm vào đó mục (122.45.1.23 ; 0111). Tiế theo D sẽ gửi gói tin yêu cầu tham gia vào nhóm có gốc A : route (JOIN ,x). Tiếp tục giao thức Pastry lại định tuyến nó tới nút E và E cũng không phải thành viên của nhóm này. Vì thế E cũng tạo ra một children table của nó và thêm mục (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 A vì A là một thành phần của nhóm cho nên ở đây A sẽ thêm mục Đồ án tốt nghiệp đại học Chương III: Ứng dụng luồng video streaming qua mạng Pastry Lê Ngọc Anh – D09VT2 59 (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 nhóm là B, D và E. 3.2.3 Quá tr nh rời nhóm (leave group) Khi một nút nào đó muốn rời khỏi nhóm thì nó sẽ ghi một cách cục bộ rằng nó đã rời khỏi nhóm (tức là chỉ một mình nó biết là nó đã rời khỏi mạng). Sau đó nếu bảng children table của nút 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 nút mà nút có con đã rời khỏi 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 gia nhập và rời khỏi nhóm như thế này và với đặc tính phân phối ngẫu nhiên của Pastry thì cây multicast sẽ được xây dựng một cách đồng đều theo nghĩa là không một nút nào trong cây mutlicast, ngay cả nút gốc phải chịu quá nhiều kết nối tới các nút khác. Việc này giúp cho Scribe có khả năng mở rộng về kích thước cũng mhư về khả năng, tức là cả khi tăng số lượng nút trong nhóm hay tăng các gói tin multicast gửi đến mạng thì Scribe vẫn có thể đảm đương được. 3.2.4 Truyền tin multicast tới mạng Khi một nút nào đó muốn truyền multicast tới các điểm trong một nhóm nào đó thì 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 nút kia IP của nó (rootIP), sau đó nút này sẽ truyền thông tin muốn gửi tới điểm gặp. Điểm gặp này sẽ sao chép gói tin multicast này và 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 sao chép 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 nút là nút lá của cây. Hình 3.4 Truyền tin multicast trong nhóm Scribe Giả sử như hình vẽ ở trên, Sender là nút 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). Nút 1100 nhận được gói tin và Đồ án tốt nghiệp đại học Chương III: Ứng dụng luồng video streaming qua mạng Pastry Lê Ngọc Anh – D09VT2 60 trả lại cho sender địa chỉ IP của nó. Từ lúc này sender giao tiếp với nút 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 tới Pastry hay P2P). Sender gửi dữ liệu cho nút gốc 1100. Nút này sẽ tạo ra một bản sao dữ liệu và gửi cho con của nó là 1101. Nút 1101 nhận được dữ liệu từ root, nó cũng sẽ tạo ra một bản sao và gửi cho 1001 là con của nó. Nút 1001 lại sao chép dữ liệu và gửi cho 0111 và 0100 là thành viên trong children table của nó. Khi các nút 0100 và 0111 nhận được dữ liệu, do 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 nhóm của nó lại phải xin và nhận IP của nút gốc rồi để sau đó giao tiếp với nút này dựa vào IP mà không sử dụng giao thức Pastry để gửi dữ liệu. Đơn giản là việc định tuyến cũng như việc gửi thông tin qua Pastry là một việc làm rất tốn thời gian và tai 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ó gửi một số hoặc nhiều gói tin. Do đó việc sender lưu IP của nút 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 mạng. Tuy nhiên nếu nút 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 nút root mới và tiếp tục truyền thông tin. 3.2.5 Sửa cây multicast Vì Scribe làm việc trong môi trường mạng, do đó muốn duy trì được sự ổn định của nhóm thì cần phải có các 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 nút bị rời khỏi mạng. Trong Scribe, nút cha sẽ định kỳ gửi các gói tin heartbeat tới nút con của nó nhằm thông báo sự tồn tại của mình trong cây. Nếu nút 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ư nút cha của nó bị lỗi. Và nó sẽ tự động tìm một nút cha khác thay thế, bằng cách gửi thông điệp JOIN với key là groupId của nhóm hiện tại (quá trình này giống như quá trình gia nhập vào nhóm). Hình 3.5 Quá trình tự sửa câymulticast Đồ án tốt nghiệp đại học Chương III: Ứng dụng luồng video streaming qua mạng Pastry Lê Ngọc Anh – D09VT2 61 Giả sử như hình vẽ trên, ban đầu ta có cây multicast với gốc là nút 1100, trong cây nút 1001 có cha là nút 1101. Khi nút 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 gia nhập nhóm. Cây multicast sẽ được xây dựng lại và bây giờ thì nút 1001 nhận một nút mới là 1111 là cha mới của nó (như hình vẽ). Trong trường hợp nút gốc bị lỗi thì các con của nó cũng chạy giải thuật như trên. Khi đó giải thuật Pastry sẽ tự chọn ra một nút gốc mới có nodetId gần nhất (tính theo hiện thời) với groupId và nhóm 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 nút 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. 3.3 Cải thiện Scribe bằng cấu trúc Splitstream Hiện nay, đã có những nghiên cứu xây dựng cây multicast dành cho truyền video streaming trên mạng ngang hàng có cấu trúc như Splitstream. Splitstream được xây dựng dựa trên nền tảng Pastry, Scribe và thêm vào đó một số giải pháp để hạn chế tình trạng quá tải tại một số nút tham gia mạng 3.3.1 Giới thiệu SplitStream SplitStream là một hệ thống cây đa luồng đề xuất trong năm 2003 của trung tâm nghiên cứu của Microsoft. SplitStream được thiết kế để khắc phục tải trọng (load) chuyển tiếp không ổn định trong hệ thống multicast thông thường dựa trên đa cây. Ý tưởng chính của SplitStream là phân chia các luồng vào các khối độc lập không giống nhau và mỗi khối được truyền multicast sử dụng một cây riêng biệt. Để đảm bảo rằng các tải trọng được chuyển tiếp có thể được lan truyền trên tất cả các peer tham gia, một mạng lưới cây được xây dựng trong đó một nút là một nút nội bộ trong nhiều nhất là một cây và là một nút lá trong tất cả các cây khác. Một tập hợp các cây như vậy được gọi là interior – node - disjoint. Hình 3.6 minh họa cách SplitStream cân bằng tải được chia thành hai đường và gói tin được multicast trong hai cây riêng biệt. Mỗi peer, xa so với nguồn, nhận được cả hai luồng tin. Mỗi peer là một nút bên trong chỉ có một cây và là chuyển tiếp các khối nội dung đến hai nút con. Khi một nút bị quá tải nhận được yêu cầu từ nút con, nó hoặc là từ chối hoặc chấp nhận nút con và từ chối một nút con hiện tại của mình, nút con bị từ chối là kém hấp dẫn hơn so với nút con mới. Một nút sẽ được mong muốn nhiều hơn nếu nodeId của nó gần hơn với nút cha của nó. SplitStream xây dựng các cây multicast cho các luồng trong khi vẫn quan tâm những hạn chế băng thông trong và băng thông bên ngoài của các peer. Nó cung cấp khả năng phục hồi thất bại các liên kết nút ra đi không báo trước và cây multicast được sửa chữa. Một trong những vấn đề chính với SplitStream là tác động của các nút Đồ án tốt nghiệp đại học Chương III: Ứng dụng luồng video streaming qua mạng Pastry Lê Ngọc Anh – D09VT2 62 với băng thông không đồng nhất về hiệu quả của nó. Một vấn đề khác là trong một interior – node - disjoint, các nút nhận gói tin riêng biệt với độ trễ khác nhau ví dụ như các nút được đặt trong khoảng cách khác nhau từ gốc của cây. Điều này là không mong muốn cho một ứng dụng luồng truyền thông trực tuyến, trong đó việc đòi hỏi thời gian thực chính xác. Thêm vấn đề khác là tăng cường quy mô hệ thống để cây có độ sâu lớn hơn và các nút được đặt trong khoảng cách đa dạng từ nguồn. Hình 3.6 Một ví dụ đơn giản minh họa cách tiếp cận của SplitStream 3.3.2 Cơ chế xây dựng luồng trong SplitStream Splitstream có thể được xem như là việc chọn lựa các cây Scribe để tạo nên cây multicast đa luồng. Việc lựa chọn các cấy Scribe sẽ dễ dàng tạo nên cây mulitcast đa luồng với tính chất: 1 nút là nút trong của 1 luồng sẽ là nút lá trong các luồng còn lại. Hình 3.7 Splitstream F luồng Việc xây dựng các luồng khá đơn giản. Như ở trên hình 3.7, với không gian Pastry được đánh địa chỉ các nút gồm F ký tự. Splitstream sẽ chọn ra các luồng có tên là 0x, 1x, …, Fx để các nút sau khi gia nhập vào cây multicast đa luồng có thể đảm bảo. Nút có Id bắt đầu là 0x sẽ là nút trong của cây multicast stripeId 0x và là nút lá của tất cả Đồ án tốt nghiệp đại học Chương III: Ứng dụng luồng video streaming qua mạng Pastry Lê Ngọc Anh – D09VT2 63 các luồng còn lại. Tương tự nút có Id bắt đầu là 1x sẽ là nút trong của cây multicast stripeId 1x và là lá của tất cả các luồng còn lại. Tuy nhiên, Splitstream sẽ gặp các vấn đề tại các máy (peer) tham gia 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 được băng thông đi ra của 1 peer do như cầu join của các peer khác: khi 1 peer đã 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 các peer này. Nếu vẫn duy trì cơ chế như cây Scribe thì sẽ có một số peer thật sự không nhận được dữ liệu từ 1 vài luồng do nút cha của nó không gửi dữ liệu thực sự đến cho nó. Splitstream sử dụng cơ chế mới để giải quyết vấn đề tại các nút mà băng thông đi ra đã bị vượt quá giới hạn. Cơ chế này bao gồm: - B1 : Xác định nút cha: H nh 3.8 X c định nút cha khi băng thông đi ra vƣợt quá giới hạn Trong ví dụ trên nút với Id là 080* đã bị limit outdegree (băng thông đi ra vượt quá giới hạn) thì nhận được yêu cầu join vào của nút với Id 001* ở luồng 0800. Nút 080* sẽ xem xét tất cả các nút con của nó để loại đi 1 nút con. Hình 3.8 (1) – (2) là trường hợp có nút con 9* nhận được nút 080* làm cha trong luồng 1800 khác với luồng 0800. Nút 080* sẽ nhận được nút 001* làm con và loại bỏ nút 9*. Sau đó nút 085* lại yêu cầu join vào nút 080*. Hình 3.8 (3) – (4) là trường hợp các nút con đều nhận 080* là cha trong luồng 0800, xét đến Id của các nút con. Nút 001* là nút có Id với số ký tự tính từ trái sang phải khác với luồng 0800 nhất. Nút 001* sẽ trở thành nút orphan và nút 085* được nhận làm nút con. Đồ án tốt nghiệp đại học Chương III: Ứng dụng luồng video streaming qua mạng Pastry Lê Ngọc Anh – D09VT2 64 - B2: Nếu sau bước 1 vẫn có nút orphan (tức là nút chưa tìm được nút cha) sẽ tiến hành bước này. Nút orphan sẽ gửi unicast đến SCG (Spare Capacity Group) để tìm được nút cha. SCG là tập hợp tất cả các nút mà băng thông đi ra chưa vượt quá giới hạn. Với cơ chế truyền tin unicast, nút orphan sẽ gửi thông điệp tìm nút có luồng mà băng thông đi ra chưa vượt quá giới hạn để nhận nó làm nút cha. Ƣu điểm: Xây dựng cây multicast đa luồng khá đơn giản dựa vào kết cấu sẵn có của Pastry và Scribe. Khi mạng ổn định và việc phân chia định danh là khá đều thì các nút trong hệ thống chịu quá tải tương đương nhau. Thêm vào đó là các cơ chế tìm nút cha nhằm đảm bảo các nút trong mạng không bị quá tải. Nhƣợc điểm: Không đảm bảo được độ chênh lệch độ trễ các luồng nhận được tại các nút 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. 3.4 Kết luận chƣơng III Chương này nhằm giới thiệu về Pastry, nền tảng xây dựng của giao thức Scribe. Đồng thời mô tả quá trình gia nhập, rời nhóm, truyền tin multicast tới mạng và quá trình sửa cây multicast trong Scribe. Từ đó đưa ra được các ưu nhược điểm của giao thức Scribe trong việc truyền tin multicast lớp ứng dụng so với IP multicast. Giới thiệu kỹ thuật SplitStream qua đó áp dụng vào giao thức Scribe nhằm khắc phục những nhược điểm của giao thức Scribe, tạo một hệ thống cây multicast đa luồng. Đồ án tốt nghiệp đại học kết luận đồ án Lê Ngọc Anh – D09VT2 65 KẾT LUẬN ĐỒ ÁN Trên thế giới, các ứng dụng mạng ngang hàng nói chung và multicast trên mạng ngang hàng đang được nghiên cứu và phát triển một cách mạnh mẽ. Nó sẽ và đang dần thay thế các mô hình mạng truyền thống như mô hình khách-chủ hay IP multicast. Trong khóa luận này đã trình bày một cách ngắn gọn về nghiên cứu multicast lớp ứng dụng cho truyền video thời gian thực trong mạng ngang hàng P2P, cụ thể là cải thiện giao thức Scribe. Tuy nhiên việc triển khai multicast lớp ứng dụng vẫn chưa thực sự đáp ứng được các yêu cầu của P2P video streaming thời gian thực, ví dụ như sự ra vào của các nút, độ trễ lớn. Hơn nữa các giải pháp này còn chưa xét đến vấn đề các nút không đóng góp. Với những kết quả đạt được và những mặt còn tồn tại, sau đây là một vài hướng phát triển tiếp theo:  Khắc phục những nhược điểm nêu trên.  Sử dụng phần mềm OverSim so sánh đánh giá hiệu năng giữa Scribe và SplitStream.  Nghiên cứu cải thiện QoS khi truyền video streaming qua mạng P2P. Một lần nữa em xin chân thành cảm ơn cô giáo Vũ Thị Thúy Hà đã hướng dẫn em, cùng các thầy cô bộ môn đã tận tình giúp đỡ em trong thời gian học tập tại trường để em có đủ kiến thức để có thể hoàn thành đồ án này. Đồ án tốt nghiệp đại học Tài liệu tham khảo Lê Ngọc Anh – D09VT2 66 TÀI LIỆU THAM KHẢO Tài liệu tiếng Việt: 1. Bùi thị Lan Hương: Luận văn thạc sĩ “Phương pháp multicast tầng ứng dụng dựa trên cơ chế kéo đẩy cho truyền video thời gian thực trên mạng P2P”. 2. Nguyễn Văn Minh: Luận văn tốt nghiệp “Truyền tin multicast đa luồng thời gian thực trên mạng ngang hàng có cấu trúc”. 3. Nguyễn Ngọc Anh, “Topology Optimization for DTH-based Application Layer Multicast”, Trường đại học Công Nghệ, 2012. 4. ThS. Vũ Thị Thúy Hà, TS. Lê Nhật Thăng, bài báo”Định tuyến trong mạng ngang hàng thế hệ mới”. Tài liệu tiếng Anh: 1. Antony Rowstron and Peter Druschel: “Pastry: Scalable, deccentralized object location and routing for lagre – scale peer – to – peer systems”. 2. Bin Rong, “Video Streaming over the Internet using Application Layer Multicast”, RMIT University, 2008. 3. Chung-Yan Chen, Yu-Wei Chen, “Design and Analysis of Streaming for P2P”, Graduate Institute of Information and Logistics Management, National Taipei University of Technology, 2013. 4. Luca Abeni, Csaba Kiraly, Renato Lo Cigno, “Scheduling P2P Multimedia Streams: Can we achieve performance and robustness?”, 2009 IEEE. 5. L. Abeni, C. Kiraly, R. Lo Cigno, “Achiving performance and robustness in P2P streaming systems”, University of Trento, Italy, Tech. Rep. TR-DISI-09- 041, 2009. 6. Indrani Gupta, Ken Binman, Prakash Linga, Al Demers, Robbert van Renesse:” Peer – to – Peer Networks: Kelips”. 7. Xuemin Shen, Heather Yu, John Buford, Mursalin Akon, “Handbook of Peer- to-Peer”, Springer 2009.