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

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