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

Chia sẻ: Lan Lan | Ngày: | Loại File: PDF | Số trang:48

Thêm vào BST

Báo xấu

207
lượt xem 60
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Truyên tin multicast thơi gian thưc trên mang ngang hang la môt nhanh trong truyên tin multicast thơi gian thưc trên mang Internet . Khác với các mô hình Client -Server truyên thông , mô hinh mang ngang hang co nhưng đăc trưng riêng biêt . Vơi mô hinh mang ngang hang ngươi thiêt kê co thê tân dung băng thông va kha năng lưu trư cua cac may tham gia mang thay vi tâp trung tải vào một số máy ch́nh như các server trong mô hinh Client-Server. Điêm manh này của mô hình mạng ngang hàng đã làm...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

ĐẠI HỌC QUỐC GIA HÀ NỘI 1 TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Văn Minh TRUYỀN TIN MULTICAST ĐA LUỒNG THỜI GIAN THỰC TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2010
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Văn Minh TRUYỀN TIN MULTICAST ĐA LUỒNG THỜI GIAN THỰC TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hƣớng dẫn: TS. Nguyễn Hoài Sơn HÀ NỘI - 2010
LỜI CẢM ƠN Em xin chân thành cảm ơn các thầy cô trường Đại học Công Nghệ - Đại học Quốc Gia Hà Nội đã tận tình giảng dạy và giúp đỡ em trong suốt 4 năm vừa qua để em có đủ kiến thức để hoàn thành khóa luận này. Đặc biệt em xin gửi lời cảm ơn sâu sắc đến thầy Nguyễn Hoài Sơn. Thầy đã hướng dẫn và định hình cho em cách tiếp cận nghiên cứu khoa học. Đồng thời trong suốt quá trình làm luận văn luôn phải đối mặt với các vấn đề khó khăn cần giải quyết thầy đã luôn theo sát để em tránh khỏi sai lầm giúp em từng bước hoàn thành khóa luận này. Em cũng xin gửi lời cảm ơn đến các anh chị và các bạn trong nhóm nghiên cứu của thầy Nguyễn Hoài Sơn đặc biệt là cô Bùi Thị Lan Hương đã nhiệt tình hỗ trợ về mặt ý tưởng và kinh nghiệm để em có thể hoàn thành khóa luận này thật tốt. Con xin gửi tới bố mẹ và những người thân trong gia đình lòng biết ơn sâu sắc đã luôn động viên , giúp đỡ cho con vượt qua giai đoạn khó khăn này. Hà Nội, tháng 5 năm 2010 Sinh viên Nguyễn Văn Minh
Tóm tắt Trong thời gian gầ n đây sự phát triể n ma ̣nh mẽ của ha ̣ tầ ng Internet đã cho ra đời những ứng du ̣ng mới thay đổ i hoàn toàn cách tương tác của con người với nhau trên toàn thế giới. Kế t nố i với ba ̣n bè thông qua ma ̣ng Internet trở nên đơn giản hơn bao giờ hế t nhờ những ứng du ̣ng nh ư Chat , Voice Call , Video Conference..Hay như cách thức xem truyề n hình IP TV, xem video theo yêu cầ u thông qua ma ̣ng Internet với chấ t lươ ̣ng cao cũng cho thấ y sự thú vị hơn việc xem tivi truyền thống . Mô ̣ phầ n trong những ứng du ̣ng này được xây dựng dựa trên nền tả ng truyề n tin multicast thời gian thực đươ ̣c đề câ ̣p đế n trong khóa luâ ̣n . Truyề n tin multicast thời gian thực trên ma ̣ng ngang hàng là mô ̣t nhánh trong truyề n tin multicast thời gian thực trên ma ̣ng Internet . Khác với các mô hình Client - Server truyề n thố ng , mô hình ma ̣ng ngang hàng có những đă ̣c trưng riêng biê ̣t . Với mô hinh ma ̣ng ngang hàng người thiế t kế có thể tâ ̣n du ̣ng băng thông và khả năng lưu ̀ trữ của các máy tham gia ma ̣ng thay vì tâ ̣p trung tải vào m ột số máy chính như các server trong mô hinh Client-Server. Điể m ma ̣nh này của mô hình mạng ngang hàng đã ̀ làm cho các nghiên cứu về truyền tin multicast cũng như video str eaming trên ma ̣ng ngang hàng ngày càng nhiều khi mà các nghiên cứu trên mô hình client -server đã gầ n như không thể tố i ưu hơn nữa. Khóa luận tôi trình bày nhằm đưa ra một giải pháp xây dựng cây multicast đa luồng thời gian thực trên mạng ngang hàng có cấu trúc với mong muố n đáp ứ ng đươ ̣c các yêu cầu đăc trưư g như đảm bảo đô ̣ trễ ta ̣i các node tham gia ma ̣ng không quá lớn và độ trễ giữa các luồng nhận được tại mỗi node chênh lệch nhau nhỏ . Thiết kế được đưa ra trong khóa luận dựa trên giao thức DHT và mô hình mạng Chord , kết quả mô phỏng và đánh giá bước đầu đã cho kết quả tốt. Tuy nhiên cần nhiều nghiên cứu cải tiến hơn nữa nhằm đạt hiệu quả cao nhất.
Mục lục Mở đầu .............................................................................................................................2 Chương 1. Truyền tin multicast thời gian thực ...............................................................3 1.1. Tổng quan về truyền tin multicast thời gian thực .................................................3 1.1.1. IP Multicast .....................................................................................................4 1.1.2. Multicast tầng ứng dụng .................................................................................6 1.1.3. Các mô hình truyền tin multicast tầng ứng dụng............................................8 1.2. Truyền tin multicast thời gian thực .....................................................................11 Chương 2. Truyền tin multicast đa luồng thời gian thực ..............................................13 2.1. Tổng quan về truyền tin multicast đa luồng........................................................13 2.2. Splitstream...........................................................................................................14 Chương 3. Xây dựng cây multicast đa luồng thời gian thực trên mạng ngang hàng có cấu trúc ..........................................................................................................................25 3.1. Vấn đề cần giải quyết ..........................................................................................25 3.2. Ý tưởng................................................................................................................25 3.3. Thiết kế giải pháp ................................................................................................27 3.3.1. Xây dựng cây multicast ................................................................................29 3.3.2. Duy trì cây multicast khi có node rời khỏi mạng .........................................32 Chương 4. Mô phỏng và đánh giá .................................................................................33 4.1. Chương trình mô phỏng ......................................................................................33 4.1.1. Kiến trúc mạng mô phỏng ............................................................................33 4.1.2. Các tham số trong mạng mô phỏng ..............................................................34 4.2. Kết quả và đánh giá .............................................................................................36 4.2.1. Hiệu quả độ chênh lệch số hop nhận được các luồng tại các node ..............36 4.2.2. Hiệu quả độ cân bằng tải trên toàn hệ thống ................................................38 Chương 5. Kết luận........................................................................................................40 5.1. Kết luận ...............................................................................................................40 5.2. Hướng phát triển tiếp theo của đề tài ..................................................................40
Danh mục hình ảnh Hình 1. Một số mô hình truyền tin ...........................................................................................................3 Hình 2. Mô hình IP Multicast ....................................................................................................................4 Hình 3. Bộ định tuyến trong truyền tin multicast tầng mạng ..................................................................6 Hình 4. Truyền thông multicast tầng mạng và tầng ứng dụng ................................................................7 Hình 5. Giao thức Narada.........................................................................................................................9 Hình 6. Mạng phủ 7 node (a) và cây multicast xây tương ứng (b) ....................................................... 10 Hình 7. Truyền tin mulicast đa luồng .................................................................................................... 13 Hình 8. Bảng định tuyến của node 10233102 trong Pastry .................................................................. 15 Hình 9. Node 10233102 gửi thông điệp m đến node 33321220 ........................................................... 16 Hình 10. Quá trình 1 node join vào group ............................................................................................. 19 Hình 11. Truyền tin multicast trong group Scribe ................................................................................. 20 Hình 12. Quá trình tự sửa cây multicast ............................................................................................... 21 Hình 13. Splitstream F luồng ................................................................................................................. 22 Hình 14. Xác định node cha khi băng thông đi ra vượt quá giới hạn.................................................... 23 Hình 15. Phân chia vùng gần vùng xa cho các node con....................................................................... 26 Hình 16. Bảng Finger Table trong Chord ............................................................................................... 28 Hình 17.Lưu giữ key trong mạng Chord ................................................................................................ 29 Hình 18.Tìm các node con gần và node con xa .................................................................................... 30 Hình 19. Node nhận được các luồng ..................................................................................................... 31 Hình 20. Sửa cây multicast khi có node rời khỏi mạng ......................................................................... 32 Hình 21. Mô hình mạng thực tế ............................................................................................................ 33 Hình 22. Chênh lệch hop lớn nhất giữa các luồng với 1014 node ......................................................... 37 Hình 23. Chênh lệch hop lớn nhất giữa các luồng với 2072 node ......................................................... 38 Hình 24. Hiệu quả cân bằng tải với 1014 node ..................................................................................... 38 Hình 25. Hiệu quả cân bằng tải với 2072 node .................................................................................... 39 1
Mở đầu Trong thời gian gầ n đây ha ̣ tầ ng Internet phát triể n với tố c đô ̣ chóng mă ̣t . Tố c đô ̣ truyề n tải trên ma ̣ng cao đã làm xuấ t hiê ̣n nhiề u ứng du ̣ng mới sử du ̣ng truyề n tin multicast thời gian thực như IP TV , video conference.. Chúng đang làm thay đổ i cách giao tiế p của con người , thu he ̣p mo ̣i khoảng cách vâ ̣t lí , mang đế n cho chúng ta những trải nghiê ̣m mới mẻ về cuô ̣c số ng . Truyề n tin multicast có 2 loại chính là IP multicast và multicast trên tầng ứng dụng. IP Multicast có thể xem là phương pháp multicast chinh thố ng , hiê ̣u quả nhấ t . ́ Tuy nhiên khi triể n khai trên ma ̣ng Internet thì IP Multicast gă ̣p những trở nga ̣i rấ t lớn : đó là chi phí cho viê ̣c thay thế router trên toàn ma ̣ng Inter net (do các router trước đây không có khả năng multicast ) và chi phí cho việc duy trì các cây multicast đó trên hê ̣ thố ng Internet rô ̣ng lớn . Xu hướng truyề n tin multicast vì thế chuyể n sang truyề n tin multicast trên tầ ng ứng du ̣ng . Tuy nhiên khi triể n khai trên truyề n tin multicast trên tầ ng ứng du ̣ng cũng gă ̣p không ít vấ n đề . Thay vì nhân bản các gói tin ta ̣i các router như IP Multicast , cơ chế Multicast trên tầ ng ứng du ̣ng la ̣i nhân bản các gói tin trên các má y đầ u cuố i . Do đó viê ̣c tố i ưu cây multicast nhằ m ta ̣o sự cân bằ ng tải tương đố i trên toàn ma ̣ng cũng là mô ̣t vấ n đề . Mô ̣t vấ n đề nữa phải tinh đế n là đô ̣ trễ . Các gói tin liên tục phải luân ́ chuyể n qua nhiề u vi ̣trí đầ u cuố i nên đô ̣ trễ sẽ tăng cao . Viê ̣c xây dựng đươ ̣c mô ̣t cây multicast phù hơ ̣p để giảm thiể u đô ̣ trễ cũng là mô ̣t vấ n đề quan tro ̣ng . Hiê ̣n nay đã có những nghiên cứu xây dựng cây multicast đa luồ ng trên ma ̣ng ngang hàng có cấ u trúc như Sp litstream. Splitstream đươ ̣c xây dựng dựa trên nề n tảng Pastry, Scribe thêm vào đó mô ̣t số giải pháp để ha ̣n chế tinh tra ̣ng quá tải ta ̣i mô ̣t số ̀ node tham gia ma ̣ng . Nghiên cứu này đã có kết quả tương đối tốt. Giải pháp của khóa luận đưa ra dựa trên ý tưởng và các ưu điểm của mô hình mạng có cấu trúc Chord được sửa đổi để phù hợp với việc xây dựng cây truyề n tin multicast đa luồng. Tóm tắt nội dụng trình bày trong các chương: Chương 1: Truyền tin multicast thời gian thực Chương 2: Truyền tin multicast đa luồng thời gian thực Chương 3: Xây dựng cây multicast đa luồng thời gian thực trên mạng ngang hàng có cấu trúc Chương 4: Mô phỏng và đánh giá Chương 5: Kết luận và hướng phát triển 2
Chƣơng 1.Truyền tin multicast thời gian thực 1.1.Tổng quan về truyền tin multicast thời gian thực Trong điều kiện internet phát triển rất nhanh như hiện nay việc truyền tin trên mạng đã trở nên ngày càng quan trọng và phổ biến. Mục đích cuối cùng của việc truyền tin là gửi thông tin từ máy này đến máy khác nên để đơn giản và trực quan người ta đã mô hình hóa việc truyền tin giữa các máy thành truyền tin giữa các node. Sau đây là 1 số mô hình truyền tin thường gặp : Hình 1. Một số mô hình truyền tin Chương này của khóa luận sẽ làm rõ chi tiết việc truyền tin multicast. Truyền tin multicast được định nghĩa là việc 1 máy truyền tin đến 1 nhóm máy có lựa chọn. Quá trình được mô hình hóa thành các node như trên hình 1: gói tin được nhân bản thành nhiều gói tin khác và gửi đi theo các cạnh của cây multicast . Ta có thể thấy truyền tin multcast tỏ ra rất hiệu quả trên mạng Internet. So sánh với phương pháp truyền tin broadcast (gửi không có lựa chọn) ta thấ y : mô ̣t node sẽ gửi gói tin đế n tấ t cả các node khác mà nó biế t , trong khi những node thực sự cầ n dữ liê ̣u không phải là tấ t cả các node ấ y . Điề u này thực sự làm lang phí băng thông của ̃ mạng. Chính nhờ các đặc tính riêng hiệu quả như vậy mà truyền tin multicast đang trở thành hướng phát triển truyền tin chính so với các phương pháp truyền tin khác. Truyền tin multicast hiện nay được phân loại thành 2 nhánh chính là : IP Multicast 3
(Multicast tầng mạng ) và Multicast trên tầng ứng dụng sẽ được giới thiệu ở mục tiếp theo. 1.1.1.IP Multicast Định nghĩa cơ bản nhất của IP Multicast : IP multicast là cơ chế gửi một thông điệp từ một nguồn duy nhất đến một nhóm chọn lựa các địa chỉ đích thông qua một hạ tầng mạng lớp 3 trong một dòng dữ liệu.. Hình 2. Mô hình IP Multicast Hình 2 trình bày chi tiết về mô hình IP Multicast và cách thức hoạt động của nó. Node gửi là máy Sender với mục tiêu là gửi được gói tin đến cho 2 máy Receiver. Sender sẽ gửi gói tin IP với địa chỉ multicast (cái này sẽ được giải thích chi tiết ở đoạn sau) đến Switch/Router. Switch/Router nhận được gói tin và phân tích địa chỉ multicast trên gói tin IP đó. Sau đó Switch/Router nhân bản gói tin thành n gói tin gửi đi cho n máy có địa chỉ IP Multicast trên (trong hình minh họa là 2 máy có cùng địa chỉ IP Multicast đó). Deering được xem như là người đầu tiên đề xuất giải pháp IP multicast. Năm 1990 IP Multicast ra đời , nó là sự phát triển từ mô hình dịch vụ IP unicast để nhằm nâng cao giao tiếp đa điểm. Mô hình dịch vụ multicast cung cấp hai lợi ích chính: (1) hiệu quả sử dụng băng thông và (2) việc địa chỉ nhóm gián tiếp cho phép redezvous tầng mạng. Đề xuất này của Deering đã mở ra một lĩnh vực mới cho các ứng dụng của IP Multicast. 4
Để truyền multicast thì cần dựa trên khái niệm một nhóm. Nhóm chứa tất cả các máy cùng mong muốn nhận được một dữ liệu. Nhóm này không có giới hạn về vật lý và địa lý, nó có thể nằm ở bất cứ đâu trên mạng Internet. Thực ra ban đầu IP Multicast được phát triển trong các trường đại học và các phòng nghiên cứu nhằm phục vụ chủ yếu cho video streaming với tốc độ cao nhất. Việc quản lý và phân nhóm trong khu vực mạng LAN như vậy sẽ không quá phức tạp. Tuy nhiên khi áp dụng vào mạng Internet thì nó cần 1 định nghĩa nhóm tốt hơn. Và IGMP( IGMP - Internet Group Management Protocal) đã ra đời. Các máy trên mạng Internet muốn nhận dữ liệu thì cần phải gia nhập giao thức quản lý nhóm mạng IGMP. Người dùng có thể quyết định tham gia hoặc rời bỏ nhóm bất cứ lúc nào, và có thể là thành viên của nhiều nhóm multicast cùng lúc. Vai trò của máy tham gia trong quá trình truyền multicast cũng có thể khác nhau: cùng một máy có thể là nguồn gửi trong cây multicast này, nhưng lại là máy nhận trong cây multicast khác. Mỗi một máy cần có địa chỉ multicast là địa chỉ mà mỗi máy tham gia vào nhóm và mong muốn nhận được dữ liệu. IANA ( IANA - Internet Assigned Numbers Authority) sẽ kiểm soát việc gán địa chỉ IP Multicast. IANA gán không gian địa chỉ lớp D được dùng cho IP Multicast. Như vậy tất cả địa chỉ Multicast nằm trong dải: 224.0.0.0 – 239.255.255.255. Ngoài ra, để có thể thực hiện multicast, bộ định tuyến (tiếng Anh: Router) trong mô hình này phải có chức năng multicast(đây là một trong những vướng mắc lớn nhất khiến IP Multicast khó có thể phát triển mạnh). Khi nguồn multicast truyền thông điệp multicast, bộ định tuyến cục bộ sẽ gửi thông điệp đó đến các bộ định tuyến khác được kết nối với mạng có các thành viên của nhóm multicast. Như vậy, trong cây multicast của mô hình truyền tin multicast tầng mạng, các bộ định tuyến đóng vai trò là các node trong thân cây, có nhiệm vụ chuyển tiếp các gói tin multicast tới các máy nhận, là các node lá của cây multicast. Vai trò của bộ định tuyến được minh họa như trong Error! Reference source not found.. 5
Hình 3. Bộ định tuyến trong truyền tin multicast tầng mạng Truyền tin multicast tầng mạng phát huy mạnh mẽ các ưu điểm của truyền thông multicast nói chung. Do các bộ định tuyến đóng vai trò các node trên thân cây multicast, các cạnh của cây cũng chính là các đường truyền vật lý, các gói tin multicast được nhân bản tại các bộ định tuyến làm cho số gói tin lưu thông trên đường truyền giảm tới mức tối thiểu. Do đó, hiệu suất truyền tin của mạng đạt mức tối đa. Với kiến trúc IP Multicast đang sử dụng hiện nay để triển khai trên hệ thống mạng Internet đang thực sự gă ̣p các vấ n đề khó khăn :  Khi triể n khai trên hê ̣ thố ng lớn như Internet các router phải lưu giữ rấ t nhiề u trạng thái của các nhóm . Đây thực sự là mô ̣t vấ n đề lớn khi số nhóm tăng lên cao.  Tạo và duy trì một cây multicast mấ t rấ t nhiề u tài nguyên và thời gian .  Khi có quá nhiều kết nối hoặc một node mạng không hoạt động sẽ gây ra rớt mạng và phải sửa chữa lại nhiều phần của cây.  Việc cân bằng tải và định tuyến lại cây chưa được xử lí thâ ̣t tố t. Vấ n đề lớn nhấ t của viê ̣c triể n khai IP Multicast là chi phí để thay thế lại hạ tầng mạng đã được xây dựng là cực kỳ lớn. Chính vì vậy mà xu hướng chuyển giao sang truyền thông multicast tầng ứng dụng. 1.1.2.Multicast tầng ứng dụng Do nhu cầu sử dụng truyền thông multicast đang ngày càng lớn, trong khi giao thức IP multicast ở tầng mạng chưa đủ để đáp ứng cộng với rất nhiều khó khăn ở trên, xu hướng multicast ngày càng mở rộng sang multicast tầng ứng dụng. 6
Multicast tầng ứng dụng không thay đổi và phá vỡ hệ thống mạng. Thay vào đó, nó chỉ thực hiện chức năng truyền multicast trên các máy cuối ở tầng ứng dụng. Từ tầng ứng dụng sẽ truyền xuống các tầng mạng và tầng giao vận. Ở các tầng thấp hơn, cơ chế hoàn toàn không thay đổi. Hình 4. Truyền thông multicast tầng mạng và tầng ứng dụng (Hình vuông là các router, hình tròn là các máy đầu cuối) Khi truyền multicast ở tầng ứng dụng, các gói tin không được nhân bản tại các bộ định tuyến giống như mô hình multicast nguyên thu ỷ (IP multicast) mà việc nhân bản gói tin sẽ được thực hiện tại các máy đầu cuối. Về mặt logic, các máy đầu cuối tạo nên một mạng phủ và giao thức truyền thông multicast phải xây dựng và duy trì việc truyền multicast trên mạng phủ này. Có hai thông số đo đạc tính chất của việc truyền multicast trên tầng phủ: stress và stretch. Stress được xác định theo từng kết nối và đếm số gói tin được gửi đi bởi một giao thức ở tầng mạng dưới. Stretch được đo bởi mỗi máy và là tỷ lệ của chiều dài từ nguồn đến thành viên ở một mạng phủ theo đường dẫn unicast. Nhìn chung, các giao thức tầng mạng có thể được đánh giá theo ba hướng:  Chất lượng của đường truyền dữ liệu: là chất lượng của cây được đo bởi một số thông số stress, stretch và cấp độ node.  Độ mạnh yế u của tầng phủ: Mỗi máy thường không ổn định như router, các node có thể rời mạng tạm thời hoặc vĩnh viễn làm ảnh hưởng đến các node nhận phía dưới. Độ mạnh yế u của các giao thức tầng ứng dụng được đo bởi việc đo đạc sự mất mát dữ liệu truyền khi các thành viên bị lỗi và thời gian mà nó cần để giao thức có thể khôi phục lại để truyền cho các thành viên khác.  Quá tải : để sử dụng hiệu quả tài nguyên mạng, quá tải điều khiển ở mỗi thành viên nên nhỏ. Đó là một thông số giá thành quan trọng để đo đạc tính mở rộng của thành viên. 7
Do truyền thông multicast tầng ứng dụng phải gửi các gói tin giống nhau trên cùng một kết nối, hiệu suất của mô hình này không thể tối ưu được bằng truyền thông multicast trên tầng mạng. Tuy nhiên, truyền tin multicast tầng ứng dụng vẫn có khả năng giảm tải nhiều cho đường truyền và nguồn tin multicast. 1.1.3.Các mô hình truyền tin multicast tầng ứng dụng Đề có thể truyền tin multicast được thì trước tiên cần có một cấu trúc topology của mạng phủ. Trong topology của tầng mạng phủ - tầng mạng ứng dụng, các máy tính liên kết với nhau. Mỗi máy tính gọi là một node mạng liên kết ảo với các node khác. Việc xem máy tính là 1 node ảo được sử dụng rất nhiều trong cấu trúc của các mạng ngang hàng như Chord , Pastry do tính chất phân tán và không xác định được về phương diện địa lý của các máy thật. Dựa vào topology đó, các node tương ứng với các node trên cây multicast (node lá hoặc node con), liên kết ảo sẽ tạo nên cơ chế truyền tin từ node lá sang các node con. Có hai cách thức truyền thông multicast: multicast trên mạng có cấu trúc (tree- first) và multicast trên mạng không có cấu trúc (mesh-first). Sau đây ta sẽ nghiên cứu phân tích và lựa chọn một hướng truyền thông phù hợp cho video streaming. Multicast theo hướng mesh-first Trong cách tiếp cận mesh-first, các node trước khi tham gia vào cây phải là thành viên của một mạng phủ nào đó, và giữa chúng đã tồn tại các liên kết với nhau dạng lưới. Sau đó, cây multicast sẽ được xây dựng dựa trên các liên kết của mạng phủ này. Giao thức Narada là một trong những giao thức multicast tầng ứng dụng đầu tiên và theo hướng mesh-first. Nó chỉ định một máy đặc biệt là Rendezvous Point (RP) được sử dụng để theo dõi sự gia nhập của một thành viên mới. Tất cả các giao thức multicast tầng mạng cũng sử dụng một hoặc một số các thực thể tương tự như RP trong Narada để tạo cơ chế gia nhập. Xây dựng mesh: khi một node mới muốn gia nhập nhóm multicast, nó sẽ có danh sách thành viên đã gia nhập vào mesh do RP cung cấp. Sau đó thành viên mới sẽ lựa chọn ngẫu nhiên một số các thành viên và gia nhập vào mesh và coi như là láng giềng của những thành viên đó. Quy trình gia nhập thành công khi mà ít nhất một thành viên trong danh sách đồng ý để thành viên mới là láng giềng mesh. Khi gia nhập vào mesh, thành viên mới bắt đầu định kỳ trao đổi thông điệp với các lang giềng mesh của nó. Bất cứ khi nào một node gia nhập hoặc một thành viên rời 8
nhóm, nhóm này sẽ thay đổi thông tin của tất cả thành viên. Do đó, mỗi thành viên trong nhóm giữ trạng thái của tất cả các thành viên trong nhóm. Thông tin này thường xuyên được cập nhật. Việc lưu trữ các thông tin trạng thái của tất cả thành viên trong nhóm ở mỗi thành viên dẫn tới quá tải kiểm soát lớn, quá tải kiểm soát lên tới (O(N2)) với N là kích thước của nhóm. Do đó, giao thức Narada hiệu quả chỉ khi kích thước nhóm Multicast là nhỏ. Hình 5. Giao thức Narada Khi cả thành viên D và E cùng lỗi, mesh phân chia thành 2 phần. Do đó, các thành viên A, B và C sẽ ngừng nhận được thông tin trạng thái từ F, G và H; và ngược lại. Mỗi thành viên có thể khảo sát các thành viên từ khi nó ngừng nhận được thông điệp trạng thái để tạo ra một kết nối mới và sửa các phần. Chý ý rằng, việc sửa không yêu cầu sự hỗ trợ của RP và do đó vẫn có thể thực hiện được ngay cả khi RP bị lỗi. Đường truyền dữ liệu: các thành viên của một nhóm thực hiện một giao thức định tuyến để tính ra các đường đi unicast trong mesh. Sự chọn lọc của mesh: các đường truyền dữ liệu trong Narada là các cây nhịp của mesh. Do đó, chất lượng của đường truyền dữ liệu phụ thuộc vào chất lượng của các kết nối là một phần của mesh. Khi một thành viên mới tham gia, hoặc khôi phục từ các phần, một tập ngẫu nhiên các cạnh sẽ được thêm vào mesh. Do đó, sự chọn lọc định kỳ cần phải được thực hiện với các cạnh để cải tiến chất lượng của các đường truyền dữ liệu. Việc thêm cạnh (J,G) là có ích bởi vì một số lượng lớn các node unicast 9
có thể được thay bằng một cạnh mới. Cạnh (A, C) được xoá đi. Quyết định để thêm hoặc bỏ đi một cạnh của mess được thực hiện giữa cạnh của 2 điểm cuối. Ưu điểm của mô hình này là khả năng chịu lỗi cao do mỗi node tồn tại nhiều liên kết với các node khác trong mạng. Tuy nhiên nhược điểm của mô hình này là rất khó để thực hiện cân bằng tải và cân bằng độ trễ giữa các node do phụ thuộc vào kiến trúc mạng phủ. Với nhược điểm này thì không phù hợp với truyền video streaming do các gói tin có độ trễ khác nhau, gói tin gửi trước có thể đến sau, gói tin gửi sau đến trước. Việc không cân bằng độ trễ sẽ làm ảnh hưởng đến việc trình diễn dữ liệu. Multicast theo hướng tree-first Trong cách tiếp cận tree-first, các node khi tham gia vào cây multicast sẽ tự tìm cho mình một node cha từ các node thành viên trước đó của cây. Việc chọn node cha thường được thực hiện dựa trên một số tiêu chí như cân bằng băng thông giữa các node hoặc đảm bảo độ sâu của cây cân bằng giữa các nhánh. Ưu điểm của mô hình này là các node có thể chọn node cha, do đó có thể tránh được tình trạng một node nào đó phải chịu tải quá cao. Hình 6. Mạng phủ 7 node (a) và cây multicast xây tương ứng (b) Scribe là hệ thống multicast tầng ứng dụng mở rộng được xây dựng trên Pastry. Để tạo nhóm multicast, Scribe tạo ra một khoá Pastry tự động được biết như Id của một nhóm. Cây multicast tương ứng với một nhóm được thực hiện bằng một tập hợp các bộ định tuyến Pastry từ một node thành viên đến nhóm gốc của Id. Bằng việc truyền lùi lại trên đường dẫn, các gói tin multicast từ gốc tới mỗi thành viên. SplitStream là hướng phát triển sau của Scribe mà tập trung vào việc phân bổ truyền thông. Ngoài Scribe là hệ thống multicast tầng ứng dụng xây dựng trên Pastry, ta cũng có thể xây dựng multicast trên các mạng ngang hàng có cấu trúc DHT khác như CAN, CHORD… 10
Mạng ngang hàng có cấu trúc thuộc nhánh các mạng ngang hàng phân tán trong các mô hình mạng ngang hàng. Mạng ngang hàng có cấu trúc khắc phục nhược điểm của mạng không cấu trúc bằng cách sử dụng hệ thống DHT (Bảng Băm Phân Tán, tiếng anh: Distributed Hash Table). Hệ thống này định nghĩa liên kết giữa các nút mạng trong mạng phủ theo một thuật toán cụ thể, đồng thời xác định chặt chẽ mỗi nút mạng sẽ chịu trách nhiệm đối với một phần dữ liệu chia sẻ trong mạng. Với cấu trúc này, khi một máy cần tìm một dữ liệu, nó chỉ cần áp dụng một giao thức chung để xác định nút mạng nào chịu trách nhiệm cho dữ liệu đó và sau đó liên lạc trực tiếp đến nút mạng đó để lấy kết quả. Phát triển trên mạng ngang hàng có cấu trúc sẽ tận dụng ưu điểm là khả năng dễ mở rộng do cấu trúc liên kết rõ ràng; việc tìm kiếm thông tin nhanh hơn. Giao thức tìm kiếm chung trong mạng sẽ đảm bảo thông tin được tìm kiếm chính xác. Đây là một lợi thế rất quan trọng khi áp dụng mạng ngang hàng có cấu trúc để triển khai truyền tin multicast, do truyền tin multicast yêu cầu khả năng định tuyến của mạng phủ để xây dựng nên cây multicast. Ngoài ra, tài nguyên được phân bố một cách hợp lý để không có một máy tính nào lưu giữ quá nhiều dữ liệu dẫn đến quá tải thông tin định tuyến. Do mạng là có cấu trúc nên các thông điệp chuyển đi giữa các máy tí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 11
lượng có thể chấp nhận được. Đó chí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 12
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 13
đó 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 đí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 chí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. 14
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. 15